|
Simplex Algorithm -
Convert the LP problem to a system of linear equations.
Example1)
Maximize p = x + 2y + 3z subject to the constraints
7x + z
6
x + 2y
20
3y + 4z
30
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
4x - 3y + z
3
x + y + z
10
2x + y - z
10
in the above LP problem are written as equations by adding a new "slack"
variable to the left-hand side of each to "take up the slack." In addition, the
objective function
is rewritten with all the unknowns on the left-hand side.
-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 |
the initial tableau is as follows (notice how we separate the last row using a
line).
| 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
| 
