Scribd Logo
Upload

Welcome to Scribd!

  • 1K views

    Simplex Method Problem-Solved

    Uploaded by

    Chandra Hasan
    This document discusses the simplex method for solving linear programming problems (LPP) with multiple constraints. It provides steps to set up the initial simplex table and the first iteration table to arrive at an optimal solution. The example problem is maximizing Z=4x1+10x2 subject to 3 constraints. The solution found is Z=200, x1=0, x2=20 by going through the steps of setting up the initial table and first iteration table to arrive at all positive values in the Zj-Cj row.

    Copyright:

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

    Simplex Method Problem-Solved

    Uploaded by

    Chandra Hasan
    1K views3 pages
    This document discusses the simplex method for solving linear programming problems (LPP) with multiple constraints. It provides steps to set up the initial simplex table and the first iteration table to arrive at an optimal solution. The example problem is maximizing Z=4x1+10x2 subject to 3 constraints. The solution found is Z=200, x1=0, x2=20 by going through the steps of setting up the initial table and first iteration table to arrive at all positive values in the Zj-Cj row.

    Original Title

    1. Simplex Method Problem-solved (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses the simplex method for solving linear programming problems (LPP) with multiple constraints. It provides steps to set up the initial simplex table and the first iteration table to arrive at an optimal solution. The example problem is maximizing Z=4x1+10x2 subject to 3 constraints. The solution found is Z=200, x1=0, x2=20 by going through the steps of setting up the initial table and first iteration table to arrive at all positive values in the Zj-Cj row.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    1K views3 pages

    Simplex Method Problem-Solved

    Uploaded by

    Chandra Hasan
    This document discusses the simplex method for solving linear programming problems (LPP) with multiple constraints. It provides steps to set up the initial simplex table and the first iteration table to arrive at an optimal solution. The example problem is maximizing Z=4x1+10x2 subject to 3 constraints. The solution found is Z=200, x1=0, x2=20 by going through the steps of setting up the initial table and first iteration table to arrive at all positive values in the Zj-Cj row.

    Copyright:

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

    3 methods to solve a LPP

    - Graphical method- only 2 variables


    Unlimited variables- Simplex method – For constraints with ≤
    Big M Method- For constraints with = or ≥

    Simplex Method
    1.Max Z = 4x1 + 10x2
    Subject to 2x1 + x2 ≤ 50

    2x1 + 5x2 ≤ 100


    2x1 + 3x2 ≤ 90 and x1, x2 ≥ 0

    Step 1: To convert inequality in to equation form (S- Slack variable)

    Z=4x1 + 10x2 + 0S1 + 0S2 + 0S3

    2x1 + x2 + S1 = 50

    2x1 + 5x2 + S2 = 100

    2x1 + 3x2 + 1S3 = 90

    Step 2: Initial Simplex Table by using matrix transpose

    Cj 4 10 0 0 0
    Qmin = Xb/PC
    Cb Yb Xb X1 X2 S1 S2 S3
    0 S1 50 2 1 1 0 0 50/1=50
    0 S2 100 2 5 0 1 0 100/5=20
    0 S3 90 2 3 0 0 1 90/3=30
    Zj-Cj 0 -4 -10 0 0 0

    Steps to create the initial simplex table

    (1) Write the coordinate values of the corresponding variables in each


    equation in the table, where Xb is the right side values of the constraint
    equations

    (2) Zj-Cj = Cb.Xi – Cj where Xi can be Xb , X1, X2, S1, S2, S3


    For X1 column (Zj-Cj )=(0x2+0x2+0x2)-4 =-4
    For X2 column (Zj-Cj) =(0x1+0x5+0x3)-10 = -10
    Complete for other columns too
    (3) Find the most negative of Zj-Cj. It is -10. So X2 is the pivot column.
    (4) Now divide Xb column values by the corresponding pivot column values

    and put in Qmin column.


    (5) Find the smallest positive value in Qmin column. Mark the pivot row.
    (6) Now the variable in the pivot row leaves the basis and variable in the
    pivot column enters the basis
    Step 3: Steps to create the first iteration simplex table
    X2=incoming variable
    S2=outgoing variable
    For the pivot row
    New X2 row = (Old S2 Eq)/Pivot Element
    = (100, 2, 5, 0, 1, 0)/5

    New X2 row = (20, 2/5, 1, 0, 1/5,0)

    For all other rows except pivot row


    New S1 row = (Old S1 row) – (corresponding Column Coefficient in
    Pivot Column)xNew X2 row
    = (50, 2, 1, 1, 0, 0) – (1)(20, 2/5, 1, 0, 1/5, 0)
    New S1 Eq = (30, 8/5, 0, 1, -1/5, 0)

    New S3 row = (Old S3 row) – (corresponding Column Coefficient in


    PC)xNew X2 Eq

    = (90, 2, 3, 0, 0, 1) – (3) (20, 2/5, 1, 0, 1/5, 0)

    = (90, 2,3,0,0,1) – (60, 6/5, 3, 0, 3/5,0)

    New S3 Eq = (30, 4/5, 0, 0, -3/5, 1)

    New Zj - Cj row = (Old Zj-Cj row) – (corresponding Column


    Coefficient in PC)xNew X2 Eq

    =(0, -4, -10, 0, 0, 0) – (-10) (20, 2/5, 1, 0, 1/5, 0)

    = (0, -4, -10, 0, 0, 0) + (200, 4, 10, 0, 2, 0)

    New Zj-Cj = (200, 0, 0, 0, 2, 0)


    Step 3: First Iteration Simplex Table
    Cj 4 10 0 0 0
    Qmin = Xb/PC
    Cb Yb Xb X1 X2 S1 S2 S3
    0 S1 30 8/5 0 1 -1/5 0
    10 X2 20 2/5 1 0 1/5 0
    0 S3 30 4/5 0 0 -3/5 1
    Zj-Cj 200 0 0 0 2 0

    Check for the most negative value in Zj-Cj. If all values are positive,
    then we have reached the solution.

    Results:

    Z=200, X1 =0, X2 = 20

    Checking

    Max Z = 4x1 + 10x2


    Z= 4(0)+10(20)=200

    Example
    Minimise Z=8x1-2x2
    Subjected to -4x1+2x2 ≤ 1
    5x1-4x2 ≤ 3
    Convert into a maximization problem, change the signs of the
    variables in the objective function

    Maximise Z= -8x1+2x2

    No change in the constraint eqns


    -4x1+2x2 ≤ 1
    5x1-4x2 ≤ 3

    Solution
    Z=1, x1=0, x2=1/2
    8(0)-2(1/2)=-1

    You might also like