用对偶单纯形法求对偶问题的最优解知识讲解.doc

用对偶单纯形法求对偶问题的最优解精品资料用对偶单纯形法求对偶问题的最优解摘要：在线性规划的应用中，人们发现一个线性规划问题往往伴随着与之配对的另一个线性规划问题.将其中一个称为原问题，另一个称为对偶问题.对偶理论深刻揭示了原问题与对偶问题的内在联系.由对偶问题引申出来的对偶解有着重要的经济意义.本文主要介绍了对偶问题的基本形式以及用对偶单纯形法求解对偶问题的最优解.关键词：线性规划；对偶问题；对偶单纯形Using Dual Simplex Method To Get The Optimal Solution Of The Dual ProblemAbstract：In the application of the linear programming， people find that a linear programming problem is often accompanied by another paired linear programming problem. One is called original problem. Another is called the dual problem. Duality theory reveals the internal relationsbetween the dual problem and the original problem. The solution of the 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 to get the optimal solution of the dual problem.Key words: linear programming；dual problem；dual simplex method字典 - 查看字典详细内容1. 代词 1. another显示对应的拉丁字符的拼音字典 - 查看字典详细内容1 引言首先我们先引出什么是线性规划中的对偶问题.任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题.每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系.下面将讨论线性规划的对偶问题的基本形式以及用对偶单纯形法求最优解.在一定条件下，对偶单纯形法与原始单纯形法相比有着显著的优点.2 对偶问题的形式对偶问题的形式主要包括对称形对偶问题和非对称性对偶问题.2.1对称形对偶问题设原线性规划问题为Max （2.1）则称下列线性规划问题Max （2.2）为其对偶问题，其中称其为对偶变量，并称（2.1）和（2.2）式为一对对称型对偶问题.原始对偶问题（2.1）和对偶问题（2.2）之间的对应关系可以用表2-1表示.表2-1 原始约束Min W对偶约束 Max Z 这个表从横向看是原始问题，从纵向看使对偶问题.用矩阵符号表示原始问题（2.1）和对偶问题（2.2）为原问题 （2.3）对偶问题 （2.4）其中是一个行向量. 2.2 非对称对偶问题 线性规划有时以非对称形式出现，那么如何从原始问题写出它的对偶问题，我们从一个具体的例子来说明这种非对称形式的线性规划问题的对偶问题的建立方法.例1 写出下列原始问题的对偶问题解： 第一约束不等式等价与下面两个不等式约束第二个约束不等式照写第三个不等式变成以 分别表示这四个不等式约束对应的对偶变量，则对偶问题为令 ，则上式的对偶问题变为： 一般可以证明，若原问题中的某个变量无非负限制，则对偶问题中的相应约束为等式.3 对偶单纯形法对偶问题求解具有重要的意义，有多种方法解决对偶问题.下面介绍用对偶单纯形法来解决线性规划的对偶问题.先介绍以下几个线性规划的基本概念：基： 已知是约束条件的系数矩阵，其秩为.若是中阶非奇异子矩阵（即可逆矩阵），则称是线性规划问题中的一个基.基向量：基中的一列即称为一个基向量.基中共有个基向量. 非基向量：在中除了基B之外的一列则称之为基的非基向量. 基变量：与基向量相应的变量叫基变量，基变量有个.非基变量：与非基向量相应的变量叫非基变量，非基变量有个.由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解.首先重新回顾一下单纯形法的基本思想，其迭代的基本思路是：先找出一个基可行解，判断其是否为最优解，如果不是，则转换到另一更优的基可行解，并使目标函数值不断优化，直到找到最优解为止.我们可以用另一种思路，使在单纯形法每次迭代的基本解都满足最优检验，但不一定满足非负约束，迭代时使不满足非负约束的变量个数逐步减少.当全部基变量都满足非负约束条件时，就得到了最优解，这种算法就是对偶单纯形法.因此，单纯形法是从一个可行解通过迭代转到另一个可行解，直到检验数满足最优条件为止.对偶单纯形法是从满足对偶可行性条件出发通过迭代逐步搜索出最优解.在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失.现把对偶单纯形法的基本步骤总结如下:第一，把所给的线性规划问题转化为标准型；第二，找出一个初始正则基，要求对应的单纯形表中的全部检验数 ，但“右边”列中允许有负数；第三，若“右边”列中各数均非负，则已是最优基，于是，已求得最优解，计算终止.否则转为第四步；第四，换基：“右边”列中取值最小（即负的最多）的数所对应的变量为出基变量.计算最小比值.最小比值出现在末列，则该列所对应的变量即为进基变量，换基后得新基，以出基变量的行和进基变量列交点处的元素为主元进行单纯形迭代，再转入第三步.下面用一个例子具体说明用对偶单纯形法求线性规划问题最优解的步骤： 例1 求解线性规划问题min ;添加松弛变量以后的标准型min 将每个等式两边乘以-1，则上述问题转化为min ;如果取作为初试基变量，有如下初试单纯形表（表）表3-1右边0-3-2-210-50-5-1-201-4-15-5-1100由此可见，两个基变量均取负值，所以，所确定的基本解不是基可行解，从而也就不能用单纯形法求解.下面我们用一种新的方法对偶单纯形法求解此题，并通过例题来说明方法步骤.对偶单纯形法的基本思想：是保证检验数行全部非正的条件下，逐步使得“右边”一列各数变成非负.一旦“右边”一列各数均满足了非负条件（即可行性条件），则就获得最优解.现在，不是可行基（称为正则基），为保证上述方法的实现，可按下面的方法确定出基变量和进基变量.出基变量的确定 可以取任意一个具有负值的基变量（一般可取最小的）为出基变量.在上例中，两个基变量都取负值，且最小，故 为出基变量.现在考虑出基变量所对应的负所有元素 ，对每个这样的元素作比值 ，令 （3.1）则 为进基变量.在表2-4中，基变量 所在的行有三个取负值，其值分别为-3，-2，-2.它们对应的检验数分别为-15，-5，-11.于是由此可知， 为进基变量.主元素为 ，对表2-1进行一次迭代便得表2-2，在表2-2的（1）中，基变量 所取之值 ，故 为出基变量.又故 是进基变量；，主元为 .对（1）再作单纯形变换，得表3-1之（2）.由于它的“右边”已列出全部非负，故它就是最优表.最优解为： ， ；最优值 .表3-1 右边（1） 0 0 0 （2）0 1 1 0 0 0 然而在有些问题中，我们很容易找到初始基本解，因此使用对偶单纯形法求解线性规划问题是有一定条件的，其条件是：(1) 单纯形表的b列中至少有一个负数.(2) 单纯形表中的基本解都满足最优性检验.对偶单纯形法与原始单纯形法相比有两个显著的优点：(1) 初始解可以是不可行解，当检验数都非正时，即可进行基的变换，这时不需要引入人工变量，因此简化了计算.(2) 对于变量个数多于约束方程个数的线性规划问题，采用对偶单纯形法计算量较少.因此对于变量较少、约束较多的线性规划问题，可以先将其转化为对偶问题，然后用对偶单纯形法求解.对变量多于约束条件的线性规划问题，用对偶单纯形法进行计算可以减少计算的工作量.因此对变量较少，而约束条件很多的线性规划问题，可先将此问题转化为对偶问题，然后用对偶单纯形法求解.用对偶单纯形法求解线性规划问题的标准型，要求初始单纯形表检验数行的检验数必须全部非正，若不能满足这一条件，则不能运用对偶单纯形法求解.对偶单纯形法的局限性主要是，对大多数线性规划问题来说，很难找到一个初始可行基，因此这种方法在求解线性规划问题时，很少单独应用.参考文献：1 吴祈宗运筹学学习指导及习题集M 北京：机械工业出版社，20062 孙君曼，冯巧玲，孙慧君，等线性规划中原问题与对偶问题转化方法探讨J郑州:工业学院学报（自然科学版），2001，16(2):44463 何坚勇运筹学基础北京：清华大学出版社，20004 周汉良，范玉妹. 数学规划及其应用北京：冶金工业出版社5 陈宝林最优化理论与算法(第二版) 北京：清华大学出版社，20056 张建中，许绍吉. 线性规划. 北京：科学出版社，1999.7 姚恩瑜，何勇，陈仕平数学规划与组合优化杭州：浙江大学出版社，20018 卢开澄组合数学算法与分析清华大学出版社， 19829 Even Shimon Algzithmic Combinatorial The Macmillan Company， New York， 197310 JPTremblay， RManoharDiscrete Mathematical Structures with Applications to Computer Science， 198011 李修睦图论华中工学院出版社， 198212 Pranava R GEssays on optimization and incentive contracts CMassachusetts Institute of Technology， Sloan School of Management: Operations Research Center， 2007: 57- 6513 Schechter，MA Subgradient Duality Theorem，JMath Anal Appl，61(1977)，850-85514 Maxims S A Note on maximizing a submodular set function subject to knap sack constraintJ Operations Research Letters， 2004， 32 (5) : 41 - 4315 Schechter，MMore on Subgradient Duality，JMath.Anal.Appl，71(1979)，251-26216 Nemhauser GL， Wolsey L A， Fisher M LAn analysis of approximations formaximizing submodular set functions IIJMathProgStudy， 1978， 8: 73 - 8717 SviridenkoMA note on maximizing a submodular set function subject to knap sack contraintJOperations Research Letters， 2004， 32: 41 - 4318 卢开澄图论及其应用北京：清华大学出版社，198119 张干宗线性规划（第二版）武汉：武汉大学出版社，200720 周维，杨鹏飞运筹学北京：科学出版社，200821 宁宣熙运筹学实用教程（第二版）北京：科学出版社发行处，2009仅供学习与交流，如有侵权请联系网站删除 谢谢9