Transcript Simplex Method

The Simplex Algorithm
An Algorithm for solving Linear
Programming Problems
We Start with a Linear
Programming Problem
•
•
•
•
Maximise P = 4x +5y +3z
Subject to the constraints
8x + 5y +2z  4
x +2y +3z  1
Setting up the Tableau
• First rearrange the equation for P so that it
is equal to zero :
• P - 4x - 5y - 3z = 0
Introduce Slack variables
•
•
•
•
•
8x + 5y +2z  4 becomes
8x + 5y + 2z + s = 4
x +2y +3z  1 becomes
x +2y +3z + t = 1
s and t are called the slack variables
This is the Tableau
(Fancy word for table)
P
x
y
z
s
t
l
EQUATION
1
-4
-5
-3
0
0
0

0
8
5
2
1
0
4

0
1
2
3
0
1
1

Finding a pivot
• Chose any negative number in the first row
• Consider the positive values in the column
below it
• Divide the value in the last column by the
corresponding value in the chosen column
and see which gives you the least
• That tells you which is the pivot...it goes
like this:
P
x
y
z
s
t
l
EQUATION
1
-4
-5
-3
0
0
0

0
8
5
2
1
0
4

0
1
2
3
0
1
1

4/8 =1/2 1/1=1
1/2 is the least so 8 is the pivot
The next step is to reduce the pivot
to 1 by dividing equation by 8
P
x
y
z
s
t
l
EQUATION
1
-4
-5
-3
0
0
0

0
1
5/8 1/4 1/8
0
1/2
=/8
0
1
1
1

2
3
0
We now reduce the other elements in
the column of the pivot to zero:
s
t
l
EQUATION
1/2
0
2
=+4×
1
5/8 1/4 1/8
0
1/2
=/8
0
13/8 23/4 -1/8
1
1/2
=- 
P
x
y
z
1
0 -21/2 -2
0
0
We have now completed the first
iteration of the algorithm
P2
x
5
8
1
2
y  2z 
y
3 y 2
18
3
4
1
4
z
z
1 s  2
2
1
 1
s

8
2
1 s t  1
8
2
• This tells us that
• P = 2 when y = z = s = 0 and x = 1/2, t= 1/2
• P= 2 is not the optimal solution as we still
have negative numbers in the first row.
We now repeat the process: chose a
negative number in the first row and
1 5
4
3
1
4


find 2a new
1 8  pivot:
2 8
5
11
s
t
l
EQUATION
1/2
0
2
=+4×
1
5/8 1/4 1/8
0
1/2
=/8
0
13/8 23/4 -1/8
1
1/2
=- 
P
x
1
0
0
0
y
z
So
-21/2 -2
3
18
is the pivot
We now repeat the process: choose a
negative number in the first row and
find a new pivot:
s
t
l
EQUATION
1/2
0
2
=+4×
1
5/8 1/4 1/8
0
1/2
=/8
0
13/8 23/4 -1/8
1
1/2
=- 
P
x
1
0
0
0
y
z
-21/2 -2
Reduce the pivot to 1 by dividing
equation by 13/8 to get equation 
s
t
l
EQUATION
1/2
0
2
=+4×
5/8 1/4 1/8
0
1/2
=/8
P
x
y
1
0
-21/2 -2
0
1
0
0
1
z
1
2 -1/11 8/11
=
Reduce the other elements in the
column of the pivot to zero
P
x
y
1
0
0
3/11 14/11 210/11 210/11
0
1
0
-1 2/11 -5/11 3/11
0
0
1
1
z
s
2
t
l
-1/11 8/11
EQUATION
=+21/2
=-5/8
=
We have now completed the
second iteration of the algorithm
P
3
11
9 s  2 10 t  2 10
z  1 11
11
11
x  z 
2
11
y  2z 
s 
1
11
5 t
11
s
8 t
11

3
11

4
11
• This tells us that
• P = 210/11 when z = s = t=0 and x = 3/11, y= 4/11
• P= 210/11 is the optimal solution as we have no
negative numbers in the first row.
• P= 210/11 is the maximum value; we have finished!