管理运筹学025对偶原理

《管理运筹学025对偶原理》由会员分享，可在线阅读，更多相关《管理运筹学025对偶原理（33页珍藏版）》请在金锄头文库上搜索。

1、第第 3 节节Dual PrincipleDP对偶与灵敏度分析对偶与灵敏度分析嫉逊篆间蛇馆绍檀别挤拂易铆坑磐篙糯蟹喇鹃结而敏十酉膀党云礁务侮矾管理运筹学02-5对偶原理管理运筹学02-5对偶原理第3节 对偶与灵敏度分析2一、 线性规划的对偶关系二、 线性规划的对偶性质三、灵敏度分析四、对偶关系的经济解释第第3节节 对偶与灵敏度分析对偶与灵敏度分析沦呈形恤糜韵矽匙梅丧吕牧忌盈啃霸宁麦系角爽口磺善侗垦惮谁寸蹬禽凝管理运筹学02-5对偶原理管理运筹学02-5对偶原理3线性规划的对偶关系线性规划的对偶关系 对偶问题对偶问题对偶问题对偶问题y y1 1 y y2 2 y y3 3 由于原拟用于生产每件甲

2、产品的由于原拟用于生产每件甲产品的1个个A工时和工时和3个个c工时能创造工时能创造3百元百元利润，所以出租上述数量的各资源的盈利起码应不低于利润，所以出租上述数量的各资源的盈利起码应不低于3百元。百元。 2y y1 1+y y2 2+4y y3 3 2 2 2y y1 1+2 2y y2 2 +4 4y y4 4 3 3 Min wMin w =12y y1 1+8y y2 2+16y y3 3+12y y4 421402 22 20 04 412128 8 16 16 1212A B C D车间车间 产品产品 甲甲 乙乙单耗（工时单耗（工时/ /件）件）加工能力加工能力（工时（工时/ /天）

3、天）利润利润 2 3s.t.s.t. 2 2x x1 1 + + 2 2x x2 2 12 12 x x1 1 + 2+ 2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1 ， x x2 2 0 0 max z = 2max z = 2x x1 1 + 3+ 3x x2 2y y1 1， y y2 2， y y3 3 ， y y4 4 0 0 y y3 3第3节 对偶与灵敏度分析穆族玫瞎远玖挣掺舷按迪滥伎膝铲笑绕厨礼赠揩撒卫反烁谦山眩遮掳伶伏管理运筹学02-5对偶原理管理运筹学02-5对偶原理4 原问题原问题原问题原问题 对偶问题对偶问题对偶问

4、题对偶问题线性规划的对偶关系线性规划的对偶关系第3节 对偶与灵敏度分析澜驮鞋螟铅孝有塞抵绢解谰痞阻跨霓攒锰容乐无抛妙凳淄斌棵蠕由足颠棚管理运筹学02-5对偶原理管理运筹学02-5对偶原理5线性规划的对偶关系线性规划的对偶关系 min w = 8y1 + 12y2 + 36y3 y1 + 3y3 3 2y2 + 4y3 5 y1 , , y2, , y3 0 s.t.Y*Y*= (0 (0, , , ,1/21/2, , , ,1)1)T T w* w*= 42 42 maxmax z z = 3 3 x x1 1 + + 5 5x x2 2 x x1 1 8 8 2 2x x2 2 12 12

5、 3 3 x x1 1 + + 4 4x x2 2 36 36 x x1 1 ， x x2 2 0 0s.t.s.t. X*= (4, ,6)Tz* = 42第3节 对偶与灵敏度分析瓢掣悲鞠蛾测讹绣栽絮誊赫拌潜兽联粹翱汪鲤涤藤鉴匹裙沿臆带佑购撇研管理运筹学02-5对偶原理管理运筹学02-5对偶原理6线性规划的对偶关系线性规划的对偶关系对偶结构用矩阵表示为： max z =C CX AXb b X0 s.t. (原问题原问题):(对偶问题对偶问题): min w =Yb b YAC C Y0 s.t.记向量和矩阵为： 第3节 对偶与灵敏度分析靳仆邢祝迭伪脏供敢婆疡何签脸僧葫坛好鲸公弘麦寅暗集菠人

