Scribd Logo
Upload

Welcome to Scribd!

  • 161 views

    Big M Method: REC, Deapartment of Mathemati Cs 1

    Uploaded by

    Amarnath Chandran
    The document describes the Big M method for solving linear programming problems with equality or greater than constraints. It involves introducing slack, surplus, and artificial variables to transform the problem into standard form. The example problem is solved using the Big M method in multiple iterations. The optimal solution is found when all reduced costs are greater than or equal to zero.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Big M Method: REC, Deapartment of Mathemati Cs 1

    Uploaded by

    Amarnath Chandran
    161 views18 pages
    The document describes the Big M method for solving linear programming problems with equality or greater than constraints. It involves introducing slack, surplus, and artificial variables to transform the problem into standard form. The example problem is solved using the Big M method in multiple iterations. The optimal solution is found when all reduced costs are greater than or equal to zero.

    Original Title

    Big M Method

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the Big M method for solving linear programming problems with equality or greater than constraints. It involves introducing slack, surplus, and artificial variables to transform the problem into standard form. The example problem is solved using the Big M method in multiple iterations. The optimal solution is found when all reduced costs are greater than or equal to zero.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    161 views18 pages

    Big M Method: REC, Deapartment of Mathemati Cs 1

    Uploaded by

    Amarnath Chandran
    The document describes the Big M method for solving linear programming problems with equality or greater than constraints. It involves introducing slack, surplus, and artificial variables to transform the problem into standard form. The example problem is solved using the Big M method in multiple iterations. The optimal solution is found when all reduced costs are greater than or equal to zero.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 18

    Big M Method

    REC, Deapartment Of Mathemati 1


    cs
    Introduction:

    In some problems, the slack variable can not


    provide the initial basic feasible solution.
    In these problems atleast one of the
    constraints is of ‘ = ‘ or ‘ ≥ ’ type.
    To solve such linear programming problems,
    there are two methods available.
    (i) The Big M – method or Method of
    penalties (ii) The Two phase Method.
    REC, Deapartment Of Mathemati 2
    cs
    Practical steps:
    • Step1: Express the linear progrmming problem in the
    standard form by introducing slack and /or surplus
    variables, if necessary.
    • Step2: Add slack variables in case of constraints having ( ≤
    symbol)
    • Step3: Detect surplus variables and artificial variables (say
    R1, R2) in case of constraints having ≥ sign.
    • Step 4: Add artificial variables in case of constraints
    having = sign.
    • Step 5: The contribution of artificial variables will be
    detected in the objective function.

    REC, Deapartment Of Mathemati 3


    cs
    EXAMPLE 1
    • Solve the following LPP using big M
    method
    Maximise Z = 2x1 + x2 + x3

    subject to 4x1 + 6x2 + 3x3 ≤ 8


    3x1 - 6x2 - 4x3 ≤ 1
    2x1 + 3x2 - 5x3 ≥ 4

    REC, Deapartment Of Mathemati 4


    cs
    STEP 1: Formation of LP problem after introducing slack
    and surplus variables :

    Max Z = 2x1 + x2 + x3 + 0s1 + 0s2 + 0s3 - M R1

    subject to 4x1 + 6x2 + 3x3 + s1 = 8


    3x1 - 6x2 - 4x3 + s2 = 1
    2x1 + 3x2 - 5x3 - s3 + R1 = 4
    Here: s1, s2 = slack variables
    s3 = surplus variable
    R1 = Artificial variable
    M = Penalties REC, cs
    Deapartment Of Mathemati 5
    Initial Iteration:
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1

    0 S1 8 4 6 3 1 0 0 0

    0 S2 1 3 -6 -4 0 1 0 0

    -M R1 4 2 3 -5 0 0 -1 1
    Zj - Cj

    Note: Verify the basic variables (S1, S2, R1) forms the unit matrix.
    REC, Deapartment Of Mathemati 6
    cs
    Initial Iteration:
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1

    0 S1 8 4 6 3 1 0 0 0

    0 S2 1 3 -6 -4 0 1 0 0

    -M R1 4 2 3 -5 0 0 -1 1
    Zj - C j -4M -2M-2 -3M-1 5M-1 0 0 M 0

    Compute (Zj – Cj) Since there are some (Zj – Cj) < 0, the current basic
    feasible solution is not optimal.
    REC, Deapartment Of Mathemati 7
    cs
    Initial Iteration:
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1

    0 S1 8 4 6 3 1 0 0 0

    0 S2 1 3 -6 -4 0 1 0 0

    -M R1 4 2 3 -5 0 0 -1 1
    Zj - Cj -4M -2M-2 -3M-1 5M-1 0 0 M 0

    Here the atmost negative integer is - 3M – 1. So the new entering variable


    is x2
    REC, Deapartment Of Mathemati 8
    cs
    Initial Iteration:
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1 θ

    0 S1 8 4 6 3 1 0 0 0 1.33

    0 S2 1 3 -6 -4 0 1 0 0 -

    -M R1 4 2 3 -5 0 0 -1 1 1.33

    Zj - Cj -4M -2M-2 -3M-1 5M-1 0 0 M 0

    To find leaving variables: Compute θ = XB / X2


    REC, Deapartment Of Mathemati
    and select minimum value. 9
    cs
    Initial Iteration:
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1 θ

    0 S1 8 4 6 3 1 0 0 0 1.33

    0 S2 1 3 -6 -4 0 1 0 0 -

    -M R1 4 2 3 -5 0 0 -1 1 1.33

    Zj - Cj -4M -2M-2 -3M-1 5M-1 0 0 M 0

    Key Row indicates that out going variable is R1 and key column indicates
    that incoming variable is x
    REC,
    2 Deapartment Of Mathemati 10
    cs
    First Iteration:
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1 θ

    0 S1

    0 S2

    1 x2 4/3 2/3 1 -5/3 0 0 -1/3 1/3

    Zj - Cj -4M -2M-2 -3M-1 5M-1 0 0 M 0

    Replacing the out going variable R1 by the incoming variable x2 togother


    with its contribution and compute new valus of key row as under:
    New values of Key row = old values of key row / key element
    REC, Deapartment Of Mathemati 11
    cs
    Calculating the new values of other rows:

    • New S1 = old S1 – ( corresponding column


    coefficient ) x ( New values of key row)
    Old S1 = ( 8 4 6 3 1 0 0 0)
    Column coefficient = 6
    New values of key row = ( 4/3 2/3 1 -5/3
    0 0 -1/3 1/3)
    New S1 = (0 0 0 13 1 0 2 -2)
    Similiarly S2
    REC, Deapartment Of Mathemati 12
    cs
    First Iteration Table :
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1 θ

    0 S1 0 0 0 13 1 0 2 -2 0

    0 S2 9 7 0 -14 0 1 -2 2 -

    1 x2 4/3 2/3 1 -5/3 0 0 -1/3 1/3 -


    Zj - C j 4/3 -4/3 0 -8/3 0 0 -1/3 1/3 +M

    Since there are some (Zj – Cj ) < 0, the current basic feasible solution is not
    optimal. REC, Deapartment Of Mathemati 13
    cs
    Second Iteration Table :
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1 θ

    1 x3 0 0 0 1 1/13 0 2/13 -2/13 -

    0 S2 9 7 0 0 14/13 1 2/13 -2/13 9/7

    1 x2 4/3 2/3 1 0 5/39 0 -1/13 1/13 2


    Zj - C j 4/3 -4/3 0 0 8/39 0 1/13 M-1/13

    Since there are some (Zj – Cj ) < 0, the current basic feasible solution is not
    optimal. REC, Deapartment Of Mathemati 14
    cs
    Third Iteration Table :
    Cj 2 1 1 0 0 0 -M

    CB YB XB x1 x2 x3 S1 S2 S3 R1 θ

    1 x3 0 0 0 1 1/13 0 2/13 -2/13

    2 x1 9/7 1 0 0 2/13 1/7 2/91 -2/91

    1 x2 10/21 0 1 0 1/39 -2/21 -25/273 325/3


    549
    Zj - Cj 64/21 0 0 0 16/39 4/21 29/273

    Since all (Zj – Cj ) ≥ 0, the current basic feasible solution is optimal.


    REC, Deapartment Of Mathemati 15
    cs
    Conclusion:
    The optimal solution is max Z = 64/ 21,
    X1 = 9/ 7,
    X2 = 10/ 21,
    X3 = 0,

    REC, Deapartment Of Mathemati 16


    cs
    Solve the following problem by
    simplex method:
    • Maximize: z=x1+2x2+3x3-x4
    Subject to
    X1+2x2+3x3 = 15
    2x1+x2+5x3 ≥ 20
    X1+2x2+x3+x4 ≥ 10
    X1,x2,x3,x4 ≥ 0
    Answer: Z=15,x1 = 5/2, x2=5/2, x3=5/2,x4=0
    REC, Deapartment Of Mathemati 17
    cs
    Solve the following problem by
    simplex method:
    • Minimize: z=4x1+3x2
    Subject to
    2X1+x2 ≥ 10
    -3x1+2x2 ≤ 6
    X1+x2 ≥ 6
    X1,x2, ≥ 0
    Answer: min Z=22,x1 = 4, x2=2
    REC, Deapartment Of Mathemati 18
    cs

    You might also like