Linear Programming: Chapter 7 Sensitivity and Parametric ...

← Back to document page

Linear Programming: Chapter 7Sensitivity and Parametric AnalysisRobert J. VanderbeiOctober 17, 2007Operations 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 0From 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.

Linear Programming: Chapter 7 Sensitivity and Parametric Analysis Robert J. Vanderbei October 17, 2007 Operations Research and Financial Engineering

  Analysis