第四章 线性规划的对偶问题

第四章线性规划的对偶问题4.1对称的对偶规划在线性规划早期发展中,对偶问题是一项重要的发现。早在1928著名数学家John.Von.Neumann在研究对策理论时就已经有原始和对偶的思想。对偶理论有着重要的应用。首先是在原始和对偶两个线性规划中求解任一规划时，会自动地给出另一个规划的最优解。当对偶问题比原问题有较少分量时，求解对偶问题比求解原始问题方便得多。对偶理论另一个应用是Lemke，1954提出的对偶单纯形法。对偶理论对影子价值的分析在经济理论上有着重要作用。一对偶问题的提出:例:某厂生产A.B.C三种畅销产品,每台产品需四种资源,具体数据表：资源产品甲乙丙丁每台收益A32112000B41324000C22343000资源总量600400300200问怎样安排生产,效益最大？设决策变量得出模型:3,2,1.0200423003340022600243..300040002000max321321321321321ixxxxxxxxxxxxxtsxxxzi321,,xxx现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生产这些产品时可以得到的最大效益.这就需建立另一个线性规划模型,设代表销售这四种资源的价格，买方希望总售价尽可能低,即：4321200300400600minyyyyw4321,,yyyy为了使工厂效益不减少,就要求订时,使这个效益额不低于原来生产一台产品A可以得到的效益,因此满足约束:4321,,,yyyy2000234321yyyy30004322400023443214321yyyyyyyy对B,C产品可列出类似约束.432123yyyy原来生产产品A每台需用的资源按现在的单价计算,每台收益为:易见,后一个问题的数据完全由另一问题数据确定.对每一个线性规划问题都伴随有另一个线性规划问题,即：max()..0CxLPstAxbx都伴随一个对偶规划(LD)。定义1:对应着每一个(LP),都存在着线性规划问题(LD)0..minucuAtsub其中是m维行向量,称(LP)为原始线性规划，称(LD)为(LP)的对偶线性规划。),...(1muuu因此得到的线性规划问题模型如下:)4~1(0300043224000234200023..432143214321iyyyyyyyyyyyyytsi4321200300400600minyyyyw下面进一步探讨(LP)与(LD)之间的关系：其对偶问题:(LD)))(~1(0,...,,...,,...,,...,),...,(...min21212222111211212211号约束条件最小化特点，：miucccaaaaaaaaauuubububuwinmnmmnnmmm11221112111212222212max...,,,,..,,0(1~)(:,nnnnmmmnnnjzcxcxcxaaabxaaabxstaaabxxjn特点最大化约束条件号）(LP)用下表表示二者之间关系,更为清楚:原始约束,...,nccc,...,21max对偶问题jxiynxxx,...,2112myyyminwmbbb21mnmmnnaaaaaaaaa,...,,...,,...,212222111211z对偶线性规划问题一定要有一对线性规划问题，没有一个“对偶”的线性规划问题，也就无所谓“原始线性规划问题”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了。线性规划的对偶关系具有“对合”性质,什么是对合性质呢?0)(..max:)(:)(00maxmaxminTTTTTTTTTTTTcAtsbLPLDcAcAcAbbb可写成因而问题因可见，（LP）’与（LP）是同一类型的问题，依照定义1，又可写出（LP）’的对偶线性规划。记为（LD）’（LD）'min()s.t.()0TTTTTTxcxAbx（LD）’又可等价地写成：既（LD）’就是前面的（LP）这表明，对于一个给定的（LP）可以根据对偶规则写出（LD）；而对于新问题（LD），又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（LP）的对偶是（LD），（LD）的对偶是（LP）。0..maxxbAxtscx这就是线性规划对偶关系的“对合”性质。这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。下面我们举例说明怎样由一个规则写出其对偶问题。例：写出：min4321765xxxxs.t.0...3241728147367241432143214321xxxxxxxxxxxxxx的对偶规划。解：因目标函数最小化，故先把约束条件都写成“”形式：0xx32x-4x-17x28x147xx3x-6x7x-x-2xxs.t.x7x6x-5xMin)(414321432143214311LP由于这是个（LD）问题。故其对偶是（LP）问题。对偶函数目标系数由给出的（LD）约束右端列向量（-7，14，3)可得，对偶的约束方程右端常数，向量由（LD）的目标函数系数向量（5，-6，7，1）可得，从而写出（LP）问题：0,,127746173252863147321321321321321321uuuuuuuuuuuuuuuuuumax(LP)(s.t.)个约束不等式。，因此对偶问题中有四因原问题中有四个变量分别与之对应。量不等式，故引入三个变”）中三个“”号，因（不等式，用“目标函数极大化，约束4321321,,,,,xxxxuuuLD所以把它们称为一对对称的对偶规划。下面来讨论它们的关系。二（LP）、（LD）的对偶定理定理1对于（LP）的任意可行解x及（LD）的任意可行解u有cx≤ub。证：因x、u满足：Ax≤b,x≥0（1）uA≥cu≥0（2）用u左乘（1），x右乘（2）的：cx≤uAx≤ub故cx≤ub。由于（LP）与（LD）形式上是等价的0maxxbAxcx0minucuAub定理1给出了（LP）（LD）这对互为对偶的线性规问题目标函数的一个界限。若（LP）有可行解x，则（LD）的目标值ub就有了下界cx；反之，若（LD）有可行解u，则（LP）的目标值cx就有了上界ub。推论：若（LP）有无界解，则（LD）无可行解。若（LD）有无界解，则（LP）无可行解。证：只证前面，后面一样，反证法。若（LP）有无界解，而（LD）有可行解u0，而根据定理一，对（LP）的任何可行解x，cx≤u0b这与（LP）目标函数无上界矛盾。注：这个推论的逆不一定成立。即一对对偶问题中有一个无可行解，不能判定另一个有无界解。例：（LP）0,,12..max3213321321xxxxxxxtsxxx0,111..2min21211121uuuuuutsuu（LD）上面（LP）无可行解，而（LD）并没有无界解，而是无可行解。定理2：二者同时有可行解。）有最优解）（对偶规划（LDLPLPLDLPLDxu显然，有最优解的（）（），必有可行解。若（）（）分别有可行解、，对()LPxcxub的任一可行解，由定理1，）亦有最优解。同理：（）必有最优解。（然有最优解，从而可能为无界的情形，必可行解的线性规划又不不可能无界。而一个有行域上有上界，）极大化目标函数在可表明（LDLPLP证明：证明：）的最优解。）（分别是（、，则）的可行解，且）（分别是（、如果LDLPuxbucxLDLPux推论2）的最优解。）（分别是（、优值。因而）的目标函数的最）（分别是（、表明，，知：定理，由）的任意可行解，（）的任意可行解对（LDLPuxLDLPbucxbucxubcxbucxuLDxLP1定理30,,0max0max01yxbyxIAYcxyxbIyAxcxLPyyyLPLDLPTTm，即）标准化得：（，将变量）有最优解，引进松弛若（等。者的目标函数最优值相个也有最优解，并且俩则另一）中有一个有最优解，）（若对偶规划（证明：这样（LP）就化成了等价的（*）问题。由于假定（LP）有最优解，则（*）亦有最优解。）的可行解。是（先证明）的最优解。是（的单纯形乘子下面证明基LDBcuLDBcBBB11mT1000亦即0maxvbvAvc（*）其中mnTcc10,IAA,yxvmspyyxxvspiijj，，。设其基变量为：一个基本最优解的法）得到括处理退化的情形的方从而可用单纯形法（包111ppBj{,...0对应的最优基为jB-1c，组成的m维向量记为，，在其中取出基变量对,…cc,…,cc,...00001应的分量。满足个jjsbBbucx**的内积为：与，则，维向量。即的中基变量取值所组成是又因为，所以才可能不等于中只有基变量而bBcccyyxxbBmvbBxcxccxxxxTjjBTiijjjjjjjjpspppp111000111111yxvLDBcuB）的最优解。设是（再证明1）的可行解。是（故、即、亦即，，或有判别数应非负。记则所的一个最优基可行解。是用单纯的形法得到的故LDBcuucAuBccABccIABccABcvBBBTBB111110000*02xAxbxxLPuLD则满足：、，即是（）的可行解。要证是（）的最优解，由推论可知，只须证明：***1*11cxxcxcbBcbuppjjjjB）（令写成再将令写成将，又设njcpunjcpucAumixAbmibxAbAxuuuxxxjjjjjiiiiimTn~1~1~1~1***11jijijiipjAniaaaAiAuxLDLP列向量为的第行向量为的第设的互补松弛性质。、）的最优解）（下面证明（~1,1的另一部分证明类似。优目标值相等。定理）的最优解，且俩者最是（即知）的可行解。由推论）（分别为（、因已证LDBcuLDLPuxB12,0jjjcpu有jjcpu2,,,10,:,,,2,1001,jknkxcxpuxxcpujknkxcxpuxkkkkkkkkkjjjjjj得：俩边同乘于是有外，其余而除得：俩端同乘定理4jjjjjiiiiicpunjxxAbmiu*,~10,~10则一定有：、有最优解）分别）（对对偶规划（（互补松弛性质）若一uxLDLP，由于：，法，若不然。设不同时大于零。用反证、明成立，只须证，因此，要、因为明类似。只证后一式，前一式证00000jjjjjjjjxxxx证明：2