清华大学工业工程系运筹学课件

1、Chapter 4 Sensitivity Analysis and Duality Operations Research (1)Dept. of Industrial Engineering2022/8/101Context4.1 A Graphical Introduction to Sensitivity Analysis4.2 Some Important Formulas4.3 Sensitivity Analysis4.4 Sensitivity Analysis When More Than One Parameter is Changed: The 100% Rule4.5

2、Finding the Dual of an LP4.6 Economic Interpretation of the Dual Problem 24.1 A Graphical Introduction to Sensitivity AnalysisGiapettos Woodcarving Example:Types of toysSoldierTrainPrice$27$21Raw material$10$9Variable labor and overhead costs$14$10Labor:carpentry1hour1hourLabor:finishing2hours1hourA

3、vailable resource&Demand:Raw material:unlimitedFinishing hours:100;Carpentry hours:80hoursTrains:unlimited; Soldiers: =40Objective:Maximize weekly profit3Solution:x1=number of soldiers produced each weekx2=number of trains produced each weekSolution:Optimal Solution: z=180, x1=20, x2=604As1,x2,s3Bx1

4、,x2,s3Cx1,x2,s2D5Effect of a Change in an Objective Function Coefficientx2=-C/2 x1+constant/2? =C= ?the current basis remain optimal6Effect of a Change in a RHS on the LPs Optimal Solutionthe current basis remain optimal? =b1A new basic variable in optimal solution.1819c2 is changed and BV remains o

5、ptimal, but the values of decision variables and z-value remain unchanged20 x2 is entering variable212. Changing the Objective Function Coefficient of a basic VariableThe current basis remain optimalThe current basis is no longer optimal:223. Changing the Right-Hand Side of a ConstraintThe current b

6、asis remain optimalThe current basis is no longer optimal=Dual simplex algorithm234. Changing the Column of a VariableBasic Variable:Nonbasic Variable:Remain optimalNo longer optimal245. Adding a New ActivityOptimalNo optimal25Summary (Max Problem)Change in Initial ProblemEffect on Optimal TableauCu

7、rrent Basis Is Still Optimal If:Changing nonbasic objective function coefficient cjCoefficient of xj in optimal row 0 is changedCoefficient of xj in row 0 for current basis is still nonnegativeChanging basic objective function coefficient cjEntire row0 may change Each variable still has a nonnegativ

8、e coefficient in row 0Changing right-hand side of a constraint Right-hand side of constraints and row 0 are changedRight-hand side of each constraint is still nonnegativeChanging the column of a nonbasic variable xj or adding a new variable xjChanges the coefficient for xj in row 0 and xjs constrain

9、t column in optimal tableau The coefficient of xj in row 0 is still nonnegativeNext264.4 Sensitivity Analysis When More Than One Parameter Is Changed: The 100% Rule1. The 100% Rule for Changing Objective Function CoefficientsCase 1: All variable whos objective function coefficients are changed have

10、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 zero27If and only if the objective function coefficient for each variable remains within the allowable range.the current basis remains optimal, both the valu

11、es of the decision variables and objective function remain unchanged. If the objective function coefficient for any variable is outside its allowable range, the current basis is no longer optimal.Case 1: 28Case 2:100% Rule:Define ratio rj:292. The 100% Rule for Changing Right-Hand SidesCase 1: All c

12、onstraints whose right-hand sides are being modified are nonbinding constraints Case 2: At least one of the constraints whose right-hand side is being modified is a binding constraint30If and only if each right-hand side remains within its allowable range. Then both the values of the decision variab

13、les and optimal objective function remain unchanged. If the objective function coefficient for any variable is outside its allowable range, the current basis is no longer optimal.Case 1: 31Case 2:100% Rule:Define ratio rj:324.5 Finding the Dual of an LPNormal max problemNormal min problemDUALCATbTma

14、xmnminbACTmn33Finding the Dual of a Normal Max or Min Problem34Example35Finding the Dual of a Nonnormal LPTransform nonnormal form into normal formFor = constraint: Multiply by -1For = constraint: =For urs : x=x-x”36Example:37Finding the Dual of a Nonnormal Max Problem For = constraints, dual variab

15、les must satisfy =0For = constraints, dual variables is ursFor urss variable, the dual constraint is an equality constraint38Example:39Finding the Dual of a Nonnormal Min Problem For = constraints, dual variables must satisfy =0For = constraints, dual variables is ursFor urss variable, the dual cons

16、traint is an equality constraint40Exercise:414.6 Economic Interpretation of the Dual ProblemInterpreting the Dual of a Max ProblemResource/productAmount of Resource AvailabbleResourceDeskTableChairLumber8 board ft6 board ft1 board ft48 board ftFinishing4hours2hours1.5hours20hoursCarpentry2hours1.5hours0.5hours8hoursSelling price$60$30$204