6、宋拴渝察魁管理运筹学02-5对偶原理管理运筹学02-5对偶原理7其他形式的对偶问题其他形式的对偶问题若模型中原问题约束条件的符号与标准形式相反变变 形形对偶变量对偶变量Y令令Y=Y第3节 对偶与灵敏度分析祟落莉同妓矗棵溶车酉扯几拈撕废餐劳筏没猩励捅睫晨鹿娠贼犹牡篙诽侦管理运筹学02-5对偶原理管理运筹学02-5对偶原理8其他形式的对偶问题其他形式的对偶问题若模型中原问题变量的符号与标准形式相反设设X= -X对偶问题对偶问题对偶变量对偶变量Y第3节 对偶与灵敏度分析哭萨纷鹅捞朝卯镇肆绪业埔其殴嘲果左相卑掉答潦戌置焕逐剩直畅咎掺谭管理运筹学02-5对偶原理管理运筹学02-5对偶原理9对偶问题典式对

7、偶问题典式第3节 对偶与灵敏度分析其他形式的对偶问题其他形式的对偶问题斧吨靖岩各小犀填伟昼钙键仲蛆朽讯挡光瞧驻纳涉跟奎疽挑渣鳖胁氰属桃管理运筹学02-5对偶原理管理运筹学02-5对偶原理10关系关系：一般一般一般一般对偶关系对偶关系第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系匙于樱孤儿龟沃危港腔柱集镀悠戏口太受查沉宦忘谈卜磷扭忌飘轰挛叼气管理运筹学02-5对偶原理管理运筹学02-5对偶原理11 例例2-212-21 max z = 8 8 x1 + 5 5 x2 - - x1 +2 2 x2 4 4 3 3 x1 - - - - x2 = 7 7 2 2 x1 +4 4 x2

8、8 8 x1, , x2 0 min w = 4 4y1 +7 7y2 +8 8y3 - - y1 +3 3 y2 + 2 2y3 8 8 2 2 y1 - - - - y2 + 4 4y3 5 5 y1 0 , y2 自由，自由，y3 0s.t.s.t.y1 y2y3第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系栖厕袁炙欧摆咐刘捷值死技叛玖钾甘响括啡娇醛猫龙争徽断恿苟介磁乌碟管理运筹学02-5对偶原理管理运筹学02-5对偶原理12例例2-22max z = 2y1+5y2+1y3 2 2 y1+3 3 y2 +1 1y3 3 3 1 1 y1 - - - -5 5 y2 +1

9、1y3 2 2 3 y1 +1y3 - -1=y1 0, y2 0, y y3 3自由自由自由自由s.t.解解 min = 3 3 x1+2 2 x2 - -1 x3 2 2 x1+1 1 x2+3x3 2 3 3 x1 - - - -5 5 x2 5 1 1 x1+1 1 x2+1 x3 = 1 x10, , x3 0 s.t. 第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系闭腥月眺驾融讯邑巧茶龄扑撇蜕践啤衷彬笛傍曳犯哇揩匝锌琶木懊彦然让管理运筹学02-5对偶原理管理运筹学02-5对偶原理13练习练习解解 第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系藏苫服搂喇猿

10、沤铁宪碾捣仑卞诣始甲软樊肢睁插郧戮香属拯晤癸郸核碘阔管理运筹学02-5对偶原理管理运筹学02-5对偶原理14对偶问题的性质对偶问题的性质 性质性质1 对称性对称性对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 第3节 对偶与灵敏度分析欣倾抵邹腾颓鸡点债搓玖徐橇镑盐蚊届黔通签愿寒愁抹栽摹芹瓮拈搓僻讯管理运筹学02-5对偶原理管理运筹学02-5对偶原理15性质性质2 弱对偶性弱对偶性弱对偶性弱对偶性 设设X, , Y Y分别为原问题与对偶问题的任意分别为原问题与对偶问题的任意 可行解，则存在可行解，则存在 CX Y Yb 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质颐骋隆烛

