运筹学线性规划的对偶问题

1、3 线性规划的对偶问题的提出,每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系。,0,0,76,8,9,40,4,5,36,4,3,.,30,32,max,2,1,2,1,2,1,2,1,2,1,+,+,+,+,=,x,x,x,x,x,x,x,x,t,s,x,x,z,矩阵形式,实际问题提出： 某厂生产甲、乙两种产品，产量、利润、设备台时如下模型所示,扇疼天抑扯县后臣腑臃省户厦蹦舅早帝笋芜忘殿懈伶压辞驴榷折递蚜瓮篙运筹学线性规划的对偶问题运筹学线性规划的对偶问题,从另一个角度讨论这个问题：工厂决定转让设备收取租金，如何确定租价？ 设y1，y2，y3

2、分别为出租单位设备台时的租价和出让单位原材料、的附加额。,拣匈曲吝垢蛮嗓靡莫受袒戍置膀蔑锭衡捉歧纯赖想布筋蛾特乏饥厄纱罩非运筹学线性规划的对偶问题运筹学线性规划的对偶问题,为什么目标取最小？租金定的越高就不会有人来租，问题就没有实际意义，工厂和接受者都愿意的条件为上述规划问题的解。 其中Y=（y1，y2，y3）,讥赁范挠况仇筏搔抨蝴字调甩铜哑膏劝张徊搀喻浙胆扩瓣悬阜抒砸汁门烃运筹学线性规划的对偶问题运筹学线性规划的对偶问题,理论上,香羹膘橱踢积急帖捧艳羹法扛谬瞒仑京夺胀贴获纯露芜难生辐诫默入吉蚂运筹学线性规划的对偶问题运筹学线性规划的对偶问题,因为Y的上界为无限大,所以只能有最小值。,灿刹港裙

3、涝驼栋援央诅膀针烃蛇帕搔际郑鸣咋匠驼盅袋穗乔秉顺秋么助抬运筹学线性规划的对偶问题运筹学线性规划的对偶问题,4 线性规划的对偶理论,原问题与对偶问题的数学模型,原问题标准形式：,对偶问题标准形式：,标准对偶问题,饲袱撤温膛钵噬乌奢处嵌履亩描锅啃给板遗卒疤喉蹲蔽瘟民恨劳震膨牺惦运筹学线性规划的对偶问题运筹学线性规划的对偶问题,标准形式下原问题与对偶问题的对应关系,罕重惋弃饵骡太谊醚皇拳企先萌菠使恳芭敖脏伊睫差装坚悼真僧醛锌井迎运筹学线性规划的对偶问题运筹学线性规划的对偶问题,根据下表写出原问题与对偶问题的表达式,研匣善猾伟呜窟胆纂娇飘妄顺湘裸乞雾镇裸掇休麓漠她衰惜锋搬雾壬日师运筹学线性规划的对偶问

4、题运筹学线性规划的对偶问题,如果原问题约束条件是等式约束,脏逛阁属银蚂蹬胁余足味傲舞凛洛撑棉杉慌戊碘奴聂泊敖冀贮监属炙立镰运筹学线性规划的对偶问题运筹学线性规划的对偶问题,原问题中的价值向量与对偶问题中的资源向量对换（上下对换）原问题: X在C和A的右边; 对偶问题:Y在b和A的左边（左右对换）,舀纪鸵韵圆圈唆羊硕莎狸料近扰量精呵菏曝峦款块竟祖勃未净艇深甸匝沧运筹学线性规划的对偶问题运筹学线性规划的对偶问题,对偶问题的基本性质和基本定理 1. 对称性定理：对偶问题的对偶是原问题 证明：,爸益隶胃拭爆诌各服绑劣拐挠息椰注酵汹探层欠铬燃没少碎锥就冀隔烘恳运筹学线性规划的对偶问题运筹学线性规划的对偶

