线性规划及其对偶问题学习教案

1、会计学1第一页，共152页。解: 设产品A, B产量分别为变量x1， x2可以建立(jinl)如下的数学模型：Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标(mbio)函数约束条件可用资源煤劳动力仓库A B1 23 20 2单位利润40 50306024第1页/共152页第二页，共152页。专业建筑物建筑结构设备电器设计费收入（万元/万 ）办公建筑532136工业厂房121220全院现有专业人数28261210解设办公建筑和工业(gngy)厂房各承揽、万。根据题意max Z36x120 x2 5 x1x228 s

2、.t 3 x12x228 2 x1x212 x12x210 x1 、x2 0第2页/共152页第三页，共152页。 2.9m钢筋架子100个，每个需用 2.1m 各1，原料长7.4m 1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案； 计算出每个方案可得到的不同长度钢筋的数量及残余料头长度； 确定决策变量； 根据下料目标确定目标函数； 根据不同长度钢筋的需要量确定约束方程。例、合理(hl)下料问题第3页/共152页第四页，共152页。设按第i种方案(fng n)下料的原材料为xi根8 , 7 , 6 , 5 , 4 , 3 , 2 , 110043203010000230

3、2010000002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini为大于零的整数，组合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0 1.5m 1 0 1 3 0 2 3 4 合 计 6.3m 6.1m 6.5m 7.4m 6.3m 6.2m 6.6m 6.0m 料 长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4

4、m 料 头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m第4页/共152页第五页，共152页。例、运输(ynsh)问题 工 厂 1 2 3 库存 仓 1 2 1 3 50 2 2 2 4 30 库 3 3 4 2 10 需求 40 15 35运输单价求：运输费用(fi yong)最小的运输方案。第5页/共152页第六页，共152页。解：设xij为i 仓库运到j工厂(gngchng)的产品数量 其中：i 1，2，3 j 1，2，3Min Z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+

5、 x13 = 50 x21 + x22+ x23 = 30 x31 + x32+ x33 = 10 x11 + x21+ x31 = 40 x12 + x22+ x32 = 15x13 + x23+ x33 = 35 xij 0s.t第6页/共152页第七页，共152页。(2) 线性规划(xin xn u hu)问题的特点l决策变量： (x1 xn)T 代表某一方案， 决策者要考虑和控制的因素非负；l目标函数：Z=(x1 xn) 为线性函数，求Z极大或极小;l约束条件：可用线性等式或不等式表示.l具备以上三个要素的问题(wnt)就称为 线性规划问题(wnt)。第7页/共152页第八页，共152

6、页。0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标(mbio)函数约束条件(3) 线性规划模型一般(ybn)形式第8页/共152页第九页，共152页。第9页/共152页第十页，共152页。 20,.1XbAXtsCXZMinMax定义1：满足约束(2)的X=(X1 Xn)T称为线性规划(xin xn u hu)问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为(chn wi)线性规划问题的最优解。第10页/共152页第十一页，共152页。例1 Max Z

7、=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第11页/共152页第十二页，共152页。解：(1)、确定(qudng)可行域 X1+2X2 30 3X1+2X2 60 2X2 24 X1 0 X2 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 0X2 0可行(kxng)域第12页/共152页第十三页，共152页。(2)、求最优解最优解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C点： X1+2X2 =30 3X1

8、+2X2 =600203010102030X1X2DABC最优解Z=975可行(kxng)解Z=0等值线第13页/共152页第十四页，共152页。例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第14页/共152页第十五页，共152页。解：(1)、确定(qudng)可行域与上例完全相同。 (2)、求最优解0203010102030DABC最优解Z=1200最优解：BC线段(xindun)第15页/共152页第十六页，共152页。最优解：BC线段(xindun)B点：X(1)=(6,12) C点：X(2)=(15,7.5)X

9、=X(1)+(1-)X(2) (0 1) Max Z=1200 X1 6 15 X2 12 7.5X= = +(1- )X1 =6 +(1- )15X2=12+(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)第16页/共152页第十七页，共152页。例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.tZ=08246X240X1-2X1+X2 22X1+X2 8X1 0X20可行(kxng)域无界无有限(yuxin)最优解无有限(yuxin)最优解可行域无上界第17页/共152页第十八页，共152页。例4、 Max Z=3X1+2X2

