对偶单纯刑法

变换形式归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项无约束、，4321432143243214321321321321321321,002473254304324323min20,,5643732532422min.1xxxxxxxxxxxxxxxxxxxZ.xxxxxxxxxxxxxxxZ练习：无约束答案：32132132132131321321321321321321y0,y0,y44y4y4y37y3y3y23yy2y32yy253max.20.yy0,y46y7y5y24yy3y2y3y2y532max.1yyyWyyyWminZ’=-CXs.t.-AX≤-bX≥01、对称性定理：对偶问题的对偶是原问题。minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0对偶的定义对偶的定义maxW’=-Ybs.t.YA≥CY≤0（二）对偶问题的性质2、弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有__X__YnjmiiijjbyxcbYXC11____,即推论⑴.若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。__XCbY____X__Y推论⑵在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：问题无界无可行解无可行解问题无界对偶问题原问题0,0242max21212121xxxxxxxxZ无界如：（原）0,01224min21212121yyyyyyyyW无可行解（对）推论⑶在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。例一、02023220322432max41432143214321xxxxxxxxxxxxxZ试估计它们目标函数的界，并验证弱对偶性原理。（P）解：0,042333222122020min212121212121yyyyyyyyyyyyW（D）由观察可知：=（1,1,1,1），=（1,1），分别是（P）和（D）的可行解。Z=10，W=40，故有，弱对偶定理成立。由推论⑴可知，W的最小值不能小于10，Z的最大值不能超过40。__XCbY__＜__X__Y例二已知0,,1222max32132132121xxxxxxxxxxxZ:p0,02122min:2121212121yyyyyyyyyyWD试用对偶理论证明原问题无界。解：=（0,0,0）是P的一个可行解，而D的第一个约束条件不能成立（因为y1,y2≥0)。因此，对偶问题不可行，由推论⑶可知，原问题无界。__X例3、已知0,11max:21212121xxxxxxxxZP0,11min:21212121yyyyyyyyWD显然，这两个问题都无可行解。3、最优性判别定理：若X*和Y*分别是P和D的可行解且CX*=Y*b，则X*.Y*分别是问题P和D的最优解。例如，在例1中，可找到X*=（0,0,4,4），Y*=（1.2，0.2）,则Z=28，W=28.故X*.Y*分别是P和D的最优解。4、对偶定理（强对偶性）：若一对对偶问题P和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。推论⑷若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①都有最优解，分别设为X*和Y*，则必有CX*=Y*b；②一个问题无界，则另一个问题无可行解；③两个都无可行解。5、互补松弛定理：设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是剩余变量或或ssssYXXYXCAYXYAXbY.00)(00)(同时成立一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。例4、已知03223595243min5154321543254321xxxxxxxxxxxxxxxZ试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为0,)5(923)4(55)3(2)2(4)1(332max2121212121221yyyyyyyyyyyyyW用图解法求出：Y*=（1,3），W=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=（x1,x2,x3,x4,x5），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）又由于y*1＞0，y*2＞0，原问题的约束必为等式，即322352152xxxxx5251321xxxx化简为此方程组为无穷多解令x5=0,得到x1=1，x2=2即X*1=（1,2,0,0,0）为原问题的一个最优解，Z=11。再令x5=2/3，得到x1=5/3，x2=0即X*2（5/3,0,0,0,2/3）也是原问题的一个最优解，Z=11。例5、已知原问题的最优解为X*=（0,0,4），Z=12试求对偶问题的最优解。无约束321321321321321,0,04163253234maxxxxxxxxxxxxxxxxZ解：无约束321321321321321,0,03654313242minyyyyyyyyyyyyyyyW（1）（2）（3）将X*=（0,0,4）代入原问题中，有下式：4412463220532321321321xxxxxxxxx所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为Y*=（0,0,3），W=12。6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。⑴设原问题为：maxZ=CXAX≤bX≥0引入xs，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0，则求得最优解。此时，xs对应的σjs为-Y*，故求对偶Y*，只要将最优单纯形表上xs对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1例一0,150510032170251810max2121212121xxxxxxxxPxxZ0,,185321025150100170min321321321321yyyyyyyyyDyyyW0150510032170250001810max5152142132154321xxxxxxxxxxxxxxxZcj1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5-Z01018000icj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最终表由上表可知：X*=（50/7,200/7），Z=4100/7对偶问题的最优解：Y*=（0,32/7,6/7），W=4100/7也就是外加工时的收费标准。⑵设原问题：maxZ=CXAX=bX≥0此时，矩阵A中没有现成的矩阵I，必须通过加入人工变量来凑一个单位矩阵，再用大M法或两阶段法求解。如何求Y*，经分析得出如下结论：σB=0最优基变量检验数向量σI=CI－CBB-1初始基变量检验数向量σD=CD－CBB-1D非基变量检验数向量所以，Y*=CI－σI例二0123241123max3131321321321xxxxxxxxxxxxP无约束32132121321321,0,01212324311minyyyyyyyyyyyDyyyWcj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011-Z3-6M-1+M-1+3M0-M00i所以，X*=（4,1,9），Z=2∴y*1=(0－σ4)=1/3y*2=(－M－σ6)=－M－(1/3－M)=－1/3y*3=(－M－σ7)=－M－(2/3－M)=－2/3Y*=（1/3,－1/3,－2/3）W=2初始基变量的检验数σ4=－1/3，σ6=1/3－M,σ7=2/3－M定义：在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。0D0minmaxYCYAXbAXPYbWCXZ三、对偶问题的经济解释——影子价格设：B是问题P的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*Ibi+…+y*mbm当bi变为bi+1时（其余右端项不变，也不影响B），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1目标函数最优值变为：Z′*=y*1b1+y*2b2+…+y*I（bi+1）+…+y*mbm∴△Z*=Z′*－Z*=y*i)2,1(**miybZii也可以写成：即y*i表示Z*对bi的变化率。其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第i个约束条件的影子价格。也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。若第i种资源的单位市场价格为mi，当yimi时，企业愿意购进这种资源，单位纯利为yi－mi，则有利可图；如果yimi，则企业有偿转让这种资源，可获单位纯利mi－yi，否则，企业无利可图，甚至亏损。0,150510032170251810max2121212121xxxxxxxxPxxZ01020304050601020304050x2x1123(50/7,200/7)74132)719918()75510(Z多了32/7x101020304050601020304050x2123(55/7,199/7)74100)720018()75010(Z01020304050601020304050