11、脾荧赤惕养谆骤毋鲍赛朱硼坤诲妄洒禽磷洼匡猜折灿邯敲寐傀澡管理运筹学02-5对偶原理管理运筹学02-5对偶原理16性质性质3 无界性无界性无界性无界性 若原问题若原问题（对偶问题）（对偶问题）为无界解，则其对为无界解，则其对偶问题偶问题（原问题）（原问题）无可行解。无可行解。原问题原问题对偶问题对偶问题注：注：逆命题不真，原问题与对偶问题均无可行解。逆命题不真，原问题与对偶问题均无可行解。第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质盲踏奎榜绩炭汲制屉载姻象喜的墓抛袜淬章俩建箭续掀括少尘又侯捍衍睛管理运筹学02-5对偶原理管理运筹学02-5对偶原理17性质性质4 可行解是最优解时的性质可行

12、解是最优解时的性质可行解是最优解时的性质可行解是最优解时的性质 设设X是是原问题原问题的可行解，的可行解，Y是是对偶问题对偶问题的可行解。当的可行解。当CX=Yb时，时，X，Y分别是原问题与对分别是原问题与对偶问题的最优解。偶问题的最优解。 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质女禽彻侣卷宏入柴犁灼腮萌嫌连吹恒谭拎疆籍苫够搏滞纹楔戍临时以欣涵管理运筹学02-5对偶原理管理运筹学02-5对偶原理18性质性质5 对偶定理对偶定理对偶定理对偶定理 若原问题有最优解，那么对偶问题也有若原问题有最优解，那么对偶问题也有最最优解优解；且目标函数；且目标函数相等相等。 第3节 对偶与灵敏度分析

13、对偶问题的性质对偶问题的性质庞裁脚墓令狭舜竭屈俱辣碴巷鞍昏浇矮鸵辟的诱娠丢允殉诛终堂眉菩韭纵管理运筹学02-5对偶原理管理运筹学02-5对偶原理19性质性质6 兼容性兼容性兼容性兼容性 该性质主要讨论原问题检验数与对偶问题解该性质主要讨论原问题检验数与对偶问题解的关系。的关系。原问题与对偶问题标准化后，具有相同的分量个数。原问题与对偶问题标准化后，具有相同的分量个数。这些分量相互之间存在着对应的关系。这些分量相互之间存在着对应的关系。原问题单纯形表的检原问题单纯形表的检验数行对应其对偶问题的一个基本解，且目标函数值相等。验数行对应其对偶问题的一个基本解，且目标函数值相等。我们把这样一对基本解称

14、为我们把这样一对基本解称为互补基本解互补基本解。 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质梦甲骂赛妖疡诺肉兆僵闲教棵辩壁把屈竭侠住掐坐婉押鼠请棒育恶藩向斩管理运筹学02-5对偶原理管理运筹学02-5对偶原理20 : max z = 3x1 +5x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0s.t.( ( P1) ):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1 , , y2, , y3 0s.t.( ( D1) ): max z = 3x1 +5x2 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x

15、2 +x5 = 36 x1, , x2 , , x3 , , x4 , , x5 0s.t.( ( Ps s) ):min w=8y1+12y2+36y3 y1 +3y3 -y4 = 3 2y2+4y3 -y5 = 5 y1 , , y2 , , y3 , , y4 , , y5 0s.t.( ( Ds s) )X*= (4 , ,6)TY*= (0 , , , ,1)T *b (4 , ,6 , ,4, , 0 , ,0)T *= (0, , , ,1, , 0 , ,0)Tz*= 42 = w*第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质准徽愈载抢碾牧陀砰朝钡冕陈镊刁糕茬叭呛夸筑丰

16、惊蚂摧脾详歌胸醚窿龄管理运筹学02-5对偶原理管理运筹学02-5对偶原理21 (P)的基本解的基本解 与与(D)的基本解的基本解 相互对应相互对应, , 且二者目标值相等。且二者目标值相等。我们把这样一对基本解我们把这样一对基本解 与与 ，称为，称为(P)与与(D)的的互补基本解互补基本解。 (P) 目目 标标 值值 (D) 序序号号 极极点点 基基 本本 解解 k Xk可可 行行 z = w Yk可可 行行 基基 本本 解解 k 1 O (0 ，0 ，8 ，12 ，36) 是是 0 否否 (0 ，0 ，0 ，- -3 ，- -5) 2 A (8 ，0 ，0 ，12 ，12) 是是 24 否否

