Simplex Algorithm: Step by Step

Optimization
Simplex Algorithm: step by step
This note shows the step by step procedure how to solve the problem using Simplex Algorithm (method).
Let’s consider the following LP model.
Max Z = 3 x1 + 5x2
s.t. x1 ≤ 4
2x2 ≤ 12
3 x1 + 2x2 ≤ 18
x1, x2 ≥ 0
Iteration 0: setting
1. Change the original problem to standard form (Augmented form of the model). See lecture note
for how to make standard form.
Max Z - 3x1 - 5x2 – 0x3 – 0x4 – 0x5 = 0

s.t. x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
x1, x2, x3, x4, x5 ≥ 0
2. Create a tableau form with coefficients of augmented form.
B.V. Z X1 X2 X3 X4 X5 RHS
Z 1 -3 -5 0 0 0 0
X3 0 1 0 1 0 0 4
X4 0 0 2 0 1 0 12
X5 0 3 2 0 0 1 18
Note that the basic variables are the slack or excess variables at the setting.
Basic Variables: X3 = 4, X4 = 12, X5 = 18

Non Basic Variables: X1 = X2 = 0
Solution at this tableau: (X1, X2, X3, X4, X5) = (0, 0, 4, 12, 18) with Z = 0
*the right hand side (RHS) values are the solution.
Note: Basic variables (x3, x4 and x5) make identity matrix (see shaded area). In every tableau, at
each iteration, basic variables always will make identity matrix.
3. Do the optimality test.

a. Check the Z-row
i. If you can see values with “-“ sign, then it is not optimal.
ii. If you cannot see values with “-“ sign, then it is optimal, then stop!
Optimization
Iteration 1:
1. If it is not optimal, then select an entering variable.

a. The entering variable is the smallest value with “-“ sign in Z-row.
i. This example, X2 has -5 in Z-row, so X2 is the entering variable. It means X2
will be a basic variable (it will have some value instead of 0).
2. Select leaving variable.
a. Do the ratio test.
i. Ratio = RHS / entry in entering variable column (except Z-row, value with 0
and “-“ signs)
ii. Select smallest ratio for leaving variable.
iii. In this example, X4 is the leaving variable.
B.V. Z X1 X2 X3 X4 X5 RHS Ratio

Z 1 -3 -5 0 0 0 0
X3 0 1 0 1 0 0 4
X4 0 0 2 0 1 0 12 12/2=6
X5 0 3 2 0 0 1 18 18/2=9
The cell in intersection of entering and leaving variable is called “pivot.” See the table below
(shaded cell) in this example.
Z
X3
X4 2
X5
3. Updating the tableau

a. Make the pivot value to 1 and all other entries to 0 in the column.
b. To make the pivot to 1, just divide the value to the pivot value. This should be done
for all elements in the row.
c. In this example, the pivot value is 2, so divide by 2, and then the value becomes 1.
Z
X3
X2 0/2 0/2 2/2 0/2 1/2 0/2 12/2
X5
Z
X3
X2 0 0 1 0 1/2 0 6
X5
Optimization
Calculations to update the table (to make 0 for X2 column entries except pivot).
Old Z-row) 1 -3 -5 0 0 0 0
+ New X2-row ×5) 0 0 5 0 5/2 0 30
New Z-row) 1 -3 0 0 5/2 0 30
Old X5-row) 0 3 2 0 0 1 18
+ New X2-row ×-2) 0 0 -2 0 -1 0 -12
New X5-row) 0 3 0 0 -1 1 6
The entry in X3-row and X2-column is already 0, so no calculation is required.

Remember that I used “Old row + new row”, not “Old row - new row” for consistency.
Z 1 -3 0 0 5/2 0 30
X3 0 1 0 1 0 0 4
X2 0 0 1 0 1/2 0 6
X5 0 3 0 0 -1 1 6
• Note that basic variables are X3 = 4, X2 = 6, and X5 = 30 and non-basic variables are X1 = X4 = 0.
• Solution at this tableau: (X1, X2, X3, X4, X5) = (0, 6, 4, 0, 6) with Z = 30 (see RHS value in Z-row)
• Also note that columns X3, X2 and X5 make the identity matrix (exclude Z-row).

a. Check the Z-row
i. If you can see values with “-“ sign, then it is not optimal.
ii. If you cannot see values with “-“ sign, then it is optimal, then stop!
Iteration 2:
1. If it is not optimal, then select an entering variable.

a. The entering variable is the smallest value with “-“ sign in Z-row.
i. This example, X1 has -3 in Z-row, so X1 is the entering variable. It means X1 will
be a basic variable (it will have some value instead of 0).
2. Select leaving variable.
a. Do the ratio test.
i. Ratio = RHS / entry in entering variable column (except Z-row, value with 0 and
“-“ signs)
ii. Select smallest ratio for leaving variable.
iii. In this example, X4 is the leaving variable.
B.V. Z X1 X2 X3 X4 X5 RHS Ratio

Z 1 -3 0 0 5/2 0 30
X3 0 1 0 1 0 0 4 4/1 = 4
X2 0 0 1 0 1/2 0 6
X5 1 3 0 0 -1 1 6 6/3 = 2
Optimization
3. Updating the tableau
Old Z-row) 1 -3 0 0 5/2 0 30

+ New X1-row ×3) 0 3 0 0 -1 1 6
New Z-row) 1 0 0 0 3/2 1 36
Old X3-row) 0 1 0 1 0 0 4
+ New X1-row ×-1) 0 -1 0 0 1/3 -1/3 -2
New X3-row) 0 0 0 1 1/3 -1/3 2
Z 1 0 0 0 3/2 1 36
X3 0 0 0 1 1/3 -1/3 2
X2 0 0 1 0 1/2 0 6
X1 0 1 0 0 -1/3 1/3 2
• Note that basic variables are X3 = 2, X2 = 6, and X1 = 2 and non-basic variables are X4 = X5 = 0.
• Solution at this tableau: (X1, X2, X3, X4, X5) = (2, 6, 2, 0, 0) with Z = 36
• Also note that columns X3, X2 and X1 make the identity matrix.

a. All values in Z-row have “+” signs, so it is optimal! STOP!
At the second iteration, the simplex algorithm found the optimal solution. The Optimal solution is (X1,
X2, X3, X4, X5) = (2, 6, 2, 0, 0) and this generates the objective value 36.

Simplex Algorithm: Step by Step

Uploaded by

Copyright:

Available Formats

Simplex Algorithm: Step by Step

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Simplex Algorithm: Step by Step

Uploaded by

Copyright:

Available Formats

Optimization

Simplex Algorithm: step by step

Max Z - 3x1 - 5x2 – 0x3 – 0x4 – 0x5 = 0

2. Create a tableau form with coefficients of augmented form.

Basic Variables: X3 = 4, X4 = 12, X5 = 18

3. Do the optimality test.

1. If it is not optimal, then select an entering variable.

B.V. Z X1 X2 X3 X4 X5 RHS Ratio

3. Updating the tableau

The entry in X3-row and X2-column is already 0, so no calculation is required.

4. Do the optimality test.

1. If it is not optimal, then select an entering variable.

B.V. Z X1 X2 X3 X4 X5 RHS Ratio

3. Updating the tableau

Old Z-row) 1 -3 0 0 5/2 0 30

4. Do the optimality test.

You might also like