清华大学工业工程系运筹学课件(ppt).ppt

1、2020/9/22,1,Chapter 4 Sensitivity Analysis and Duality,Operations Research (1),Dept. of Industrial Engineering,2,Context,4.1 A Graphical Introduction to Sensitivity Analysis 4.2 Some Important Formulas 4.3 Sensitivity Analysis 4.4 Sensitivity Analysis When More Than One Parameter is Changed: The 100

2、% Rule 4.5 Finding the Dual of an LP 4.6 Economic Interpretation of the Dual Problem,3,4.1 A Graphical Introduction to Sensitivity Analysis,Giapettos Woodcarving Example:,Available resource Soldiers: =40 Objective:Maximize weekly profit,4,Solution:,x1=number of soldiers produced each week x2=number

3、of trains produced each week,Solution:,Optimal Solution: z=180, x1=20, x2=60,5,6,Effect of a Change in an Objective Function Coefficient,x2=-C/2 x1+constant/2 ? =C= ?,the current basis remain optimal,7,Effect of a Change in a RHS on the LPs Optimal Solution,the current basis remain optimal,? =b1= ?,

4、b1= 100+D,2x1+x2= 100+D x1+x2=80,x1= 20+D x2=60-D,8,Shadow Prices,Shadow Prices for the ith constraint of an LP to be the amount by which the optimal z-value is improvedincreased in a max problem and decreased in min problem if the rhs of the ith constraint is increased by 1,9,Max Problem New optima

5、l z-value=(old optimal z-value)+(Constraint is shadown price) bi Min Problem New optimal z-value=(old optimal z-value)-(Constraint is shadown price) bi,10,Importance of Sensitivity Analysis:,11,4.2 Some Important Formulas,12,Tableau,13,Simplifying Formula for Slack, Excess, and Artificial Variables,

6、If they are BV, its coefficients =?,14,Example 1: Compute the optimal tableau,15,16,4.3 Sensitivity Analysis,Criteria: A simplex tableau (max problem) for a set of basic variables BV is optimal if and only if each constraint has a nonnegative right-hand side and each variable has a nonnegative coeff

7、icient in row 0,Methods: Using the matrix forms, determine how changes in the LPs parameters change the rhs and row 0 of the optimal tableau If each variable in row 0 has a nonnegative coefficient and each constraint has a nonnegative rhs, BV is still optimal. Otherwise, BV is no longer optimal.,17,

8、Example:,Optimal basis? BVs values Z-value,18,1. Changing the Objective Function Coefficient of a Nonbasic Variable,The current basis remain optimal,The current basis is no longer optimal =A new basic variable in optimal solution.,19,20,c2 is changed and BV remains optimal, but the values of decisio

9、n variables and z-value remain unchanged,21,22,2. Changing the Objective Function Coefficient of a basic Variable,The current basis remain optimal,The current basis is no longer optimal:,23,3. Changing the Right-Hand Side of a Constraint,The current basis remain optimal,The current basis is no longe

10、r optimal =Dual simplex algorithm,24,4. Changing the Column of a Variable,Basic Variable:,Nonbasic Variable: Remain optimal No longer optimal,25,5. Adding a New Activity,Optimal,No optimal,26,Summary (Max Problem),Next,27,4.4 Sensitivity Analysis When More Than One Parameter Is Changed: The 100% Rul

11、e,1. The 100% Rule for Changing Objective Function Coefficients,Case 1: All variable whos objective function coefficients are changed have nonzero reduced costs in the optimal row 0,Case 2: At least one variable whose objective function coefficient is changed has a reduced cost of zero,28,If and onl

12、y if the objective function coefficient for each variable remains within the allowable range.the current basis remains optimal, both the values of the decision variables and objective function remain unchanged. If the objective function coefficient for any variable is outside its allowable range, th

13、e current basis is no longer optimal.,Case 1:,29,Case 2:,100% Rule: Define ratio rj:,30,2. The 100% Rule for Changing Right-Hand Sides,Case 1: All constraints whose right-hand sides are being modified are nonbinding constraints,Case 2: At least one of the constraints whose right-hand side is being m

14、odified is a binding constraint,31,If and only if each right-hand side remains within its allowable range. Then both the values of the decision variables and optimal objective function remain unchanged. If the objective function coefficient for any variable is outside its allowable range, the curren

15、t basis is no longer optimal.,Case 1:,32,Case 2:,100% Rule: Define ratio rj:,33,4.5 Finding the Dual of an LP,Normal max problem,Normal min problem,DUAL,34,Finding the Dual of a Normal Max or Min Problem,35,Example,36,Finding the Dual of a Nonnormal LP,Transform nonnormal form into normal form,For =

16、 constraint: Multiply by -1,For = constraint: =,For urs : x=x-x”,37,Example:,38,Finding the Dual of a Nonnormal Max Problem,For = constraints, dual variables must satisfy =0,For = constraints, dual variables is urs,For urss variable, the dual constraint is an equality constraint,39,Example:,40,Finding the Dual of a Nonnormal Min Problem,For = constraints, dual variables must satisfy =0,For = constraints, dual variables is urs,For urss variable, the dual constraint is an equality constraint,41,Exercise:,42,4.6 Economic Interpretation of the Dual Problem,Interpreting the Dual of a Max Prob