Archive for February 2007
The Simplex Algorithm
Posted on Friday, February 23, 2007 at 12:06 AM by Malcolm
This page gives an example of the Simplex Algorithm taken from the
"Operations Research" book by Wayne L. Winston.
Steps for Simplex Algorithm
The steps for the Simplex Algorithm are as follows:- Step 1: Convert the LP to standard form.
- Step 2: Obtain a basic feasible solution (bfs) from the standard form.
- Step 3: Determine whether the current bfs is optimal.
- Step 4: If the current bfs is not optimal, determine which non-basic variable should become a basic variable and which basic variable should become a non-basic variable so as to find a new bfs with a better objective function value.
- Step 5: Use Elementary Row Operation (ERO) to find the new bfs with the better objective function value. Go back to step 3.
Example:
max z = 60x1 + 30x2 + 20x3
s.t. 8x1 + 6x2 + x3 = 48
4x1 + 2x2 + 1.5x3 = 20
2x1 + 1.5x2 + 0.5x3 = 8
x2 = 5
x1, x2, x3 >= 0
Convert the LP to Standard Form
To convert the Lp to the standard form, first convert the LP's objective function to the row 0 format as shown in the table below. To convert the constraints to standard form, the slack variables s1, s2, s3, s4 are added as shown in the table below. Note that s1>=0, s2>=0, s3>=0, s4>=0.| Row | Basic Variable | |
|
0 1 2 3 4 |
z - 60x1 - 30x2 - 20x3 = 0
8x1 + 6x2 + x3 + s1 = 48
4x1 + 2x2 + 1.5x3 + s2 = 20
2x1 + 1.5x2 + 0.5x3 + s3 = 8
x2 + s4 = 5
|
z = 0 s1 = 48 s2 = 20 s3 = 8 s4 = 5 |
Basic Feasible Solution
Basic feasible solution, z=0, s1=48, s2=20, s3=8, s4=5, x1=x2=x3=0. Here, the basic variables BV = {z, s1, s2, s3, s4}, and the non-basic variables NBV = {x1, x2, x3}Determine if the BFS is Optimal
To determine if the bfs is optimal, try to determine if z can be increased by increasing some non-basic variable by re-arranging row 0 to:z = 60x1 + 30x2 + 20x3For each non-basic variable k, use the above to determine if increasing k (holding all other NBV at 0) will increase z. Here, increasing x1 will result in the largest increase of z. Thus, x1 is chosen to be increased. This will cause x1 to become a basic variable. Thus, x1 is termed as the "entering variable" at this step. Ideally we would like to increase x1 as much as possible. However, the increase of x1 is restricted by the constraints on the slack variables. In other words, we can increase x1 as long as s1, s2, s3 and s4 stays positive. For each row in the able table, we can find a limit on x1 for the corresponding slack variable to stay positive.
- Row 1 limit on x1 = 48/8 = 6
- Row 2 limit on x1 = 20/4 = 5
- Row 3 limit on x1 = 8/2 = 4
- Row 4 limit on x1 = no limit (coefficient on x1 on row 4 is nonpositive)
-
ERO 1: Create a coefficient of 1 for x1 by multiplying Row-3 by 1/2.
The resulting row is:
x1 + 0.75x2 + 0.25x3 + 0.5s3 = 4 --- (Row-3)
-
ERO 2: Create a zero coefficient for x1 in Row-0 by replacing Row-0
with 60xRow-3+Row-0
z + 15x2 - 5x3 + 30s3 = 240 --- (Row-0)
-
ERO 3: Create a zero coefficient for x1 in Row-1 by replacing Row-1
with -8xRow-3+Row-1
-x3 + s1 - 4s3 = 16 --- (Row-1)
-
ERO 4: Create a zero coefficient for x1 in Row-2 by replacing Row-2
with -4xRow-3+Row-2
-x2 + 0.5x3 + s2 -2s3 = 4 (Row-2)
-
x1 does not appear in Row-4 so there is no ERO to be carried out
x2 + s4 = 5
| Row | Basic Variable | |
|
0' 1' 2' 3' 4' |
z + 15x2 - 5x3 + 30s3 = 240
- x3 + s1 - 4s3 = 16
- x2 + 0.5x3 + s2 - 2s3 = 4
x1 + 0.75x2 + 0.25x3 + 0.5s3 = 4
x2 + s4 = 5
|
z = 240 s1 = 16 s2 = 4 x1 = 4 s4 = 5 |
From the above table, we observe that increasing x3 (but not x2 and s3) will cause z to be increased. Thus, we again pivot x3 on Row-2 based on the ratio test. The resulting new basic feasible solution is given by the following table.
| Row | Basic Variable | |
|
0'' 1'' 2'' 3'' 4'' |
z + 5x2 + 10s2 + 10s3 = 280
- 2x2 + s1 + 2s2 - 8s3 = 24
- 2x2 + x3 + 2s2 - 4s3 = 8
x1 + 1.25x2 - 0.5s2 + 1.5s3 = 2
x2 + s4 = 5
|
z = 280 s1 = 24 s2 = 8 x3 = 2 s4 = 5 |
At this point, the basic feasible solution found is the optimal solution, since increasing either x2, s2 or s3 will cause a decrease in z. Edited on: Monday, February 23, 2009 1:16 PM
Posted in (RSS)
