Page 292 -

272 CHAPTER 6 SIMPLEX-BASED SENSITIVITY ANALYSIS AND DUALITY

Min 2x 1 3x 2
s:t:
1x 1 2x 2 12
4x 1 2x 2 3
6x 1 1x 2 10
6x 1 þ 1x 2 10
x 1 ; x 2 0

With the primal problem now in canonical form for a minimization problem,
we can easily convert to the dual problem using the primal–dual procedure
2
presented earlier in this section. The dual becomes :
0
Max 12u 1 þ 3u 2 þ 10u 10u 00 3
3
s:t:
0
00
1u 1 þ 4u 2 þ 6u 6u 2
3
3
0
00
2u 1 2u 2 1u þ 1u 3
3 3
0
00
u 1 ; u 2 ; u ; u 0
3
3
The equality constraint required two constraints, so we denoted the dual variables
0 00 0
associated with these constraints as u 3 and u 3 . This notation reminds us that u 3
00
and u 3 both refer to the third constraint in the initial primal problem. Because two
dual variables are associated with an equality constraint, the interpretation of the
dual variable must be modified slightly. The dual variable for the equality constraint
Can you write the dual of 0 00
any linear programming 6x 1 1x 2 ¼ 10 is given by the value of u 3 u 3 in the optimal solution to the dual.
problem? Try Problem 14. Hence, the dual variable for an equality constraint can be negative.
Summary
In this chapter we have developed the simple sensitivity analysis introduced in Chapter 3 and also the
dual problem.

l The information in the final simplex tableau provides the sensitivity analysis for the optimal solution.
l Sensitivity analysis can be carried out on the objective function coefficients and the right-hand side
values of the constraints.
l It is important to remember that sensitivity analysis can normally only be carried out on one part of the
problem at a time.
l The original LP problem can be converted into its associated dual LP problem.
l Solving either the primal or dual problem gives the solution to both.

2
Note that the right-hand side of the second constraint is negative. Thus, we must multiply both sides of the
constraint by 1 to obtain a positive value for the right-hand side before attempting to solve the problem with
the Simplex method.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.