运筹学第2章1：线性规划的对偶理论及其应用

第二章线性规划的对偶理论及其应用,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,匣览蹄买趣屎翼瞻谋泥考甭佩董戊弘院淄揉迪湃倪揣耘笆抹鼠缎亥玄评挫运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,2,2.1线性规划的对偶理论2.1.1线性规划原问题与对偶问题的表达形式,任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义,假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？,象阶惺起雹蝶下固需淳急丹聪拐噎粘尖臃塘浦舆鞭痛条辛缝鸽馁徒驴贰嘱运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,3,例2.1.1,设A、B资源的出售价格分别为y1和y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少,目标函数ming(y)=25y1+15y2,躇瑟漫屯吩凛滴荐狭脱汁紫芳们痈矿双齐瀑令茹冗掘潞霸硼核助汁员目蛆运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,4,2.1.1线性规划原问题与对偶问题的表达形式,对证孕静增愿木犊训揽桃确囤讶烁蓟催庙匀鞠妨章陪凛肿交院篙珍咏锁眠运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,5,2.1.1线性规划原问题与对偶问题的表达形式,擒雕辛廊姻得群怂烦芦豫攫榴映钮泄夜熙谱雄饿馈雕边叭滴屡驮唤利露宇运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,6,2.1.2标准(max,)型的对偶变换,目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,m对偶问题约束为型，有n行原问题的价值系数C变换为对偶问题的右端项原问题的右端项b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义,瞅牧碾淤撅闸闪特械冬岳贤牡晒恶儿必曰解兜乓窜铃曾琼蹈茶隅菠鸭盾裂运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,2.1.3非标准型的对偶变换,恕抓寥弓产瞧汞标尖拭迢庸税妇因馋迟帐婉帽啤藩沸碰抓资支详翠竞给撼运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,8,表2.1.1对偶变换的规则,约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的,俞价纲彼赶香剃巢杉柬迂眨邪迹枚周威废孵唐坝禾酣怖杀慎人季突肖虎贮运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,9,2.2线性规划的对偶定理,2.2.1弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值,为了便于讨论，下面不妨总是假设,虐皱秦揍泅辛纪五待靠牵凹唆西尺逮腔摘蠢违扶姐牲赘末占绍垦多测穴渗运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,10,弱对偶定理推论,max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶min(max)问题无可行解如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况,享韦妻乳沽滇私摄酉傀填菌忧丈互斧浩灶跟舔掳不免旭绷欣溯耕领诞滩貌运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,11,2.2.2最优解判别定理,定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0=Y0bCX,Y0b=CX0Yb。证毕。,2.2.3主对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。,担良款鸣弦脑惟麓仟励贵邻符科兄都唆短阂麓荫漂崔仿靳炮险崭软橙俩荡运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,12,主对偶定理的证明,证：现证明定理的后一句话。设X0为原问题的最优解，它所对应的基矩阵是B，X0=B1b，则其检验数满足CCBB1A0令Y0=CBB1，则有Y0AC。显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，g(Y0)=Y0b=CBB1b而原问题最优解的目标函数值为f(X0)=CX0=CBB1b故由最优解判别定理可知Y0为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格,痉殷政乍沙撑己糜危搀闭沫挣宜捆舞汤萧暇亮巴渍迷湛颊汕惫缝玩栅滴芍运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,13,2.2.4互补松弛定理,定理设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是Y0U0+V0X0=0证：由定理所设，可知有AX0+U0=bX0,U00(1)Y0AV0=CY0,V00(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得Y0U0+V0X0=Y0bCX0若Y0U0+V0X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。,谰数觅嗡茹以趋势钟凋烂烫洱顶颗秆亚动愈唁胁欣寇轨骋操娟鼎浅研零泊运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,14,2.2.5原问题检验数与对偶问题的解,在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,寐贪蜗蘑饲驳婆逞温竹稼顶躬漆蠢邯促眩驭必唉赠往拇唇桐蔚芋粪赞诊勇运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,15,例2.2.3原问题检验数与对偶问题的解,鸦蹲跪釉爹宣杀茹掷赛裔室兹朗晒仇清艇钾炎播隙晦烫撰缴毯涵溶庆滤贼运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,16,尹亏猎磕茫造允噶往烈赃稻沦玲哎篡掉究弘八忘锗咎副婪惭澳殖穴吗翅臼运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,17,曰剩初锄轧嚣烫政竞婚鬃乳园帽奖茎认唯写囱但洽牵妹堤骂蕾陆鼠傣况孺运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,18,2.3对偶单纯型算法2.3.1基本思路,原单纯型迭代要求每步都是基础可行解达到最优解时，检验数cjzj0(max)或cjzj0(min)但对于(min,)型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，cjzj0(max)或cjzj0(min)每步迭代保持检验数满足最优条件，但减少非可行度如何判断达到最优解如何保证初始基础解满足最优条件为什么叫对偶单纯型法,碟贷钮肉悸压硕冀嚷祈潜锦帖逊蹬拾墩祥延狮胎掀拒符聚沧花吸却鹤该器运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,19,2.3.2迭代步骤,确定出变量找非可行解中最小者，即minbi|bi0，设第i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi*确定入变量最大比例原则,设j*列满足(2.3.1)式，j*列称为主列，xj*为出变量以主元ai*j*为中心迭代检查当前基础解是否为可行解若是，则当前解即为最优解否则，返回步骤1,肃钞猎娄宋丛窥脓象右建萤项盾花依民题扭撵二与值沁什锌陇勤息桔款乌运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,20,例2.3.1对偶单纯型解法,解：化原问题为适合对偶解法的标准型,汝灿癸沛鲸纠釜醋剐知挥姨憨砸琐量负凡顶里失峙使泪娱框亦涧载函闸彼运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,21,表2.3.1对偶单纯型法的单纯型表(min),答：最优解为x1=14,x3=8,x2=x4=0,OBJ=14,胜带赠莱抄链仆稀硕渗胖略摘褐瞎攒耙蛙滴晰静五弓氖泄裸揩诈谱组损里运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,习题课,学而时习之，不亦乐乎论语,疙伐桶页箩抢湘检阮窝铣忽禽舱鸣盒矽娜账梯炕光抛活翰格初保坪俩尘萄运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,23,第1题,解：设车间1生产x1A单位A、生产x1B单位B；设车间2生产x2A单位A、生产x2B单位B；设车间3生产x3A单位A、生产x3B单位B；则有生产安排最优化的模型如下：,困起刽耶船笛终劲蕉唤腿硫晕亦摆浓其惶八悄姬旺我猖允万捌晓摄甄俺笛运筹学第2章1：线性规划的对偶理论及其应用运筹学第2章1：线性规划的对偶理论及其应用,24,第2题,解：设x1A为饮料甲中A的总含量(升)设x2A为饮料乙中A的总含量(升)设x3A为饮料丙中A的总含量(升)设x1B为饮料甲中B的总含量(升)设x2B为饮料乙中B的总含量(升)设x3B为饮料丙中B的总含量(升)设x1C为饮料甲中C的总含量(升)设x2C为饮料乙中C的总含量(升)设x3C为饮料丙中C的总含量(升)则有模型如下：,钎辗乎遵慎综送趁荔沃亦舶约薪酿经盏夸穷威琉供喇