4.5 Sensitivity or Postoptimality Analysis 207
μ 11 +μ 12 +μ 13 = 1
μ 21 +μ 22 +μ 23 = 1
with
μ 11 ≥ 0 ,μ 12 ≥ 0 ,μ 13 ≥ 0 ,μ 21 ≥ 0 ,μ 22 ≥ 0 , μ 23 ≥ 0
Theoptimization problem can be stated in standard form (after adding the slack
variablesαandβ) as
Minimizef= − 1200 μ 12 − 008 μ 13 − 0008 μ 22 − 0002 μ 23
subject to
600 μ 12 + 006 μ 13 + 0003 μ 22 + 0001 μ 23 + α= 1000
400 μ 13 + 0001 μ 22 + 0001 μ 23 + β= 500
μ 11 +μ 12 +μ 13 = 1
μ 21 +μ 22 +μ 23 = 1
μij≥ 0 (i= 1 , 2 ;j= 1 , 2 , 3 ), α≥ 0 , β≥ 0
(E 10 )
Step 3The problem (E 10 ) an now be solved by using the simplex method.c
4.5 Sensitivity or Postoptimality Analysis
In most practical problems, we are interested not only in optimal solution of the LP
problem, but also in how the solution changes when the parameters of the problem
change. The change in the parameters may be discrete or continuous. The study of
the effect of discrete parameter changes on the optimal solution is calledsensitivity
analysisand that of the continuous changes is termedparametric programming. One
way to determine the effects of changes in the parameters is to solve a series of new
problems once for each of the changes made. This is, however, very inefficient from a
computational point of view. Some techniques that take advantage of the properties of
the simplex solution are developed to make a sensitivity analysis. We study some of
these techniques in this section. There are five basic types of parameter changes that
affect the optimal solution:
1.Changes in the right-hand-side constantsbi
- hanges in the cost coefficientsC cj
- hanges in the coefficients of the constraintsC aij
- ddition of new variablesA
5.Addition of new constraints
In general, when a parameter is changed, it results in one of three cases:
1.The optimal solution remains unchanged; that is, the basic variables and their
values remain unchanged.
2.The basic variables remain the same but their values are changed.
3.The basic variables as well as their values are changed.
