运筹学教学中对影子价格和对偶问题最优解关系的讨论

李钦

运筹学教学中对影子价格和对偶问题最优解关系的讨论

李钦

（安徽财经大学 管理科学与工程学院，安徽 蚌埠 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