运筹学第4章 单纯形法的对偶问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,第4章 单纯形法的对偶问题,1线性规划的对偶问题,2对偶规划的基本性质,3对偶单纯形法,卫虚茧沼驼肢逻鞍砌去携楞窝馁袜审封砒骑堵例褒饲牡富诫琅第元半涣笑运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,2,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。,例题1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、c台时如表所示,该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？,解：设 为产品 的计划产量， 为产品的计划产量，则有,目标函数： Max z=50 + 100,约束条件：,1 线性规划的对偶问题,冤蚤胆儒头娠渡傲坠臼斤马砌巴忻拨幅糙面钞僳北渭挛尺孝琢泰泉傅箔耘运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,3,现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、c，那么该厂的厂长应该如何来确定合理的租金呢？,设 分别为设备A、B、c的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产 产品以获利50元；同样生产一单位 产品 所需各设备的台时的总租金也不应当低于原利润100元， 即 ，否则这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型：,目标函数：,约束条件：,这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。,1 线性规划的对偶问题,蹲蚀酒腋范毋匣埠乱堪痞稠更酌膨舱踢氨筛瘁性戌娶焕兵卧捂蝎灭酌捞炭运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,4,如果我们把求目标函数最大值的线性规划问题看成原问题，则把求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。,1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。,2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。,3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于对偶问题的目标函数中的第i个变量的系数。,4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置 。,设,A=,则,1 线性规划的对偶问题,冻赚霍纱棱劲估复溯劫匆悬氧孰哄豪严乔氨舶徽郸快野申剃氮港竣慌葛粥运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,5,如果我们用矩阵形式来表示，则有原问题：,其中A是 矩阵mn，该问题有m个约束条件n个变量， , ,对偶问题：,其中 是A的转置， 是b的转置, 是c的转置, y=,现在我们用单纯形法求对偶问题的解。,1 线性规划的对偶问题,立舵碗沸潜颊跨扦毙短拔告稽啊余账翘赡森礼却氟限罐练俱宋戍惺灵伪撒运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,6,加上剩余变量 和人工变量 ，把此问题化成标准型如下：,把上述数据填入单纯形表计算。,1 线性规划的对偶问题,柜主吹栗辰翼还蛰兔寝挤潍嗅瞥宿成腔贴司糯烟膳瑞捎庙鼻曲渠仇瓷纱干运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,7,迭代变量,基变量,b,-300,-400,-250,0,0,-M,1,-M,1,0,-1,0,1,50,50/2,-250,1,1,1,0,-1,0,100,100/1,-M-250,-2M-250,-250,M,250,-M,-50M-25000,M-50,2M-150,0,-M,-250,0,2,-400,1/2,1,0,-1/2,0,1/2,25,-250,1/2,0,1,1/2,-1,-1/2,75,-325,-400,-250,75,250,-75,-28750,25,0,0,-75,-250,-M+75,3,-300,1,2,0,-1,0,1,50,-250,0,-1,1,1,-1,-1,50,-300,-350,-250,50,250,-50,-27500,0,-50,0,-50,-250,-M+50,1 线性规划的对偶问题,干浮拧丈衙疡饶名保蓑揉演虽疡藩欺钩冻奢滋亿频垫夸井口牧性亲碱订瑰运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,8,由上表，最优解： =50，,-f 的最大值为-27500，即目标函数f的最小值为f=27500元。,从上面可知租金：A设备为50元，B设备为0元，c设备为50元。这样把工,厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出,租设备的最小费用，因为这是目 标函数的最小值。,通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种,设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划,的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而,求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最,优值，因为这两个最优值相等。,1 线性规划的对偶问题,写惹附狡贝阿驰柠江忙铁歹口去奖介筐厉迭摩玄墙届蔓猜茫潜梆淬百思豺运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,9,下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。,s.t.,1 线性规划的对偶问题,叶筛肛崖仁轰侩曝遁作私烦兄猩嘱狙珍莲洞瓮沫蜡越戮瞪力缉分鄙淋掀冷运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,10,这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于等于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以 -1，使不等号方向改变即可，得,这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有,显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的,两边都乘以-1，得,1 线性规划的对偶问题,虫线臼龙友抡樱谎葱灰陆革膨插维爽题膊撵这拔冯邵盛饿藕大龟您滴锯风运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,11,通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：,s.t.,1 线性规划的对偶问题,欣汛蜘准谱凝瞪扶弗乞热梆良手侍浇既志咸钵缘逃竟施蔚豢稻镀烬梧郎瑟运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,12,这个求最大值的线性规划问题的约束条件都取小于等于号，我们马,上可以写出其对偶问题：,s.t.,1 线性规划的对偶问题,旱算卖存淄峙烫貌勺兴贰俘褐阻膛饰欺划蛆审秤杰鹃蓑弥憋瘸怨扁留跃壁运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,13,这里 和 一样都是不同的决策变量，为了表示这两个,决策变量都来源于原问题的第三个约束条件，记为 。,因为在该对偶问题中 和 的系数只相差一个符号，我们可以把,上面的对偶问题化为：,s.t.,1 线性规划的对偶问题,淹楔妨柔柱拒试认椰辑筋夷蹋大逆株匿硝众水至余鸦俏躇瓣蚌孩壬堪逛反运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,14,进一步，我们可以令 ，这时当 时， ，当,时， 。这也就是说，尽管 但 的取值可以为正，可以为0，,可以为负，即 没有非负限制。,这样我们把原规划的对偶问题化为,s.t.,没有非负限制。,对照原线性规划问题，我们可以知道：,当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非,负限制。,如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用,进行替换，这里 ， ，用类似的方法知道其对偶问题中第 i个,约束条件取等号。,1 线性规划的对偶问题,种碟五殴涟丁詹湃鳞兄滩腺玛谎寡苑多毯盾吐胯斤凸睬欲疼在藐嫌命粒傍运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,15,另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变,量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。,原线性规划问题为：,s.t.,1 线性规划的对偶问题,瑚押霉红铀符寅页腆群匣秸辐蜜佃悦颓祈离哲眺吞烈诊私赫犁迭腔吃屋尸运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,16,首先在写对偶问题之前，我们先把第二个约束条件两边乘以-1得,然后按照上面的规则，我们可以得到其对偶问题为,s.t.,1 线性规划的对偶问题,彭甘郡西正企乞缔稗诊穆筑嘿府棠姚冠在嘉萝爬热饭厘瞪努孙缺业烽雄钢运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,17,2对偶规划的基本性质,对偶规划的基本性质,1对称性。即对偶问题的对偶是原问题。,2弱对偶性。即对于原问题和对偶问题的可行解 ， 都有 。,由弱对偶性，可得出以下推论：,（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：此性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。,（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,敌声找揭肪及卧小废缀焰救足惟坚絮单贿晌羡尝耘氖两勘强渗团荡粘胃秆运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,18,2对偶规划的基本性质,3最优性。如果 是原问题的可行解， 是对偶问题的可行解，并且 ，则 和 分别为原问题和对偶问题的最优解。,4强对偶性。即若原问题及其对偶问题都有可行解，则两者都有最优解，且它们的最优解的目标函数都相等。,5互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即,若yi*0,则有,若 ，则有yi*=0,萌便函锯棠讽悬栽妓汰澄撼减娜咆绎锨营冷狈絮雀枉票计揖譬痢碉柯声东运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,19,3对偶单纯形法,对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原,有问题的所有检验数都小于等于零的情况下，通过迭代使得所有约束条件的常,数都大于等于零，最后求得最优解。,简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是,大多数线性规划问题很难找到初始解使得其所有检验数都小于等于零。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。 上节分析中已知当250b1325时第一个约束条件的对偶价格不变，现在b1=300变成b1=350，请问这时第一个约束方程的对偶价格应为多少呢？,解：求出在第二次迭代表上的常数列,拿扒踌蒂捞讲遥缕搅串淘汇罪种结锐脱吐影逞汉冤畏惮峻被癣奎尘脸炎轰运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,20,3对偶单纯形法,迭代次数,基变量,c,B,x,1,x,2,S,1,S,2,S,3,b,50 100 0 0 0,2,x,1,50,1 0 1 0 -1,100,S,2,0,0 0 -2 1 1,-50,x,2,100,0 1 0 0 1,250,z,j,50 100 50 0 50,c,j,-z,j,0 0 -50 0 -50,1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行的基变量为出基变量,彝亮猾冒嘿邮沙真惋防示板寸贺王枢安辜想迅皿狈代锦踞隆岿灿龄褂仰缆运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,21,3对偶单纯形法,4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。,迭代次数,基变量,c,B,x,1,x,2,S,1,S,2,S,3,b,50 100 0 0 0,2,x,1,50,1 0 0 1/2 -1/2,75,S,1,0,0 0 1 -1/2 -1/2,25,x,2,100,0 1 0 0 1,250,z,j,50 100 0 25 75,28750,c,j,-z,j,0 0 0 -25 -75,盏了州争谤殃魂缺滥甫吝沪瘁穴萍雷逻减聂斟托浊醇哼处刺嗣怨漳交向夸运筹学第4章 单纯形法的对偶问题运筹学第4章 单纯形法的对偶问题,