线性规划—对偶单纯形学习教案

1、会计学1线性规划线性规划(xin xn u hu)对偶单纯形对偶单纯形第一页，共62页。表1. 产品(chnpn)数据表 设备设备产品产品ABCD产品利润产品利润（元件）（元件） 甲甲 21402乙乙 22043设备可利用设备可利用机时机时数（时）数（时） 1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？1. 第2页/共62页第二页，共62页。 0,124164821222.32max2121212121xxxxxxxxtsxxz反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么(n me)种机器的机时如何定价才是最佳决策？

2、第3页/共62页第三页，共62页。设A、B、C、D设备的机时价(shji)分别为y1、y2、y3、y4，则新的线性规划数学模型为： 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy第4页/共62页第四页，共62页。表2. 原问题(wnt)与新问题(wnt)对比表A（y1） B（y2） C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 第5页/共62页第五页，共62页。2. 原问题与对偶问题的对应(duyng)关系 0,124164821222.32max21212121

3、21xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原问题(wnt)（对偶问题(wnt)）对偶问题（原问题）原始规划与对偶规划是同一组数据参数,只是位置有所不同,所描述的问题实际上是同一个问题从另一种角度去描述.第6页/共62页第六页，共62页。特点：目标函数(hnsh)求极大值时，所有约束条件为号，变量非负;目标函数(hnsh)求极小值时，所有约束条件为号，变量非负. min . .0TLPZC XAXbs tX ： : max . .0TTDPWb YA YCs tY 对称形式的对偶(du u)线性

4、规划问题原始线性规划问题对偶线性规划问题第7页/共62页第七页，共62页。定理6.1 对偶(du u)线性规划的对偶(du u)问题是原始线性规划问题。min . .0TC XAXbs tX max. .0TTb YA YCs tY 对偶(du u)定义min. .0TTb YA YCs tY max . .0TC XAXbs tX 对偶(du u)定义第8页/共62页第八页，共62页。 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先将原问题(wnt)变形为 0,5 64 3 7 32532432max3213213213232

5、1xxxxxxxxxxxxxxxZ第9页/共62页第九页，共62页。 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW对对偶偶问问题题：若给出的线性规划不是对称形式，可以先化成对称形式再写对偶(du u)问题。第10页/共62页第十页，共62页。12121212212 max( )4532204310. .50 ,f xxxxxxxs txxxx 例例原原线线性性规规不不限限划划问问题题122122122122122122 max( )45532220433105. .5 ,0(max, )f xxxxxxxxxxxxxs txxxxxx

6、化化为为型型标标准准问问题题第11页/共62页第十一页，共62页。12341234123412341234min ()201055344235. .235,0h wwwwwwwwwwwwws twwwww www 应应用用对对称称形形式式对对偶偶变变换换规规则则123123123123min ( )20105344. .2350,0,g yyyyyyys tyyyyyy 不不限限1122334 ,ywywyww 令令12121212212 m ax()4532204310. .50 ,fxxxxxxxs txxxx 例例原原 线线 性性 规规不不 限限划划 问问 题题第12页/共62页第十二页

7、，共62页。原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量00=无约束无约束变变量量n个个n个个约约束束条条件件00无约束无约束=第13页/共62页第十三页，共62页。对偶问题(wnt)的形成min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w

8、=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3: unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用 表示 原始问题约束条件的性质影响对偶问题变量的性质，用 表示第14页/共62页第十四页，共62页。 无无约约束束4321432142143214321, 0, 06 43 247 23 523

9、4 532maxxxxxxxxxxxxxxxxxxxxZ解：原问题(wnt)的对偶问题(wnt)为 无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyW第15页/共62页第十五页，共62页。 min . .0TLPZC XAXbs tX ： : max . .0TTTDPWY bYACs tY 原始线性规划问题对偶线性规划问题非对称形式的对偶线性规划(xin xn u hu)问题第16页/共62页第十六页，共62页。123412341341234123max57322527260. .22430510,0,Z

