线性规划无穷多最优解的讨论.pdfVIP

维普资讯 第 8卷 第 1期 运 筹 与 管 理 Vo1．8，No．1 1999年 3 月 OPER人T10NSRESE人RCH AND M AN人GEM ENT SCIENCE Mar．，1999 线性规划无穷多最优解的讨论 李 军 (西南交通大学经济管理学 院，四川I，成都 ，610031) 摘 要 利用线性规划单纯形表埘线性规划原问题存在无穷多最优解和对偶 问题 存在无穷多最 优解的情况进行 了讨论，并分析 了对偶 问题存在无穷多最优解情况 F的影子价格的方向性 。最后 以实例说明了各种情况。对初学者加深理解及决策者决策参考有…定帮助。 关键词 线性规划；单纯形表 ；无穷多最优解 ；对偶 问题 ；影子价格 中图法分类号 0221．1 TheDiscussonAlternativeOptimalSolutions ofLinearPrOgramming (CollegeofEconomicsandManagement，SouthwestJiaotongUniversity， Chengdu，Sichuan，610031China) Abstract Inthepaper，basedon thesimplex tableau alternativeoptimalsolutionsofthe primallinearprogramming and thedualproblem arediscussed．Then theshadowpriceis analyzedatthecaseofalternativeoptimaldualsolutions．Atlast，somecasesareapplied． Thepapermaybehelpfulforthelearneranddecisionmakerinthefield． Key words linear programming；simplex tableau；alternative optimal solutions；dual problem ；shadowprice 0 引言 当一个线性规划 问题存在无穷多最优解时 ，说明对应的实际问题的最佳方案不唯一 ，这对 决策者决策参考很有益处。因此求出所有的最优解或最优解表达式是非常必要的。但 目前，一 般的教科书对无穷多最优解的判定条件不明确 l，而对求解也极少讨论 。我们知道 ，对偶 问 题的最优解称之为影子价格 ，它表示相应资源的单位收益，是决策者在进行决策 ，合理配置资 源时必须考虑到的因素 。当线性规划对偶问题存在无穷多最优解时，如何理解影子价格?一般 文献几乎没有讨论这种情况。本文将分别对原问题及对偶问题存在无穷多最优解的情况进行 讨论 。这些对于学习运筹学课程的初学者掌握单纯形法并加深理解有一定帮助，对决策者应用 收稿 日期 ；1998 10 2O 李军 ，女，1967年 5月出生 ，博士研究生 ，副教授 ，管理科学 与工程系副主任 维普资讯 88 运 筹 与 管 理 1999年第8卷 决策也有一定的指导意义 。 1 原 问题存在无穷多最优解的讨论 考虑标准型线性规划 fmaxz — CX ．《X — b (1) lX ≥ 0 其 中， 为m×”矩阵，”，其秩为 ；C为 ”维行 向量，记为 C一 (c 一，Cn)；X为 ”维列向 量 ，记为 X一 (z 一， ) ；6为 维列 向量 ，记为6一 (6 ”，6m)。 设有可行基 B一( 一