Transcript Chapter 6 The Revised Simplex Method

Chapter 6
The Revised Simplex Method
 This
method is a modified version of the
Primal Simplex Method that we studied in
Chapter 5.
 It is designed to exploit the fact that in
many practical applications the coefficient
matrix {aij} is very sparse, namely most of
its elements are equal to zero.
6(1).1
 Bottom
–
6(1).2
line:
Don’t update all the columns of the
simplex tableau: update only those
columns that you need!
Standard Form
n
• opt=max
• ~ 
• bi ≥ 0 ,
for all i.
max Z   cj x j
x
j 1

a11 x1  a12 x2  ...  a1n xn  b1
a21 x1  a22 x 2  ...  a2 n x n  b2
.....
.....
...
....
.....
.....
...
....
am1 x1  am 2 x2  ...  amn xn  bm
6(1).3
x j  0 , j  1,...,n
More Convenient Form
max Z
x
s. t .
Z  cx  0
Ax  b
x0
6(1).4
Canonical Form
n
max z   c j x j
j 1
a11x1  a12 x2  ...
 a 1n xn  x n1
a21 x1  a22 x 2  ...
 a2 n x n 
.....
.....
...
....
.....
.....
...
....
am1 x1  am 2 x2  ...  amn xn 
x j  0 , j  1,...,n  m
6(1).5
 b1
 xn 2
 b2
....
....
As in the standard format, bi≥0 for all i.
 x n m  bm
System P
max Z
x
s.t.
Z cx  0
Sx  b
6(1).6

x 0
(6.4)
Example 6.1.1
max Z  4 x1  3 x2
x
2 x1  x2  x3
 40
x1  x2
 x4
 30
x1
 x5  15
x1 , x 2 , x3, x 4 , x 5  0
6(1).7
System P
2 1 1 0 0 


S  1 1 0 1 0 


1
0
0
0
1



b  ( 40, 30, 15)
c  ( 4, 3, 0, 0, 0 ) .
6(1).8
After a number of Pivot Operations
System P’
max Z'
x
s. t .
Z'  c' x'  z'
S' x'  b'
x'  0
6(1).9
Observation
 After
any iteration of the simplex method
the columns of the m basic variables
comprise the columns of the mxm identity
matrix.
 The order in which these columns are
arranged for this purpose is important.
 This order is specified in the BV column of
the simplex tableau.
6(1).10
BV
x3
x4
x1
Z
Eq. #
1
2
3
Z
Example 6.1.2
x1
x2
0
0
1
0
1
1
0
-3
x3
1
0
0
0
0 1 1 0 2 
0 1 0 1 1 
S'  

1 0 0 0

1



b'  (10,1515
, )
c'  (0, 3, 0, 0, 4)
6(1).11
Z'=60.
x4
x5
0
1
0
0
-2
-1
1
4
RHS
10
15
15
60
6.2 The Transformation
 How
can we compute S’ from S ?
 From Linear Algebra we know that any finite
sequence of pivot operations is equivalent to
(left) multiplication by a matrix.
 In other words,
S’ = TS
 The question is then:
T = ??????
6(1).12
What is T ???
 Observation
1:
After any number of iterations of the simplex
method, the columns of the coefficient matrix
corresponding to the basic variables at that
iteration, comprise the identity matrix.
 Observation 2:
Initially, the last m columns of the coefficient
matrix comprise the identity matrix.
6(1).13
Analysis
 If
we group the columns of the basic variables
into I and the nonbasic variables into D’, then
S’ = [I,D’]
 If we do the same for the initial matrix S, we
have
S = [B,D]
where B is the matrix constructed from the
columns of the initial matrix corresponding to
6(1).14the current basic variables.
 Since
S’ = TS, it follows that
S’ = [I,D’] = TS = [TB,TD]
hence
I = TB
from which we conclude that
T = B-1
6(1).15
Example 6.2.1
BV
x3
x4
x5
Z
Eq. #
1
2
3
Z
x1
x2
2
1
1
1
1
0
-4
-3
x3
1
0
0
0
x4
0
1
0
0
2 1 1 0 0 


S  1 1 0 1 0 


1
0
0
0
1



6(1).16
x5
0
0
1
0
RHS
40
30
15
0
BV
Eq. #
x2
x4
x1
Z
1
2
3
Z
S

6(1).17
(2)
x1
0
0
1
0
x2
1
0
0
0
x3
1
-1
0
3
x4
0
1
0
0
x5
-2
1
1
-2
0 1 1 0 2


 0 0 1 1
1

1
1 0 0 0

RHS
10
5
15
90
1 0 0 
(2)
(2)
(2)


I  S.2 , S.4 ,S.1   0 1 0 


0
0
1



 1 2 
(2)
(2)


D'  S.3 ,S.5  1 1


0
1



6(1).18
B  S.I B
1
 S.2 , S.4 , S1   1

0
D  S.I D
6(1).19
0
1
0
2
1
1

1 0


 S.3,S.5  0 0

0 1

 1 0 2 
1


B  1 1 1


0
0
1



S( 2)  B 1S
1 0 2 
 1 0 2 2 1 1 0 0 0 1
1 1 0 1 0  0 0 1 1 1  S(2)
B 1 S  
1
1
1


 







0
0
1
1
0
0
0
1
1
0
0
0
1







6(1).20

Notation:
 IB
= Indices of the basic elements (in
canonical form)
 ID = indices of the nonbasic variables in
increasing order
 cB = Initial cost vector of the basic
variables
 cD = Initial cost vector of the nonbasic
variables
6(1).21
r
= reduced costs vector
 D = columns of the coefficient matrix in the
initial simplex tableau corresponding to the
current nonbasic variables.
6(1).22
Behind the Formula (NILN)
 Each
column of the coefficient matrix in the
new tableau is equal to B-1 times the
corresponding initial column, i.e
new column = B-1 initial column
 This is also true for the right-hand-side
vector, i.e
new RHS = B-1 initial RHS
 Observe that the z-row is not included in
6(1).23 this formulation (why?)
1
D'  B D
b' 
,
,
c'  c B , cD
1
B b
,
,
,
,
(c B :  c I ; cD :  cI )
B
D
,
c'  0, c D
6(1).24
z'  cB B 1b
rD =
1
,
D
(c )  c B B D  cD
correction
C’B = (0,0,...,0)
6(1).25
(NILN)
But how do we compute B-1 ?
 Bad
news:
 We have to compute it as we go along
 Good News:
 We do not have to compute it from scratch
 Observation:
S’ = B-1S = B-1 [M,I] = [B-1M,B-1I] = [B-1M,B-1]
 Hence, B-1 is equal to the matrix comprising the
6(1).26
last m columns of the LHS matrix.