Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    Simplex Method: Minimization Two Phase Method

    Uploaded by

    melbe5jane5quiamco

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Simplex Method: Minimization Two Phase Method

    Uploaded by

    melbe5jane5quiamco
    7 views27 pages

    Original Title

    3423973

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    7 views27 pages

    Simplex Method: Minimization Two Phase Method

    Uploaded by

    melbe5jane5quiamco

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 27

    Simplex Method

    LECTURE 14

    MINIMIZATION
    TWO PHASE METHOD
    BY
    DR. ARSHAD ZAHEER
    Two Phase Method
    Illustration

    Minimize f=4x1+ x2 (Objective Function)


    Subject to: (Constraints)
    3x1+ x2 = 3
    4x1+ 3x2 ≥6
    x1+ 2x2 ≤4
    x1, x2 ≥ 0 (Non-Negativity
    Constraints)
    Inequalities Constraints in Equation Form

    Let S1 and S2 be the surplus and slack variables for


    second and third constraints, respectively.
    Minimize f =4x1+ x2 (Objective Function)
    Subject to: (Constraints)
    3x1+ x2 = 3 …………. (1)
    4x1+ 3x2 – S1 = 6 …………. (2)
    x1+ 2x2 + S2 = 4 …………. (3)
    x1, x2, S1 , S2≥ 0
    Initial solution

    Arbitrary values =# of Variables -- # of Equations


    4 - 2=2
    Let x1=
    This 0, x2 = 0 cannot be called as
    situation
    Putting above This is
    values inagainst the
    objective basic rules of
    function
    initial feasible solutionasbecause
    Mathematics it is
    the 0 cannot be not
    (f =5x1+ 4x2) and equation 1-3,
    satisfying the equalcondition.
    to 3. In order to
    make it f =feasible
    0
    we need to add
    0 = 3 (Contradiction)
    Artificial variables In equations having
    S1 = -6 (Violation)
    contradictions and violation
    S2 = 4
    This is against the non negativity
    constraint that X must be non zero.
    Artificial Variables

    Let A1 and A2 be the artificial variables for first and


    second equation respectively.
    Minimize: f =4x1+ x2 (Objective Function)
    Subject to: (Constraints)
    3x1+ x2 + A1= 3 …………. (4)
    4x1+ 3x2 – S1 + A2= 6 …………. (5)
    x1+ 2x2 + S2 = 4 …………. (6)
    x1, x2, S1 , S2 , A1 + A2 ≥ 0
    Solution of Artificial Variable

    Questions which involve artificial variables can not


    solve straight away. We have to use following two
    methods to solve it

    1. Penalty Method or M-Method (Big M


    Method)
    2. Two Phase Method
    In this lecture we will solve this problem by
    Two Phase Method
    Solution by Two Phase Method

    Phase I:
    In Phase I we introduce artificial objective function
    Capital “F” as the sum of artificial variables
    introduced in the constraints. We substitute the
    values of artificial variables from the constraints
    and get artificial objective function.
    We have Two artificial variables so the artificial
    objective function would be as under;
    F = A1 + A2
    Artificial Objective Function

    A1
    Use Equation no 4 to find the value of A1
    3x1+ x2 + A1= 3
    A1 = 3 - 3x1- x2
    A2
    Use Equation no 5 to find the value of A2
    4x1+ 3x2 – S1 + A2= 6
    A2= 6 - 4x1- 3x2 + S1
    F = A 1 + A2
    Putting the values of A1 and A2
    F = ( 3 – 3X1- X2) + (6 – 4X1- 3X2 + S1)
    =9 - 7x1-4 x2 + S1

    Minimize f = 4x1+ x2
    F=9 - 7x1-4 x2 + S1
    Subject to:
    3x1+ x2 + A1 = 3 …………. (4)
    4x1+ 3x2 – S1 + A2= 6 …………. (5)
    x1+ 2x2 + S2 = 4 …………. (6)
    x x , S , S , A + A ≥0
    Initial Feasible Solution

    Arbitrary values =# of Variables -- # of Equation


    6 - 3=3
    This
    Let x1=solution is= called
    0, x2 = 0, S1 0 initial feasible
    solution because
    Putting above values initobjective
    satisfies the all Non
    functions
    negativity
    and equation constraint
    4-6, and also do not
    have any
    F = 9 contradiction or violation
    f=0
    A1 = 3
    A2 = 6
    S2 = 4
    Initial
    For leaving variable Tableau
    the rule is same as maximization,
    the variable with minimum ratio;A1

    Basics X1 X2 S1 S2 A1 A2 RHS Ratio


    A1 3 1 0 0 1 0 3 3/3=1(Min)
    A2 4 3 -1 0 0 1 6 6/4=1.5
    S2 1 2 0 1 0 0 4 4/1=4
    f -4 -1 0 0 0 0 0
    F 7 4 -1 0 0 0 9
    ↑
    In artificial function of minimization we select the
    maximum positive as the entering variable which is
    X1
    Optimal solution for Artificial objective Function

    The solution of artificial objective


    function is said to be optimal when
    artificial objective functions
    coefficients become non-positive or
    zero
    Calculation

    1
    New Pivot Row = X Old Pivot Row
    Pivot No.
    1
    New Pivot
    X [3 1 0 0 1 0 3]
    Row =
    3
    [1 1/3 0 0 1/3 0 1]
    Calculation

    New Row = Old Row – Pivot Column Coefficient x New Pivot Row
    New A2 Row = [4 3 -1 0 0 1 6]
    - (4)[1 1/3 0 0 1/3 0 1]
    = [0 5/3 -1 0 -4/3 1 2]
    New S2 Row =[1 2 0 1 0 0 4]
    - (1) [1 1/3 0 0 1/3 0 1]
    = [0 5/3 0 1 -1/3 0 3]
    New f Row = [-4 -1 0 0 0 0 0]
    - (-4) [1 1/3 0 0 1/3 0 1]
    = [0 1/3 0 0 4/3 0 4]
    New F Row = [7 4 -1 0 0 0 9]
    - (7) [1 1/3 0 0 1/3 0 1]
    = [0 5/3 -1 0 -7/3 0 2]
    Tableau I

    Basics X1 X2 S1 S2 A1 A2 RHS Ratio


    X1 1 1/3 0 0 1/3 0 1 1÷1/3=3
    2 ÷5/3=1.2
    A2 0 5/3 -1 0 -4/3 1 2
    (Min)
    S2 0 5/3 0 1 -1/3 0 3 3/5 ÷ 3=1.8
    f 0 1/3 0 0 4/3 0 4
    F 0 5/3 -1 0 -7/3 0 2
    ↑
    Still there is one positive coefficient so we
    need to make further tableau
    Calculation

    1
    New Pivot Row = X Old Pivot Row
    Pivot No.
    1
    New Pivot
    X [0 5/3 -1 0 -4/3 1 2]
    Row =
    5/3
    [0 1 -3/5 0 -4/5 3/5 6/5]
    Calculation

    New Row = Old Row – Pivot Column Coefficient x New Pivot Row
    New X1 Row =
    [1 1/3 0 0 1/3 0 1]
    -(1/3)[0 1 -3/5 0 -4/5 3/5 6/5]
    = [1 0 1/5 0 3/5 -1/5 3/5]

    New S2 Row =
    [0 5/3 0 1 -1/3 0 3]
    -(5/3)[0 1 -3/5 0 -4/5 3/5 6/5]
    = [0 0 1 1 1 -1 1]
    Calculation

    New f Row =
    [0 1/3 0 0 4/3 0 4]
    -(1/3)[0 1 -3/5 0 -4/5 3/5 6/5]
    = [0 0 1/5 0 8/5 -1/5 18/5]
    New F Row
    [0 5/3 -1 0 -7/3 0 2]
    -(5/3)[0 1 -3/5 0 -4/5 3/5 6/5]
    = [0 0 0 0 -1 -1 0]
    Tableau II

    Basics X1 X2 S1 S2 A1 A2 RHS
    X1 1 0 1/5 0 3/5 -1/5 3/5
    X2 0 1 -3/5 0 -4/5 3/5 6/5
    S2 0 0 1 1 1 -1 1
    f 0 0 1/5 0 8/5 -1/5 18/5
    F 0 0 0 0 -1 -1 0

    Now there is no positive value in the artificial


    function so this is the end of Phase I
    Phase II

    In phase two rewrite the previous tableau by dropping


    the artificial objective function and artificial
    variables
    Basics X1 X2 S1 S2 RHS Ratio
    X1 1 0 1/5 0 3/5 3/5÷1/5=3
    X2 0 1 -3/5 0 6/5
    S2 0 0 1 1 1 1/1=1(Min)
    f 0 0 1/5 0 18/5
    ↑
    Calculation

    1
    New Pivot Row = X Old Pivot Row
    Pivot No.
    1
    New Pivot
    X [0 0 1 1 1]
    Row =
    1
    [0 0 1 1 1]
    Calculation

    New Row = Old Row – Pivot Column Coefficient x New Pivot Row
    New X1 Row =
    [1 0 1/5 0 3/5]
    -(1/5) [0 0 1 1 1]
    = [1 0 0 -1/5 2/5]
    New X2 Row =
    [0 1 -3/5 0 6/5]
    -(-3/5)[0 0 1 1 1]
    = [0 1 0 3/5 9/5]
    Calculation

    New f Row =
    [0 0 1/5 0 18/5]
    -(1/5) [0 0 1 1 1]
    = [0 0 0 -1/5 17/5]
    Tableau

    Basics X1 X2 S1 S2 RHS
    X1 1 0 0 -1/5 2/5
    X2 0 0 0 3/5 9/5
    S1 0 0 1 1 1
    f 0 0 0 -1/5 17/5

    Now there is no positive value in the objective


    function so this is the optimal point
    Optimal Solution

    X1 = 2/5
    X2 = 9/5
    f = 17/5
    Cross checking of maximization point
    put values of X1 and X2 from above solution into
    original objective function
    f=4x1+ x2
    =4 (2/5) + (9/5)
    =17/5
    Thank You

    You might also like