Page 284 -

264 CHAPTER 6 SIMPLEX-BASED SENSITIVITY ANALYSIS AND DUALITY

2 3 2 3 2 3
b 1 a 1j 0
6 7 6 7 6 0 7
6 b 2 7 6 a 2j 7 6 7
6
6 : : 7 þ b i 6 : 7 6 7 (6:8)
:
6 7
6
6
7
7
! 6 b m 7 6 a mj 7 6 7
7
6 7
6
7
!
:
:
4 5
5
4
5
4
:
:
:
0
Current solution Column of the final simplex
(last column of tableau corresponding to the
the final simplex slack variable associated
tableau) with constraint i
The inequalities are used to identify lower and upper limits on b i . The range of
feasibility can then be established by the maximum of the lower limits and the
minimum of the upper limits.
Similar arguments can be used to develop a procedure for determining the range
of feasibility for the right-hand side value of a greater-than-or-equal-to constraint.
Essentially the procedure is the same, with the column corresponding to the surplus
variable associated with the constraint playing the central role. For a general
greater-than-or-equal-to constraint i, we first calculate the range of values for b i
that satisfy the inequalities shown in inequality (6.9).
2 3 2 3 2 3
b 1 a 1j 0
6 7 6 7 6 0 7
6 b 2 7 6 a 2j 7 6 7
6
6 : : 7 b i 6 : 7 6 7 (6:9)
:
7
6
7
6 7
6
! 4 b m 5 4 a mj 5 4 5
6 7
: 7
7
6
!
:
6
7
7
6 7
6
:
:
:
0
Current solution Column of the final simplex
(last column of tableau corresponding to the
the final simplex surplus variable associated
tableauÞ with constraint i
Once again, these inequalities establish lower and upper limits on b i . Given these
limits, the range of feasibility is easily determined.
A range of feasibility for the right-hand side of an equality constraint can also be
Try Problem 4 to make calculated. To do so for equality constraint i, one could use the column of the final
sure you can compute simplex tableau corresponding to the artificial variable associated with constraint i in
the range of feasibility by
working with the final Equation (6.8). Because we have suggested dropping the artificial variable columns
simplex tableau. from the simplex tableau as soon as the artificial variable becomes non-basic, these
columns will not be available in the final tableau. Thus, more involved calculations
are required to compute a range of feasibility for equality constraints. Details may be
found in more advanced texts.
As long as the change in a right-hand side value is such that b i stays within its
range of feasibility, the same basis will remain feasible and optimal. Changes that
Changes that force b i
outside its range of force b i outside its range of feasibility will force us to re-solve the problem to find the
feasibility are normally new optimal solution consisting of a different set of basic variables. (More advanced
accompanied by
changes in the dual linear programming texts show how it can be done without completely re-solving the
prices. problem.) In any case, the calculation of the range of feasibility for each b i is
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.