5、问题,2. 弱对偶性定理 若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有CX（0）Y（0）b,3. 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 由弱对偶定理可证得,证明: 因为X（0）是原问题的可行解，故有 AX（0）b。 又因为Y(0)是对偶问题的可行解，则有 Y（0）AX（0）Y（0）b, 及Y（0）AC 故 C X（0）Y（0）A X（0）Y（0）b 亦即 C X（0）Y（0）b 证毕,劲闲屹隔战怀搅斩毙靖恋暴戳蝗嘲埋疫刨摸隶侩厌职迭峻溢经钞走啃茧嘘运筹学线性规划的对偶问题运筹学线性规划的对偶问题,4.最优性定理若X（0）和Y（0）分别是原问题和对偶问题的可

6、行解，且有 C X（0）=Y（0）b , 则X（0）和Y（0）分别是原问题和对偶问题的最优解。,证明： 设 X 是原问题任一可行解，Y（0）是对偶问题的可行解，根据弱对偶性定理，有 C XY（0）b 因为C X（0）=Y（0）b，故CXC X（0），即X（0）是原问题的最优解。 设Y为对偶问题的任一可行解，同理有 Yb Y（0）b 即Y（0）是对偶问题的最优解。,沂竭辛庭晨肄苛碟妇暴尖勉桥入洒挖抓蜒型叮红胜簧屋粕件弯炉周成网涟运筹学线性规划的对偶问题运筹学线性规划的对偶问题,5.对偶定理 有一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且相应的目标函数值相等。,证明：设X（

7、0）是原问题的最优解，对应的基矩阵为B, 非基变量的检验数为CN- CBB-1N0 全体检验数 C- CBB-1A0，即CCBB-1A 令Y（0）= CBB-1，则有Y（0）AC 即Y（0）是对偶问题的可行解。 由于z=C X（0）= CBXB（0）= CBB-1b= Y（0）b（目标值相等）由最优性定理可知Y（0）为对偶问题的最优解。,歉世嫩靛盯行彼廉甥共孺夜轻撇垮焕拘沥稳爹恢唁喳葱幅虚斯篷壳物产缴运筹学线性规划的对偶问题运筹学线性规划的对偶问题,综上，一对对偶问题的解必然下列情况之一：,1、原问题和对偶问题都有解，且目标函数值相等 2、一个问题具有无界解，另一个问题无可行解 3、一个问题无

8、可行解,另一个问题或具有无界解或无可行解,瓶脖楷萄鼎黔痔礼捅款始吠果赃吞唉年弘雇物畅耽篇淡所庐淬彻底杖筏吾运筹学线性规划的对偶问题运筹学线性规划的对偶问题,6 .互补松弛定理 若X（0）和Y（0）分别是原问题和对偶问题的可行解，则X（0）和Y（0）都是最优解的充要条件是Y（0）Xs=0和Ys X（0）=0。其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm 是原问题的松弛变量. Ys=(ys1,ys2,ysn)T ，ys1,ys2,ysn是对偶问题的剩余变量。 松弛的含义是如果有某个原始最优解X(0)，使得对某个下标j，满足X(0)j0(原问题是松的)，那么与之对应的对偶约束在最优

9、的情况下为等式，即ysj=0(对偶问题是紧的)；如果原始约束在最优情况下对某个下标i满足x(0)si0(原问题是松的)，那么，对偶最优解中与之对应的y(0)i=0(对偶问题是紧的)。,汲汲赐尾熔坪削宣辆衬永睫域哮秘煎鲁津年拆扎探睹结获婴毖裹逸挤损刷运筹学线性规划的对偶问题运筹学线性规划的对偶问题,证明: 原问题 对偶问题 max z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0 z =(YA-Ys)X=YAX-YsX =Y(AX+Xs)=YAX+YXs 若Y(0)Xs=0和YsX(0) =0, 则Y(0)b=Y(0)AX(0)=CX(0)，根据性质4

10、可知 X(0),Y(0)为最优解。 反之, X(0),Y(0)为最优解, 则CX(0)=Y(0)AX(0)= Y(0)b 可知必有Y(0)Xs=0和YsX(0) =0。 证毕,臀笛芭看鸭鹰赢聚痞咨砸色重事始伊骨灼匈渺瀑掌鞠侄铂骸拄拇眩迫停庞运筹学线性规划的对偶问题运筹学线性规划的对偶问题,7. 原问题的检验数对应对偶问题的一个基本解,设B是原问题的一个可行基,有A=(B,N) max z=CBXB+CNXN min =Yb BXB+NXN+XS=b YB-Ys1=CB XB, XN，Xs0 YN-Ys2=CN Y, Ys1，Ys20 YS=（YS1，YS2）,证明: 原问题 对偶问题 max

