Scribd Logo
Upload

Welcome to Scribd!

  • 691 views

    5-LP Simplex (CJ-ZJ Tableau)

    Uploaded by

    zuluagaga
    The document describes an alternative form of the simplex method called the Cj-Zj tableau form. This form selects the entering variable as the one in the column with the most positive Cj-Zj value, where Cj is the contribution rate and Zj is the current profit. It also tests for optimality by checking if all Cj-Zj values are less than or equal to zero. The method is demonstrated on the classic Wyndor Glass problem, showing the initial tableau and four iterations to reach the optimal solution of 2 batches of doors and 6 batches of windows for $36,000 profit.

    Copyright:

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

    5-LP Simplex (CJ-ZJ Tableau)

    Uploaded by

    zuluagaga
    691 views7 pages
    The document describes an alternative form of the simplex method called the Cj-Zj tableau form. This form selects the entering variable as the one in the column with the most positive Cj-Zj value, where Cj is the contribution rate and Zj is the current profit. It also tests for optimality by checking if all Cj-Zj values are less than or equal to zero. The method is demonstrated on the classic Wyndor Glass problem, showing the initial tableau and four iterations to reach the optimal solution of 2 batches of doors and 6 batches of windows for $36,000 profit.

    Original Title

    5-LP Simplex (Cj-Zj Tableau)

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an alternative form of the simplex method called the Cj-Zj tableau form. This form selects the entering variable as the one in the column with the most positive Cj-Zj value, where Cj is the contribution rate and Zj is the current profit. It also tests for optimality by checking if all Cj-Zj values are less than or equal to zero. The method is demonstrated on the classic Wyndor Glass problem, showing the initial tableau and four iterations to reach the optimal solution of 2 batches of doors and 6 batches of windows for $36,000 profit.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    691 views7 pages

    5-LP Simplex (CJ-ZJ Tableau)

    Uploaded by

    zuluagaga
    The document describes an alternative form of the simplex method called the Cj-Zj tableau form. This form selects the entering variable as the one in the column with the most positive Cj-Zj value, where Cj is the contribution rate and Zj is the current profit. It also tests for optimality by checking if all Cj-Zj values are less than or equal to zero. The method is demonstrated on the classic Wyndor Glass problem, showing the initial tableau and four iterations to reach the optimal solution of 2 batches of doors and 6 batches of windows for $36,000 profit.

    Copyright:

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

    Linear Programming The Simplex Method: an Alternative (Cj-Zj) Tableau Form

    ECS716: Operational Research Pn Paezah Hamzah

    Learning Outcomes Solving LP problems using an alternative form of simplex tableau (with Cj-Zj row) Recall the modified Wyndor Glass Co. problem in which Plant 3 operates at full capacity. We used the following steps to set up the initial simplex tableau.

    Max

    The Real Problem

    Z = 3X1 + 5X2 s.t. X1 4 2X2 12 3X1 +2X2 = 18 X1, X2 0

    Max

    The Artificial Problem in the standard form

    Z = 3X1 + 5X2 +0S1 + 0S2 MA1 s.t. X1 + S1 = 4 2X2 + S2 = 12 3X1 + 2X2 +A1 = 18 X1, X2, S1, S2, A1 0

    Eliminate variable A1 from the objective function to get the canonical form

    Z - 3X1 - 5X2 X1 2X2 3X1 + 2X2

    + S1

    + MA1 = 0 = 4 + S2 = 12 + A1 = 18

    (1) (2) (3) (4)

    The elimination of variable A1 to get the canonical form is rather lengthy.

    Multiply both sides of equation (4) by M we get 3MX1 + 2MX2 + MA1 = 18M

    Then, subtract the new equation from (1) as follows: Z3X1 3MX1 + 5X2 + MA1 = 0 2MX2 + MA1 = 18M = -18M (1)

    Z +(3M+3)X1 (2M+5)X2

    The standard model in a canonical form

    Z - (3 +3M)X1 (5+ 2M)X2 = X1 + S1 = 2X2 + S2 = 3X1 + 2X2 + A1 =

    -18M 4 12 18

    The objective function (z-row) written at the bottom

    2X2 3X1 + 2X2 Z - (3 +3M)X1 (5+ 2M)X2

    X1

    + S1

    = 4 + S2 = 12 + A1 = 18 = -18M

    Iteration 1

    Basic Var. S1 S2 S3 Z

    Z 0 0 0 1

    X1 1 0 3 -3M-3

    X2 0 2 2 -2M-5

    S1 1 0 0 0

    S2 0 1 0 0

    A1 0 0 1 0

    RHS 4 12 18 -18M

    Basic Var.

    Z 0 0 0 1 Z 0 0 0 1

    X1 1 0 0 0 X1 1 0 0 0

    X2 0 2 2 -2M-5 X2 0 0 1 0

    S1 1 0 -3 3M+3 S1 1 3 -3/2 -9/2

    S2 0 1 0 0 S2 0 1 0 0

    A1 0 0 1 0 A1 0 -1 1/2 M+5/2

    RHS 4 12 6 -6M+12 RHS 4 6 3 27

    Iteration 2

    X1 S2 S3 Z Basic Var.

    Iteration 3

    X1 S2 X2 Z

    Iteration 4

    Basic Var. X1 S1 X2 Z

    Z 0 0 0 1

    X1 1 0 0 0

    X2 0 0 1 0

    S1 0 1 0 0

    S2 -1/3 1/3 1/2 3/2

    A1 1/3 -1/3 0 M+1

    RHS 2 2 6 36

    All z-row coefficients 0. Hence, the optimal solution is reached. Optimal solution: X1= 2, X2 = 6, S1 = 2, S2 =0, S3 =0, A1 =0 Optimal value=36

    An Alternate Simplex Procedure (Cj-Zj Form) The procedure (in the pink box) done to eliminate variable to get the canonical form in order to set up the initial simplex tableau is rather lengthy. There is an alternate form of simplex tableau which can reduce this step. The simplex procedure is shown in the following flow chart.

    Start Convert LP model to Standard Form

    Obtain an Initial Basic Feasible Solution

    Test for Optimality

    Optimal

    Interpret

    Stop

    Not Optimal Determine the Entering Variable *Choose the variable from the pivot column (column with the MOST POSITIVE Cj-Zj row value)

    Determine the Leaving Variable

    Choose variable from the pivot row (row with the smallest positive RHSto- pivot column ratio)

    Obtain an Improved BF Solution

    Perform elementary row operations (ERO)

    *Testing for Optimality (Maximization problems): All Cj-Zj row values 0 Optimal

    *Testing for Optimality (Minimization problems): All Cj-Zj row values 0 Optimal

    *Note: The differences in this method occur in the following steps (shown in blue boxes): Selecting the entering variable. Testing for optimality.

    How to Use the Cj-Zj Form? To demonstrate the new method, we solve the original Wyndor Glass again. Maximize subject to: Z = 3X1 + 5X2 +0S1 + 0S2 + 0S3 2X2 3X1 + 2X2 X1 + S1 + S2 = 4 = 12 +S3 = 18 0 (Plant 1, hours) (Plant 2, hours) (Plant 3, hours)

    X1, X2, S1, S2, S3

    where X1 = number of batches of doors produced per week X2 = number of batches of windows produced per week S1= unused hours in Plant 1 S2= unused hours in Plant 2 S3= unused hours in Plant 3

    The initial simplex tableau can be written as follows: Cj 0 0 0 Basic S1 S2 S3 Zj Cj-Zj X1 3 1 0 3 X2 5 0 2 2 S1 0 1 0 0 S2 0 0 1 0 S3 0 0 0 1

    Coefficients in the objective function for basic variables where Cj Zj

    RHS 4 12 18

    = the contribution rate (unit profit) = the gross profit given up by adding 1 unit of a variable into the current solution. Cj-Zj = the net profit

    How to obtain Zj and Cj-Zj row values? Take the sum of the product of each entry under column Cj and the corresponding entry under each column. Cj 0 0 0 Basic S1 S2 S3 Zj Cj-Zj X1 X2 5 0 2 2 S1 0 1 0 0 S2 0 0 1 0 S3 0 0 0 1

    3 1 0 3 0 3-0=3

    RHS 4 12 18

    (Column Cj) x (Column X1) 0(1) = 0 0(0) = 0 0(3) = 0 Sum = 0 Cj-Zj = 3 0 = 3 The complete initial tableau is shown below.

    Iteration 1 Basic S1 S2 S3 Zj Cj-Zj X1 3 1 0 3 0 3 X2 5 0 2 2 0 5 S1 0 1 0 0 0 0 S2 0 0 1 0 0 0 S3 0 0 0 1 0 0

    Cj 0 0 0

    RHS 4 12 18 0

    From the above tableau, we pivot on column X2, the column with the largest positive Cj-Zj value as follows: Iteration 1 Basic S1 S2 S3 Zj Cj-Zj X1 3 1 0 3 0 3 X2 5 0 2 2 0 5 S1 0 1 0 0 0 0 S2 0 0 1 0 0 0 S3 0 0 0 1 0 0

    Cj 0 0 0

    RHS 4 12 18 0

    ratio -12/2=6 18/2=9

    SMALLEST positive ratio

    LARGEST positive Cj-Zj

    Iteration 2 Basic S1 X2 S3 Zj Cj-Zj X1 3 1 0 3 0 3 X2 5 0 1 0 5 0 S1 0 1 0 0 0 0 S2 0 0 0.5 -1 2.5 -2.5 S3 0 0 0 1 0 0

    Cj 0 5 0

    RHS 4 6 6 30

    ratio 4/1=4 -6/3=2

    SMALLEST positive ratio

    LARGEST positive Cj-Zj

    Iteration 3 Basic S1 X2 X1 Zj Cj-Zj X1 3 0 0 1 3 0 X2 5 0 1 0 5 0 S1 0 1 0 0 0 0 S2 0 1/3 0.5 -1/3 1.5 -1.5 S3 0 -1/3 0 1/3 1 -1

    Cj 0 5 3

    RHS 2 6 2 36

    No positive Cj-Zj optimal.


    Optimal solution: X1=2, X2=6 [produce 2 batches of doors, 6 batches of windows] Optimal value : $36,000

    The Big-M Method Example: Wyndor Glass Co. Suppose Plant 3 is required to operate at full capacity. The third constraint 3X1 +2X2 18 is rewritten as 3X1 2X2 =18.

    Max

    The Real Problem

    Z = 3X1 + 5X2 s.t. X1 4 2X2 12 3X1 +2X2 = 18 X1, X2 0

    Max

    The Artificial Problem

    Z = 3X1 + 5X2 +0S1 + 0S2 MA1 s.t. X1 + S1 = 4 2X2 + S2 = 12 3X1 + 2X2 +A1 = 18 X1, X2, S1, S2, A1 0

    There is no need to eliminate variable A1 from the objective function.


    Iteration 1 Cj 0 0 -M Basic S1 S2 A1 Zj Cj-Zj X1 3 1 0 3 -3M 3M+3 X2 5 0 2 2 0 -2M+5 S1 0 1 0 0 0 0 S2 0 0 1 0 M -M A1 -M 0 0 1 -M 0 RHS 4 12 18 -18M ratio 4/1=4 -18/3=6
    SMALLEST positive ratio

    LARGEST positive Cj-Zj

    Iteration 2 Cj 3 0 -M Basic X1 S2 A1 Zj Cj-Zj X1 3 1 0 0 3 0 X2 5 0 2 2 -2M 2M+5 S1 0 1 0 -3 3+3M -(3M+3) S2 0 0 1 0 0 0 A1 -M 0 0 1 -M 0 RHS 4 12 6 12-6M ratio --6 3

    LARGEST positive Cj-Zj

    Iteration 3 Cj 3 0 5 Basic X1 S1 X2 Zj Cj-Zj X1 3 1 0 0 3 0 X2 5 0 0 1 5 0 S1 0 1 3 -3/2 -9/2 9/2 S2 0 0 1 0 0 0 A1 -M 0 -1 1/2 5/2 -M-5/2 RHS 4 6 3 27 ratio 4 2 ---

    Iteration 4 Cj 3 0 5 Basic X1 S1 X2 Zj Cj-Zj X1 3 1 0 0 3 0 X2 5 0 0 1 5 0 S1 0 0 1 0 0 0 S2 0 -1/3 1/3 1/2 0 -3/2 A1 -M 1/3 -1/3 0 1 -M-1 RHS 2 2 6 36

    All Cj-Zj 0 optimal.


    Optimal solution: X1 = 2, X2 = 6 Wyndor should produce 2 batches of doors and 6 batches of windows. Maximum profit = $36,000

    You might also like