Solved Examples for Chapter 7
Example for Section 7.2
Consider the following problem.
Maximize Z = 2 x1 – 1 x2 + 1 x3,
subject to
3 x1 + 1 x2 + 1 x3 ≤ 60
1 x1 – 1 x2 + 2 x3 ≤ 10
1 x1 + 1 x2 – 1 x3 ≤ 20
and
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Let x4, x5 and x6 denote the slack variables for the respective constraints. The final
simplex tableau is
Coefficient of:
Basic
Variable
Eq.
Z
x2
x3
x5
x6
Right
Side
Z
(0)
1
0
0
3/2
0
3/2
1/2
25
x4
(1)
0
0
0
1
1
-1
-2
10
x1
(2)
0
1
0
1/2
0
1/2
1/2
15
x2
(3)
0
0
1
-3/2
0
-1/2
1/2
5
Now let us conduct sensitivity analysis by independently investigating each of the
following six changes in the original model. For each change, we will use the
sensitivity analysis procedure to revise this final tableau and (if needed) convert it to
proper form from Gaussian elimination for identifying and evaluating the current
basic solution. Then we will test this solution for feasibility and for optimality. If
either test fails, we also will reoptimize to find a new optimal solution.
(a) Change the right-hand sides
from
b1
b2
b3
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
=
60
10
20
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
to
b1
b2
b3
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
=
70
20
10
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
.
Δb =
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−10
10
10
. With this change in b, the entries in the right-side column changes
to the following values:
Z* = y*
b
=
[ ]
2/12/30
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
10
20
70
= 35. S*
b
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−−
2/12/10
2/12/10
211
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
10
20
70
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−5
15
30
.
Therefore, the current (previously optimal) basic solution has become (x1, x2, x3, x4,
x5, x6) = (15, -5, 0, 30, 0, 0), which fails the feasibility test. The dual simplex method
(described in Sec. 8.1) now can be applied to the revised simplex tableau (the first one
shown below) to find the new optimal solution (x1, x2, x3, x4, x5, x6) = (40/3, 0, 10/3,
80/3, 0, 0), as displayed in the second tableau below.
Basic
Variable
Coefficient of:
Right
Side
Z
x1
x2
x3
x4
x5
x6
Z
1
0
0
3/2
0
3/2
1/2
35
x4
0
0
0
1
1
-1
-2
30
x1
0
1
0
1/2
0
1/2
1/2
15
x2
0
0
1
-3/2
0
-1/2
1/2
-5
Z
1
0
1
0
0
1
1
30
x4
0
0
2/3
0
1
-4/3
-5/3
80/3
x1
0
1
1/3
0
0
1/3
2/3
40/3
x3
0
0
-2/3
1
0
– 1/3
-1/3
10/3
(b) Change the coefficients of x1
from
c1
a11
a21
a31
⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥
⎥
=
2
3
1
1
⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥
⎥
to
c1
a11
a21
a31
⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥
⎥
=
1
2
2
0
⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥
⎥
.
Since the only change is in the coefficients of x1, we only need to recompute the
column corresponding to the basic variable x1 in the final tableau:
z1–
1
c
= y*
1
A
–
1
c
=
[ ]
2/12/30
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
0
2
2
– 1 = 2.
A1* = S*
1
A
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−−
2/12/10
2/12/10
211
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
0
2
2
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−1
1
0
.
The revised final tableau is
Basic
Variable
Coefficient of:
Right
Side
Z
x1
x2
x3
x4
x5
x6
Z
1
2
0
3/2
0
3/2
1/2
25
x4
0
0
0
1
1
-1
-2
10
x1
0
1
0
1/2
0
1/2
1/2
15
x2
0
-1
1
-3/2
0
– 1/2
1/2
5
The new column for the basic variable x1 is not in proper form from Gaussian
elimination, so elementary row operations are required to restore proper form. After
doing this, the proper form of the above revised tableau is
Basic
Variable
Coefficient of:
Right
Side
Z
x1
x2
x3
x4
x5
x6
Z
1
0
0
1/2
0
1/2
-1/2
-5
x4
0
0
0
1
1
-1
-2
10
x1
0
1
0
1/2
0
1/2
1/2
15
x2
0
0
1
-1
0
0
1
20
Because of the negative coefficient for x6 in row (0), the current (previously optimal)
basic solution is feasible but not optimal. We can apply the simplex method to the
above tableau in proper form and find the optimal solution (x1, x2, x3, x4, x5, x6) = (5,
0, 0, 50, 0, 20), as displayed below.
Basic
Variable
Coefficient of:
Right
Side
Z
x1
x2
x3
x4
x5
x6
Z
1
0
1/2
0
0
1/2
0
5
x4
0
0
2
-1
1
-1
0
50
x1
0
1
-1/2
1
0
1/2
0
5
x6
0
0
1
-1
0
0
1
20
(c) Change the coefficients of x3
c3
⎡
⎢
⎤
⎥
1
⎡
⎢
⎤
⎥
c3
⎡
⎢
⎤
⎥
2
⎡
⎢
⎤
⎥