Simplex Algorithm Example

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

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.

-2x

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