《北邮运筹学ch22对偶性质》由会员分享，可在线阅读，更多相关《北邮运筹学ch22对偶性质（22页珍藏版）》请在金锄头文库上搜索。
1、Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 1 of 23设原问题是（记为LP）： 对偶问题是（记为DP）：这里A是mn矩阵X是n1列向量，Y是1m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。【性质性质1】 对称性 对偶问题的对偶是原问题。 【证证】设原问题是8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 2 of 23它与下列线性规划问题是等价的：再写出它的对偶问题。它与下列线性规划问题是等价的即是原问题。 由表21知，它的对偶问题是8/5/2024Ch2 Dual
2、Problem2.2对偶性质对偶性质 Dual Property Page 3 of 23【性质【性质2】 弱对偶性弱对偶性 设设X、Y分别为（分别为（LP）与（）与（DP）的可行）的可行解，则解，则 【证】因为【证】因为X、Y是可行解，故有是可行解，故有AXb, X0及及YAC，Y0, 将不等式将不等式 AXb 两边左乘两边左乘Y得得YAXYb再将不等式再将不等式YAC两边右乘两边右乘X，故故 C XYAXYb这这一一性性质质说说明明了了两两个个线线性性规规划划互互为为对对偶偶时时，求求最最大大值值的的线线性性规规划划的的任任意意目目标标值值都都不不会会大大于于求求最最小小值值的的线线性性规
3、规划划的的任任一一目目标标值值，不能理解为原问题的目标值不超过对偶问题的目标值。不能理解为原问题的目标值不超过对偶问题的目标值。得得C XYAX8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 4 of 23由这个性质可得到下面几个结论： （1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解； (3）若原问题可行且另一个问题不可行，则原问题具有无界解。 注意上述结论（2）及（3）的条件不能少。一个问题
4、有可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 5 of 23例如：无可行解，而对偶问题有可行解，由结论（3）知必有无界解。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 6 of 23【性性质质3】最最优优准准则则定定理理 设设X与与Y分分别别是是（LP）与与（DP）的的可可行行解解，则则当当X、Y是是（LP）与与（DP）的的最最优优解解当当且且仅仅当当C X= Yb.【证证】若若X、Y为为最最优优解解
5、，B为为（LP）的的最最优优基基，则则有有Y=CBB1，并且，并且当当C X= Yb时，由性质时，由性质1，对任意可行解，对任意可行解 有有即即Yb是是（DP）中中任任一一可可行行解解的的目目标标值值的的下下界界，C X是是（LP）中任一可行解的目标值的上界，从而中任一可行解的目标值的上界，从而X、Y是最优解。是最优解。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 7 of 23【性性质质4】 还还可可推推出出另另一一结结论论：若若（LP）与与（DP）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无
6、最最优优解解，则则另另一一问问题题也也无最优解。无最优解。【证】设（【证】设（LP）有最优解）有最优解X，那么对于最优基，那么对于最优基B必有必有C CBB-1A0与与CBB-10，即有，即有YAC与与Y0，这里这里Y= CBB-1 ，从而，从而Y是可行解，对目标函数有是可行解，对目标函数有由性质由性质3知知Y是最优解。是最优解。由由性性质质 4 还还可可推推出出另另一一结结论论：若若（LP）与与（DP）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无最最优优解解，则则另另一一问问题题也也无无最最优解。优解。8/5/2024Ch2 Dual Problem2.2
7、对偶性质对偶性质 Dual Property Page 8 of 23【性性质质5】互互补补松松弛弛定定理理 设设X、Y分分别别为为（LP）与与（DP）的的可可行行解解，XS和和YS是是它它的的松松弛弛变变量量的的可可行行解解，则则X和和Y是最优解当且仅当是最优解当且仅当YSX=0和和YXS=0【证证】设设X和和Y是是最最优优解解，由由性性质质3 ，C X= Yb，由由于于XS和和YS是松弛变量，则有是松弛变量，则有A XXSbYAYS=C将第一式左乘将第一式左乘Y，第二式右乘，第二式右乘X得得YA XYXSYbYA XYS X=C X8/5/2024Ch2 Dual Problem2.2对偶
8、性质对偶性质 Dual Property Page 9 of 23显然有 YXS=YS X又因为Y、Xs、Ys、X0，所以有YXS=0和YS X=0成立。反之， 当YXS=0和YS X=0时，有YA XYbYA X=C X显然有Yb=C X,由性质3知Y与X是（LP）与（DP）的最优解。证毕。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 10 of 23性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y求X或已知X求Y。YXS=0和YS X=0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求
9、和式等于零，则必定每一分量为零，因而有下列关系：8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 11 of 23（1）当yi0时， ，反之当 时yi=0；注意：对于非对称形式，性质5的结论仍然有效。【例2.6】 已知线性规划的最优解是 ，求对偶问题的最优解。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 12 of 23的最优解是 ，求对偶问题的最优解。【解解】对偶问题是因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1,y2=1
10、,从而对偶问题的最优解为Y=（1，1），最优值w=26。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 13 of 23【例例2.7】 已知线性规划 的对偶问题的最优解为Y=（0, -2），求原问题的最优解。【解解】对偶问题是由y20得 =0，由 得x2=0，原问题的约束条件变为: 解此方程组得原问题最优解：X=(-5, 0, -1)T，minZ = -12。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 14 of 23【例例2.8】 证明下列线性规划无最优解：【证证】
11、容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题将三个约束的两端分别相加得 ，而第二个约束有y21，矛盾，故对偶问题无可行解， 因而原问题为无界解，即无最优解。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 15 of 23【性性质质6】 （LP）的检验数的相反数对应于（DP）的一组基本解. 其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。8/5/2024Ch
12、2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 16 of 23【例例2.9】 线性规划（1）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；（4）用公式Y=CBB-1求对偶问题的最优解。【解解】（1）加入松弛变量x4、x5后，单纯形迭代如表22所示。8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 17 of 23表22XBx1x2x3x4x5b(1)x4x52*1-1024100124j6-2100(2)x1x510-1/21/2*131/
13、2-1/20113j01-5-30(3)x1x21001460-11246j00-11-2-28/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 18 of 23最优解X=（4，6，0），最优值Z=6426=12； （2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、 y3、y4、y5），由性质6得到对偶问题的基本解 （y1、y2、 y3、y4、y5） =（4，5，1，2，3），即 表22（1）中=（6，2，1，0，0）， 则Y（1）=（0，0，-6，2，1）表22（2）中=（0，1，5，3，0）， 则Y（2）=
14、（3，0，0，1，5）表22（3）中=（0，0，11，2，2）， 则Y（3）=（2，2，0，0，11）8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 19 of 23（1）因为表22（3）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解；（1）表22（3）中的最优基 B-1 为表22（3）中x4，x 5两列的系数，即CB=（6，2），因而8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 20 of 23本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解
15、的对应关系；表23也许对您了解这些性质有帮助。表238/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 21 of 23试一试：判断下列结论是否正确，如果不正确，应该怎样改正？1任何线性规划都存在一个对应的对偶线性规划.2原问题第i个约束是“”约束，则对偶变量yi0.3互为对偶问题，或者同时都有最优解，或者同时都无最优解.4对偶问题有可行解，则原问题也有可行解.5原问题有多重解，对偶问题也有多重解.6对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7原问题无最优解，则对偶问题无可行解. 8若某种资源影子价格为零，则该资源一定有剩余.9对偶问题不可行，原问题可能无界解.10原问题与对偶问题都可行，则都有最优解.11原问题具有无界解，则对偶问题不可行.12对偶问题具有无界解，则原问题无最优解.13若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.14在资源优化的线性规划问题中，若某一资源有剩余，则该资源影子价格为零.8/5/2024Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 22 of 23作业：教材P75 T2.4、2.6 、2.5The End of Section 2.2对偶单纯形法Exit8/5/2024