10、 -X1 -X2 1X1 , X2 0无可行(kxng)域无可行(kxng)解-1X2-1X10s.tX2 0X1 0-X1 -X2 1第18页/共152页第十九页，共152页。第19页/共152页第二十页，共152页。第20页/共152页第二十一页，共152页。0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标(mbio)函数约束条件(1) 线性规划模型一般(ybn)形式第21页/共152页第二十二页，共152页。价值(jizh)系数决策(juc)变量技术(jsh)系数右端常数

11、0,b,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0,.21221122222121112121112211(2) 线性规划模型标准形式第22页/共152页第二十三页，共152页。0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21价值(jizh)向量决策(juc)向量系数(xsh)矩阵mbbbb21右端向量(3) 线性规划模型矩阵形式第23页/共152页第二十四页，共152页。对于各种非标准形式的线性规划问题，我们总可以(ky)通过以下变换，将其转化为标准形式:(4)

12、 一般(ybn)型向标准型的转化l目标函数l目标函数为极小化l约束条件l分两种情况：大于、小于l决策变量(binling)l可能存在小于零的情况第24页/共152页第二十五页，共152页。 302.1XbAXtsCXZMax(1) 解的基本概念定义(dngy) 在线性规划问题中，约束方程组(2)的系数矩阵A(假定 )的任意一个 阶的非奇异(可逆)的子方阵B(即 )，称为线性规划问题的一个基阵或基。mm0Bnm 第25页/共152页第二十六页，共152页。mnmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaA212122212222211211111211mmmmmmaaaa

13、aaaaaB212222111211mnmmmmnmmnmmaaaaaaaaaN212221212111基阵非基阵TmBxxxX21TnmmNxxxX21基向量非基向量基变量(binling)非基变量(binling)第26页/共152页第二十七页，共152页。NBANBXXXbAX bXXNBNBbNXBXNBNBNXbBXNBNXBbBX11NBXXXNNXNXBbBX11令0NX则01bBX定义 在约束方程组(2) 中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应(xingyng)于基B的基本解。第27页/共152页第二十八页，共152页。定义 在基本解中，若该基本解满足非