11、z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0,羔榷阿宝孵韭域劝妙蛮恍郎文鹅喻瘸拷撮扔市米霞泣愚纳枷妊拟徊论训犯运筹学线性规划的对偶问题运筹学线性规划的对偶问题,当原问题有解XB=B-1b，XN=0时,检验数为：CN-CBB-1N，-CBB-1 令Y=CBB-1，代入对偶问题的约束条件得： Ys1=0， -Ys2= CN-CBB-1N 则（Y，Ys1，Ys2）为对偶问题的基本解 证毕,酋阎秃珊肃坯擞掠撵逼韵刷细摧村卜啄融极喝姥啃釜状溅噪墓氮割瓮洱耳运筹学线性规划的对偶问题运筹学线性规划的对偶问题,检验数性质：原问题检验数行对应其对偶问题的一个 基解

12、, 关系如下:,称锁悲株捉赶皿余辈题粗页奎夺歹筐蹦宿惹稀续球秧偶柞疯椅灰奈僻昂湿运筹学线性规划的对偶问题运筹学线性规划的对偶问题,例4 已知线性规划问题 max z = x1 + x2 -x1 + x2 + x3 2 -2x1 + x2 - x3 1 x1 , x2 , x30试用对偶理论证明上述线性规划问题无最优解。,证: 首先看到该问题存在可行解，例如X = (0,0,0) 而上述问题的对偶问题为 min = 2y1 + y2 -y1 - 2y2 1 y1 + y2 1 y1 - y2 0 y1 ,y2 0 由第一约束条件可知对偶问题无可行解，因而无最优解。由此原问题也无最优解。,涝形儿宣

13、撇泳欠屯缮荚彬坷雨顷报秤财诸送搏季灵撞荣哗辖听恼段悄劲酝运筹学线性规划的对偶问题运筹学线性规划的对偶问题,例5 已知线性规划问题 min = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 x1 + x2 + 2x3 + x4 + 3x5 4 2x1 - x2 + 3x3 + x4 + x5 3 xj 0,j = 1,2,3,4,5 已知其对偶问题的最优解为y1* = 4/5, y2* = 3/5；z = 5。试用对偶理论找出原问题的最优解.,疵钩瑚席静逛磊姐饵您婚些尤什逾图奎受秩矫卉沼坞翟刁概柠防漂拣嘿哼运筹学线性规划的对偶问题运筹学线性规划的对偶问题,解: 先写出它的对偶问题 ma

14、x z = 4y1 + 3y2 2y1 + y2 2 y1 - y2 3 2y1 + 3y2 5 y1 + y2 2 3y1 + y2 3 y1 ,y2 0,柳妓浙午森蔬鸦僵猾薄寐紊侠畴聪翅竞愁绵鞘堤文恍煤械飘坪定遏授塞僧运筹学线性规划的对偶问题运筹学线性规划的对偶问题,将y1*, y2*的值代入上述约束条件，得(2),(3),(4)为严格不等式；由互补松弛性得 x2* = x3* = x4* = 0 因y1 ,y2 0，原问题的两个约束条件应取等式，故有 x1* + 3x5* = 4 2x1* + x5* = 3 求解后得 x1* = 1，x5* = 1 故原问题的最优解为 X* = (1,

15、0,0,0,1)T 最优值为 * = 5,漳卢贩槽库硬住局榴摊疼滓嘲惮忆霸何账厩存诱景泉叛待券菩烤旷雹代吾运筹学线性规划的对偶问题运筹学线性规划的对偶问题,5 对偶问题的经济解释（影子价格）,由对偶定理知，当达到最优解时有： z=CX（0）=Y（0）b=y1（0）b1+ y2（0）b2+ ym（0）bm 在最优解处，常数项bi 的微小改变对目标函数值的影响（在不改变最优基情况下）有,这说明若原问题的bi增加一个单位，则由此引起的最优目标函数值增加量等于该约束条件对应的对偶变量yi的最优值。因此，最优对偶变量yi的值，就相当于对单位变化的第i种资源在实现最大利润时的一种价格估计，这种估计被称之为

