Linear Programming: Chapter 7 Sensitivity and Parametric ...

1 Linear Programming: Chapter 7 Sensitivity and Parametric AnalysisRobert J. VanderbeiOctober 17, 2007 Operations Research and Financial EngineeringPrinceton UniversityPrinceton, NJ 08544 rvdbRestartingConsider an optimal dictionary: = z NTxNxB=x B B definitions ofx B,z N, and :x B=B 1bz N= (B 1N)TcB cN =cTBB , suppose objective coefficients change fromcto adjust current dictionary, recomputez N, and recompute .Note thatx Bremains unchanged. Therefore, Adjusted dictionary isprimal feasible. Apply primal simplex method. Likely to reach optimality it been the right-hand sidesbthat changed, then Adjusted dictionary would bedual feasible. Could apply dual simplex an optimal dictionary: = z NTxNxB=x B B :Ifcwere to change to c=c+ c,for what range of s does the current basis remain optimal?Recall that:z N= (B 1N)TcB cNTherefore, dual variables change as follows by zNwhere zN= (B 1N)T cB cNWe want:z N+ zN 0 From familiar ratio tests, we get(minj N zjz j) 1 (maxj N zjz j) : A similar analysis works for changes to the right-hand side.

2 An example is worked out in the with the Pivot initial dictionary:The optimal dictionary:Question:If the coefficient onx2in original problem were changed to1 + (and everything remains unchanged),for what range of s does the current basis remain optimal?Ranging with the Pivot Tool artificial rhs column to zeros. Set artificial objective row to x2 :The range of values is shown at the bottom of the pivot Primal-Dual Simplex Examplemaximize 3x1+ 11x2+ 2x3subj. to x1+3x2 53x1+3x2 43x2+ 2x3 6 3x1 5x3 4x1, x2, x3 Dictionary: = 3x1+ 11x2+ 2x3w1=5 +x1 3x2w2=4 3x1 3x2w3=6 3x2 2x3w4= 4 +3x1+ 5x3 Note: neither primal nor dual a parameter and perturb: = 3x1+ 11x2+ 2x3 x1 x2 x3w1=5 + +x1 3x2w2=4 + 3x1 3x2w3=6 + 3x2 2x3w4= 4 + +3x1+ 5x3 For large, dictionary : For which values is dictionary optimal? Answer: 3 011 0 2 0 5 + 04 + 06 + 0 4 + 0 Note: only those marked with (*) give inequalities that omit = : 11 Achieved by: objective row perturbation Leaves?

3 Do ratio test using current lowest value, = 11:5 + 11 3x2 04 + 11 3x2 06 + 11 3x2 0 4 + 11 0 Tightest:4 + 11 3x2 by: constraint containing basic the pivot: = 14x1 + 2x3+ w2 x3w1=1+4x1+w2x2= + x1 +3x1+w2 2x3w4= 4 + +3x1+ 5x3 Second PivotUsing theadvancedpivot tool, the current dictionary is:Note: the parameter is not it is there!Question: For which values is dictionary optimal? Answer: 14 0 + 02 0 1 + 02 0 4 + 0 Tightest lower bound: 4 Achieved by: constraint containing basic Pivot ContinuedWho shall enter?Recall the current dictionary:Dodual-typeratio test using current lowest value, = 4:14 +0 4 3y4 4 0 2 +1 4 5y4 0 Tightest: 2 + 1 4 5y4 by: objective term containing nonbasic PivotThe current dictionary is:Question: For which values is dictionary optimal? Answer: + 0 + 0 1 + + 0 Tightest lower bound: 2 Achieved by: objective term containing nonbasic Pivot ContinuedWho shall leave?

4 Recall the current dictionary:Doprimal-typeratio test using current lowest value, = 2:1 +0 2 + 2 + 2 2 + 0 + 2 0 Achieved by: constraint containing basic PivotThe current dictionary is:It soptimal!Also, the range of values includes = 0: 11 0 0 1 + 01 + 01 +1 01 0 That is, 1 2 Range of values is shown at bottom of pivot ranges are highlighted in yellow.