10、xxxxxxxxxxxs txxxxxxx 自自由由变变量量练习(linx) 写出下面线性规划的对偶(du u)规划模型第17页/共62页第十七页，共62页。解： 先将约束条件变形(bin xng)为“”形式1234134123441234322527260224301050,0,xxxxxxxxxxxxxxxx 自自由由变变量量第18页/共62页第十八页，共62页。再根据非对称形式的对应关系，直接(zhji)写出对偶规划1234512313123124512345min2560301052213212745. .27,0fyyyyyyyyyyyyys tyyyyyyyyy 没没有有非非负负限

11、限制制第19页/共62页第十九页，共62页。 min . .0TLPZC XAXbs tX ： : max . .0TTTDPWY bYACs tY 原始线性规划问题对偶线性规划问题为了便于讨论，下面不妨总是(zn sh)以非对称形式的线性规划问题作证明.第20页/共62页第二十页，共62页。若x 0 ,y 0分别(fnbi)是(LP)与(DP)的可行解,则定理6.2 弱对偶原理(弱对偶性)：设 和 分别是问题(LP)和(DP)的可行解，则必有0X0Y0011nmTTjjiijiC XYbc xy b 即即：证明(zhngmng)：0,AXb 0TTYAC 于是(ysh)，000TTYAXC

12、X 0TYb 推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的上界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的下界。第21页/共62页第二十一页，共62页。推论2: 在一对对偶(du u)问题（LP）和（DP）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；这也是对偶(du u)问题的无界性。 min . .0TLPZC XAXbs tX ： : max . .0TTTDPWY bYACs tY 00TTC XYb 第22页/共62页第二十二页，共62页。定理6.3 最优性定理：如果 是原问题的可行解， 是其对偶问题的可行解，并且:0X0Y00: zw

13、TTC XYb 即即则 是原问题的最优解， 是其对偶问题的最优解。0X0Y设x 是(LP) 问题(wnt)的任一可行解,则证明(zhngmng)：0X于于是是，是是原原始始线线性性规规划划问问题题的的最最优优解解. .0TTC XYb 0Y类类似似可可证证，是是对对偶偶线线性性规规划划问问题题的的最最优优解解. .0TC X 第23页/共62页第二十三页，共62页。考虑(kol)如下的线性规划121231241234532430min(). .,zxxxxxLPs txxxx x x x 2 2考虑(kol)基解 (0,1,0,-2)T (不可行) 对应(duyng)的规范式为 1312313

14、412343 72 3222172220min/. ./,xxxxxs txxxx x x x 其判别数向量 (7/2,0,3/2,0)是非负的. 第24页/共62页第二十四页，共62页。判别数向量(xingling)用(LP)中的符号可以记为1TTBcc B A 则判别(pnbi)数向量为1() ,TTByc B 令TTcy A 上述的判别数向量(xingling)非负，因此有0TTcy A即.TA yc 这说明y是对偶规划的可行解.1()TTByc B 并并且且这一可行解对应的目标函数值为即为在原始线性规划中基解对应的目标函数值.1TTBy bc B b 判别数非负对偶解可行第25页/共6

15、2页第二十五页，共62页。对偶(du u)的线性规划问题的解原始规划的最优性10TTBcc BA 1()TTByc B 对偶规划的可行性.TA yc 定理(dngl)6.4 设B是问题min. .0TZc XAXbs tX 的一个基矩阵,对应(duyng)的基解满足最优性条件10TTBcc B A 则对偶线性规划问题有可行解1() ,TTByc B TTBBc XY b 且且在上述条件下,(LP)的基解的目标函数值等于(DP)的解的目标函数值.如果xB是可行解,则显然是(LP)的最优解.此时对应的y是(DP)的最优解.第26页/共62页第二十六页，共62页。定理6.5 若原始线性规划(xin

16、xn u hu)问题与对偶线性规划(xin xn u hu)问题之一有最优解,则另一个也有最优解,并且它们目标函数的最优值相等.证明: 考虑(kol)到对合性,只需选取两个规划中的任一个证明.min. .0TZc XAXbs tX 设有最优解x0,且其为基可行(kxng)解再设基矩阵为B,10TTBc xc B b x0为最优解,判别数非负,有10TTBcc B A 10() ,TTByc B 令0.则TA yc y0可行,且100TTTBy bc B bc x y0是对偶规划最优解.对偶的线性规划问题的解第27页/共62页第二十七页，共62页。定理6.6 强对偶性：若原问题(wnt)及其对偶

