Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
True / False
1. The range of optimality is useful only for basic variables.
a.
True
b.
False
2. The range of optimality is calculated by considering changes in the cj − zj value of the variable in question.
a.
True
b.
False
3. As long as the objective function coefficient remains within the range of optimality, the variable values will not change
although the value of the objective function could.
a.
True
b.
False
4. If the simplex tableau is from a maximization converted from a minimization, the signs and directions of the
inequalities that give the objective function ranges will need to be adjusted to apply to the original coefficients.
a.
True
b.
False
5. The ranges for which the right-hand side values are valid are the same as the ranges over which the dual prices are
valid.
a.
True
b.
False
6. There is a dual price associated with each decision variable.
a.
True
b.
False
7. The dual price for an equality constraint is the zj value for its artificial variable.
a.
True
b.
False
8. The entries in the associated slack column of the final tableau indicate the changes in the values of the current basic
variables corresponding to a one-unit increase in the right-hand side.
a.
True
b.
False
9. The range of optimality for a basic variable defines the objective function coefficient values for which the variable will
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
remain part of the current optimal basic feasible solution.
a.
True
b.
False
10. The dual price is the improvement in value of the optimal solution per unit increase in the value of the right-hand side
associated with a linear programming problem.
a.
True
b.
False
Multiple Choice
11. Dual prices and ranges for objective function coefficients and right-hand side values are found by considering
a.
dual analysis.
b.
optimality analysis.
c.
ranging analysis.
d.
sensitivity analysis.
12. For the basic feasible solution to remain optimal
a.
all cj − zj values must remain ≤ 0.
b.
no objective function coefficients are allowed to change.
c.
the value of the objective function must not change.
d.
each of the above is true.
13. A one-sided range of optimality
a.
always occurs for non-basic variables.
b.
always occurs for basic variables.
c.
indicates changes in more than one coefficient.
d.
indicates changes in a slack variable’s coefficient.
14. A linear programming problem with the objective function 3x1 + 8x2 has the optimal solution x1 = 5, x2 = 6. If c2
decreases by 2 and the range of optimality shows 5 ≤ c2 ≤ 12, the value of Z
a.
will decrease by 12.
b.
will decrease by 2.
c.
will not change.
d.
cannot be determined from this information.
15. The improvement in the value of the optimal solution per-unit increase in a constraint’s right-hand side is
a.
the slack value.
b.
the dual price.
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
c.
never negative.
d.
the 100% rule.
16. The dual variable represents
a.
the marginal value of the constraint
b.
the right-hand side value of the constraint
c.
the artificial variable
d.
the technical coefficient of the constraint
17. The range of feasibility indicates right-hand side values for which
a.
the value of the objective function will not change.
b.
the values of the decision variables will not change.
c.
those variables which are in the basis will not change.
d.
more simplex iterations must be performed.
18. If the dual price for b1 is 2.7, the range of feasibility is 20 ≤ b1 ≤ 50, and the original value of b1 was 30, which of the
following is true?
a.
There currently is no slack in the first constraint.
b.
We would be willing to pay up to $2.70 per unit for up to 20 more units of resource 1.
c.
If only 25 units of resource 1 were available, profit would drop by $13.50.
d.
Each of the above is true.
19. The number of constraints to the dual of the following problem is:
Max Z
= 3x1 + 2x2 + 6x3
s.t.
4x1 + 2x2 + 3x3 ≥ 100
2x1 + x2 − 2x3 ≤ 200
4x2 + x3 ≥ 200
a.
1.
b.
2.
c.
3.
d.
4.
20. Given the simplex tableau for the optimal primal solution
a.
the values of the dual variables can be found from the cj − zj values of the slack/surplus variable columns.
b.
the values of the dual surplus variables can be found from the cj − zj values of the primal decision variable
columns.
c.
the value of the dual objective function will be the same as the objective function value for the primal
problem.
d.
each of the above is true.
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
Subjective Short Answer
21. Given the following linear programming problem
Max Z
0.5x1 + 6x2 + 5x3
s.t.
4x1 + 6x2 + 3x3 ≤ 24
1x1 + 1.5x2 + 3x3 ≤ 12
3x1 + x2 ≤ 12
and the final tableau is
x1
x2
x3
s1
s2
s3
Basis
cB
.5
6
5
0
0
0
x2
6
1
1
0
.22
−.22
0
2.67
x3
5
0
0
1
.11
−.44
0
2.67
s3
0
2.33
0
0
−.22
.22
1
9.33
zj
4
6
5
.77
.88
0
29.33
cj − zj
.5
0
0
−.77
−.88
0
a.
Find the range of optimality for c1, c2, c3, c4, c5, and c6.
b.
Find the range of feasibility for b1, b2, and b3.
c1 ≤ 4
2.5 < c2 ≤ 10
3 < c3 ≤ 12
c4 ≤ .77
−1.5 ≤ c6 ≤ 3.5
b.
12 ≤ b1 ≤ 48
6 ≤ b2 ≤ 24
b3 ≥ 2.67
22. For the following linear programming problem
Max Z
−2x1 + x2 − x3
s.t.
2x1 + x2 ≤ 7
1x1 + x2 + x3 ≥ 4
the final tableau is
x1
x2
x3
s1
s2
a2
Basis
cB
−2
1
−1
0
0
−M
s2
0
1
0
−1
1
1
−1
3
x2
1
2
1
0
1
0
0
7
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
zj
2
1
0
1
0
0
7
cj − zj
−4
0
1
−1
0
−M
a.
Find the range of optimality for c1, c2 , c3. c4, c5 , and c6.
b.
Find the range of feasibility for b1, and b2.
a.
0 ≤ c2
−1 ≤ c5 ≤ 1
b.
b2 ≤ 7
23. Write the dual of the following problem
Min Z
= 2x1 − 3x2 + 5x3
s.t.
−3x1 + 2x2 + 5x3 ≥ 7
2x1 − x3 ≥ 5
4x 2 + 3x3 ≥ 8.
s.t.
−3y1 +2y2 ≤ 2
2y1 + 4y3 ≤ −3
5y1 − y2 + 3y3 ≤ 5
24. Given the following linear programming problem
Max
10x1 + 12x2
s.t.
1x1 + 2x2 ≥ 40
5x1 + 8x2 ≤ 160
1x1 + 1x2 ≤ 40
x1, x2 ≥ 0
the final tableau is
x1
x2
s1
s2
s3
Basis
cB
10
12
0
0
0
x2
12
0
1
−2.5
−.5
0
20
x1
10
1
0
4
1
0
0
s3
0
0
0
−1.5
−.5
1
20
zj
10
12
10
4
0
240
cj − zj
0
0
−10
−4
0
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
a.
Find the range of optimality for c1 and c2.
b.
Find the range of feasibility for b1, b2, and b3.
c.
Find the dual prices.
7.5 ≤ c1 < ∞
b.
c.
25. For this optimal simplex tableau the original right-hand sides were 100 and 90. The problem was a maximization.
x1
x2
x3
s1
s2
Basis
cB
2
4
8
0
0
x3
8
0
.48
1
.12
−.04
8.4
x1
2
1
.2
0
−.2
.4
16
zj
2
4.24
8
.56
.48
99.2
cj − zj
0
−.24
0
−.56
−.48
a.
What would the new solution be if there had been 150 units available in the first constraint?
b.
What would the new solution be if there had been 70 units available in the second
constraint?
b.
26. For this optimal simplex tableau, the right-hand sides for the two original ≥ constraints were 300 and 250. The
problem was a minimization.
x1
x2
x3
s1
s2
Basis
cB
−100
−110
−95
0
0
x3
−95
0
−1.5
1
1
−1.5
75
x1
−100
1
2
0
−1
1
50
zj
−100
−57.5
−95
5
42.5
−12125
cj − zj
0
−52.5
0
−5
−42.5
a.
What would the new solution be if the right-hand side value in the first constraint had been
325?
b.
What would the new solution be if the right-hand side value for the second constraint had
been 220?
a.
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
27. Creative Kitchen Tools manufactures a wide line of gourmet cooking tools from stainless steel. For the coming
production period, there is demand of 1200 for 8 quart stock pots, and unlimited demand for 3 quart mixing bowls and
large slotted spoons. In the following model, the three variables measure the number of pots, bowls, and spoons to make.
The objective function measures profit. Constraint 1 measures steel, constraint 2 measures manufacturing time, constraint
3 measures finishing time, and constraint 4 measures the stock pot demand.
Max
5x1 + 3x2 + 6x3
s.t.
3x1 + 1x2 + 2x3 ≤ 15000
4x1 + 4x2 + 5x3 ≤ 18000
2x1 + 1x2 + 2x3 ≤ 10000
x1 ≤ 1200
x1, x2, x3 ≥ 0
The final tableau is:
x1
x2
x3
s1
s2
s3
s4
Basis
cB
5
3
6
0
0
0
0
s1
0
0
−2
−1.75
1
−.75
0
0
1500
s4
0
0
1
1.25
0
.25
0
1
3300
s3
0
0
−1
−.5
0
−.5
1
0
1000
x1
5
1
1
1.25
0
.25
0
0
4500
zj
5
5
6.25
0
1.25
0
0
22500
cj − zj
0
−2
−.25
0
−1.25
0
0
a.
Calculate the range of optimality for c1, c2, and c3.
b.
Calculate the range of feasibility for b1, b2, b3, and b4.
c.
Suppose that the inventory records were incorrect and the company really has only 14000
units of steel. What effect will this have on your solution?
d.
Suppose that a cost increase will change the profit on the pots to $4.62. What effect will this
have on your solution?
e.
Assume that the cost of time in production and finishing is relevant. Would you be willing to
pay a $1.00 premium over the normal cost for 1000 more hours in the production
department? What would this do to your solution?
a.
b.
13500 ≤ b1 < ∞
480 ≤ b2 ≤ 20000
This would affect only the amount of slack, decreasing it from 1500 to 500.
b.
x3 = 30, x1 = 80, Z = 10850
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
28. Stelle Office Supplies must fill an order for 2000 modular office dividers. Each divider consists of a frame, a set of
legs, and a panel. SOS has limited production and finishing time available and is considering the purchase of some of the
components. Let x1, x2, and x3 be the number of frames, leg sets, and panels to make, and x4, x5, and x6 be the number of
each to buy. The model reflects the costs to be minimized, the amount of production time, the amount of assembly time,
and the need for 2000 of each component.
Min
20x1 + 14x2 + 15x3 + 28x4 + 20x5 + 25x6
s.t.
30x1 + 40x2 + 25x3 ≤ 180000
15x1 + 10x2 + 30x3 ≤ 90000
x1 + x4 = 2000
x2 + x5 = 2000
x3 + x6 = 2000
all xi ≥ 0
The final tableau is
x1
x2
x3
x4
x5
x6
s1
s2
Basis
cB
−20
−14
−15
−28
−20
−25
0
0
x6
−25
0
0
0
.5
.333
1
0
−.033
666.67
s1
0
0
0
0
−17.5
−31.67
0
1
−.833
6666.67
x1
−20
1
0
0
1
0
0
0
0
2000
x2
−14
0
1
0
0
1
0
0
0
2000
x3
−15
0
0
1
−.5
−.333
0
0
.033
1333.33
zj
−20
−14
−15
−25
−17.33
−25
0
.33
68667
cj − zj
0
0
0
−3
−2.67
0
0
−.33
a.
Calculate the range of optimality for all of the objective function coefficients.
b.
Calculate the range of feasibility for the first two right-hand sides.
c.
How much less expensive would it have to be to buy frames before you would consider it?
d.
How much more expensive would legs have to be to make before you would change your
solution?
e.
What would the total cost be if the cost to make a panel increased by $3.00?
f.
What would you be willing to pay for more production time?
g.
What would happen to the total cost if the amount of assembly time decreased by 2000
hours?
d.
This change is out of the range of optimality so the basis would change.
price, so it makes sense to do this. The new solution would be
x1 = 4500 + .25(1000) = 4750
Z = 22500 + (1.25 − 1)(1000) = 22750
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
25 ≤ c4 < ∞
15 ≤ c6 ≤ 31
29. Write the dual to the following problem.
Min
12x1 + 15x2 + 20x3 + 18x4
s.t.
x1 + x2 + x3 + x4 ≥ 50
3x1 + 4x3 ≥ 60
2x2 + x3 − 2x4 ≤ 10
x1, x2, x3, x4 ≥ 0
Max
50u1 + 60u2 − 10u3
s.t.
u1 + 3u2 ≤ 12
u1 − 2u3 ≤ 15
u1 + 4u2 − u3 ≤ 20
u1 + 2u3 ≤ 18
u1, u2, u3 ≥ 0
30. The primal problem is
Min
2x1 + 5x2 + 4x3
s.t.
x1 + 3x2 + 3x3 ≥ 30
3x1 + 7x2 + 5x3 ≥ 70
x1, x2, x3 ≥ 0
The final tableau for its dual problem is
u1
u2
s1
s2
s3
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
Basis
cB
30
70
0
0
0
u2
70
0
1
3/4
0
−1/4
1/2
s2
0
0
0
−3/2
1
−1/2
0
u1
30
1
0
−5/4
0
3/4
1/2
zj
30
70
15
0
5
50
cj − zj
0
0
−15
0
−5
Give the complete solution to the primal problem.
x1 = 15, x2 = 0, x3 = 5, s1 = 0, s2 = 0, Z = 50
31. The linear programming problem:
Max
6x1 + 2x2 + 3x3 + 4x4
s.t.
x1 + x2 + x3 + x4 ≤ 100
4x1 + x2 + x3 + x4 ≤ 160
3x1 + x2 + 2x3 + 3x4 ≤ 240
x1, x2, x 3, x4 ≥ 0
has the final tableau:
x1
x2
x3
x4
s1
s2
s3
Basis
cB
6
2
3
4
0
0
0
x2
2
0
1
1/2
0
3/2
0
−1/2
30
x1
6
1
0
0
0
−1/3
1/3
0
20
x4
4
0
0
1/2
1
−1/6
−1/3
1/2
50
zj
6
2
3
4
2.33
.67
1
380
cj − zj
0
0
0
0
−2.33
−.67
−1
Fill in the table below to show what you would have found if you had used The Management Scientist to solve this
problem.
LINEAR PROGRAMMING PROBLEM
MAX
6X1+2X2+3X3+4X4
S.T.
1) 1X1 + 1X2 + 1X3 + 1X4 < 100
2) 4X1 + 1X2 + 1X3 + 1X4 < 160
3) 3X1 + 1X2 + 2X3 + 3X4 < 240
OPTIMAL SOLUTION
Objective Function Value =
Variable
Value
Reduced Cost
X1
______
______
X2
______
______
X3
______
______
X4
______
______
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
Constraint
Slack/Surplus
Dual Price
1
______
______
2
______
______
3
______
______
OBJECTIVE COEFFICIENT RANGES
Variable
Lower Limit
Current Value
Upper Limit
X1
______
______
______
X2
______
______
______
X3
______
______
______
X4
______
______
______
RIGHT HAND SIDE RANGES
Constraint
Lower Limit
Current Value
Upper Limit
1
______
______
______
2
______
______
______
3
______
______
______
MAX
6X1 + 2X2 + 3X3 + 4X4
Variable
Value
Reduced Cost
X1
20.000
0.000
X2
30.000
0.000
X3
0.000
X4
50.000
0.000
Constraint
Slack/Surplus
Dual Price
1
0.000
0.333
2
0.000
0.667
3
0.000
1.000
Variable
Lower Limit
Current Value
Upper Limit
X1
4.000
6.000
7.000
X2
2.000
2.000
4.000
X3
3.000
3.000
X4
4.000
4.000
6.000
Constraint
Lower Limit
Current Value
Upper Limit
1
80.000
100.000
160.000
2
100.000
160.000
310.000
3
140.000
240.000
300.000
Essay
32. For an objective function coefficient change outside the range of optimality, explain how to calculate the new optimal
solution. Must you return to the (revised) initial tableau?
Chapter 18 – Simplex-Based Sensitivity Analysis and Duality
33. When sensitivity calculations yield several potential upper bounds and several lower bounds, how is the range
determined?
34. Explain why the zj value for a slack variable is the dual price.
35. Explain how to put an equality constraint into canonical form and how to calculate its dual variable value.
36. Explain the simplex tableau location of the dual constraint for each type of constraint.