用对偶单纯形法求对偶问题的最优解

1、用对偶单纯形法求对偶冋题的最优解欧阳引擎(2021.01.01)摘要：在线性规划的应用中，人们发现一个线性规划问题往往 伴随着与之配对的启一个线性规划问题将其中一个称为原问 题，号一个称为对偶问题对偶理论深刻揭示了原问题与对偶冋 题的内在联系由对偶冋题引申出来的对偶解有着重要的经济意 义本文主要介绍了对偶问题的基本形式以及用对偶单纯形法求 解对偶问题的最优解.关键词：线性规划；对偶问题；对偶单纯形UsingDual Simplex MethodToGetThe Optimal SolutionOfTheDualProblemAbstract: In the application of the

2、 linear programming, people find thata linear programming problem is often accompanied by another paired linear programming problem.One is called original problem Another is calledthe dual problem.Duality theory reveals the internal relationsbetween the dual problem and the original problem.The solu

3、tion ofthe dual problem is of a great economic significance.In this paper, we mainly discuss the basic form of the dual problem and how to use dual simplex method toget the optimal solution of the dual problem.Keywords: linear programming ; dual problem ; dual simplex method1引言首先我们先引出什么是线性规划中的对偶冋题任何

4、一个求 极大化的线性规划冋题都有一个求极小化的线性规划问题与之 对应，反之亦然，如果我们把其中一个叫原冋题，则另一个就 叫做它的对偶问题，并称这一対互相联系的两个冋题为一对对 偶问题每个线性规划都有号一个线性规划（对偶问题）与它密切 相关，对偶理论揭示了原问题与对偶问题的内在联系.下面将讨 论线性规划的对偶冋题的基本形式以及用对偶单纯形法求最优 解.在一定条件下，对偶单纯形法与原始单纯形法相比有着显著 的优点.2对偶冋题的形式对偶问题的形式主要包括对称形对偶冋题冈和非对称性对偶问 题.2.1对称形对偶问题设原线性规划问题为Max Z = CE+C2X2+.+C,d”6內+如吃+%2rV| +a

