第2章 线性规划(对偶问题).ppt





《第2章 线性规划(对偶问题).ppt》由会员分享,可在线阅读,更多相关《第2章 线性规划(对偶问题).ppt(59页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第2章章对偶理论对偶理论线性规划续线性规划续知识点知识点了解对偶问题的特点,熟悉互为对偶的问了解对偶问题的特点,熟悉互为对偶的问题之间的关系;题之间的关系;掌握对偶规划的理论和性质,如可逆性、掌握对偶规划的理论和性质,如可逆性、弱对偶性、对偶定理、互补松驰定理等;弱对偶性、对偶定理、互补松驰定理等;掌握对偶单纯形法;掌握对偶单纯形法;主要内容主要内容一、对偶问题的基本概念一、对偶问题的基本概念二、对称的对偶线性规划二、对称的对偶线性规划三、对偶的基本性质三、对偶的基本性质四、对偶单纯形法四、对偶单纯形法一、对偶问题的基本概念一、对偶问题的基本概念载重汽车载重汽车 大轿车大轿车资源限制资源限制
2、钢材钢材劳动力劳动力座椅座椅22.5025116002500400利润(千元利润(千元/辆)辆)34传统的线性规划问题:传统的线性规划问题:在有限的资源下如何安排生产以获得最大利润在有限的资源下如何安排生产以获得最大利润该问题的线性规划模型为:该问题的线性规划模型为:目标函数:目标函数:maxZ=4x1+3x2约束条件:约束条件:2x12x2 16005x1+2.5x2 2500 x1 400 x1 0,x2 0现在的问题:如果工厂目前不再打算生产现在的问题:如果工厂目前不再打算生产汽车,而是将钢材和座椅以比买价更高的汽车,而是将钢材和座椅以比买价更高的价格卖出去(加价),把生产能力以更高价格
3、卖出去(加价),把生产能力以更高的工时费接受外协加工,那么材料和工时的工时费接受外协加工,那么材料和工时的定价应该是多少才是合算的?的定价应该是多少才是合算的?假设假设y1表示出售单位钢材的利润,表示出售单位钢材的利润,y2表示外协加工的工时利润,表示外协加工的工时利润,y3表示出售每套大轿车座椅的利润表示出售每套大轿车座椅的利润那么生产一辆载重汽车的材料销售利润和那么生产一辆载重汽车的材料销售利润和工时利润之和不应低于出售一辆载重汽车工时利润之和不应低于出售一辆载重汽车所得的利润,即:所得的利润,即:2y1+2.5y2 3同样有,同样有,2y1+5y2+y3 4为了不亏本,各种材料的利润(加
4、价)不为了不亏本,各种材料的利润(加价)不能为负值,即:能为负值,即:y1、y2、y3 0工厂的总利润是出售材料的利润、工时利工厂的总利润是出售材料的利润、工时利润和座椅利润之和,即:润和座椅利润之和,即:W=1600y1+2500y2+400y3从工厂决策者的角度看从工厂决策者的角度看W越大越好。但为了越大越好。但为了在市场实现交易,在满足上述条件的基础在市场实现交易,在满足上述条件的基础上,上,W应尽可能小。从而得到如下线性规划应尽可能小。从而得到如下线性规划模型:模型:MinW=1600y1+2500y2+400y32y1+2.5y2 3s.t.2y1+5y2+y3 4y1、y2、y3
5、0线性规划原问题和对偶问题线性规划原问题和对偶问题原问题:原问题:MaxZ=c1x1+cnxna11x1+a1nxn b1a21x1+a2nxn b2s.t.am1x1+amnxn bmX1,xn 0对偶问题:对偶问题:MinW=b1y1+bmyma11y1+am1ym c1a12y1+am2ym c2s.t.a1ny1+amnym cny1,ym 0矩阵表述矩阵表述原问题:原问题:MaxZ=CTXs.t.AX bX 0对偶问题:对偶问题:MinW=bTYs.t.ATY CY 0两个模型之间的关系:两个模型之间的关系:原问题是求最大值,而对偶问题是求最小值;原问题是求最大值,而对偶问题是求最小
6、值;原问题的约束条件是原问题的约束条件是“”,而对偶问题的约,而对偶问题的约束条件是束条件是“”;原问题的目标函数系数是对偶问题的约束条件原问题的目标函数系数是对偶问题的约束条件右端的常数项;原问题的约束条件右端的常数右端的常数项;原问题的约束条件右端的常数项是对偶问题目标函数的系数;项是对偶问题目标函数的系数;原问题约束条件中原问题约束条件中xi的系数是对偶问题第的系数是对偶问题第i个约个约束条件的系数,原问题第束条件的系数,原问题第i个约束条件的系数是个约束条件的系数是对偶问题的约束条件中对偶问题的约束条件中yi的系数。的系数。对称的对偶线性规划对称的对偶线性规划定义:如果一个线性规划具备
7、下面两个条定义:如果一个线性规划具备下面两个条件,则称它具有对称形式:件,则称它具有对称形式:所有的变量都是非负的;所有的变量都是非负的;所有的约束条件都是不等式,且在目标函数是所有的约束条件都是不等式,且在目标函数是求极大值的情况下,为求极大值的情况下,为“”型,求极小值时,型,求极小值时,为为“”型。型。原问题(对偶问题)原问题(对偶问题)对偶问题(原问题)对偶问题(原问题)目标函数目标函数限定向量限定向量价值向量价值向量技术系数技术系数约束条件约束条件变量数目变量数目约束条件个数约束条件个数变量正负变量正负目标函数目标函数价值向量价值向量限定向量限定向量技术系数技术系数对偶变量对偶变量约
8、束条件个数约束条件个数对偶变量数目对偶变量数目约束条件约束条件非对称形式的对偶问题非对称形式的对偶问题在原线性规划问题为在原线性规划问题为Max型,且变量非负型,且变量非负的前提下:的前提下:1.原问题约束条件是原问题约束条件是“”型型两边都乘以两边都乘以“-1”转化为转化为“”型,得到对偶型,得到对偶规划的变量约束为:规划的变量约束为:yi 0例:例:MaxZ=x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3 2x1,x2,x3 0MaxZ=x1+2x2-3x3S.t.-x1-2x2-5x3-12x1-3x2-4x3 2x1,x2,x3 0MinW=-y1+2y2S
9、.t.-y1+2y2 1-2y1-3y2 2-5y1-4y2-3y1,y2 0令令y1=-y1,上述模型化为:,上述模型化为:MinW=y1+2y2S.t.y1+2y2 12y1-3y2 25y1-4y2-3y1 0,y2 0例:例:MaxZ=x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3 2x1,x2 0,x3 0令令x3=-x3,得:,得:MaxZ=x1+2x2+3x3S.t.x1+2x2-5x3 12x1-3x2+4x3 2x1,x2,x3 0MinW=y1+2y2S.t.y1+2y2 12y1-3y2 2-5y1+4y2 3y1,y2 0第三个方程两边同乘第
10、三个方程两边同乘-1,得,得MinW=y1+2y2S.t.y1+2y2 12y1-3y2 25y1-4y2-3y1,y2 02.原问题约束条件是原问题约束条件是“=”型型看成两个约束条件:看成两个约束条件:”+”组成,得到组成,得到对偶规划的变量约束为:对偶规划的变量约束为:yi无非负约束(即可正可负)无非负约束(即可正可负)例:例:MaxZ=x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3=2x1,x2,x3 0MaxZ=x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3 22x1-3x2-4x3 2x1,x2,x3 0MinW=y1+2y2
11、-2y3S.t.y1+2y2-2y3 12y1-3y2+3y3 25y1-4y2+4y3-3y1,y2,y3 0MaxZ=x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3 2-2x1+3x2+4x3-2x1,x2,x3 0令令y4=y2-y3,得:,得:MinW=y1+2y4S.t.y1+2y4 12y1-3y4 25y1-4y4-3y1 0,y4无符号约束无符号约束原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题(或对偶问题)原问题(或对偶问题)对偶问题(或原问题)对偶问题(或原问题)目标函数为目标函数为MaxZ目标函数为目标函数为MinW变量变量n个个
12、0 0无约束无约束n个个 约束条件约束条件约束约束条件条件m个个 m个个 0 0无约束无约束变量变量价值系数价值系数cj约束条件右端项约束条件右端项bi约束条件的系数矩阵约束条件的系数矩阵A约束条件右端项约束条件右端项cj价值系数价值系数bi约束条件的系数矩阵约束条件的系数矩阵AT例:例:写出下面线性规划问写出下面线性规划问题的对偶问题:题的对偶问题:1.解:根据上述对偶关解:根据上述对偶关系,可以写出原问题系,可以写出原问题的对偶问题:的对偶问题:例:例:写出下面线性规划问写出下面线性规划问题的对偶问题:题的对偶问题:2.解:根据上述对偶关解:根据上述对偶关系,可以写出原问题系,可以写出原问
13、题的对偶问题:的对偶问题:对偶的基本性质对偶的基本性质原问题:原问题:MaxZ=CTXs.t.AX bX 0对偶问题:Min W=bTY s.t.ATY C Y 0对称性:对偶问题的对偶是原问题;对称性:对偶问题的对偶是原问题;弱对偶性:若弱对偶性:若X是原问题的可行解,是原问题的可行解,Y是是对偶问题的可行解,则对偶问题的可行解,则CTX bTY弱对偶性的证明:弱对偶性的证明:AX bXTAT bTXTATY bTY所以:所以:bTY XTATY XTC=CTX无界性:若原问题(对偶问题)为无界无界性:若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。解,则其对偶问题(原问题)无
14、可行解。例:例:说明:无界性质并不存在逆(例见:说明:无界性质并不存在逆(例见:P57)可行解是最优解的条件:可行解是最优解的条件:设设X*是原问题的可行解,是原问题的可行解,Y*是对偶问题的可行是对偶问题的可行解,当解,当CTX*=bTY*时,时,X*,Y*是最优解。是最优解。证明:由弱对偶性,可知原问题的所有可行解证明:由弱对偶性,可知原问题的所有可行解X均满足均满足CTX bTY*又因为又因为CTX*=bTY*,所以,所以CTX CTX*,即:,即:X*是使目标函数取值最大的可行解。因而是最是使目标函数取值最大的可行解。因而是最优解。优解。同理可证同理可证Y*也是最优解。也是最优解。对偶
15、定理:若原问题有最优解,则对偶对偶定理:若原问题有最优解,则对偶问题也有最优解,且最优目标函数值相等。问题也有最优解,且最优目标函数值相等。证明:设证明:设X*是原问题的最优解,则其对应的基矩阵是原问题的最优解,则其对应的基矩阵B必有:必有:CBTB-1A-CT 0,(非基变量的检验数大于或等于,(非基变量的检验数大于或等于0,基变量的检验数等于基变量的检验数等于0)即:即:ATY*C,其中,其中,Y*=CBTB-1T故故Y*是对偶问题的可行解,它使:是对偶问题的可行解,它使:W=bTY*=bTCBTB-1T=CBTB-1b由于由于X*是原问题的最优解,使目标函数值是原问题的最优解,使目标函数
16、值Z=CTX*=CBTB-1b由此得到:由此得到:bTY*=CBTB-1b=CTX*因此,因此,Y*是对偶问题的最优解。是对偶问题的最优解。原规划的检验数对应于对偶规划的一个解;原规划的检验数对应于对偶规划的一个解;对偶规划的检验数对应于原规划的一个解。对偶规划的检验数对应于原规划的一个解。特别地,若原问题的最优基为特别地,若原问题的最优基为B,则其对偶,则其对偶问题的最优解为问题的最优解为Y*=CBTB-1互补松驰定理:设原问题和对偶问题的标准互补松驰定理:设原问题和对偶问题的标准型分别为:型分别为:若若X*,Y*分别是原问题和对偶问题的可行解,分别是原问题和对偶问题的可行解,那么那么Y*T
17、Xs=0和和YsTX*=0当且仅当当且仅当X*、Y*为最优为最优解。解。证明:证明:原问题原问题对偶问题对偶问题MaxZ=CXMinW=YbAX+Xs=bYA-Ys=CX,Xs 0Y,Ys 0Z=CX=(YA-Ys)X=YAX-YsXW=Yb=Y(AX+Xs)=YAX+YXs充分性:充分性:P58必要性:必要性:P58该定理的隐含结论:该定理的隐含结论:当一对对偶规划达到当一对对偶规划达到最优最优时,若一个问题的某时,若一个问题的某个变量为正数,则相应的另一个问题的约束必个变量为正数,则相应的另一个问题的约束必取等式;或者一个问题中的约束条件取不等式,取等式;或者一个问题中的约束条件取不等式,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第2章 线性规划对偶问题 线性规划 对偶 问题

限制150内