Chapter 4: Revised Simplex Method

¨Revised Simplex Solving for Basic Feasible

Solution
¨The Simplex Tableaux in Matrix form
¨Fundamental Insight
 1. Revised Simplex Solving for Basic
Feasible Solution
• One of the key feature of revised simplex method
involves the way in which it solves for each new Basic
Feasible Solution after identifying its basic and non-
basic variables.
• Given these variables, the resulting basic solution is
x
the solution of the m equations: A, Ix   b
s  
• The n nonbasic variables from the n+m elements of
are set to zero.  x 
x   0
 s
 Revised Simplex Solving for Basic
Feasible Solution (cont.)
¨ The set of m equations with m basic variables denoted by
BxB=b
 xB1 
Where  
x
xB   B 2 
¨ Vector of basic variables:  
 
 xBm 
x
obtained by eliminating the nonbasic variables from x 
B B
11 B 
12 1m  s
 
 B21 B22 B2 m 
B
   
¨ Basis matrix:  
 Bm1 Bm 2 Bmm 

A, I 
obtained by eliminating the columns corresponding to
coefficient of nonbasic variables from B-1BxB=B-1b
 Revised Simplex Solving for Basic
Feasible Solution (cont.)
¨ To solve BxB = b both side are multiplied by B-1
or xB=B-1b
¨ Then Z = cBxB= cBB-1b
¨ Solution process:
Determine xB  B  B-1  Calculate
xB=B-1b
Z = cBxB= cBB-1b
2. The Simplex Tableaux in Matrix
Form
 Matrix Notation
Maximize Z= cx Matrix:
 a11 a12  a1n 
a a22  a2 n 
subject to A  21

Ax = b    
 
x0  am1 am 2  amn 

Row vector: c  c1 , c2 ,..., cn 

Column vectors: x 1 b1  0   xn 1 
x  b  0   
x   2 b   2 0    xs  
xn  2 
    
       
 xn  bn  0  x
 nm 
The constrains become: x  x 
 A, I   x   b x   0
 s  s
 Revised Simplex Method
(Wyndor Glass Problem in Matrix Form)
Maximize Z = 3x1 + 5x2 Maximize Z = 3x1 + 5x2
Subject to Subject to
x1 ≤4 x1 + x3 =4
2x2 ≤ 12
2x2 + x4 = 12
3x1 + 2x2 ≤ 18
x1 ≥ 0 3x1 + 2x2 + x5 = 18
x2 ≥ 0.
x1≥ 0, x2 ≥ 0, x3 ≥0, x4 ≥0, x5 ≥0.
In this case
c = [3, 5] 1 0 1 0 0 4
[ A, I ]  0 2 0 1 0 b  12
3 2 0 0 1 18
 x3 
 x1 
x =  x2  xs =  x4 
 x5 
 The Simplex Tableau
Iteration Eq. Basic X1 X2 S1 S2 S3 RHS Ratio
variable
(0) Z -3 -5 0 0 0 0
(1) S1 1 0 1 0 0 4
0
(2) S2 0 2 0 1 0 12 12/2
(3) S3 3 2 0 0 1 18 18/2
(0) Z -3 0 0 5/2 0 30
1 (1) S1 1 0 1 0 0 4 4/1
(2) X2 0 1 0 1/2 0 6
(3) S3 3 0 0 -1 1 6 6/3
(0) Z 0 0 0 3/2 1 36
2 (1) S1 0 0 1 1/3 -1/3 2
(2) X2 0 1 0 1/2 0 6
(3) X1 1 0 0 -1/3 1/3 2
 The Sequence of Basic Feasible Solution
• Iteration 0
 x3  1 0 0  4 
4
 x3  1 0 0
       
x   0 1 0  so  x4   0 1 0 12  12
x =B  4 B   =B-1
 x5  0 0 1  x5  0 0 1 18 18
4
cB = [0, 0, 0] so
12
Z = [0, 0, 0]   =0
18

• Iteration 1
 x3  1 0 0  4 
 4
 x3  1 0 0  1 0 0  
    
x   0 2 0  
-1 0 1 / 2 0
 so  x2   0 1 / 2 0 12  6
x =B  2 B   B  
6
 x5  0 2 1 0  1 1  x5  0  1 1 18
 4
cB = [0, 5, 0] 6 
so Z = [0, 5, 0]   = 30
6
• Iteration 2
1 0 1  1 1 / 3  1 / 3  x3  1  1 / 3
 4   2
 x3  1/ 3
12  6
x  0 2 0    so  x   0 0 
x = 
B   -1  0 1 / 2
B  0   2  0
1/ 2
   
B  2  x1    1 / 3 1 / 3 
18 2
 x1  0 2 3 0  1 / 3 1 / 3 
 2
cB = [0, 5, 3]  
so Z = [0, 5, 3] 6 = 36
2
THE SIMPLEX TABLEAUX IN MATRIX FORM
Basic Z Coefficient of: RHS
variable Original variable Slack
variable
Z 1 cB .B-1.A - c cB .B-1 cB .B-1.b

xB 0 B-1.A B-1 B-1.b

cB : vector whose elements are the objective

function coefficients (including zero for slack variables)
for the corresponding elements of xB
xB : vector of basic variables
B : basis matrix
B-1 : inverse of basis matrix
b : vector of RHS
 Solution Process