5、22x2 +a2nxn b2(2.1)则称下列线性规划冋题Max+%如x+如乃+弘儿色必+山2必+如片2(2.2)為必+%汀2+ + %儿Sq 兀 no(丿= 1,2,为其对偶冋题，其中”（心12.,加）称其为对偶变量，并称（2.1） 和（2.2）式为一对对称型对偶问题.原始对偶冋题(21)和对偶问题(2.2)之间的对应关系可以用表2-1表示.表2-1X X2 Xn原始约朿Min W】a2%2l“22 %b2儿Cimlam2%.Max ZC1 C2 .-这个表从横向看是原始问题，从纵向看使对偶冋题用矩阵符号表加原始冋题(2.1)和对偶冋题(2.2)为AXb原冋题x (2.3)YA52yi-3y

6、2+17y3-61 + 旳_437-必_72_2淀4,从0无符号限制般可以证明，若原问题中的某个变量无非 负限制，则对偶冋题中的相应约束为等式.3对偶单纯形法对偶问题求解具有重要的意义，有多种方法解决对偶冋题. 下廂介绍用对偶单纯形法来解决线性规划的对偶问题先介绍以 下几个线性规划的基本概念同：基：已知人是约束条件的 系数矩阵，其秩为加.若B是 A中恥邛介非奇异子矩阵（即可逆矩阵），则称B是线性规划 冋题中的一个基.基向量：基中的一列即称为一个基向量基B中共有川个 基向量.非基向量：在人中除了基B之外的一列则称之为基3的非 基向量.基变量：与基向量相应的变量叫基变量，基变量有加个.非基变量：与

7、非基向量相应的变量叫非基变量，非基变量 有nm个.由线性代数的知识知道，如果我们在约束方程组系数矩阵 中找到一个基，令这个基的非基变量为零，再求解这个川元线 性方程组就可得到唯一的解了，这个解我们称之为线性规划的 基本解.首先重新回顾一下单纯形法的基本思想，其迭代的基本思 路杲：先找出一个基可行解，判断其是否为最优解，如果不 是，则转换到另一更优的基可行解，并使目标函数值不断优 化，直到找到最优解为止.我们可以用启一种思路，使在单纯形法每次迭代的基本解 都满足最优检验，但不一定满足非负约束，迭代时使不满足非 负约束的变量个数逐步减少.当全部基变量都满足非负约束条件 时，就得到了最优解，这种算法

8、就是对偶单纯形法.因此，单纯形法是从一个可行解通过迭代转到另一个可行解， 直到检验数满足最优条件为止.对偶单纯形法是从满足对偶可行 性条件出发通过迭代逐步搜索出最优解在迭代过程中始终保持 基解的对偶可行性，而使不可行性逐步消失现把对偶单纯形法 的基本步骤总结如下巴第一，把所给的线性规划冋题转化为标准型；第二，找出一个初始正则基垃，要求对应的单纯形表中的 全部检验数但“右边”列中允许有负数；第三，若“右边”列中各数均非负，则弘已是最优基，于 是，已求得最优解，计算终止否则转为第四步；第四，换基：“右边”列中取值最小（即负的最多）的数 所对应的变量为出基变量计算最小比值&.最小比值出现在末 列，则

9、该列所对应的变量即为进基变量，换基后得新基d,以 出基变量的行和逬基变量列交点处的元素为主元进行单纯形迭 代，再转入第三步.下面用一个例子具体说明用対偶单纯形法求线性规划问题最优 解的步骤：例1求解线性规划冋题min = 15y1+5y2+lly3;添加松弛变量以后的标准型min 用=15“+5儿 + 11儿将每个等式两边乘以-1,则上述冋题转化为min可=15开+5儿+ 11为；如果取入讯九亠）作为初试基变量，有如下初试单纯形表（表）表3-14旳右边人-3-2-210-5儿-51-201-4W-15-5-1100由此可见，两个基变量儿亠均取负值，所以，风所确定的基本解不是基可行解，从而也就不

10、能用单纯形法求解下廂我们 用一种新的方法对偶单纯形法求解此题，并通过例题来说明方 法步骤.对偶单纯形法的基本思想：是保证检验数行全部非正的条 件下，逐步使得“右边”一列各数变成非负一旦“右边”一列 各数均满足了非负条件（即可行性条件），则就获得最优解.现在，“不是可行基（称为正则基），为保证上述方法的 实现，可按下面的方法确定出基变量和进基变量.出基变量的确定可以取任意一个具有负值的基变量（一般可取 最小的）为出基变量在上例中，两个基变量心）都取负值， 且儿=一5最小，故几为出基变量.现在考虑出基变量所对应的负所有元素对每个这2样的元素作比值石，令0 = min 1儿儿4 5右边 TOC o

11、1-5 h z （1）儿315儿2 H_2 o271_32 o -1_2 1225_T 0 -6_2 02y,4 _5 313”0 1 7_7772 _23107 777w27 10 1511000TTT然而在有些问题中，我们很容易找到初始基本解，因此使 用对偶单纯形法求解线性规划问题是有一定条件的，其条件 杲：单纯形表的b列中至少有一个负数.(2)单纯形表中的基本解都满足最优性检验.对偶单纯形法与原始单纯形法相比有两个显著的优点：初始解可以杲不可行解，当检验数都非正时，即可进行基的 变换，这时不需要引入人工变量，因此简化了计算.对于变量个数多于约束方程个数的线性规划问题，采用对偶 单纯形法计

12、算量较少因此对于变量较少、约束较多的线性规划 冋题，可以先将其转化为对偶冋题，然后用对偶单纯形法求解.对变量多于约束条件的线性规划问题，用对偶单纯形法进 行计算可以减少计算的工作量.因此对变量较少，而约束条件很 多的线性规划问题，可先将此冋题转化为对偶问题，然后用对 偶单纯形法求解.用对偶单纯形法求解线性规划冋题的标准型， 要求初始单纯形表检验数行的检验数必须全部非正，若不能满 足这一条件，则不能运用对偶单纯形法求解对偶单纯形法的局 限性主要是，对大多数线性规划问题来说，很难找到一个初始 可行基，因此这种方法在求解线性规划问题时，很少单独应用. 参考文献：吴祈宗.运筹学学习指导及习题集M.北京

13、：机械工业出 版社，2006.孙君曼，冯巧玲，弘慧君，等.线性规划中原问题与对偶冋题转化方法探讨卩郑州：工业学院学报（自然科学版），2001, 16（2）:4446.何坚勇.运筹学基础.北京：清华大学出版社，2000.周汉良，范玉妹.数学规划及其应用.北京：冶金工业出版 社.陈宝林.最优化理论与算法（第二版）.北京：清华大学出版 社，2005.张建中，许绍吉.线性规划.北京：科学出版社，1999.姚恩瑜，何勇，陈仕平.数学规划与组合优化.杭州：浙江 大学出版社，2001.卢开澄.组合数学算法与分析.清华大学出版社，1982.Even. Shimon. Algzithmic Combinator

14、ial. The Macmillan Company, New York, 1973.J . P . Tremblay, R . Manohar. Discrete Mathematical Structures with Applications to Computer Science, 1980.李修睦.图论.华中工学院出版社，1982.Pranava R G. Essays on optimization and incentive contracts C Massachusetts Institute of Technology, Sloan School of Management:

15、 Operations Research Center, 2007: 57- 65.Schechter, M. A Subgradient Duality Theoremt J. Math AnalAppl. , 61(1977), 850-855.Maxims S A. Note on maximizing a submodular set function subject to knap sack constraintJ. Operations Research Letters, 2004, 32 (5):41 -43.Schechter , M . More on Subgradient Duality , J. Math.Anal.Appl. , 71(1979), 251-262.Nemhauser GL, Wolsey L A, Fisher M L. An analysis of approximations formaximizing submodular set functions IIJ. Math. Prog. Study, 1978, 8:73 - 87.Sviride