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

用对偶单纯形法求对偶问题的最优解摘要：在线性规划的应用中，人们发现一个线性规划问题往往伴随着与之配对的另一个线性规划问题.将其中一个称为原问题，另一个称为对偶问题.对偶理论深刻揭示了原问题与对偶问题的内在联系.由对偶问题引申出来的对偶解有着重要的经济意义.本文主要介绍了对偶问题的基本形式以及用对偶单纯形法求解对偶问题的最优解.关键词：线性规划；对偶问题；对偶单纯形UsingDualSimplexMethodToGetTheOptimalSolutionOfTheDualProblemAbstract：Intheapplicationofthelinearprogramming，peoplefindthatalinearprogrammingproblemisoftenaccompaniedbyanotherpairedlinearprogrammingproblem.Oneiscalledoriginalproblem.Anotheriscalledthedualproblem.Dualitytheoryrevealstheinternalrelationsbetweenthedualproblemandtheoriginalproblem.Thesolutionofthedualproblemisofagreateconomicsignificance.Inthispaper，wemainlydiscussthebasicformofthedualproblemandhowtousedualsimplexmethodtogettheoptimalsolutionofthedualproblem.Keywords:linearprogramming；dualproblem；dualsimplexmethod1引言首先我们先引出什么是线性规划中的对偶问题.任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题.每个线性规划都有另一个线性规划（对偶问题）与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系.下面将讨论线性规划的对偶问题的基本形式以及用对偶单纯形法求最优解.在一定条件下，对偶单纯形法与原始单纯形法相比有着显著的优点.2对偶问题的形式对偶问题的形式主要包括对称形对偶问题网和非对称性对偶问题.【对称形对偶问题设原线性规划问题为MaxZ=cx+cx+...+cx1122nn

ax+ax+...+ax<b1111221nn1ax+ax+...+ax<b2112222nn2其中Y=G1,七,...,ym)是一个行向量.()ax+ax+...+ax:m11m2()ax+ax+...+ax:m11m2/2mnnxx.>0.(j=1,2,...,n)<bn则称下列线性规划问题MaxW=by+by+...+by1122mmay+ay+...+ay<c1111221nn1ay+ay+...+ay<c2112222nn2<……()ay+ay+...+ay<c

