運籌學教學中對影子價格和對偶問題最優解關系的討論

李欽

運籌學教學中對影子價格和對偶問題最優解關系的討論

李欽

（安徽財經大學 管理科學與工程學院，安徽 蚌埠 233030）

對偶理論是運籌學課程的重要內容．在對運籌學影子價格及靈敏度分析的教學過程中，如果不討論線性規劃原問題的最優解是否發生退化，學生可能無法正確理解影子價格和對偶問題最優解的關系．通過實例說明，原問題的最優解不發生退化時，影子價格等于對偶問題的最優解；原問題的最優解發生退化時，影子價格表現出方向性，不同方向的影子價格和對偶問題的最優解及資源限量的有效變化范圍密切相關．

線性規劃；影子價格；退化解；靈敏度分析

資源的影子價格反映了資源的稀缺程度，體現了資源對目標函數值的邊際貢獻，是管理決策者實現資源合理配置的重要依據．運籌學教材對影子價格的討論側重于影子價格的一般性定義及經濟意義，對影子價格的計算和分析較少涉及．現有文獻對影子價格的討論主要集中在影子價格的不唯一性和臨界值，圍繞原問題的最優解發生退化或對偶問題存在多重最優解展開分析，但對影子價格和對偶問題最優解的關系尚未達成共識．本文從原問題的最優解是否發生退化的角度，討論影子價格和對偶問題最優解的關系．

已知線性規劃模型LP（Linear Programming）和對偶問題模型DP（Dual Programming）分別為

就如何有效利用資源問題，原問題（1）的最優解提供了有限資源的最優配置信息；對偶問題（2）的最優解提供了資源向量變化導致的目標函數值的改變情況．

就原問題的最優解是否發生退化，結合實例討論影子價格和對偶問題最優解的關系，并分析影子價格的經濟意義．

1　原問題的最優解不發生退化情況下的影子價格分析

應用２個例題分別討論原問題有唯一非退化最優解和無窮多非退化最優解情況下的資源影子價格．

1.1　原問題有唯一非退化最優解

已知線性規劃問題（3）的模型為

計算原問題（3）的最優表，結果見表1．

表1 原問題（3）的最優表

計算原問題（3）的最優基不變時資源的影子價格和有效范圍，結果見表２．

表2 原問題（3）的最優基不變時資源的影子價格和有效范圍

1.2　原問題有無窮多非退化最優解

在《管理運籌學》[3]（第3版）第6章習題5中，題目這樣描述：某公司制造３種產品A，B，C，需要２種資源（即勞動力和原材料），要求確定使總利潤最大的最優生產計劃．

該線性規劃問題的模型為

計算原問題（4）的最優表，結果見表3．

表3 原問題（4）的最優表

表4 以非基變量作為入基變量時原問題（4）的最優表

比較表3和表4，不難發現，雖然原問題（4）的最優基和最優解不同，但對偶問題的最優解完全相同．對原問題（4）的對偶問題（即模型（5））應用對偶單純形法求解，結果見表５．

表5　原問題（4）的對偶問題（模型（5））的最優表

表6 原問題（4）的最優基不變時資源的影子價格和有效范圍

表7 原問題（4）的最優基不變時資源的影子價格和有效范圍

2　原問題的最優解發生退化情況下的影子價格分析

原問題的最優解不發生退化時，無論原問題的最優解是唯一非退化最優解，還是無窮多非退化最優解，資源的影子價格都等于對偶問題的最優解．

應用實例討論原問題最優解發生退化情況下影子價格和對偶問題最優解的關系．

已知某線性規劃問題的模型為

計算原問題（6）的最優表，結果見表8．

表8 原問題（6）的最優表

表9 對表8應用對偶單純形法后原問題（6）的最優表

表10 原問題（6）的最優基不變時資源的影子價格和有效范圍

表11 原問題（6）的最優基不變時資源的影子價格和有效范圍

3　結語

[1] Gal T．Shadow prices and sensitivity analysis in linear programming under degeneracy[J]．OR Spektrum，1986，8（2）：59-71

[2] 《運籌學》教材編寫組．運籌學[M]．4版．北京：清華大學出版社，2012：72-74

[3] 韓伯棠．管理運籌學[M]．3版．北京：高等教育出版社，2010：124

[4] 費威．線性規劃影子價格的定義及計算[J]．高等數學研究，2013，16（4）：5-8

[5] 費威．線性規劃影子價格的求解判斷方法探討[J]．數學的實踐與認識，2012，42（20）：7-16

[6] 吳海平．影子價格非唯一性的經濟學解釋[J]．石家莊鐵道大學學報：社會科學版，2012，6（4）：19-23

[7] 馬贊甫，彭凱．影子價格的特征及其計算[J]．管理學報，2009，6（7）：984-987

[8] 夏少剛，申樹斌，潘權．關于資源影子價格問題的討論[J]．運籌與管理，2002，11（1）：23-27

[9] 劉舒燕．關于資源影子價格不唯一問題的討論[J]．運籌與管理，2001，10（2）：33-36

[10] 李軍．線性規劃無窮多最優解的討論[J]．運籌與管理，1999，8（1）：87-92

[11] 李超英．對偶問題多重解時影子價格的方向性及算法[J]．中國管理科學，1995（2）：42-48

[12] Jansen B，Dejong J J，Roos C，et al．Sensitivity analysis in linear programming： just be careful [J]．European Journal of Operational Research，1997（1）：15-28

[13] Akgul M．A note on shadow prices in linear programming[J]．Journal of the Operational Research Society，1984，35（5）：425-431

[14] 楊桂元．影子價格與影子成本[J]．運籌與管理，2005，14（5）：41-45

[15] Koltai T，Tatay V．A practical approach to sensitivity analysis in linear programming under degeneracy for management decision making [J]．International Journal of Production Economics，2011（1）：392-398

[16] Koltai T，Terlaky T．The difference between the managerial and mathematical interpretation of sensitivity analysis results in linear programming [J]．International Journal of Production Economics，2000，65（3）：257-274

On the relationship between shadow prices and optimal solutions to dual problems in the operational research teaching

LI Qin

（School of Management Science and Engineering，Anhui University of Finance and Economics，Bengbu 233000，China）

Dual theory is very important in operational research. During the teaching of shadow price and sensitivity analysis in operational research，students could hardly understand the relationship between shadow prices and optimal solutions to dual problems if the primal degeneracy in the optimal solutions were not taken into consideration. Examples indicate that the shadow prices are identical with the optimal solutions to dual problems when the optimal solution of the original problem does not degenerate，the shadow prices are interpreted as many-sided when the optimal solution of the original problem degenerates，and different-sided shadow prices are closely related with optimal solutions to dual problems and validity range of resources.

linear programming；shadow price；degeneracy；sensitivity analysis

F224.31∶G462.0

A

10.3969/j.issn.1007-9831.2020.10.013

1007-9831（2020）10-0057-07

2020-03-31

安徽省大規模在線開放課程（MOOC）示范項目（2018mooc482）——《管理運籌學》的階段成果

李欽（1970-），女，安徽東至人，副教授，碩士，從事運籌學和戰略決策分析研究．E-mail：xuqunzhi@126.com