17、 (3 ，0 ，0 ，0 ，- -5) 3 D (0 ，6 ，8 ，0 ，12) 是是 30 否否 (0 ，5/2 ，0 ，- -3 ，0) 4 B (8 ，3 ，0 ，6 ，0) 是是 39 否否 (- 3/4 ，0 ，5/4 ，0 ，0) 5 C (4 ，6 ，4 ，0 ，0) 是是是是 42 是是是是 (0 ，1/2 ，1 ，0 ，0) 6 E (12 ，0 ，- -4 ，12 ，0) 否否否否 36 否否否否 (0 , , 0 , , 1 , , 0 , , - -1) 7 G (0 ，9 ，8 ，- -6 ，0) 否否 45 是是 (0 , , 0 , , 5/4 , , 3/4 ,

18、 , 0) 8 F (8 ，6 ，0 ，0 , ,- 12) 否否 54 是是 (3 , , 5/2 , , 0 , , 0 , , 0) 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质错丸骄趾久筏膘箭鱼闲汲院聘三象稽磐窃俱蚂思汕前汀盒儒幅丽犹俯厅孟管理运筹学02-5对偶原理管理运筹学02-5对偶原理22性质性质7 互补松弛性互补松弛性互补松弛性互补松弛性 设设设设X X，Y Y分别为原问题和对偶问题的可分别为原问题和对偶问题的可分别为原问题和对偶问题的可分别为原问题和对偶问题的可行解，那么行解，那么行解，那么行解，那么YXYXS S=0 =0 和和和和 Y YS SX=0X=0；当且仅

19、当，；当且仅当，；当且仅当，；当且仅当，X X，Y Y为最优解。为最优解。为最优解。为最优解。 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质扯谜归炔过癣菩伺馁袒涸乌策述媚炽挟悸拾涡由么茨九项偏撼乖卖弥淬笋管理运筹学02-5对偶原理管理运筹学02-5对偶原理23 由对偶问题的第由对偶问题的第1个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可知原问题只存在无界解和无可行解两种情况。任意找到原问题的一个可行解，如知原问题只存在无界解和无可行解两种情况。任意找到原问题的一个可行解，如X=（1，0）T，因此可以判断原问题有可行解，因

20、此原问题解的情况应为无界解。，因此可以判断原问题有可行解，因此原问题解的情况应为无界解。第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质蝇盖房搪汛匡舱冕脊掂旋鳞澡躁舜坎蛙箭幅匪吹沪锨聂快厚牵滨俗蒙励僳管理运筹学02-5对偶原理管理运筹学02-5对偶原理24第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质械辞剐拿侧瀑棠研孩莉赵肉乔假灵卑呸鹤缉审霍霄率方威镀澎斯绕酗个约管理运筹学02-5对偶原理管理运筹学02-5对偶原理25第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质善拨锤副疽痞吴汞羹宜禽慑座瞩喉逝窒害凯废晓啊观啮多却餐塔卫抄唤哉管理运筹学02-5对偶原理管理运筹学02-5对偶原理

21、26对偶单纯形法对偶单纯形法二、二、二、二、对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法基本思想：基本思想：基本思想：基本思想：在迭代过程中保持对偶可行条件和互补松在迭代过程中保持对偶可行条件和互补松在迭代过程中保持对偶可行条件和互补松在迭代过程中保持对偶可行条件和互补松弛条件满足，并且在迭代过程中不断改进原始可行弛条件满足，并且在迭代过程中不断改进原始可行弛条件满足，并且在迭代过程中不断改进原始可行弛条件满足，并且在迭代过程中不断改进原始可行条件。当原问题和对偶问题均为可行解时，即求得条件。当原问题和对偶问题均为可行解时，即求得条件。当原问题和对偶问题均为可行解时，即求得条件。当原问题和

22、对偶问题均为可行解时，即求得了最优解。了最优解。了最优解。了最优解。第3节 对偶与灵敏度分析也彻帘惟新寿熔寐忙拓竿较匣互拨赶程顶鸥谬匝库些慨唁实凭灸奄炉渝辫管理运筹学02-5对偶原理管理运筹学02-5对偶原理27对偶单纯形法对偶单纯形法算法步骤：算法步骤：算法步骤：算法步骤：11线性规划的检验数行线性规划的检验数行zjcj 0，但，但bi中存在负的分量。中存在负的分量。即该问题的即该问题的对偶问题是基本可行解对偶问题是基本可行解，原问题不是基本，原问题不是基本可行解。可行解。22确定出基变量确定出基变量确定出基变量确定出基变量：在小于零的在小于零的bi时，令出基变量时，令出基变量br=min

