《原问题与对偶问题》PPT课件

《《原问题与对偶问题》PPT课件》由会员分享，可在线阅读，更多相关《《原问题与对偶问题》PPT课件（35页珍藏版）》请在装配图网上搜索。

1、2 原问题与对偶问题原问题与对偶问题 1对称形式的对偶对称形式的对偶 当原问题对偶问题只含有不等式约束当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。时，称为对称形式的对偶。0 min bAX 0X .CXz max YC s.t.YAYb wts原问题原问题对偶问题对偶问题情形一：情形一：0Y CA .min0X bAX .maxYtsYbwtsCXz原问题原问题对偶问题对偶问题)(YY情形二：情形二：证明证明0Y CA .min0X bAX .maxYtsbYwtsCXz对偶对偶化为标准对称型化为标准对称型 2、非对称形式的对偶非对称形式的对偶 若原问题的约束条件是等式，若原问题的

2、约束条件是等式，则则无约束min0maxYCYAYbwXbAXCXz原问题原问题对偶问题对偶问题推导推导:0 maxXbAXbAXCX z 0 max XbbXAACX z原问题原问题 根据对称形式的对偶模型根据对称形式的对偶模型,可直接可直接写出上述问题的对偶问题写出上述问题的对偶问题:-bb),Y(Yw21min0,0(2121Y YCAA),YY ,YYC A)Y(Yb )Y(Yw00min 212121无约束YCYAYb w min令令 ，得对偶问题为：，得对偶问题为：21YYY证毕。证毕。原问题原问题(对偶问题对偶问题)对偶问题对偶问题(原问题原问题)无无约约束束个个变变量量00n

3、个个约约束束条条件件m约约束束条条件件个个 n变量无约束个00m目标函数目标函数max目标函数目标函数min目标函数中变量的系数目标函数中变量的系数约束条件右端项约束条件右端项约束条件右端项约束条件右端项目标函数中变量的系数目标函数中变量的系数 例例:无约束,x x,xxxxxxxxxxs.txxxx z432143214321432101023428854235max对偶问题为对偶问题为无约束21,0428233452521212121yyyyyyyyyys.t.21108minyyw ),1(),1(0),1(),1(.max1111111nnjxnnjxmmibxammibxatsxcz

4、jjnjijijnjijijnjjj无无约约束束 miiiybw1min),1(01miyi ),1(1mmiyi 无无约约束束 mijiijnjcya11),1(mijiijnnjcya11),1(例例:3 对偶问题的基本性质对偶问题的基本性质弱对偶性；弱对偶性；强对偶性；强对偶性；最优性最优性;无界性无界性;互补松弛性互补松弛性掌握原问题和其对偶问题解之间的关系掌握原问题和其对偶问题解之间的关系对偶问题的对偶是原问题对偶问题的对偶是原问题。0,5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415

5、minyyyw对对偶偶问问题题原原问问题题租借租借方方厂厂家家n引例引例（）32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：（）32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原问题原问题的变

6、量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：2154332543212/32/7002/152/32/1102/152/14/14/1014/54/1xxxxxyyyyyyy)(jjzc 原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表（）32154213543212/14/10002/34/10102/32/14/10012

7、/72/154/51002/15yyyyyxxxxxxxxjjzc 原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题化为极小问题原问题原问题最优解最优解对偶问题对偶问题最优解最优解原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：两个问题作一比较两个问题作一比较:原问题最优解（决策变量）原问题最优解（决策变量）对偶问题最优解（决策变量）对偶问题最优解（决策变量）14 wz2/3,2/721xx 对偶问题的松弛变量对偶问题的松弛变量2/1,4/1,0321yyy原问题的松弛变量原问题的松弛变量 原问题与

8、对偶问题在某种意义上原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达问题仅仅在第一个问题的另一种表达而已。而已。理论证明：理论证明：原问题与对偶问题原问题与对偶问题解的关系解的关系 ),1(0),1(.max11njxmibxatsxczjnjijijnjjj ),1(0),1(.min11miynjcyatsybwimijiijmiii),1(njxj),1(miyi imiijnjjybxc 11jmiinjijjnjimiijxyaxya 1111)(mijinjijimijnjjixyayxa1111)(jnj

9、jxc 1imiiyb 1（1 1）极大化问题（原问题）的任一可行）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优解所对应的目标函数值是对偶问题最优目标函数值的下界。目标函数值的下界。（2 2）极小化问题（对偶问题）的任一可）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优行解所对应的目标函数值是原问题最优目标函数值的上界。目标函数值的上界。（3 3）若原问题可行，但其目标函数值无）若原问题可行，但其目标函数值无界，则对偶问题无可行解。界，则对偶问题无可行解。（4 4）若对偶问题可行，但其目标函数值）若对偶问题可行，但其目标函数值无界，则原问题无可行解。无界，

10、则原问题无可行解。（5 5）若原问题有可行解而其对偶问题无）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。可行解，则原问题目标函数值无界。（6 6）对偶问题有可行解而其原问题无可）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。行解，则对偶问题的目标函数值无界。原问题原问题对偶问题对偶问题bYXCbYCX),1(njxj),1(miyi imiijnjjybxc11 ),1(njxj),1(miyi),1(njxj ),1(miyi jnjjjnjjxcxc11imiiimiiybyb 11 wzminmax ),1,1(0,0),1(.max11njmixxm

11、ibxxatsxczsijnjisijijnjjj,0 Y),1(0miyi 0 YAC),1(1njcyanijiij ),1(0miyi bBCxcBnjjj11 miiiyb1,0 iy;1 njijijbxa,1 njijijbxa0 iyimiiyb 1 imiijnjjybxc11 0)(11 iijminjijybxa0,01 injjijibxay),1(0)(1miybxaiijnjij mijinjjijnjjxyaxc111jjjiczy ,（）32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyy

12、yxxxxxxxxjjzc 原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：2154332543212/32/7002/152/32/1102/152/14/14/1014/54/1xxxxxyyyyyyy)(jjzc 原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表（）32154213543212/14/1000

13、2/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题化为极小问题原问题原问题最优解最优解对偶问题对偶问题最优解最优解原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：目标函数值目标函数值原问题原问题对偶对偶问题问题()L()D例例 考虑下面问题考虑下面问题Max Z=x1+2x2+3x3+3x4 x1+2x2+2x3+3x4 20 s.t.2x1+x2+3x3+2x4 20 x1,x2,x3,x

14、4 0 Min W=20y1+20y2 y1+2y2 1 2y1+y2 2 s.t.2y1+3y2 3 3y1+2y2 4 y1,y20已知已知(D)的的最优解为最优解为 Y*=(6/5,1/5)T 用互补用互补松弛定理求出松弛定理求出(L)的最的最优解。优解。*13422320(1)xxxx*123423220(2)xxxx*1221.20.41.61yy*1222.40.22.62yy*342320 xx*343220 xx所以所以x1*=x2*=0.解：由于解：由于y1*0,y2*0,由互补松弛性知由互补松弛性知解得解得x3*=x4*=4.所以所以(L)的最优解为的最优解为X*=(0,0,4,4)T因为因为代入代入(1),(2)得得