
The Simplex Method for Linear Programming 265
zx
1
x
2
x
3
e
1
e
2
s
3
a
1
a
2
rhs Basis
1 −M − 1 −5M +2 −5M − 3 MM000−18Mz
0 −23 4
−10 010 12 a
1
03 2 1 0−10 0 1 6 a
2
01 1 1 001009 s
3
Step 1 tableau:
zx
1
x
2
x
3
e
1
e
2
s
3
a
1
a
2
rhs Basis
1 −
7M+5
2
−
5M−17
4
0 −
M+3
4
M 0
5M+3
4
0 −3M +9 z
0 −
1
2
3
4
1 −
1
4
00
1
4
03 x
3
0
7
2
5
4
0
1
4
−10 −
1
4
13 a
2
0
3
2
1
4
0
1
4
01 −
1
4
06 s
3
Step 2 tableau:
zx
1
x
2
x
3
e
1
e
2
s
3
a
1
a
2
rhs Basis
10
36
7
0 −
4
7
−
5
7
0
7M+4
7
7M+5
7
78
7
z
00
13
14
1 −
3
14
−
1
7
0
3
14
1
7
24
7
x
3
01
5
14
0
1
14
−
2
7
0 −
1
14
2
7
6
7
x
1
00−
2
7
0
1
7
3
7
1 −
1
7
−
3
7
33
7
s
3
Step 3 tableau:
zx
1
x
2
x
3
e
1
e
2
s
3
a
1
a
2
rhs Basis
10
14
3
0 −
1
3
0
5
3
3M+1
3
M 19 z
00
5
6
1 −
1
6
0
1
3
1
6
05 x
3
01
1
6
0
1
6
0
2
3
−
1
6
04 x
1
00−
2
3
0
1
3
1
7
3
−
1
3
−111 e
2
Step 4 tableau:
zx
1
x
2
x
3
e
1
e
2
s
3
a
1
a
2
rhs Basis
12 5 0003MM 27 z
01 1 1001 0 0 9 x
3
06 1