Scribd Logo
Upload

Welcome to Scribd!

  • 66 views

    Minimize Subject To The Constraints: X X X X

    Uploaded by

    Potnuru Vinay
    The document describes solving a linear programming problem using the two-phase method. In phase I, the problem is transformed by introducing artificial variables and minimizing their sum to obtain a starting feasible basis. In phase II, the original objective function is optimized using this starting basis. The example problem is to minimize z=2x1+x2 subject to the constraints 3x1+x2≥9 and x1+x2≥6. Phase I yields a starting basis of x1=3/2, x2=9/2. Phase II then directly solves the original problem to find the optimal solution as x1=3/2, x2=9/2, with minimum z=15/2.

    Copyright:

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

    Minimize Subject To The Constraints: X X X X

    Uploaded by

    Potnuru Vinay
    66 views16 pages
    The document describes solving a linear programming problem using the two-phase method. In phase I, the problem is transformed by introducing artificial variables and minimizing their sum to obtain a starting feasible basis. In phase II, the original objective function is optimized using this starting basis. The example problem is to minimize z=2x1+x2 subject to the constraints 3x1+x2≥9 and x1+x2≥6. Phase I yields a starting basis of x1=3/2, x2=9/2. Phase II then directly solves the original problem to find the optimal solution as x1=3/2, x2=9/2, with minimum z=15/2.

    Original Description:

    simple3a

    Original Title

    06Simplex3A

    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 solving a linear programming problem using the two-phase method. In phase I, the problem is transformed by introducing artificial variables and minimizing their sum to obtain a starting feasible basis. In phase II, the original objective function is optimized using this starting basis. The example problem is to minimize z=2x1+x2 subject to the constraints 3x1+x2≥9 and x1+x2≥6. Phase I yields a starting basis of x1=3/2, x2=9/2. Phase II then directly solves the original problem to find the optimal solution as x1=3/2, x2=9/2, with minimum z=15/2.

    Copyright:

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

    Minimize Subject To The Constraints: X X X X

    Uploaded by

    Potnuru Vinay
    The document describes solving a linear programming problem using the two-phase method. In phase I, the problem is transformed by introducing artificial variables and minimizing their sum to obtain a starting feasible basis. In phase II, the original objective function is optimized using this starting basis. The example problem is to minimize z=2x1+x2 subject to the constraints 3x1+x2≥9 and x1+x2≥6. Phase I yields a starting basis of x1=3/2, x2=9/2. Phase II then directly solves the original problem to find the optimal solution as x1=3/2, x2=9/2, with minimum z=15/2.

    Copyright:

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

    Minimize

    z 5 x1 7 x2

    Subject to the constraints

    2 x1 3 x2 42
    3 x1 4 x2 60
    x1 x2 18
    x1 , x2 0
    Ans: x1=12, x2=6 Soln(= Min z) = 102

    Introducing the surplus and artificial


    variables, R1, R2, the LPP is modified as
    follows:
    Minimize z 5 x1 7 x2 MR1 MR2 MR3
    Subject to the constraints
    2 x1 3 x2 s1
    3 x1 4 x2
    x1 x2

    R1
    s2
    s3

    42

    R2

    60

    R3 18

    x1 , x2 , s1 , s2 , s3 , R1 , R2 , R3 0

    Basic z
    z

    x1
    x2
    s1
    -5+6M -7+8M -M
    1
    -5
    -7
    0

    s2
    -M
    0

    s3
    -M
    0

    R1
    0
    -M

    R2
    0
    -M

    R1

    -1

    42

    R2

    -1

    60

    R3

    -1

    18

    1 2M
    1
    3 3

    7 5M

    -M
    3 3

    0 98+8M

    x2

    2/3

    -1/3

    1/3

    14

    R2

    1/3

    4/3

    -1

    -4/3

    R3

    1/3

    1/3

    -1

    -1/3

    7 8M
    -M
    3 3

    R3 Sol
    0 120M
    -M
    0

    Basic z
    z

    x1
    1 2M

    1 3 3

    x2

    s1

    s2

    s3

    R1

    7 5M

    3 3 -M

    x2

    2/3

    -1/3

    R2

    1/3

    4/3

    -1

    R3

    1/3

    1/3

    1 M

    4 4

    7 M

    -M - M
    4 4

    x2

    3/4

    -1/4

    1/4

    15

    s1

    1/4

    -3/4

    -1

    3/4

    R3

    1/4

    1/4

    -1

    -1/4

    7 8M

    -M 3 3

    R2

    R3

    Sol

    0 98+8M

    1/3

    14

    -4/3

    -1 -1/3

    7 5M

    4 4

    0 105+3M

    Basic z

    x1

    x2

    s1

    s2

    7 M

    4 4

    s3

    R1

    R2
    7 5M
    -M -M 4 4

    R3

    Sol

    1 M

    4 4

    x2

    3/4

    -1/4

    1/4

    15

    s1

    1/4

    -3/4

    -1

    3/4

    R3

    1/4

    1/4

    -1

    -1/4

    -2

    -M

    x2

    -1

    -3

    s1

    -1

    -1

    -1

    x1

    -4

    -1

    12

    105+3M

    2-M -1-M 102

    Basic z

    x1

    x2

    s1

    s2

    s3

    R1

    R2

    R3

    Sol

    2-M -1-M 102

    -2

    -M

    x2

    -1

    -3

    s1

    -1

    -1

    -1

    x1

    -4

    -1

    12

    -1

    -1

    1-M

    1-M

    x2

    -3

    -2

    s3

    -1

    -1

    -1

    x1

    -3

    -4

    12

    2-M 102

    Basic z

    x1

    x2

    s1

    s2

    s3

    R1

    R2

    R3

    Sol

    -1

    -1

    1-M

    1-M

    2-M

    102

    x2

    -3

    -2

    s3

    -1

    -1

    -1

    x1

    -3

    -4

    12

    This is the optimal tableau.

    Optimal solution: x1=12, x2=6


    Optimal z = Minimum z = 102

    Graphical illustration

    (0, 18)
    (0, 15)
    (0, 14)

    (12,6)

    (0, 0)

    (18, 0) (20, 0) (21, 0)

    TWO PHASE METHOD


    The Big M method involves manipulation
    with small and large numbers and so is not
    suited to a computer. We now look at the
    Two-Phase method. As the name suggests,
    the method consists of two phases: In phase
    I, we minimise the sum of all the artificial
    variables subject to the same constraint
    equations. If the original problem had a
    feasible solution this new problem will give

    a solution with all artificial variables


    zero. Taking this as a starting BFS, we
    solve the original problem. We illustrate
    by an example.

    Consider the LPP:


    Minimize

    z 2 x1 x2

    Subject to the constraints

    3 x1 x2 9
    x1 x2 6
    x1 , x2 0

    Introducing the surplus and artificial


    variables, R1, R2, the LPP is same as:
    Minimize

    z 2 x1 x2

    Subject to the constraints

    3 x1 x2 s1
    x1 x2

    R1

    s2

    R2 6

    x1 , x2 , s1 , s2 , R1 , R2 0

    Phase I:
    Minimize

    r R1 R2

    Subject to the constraints

    3 x1 x2 s1
    x1 x2

    R1

    s2

    R2 6

    x1 , x2 , s1 , s2 , R1 , R2 0
    We now solve it by Simplex method.

    Basic r

    x1

    x2

    s1

    s2

    R1

    R2

    Sol.

    2
    0

    -1
    0

    -1
    0

    0
    -1

    0
    -1

    15
    0

    4
    0

    R1

    -1

    R2

    -1

    2/3

    1/3

    -1

    -4/3

    x1

    1/3

    -1/3

    1/3

    R2

    2/3

    1/3

    -1

    -1/3

    -1

    -1

    x1

    -1/2

    1/2

    1/2

    -1/2

    3/2

    x2

    1/2

    -3/2 -1/2

    3/2

    9/2

    Note that Phase I has ended as min r =0.


    Phase II

    Now we solve the original LPP with


    3
    9
    the starting BFS: x1 , x2
    2
    2
    Note that the starting Simplex tableau is
    same as the last tableau except for the first
    row which is our z-Row. Since R1, R2 have
    served their purpose (of giving a starting
    BFS), we suppress their columns.

    Basic z

    x1

    x2

    s1

    s2

    0
    -1

    -1/2 -1/2
    0
    0

    R1

    R2

    Sol.

    0
    -2

    x1

    -1/2

    1/2

    3/2

    x2

    1/2

    -3/2

    9/2

    This is the optimal tableau.


    Optimal solution: x1 = 3/2, x2 = 9/2

    Optimal value : Min z = 15/2

    15/2
    0

    You might also like