m11m2/2mnn、n、y.>0.（j=1,2,...,m）为其对偶问题，其中y（i=1,2,...,m）称其为对偶变量，并称（）和（）式为一对对称型对i偶问题.x气x2…x原始约束MinWyma11a12...a1naa...a21222n............am1am2...amn.<b"2...bm对偶约束>>...>[MaxZcc...c原始对偶问题（）和对偶问题（）之间的对应关系可以用表2-1表示.表2-1这个表从横向看是原始问题，从纵向看使对偶问题.用矩阵符号表示原始问题（）和对偶问题（）为maxZ-CX|AX<b原问题〔X-0（）|minW-Yb对偶问题YA<CY>0()非对称对偶问题线性规划有时以非对称形式出现，那么如何从原始问题写出它的对偶问题，我们从个具体的例子来说明这种非对称形式的线性规划问题的对偶问题的建立方法例1写出下列原始问题的对偶问题maxZ=5x-6x+7x+4xx+2x—x—x=—76x-3x+x-7x<14<1234-28x-17x+4x+2x>-3、xj>02(j=1,2,3,4)解：第一约束不等式等价与下面两个不等式约束x+2x—x—x<-7&—x—2x+x+x<7第二个约束不等式照写6x-3x+x-7x<14第三个不等式变成28x1+17x2-4x3-2x4<3以y;,y;,，2,y‘分别表示这四个不等式约束对应的对偶变量，则对偶问题为minW=-7y1+7y2+14y+3y1123y1一y2+6y+28y>511232y1-2y2-3y+17y>-61123一y1+y2+y-4y>71123-y1+y2-7y-2y>41123y1,y2,y,y>01123令y1=y：-y;，则上式的对偶问题变为:minW=-7y+14y+3yy+6y+28y>5i232y-3y+17y>—6123^-七+y2-4y3>7-y-7y-2y>412一，，3、y2,y3>0,约无付号限制一般可以证明，若原问题中的某个变量无非负限制，则对偶问题中的相应约束为等式3对偶单纯形法对偶问题求解具有重要的意义，有多种方法解决对偶问题.下面介绍用对偶单纯形法来解决线性规划的对偶问题.先介绍以下几个线性规划的基本概念凶：基：已知A是约束条件的mxn系数矩阵，其秩为m.若B是A中m乂m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基.基向量：基B中的一列即称为一个基向量.基B中共有m个基向量.非基向量：在A中除了基B之外的一列则称之为基B的非基向量.基变量：与基向量相应的变量叫基变量，基变量有m个.非基变量：与非基向量相应的变量叫非基变量，非基变量有n-m个.由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解.首先重新回顾一下单纯形法的基本思想，其迭代的基本思路是：先找出一个基可行解，判断其是否为最优解，如果不是，则转换到另一更优的基可行解，并使目标函数值不断优化，直到找到最优解为止.【我们可以用另一种思路，使在单纯形法每次迭代的基本解都满足最优检验，但不一定满足非负约束，迭代时使不满足非负约束的变量个数逐步减少.当全部基变量都满足非负约束条件时，就得到了最优解，这种算法就是对偶单纯形法.因此，单纯形法是从一个可行解通过迭代转到另一个可行解，直到检验数满足最优条件为止.对偶单纯形法是从满足对偶可行性条件出发通过迭代逐步搜索出最优解.在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失.现把对偶单纯形法的基本步骤总结如下⑶:第一，把所给的线性规划问题转化为标准型；第二，找出一个初始正则基B0，要求对应的单纯形表中的全部检验数aj<0，但“右边”列中允许有负数；第三，若“右边”列中各数均非负，则B已是最优基，于是，已求得最优解，计算终0止.否则转为第四步；第四，换基：“右边”列中取值最小（即负的最多）的数所对应的变量为出基变量计算最小比值。.最小比值出现在末列，则该列所对应的变量即为进基变量，换基后得新基Bi，以出基变量的行和进基变量列交点处的元素为主元进行单纯形迭代，再转入第三步.下面用一个例子具体说明用对偶单纯形法求线性规划问题最优解的步骤：例1求解线性规划问题minW=15y+5y+11y；123'3y+2y+2y>5123(5y+y+2y>4123y,y,y>0123~添加松弛变量以后的标准型minW=15y1+5y2+11y33y+2y+2y-y=512345y+y+2y-y=41235y,y,y,y,y>012345将每个等式两边乘以-i，则上述问题转化为minW=15y+5y+11y；TOC\o"1-5"\h\z123-3y-2y-2y+y=-51234-5y-y-2y+y=-41235y,y,y,y,y>012345如果取Y0=（y4,yJ作为初试基变量，有如下初试单纯形表（表）表3-1y1y2y3y4y5右边0y4-3-2-2¥0-50y5-5-1-201III-4W-15-5-1100由此可见，两个基变量y4,y/匀取负值，所以，B0所确定的基本解不是基可行解，从而也就不能用单纯形法求解.下面我们用一种新的方法对偶单纯形法求解此题，并通过例题来说明方法步骤.*对偶单纯形法的基本思想：是保证检验数行全部非正的条件下，逐步使得“右边'一列各数变成非负.一旦“右边”一列各数均满足了非负条件（即可行性条件）则就获得最优解现在，B不是可行基（称为正则基），为保证上述方法的实现，可按下面的方法确定出0基变量和进基变量.出基变量的确定可以取任意一个具有负值的基变量（一般可取最小的）为出基变量.在上故七为出基变量.例中，两个基变量（七,七）都取负值，且七=-5故七为出基变量.现在考虑出基变量所对应的负所有元素a<0，对每个这样的元素作比值二，令aJ()0=minJT\a'<0IJ则％为进基变量.在表2-4中，基变量七所在的行有三个。，取负值，其值分别为32-2.它们对应的检验数分别为-15,-5,-11.现在考虑出基变量所对应的负所有元素a<0，()IJ于是八.1-15-5-1115b0=minJ,——，\=—=^〔-3-2-2J2a12由此可知，七为进基变量.主元素为在表2-2的（1）基变量y‘所取之值a'=-2，对表2-1进行一次迭代便得表2-2,Jb'=--由此可知，七为进基变量.主元素为在表2-2的（1）基变量y‘所取之值a'=-2，对表2-1进行一次迭代便得表2-2,Jb'=--<22。，故七为出基变量.又15—2-622J15—=—27a'12故七是进基变量;，主元为弓7,、—.对（1）再作单纯形变换，得表3-1之（2）.由于它的“右边”已列出全部非负，故它就是最优表—,3.最优解为：七=-y'-132,,，八，110y=y=y=0；最优值w=3457表3-1y1y2y3y4y5右边（1）/35y21112—0y5223711—0-122w1550250-6222（2）45313y01——277772123&10——7777>1w27101500777110然而在有些问题中，我们很容易找到初始基本解，因此使用对偶单纯形法求解线性规划问题是有一定条件的，其条件是：⑴单纯形表的b列中至少有一个负数.(2)单纯形表中的基本解都满足最优性检验.对偶单纯形法与原始单纯形法相比有两个显著的优点：⑴初始解可以是不可行解，当检验数都非正时，即可进行基的变换，这时不需要引入人工变量，因此简化了计算.(2)对于变量个数多于约束方程个数的线性规划问题，采用对偶单纯形法计算量较少.因此对于变量较少、约束较多的线性规划问题，可以先将其转化为对偶问题，然后用对偶单纯形法求解.对变量多于约束条件的线性规划问题，用对偶单纯形法进行计算可以减少计算的工作量.因此对变量较少，而约束条件很多的线性规划问题，可先将此问题转化为对偶问题，然后用对偶单纯形法求解.用对偶单纯形法求解线性规划问题的标准型，要求初始单纯形表检验数行的检验数必须全部非正，若不能满足这一条件，则不能运用对偶单纯形法求解.对偶单纯形法的局限性主要是，对大多数线性规划问题来说，很难找到一个初始可行基，因此这种方法在求解线性规划问题时，很少单独应用.，参考文献：吴祈宗.运筹学学习指导及习题集[M].北京：机械工业出版社，2006.孙君曼，冯巧玲，孙慧君，等.线性规划中原问题与对偶问题转化方法探讨[J].郑州：工业学院学报(自然科学版)，2001，16(2):44~46.何坚勇.运筹学基础.北京：清华大学出版社，2000.⑷周汉良，范玉妹.数学规划及其应用.北京：冶金工业出版社.陈宝林.最优化理论与算法(第二版).北京：清华大学出版社，2005.张建中，许绍吉.线性规划.北京：科学出版社，1999.姚恩瑜，何勇，陈仕平.数学规划与组合优化.杭州：浙江大学出版社，2001.卢开澄.组合数学算法与分析.清华大学出版社，1982.Even.Shimon.AlgzithmicCombinatorial.TheMacmillanCompany，NewYork，1973.J.P.Tremblay，R.Manohar.DiscreteMathematicalStructureswithApplicationstoComputerScience，1980.李修睦.图论.华中工学院出版社，1982.PranavaRG.Essaysonoptimizationandincentivecontracts[C.MassachusettsInstituteofTechnology，SloanSchoolofManagement:OperationsResearchCenter;2007:57-65.Schechter，M.ASubgradientDualityTheorem，J.MathAnalAppl.，61(1977)，850-855.MaximsSA.Noteonmaximizingasubmodularsetfunctionsubjecttoknapsackconstraint^].OperationsResearchLetters,2004,32⑸：41-43.Schechter,M.MoreonSubgradientDuality,J,71（1979）,251-262.NemhauserGL,WolseyLA,FisherML.Ananalysisofapproximationsformaximi