17、问题(wnt)均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。推论(tuln)4：（LP）与（DP）要么两者都有最优解，要么都无最优解。两个互为对偶的线性规划的解的情况(3) 一个有可行解,无最优解(目标函数无界),则 另一个无可行解.(1) 两个都有可行解, 两个都有最优解,且最 优值相等.(2) 两个都无最优解.(4) 一个有可行解，另一个无可行解，则可 行的一个目标函数无界.第28页/共62页第二十八页，共62页。3）互为对偶问题(wnt)，或者同时都有最优解，或者同时都无最优解.1）任何线性规划都存在一个对应(duyng)的对偶线性规划.2）原问题第i个约束是“”约束，

18、则对偶变量yi0.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.第29页/共62页第二十九页，共62页。7）原问题无最优解，则对偶(du u)问题无可行解.8）对偶(du u)问题不可行，原问题可能有无界解.9）原问题与对偶(du u)问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.第30页/共62页第三十页，共62页。分别求解下列(xili)2个互为对偶关系的线性规划问题 0

19、52426155.2max5214213221jxxxxxxxxxtsxxz 012526.52415min5321432321iyyyyyyyytsyyyw分别用单纯形法求解(qi ji)上述2个规划问题，得到最终单纯形表如下表：第31页/共62页第三十一页，共62页。XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/20001/41/2j XBb对偶问题的变量对偶问题的变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y3

20、1/215/2011/2-3/215/2007/23/2j 原问题(wnt)最优表对偶(du u)问题最优表第32页/共62页第三十二页，共62页。第33页/共62页第三十三页，共62页。定理6.7 互补松弛性：设X0和Y0分别是(LP) 问题和 (DP) 问题的可行(kxng)解，则它们分别是最优解的充要条件是：0000TsTsYXYX 其中(qzhng)：Xs为松弛变量、Ys为剩余变量.互补松弛条件证：由定理所设，可知有00(1)(2)sTTTSAXXbYAYc 分别以Y0T左乘(1)式，以X0右乘(2)式后，两式相减，即得000TTssYXYX 000,0TTssYXYX 由可行性及最优

21、性条件，可知有反之亦然。 证毕。第34页/共62页第三十四页，共62页。AXb TTb Yc X ()0TTA YcX()0TTA YcX(1)0,1,(2),01,TjjjTjjjxy pcjny pcxjn 若若则则若若则则，定理6.7* 互补松弛(sn ch)性：设X0和Y0分别是(LP) 问题和 (DP) 问题的可行解，则它们分别是最优解的充要条件是：互补(h b)松弛条件可写为：第35页/共62页第三十五页，共62页。s00TTsYXYX 由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y*0，则Xs必为0；若X*0，则Ys必为0利用上述(shngsh)关系，