14、负约束，即 ，则称此基本解为基本可行解，简称基可行解；对应(duyng)的基B称为可行基。01bBXB基本(jbn)解中最多有m个非零分量。基本解的数目(shm)不超过 个。!mnmnCmn第28页/共152页第二十九页，共152页。NBNBNNNBNNBBNBNBXNBCCbBCXCNXBbBCXCXCXXCCCXZ)()(),(111101bBXB01NBCCBNNBX若B满足(mnz)下列条件，称为最优基 称为最优解第29页/共152页第三十页，共152页。例 现有线性规划(xin xn u hu)问题0,24261553.221212121xxxxxxtsxxZMax试求其基本(jbn

15、)解、基本(jbn)可行解。第30页/共152页第三十一页，共152页。解: (1)首先(shuxin)将原问题转化为标准型 引入松弛变量x3和x40,2402615053.243214321432121xxxxxxxxxxxxtsxxZMax(2) 求基本(jbn)解由上式得10260153A2415b第31页/共152页第三十二页，共152页。可能(knng)的基阵10260153A265312B061313B160314B021523B120524B100134B612121234!24! 2! 424C 由于所有|B| 0，所以(suy)有6个基阵和6个基本解。第32页/共152页第三

16、十三页，共152页。242615532121xxxx对于(duy)基阵265312B令03x04x则TX0043415246153131xxx对于(duy)基阵令02x04x则TX0304061313B为基本(jbn)可行解，B13为可行基为基本可行解，B12为可行基第33页/共152页第三十四页，共152页。246153411xxx对于(duy)基阵令02x03x则TX6005242155232xxx对于(duy)基阵令01x04x则TX045120160314B021523B第34页/共152页第三十五页，共152页。242155422xxx对于(duy)基阵令01x03x则TX18030

17、241543xx对于(duy)基阵令01x02x则TX241500120524B100134B为基本(jbn)可行解，B24为可行基为基本可行解，B34为可行基第35页/共152页第三十六页，共152页。0ABCDETX0043415TX0304TX6005TX241500TX18030TX045120所以，本问题(wnt)存在6个基本解，其中4个为基可行解.第36页/共152页第三十七页，共152页。(2) 几点结论(jiln)v若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点(jdin);v线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点

18、(jdin);v若线性规划问题有最优解,则最优解必可在基可行解(极点(jdin)上达到;v线性规划问题的基可行解(极点(jdin)的个数是有限的,不会超过 个.mnC上述(shngsh)结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.第37页/共152页第三十八页，共152页。 (1) 单纯形法的引入(2)表格(biog)单纯形法第38页/共152页第三十九页，共152页。 n jm+1 k 1 - CBTb*amnamjamm+1 0 am1bm* xm cm aknakjakm+1 akk ak1bk* xk ck a1na1ja1m+1 a1ka11b1* x1 c1 xn

19、xjxm+1xm xk x1 b*XBCB cn cjcm+1cm ck c1 cj 单纯形表ammmmaxZc1x1十c2x2十十cnxn a11x1a12x2十十a1nxnb1 a21x1a22x2十十a2nxnb2 am1x1am2x2十十amnxnbm xj0 (jl、2、，n)a1m第39页/共152页第四十页，共152页。miijijacc110) 102050(10118)503020(1820)000010(03kjkab*Cj1018000CBXBbx1x2x3x4x5170521001002301015015001x3x5x400010 18000170/2100/3150

20、/5maxZ10 x118x2 （1） 5x12x2 x3170 s.t 2x13x2x4100 （2） x15x2x5150 xj0 （j1，2，3，4，5） 主元第40页/共152页第四十一页，共152页。x3x400 x2100/2Cj1018000CBXBbx1x2x3x4x5170521001002301015015001x3x5x400010 18000170/2150/3100181/5001/53010110（0 23/ 50 7/518 1/5）32/57/50111023/513/502/532/500018/5550/2350/7150maxZ10 x118x2 （1）

21、5x12x2 x3170 s.t 2x13x2x4100 （2） x15x2x5150 xj0 （j1，2，3，4，5） 218 （0 00 018 1） 010100（30 3）7/52（1/5 3）第41页/共152页第四十二页，共152页。x3x400 x2100/2Cj1018000CBXBbx1x2x3x4x5170521001002301015015001x3x5x400010 18000170/2150/3100181/5001/530107/50111023/513/502/532/500018/5550/2350/7150 x3x1x201018150/7005/73/754

22、0/700123/711/7200/70101/72/7X*=(50/7, 200/7, 540/7, 0, 0)T Z*=4100/700032/76/7第42页/共152页第四十三页，共152页。第43页/共152页第四十四页，共152页。元/m2)(4)住宅楼每平方米的利润:(0.17一0.095一0.175%)=0.0665(万元/m2)第44页/共152页第四十五页，共152页。 (1)总建筑面积 25002.5=6250m2(2)建筑基地(jd)总面积 250050%1250m2(3)商业楼每平方米的利润: (0.240.14一0.245%)=0.088(万元/元m2)(4)住宅楼

23、每平方米的利润:(0.17一0.095一0.175%)=0.0665(万元/m2)第45页/共152页第四十六页，共152页。max Z=0.088 x10.0665 x2 x1x26250 x1/4+x2/61250 0.14 x1十0.095 x2650 x1、x20第46页/共152页第四十七页，共152页。Cj1.3231000CBXBbx1x2x3x4x5625011100150003201068421.43710011.3231000 x3x4x5000第47页/共152页第四十八页，共152页。max Z= 1.323 x1+x2x1x262503 x1十2 x2150001.4

24、737 x1十x26842x1、x20Cj1.3231000CBXBbx1x2x3x4x50 x36250111000 x415000320100 x568421.43710011.32310006250/115000/36842/1.47370 x30 x4x11.3230146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=5000第48页/共152页第四十九页，共152页。1.32300 x30 x4x1146430.6786000.6

25、78610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=50000 x41.323x1x211500003.111402.11140125000.11141-1.4602012501-2.11140-0.754200-0.318000-1.1136最优解:x1=1250, x2=5000, x4=1250, x3= x50Z=6654即Z=0.0665 Z=442.5（万）第49页/共152页第五十页，共152页。甲住宅乙住宅丙住宅可动用的总工时瓦工工时20001000150

26、0至少 12000木工工时10004000300026000 解 设甲、乙、丙三种住宅各承建x1、x2平方米，根据问题的要求，可得下列(xili)线性规划模型第50页/共152页第五十一页，共152页。第51页/共152页第五十二页，共152页。第52页/共152页第五十三页，共152页。第53页/共152页第五十四页，共152页。例 某工程的混凝土量总计1500m3；分三种标号C20，C25，C30，其需要量为400m3、600m3 、500m3。今供应32.5#水泥(shun)250t、 42.5#水泥(shun)200t、，水泥(shun)单价及用量见表。试选择合理的配制方案，使水泥(s

27、hun)费用最省。混凝土标号单位混凝土的水泥用量（kg/m3）水泥标号C20C25C30水泥单价（元/t）水泥限量（t）32.5#253302362206525042.5#2112573022192200混凝土用量（m3）400600500第54页/共152页第五十五页，共152页。目标(mbio)函数：min z2065（ 253x1302x2362x3 ） 2192（ 211x4257x5302x6 ）253x1302x2362x3 250211x4257x5302x6 200 x1x4400 x2x5600 x3x6 500 xi0解得： x148 x2600 x344 x4252 x5

28、0 x6486 z28337.416（元）混 凝 土 标 号单 位 混 凝 土 的 水 泥 用 量 （ kg/m3）水 泥 标 号C20C25C30水 泥 单 价（ 元 /t）水 泥 限 量（ t）32.5#253302362206525042.5#2112573022192200混 凝 土 用 量 （ m3）400600500第55页/共152页第五十六页，共152页。第56页/共152页第五十七页，共152页。第57页/共152页第五十八页，共152页。标准施工期所需监理工程师如下表:工程(工地)1234567所需最少监理师人数5443322第58页/共152页第五十九页，共152页。另外

29、在高峰(gofng)施工期各工地所需监理工程师的数量要求第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人。求2003年:1高峰(gofng)施工期公司最少配置多少个监理工程师?2监理工程师年耗费的总成本是多少?第59页/共152页第六十页，共152页。标准施工期所需监理工程师如下表:工程(工地)1234567所需最少监理师人数5443322第60页/共152页第六十一页，共152页。标准施工期所需监

30、理工程师如下表:工程(工地)1234567所需最少监理师人数5443322第1和第2工地的总人数(rn sh)不少于14人;第2和第3工地的总人数(rn sh)不少于13人;第3和第4工地的总人数(rn sh)不少于11人;第4和第5工地的总人数(rn sh)不少于10人;第5和第6工地的总人数(rn sh)不少于9人;第6和第7工地的总人数(rn sh)不少于7人; 第7和第1工地的总人数(rn sh)不少于14人。x15x24x34x43x53x62x72 x1、x2、x3、x4、x5、x6、 x7 0 x1x214 x2x313 x3x411 x4x510 x5x69 x6x77 x7x

31、17Minz= x1+ x2 +x3+ x4+ x5 + x6 + x7第61页/共152页第六十二页，共152页。第62页/共152页第六十三页，共152页。第63页/共152页第六十四页，共152页。(1) 对偶(du u)问题的提出例1、生产(shngchn)组织与计划问题A, B各生产多少, 可获最大利润?可用资源煤劳动力仓库A B1 23 20 2单位利润40 50306024第64页/共152页第六十五页，共152页。Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标(mbio)函数约束条件如果因为某种原

32、因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定(qudng)各资源的使用价格？第65页/共152页第六十六页，共152页。Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标函数约束条件两个(lin )原则1.所得不得低于生产的获利2.要使对方能够(nnggu)接受设三种资源(zyun)的使用单价分别为 y1 , y2 , y3y1 y2 y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1 +3 y2 40 2y1 + 2 y2

33、+ 2y3 50第66页/共152页第六十七页，共152页。通过(tnggu)使用所有资源对外加工所获得的收益W = 30y1 + 60 y2 + 24y3根据原则(yunz)2 ，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t目标(mbio)函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1 , y2 , y3 称为影子价格第67页/共152页第六十八页，共152页。(2) 对偶(du u)问题的形式njxbxax

34、axabxaxaxabxaxaxatsxcxcxcZMaxjmnmnmmnnnnnn, 2 , 10.221122222121112121112211定义 设原线性规划问题(wnt)为 则称下列线性规划问题(wnt)miycyayayacyayayacyayayatsybybybWMininmmnnnmmmmmm, 2 , 10.221122222112112211112211为其对偶问题，其中(qzhng)yi (i=1,2,m) 称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)第68页/共152页第六十九页，共152页。对偶关系(gun x)对应表 原