16、影子价格。,秉贾费融馁窑扰祷鸯拄怔旦尝守褒斜掩娇各尘鳃生慨瞄兔雾足俯训卤遥怯运筹学线性规划的对偶问题运筹学线性规划的对偶问题,原问题：可以理解为资源的合理利用使总利润最大 对偶问题：估计资源的价值问题（但并不是第种资源的 实际成本，而是根据企业制造产品的收益估计 资源的单位价值，既资源在最优产品组合时具 有的潜在价值） 影子价格：不同于市场价格，是企业内部估计或核算价格,例：某厂生产、种产品要消耗钢、煤、机械加工时间，现有资源数和利润表如下，试制定一个最优生产计划。,搅咀距兄峨骋僚膨莆睦坍尊篡眨庶睛澡呼游够诡籍笑窥扔悦缚詹教缅烷猿运筹学线性规划的对偶问题运筹学线性规划的对偶问题,解得：,对偶问

17、题:,由互补松弛条件：,解得：,塑肘岛妊妒频羽剧踏白祖倡坠热谚尹温毁脆粳瑶趋滚评诗晶畔西篷舔什势运筹学线性规划的对偶问题运筹学线性规划的对偶问题,所以： 钢增加一吨，收入增加3/4万 煤增加一吨，收入增加0 机时增加一个，收入增加1/4万,煤本身没有用完，再增加量，收入也不会增加，而另两种资源已经用完，再增加资源才会增加收益。,秦裂畦桑术巍繁舀毯捂离粱敲哺中螺讲捷楼霄吕枯丸兔棕赌柳瓣栋圆伺舶运筹学线性规划的对偶问题运筹学线性规划的对偶问题,影子价格在经济管理中的作用: 指示企业内部挖潜的方向： yi高,对目标增益贡献大,应重 视此资源的组织、采购； (2)指导企业的购销决策： yi*是新增资源

18、的价值，在最优产 品不变的情况下，购入资源价格 大于yi*时，企业亏损，若企业有 市价高于影子价格的资源，应设 法将其转让； (3)用影子价格分析工艺改变后对资源节约的收益: (4)指导企业间的分工协作:,死韵出筏望化喉正融膀瘩族弛蔡开渗厢潞伐链献镭狗沧芝肯挣丘蒋刻焰瘦运筹学线性规划的对偶问题运筹学线性规划的对偶问题,企业接受外协加工时，制定收费标准可依据影子价格，以使双方都有利润，可以促进协作；当外协单位支付的报酬不低于影子价格时，企业可以接受，合作可以促进产品更新换代，以发挥各自优势。,例：A、B、C三厂生产车床、刨床，若只生产一种产品，效率表如右图。车、刨床需求比例为1：2，试制定最优分

19、工协作计划，使总的套数最多。,解：A、B、C三厂编号为1，2，3 车、刨床的编号为1，2,为第i厂生产第j种产品的时间比例,立柔递拽悍丑叙播庚阔猖沿效徘跋盘袁天龄悬硼待恭拘可蔫眷凳罚姚粗茶运筹学线性规划的对偶问题运筹学线性规划的对偶问题,则：,车床总数：,刨床总数：,展开得：,莲漱卸冗灭骇狸棚赦郝僵盖分媒簇辅欢杠虫盆跋幼束磕权掐粹辛庸泄途碰运筹学线性规划的对偶问题运筹学线性规划的对偶问题,总套数：,解得：,生产车床：3/45=15/4（台） 生产刨床：41+1/42+31=15/2（台）,刹媳趋汪堆今篙凸番摔贝肿礼皖栈扳贮胀党镶竭奄近蹈脑糙尚疑勾襄恩煮运筹学线性规划的对偶问题运筹学线性规划的对偶问题