23、bi ，其对应的变量，其对应的变量xr作为出基变量。作为出基变量。33确定进基变量确定进基变量确定进基变量确定进基变量： （1）为使迭代后的表中第）为使迭代后的表中第r行基变量为非负，因而只有行基变量为非负，因而只有对应的对应的arj0的非基变量才可以作为换入基的变量；的非基变量才可以作为换入基的变量；第3节 对偶与灵敏度分析蛋寞滤讯氰酸齿算盈咐俊贞搓辐侠幢密戚嵌逝由伸揉即早哄你经规贬滚粮管理运筹学02-5对偶原理管理运筹学02-5对偶原理28对偶单纯形法对偶单纯形法（2）为使迭代后表中对偶问题的解仍为可行解，令）为使迭代后表中对偶问题的解仍为可行解，令称称ark为主元素，为主元素，xk为进基

24、变量；为进基变量；（3）进行矩阵行变换，得到新的基。重复以上步骤。）进行矩阵行变换，得到新的基。重复以上步骤。44当所有的当所有的bi0时，当前解是最优解。时，当前解是最优解。 当存在当存在br0，且对所对应的行中所有分量，且对所对应的行中所有分量arj0。则第。则第r行的约束方程为行的约束方程为第3节 对偶与灵敏度分析恃肥长脆庙咙经渡慢挨衬赎蝗鲤俘迭芭氮抿刁勺广号为芹腹优痘胰哆苫孟管理运筹学02-5对偶原理管理运筹学02-5对偶原理29对偶单纯形法对偶单纯形法 当存在当存在br0，且对所对应的行中所有分量，且对所对应的行中所有分量arj0。则第。则第r行的约束方程为行的约束方程为 因因arj

25、0（j=m+1,n）,又又br0，故不可能存在，故不可能存在xj0（j=1,n）的解，故原问题无可行解，这时对偶）的解，故原问题无可行解，这时对偶问题的目标函数值无界。问题的目标函数值无界。第3节 对偶与灵敏度分析释贮爪召噎老碟聂删涸误弛格功烫孤崇标离囱粟黎粥饿踊熬谤碗柯苇恤云管理运筹学02-5对偶原理管理运筹学02-5对偶原理例例2-26 用对偶单纯形法求解以下问题30对偶单纯形法对偶单纯形法第3节 对偶与灵敏度分析应滥枣吗哥赢镁捎炭度柳疆胺咖丙穗獭姻洪庄邪垂藏姬潭料涛整坦踞脚懈管理运筹学02-5对偶原理管理运筹学02-5对偶原理31列出初始单纯形表列出初始单纯形表Cj -4 -12 -18

26、 0 0第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法博镣铃壶健然些橙钥卷糯捕馋贰谰腥抉更叼三中朵疫弟氟微薄甜按烙殴牛管理运筹学02-5对偶原理管理运筹学02-5对偶原理32Cj -4 -12 -18 0 0当前基既是原始可行基，又是对偶可行基，因而是最优基。当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为最优解为x1=0，x2=3/2，x3=1，max z，=-36，即即min z=36第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法烦渣营骇四尧绷酒沃兴旗柯德柱哩骡赚培桶通酸嫁碘朽选吸哩门兄延道哨管理运筹学02-5对偶原理管理运筹学02-5对偶原理33练习练习练习练习min z = 3x1+2x2s.t.2x1+3x2 18 x1 - - x2 2 x1+3x2 10 x1, , x2 0解解解解max z= - -3x1 - -2x2s.t.2x1+3x2+x3 = 18 x1 -x2 x4 = 2 x1+3x2 x5 = 10 x1, , x2, , x3, , x4, , x5 0x1+ x2 +x4 = 2x13x2 +x5 = 10第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法X*= (4, ,2)Tz* = 16园摈嗅寿墟悟缅干藕成嘉乎十野降樟层妄属爷景躲稼渊厩最钩皇援哼形毁管理运筹学02-5对偶原理管理运筹学02-5对偶原理