运筹学对偶问题精品文稿.ppt
《运筹学对偶问题精品文稿.ppt》由会员分享,可在线阅读,更多相关《运筹学对偶问题精品文稿.ppt(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学对偶问题第1页,本讲稿共47页4.1 对偶问题(1)(1)对偶问题的提出对偶问题的提出例例1 1、生产组织与计划问题、生产组织与计划问题A,BA,B各生产多少各生产多少,可获最大利润可获最大利润?可用资源可用资源煤煤劳动力劳动力仓库仓库AB123202单位利润单位利润4050306024第2页,本讲稿共47页MaxZ=40 x1+50 x2x1+2x2 303x1+2x2 602x2 24x1,x2 0s.t目标函数目标函数约束条件约束条件如果因为某种原因,不愿意自己生产,而希望通过将现有如果因为某种原因,不愿意自己生产,而希望通过将现有资源承接对外加工来获得收益,那么应如何确定各资源的
2、资源承接对外加工来获得收益,那么应如何确定各资源的使用价格使用价格?第3页,本讲稿共47页MaxZ=40 x1+50 x2x1+2x2 303x1+2x2 602x2 24x1,x2 0s.t目标函数目标函数约束条件约束条件两个原则两个原则1.所得不得低于生产所得不得低于生产的获利的获利2.要使对方能够接受要使对方能够接受设三种资源的使用单价分别为设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品生产单位产品A A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A A的获利的获利生产单位产品生产单位产品B B的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品B B
3、的获利的获利y1+3y2 402y1+2y2+2y3 50 50第4页,本讲稿共47页通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则根据原则2,对方能够接受的价格显然是越低越好,因此,对方能够接受的价格显然是越低越好,因此此问题可归结为以下数学模型:此问题可归结为以下数学模型:MinW=30y1+60y2+24y3y1+3y2 402y1+2y2+2y3 50y1,y2,y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题,此问题为此问题为对偶问题对偶问题,y1,y2,y3称为称为影子价
4、格影子价格第5页,本讲稿共47页(2)(2)对偶问题的形式对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题为其对偶问题,其中为其对偶问题,其中yi(i=1,2,m)称为称为对偶变量对偶变量。上述对偶问题称为上述对偶问题称为对称型对偶问题对称型对偶问题。原问题简记为原问题简记为(P),对偶问题简记为,对偶问题简记为(D)第6页,本讲稿共47页原始问题原始问题MaxZ=CXs.t.AXbX0bACMaxnm对偶问题对偶问题MinW=Ybs.t.YATCY0MinCTATbTnm第7页,本讲稿共47页例例2:求线性规划问:求线性规划问题的对偶规划
5、题的对偶规划解:由原问题的结构可知为对称型对偶问题解:由原问题的结构可知为对称型对偶问题第8页,本讲稿共47页例例3:求线性规划问:求线性规划问题的对偶规划题的对偶规划解:由原问题的结构可知不是对称型对偶问题,解:由原问题的结构可知不是对称型对偶问题,可先化为对称型,再求其对偶规划。可先化为对称型,再求其对偶规划。第9页,本讲稿共47页例例4:求线性规划问:求线性规划问题的对偶规划题的对偶规划解:由原问题的结构可知不是对称型对偶问题,解:由原问题的结构可知不是对称型对偶问题,可先化为对称型,再求其对偶规划。可先化为对称型,再求其对偶规划。第10页,本讲稿共47页上式已为对称型对偶问题,故可写出
6、它的对偶规划上式已为对称型对偶问题,故可写出它的对偶规划令令则上式化为则上式化为第11页,本讲稿共47页对偶关系对应表对偶关系对应表原问题原问题对偶问题对偶问题目标函数类型目标函数类型MaxMin目标函数系数目标函数系数目标函数系数目标函数系数右边项系数右边项系数与右边项的对应关系与右边项的对应关系右边项系数右边项系数目标函数系数目标函数系数变量数与约束数变量数与约束数变量数变量数n约束数约束数n的对应关系的对应关系约束数约束数m变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型变量变量 0约束约束 的对应关系的对应关系无限制无限制原问题约束类型与原问题约束类
7、型与 0对偶问题变量类型对偶问题变量类型约束约束 变量变量 0的对应关系的对应关系无限制无限制第12页,本讲稿共47页4.2 对偶问题的基本性质定理定理1 1 对偶问题的对偶就是原问题对偶问题的对偶就是原问题MaxW=-Ybs.t.-YA-CY0MinZ=-CXs.t.-AX-bX0MaxZ=CXs.t.AXbX0MinW=Ybs.t.YACY0对偶的定义对偶的定义对偶的定义对偶的定义第13页,本讲稿共47页定理定理2 2(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解,则有的可行解,则有C bX,yXy证明:由证明:由AX b,y 0有有 yAX by由由Ay C,X 0有有yA
8、X CX所以所以CX yAX yb第14页,本讲稿共47页推论推论2、(P)有可行解有可行解,但无有限最优解,则但无有限最优解,则(D)无可行解。无可行解。定理定理3、yX,分别为分别为(P),(D)的可行解,且的可行解,且XyC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明:对任证明:对任X,有,有CX by=CXX最优最优推论推论1、(P),(D)都有可行解,则必都有最优解。都有可行解,则必都有最优解。第15页,本讲稿共47页定理定理4 4(主对偶定理主对偶定理)若一对对偶问题若一对对偶问题(P)(P)和和(D)(D)都有可行解,则它们都有最优都有可行解,则它们都有最优解,且
9、目标函数的最优值必相等。解,且目标函数的最优值必相等。证明:证明:(1)当当X*和和Y*为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界,即可找到有限所以原问题的目标函数值有上界,即可找到有限最优解;对偶问题有下界,也存在有限最优解。最优解;对偶问题有下界,也存在有限最优解。第16页,本讲稿共47页(2)当当X*为原问题的一个最优解,为原问题的一个最优解,B为相应的最优基为相应的最优基,通过引入松弛变量通过引入松弛变量Xs,将问题将问题(P)转化为标准型转化为标准型令令令令所以所以Y
10、*是对偶问题的可行解,是对偶问题的可行解,对偶问题的目标函数值为对偶问题的目标函数值为X*是原问题的最优解,原是原问题的最优解,原问题的目标函数值为问题的目标函数值为第17页,本讲稿共47页推论:推论:若一对对偶问题中的任意一个有最优解,则另一个若一对对偶问题中的任意一个有最优解,则另一个也有最优解,且目标函数最优值相等。也有最优解,且目标函数最优值相等。一对对偶问题的关系,有且仅有下列三种:一对对偶问题的关系,有且仅有下列三种:1.1.都有最优解,且目标函数最优值相等;都有最优解,且目标函数最优值相等;2.2.两个都无可行解;两个都无可行解;3.3.一个问题无界,则另一问题无可行解。一个问题
11、无界,则另一问题无可行解。第18页,本讲稿共47页定理定理5若若X,Y分别为分别为(P),(D)的可行解,则的可行解,则X,Y为最优解的充要条件是为最优解的充要条件是同时同时成立成立证证:(:(必要性)必要性)原问题原问题 对偶问题对偶问题第19页,本讲稿共47页MaxZ=CXs.t.AX+XS=bX,XS0MinW=Ybs.t.ATY-YS=CW,WS0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数第20页,本讲稿共47页y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对
12、偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中,其中一个大于在一对变量中,其中一个大于0 0,另一个一定等于,另一个一定等于0 0第21页,本讲稿共47页4.3 对偶问题的解令令设原问题为设原问题为为原问为原问题的一题的一最优解最优解则则为对偶问题为对偶问题的一最优解的一最优解CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN-CBB-1N-CBB-1第22页,本讲稿共47页例例1MaxZ=40X
13、1+50X2X1+2X2 303X1+2X2 602X2 24X1,X2 0 0s.ty1y2y3MinW=30y1+60y2+24y3y1+3y2+0y3 402y1+2y2+2y3 50y1,y2,y3 0 0s.tMaxW=-30y1-60y2-24y3y1+3y2+0y3y4=402y1+2y2+2y3y5=50y1,y2,y3,y4,y5 0 0s.t第23页,本讲稿共47页MaxW=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7)y1+3y2+0y3y4+y6=402y1+2y2+2y3y5+y7=50y1,y2,y3,y4,y5 0 0s.tC-30-60-24
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 对偶 问题 精品 文稿
限制150内