Page 1
Revised Simplex Method 09/23/04 page 1 of 22
(includes both Phases I & II)
© Dennis Bricker
Dept of Mechanical & Industrial Engineering
The University of Iowa
Page 2
Revised Simplex Method 09/23/04 page 1 of 22
(includes both Phases I & II)
© Dennis Bricker
Dept of Mechanical & Industrial Engineering
The University of Iowa
Revised Simplex Method 09/23/04 page 2 of 22
1 2 34 56
Minimize z=3x 5 4 7 5 4 xx x x x ++ + + +
subject to
12 4 6
13 4 5 6
23 4 5
2310
33212
42 3 15
xx x x
xx x x x
xx x x
-+ + =
?
?
+- + + =
?
?
++ + =
?
and 0 1, 6
j
x j =?= …
Because of the lack of a slack variable in each constraint, we must use
Phase I to find an initial feasible basis.
Add variables X
9
, X
10
, X
11
(artificial variables), and
a Phase I objective of minimizing the sum of these three variables.
Page 3
Revised Simplex Method 09/23/04 page 1 of 22
(includes both Phases I & II)
© Dennis Bricker
Dept of Mechanical & Industrial Engineering
The University of Iowa
Revised Simplex Method 09/23/04 page 2 of 22
1 2 34 56
Minimize z=3x 5 4 7 5 4 xx x x x ++ + + +
subject to
12 4 6
13 4 5 6
23 4 5
2310
33212
42 3 15
xx x x
xx x x x
xx x x
-+ + =
?
?
+- + + =
?
?
++ + =
?
and 0 1, 6
j
x j =?= …
Because of the lack of a slack variable in each constraint, we must use
Phase I to find an initial feasible basis.
Add variables X
9
, X
10
, X
11
(artificial variables), and
a Phase I objective of minimizing the sum of these three variables.
Revised Simplex Method 09/23/04 page 3 of 22
Phase One
1 2 3 4 5 6 7 8 9 0 1 b
0 0 0 0 0 0 0 0 1 1 1 0 phase one objective
3 5 4 7 5 4 0 0 0 0 0 0 phase two objective
2 -1 0 1 0 3 0 0 1 0 0 10
1 0 3 -1 3 2 -1 0 0 1 0 12
0 4 2 3 1 0 0 -1 0 0 1 15
Values of basic (artificial) variables are:
i Xi
9 10
10 12
11 15
Page 4
Revised Simplex Method 09/23/04 page 1 of 22
(includes both Phases I & II)
© Dennis Bricker
Dept of Mechanical & Industrial Engineering
The University of Iowa
Revised Simplex Method 09/23/04 page 2 of 22
1 2 34 56
Minimize z=3x 5 4 7 5 4 xx x x x ++ + + +
subject to
12 4 6
13 4 5 6
23 4 5
2310
33212
42 3 15
xx x x
xx x x x
xx x x
-+ + =
?
?
+- + + =
?
?
++ + =
?
and 0 1, 6
j
x j =?= …
Because of the lack of a slack variable in each constraint, we must use
Phase I to find an initial feasible basis.
Add variables X
9
, X
10
, X
11
(artificial variables), and
a Phase I objective of minimizing the sum of these three variables.
Revised Simplex Method 09/23/04 page 3 of 22
Phase One
1 2 3 4 5 6 7 8 9 0 1 b
0 0 0 0 0 0 0 0 1 1 1 0 phase one objective
3 5 4 7 5 4 0 0 0 0 0 0 phase two objective
2 -1 0 1 0 3 0 0 1 0 0 10
1 0 3 -1 3 2 -1 0 0 1 0 12
0 4 2 3 1 0 0 -1 0 0 1 15
Values of basic (artificial) variables are:
i Xi
9 10
10 12
11 15
Revised Simplex Method 09/23/04 page 4 of 22
Page 5
Revised Simplex Method 09/23/04 page 1 of 22
(includes both Phases I & II)
© Dennis Bricker
Dept of Mechanical & Industrial Engineering
The University of Iowa
Revised Simplex Method 09/23/04 page 2 of 22
1 2 34 56
Minimize z=3x 5 4 7 5 4 xx x x x ++ + + +
subject to
12 4 6
13 4 5 6
23 4 5
2310
33212
42 3 15
xx x x
xx x x x
xx x x
-+ + =
?
?
+- + + =
?
?
++ + =
?
and 0 1, 6
j
x j =?= …
Because of the lack of a slack variable in each constraint, we must use
Phase I to find an initial feasible basis.
Add variables X
9
, X
10
, X
11
(artificial variables), and
a Phase I objective of minimizing the sum of these three variables.
Revised Simplex Method 09/23/04 page 3 of 22
Phase One
1 2 3 4 5 6 7 8 9 0 1 b
0 0 0 0 0 0 0 0 1 1 1 0 phase one objective
3 5 4 7 5 4 0 0 0 0 0 0 phase two objective
2 -1 0 1 0 3 0 0 1 0 0 10
1 0 3 -1 3 2 -1 0 0 1 0 12
0 4 2 3 1 0 0 -1 0 0 1 15
Values of basic (artificial) variables are:
i Xi
9 10
10 12
11 15
Revised Simplex Method 09/23/04 page 4 of 22 Revised Simplex Method 09/23/04 page 5 of 22
Iteration 1
Current partition: (B = basis, N = non-basis)
B= {9 10 11}, N= {1 2 3 4 5 6 7 8}
Basis inverse is
1 0 0
0 1 0
0 0 1
Simplex multipliers (dual solution):
i p
1 1
2 1
3 1
() []
1
10 0
1,1,1 0 1 0 [ 1 ,1 ,1]
00 1
B
B
cA
-
??
??
?p= = =
??
??
? ?
Read More