ORF 522: Lecture 7 Linear Programming: Chapter 7 ...

1 ORF 522: Lecture 7 Linear Programming: Chapter 7 Sensitivity and Parametric AnalysisRobert J. VanderbeiOctober 3, 2013 Slides last edited at 1:24pm on Thursday 3rdOctober, 2013 Operations Research and Financial Engineering, princeton 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 basisremain optimal?

2 Recall that:z N= (B 1N)TcB cNTherefore, dual variables change 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. An example is worked out in the with the Pivot ToolAn initial dictionary:The optimal dictionary:Question:If the coefficient onx2in original problem were changed from1to1 + (andeverything else remains unchanged), for what range of s does the current basis remainoptimal?3 Ranging with the Pivot Tool ContinuedSet artificial rhs column to artificial objective row to x2 :The range of values is shown at the bottom of the pivot Primal-Dual Simplex MethodAn 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?

3 Answer:5 + 04 + 06 + 0 4 + 0 3 011 0 2 0 Note: only those marked with (*) give inequalities that omit = 0. Tightest: 11 Achieved by: objective row perturbation onx2. Leaves?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+ 5x37 Second PivotUsing theadvancedpivot tool, the current dictionary is:Note: the parameter is not it is there!Question: For which values isdictionary optimal? Answer: 14 0 + 02 0 1 + 02 0 4 + 0 Tightest lower bound: 4 Achieved by: constraint containing basic variablew4. Pivot ContinuedWho shall enter?

4 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 variablew4. Pivot ContinuedWho should leave?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:1 + 01 +1 01 0 11 0 0 1 + 0 That is, 1 2 Range of values is shown at bottom of pivot tool.

5 Invalid ranges are highlighted in Remarks The initial perturbation coefficients do not have to be all ones. In fact, for those objective-function/right-hand-side coefficients that are already of thecorrect sign, the perturbation can bezero. And, those that are positive can be chosen arbitrarily evenrandomly. If all are chosen randomly with a distribution that has a density with respect to Lebesguemeasure, thendegenerate pivots arise with probability zero. Thought experiment: starts at . In reducing , there aren+mbarriers. At each iteration, one barrier is passed the others move about randomly. To get to zero, we must on average pass half the barriers. Therefore, on average the algorithm should take(m+n)