4运筹学第二章线性规划的对偶理论.ppt
《4运筹学第二章线性规划的对偶理论.ppt》由会员分享,可在线阅读,更多相关《4运筹学第二章线性规划的对偶理论.ppt(43页珍藏版)》请在咨信网上搜索。
1、运筹学基础运筹学基础1 1第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析2 2运筹学基础运筹学基础解:解:设生产设生产x1的产品的产品I,x2的产品的产品II,则,则目标函数目标函数 max z 2x1+3x2约束条件约束条件 x1+2x2 8 4 x1 16 4x2 12 x1 x2 0线性规划的对偶理论线性规划的对偶理论例例1 某某厂厂可可生生产产产产品品和和,生生产产I需需1台台设设备备,4单单位位原原料料A,生生产产II需需2台台设
2、设备备,4单单位位原原料料B。该该厂厂每每生生产产一一件件产产品品获获利利2元元每每生生产产一一件件产产品品获获利利3元元。现现有有8台台设设备备,16单单位位原原料料A,12单单位位原原料料B,问如何安排计划使获利最多,问如何安排计划使获利最多?运筹学基础运筹学基础3 3第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析4 44.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础我我们们从从另另一一个个角角度度来来讨讨论论这这个个问
3、问题题:假假设设不不生生产产品产产品,而将所有资源出租或外售。,而将所有资源出租或外售。问题:考虑每种资源如何定价。问题:考虑每种资源如何定价。5 54.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础例例1 产品产品:1台设备,台设备,4单位原料单位原料A,获利,获利2元;元;产品产品:2台设备,台设备,4单位原料单位原料B,获利,获利3元。元。现有:现有:8台设备,台设备,16单位原料单位原料A,12单位原料单位原料B设设y1,y2,y3分分别别表表示示出出售售单单位位设设备备台台时时的的租租金金和出让原材料和出让原材料A,B的附加额。根据题意可得:的附加额。根据题意可得:y1
4、+4y22 ,2 y1+4y33 ,=8 y1+16y2+12y3要实现出租的愿望,只能在满足要实现出租的愿望,只能在满足所有产品的利润所有产品的利润条件下,必须使条件下,必须使尽可能的小。尽可能的小。6 64.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础为此需解决如下的线性规划问题:为此需解决如下的线性规划问题:y1+4y2 2 2 y1 +4y33 min=8 y1+16y2+12y2 y1,y2,y30 max z2x1+3x2x1 2x2 84x1 16 4x2 12x1x2 0与与关系?关系?对原模型设:对原模型设:1 2 4 0 0 4 A=C=(2,3)b=(8,
5、16,12)TX=(x1,x2)TY=(y1,y2,y3)则可得则可得:7 74.1 4.1 对偶问题的提出对偶问题的提出运筹学基础运筹学基础max z=CXAXb (5.1)X0 y1+4y2 2 2 y1 +4y33 min=8 y1+16y2+12y3 y1,y2,y30 max z2x1+3x2x1 2x2 84x1 16 4x2 12x1x2 0与与有何关有何关系?系?对愿模型设:对愿模型设:1 2 4 0 0 4 A=C=(2,3)b=(8,16,12)TX=(x1,x2)TY=(y1,y2,y3)则可得则可得:min =YbYA C (5.2)Y0和和我们把(我们把(5.2)式的
6、问题称为()式的问题称为(5.1)式问题的)式问题的对偶线对偶线性规划问题性规划问题。运筹学基础运筹学基础8 8第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析9 94.2 4.2 原问题与对偶问题的关系原问题与对偶问题的关系运筹学基础运筹学基础1对称式的对偶对称式的对偶“”不等式约束条件的原问题与不等式约束条件的原问题与“”不等式约束条件的对不等式约束条件的对偶问题,称为偶问题,称为对称式对称式的一对对偶问题。的一对对偶问题。原问题:原问题
7、:max z=c1x1+c2x2+cnxn a11 a12 a1n am1 am2 amnx1xnb1bm x1,x2,xn0对偶问题:对偶问题:min =b1y1+b2y2+bmym a11 a12 a1n am1 am2 amn y1,y2,ym 0(y1,y2,ym)(c1,c2,cn)n个变量,m个约束条件 m个变量,n个约束条件1010运筹学基础运筹学基础2约束条件全部为约束条件全部为“=”的对偶的对偶max z=CXAXbX0原问题:原问题:max z=CXAXbX0AXb等价max z=CXAXbX0AXbmax z=CXX0AAXbbmin =(Y1,Y2)Y1,Y20AACb
8、b(Y1,Y2)其中其中 Y1=(y1,y2,ym),Y2=(ym+1,ym+2,y2m)等价等价min =YbY为无约束为无约束YA Cmin =(Y1Y2)bY1,Y20(Y1 Y2)A C令令Y=(Y1 Y2)对偶问题对偶对偶问题问题11114.2 4.2 原问题与对偶问题的关系原问题与对偶问题的关系运筹学基础运筹学基础3约束条件为约束条件为“”的对偶的对偶max z=CXAXbX0原问题:原问题:max z=CXAX bX0min =Y1(b)Y1(A)CY10min =YbYA CY0等价等价对对偶偶问问题题令令Y=Y1对偶对偶问题问题1212运筹学基础运筹学基础4变量变量0的对偶的
9、对偶max z=CXAXbX0原问题:原问题:令令X=X1max z=C(X1)A(X1)bX10max z=(C)X1(A)X1 bX10min =Y bY(A)CY0min =Y bY A CY0对对偶偶问问题题对偶对偶问题问题等等价价1313运筹学基础运筹学基础5变量无约束的对偶变量无约束的对偶max z=CXAXbX无约束无约束原问题:原问题:令令X=X1 X2 X1,X20max z=CX1CX2X1,X20AX1 AX2 bmax z=(C,C)X1,X20bX1X2(A,A)X1X2等等价价min =YbY0Y(A,A)(C,C)对对偶偶min=YbYACY0 YA Cmin=Y
10、bYA CY0min=YbYACY0YA C等价等价等等价价等等价价对偶对偶问题问题1414运筹学基础运筹学基础6原问题与对偶问题的关系表原问题与对偶问题的关系表原问题(或对偶问题)原问题(或对偶问题)对偶问题(或原问题)对偶问题(或原问题)目标函数目标函数 max zn个变量个变量变量变量0变量变量0变量无约束变量无约束目标函数目标函数 min n个约束条件个约束条件约束约束约束约束约束约束=m个约束条件个约束条件约束约束约束约束约束约束=约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数m个变量个变量变量变量0变量变量 0变量无约束变量无约束 目标函数变量系数目标函数变量系数约束
11、条件右端项约束条件右端项1515运筹学基础运筹学基础例:求下列线性规划问题的对偶问题例:求下列线性规划问题的对偶问题 max z5x1+4x2+6x3x1+2x2 2x1 +x3 33x1+2x2+x3 5x1 0 x20,x3 无约束无约束 x1x2 +x3=1C=(5,4,6)b=(2,3,-5,1)T1 2 01 0 1 -3 2 1A=1-1 1解:解:因原问题有因原问题有3个变个变量,量,4个约束条件,个约束条件,所以对偶问题所以对偶问题4个个变量,变量,3个约束条个约束条件。设变量件。设变量Y=(y1,y2,y3,y4)min=2y1+3y25y3+y4于是于是 y1+y23y3+
12、y45 2y1 +2y3y44 y2 +y3+y46y10,y2,y3 0,y4无约束无约束Y AC确定约束条件确定约束条件运筹学基础运筹学基础1616第二章第二章 线性规划线性规划q 对偶问题的提出对偶问题的提出q 原问题与对偶问题的关系原问题与对偶问题的关系q 对偶问题的基本性质对偶问题的基本性质q 对偶单纯形法对偶单纯形法q 灵敏度分析灵敏度分析17174.3 4.3 对偶问题的基本性质对偶问题的基本性质运筹学基础运筹学基础1对称性:对称性:对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。证:证:设原问题为:设原问题为:max z=CX;AXb;X0则则对偶问题为:对偶问题为:m
13、in=Yb;YAC;Y 0因因min=max()max()=Yb;YAC;Y 0 min(1)=CX;AX b;X 0对偶问题对偶问题又因又因min(1)=max(1)max(1)=CX;AX b;X 0这就是原问题。这就是原问题。18184.3 4.3 对偶问题的基本性质对偶问题的基本性质运筹学基础运筹学基础2弱对偶性:弱对偶性:若若X(0)是原问题的可行解,是原问题的可行解,Y(0)是对偶问是对偶问题的可行解,则存在题的可行解,则存在CX(0)Y(0)b。证:证:设原问题为:设原问题为:max z=CX;AXb;X0则则因因X(0)是原问题的可行解,所以是原问题的可行解,所以AX(0)b又
14、因又因Y(0)是对偶问题的可行解,所以是对偶问题的可行解,所以Y(0)AC Y(0)A X(0)Y(0)b 因此,因此,CX(0)Y(0)A X(0)Y(0)b结论成立。结论成立。对偶问题为:对偶问题为:min=Yb;YAC;Y 0Y(0)A X(0)CX(0)19194.3 4.3 对偶问题的基本性质对偶问题的基本性质运筹学基础运筹学基础3无界性:无界性:若原问题无界解,若原问题无界解,则其对偶问题无可行解则其对偶问题无可行解。证:由弱对偶性可知结论成立。证:由弱对偶性可知结论成立。(CX(0)Y(0)b)4最优性:最优性:若若X(0)是原问题的可行解,是原问题的可行解,Y(0)是对偶问题的
15、是对偶问题的可行解,且可行解,且CX(0)=Y(0)b ,则,则X(0),Y(0)是最优解。是最优解。证:证:设设Y(1)是对偶问题的任意可行解,由性质是对偶问题的任意可行解,由性质2可得可得Y(1)b CX(0)=Y(0)b ,则,则Y(0)是对偶问题的最优解。是对偶问题的最优解。设设X(1)是原问题的任意可行解,由性质是原问题的任意可行解,由性质2可得可得CX(0)=Y(0)b CX(1),则,则X(0)是原问题的最优解。是原问题的最优解。20204.3 4.3 对偶问题的基本性质对偶问题的基本性质运筹学基础运筹学基础5对偶定理:对偶定理:若原问题有最优解,若原问题有最优解,那么对偶问题也
16、那么对偶问题也有优解;且目标函数值相等。有优解;且目标函数值相等。证:证:设设X(0)是原问题的最优解,它对应的基是原问题的最优解,它对应的基B,必有,必有CCBB-1A0,且,且 z=CX(0)=CBB-1b 。令令Y(0)=CBB-1显然,显然,Y(0)AC。所以所以 Y(0)是对偶问题的可行解。是对偶问题的可行解。又因又因Y(0)b=CBB-1b=CX(0)由性质由性质4可知可知Y(0)是对偶问题的最优解。是对偶问题的最优解。因此,结论成立。因此,结论成立。2121运筹学基础运筹学基础6互补松弛性:互补松弛性:若若X(0)是原问题的可行解,是原问题的可行解,Y(0)是对偶是对偶问题的可行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第二 线性规划 对偶 理论
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。