22、建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。第36页/共62页第三十六页，共62页。 3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最优解是X*=(6,2,0)T,求其对偶(du u)问题的最优解Y*。解：写出原问题的对偶问题，即 0,1422321610min2121212121yyyyyyyyyyw 0,1422321610min5432152142132121yyyyyyyyyyyyyyyyw标准化第37页/共62页第三十七页，共62页。00 ssXYXY即：0),)(,(0),)(,(5421321543 TTxxyy

23、xxxyyy因为x10，x20，所以对偶问题的第一(dy)、二个约束的松弛变量等于零，即y30，y40，带入方程中： 422322121yyyy解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y*=(1,1)，最优值w=26。第38页/共62页第三十八页，共62页。 无约束无约束321321321321, 0, 06422minxxxxxxxxxxxxz的对偶(du u)问题的最优解为Y*=(0,-2)，求原问题的最优解。解: 对偶问题是 021264max2121212121yyyyyyyyyyw无无约约，标准化 0, 0,21264max43212142132121yyyyyy

24、yyyyyyyyw无无约约第39页/共62页第三十九页，共62页。0),)(,(0),)(,(5421321543 TTxxyyxxxyyy将Y*带入由方程(fngchng)可知，y3y50，y41。y2=-20 x50又y4=10 x20将x2，x5分别带入原问题约束方程中，得： 643131xxxx解方程组得：x1=-5,x3=-1, 所以原问题的最优解为X*=(-5,0,-1)，最优值 z=-12第40页/共62页第四十页，共62页。三、单纯形方法(fngf)对偶单纯形法 用单纯形方法求解线性规划时, x的可行性是满足的,但是最优性条件不满足，即w不可行. 迭代是使最优性条件逐步得到(d

25、 do)满足,（检验数非负），即使w逐步可行的过程。 构造另一种方法,最优性条件(tiojin)始终满足,即y可行,而x不可行. 逐步迭代使x最终可行,从而是最优解. 对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。而不是求解对偶问题的单纯形法。第41页/共62页第四十一页，共62页。判别(pnbi)数向量非负1()TTByc B 为对偶规划的可行解单纯形方法(fngf)保证(bozhng)解可行最优性条件不满足(有负判别数)对偶规划解不可行最优性条件满足(判别数非负)对偶规划解可行形方法对偶单纯划解可行保证对偶规解不可行解可行两种

26、方法都始终保证()0TTA Y c X 所以只要x,y都可行,必然最优第42页/共62页第四十二页，共62页。 找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过(tnggu)变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理6.4可得最优解。第43页/共62页第四十三页，共62页。找出一个(y )DP的可行基LP是否(sh fu)可行（XB 0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束第44页/共62页第四十四页，共62页。1. 最优解的判别(pnbi)已知线性规划问题(wnt)

27、的基矩阵B及它对应的基解,10BxB b 若若则所得的基解为最优解.并且此基解的所有判别数非负.2. 确定出(离)基变量111iimin0()lB bB bB b 令令 ( () )| |( () )则以xl为离基变量若xl所在行的所有系数alj0 (j=1,2,n), 则线性规划问题无可行解.(此时若有可行解1122ln0)lllnba xa xa x 第45页/共62页第四十五页，共62页。3.确定(qudng)进基变量设目标函数(hnsh)的形式为已确定离基变量为xl,设进基变量为xk.在目标函数中,用xk替换xl ，0jjj Tffx lljjlkklj Tj kba xa xx 0(

28、)ljlkkjkjlj Tlklklkj kabffxxaaa （）+ +1()klljjlj Tlkj kxba xxa 得第46页/共62页第四十六页，共62页。0()ljlkkjkjlj Tlklklkj kabffxxaaa （）+ +3.确定(qudng)进基变量0(1)0, (2),klkljjklkaaajT jk 由(1)式，0lka 0 (2)lja 若若， 式式恒恒成成立立；0lja 若若，max|0jkljlkljaaa 令令则xk为进基变量(binling)最大比例原则为保持(boch)判别数非负，有第47页/共62页第四十七页，共62页。例 2.6. 用对偶(du u

29、)单纯形法求解：1234123124min128161224222430(1.2.3 4)jZxxxxxxxxxxxj ，引入松弛(sn ch)变量得到标准型线性规划123412351246min1281612242. .22430(1.2.34,5,6)jZxxxxxxxxs txxxxxj ，解：第48页/共62页第四十八页，共62页。123412351246min1281612242. .2243Zxxxxxxxxstxxxx 构造对偶单纯形表选取(xunq)离基变量63min|0jjbbb 选取(xunq)进基变量46466m0ax|jjjaaa 第49页/共62页第四十九页，共62页

30、。第50页/共62页第五十页，共62页。基解已可行(kxng),最优解为x*=(0,3/2,1/8,0) T最优值为z*=14第51页/共62页第五十一页，共62页。例2.7 用对偶(du u)单纯形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解: 将模型(mxng)化为标准型。第52页/共62页第五十二页，共62页。1231234123512361 6min9121522 1023 12 5 140Zxxxxxxxxxxxxxxxx cj91215000cBxBbx1x2x3x4x5x60 x4-10-2-2-11

31、000 x5-12-2-3-10100 x6-14-1-1-5001(9/-1，12/-1， 15/-5)91215000ij 第53页/共62页第五十三页，共62页。cj91215000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5 -14/5001-1/515x314/51/51/5100-1/5(-30/9,-45/14,-15/1)690003ij 第54页/共62页第五十四页，共62页。cj91215000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/1412x223/79/14100-5/141/14(-3/9,-45/9,-33/1