35、问题 对偶问题目标函数类型 Max Min目标函数系数 目标函数系数 右边项系数与右边项的对应(duyng)关系 右边项系数 目标函数系数变量数与约束数 变量数n 约束数 n的对应(duyng)关系 约束数m 变量数m原问题变量类型与 0 对偶问题约束类型 变量 0 约束 的对应(duyng)关系 无限制 原问题约束类型与 0 对偶问题变量类型 约束 变量 0 的对应(duyng)关系 无限制第69页/共152页第七十页，共152页。定理1 对偶问题(wnt)的对偶就是原问题(wnt)Max W=-Ybs.t. -YA-CY0Min Z=-CXs.t. -AX-bX 0Max Z=CXs.t.

36、 AX bX 0Min W=Ybs.t. YA C Y0对偶的定义对偶的定义第70页/共152页第七十一页，共152页。定理(dngl)2 (弱对偶定理(dngl)分别(fnbi)为(P), (D)的可行解，则有C bX， yX y证明：由AX b, y0 有 yAX b y 由 Ay C, X 0 有 y A X C X所以(suy)C X y A X yb第71页/共152页第七十二页，共152页。推论(tuln)2、(P)有可行解, 但无有限最优解，则(D)无可行解。定理3、 yX,分别为(P), (D)的可行解，且X yC=b, 则它们是(P), (D) 的最优解。证明：对任X，有CX

37、b y =CXX最优推论(tuln)1、(P), (D)都有可行解，则必都有最优解。第72页/共152页第七十三页，共152页。定理(dngl)4(主对偶定理(dngl)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明(zhngmng)：(1) 当X*和Y*为原问题和对偶问题的一个(y )可行解有bAX *CAY*bYAXY*CXAXYbYAXYCX*原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。第73页/共152页第七十四页，共152页。(2) 当X*为原问题的一个最优解，B为相应

38、的最优基,通过引入松弛变量(binling)Xs,将问题(P)转化为标准型0,.0sssXXbIXAXtsXCXZMax令sXXX*00111BCABCCIABCCBBB0011ABCCBCBB01BCB令01BCYB0AYCCAY所以Y*是对偶问题的可行(kxng)解，对偶问题的目标函数值为bBCbYWB1X*是原问题的最优解，原问题的目标(mbio)函数值为bBCCXZB1WZ第74页/共152页第七十五页，共152页。推论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数(hnsh)最优值相等。一对对偶问题的关系(gun x)，有且仅有下列三种：都有最优解，且目标函数最

39、优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。第75页/共152页第七十六页，共152页。n从两图对比(dub)可明显看到原问题无界，其对偶问题无可行解y1y20112212121y,yyyyy0242212121x ,xxxxx第76页/共152页第七十七页，共152页。n例4 已知线性规划(xin xn u hu)问题max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶(du u)理论证明上述线性规划问题无最优解。第77页/共152页第七十八页，共152页。n上述问题(wnt)的对偶问题(wnt)为min w=2y1+y2-y1-2y21

40、y1+ y21y1- y20y1，y20由第1约束条件，可知对偶问题(wnt)无可行解；原问题(wnt)虽然有可行解，但无最优解。第78页/共152页第七十九页，共152页。n例5 已知线性规划(xin xn u hu)问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题(wnt)的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题(wnt)的最优解 。第79页/共152页第八十页，共152页。n例5 已知线性规划问题(wnt)n 解：先写出它的对偶问题(wnt)m

41、ax z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20第80页/共152页第八十一页，共152页。n例5 已知线性规划(xin xn u hu)问题n 将y1* =4/5,y2* =3/5的值代入约束条件，得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛(sn ch)性得 x2*=x3*=x4*=0。因y1，y20；原问题的两个约束条件应取等式，故有 x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；w*=5第81页/共152页第八十二页

42、，共152页。定理(dngl)5 若 X , Y分别为(P) , (D)的可行解，则X , Y为最优解的充要条件是00XCYAAXbY同时(tngsh)成立证: (必要性）原问题(wnt) 对偶问题(wnt)0,.ssXXbXAXtsCXZMax0,.ssYYcYYAtsYbWMinbXAXsCYYAsAXbXsCYAYsYbYXYAXsCXXYYAXs0XYYXss第82页/共152页第八十三页，共152页。 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶(du u)问题的变量 对偶(du u)问题的松弛变量 原始问题(wnt)的变量 原

43、始问题(wnt)的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定(ydng)等于0第83页/共152页第八十四页，共152页。影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划(jhu)下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzyiooimmiiybybybybWZ2211mmiiiybybbybybZZ)(2211iiybZ4.3 影子(yng zi)价格变量yi*的经济意义(yy)是在其他条件不变的情况下，单位资源变化所引起

44、的目标函的最优值的变化。第84页/共152页第八十五页，共152页。n第1章中例1的影价格及其经济(jngj)解释。n 由表1-5可知cj23000 CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。 第85页/共152页第八十六页，共152页。n第1章中例1的影价格(jig)及其经济解释。n 这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。 从

45、图2-1可看到，设备增加一台时，代表该约束条件的直线由移至，相应的最优解由(4，2)变为(4，2.5)，目标函数z=24+32.5=15.5，即比原来(yunli)的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由移至，相应的最优解从(4，2)变为(4.25，1.875)，目标函数z=4.25+31.875=14.125。比原来(yunli)的增加0.125。原材料B增加1kg时，该约束方程的直线由移至，这时的最优解不变。第86页/共152页第八十七页，共152页。n第1章中例1的影价格(jig)及其经济解释。n 第87页/共152页第八十八页，共152页。nyi*的值代表对第i种

46、资源(zyun)的估价影子价格。n 这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济(sh chn jn j)的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。第88页/共152页第八十九页，共152页。第89页/共152

47、页第九十页，共152页。的影子价格与当时的市场价格进行比较。1）当i种资源的影子价格高于市场价格时，则企业可以买进该种资源；2）当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润。3）随着资源的买进和卖出，它的影子价格也将发生变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。所以我们说影子价格又是一种机会成本，它在决定企业的经常策略中起着十分重要的作用。第90页/共152页第九十一页，共152页。 m aijyii=1 表示生产(shngchn)第j种产品所消耗的各项资源的影子价格的总和，它可以称为第j种产品的隐含成本， 检验(ji

48、nyn)数j 称作是第j种产品的相对价值系数。 mj = cj CBB-1Pj = cj aijyi (j= 1,2,n). i=1由于（3）影子价格在新产品开发决策中的应用企业在新产品投产之前，可以用影子价格，通过分析产品使用资源的经济效果，以决定新产品是否应该投产。0，产品B所能提供的单件利润大于其隐含成本，产品值得投产第91页/共152页第九十二页，共152页。 产品单件消耗资源 A B影子价格钢材煤机时1 22 13 4032/76/7单件利润（万元） 10 18 例MaxZ = 10 x1 + 18x2; x1 + 2x2 170; 2x1 + x2 100;s.t. 31 + 4x

49、2 150; x1 、x2 0. mA= CA aijyi i=1=10 (10 + 232/7 3 6/7 ) = 12/7 0;解说明产品A所能提供的单件利润小于其隐含成本，相对价值(jizh)系数A0. i=1说明产品(chnpn)B所能提供的单件利润大于其隐含成本，相对价值系数B0，故产品(chnpn)B值得投产。 产 品单 件 消 耗资 源 A B影 子 价 格钢 材煤机 时1 22 13 4032/76/7单 件 利 润（ 万 元 ） 10 18 第93页/共152页第九十四页，共152页。 Y*= CBB-1 =（0，15，18） =（0， 57/ 7 ， 9 /7 ）由于y3*

50、= -9 /7 0，说明现有的解不是最优解，还须继续迭代求新的最优解。而y2*= 57/7比原来(yunli)增大了，说明第二种资源更紧缺了。 C 10 18 0 0 0CBXBb x1 x2 x3 x4 x501018x3x1x2540/750/7200/7 0 0 1 -23/7 11/7 1 0 0 5/7 -3/7 0 1 0 -1/7 2/7Z-4100/7 0 0 0 -32/7 -6/7 1 -23/7 11/7 0 5/7 -3/7 0 -1/7 2/7n maxZ = 10 x1 + 18x2 ; x1 + 2x2 +x3=170; 2x1+x2 +x4= 100;s.t.

51、3x1 + 4x2 +x5= 150; x1 ,x2 0;第94页/共152页第九十五页，共152页。n maxZ = 10 x1 + 18x2 ; 5x1 + 2x2 +x3=170; 2x1 - 3x2 +x4= 100;s.t. x1 + 5x2 +x5= 150; x1 ,x2 0;第95页/共152页第九十六页，共152页。 设备有效台时（每月）ABC8102251310810300400420单位产品利润（千元）322.9第96页/共152页第九十七页，共152页。第97页/共152页第九十八页，共152页。第98页/共152页第九十九页，共152页。154135z4/15(千元/

52、台时)18（千元）/60（台时）=0.34/15，故借用(jiyng)B设备并不合算借用(jiyng)别的工厂的设备B，每月可借用(jiyng)60台时，借金1.8万元则借用设备的租金为:第99页/共152页第一百页，共152页。故生产(shngchn)产品在经济上不合算第100页/共152页第一百零一页，共152页。所以生产(shngchn)产品V在经济上合算由单纯性表知:第101页/共152页第一百零二页，共152页。故线性规划(xin xn u hu)最优解X*=（ 107/4,31/2,0,0,0,0，55/4)T目标函数最优值Z*=136.9625第102页/共152页第一百零三页，

53、共152页。对偶单纯形法的基本(jbn)思想v从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。v如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步(zhb)变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。4.4 对偶(du u)单纯形法第103

54、页/共152页第一百零四页，共152页。n前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。n通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。n根据对偶问题的对称性，可以(ky)这样考虑：若保持对偶问题的解是基可行解，即cjCBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。 第104页/共152页第一百零五页，共15

55、2页。n设原问题为 max z=CX AX=b X0n 又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应(duyng)的变量为 XB=(x1，x2，,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是n (1) 对应(duyng)基变量x1，x2，,xm的检验数是ni=ci zi=ci CBB-1Pj=0，i=1,2,mn (2) 对应(duyng)非基变量xm+1，xn的检验数是nj=cj zj=cj CBB-1Pj0，j=m+1,n第105页/共

56、152页第一百零六页，共152页。n每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换(binhun)，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。第106页/共152页第一百零七页，共152页。n对偶单纯形法的计算步骤如下：n (1) 根据线性规划问题，列出初始(ch sh)单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。n (2) 确定换出变量。按min(B-1b)i(B-1b)i0(B-1b

57、)l对应的基变量xi为换出变量n (3) 确定换入变量。在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。若存在lj0 (j=1,2,，n), 计算 min0jjkkljjljlkczczaaa第107页/共152页第一百零八页，共152页。n对偶单纯形法的计算步骤如下：n 按规则所对应的列的非基变量xk为换入变量，这样才能(cinng)保持得到的对偶问题解仍为可行解。n (4) 以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。n 重复步骤(1)(4)。第108页/共152页第一百零九页，共152页。n例6 用对偶(du u)单纯

58、形法求解min w=2x1+3x2+4x3x1+2x2+x332x1x2+3x34x1，x2，x30 解：先将此问题化成下列形式，以便得到(d do)对偶问题的初始可行基 max z= 2x1 3x2 4x3 x1 2x2 x3+x4 = 32x1+x2 3x3 +x5= 4xj0，j=1,2,5第109页/共152页第一百一十页，共152页。n例6的初始(ch sh)单纯形表，见表2-6。cj -2 -3 -4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 -3 -4 -1 -2 -2 1 -1 -3 1 0 0 1 cj-zj -2 -3 -4 0 0 从表2-

59、6看到，检验数行对应的对偶问题的解是可行解。因b列数字(shz)为负，故需进行迭代运算。 第110页/共152页第一百一十一页，共152页。n换出变量的确定：n换入变量的确定：按上述(shngsh)对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。按上述对偶单纯形法计算(j sun)步骤(2)，即按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量。计算(j sun)min( 3, 4)= 4故x5为换出变量。 12234,22min故x1为换入变量。换入、换出变量的所在列、行的交叉处“2”

60、为主元素。按单纯形法计算步骤进行迭代，得表2-7。第111页/共152页第一百一十二页，共152页。cj -2 -3 -4 0 0 CB XB b x1 x2 x3 x4 x5 0 -2 x4 x1 -1 2 0 1 -5/2 -1/2 1/2 3/2 1 0 -1/2 -1/2 cj-zj 0 -4 -1 0 1 由表 2-7 看出，对偶问题仍是可行解，而 b 列中仍有负分量。 故重复上述迭代步骤，得表 2-8。 第112页/共152页第一百一十三页，共152页。表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应(duyng)两个约束