¨ Determine xB  B, c, cB B-1
¨ Calculate
xB=B-1b
Z = cBxB= cBB-1b
¨ Determine entering variable: cBB-1A –c 
negative or not?most negative
¨ Determine leaving variable: min{B-1 .b/B-1 .A}
 Example

Maximize Z = 3x1 + 5x2 Maximize Z = 3x1 + 5x2

Subject to Subject to
x1 ≤4 x1 + x3 =4
2x2 ≤ 12
2x2 + x4 = 12
3x1 + 2x2 ≤ 18
x1 ≥ 0 3x1 + 2x2 + x5 = 18
x2 ≥ 0.
x1≥ 0, x2 ≥ 0, x3 ≥0, x4 ≥0, x5 ≥0.
In this case
c = [3, 5] 1 0 1 0 0 4
1 0  [ A, I ]  0 2 0 1 0 b  12

A   0 2
3 2 0 0 1 18
 x3 
 3 2  x
 x1 
=  x2  xs =  x4 
 x5 
 The Sequence 4
12
• Iteration 0 4 4
1 0 0  x3  1 0 0     Z = [0, 0, 0]   = 0
 x3      12  12 18
x   0 1 0  so  x4   0 1 0    
x =B  4 B   =B-1     18
 x5  0 0 1 18  
Coefficient values of x2
 x5  0 0 1 1 0 0  1 0  1 0 
1 0 
  B 1. A  0 1 0  0 2   0 2 
cB = [0, 0, 0], c = [3, 5] cB .B . A  c  0 0 0 0 2   3 5  3  5
1

0 0 1   3 2   3 2 
 3 2 

x2 : entering variable
1 0 0   4   4 
B 1.b  0 1 0  12   12 

[]
−
12
min 𝑟𝑎𝑡𝑖𝑜 2 =6  x4 : leaving variable 0 0 1  18  18 
18
2

• Iteration 1
 x3  1 0 0  4 
 4
 x3  1 0 0  1 0 0  
    
x     
-1 0 1 / 2 0 so  x2   0 1 / 2 0 12  6
x =B  
2 B  0 2 0  B  x5  0  1 1 18 6
 x5  0 2 1 0  1 1
 4
cB = [0, 5, 0]
Z = [0, 5, 0] 6= 30
1 0  6
 5 
cB .B 1. A  c  0 0  0 2   3 5  [−3
3 50 ]
 2 
 3 2  The most negative x1 : entering variable
 The Sequence
x1 : entering variable and original variable
Thus, consider
1 0 0 
  1 0  1 0 
1
B 1. A  0 0  0 2   0 1 Coefficient values of x1
 2 
0 1 1   3 2   3 0 
 
4
1 0 0  1
   4   4
1      
1
B .b  0  
0 12    6  Min ratio     2
 2  6
0 1 1  18   6    x5 : leaving variable
  3

• Iteration 2
1 0 1  1 1 / 3  1 / 3  x3  1 1 / 3  1 / 3
 4   2
 x3  12  6
 0 2 0   so  x   0 0 
x =
B
x 
 2 B -1  0 1 / 2
B  0   2  0
1/ 2
 1 / 3 1 / 3 
   
 x1  0 2 3 0  1 / 3 1 / 3   x1   18 2
1 1 / 3  1 / 3 1 0
cB = [0, 5, 3] cB B 1 A  c  [0,5,3]0 1 / 2 0  0 2  [3,5]  [0,0] Non negative

2 0  1 / 3 1 / 3  3 2

 
Z = [0, 5, 3] 6 = 36 Solution is optimal
2
3. Fundamental Insight
 Fundamental Insight
Initial Z Decision Slack variables RHS
variables
Table
Z x1 x2 s1 s2 s3 rhs

1 -3 -5 0 0 0 0
t= -c 0
0 1 0 1 0 0 4

0 0 2 0 1 0 12
T= A I b
0 3 2 0 0 1 18

t 1 -c 0 0
=
T 0 A I b
1 cb B 1 A  c | cb B 1 cb B 1b
t* =
T* 0 B 1 A | B 1 B 1b
 Fundamental Insight
Final Z Decision Slack variables rhs
variables
Table
Z x1 x2 s1 s2 s3 Rhs

1 0 0 0 3/2 1 36
t* = z*-c y* Z*
0 0 0 1 1/3 -1/3 2

0 0 1 0 ½ 0 6
T* = A* S* b*
0 1 0 0 -1/3 1/3 2

t* 1 z*-c y*
= Z*
T* 0 A* S*
b*
1 y*A-c y* y*b 1 y* T T + y*T
= = =
0 S*A S* S*b 0 S* T S*T
 Fundamental Insight
Z Decision variables Slack rhs
variables

1 y A c
*
y * *
yb
* * *
0 SA S Sb
We can use the fundamental insight for sensitivity analysis.
Vector y* plays a very special role. These are shadow prices.
 Fundamental Insight
Optimal value:
m
Z *  y * b   yi *bi
i 1

Old optimal value:

4 
 3 
Z *  y1b1  y2b2  y3b3  0 1 12   36

 2 
18 
New optimal value:
4 
 3 
Z *  0 1 13   37.5

 2 
18 

Z *  1.5
 Summary

If both CB.B-1 and CB.B-1.A-c are non negative for

MAXIMIZE PROBLEM (non-positive for MINIMIZE

PROBLEM), the solution will reach optimal.