运筹学基础-对偶线性规划(2).ppt

线性规划的对偶理论包括以下几个基本定理。定理1（对称性定理）2.2线性规划的对偶理论定理2（弱对偶定理）即对偶问题的对偶是原问题。设x和y分别是原问题和对偶问题的可行解，则必有cxyb，即原问题的目标值小于对偶问题的目标值定理3（无界性）若原问题(对偶问题)为无界解无界解无界解无界解，则其对偶问题(原问题)无可行解无可行解。若原（对偶）问题有可行解有可行解,对偶（原）问题无可行解无可行解，则原（对偶）问题一定无界无界；注:此定理可以判定解的情况定理4（可行解是最优解的性质）定理5（强对偶定理）设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时，X*与Y*是最优解。若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等综合上述结论得原问题与对偶问题的解的关系一般是：一般是：cxyb 对 偶 问 题 有最优解 无界 无可行解原 有最优解 一定 不可能 不可能问 无 界 不可能 不可能 一定题 无可行解 不可能 可能 可能原问题与对偶问题解的对应关系原问题与对偶问题解的对应关系由原问题与对偶问题的解的关系可以判定线性规划的解。例4已知线性规划问题Maxz=x1+x2S.t.x1+x2+x322x1+x2x31xi0(i=1,2,3)Minw=2y1+y2S.t.y12y21y1+y21y1y20y1,y20应用如上关系求解线性规划问题应用如上关系求解线性规划问题试用对偶理论证明上述规划问题无最优解。由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解，由于原问题存在可行解，所以解无界。表2：原问题与对偶问题解的对应关系 对 偶 问 题 有最优解 无界 无可行解原 有最优解 一定 不可能 不可能问 无 界 不可能 不可能 一定题 无可行解 不可能 可能 可能解该问题存在可行解，如X=(0，0，0)；其对偶问题为：对偶问题无可行解定理6（互补松弛定理）在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零对偶变量值为非零对偶变量值为非零对偶变量值为非零，则该约束条件取严格等式严格等式严格等式严格等式；反之如果约约约约束条件取严格不等式束条件取严格不等式束条件取严格不等式束条件取严格不等式，则其对应的对偶变量一定为零对偶变量一定为零对偶变量一定为零对偶变量一定为零。注：证明过程参见教材注：证明过程参见教材5959页性质页性质5 5证明证明讨论:互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。线性规划达到线性规划达到最优最优时的关系时的关系例5已知线性规划问题MinS=2x1+3x2+5x3+2x4+3x5S.t.x1+x2+2x3+x4+3x542x1x2+3x3+x4+x53xi0(i=1,2,3,4,5)221/5317/557/523=3解：写出对偶问题为：MaxZ=4y1+3yS.t.y1+2y22y1y232y1+3y25y1+y223y1+y23y1,y20又例又例:应用如上关系求解线性规划问题应用如上关系求解线性规划问题已知对偶问题的最优解为y1=4/5,y2=3/5,试应用对偶理论求解原问题。x2=0 x3=0 x4=0等号又因y1,y20，故原问题的两个约束必为紧约束，即x1+3x5=42x1+x5=3解得：x1=x5=1。maxZ=5=minS=5得原问题的最优解X*=(1,0,0,0,1)minS=5Max.Z=2x1+4x2+x3+x4s.t.x1+3x2+x482x1+x26x2+x3+x46x1+x2+x39xj0（j=1,2,3,4）附练习答案：y1=4/5,y2=3/5,y3=1,y4=0已知原问题的最优解为:X*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4s.t.y1+2y2+y423y1+y2+y3+y44y3+y41y1+y31yj0（j=1,2,3,4）练习：已知线性规划问题为：为严格不等式，由互补松弛定知，必有y4=0；Max.Z=2x1+4x2+x3+x4s.t.x1+3x2+x482x1+x26x2+x3+x46x1+x2+x39xj0（j=1,2,3,4）8=86=66=689解之，有：y1=4/5,y2=3/5,y3=1，y4=0答案：因为原问题的最优解为:X*=(2,2,4,0)T：又因x1,x2,x30，故对偶问题的前三个约束必为紧约束线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4s.t.y1+2y2+y423y1+y2+y3+y44y3+y41y1+y31yj0（j=1,2,3,4）y1+2y2=23y1+y2+y3=4y3=1等号（1）写出对偶问题；（2）已知原问题的最优解为X*=（2，0，1，1）T，求对偶问题的最优解。已知线性规划问题定理7结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解基本可行解的同时，其：线性规划原问题及其对偶问题之间存在一对互补的基解，其中原原原原问问问问题题题题的的的的松松松松驰驰驰驰变变变变量量量量对应对对对对偶偶偶偶问问问问题题题题的的的的变变变变量量量量，对对对对偶偶偶偶问问问问题题题题的的的的剩剩剩剩余余余余变变变变量量量量对应原原原原问问问问题题题题的的的的变变变变量量量量；这些互相对应的变量如果在一个问题的解中是基基变变量量，则在另一问题的解中是是是是非非非非基基基基变变变变量量量量；将这两个解代入各自的目标数中有z=w。注：证明过程参见教材注：证明过程参见教材6060页性质页性质6 6证明证明检验数行的-(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；用单纯形法同时求解用单纯形法同时求解原问题原问题和和对偶问题对偶问题原问题是：maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0原问题的标准型是：maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =15 6x1+2x2 +x4 =24 x1+x2 +x5=5 xi 0 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52100015051002462010511001x3x4x5000021000 maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =15 6x1+2x2 +x4 =24 x1+x2 +x5=5 xi 0-24/6=45/1=5原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3得原问题可行解得原问题可行解得原问题可行解得原问题可行解:X X=(0,0,15,24,5)=(0,0,15,24,5)T T对偶问题解对偶问题解对偶问题解对偶问题解:Y*Y*=(0,0,0,-2,-=(0,0,0,-2,-1)1)T T检验数行的(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；检验数检验数 j1505100411/301/60102/30-1/61x3x1x5020-801/30-1/303121.5得原问题可行解得原问题可行解得原问题可行解得原问题可行解:X X=(4,0,15,0,1)=(4,0,15,0,1)T T，此时，此时，此时，此时Z=8Z=8同时得对偶问题基础解同时得对偶问题基础解同时得对偶问题基础解同时得对偶问题基础解:Y*Y*=(0,1/3,0,0,-1/3)=(0,1/3,0,0,-1/3)T T，W=8W=8对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3原问题变量原问题松驰变量检验数行的-(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；变换单纯形表变换单纯形表Cj比比值值CBXBb检验数检验数 j=cj-zjx1x2x3x4x52100015/20 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2此时得原问题最优解此时得原问题最优解此时得原问题最优解此时得原问题最优解:X X*=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)T T，Z Z*=17/2=17/2原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3则对偶问题最优解则对偶问题最优解则对偶问题最优解则对偶问题最优解:Y Y*=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T，S S*=17/2=17/2检验数行的-(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；又例：又例：用单纯形法同时求解用单纯形法同时求解原问题原问题和和对偶问题对偶问题maxZ=100 x1+80 x2 2 x1+4 x2 80 3 x1+x2 60 x1,x2 0将线性规划问题标准化将线性规划问题标准化将线性规划问题标准化将线性规划问题标准化maxZ=100 x1+80 x2+0 x3+0 x4 2 x1+4 x2+x3 =80 3 x1+x2 +x4=60 x1,x2 x3 x4 0 00080100-Z60101308001420此时得原问题的最优解：X0=(16,12,0,0)T,maxZ=2560初等变换初等变换-2000-100/30140/30-Z201/301/31 1040-2/3110/300 2 x1+4 x2 +x3 =80 3 x1+x2 +x4=60-Z+100 x1+80 x2+0 x3+0 x4=0-2560-24-1400-Z162/5-1/1001012-1/53/101 100-Z x1 x2 x3 x4 b同时得对偶问题的最优解：y1=14,y2=24,y3=0,y4=0,即Y0=(14,24,0,0)T,minS=25602.3 对偶单纯形方法对偶单纯形方法原问题是：原问题的标准型是：minZ=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1,y2,y3 0maxw=-15y1-24y2-5y3+0y4+0y5 6y2+y3-y4 =25y1+2y2+y3 -y5=1 y1,y2,y3,y4,y5 0利用单纯形法：maxw=-15y1-24y2-5y3+0y4+0y5-My6-My7 6y2+y3-y4 +y6 =25y1+2y2+y3 -y5 +y7=1 y1,y2,y3,y4,y5,y6,y7 0一、一、一、一、用对偶单纯形方法解线性规划用对偶单纯形方法解线性规划用对偶单纯形方法解线性规划用对偶单纯形方法解线性规划对偶单纯形方法对偶单纯形方法对偶单纯形方法对偶单纯形方法是使用对偶原理求解原问题解的一种方法，而不是求解对偶问题解的单纯形方法。与对偶单纯形方法相对应，原已有的单纯形方法称原始单纯形方法原始单纯形方法原始单纯形方法原始单纯形方法。用对偶单纯形方法解下述线性规划问题用对偶单纯形方法解下述线性规划问题原问题是：原问题的标准型是：minZ=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1,y2,y3 0maxw=-15y1-24y2-5y3+0y4+0y5 6y2+y3-y4 =25y1+2y2+y3 -y5=1 y1,y2,y3,y4,y5 0maxw=-15y1-24y2-5y3+0y4+0y5 -6y2-y3+y4 =-2 -5y1-2y2-y3 +y5=-1 y1,y2,y3,y4,y5 0对偶单纯形方法对偶单纯形方法对偶单纯形方法对偶单纯形方法 Cj比比值值CBXBb检验数检验数 jy1y2y3y4y5-15-24-500-20-6-110-1-5-2-101y4Y5000-15-24-500检验数检验数 j1/3011/6-1/60-1/3-50-2/3-1/31Y2y5-2408-150-1-40maxw=-15y1-24y2-5y3+0y4+0y5 -6y2-y3+y4 =-2 -5y1-2y2-y3 +y5=-1 y1,y2,y3,y4,y5 0检验数检验数 j1/4-5/410-1/41/41/215/2011/2-3/2Y2y3-24-517/2-15/200-7/2-3/2最优解最优解最优解最优解:Y Y*=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T，maxmaxw*=-17/2=-17/24531.512MinZ=17/2=17/2应用对偶单纯形方法之矩阵法maxw=-15y1-24y2-5y3+0y4+0y5 -6y2-y3+y4 =-2 -5y1-2y2-y3 +y5=-1 y1,y2,y3,y4,y5 000-5-24-15-W-11-1-2-50-20-1-60000180-10-15-W-1/31-2/30-501/301/6100-4-1/3-1/617/2-3/200-15/2-W1/2-3/21015/201/4001-5/40-7/21/2-1/4最优解最优解最优解最优解:Y Y*=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T，max max w*=-17/2*=-17/2Min Z=17/2=17/2两种方法的主要区别区别区别区别在于：而对偶单纯形方法在整个迭代过程中，则是始终保持对偶对偶问题的可行性问题的可行性即亦即,，也就是全部检验数0，最后达到全部右边项所有负分量逐步变为全部右边项0,即满足原问题的可行性时为止。所以,对偶单纯形方法实质对偶单纯形方法实质对偶单纯形方法实质对偶单纯形方法实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。原始单纯形方法在整个迭代过程中，始终是保持原问题的原问题的可行性可行性，最后达到检验数即即maxZ取得最优值时为止。-2560-24-1400-Z162/5-1/1001012-1/53/101 100相当于：直到对偶问题的解可行为止相当于：直到对偶问题的解可行为止相当于：即直到原问题的解可行为止相当于：即直到原问题的解可行为止用对偶单纯形方法解下述线性规划问题原问题是：原问题的标准型是：minZ=2x1+3x2+4x3 x1+2x2+x3 3 2x1-x2+3x3 4 x1,x2,x3 0maxZ=-2x1-3x2-4x3+0 x4+0 x5 x1+2x2+x3 -x4 =32x1-x2+3x3 -x5=4 x1,x2,x3,x4,x5 0maxw=-2x1-3x2-4x3+0 x4+0 x5 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0应用对偶单纯形方法之矩阵法00-4-3-2-W-41-31-20-30-1-2-100014-1-1-40-W2-1/23/2-1/210-1-1/21/2-5/20000128/5-1/5-3/500-W11/5-2/57/50102/51/5-1/5100-8/5-1/5-2/5最优解最优解最优解最优解:Y Y*=(11/5,2/5,0,0,0)=(11/5,2/5,0,0,0)T T，MaxwMaxw=-28/5=-28/5maxw=-2x1-3x2-4x3+0 x4+0 x5 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0MinZMinZ*=28/5*=28/5小结：对偶单纯形方法的解题过程一般分为四步（1）写写出出与与已已有有的的初初始始基基B对对应应的的初初始始单单纯纯形形表表。根据模型的标准型，若若若若右右右右边边边边项项项项的的的的数数数数字字字字都都都都为为为为非非非非负负负负，且且且且检检检检验验验验数数数数都都都都为为为为非非非非正正正正，则已得到最优解，计算结束；否则，若右边项中至少有一个负分量，且检验数也仍然非正，则进行如下计算。（2）确定出基变量）确定出基变量。若有：则以对应的变量xr为出基变量。（3）确确定定入入基基变变量量。在单纯形表中观察xr所在行的各系数arj，若所有的arj0，则无可行解，停止计算；否则若存在：，则以xk为入基变量。（4）以以ark为主元按原始单纯形方法的迭代方法进行迭代为主元按原始单纯形方法的迭代方法进行迭代，得到新的单纯形表。对偶单纯形方法的显著优点：对偶单纯形方法的显著优点：（1）初始解可以是不可行解，当检验数都非正时，即可以进行基的变换，这时不需要引进人工变量，因此就简化了计算。（2）对于变量个数多于约束方程个数的线性规划问题，采用对偶单纯形法计算量较少。因此对于变变变变量量量量较较较较少少少少、约约约约束束束束较较较较多多多多的线性规划问题,可以先将它转化成对偶问题，然后用对偶单纯形方法求解。2.4 影子价格影子价格 从对偶问题的基本性质可以看出，在单纯形法的每步迭代中有目标函数 其中bi原来代表第i种资源的拥有量；现在代表第i种资源的估价。此时的估价不是市场价格，而是根据资源在生产中的贡献而作的估价。此时的定价区别于市场价格称为影子价此时的定价区别于市场价格称为影子价格。格。n 说明说明 1、市场价格主要随市场供求变化；而它的影子价格有赖于资源的利用情况。生产任务、结构的改变会影响影子价格。生产任务、结构的改变会影响影子价格。2、影子价格是一种边际价格。y yi i代表代表b bi i每增加一个单位，每增加一个单位，目标函数目标函数z z的增量的增量maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0 x1=82x2=123x1+4 x2=36+1 （1 1）z*=42 z*=42 不变，不变，A A的边际价格为的边际价格为0 0+1 （2 2）x*=(10/3,13/2)z*=42.5x*=(10/3,13/2)z*=42.5，B B的边际价格为的边际价格为0.50.5+1 （3 3）x*=(13/3,6)z*=43x*=(13/3,6)z*=43，C C的边际价格为的边际价格为1 1n 说明说明3、资源的影子价格实际上是一种机会成本。市场价格低于影子价格时，可以买进这种资源。市场价格低于影子价格时，可以买进这种资源。市场价格高于影子价格时，可以卖出这种资源。市场价格高于影子价格时，可以卖出这种资源。随着资源的买进和卖出，它的影子价格也随之发生变化。4、生产过程中，如果某种资源bi未得到充分利用时，该种资源的影子价格为0；某种资源的影子价格不为0时，表明该种资源已经耗尽。