運籌學(xué)教學(xué)中對影子價格和對偶問題最優(yōu)解關(guān)系的討論

李欽

運籌學(xué)教學(xué)中對影子價格和對偶問題最優(yōu)解關(guān)系的討論

李欽

（安徽財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 蚌埠 233030）

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

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

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

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

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

就原問題的最優(yōu)解是否發(fā)生退化，結(jié)合實例討論影子價格和對偶問題最優(yōu)解的關(guān)系，并分析影子價格的經(jīng)濟意義．

1　原問題的最優(yōu)解不發(fā)生退化情況下的影子價格分析

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

1.1　原問題有唯一非退化最優(yōu)解

已知線性規(guī)劃問題（3）的模型為

計算原問題（3）的最優(yōu)表，結(jié)果見表1．

表1 原問題（3）的最優(yōu)表

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

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

1.2　原問題有無窮多非退化最優(yōu)解

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

該線性規(guī)劃問題的模型為

計算原問題（4）的最優(yōu)表，結(jié)果見表3．

表3 原問題（4）的最優(yōu)表

表4 以非基變量作為入基變量時原問題（4）的最優(yōu)表

比較表3和表4，不難發(fā)現(xiàn)，雖然原問題（4）的最優(yōu)基和最優(yōu)解不同，但對偶問題的最優(yōu)解完全相同．對原問題（4）的對偶問題（即模型（5））應(yīng)用對偶單純形法求解，結(jié)果見表５．

表5　原問題（4）的對偶問題（模型（5））的最優(yōu)表

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

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

2　原問題的最優(yōu)解發(fā)生退化情況下的影子價格分析

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

應(yīng)用實例討論原問題最優(yōu)解發(fā)生退化情況下影子價格和對偶問題最優(yōu)解的關(guān)系．

已知某線性規(guī)劃問題的模型為

計算原問題（6）的最優(yōu)表，結(jié)果見表8．

表8 原問題（6）的最優(yōu)表

表9 對表8應(yīng)用對偶單純形法后原問題（6）的最優(yōu)表

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

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

3　結(jié)語

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

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

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

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

[5] 費威．線性規(guī)劃影子價格的求解判斷方法探討[J]．?dāng)?shù)學(xué)的實踐與認識，2012，42（20）：7-16

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

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

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

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

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

[11] 李超英．對偶問題多重解時影子價格的方向性及算法[J]．中國管理科學(xué)，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

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

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