Simplex Algorithm - Convert the LP problem to a system of linear equations.
Example1)
Maximize p = x + 2y + 3z subject to the constraints
The initial tableau is:
x | y | z | s | t | u | p | Ans | ||
7 | 0 | 1 | 1 | 0 | 0 | 0 | 6 | ||
1 | 2 | 0 | 0 | 1 | 0 | 0 | 20 | ||
0 | 3 | 4 | 0 | 0 | 1 | 0 | 30 | ||
-1 | -2 | -3 | 0 | 0 | 0 | 1 | 0 |
The final tableau is
x | y | z | s | t | u | p | Ans | |
7 | 0 | 1 | 1 | 0 | 0 | 0 | 6 | |
59 | 0 | 0 | 8 | 3 | -2 | 0 | 48 | |
-28 | 3 | 0 | -4 | 0 | 1 | 0 | 6 | |
4 | 0 | 0 | 1 | 0 | 2 | 3 | 66 |
The x-column is not cleared, so x = 0.
Since the y-column is cleared with pivot 3, the value of y is 6/3 = 2.
Since the z-column is cleared with pivot 1, the value of z is 6/1 = 6.
Since the t-column is cleared with pivot 3, the value of t is 48/3 = 16.
Since the s and u-columns are not cleared, their value is 0.
Since the p-column is cleared with pivot 3, the value of y is 66/3 = 22.
Example2)
The constraints
-2x + 3y - 4z + p = 0
This gives the following system of equations.
4x | - | 3y | + | z | + | s | = | 3 | ||||||
x | + | y | + | z | + | t | = | 10 | ||||||
2x | + | y | - | z | + | u | = | 10 | ||||||
-2x | + | 3y | - | 4z | + | p | = | 0 |
x | y | z | s | t | u | p | Ans | ||
4 | -3 | 1 | 1 | 0 | 0 | 0 | 3 | ||
1 | 1 | 1 | 0 | 1 | 0 | 0 | 10 | ||
2 | 1 | -1 | 0 | 0 | 1 | 0 | 10 | ||
-2 | 3 | -4 | 0 | 0 | 0 | 1 | 0 |
Thus, the matrix containing all information has 4 rows and 8 columns.
Now enter edit matrix A under F7 using n=#rows=4 and m=#columns=8 .
MATRIX A will look as follows:
4 | -3 | 1 | 1 | 0 | 0 | 0 | 3 |
1 | 1 | 1 | 0 | 1 | 0 | 0 | 10 |
2 | 1 | -1 | 0 | 0 | 1 | 0 | 10 |
-2 | 3 | -4 | 0 | 0 | 0 | 1 | 0 |
The Solution is
x=0 ( as x column is not cleared)
y=7/4 = 1.75
z=33/2 = 16.5
p=111/4 = 27.75