第二章线性规划的对偶理论与灵敏度分析教材课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第二章线性规划的对偶理论与灵敏度分析教材课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 线性规划 对偶 理论 灵敏度 分析 教材 课件
- 资源描述:
-
1、运筹学运筹学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院2022-12-162第二章第二章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析1.线性规划的对偶问题线性规划的对偶问题2.影子价格影子价格3.对偶单纯形法对偶单纯形法4.灵敏度分析灵敏度分析2022-12-163例例1 美佳公司计划制造美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设两种家电产品。已知各制造一件时分别占用的设备备A A、B B的台时、调试时间及的台时、调试时间及A A、B B设备和调试工序每天可用于这两种家电的能力、设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如
2、下表所示。问该公司应制造各售出一件时的获利情况如下表所示。问该公司应制造、两种家电备多少两种家电备多少件使获取的利润为最大。件使获取的利润为最大。设:设:x x1 1 A A产品的生产量产品的生产量 x x2 2 B B产品的生产量产品的生产量利润利润 z=2 xz=2 x1 1+x+x2 2 约束约束条件条件5 5x x2 2 15 156 6x x1 1+2x+2x2 2 24 24x x1 1+x+x2 2 5 5x x1 1,x x2 2 0 0stst.第一节第一节 线性规划的线性规划的对偶问题对偶问题2022-12-1645 5x x2 2 +x x3 3 =15 156 6x x
3、1 1+2x+2x2 2 +x+x4 4 =24 24x x1 1+x+x2 2 +x x5 5=5 5x x1 1,x x2 2,x x3 3 ,x x4 4 ,x x5 5 0 0约束约束条件条件stst.利润利润 max z=2 xmax z=2 x1 1+x+x2 2 +0 x+0 x3 3+0 x+0 x4 4+0 x+0 x5 5 标准化标准化最终单纯形表最终单纯形表C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 0 0 x x3 3 x x4 4 x x5 5151524245 5 0 5 1 0 0 0 5 1 0
4、0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 2 1 0 0 0 2 1 0 0 0最优解最优解X X*=(7/2,3/2,=(7/2,3/2,15/215/2,0 0,0 0)Z Z*=17/2=17/2C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x50 0 2 2 x x3 3 x x1 1 x x2 215/215/27/27/23/23/2 0 0 1 5/4 -15/2 0 0 1 5/4 -15/2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/
5、20 -1/4 3/2 0 0 00 0 0 -1/4 -1/2 -1/4 -1/2 2022-12-1655 5x x2 2 15 156 6x x1 1+2x+2x2 2 24 24x x1 1+x+x2 2 5 5x x1 1,x x2 2 0 0约束约束条件条件把解把解X=(7/2,3/2)X=(7/2,3/2)代入原问题代入原问题(因为因为为附加变量为附加变量)分析分析5 53 32 215/215/224245 5P O 一个问题?一个问题?市场上设备市场上设备A A、设备设备B B和调试工序每小时值多少钱?和调试工序每小时值多少钱?在什么价位时,才能使美佳公司愿意出让自己的资源?
6、在什么价位时,才能使美佳公司愿意出让自己的资源?2022-12-1666 6y y2 2+y+y3 3分分析析设:设:y y1 1 设备设备A A值的值的价值价值 y y2 2 设备设备B B值的值的价值价值 y y3 3 调试工序调试工序值的值的价值价值2 25 5y y1 1+2y+2y2 2+y+y3 31 1z=15 yz=15 y1 1+24y+24y2 2 +5y+5y3 3总价值总价值minminy y1 1,y,y2 2,y,y3 30 0stst.2022-12-1676 6y y2 2+y+y3 32 25 5y y1 1+2y+2y2 2+y+y3 31 1z=15 yz
7、=15 y1 1+24y+24y2 2 +5y+5y3 3minminy y1 1,y,y2 2,y,y3 30 0stst.z z=-15 y=-15 y1 1-24y-24y2 2-5y 5y3 3maxmaxstst.6 6y y2 2+y+y3 3 y y4 4=2 25 5y y1 1+2y+2y2 2+y+y3 3 y y5 51 1=y y1 1,y,y2 2,y,y3 3,y,y4 4,y,y5 5 0 0C C-15 -24 -5 -15 -24 -5 0 0 -M 0 0 -M -M-MC CB BY YB Bb y1 y2 y3 y4 y5 y6 y7-M M-M-My
8、y6 6y y7 72 21 1 0 6 1 -1 0 1 0 0 6 1 -1 0 1 0 5 2 5 2 1 1 0 -1 0 1 0 -1 0 1 M-15 8M-24 2M-5 -M M-15 8M-24 2M-5 -M -M-M 0 0 0 0问题求解问题求解2022-12-168C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y y2 2y y3 31/41/41/21/2-5/4 1 0 -1/4 1/4-5/4 1 0 -1/4 1/415/2 0 1 15/2 0 1 1/2 -3/2
9、1/2 -3/2 -15/2 0 0 -7/2 -3/2-15/2 0 0 -7/2 -3/2 Y=(0,Y=(0,0,0),0,0)z z=-17/2=-17/2z z=17/2=17/22022-12-169Y=(0,Y=(0,0,0),0,0)问题分析问题分析问题问题的解的解6 6y y2 2+y+y3 32 25 5y y1 1+2y+2y2 2+y+y3 31 1z=15yz=15y1 1+24y+24y2 2 +5y+5y3 3minminy y1 1,y,y2 2,y,y3 30 0stst.问题:问题:?原问题:原问题:利润利润 z=2 xz=2 x1 1+x+x2 2 约束约
10、束条件条件5 5x x2 2 15 156 6x x1 1+2x+2x2 2 24 24x x1 1+x+x2 2 5 5x x1 1,x x2 2 0 0stst.问题问题的解的解X X*=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)Z Z*=17/2=17/2Z Z*=17/2=17/25 5*3/2 =15/23/2 =15/215156 6*7/2+27/2+2*3/2=243/2=242424=7/2+3/2=57/2+3/2=55 5=结结论论估价估价影子价格影子价格(即增加单位资源所(即增加单位资源所得到的贡献)得到的贡献)Z=CX=Yb Z/b=(
11、Yb)=Y2022-12-1610C C 2 1 2 1 0 0 00 0 0C CB BX XB Bbx1 x2 x3 x4 x50 02 21 1x x3 3x x1 1x x2 215/215/27/27/23/23/20 0 1 5/4 -15/20 0 1 5/4 -15/21 01 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/20 0 0 -1/4 -1/20 0 0 -1/4 -1/2-0 0 0 1/4 1/20 0 0 1/4 1/2利润利润 z=2 xz=2 x1 1+x+x2 2 约束约束条件条件5 5x x2 2
12、 15 156 6x x1 1+2x+2x2 2 24 24x x1 1+x+x2 2 5 5x x1 1,x x2 2 0 0stst.6 6y y2 2+y+y3 32 25 5y y1 1+2y+2y2 2+y+y3 31 1z=15yz=15y1 1+24y+24y2 2 +5y+5y3 3minminy y1 1,y,y2 2,y,y3 30 0stst.C C-15 -24 -5 -15 -24 -5 0 00 0C CB BY YB Bb y1 y2 y3 y4 y5-24-24-5-5y y2 2y y3 31/41/41/21/2-5/4 1 0 -1/4 1/4-5/4 1
13、 0 -1/4 1/4 15/2 0 1 15/2 0 1 1/2 -3/2 1/2 -3/2 -15/2 0 0 -7/2 -3/2-15/2 0 0 -7/2 -3/2-15/2 0 0 7/2 3/2 15/2 0 0 7/2 3/2 Y=(0,Y=(0,0,0),0,0)X X*=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)问题变量问题变量问题剩余松弛变量问题剩余松弛变量解的关系解的关系2022-12-1611一、对偶问题一、对偶问题对对称称形形式式X X 0 0stst.AX AX b bmax z=max z=CXCX其中:其中:C=C=(c c1 1
14、,c c2 2,c cn n)b=b=(b b1 1,b b2 2,b bm m)T T X=X=(x x1 1,x x2 2,x xn n)T T Y=Y=(y y1 1,y y2 2,y ym m)T TY Y 0 0stst.A AT TY CY CT Tmin w=min w=Y YT Tb b利润利润 z=2 xz=2 x1 1+x+x2 2 约束约束条件条件5 5x x2 2 15 156 6x x1 1+2x+2x2 2 24 24x x1 1+x+x2 2 5 5x x1 1,x x2 2 0 0stst.6 6y y2 2+y+y3 32 25 5y y1 1+2y+2y2
15、2+y+y3 31 1z=15yz=15y1 1+24y+24y2 2 +5y+5y3 3minminy y1 1,y,y2 2,y,y3 30 0stst.2022-12-1612非非对称形式对称形式x x1 1 0,x 0,x2 2 0,x 0,x3 3无约束无约束 stst.a a1111x x1 1+a+a1212x x2 2+a+a1313x x3 3 b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2323x x3 3 =b =b2 2a a3131x x1 1+a+a3232x x2 2+a+a3333x x3 3 b b3 3max z=cmax z=
16、c1 1x x1 1+c+c2 2x x2 2+c+c3 3x x3 3 x x1 1,x x2 2,x x3 3,x x3 3 00stst.a a1111x x1 1-a-a1212x x2 2 +a+a1313x x3 3-a a1313x x3 3 b b1 1a a2121x x1 1-a-a2222x x2 2 +a+a2323x x3 3-a a2323x x3 3 b b2 2-a-a2121x x1 1+a+a2222x x2 2 _ a_ a2323x x3 3+a a2323x x3 3 -b-b2 2-a-a3131x x1 1+a+a3232x x2 2 -a-a33
17、33x x3 3+a a3333x x3 3 -b-b3 3max z=cmax z=c1 1x x1 1-c-c2 2x x2 2 +c+c3 3x x3 3 -c-c3 3x x3 3 y y1 1,y,y2 2,y,y2 2 ,y y3 3 00stst.a a1111y y1 1+a a2121y y2 2 a a2121y y2 2-a a3131y y3 3 c c1 1-a-a1212y y1 1-a a2222y y2 2+a+a2222y y2 2-a a3232y y3 3-c-c2 2a a1313y y1 1+a a2323y y2 2 a a2323y y2 2-a
18、a3333y y3 3 c c3 3-a-a1313y y1 1-a a2323y y2 2+a+a2323y y2 2+a a3333y y3 3-c-c3 3min w=bmin w=b1 1y y1 1+b+b2 2y y2 2-b-b2 2y y2 2 -b-b3 3y y3 3 min w=bmin w=b1 1y y1 1+b+b2 2y y2 2+b+b3 3y y3 3a a1111y y1 1+a a2121y y2 2+a a3131y y3 3 c c1 1a a1212y y1 1+a a2222y y2 2+a a3232y y3 3 c c2 2a a1313y y
19、1 1+a a2323y y2 2+a a3333y y3 3 =c=c3 3stst.y y1 10,y0,y2 2无约束无约束,y y3 3 0 02022-12-1613二、对偶规则二、对偶规则&原问题有原问题有m m个约束条件,对偶问题有个约束条件,对偶问题有m m个变量个变量&原问题有原问题有n n个变量,对偶问题有个变量,对偶问题有n n个约束条件个约束条件&原问题的价值系数对应对偶问题的右端项原问题的价值系数对应对偶问题的右端项&原问题的右端项对应对偶问题的价值系数原问题的右端项对应对偶问题的价值系数&原问题的系数矩阵转置后为对偶问题系数矩阵原问题的系数矩阵转置后为对偶问题系数矩
20、阵变量、约束与系数变量、约束与系数2022-12-1614变量与约束对应关系变量与约束对应关系原问题(对偶问题)原问题(对偶问题)对偶问题(原问题)对偶问题(原问题)max z=CX AX ()b X()0 或无约束或无约束 min w=Yb ATY()C Y()0 或无约束或无约束 有有n个决策变量个决策变量 xj (j0、2n)xj 0 0变量变量 xj 0 0 xj 无约束无约束 有有n个约束条件个约束条件 对应的约束为对应的约束为 约束约束 对应的约束为对应的约束为 对应的约束为对应的约束为 有有m个约束条件个约束条件 对应的约束为对应的约束为 约束约束 对应的约束为对应的约束为 对应
21、的约束为对应的约束为 有有m个决策变量个决策变量 yj (j0、2m)yj 0 0变量变量 yj 0 0 yj 无约束无约束2022-12-1615三、对偶问题的基本性质(对称形)三、对偶问题的基本性质(对称形)1对称性:对偶问题的对偶问题是原问题对称性:对偶问题的对偶问题是原问题1弱对偶性:极大化原问题的任一可行解的目弱对偶性:极大化原问题的任一可行解的目标函数值,不大于其对偶问题任意可行解的标函数值,不大于其对偶问题任意可行解的目标函数值目标函数值1对偶定理:若一个问题有最优解,则另一问对偶定理:若一个问题有最优解,则另一问题也有最优解,且目标函数值相等。若原问题也有最优解,且目标函数值相
22、等。若原问题最优基为题最优基为B B,则其对偶问题最优解则其对偶问题最优解Y Y*=C=CB BB B-1-11无界性:原问题无界,对偶问题无可行解无界性:原问题无界,对偶问题无可行解需要说明的是:需要说明的是:这些性质同样适用于非对称形问题这些性质同样适用于非对称形问题2022-12-1616X X 0 0stst.AX AX b bmax z=CXmax z=CXX,Xs 0X,Xs 0stst.AX+AX+IXsIXs =b bmax z=CX+0Xsmax z=CX+0XsC C C C 0 0C CB BX XB Bb X Xs0 0X Xs sb b A IA IC C C CB
23、B C CN N 0 0C CB BX XB Bb XB XN Xs0 0X Xs sb b B N IB N IC C C CB B C CN N 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B-1-1B B B B-1-1N N B B-1-1I IC CB B-C-CB BB B-1-1B B C CN N-C-CB BB B-1-1N 0-CN 0-CB BB B-1-1I I C C C CB B C CN N 0 0C CB BX XB Bb XB XN XsC CB BX XB BB B-1-1b b B B-1-1B B
24、B B-1-1N N B B-1-1I I 0 0 C CN N-C-CB BB B-1-1N -CN -CB BB B-1-12022-12-1617C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x5151524245 5 0 5 1 0 0 0 5 1 0 0 6 6 2 2 0 1 0 0 1 0 1 1 1 1 0 0 10 0 1 C C 2 1 2 1 0 0 0 0 0 0C CB BX XB Bb x1 x2 x3 x4 x515/215/27/27/23/23/2 0 0 1 5/4 -15/2 0 0 1 5/4 -15/
25、2 1 0 1 0 0 1/4 -1/2 0 1/4 -1/2 0 1 0 1 0 -1/4 3/20 -1/4 3/2 B与与B-1B B-1-1=1 5/4 -15/21 5/4 -15/20 1/4 -1/20 1/4 -1/20 -1/4 3/20 -1/4 3/2B=B=1 0 51 0 50 6 20 6 20 1 10 1 12022-12-1618第二节第二节 影子价格影子价格*1*1*miiinjjjybxczbi是线性规划原问题约束条件的右端项,它代表第是线性规划原问题约束条件的右端项,它代表第i i种资源的拥种资源的拥有量;有量;对偶变量对偶变量yiyi*的意义代表在资源
展开阅读全文