线性规划及其对偶问题幻灯片.ppt

《线性规划及其对偶问题幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划及其对偶问题幻灯片.ppt（153页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划及其对偶问题第1页，共153页，编辑于2022年，星期二1 线性规划问题及其数学模型线性规划问题及其数学模型(1)线性规划问题线性规划问题例、生产组织与计划问题例、生产组织与计划问题A,B A,B 各生产多少各生产多少,可获最大利润可获最大利润?可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 20 2单位利润单位利润40 50306024第2页，共153页，编辑于2022年，星期二解解:设产品设产品A,B产量分别为变量产量分别为变量x1，x2可以建立如下的数学模型：可以建立如下的数学模型：Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24

2、 x1，x2 0s.t目标函数目标函数约束条件约束条件可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 20 2单位利润单位利润40 50306024第3页，共153页，编辑于2022年，星期二 例 某建筑设计院设计每万办公建筑和工业厂房需要的建筑师、结构工程师、设备工程师和电气工程师的平均人数列在表。问该院应如何安排设计任务，才能使设计费收入最大?专业建筑物建筑结构设备电器设计费收入（万元/万）办公建筑532136工业厂房121220全院现有专业人数28261210解设办公建筑和工业厂房各承揽、万。根据题意max Z36x120 x2 5 x1x228 s.t 3 x12x228 2

3、x1x212 x12x210 x1、x2 0第4页，共153页，编辑于2022年，星期二 2.9m 2.9m钢筋架子钢筋架子100100个，每个需用个，每个需用 2.1m 2.1m 各各1 1，原料长，原料长7.4m7.4m 1.5m 1.5m求：如何下料，使得残余料头最少。求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；料头长度；确定决策变量；确定决策变量；根据下料目标确定目标函数；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程

4、。根据不同长度钢筋的需要量确定约束方程。例、合理下料问题例、合理下料问题第5页，共153页，编辑于2022年，星期二设按第设按第i i种方案下料的原材料为种方案下料的原材料为x xi i根根组合方案组合方案 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 合合 计计 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 长长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料料 头头 0.1m 0.3m 0.9m 0.0m

5、 1.1m 0.2m 0.8m 1.4m第6页，共153页，编辑于2022年，星期二例、运输问题例、运输问题 工工 厂厂 1 2 3 库存库存 仓仓 1 2 1 3 50 2 2 2 4 30 库库 3 3 4 2 10 需求需求 40 15 35运输单价求：求：运输费用最小的运输方案运输费用最小的运输方案。第7页，共153页，编辑于2022年，星期二解：设解：设x xijij为为i i 仓库运到仓库运到j j工厂的产品数量工厂的产品数量 其中：其中：i i 1 1，2 2，3 3 j j 1 1，2 2，3 3Min Z=2x11+x12+3x13+2x21+2x22+4x23+3x31+4

6、x32+2x33x11 +x12+x13 =50 x21+x22+x23 =30 x31+x32+x33 =10 x11 +x21+x31 =40 x12 +x22+x32 =15x13 +x23+x33 =35 xij 0s.t第8页，共153页，编辑于2022年，星期二(2)线性规划问题的特点线性规划问题的特点l决策变量：决策变量：(x x1 1 x xn n)T T 代表某一方案，代表某一方案，决策者要考虑和控制决策者要考虑和控制的因素非负；的因素非负；l目标函数：目标函数：Z=Z=(x x1 1 x xn n)为线性函数，求为线性函数，求Z Z极大或极小极大或极小;l约束条件：可用线性

7、等式或不等式表示约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为具备以上三个要素的问题就称为 线性规划问题线性规划问题。第9页，共153页，编辑于2022年，星期二目标函数约束条件(3)线性规划模型一般形式线性规划模型一般形式第10页，共153页，编辑于2022年，星期二隐含的假设隐含的假设n比例性：决策变量变化引起目标的改变量与决策变量改变量成正比例性：决策变量变化引起目标的改变量与决策变量改变量成正比比n可加性：每个决策变量对目标和约束的影响独立于其它变量可加性：每个决策变量对目标和约束的影响独立于其它变量n连续性：每个决策变量取连续值连续性：每个决策变量取连续值n确定性：

8、线性规划中的参数确定性：线性规划中的参数aij,bi,cj为确定值为确定值第11页，共153页，编辑于2022年，星期二2 线性规划问题的图解法线性规划问题的图解法定义定义1 1：满足约束：满足约束(2)(2)的的X=(X=(X X1 1 X Xn n)T T称为线性规划问题的称为线性规划问题的可行解可行解，全部可行解的集合称为全部可行解的集合称为可行域可行域。定义定义2 2：满足：满足(1)(1)的可行解称为线性规划问题的的可行解称为线性规划问题的最优解最优解。第12页，共153页，编辑于2022年，星期二例例1 Max Z=40X1+50X2 X1+2X2 303X1+2X2 60 2X2

9、 24 X1,X2 0 0s.t第13页，共153页，编辑于2022年，星期二解：解：(1)(1)、确定可行域、确定可行域 X1+2X2 30 3X1+2X2 60 2X2 24 X X1 1 0 0 X X2 2 0 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 0X2 0可行域第14页，共153页，编辑于2022年，星期二(2)(2)、求最优解、求最优解最优解：最优解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2 (0,0)，(10,-8)C点：点：X1+2X2=30 3X1+2X2=600203010

10、102030X1X2DABC最优解Z=975可行解Z=0等值线第15页，共153页，编辑于2022年，星期二例例2、Max Z=40X1+80X2 X1+2X2 303X1+2X2 60 2X2 24 X1,X2 0 0s.t第16页，共153页，编辑于2022年，星期二解：解：(1)(1)、确定可行域与上例完全相同。、确定可行域与上例完全相同。(2)(2)、求最优解、求最优解0203010102030DABC最优解Z=1200最优解：最优解：BCBC线段线段第17页，共153页，编辑于2022年，星期二最优解：最优解：BCBC线段线段B B点：点：X X(1)(1)=(6,12)C=(6,1

11、2)C点：点：X X(2)(2)=(15,7.5)=(15,7.5)X=X=X X(1)(1)+(1-+(1-)X)X(2)(2)(0 0 1 1)Max Z=1200 Max Z=1200 X1 6 15 X2 12 7.5X=+(1-)X1=6 +(1-)15X2=12+(1-)7.5X1=15-9 X2=7.5+4.5 (0 1)第18页，共153页，编辑于2022年，星期二例例3、Max Z=2X1+4X2 2X1+X2 8-2X1+X2 2X1,X2 0s.tZ=08246X240X1-2X1+X2 22X1+X2 8X1 0X20可行域可行域无界无界无有限最优解无有限最优解无有限最

12、优解可行域无上界第19页，共153页，编辑于2022年，星期二例例4、Max Z=3X1+2X2-X1-X2 1X1,X2 0无可行域无可行域无可行解无可行解-1X2-1X10s.tX2 0X1 0-X1-X2 1第20页，共153页，编辑于2022年，星期二直观结论直观结论n线性规划问题的解有四种情况线性规划问题的解有四种情况q唯一最优解唯一最优解q无穷多最优解无穷多最优解q无有限最优解无有限最优解q无可行解无可行解n若线性规划问题有解，则可行域是一个凸多边形（或凸若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；多面体）；n若线性规划问题有最优解，则若线性规划问题有最优解，则q唯一

13、最优解对应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；q无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；第21页，共153页，编辑于2022年，星期二3 单纯形法单纯形法3.1 3.1 线性规划问题的标准形式线性规划问题的标准形式3.2 3.2 线性规划问题的基本解线性规划问题的基本解3.3 3.3 单纯形法的基本思想单纯形法的基本思想第22页，共153页，编辑于2022年，星期二3.1 3.1 线性规划问题的标准形式线性规划问题的标准形式目标函数约束条件(1)线性规划模型一般形式线性规划模型一般形式第23页，共153页，编辑于2022年，星期二价值系数决策变

14、量技术系数右端常数(2)线性规划模型标准形式线性规划模型标准形式第24页，共153页，编辑于2022年，星期二价值向量决策向量系数矩阵右端向量(3)线性规划模型矩阵形式线性规划模型矩阵形式第25页，共153页，编辑于2022年，星期二对于各种非标准形式的线性规划问题，我们总可以通对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式过以下变换，将其转化为标准形式:(4)一般型向标准型的转化l目标函数目标函数l目标函数为极小化目标函数为极小化l约束条件约束条件l分两种情况：大于、小于分两种情况：大于、小于l决策变量决策变量l可能存在小于零的情况可能存在小于零的情况第26页，

15、共153页，编辑于2022年，星期二3.2 3.2 线性规划问题的基本解线性规划问题的基本解(1)解的基本概念定义定义 在线性规划问题中，约束方程组在线性规划问题中，约束方程组(2)(2)的系数矩的系数矩阵阵A(A(假定假定 )的任意一个的任意一个 阶的非奇异阶的非奇异(可逆可逆)的子方阵的子方阵B(B(即即 )，称为线性规划问题的一个，称为线性规划问题的一个基基阵阵或或基基。第27页，共153页，编辑于2022年，星期二基阵基阵非基阵非基阵基向量非基向量基变量非基变量第28页，共153页，编辑于2022年，星期二令令则则定义定义 在约束方程组在约束方程组(2)中，对于一个选中，对于一个选定的

16、基定的基B，令所有的非基变量为零得到的，令所有的非基变量为零得到的解，称为相应于基解，称为相应于基B的基本解。的基本解。第29页，共153页，编辑于2022年，星期二定义定义 在基本解中，若该基本解满足非负约束，即在基本解中，若该基本解满足非负约束，即 ，则称此基本解为，则称此基本解为基本可行解基本可行解，简称，简称基可行解基可行解；对应的；对应的基基B称为称为可行基可行基。基本解中最多有基本解中最多有m个非零分量。个非零分量。基本解的数目不超过基本解的数目不超过 个。个。第30页，共153页，编辑于2022年，星期二若若B满足下列条件，称为满足下列条件，称为最优基最优基 称为称为最优解最优解

17、第31页，共153页，编辑于2022年，星期二例例 现有线性规划问题现有线性规划问题试求其基本解、基本可行解。试求其基本解、基本可行解。第32页，共153页，编辑于2022年，星期二解解:(1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x4(2)求基本解求基本解由上式得由上式得第33页，共153页，编辑于2022年，星期二可能的基阵可能的基阵 由于所有由于所有|B|0，所，所以有以有6个基阵和个基阵和6个基个基本解。本解。第34页，共153页，编辑于2022年，星期二对于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B13为可行

18、基为可行基为基本可行解，为基本可行解，B12为可行基为可行基第35页，共153页，编辑于2022年，星期二对于基阵对于基阵令令则则对于基阵对于基阵令令则则第36页，共153页，编辑于2022年，星期二对于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B24为可行基为可行基为基本可行解，为基本可行解，B34为可行基为可行基第37页，共153页，编辑于2022年，星期二0ABCDE所以，本问题所以，本问题存在存在6个基本个基本解，其中解，其中4个个为基可行解为基可行解.第38页，共153页，编辑于2022年，星期二(2)几点结论几点结论v若线性规划问题有可行解若线性规划问

19、题有可行解,则可行域是一个凸多边形或凸多面体则可行域是一个凸多边形或凸多面体(凸集凸集),且仅有有限个顶点且仅有有限个顶点(极点极点);v线性规划问题的每一个基可行解都对应于可行域上的一个线性规划问题的每一个基可行解都对应于可行域上的一个顶点顶点(极点极点);v若线性规划问题有最优解若线性规划问题有最优解,则最优解必可在基可行解则最优解必可在基可行解(极点极点)上上达到达到;v线性规划问题的基可行解线性规划问题的基可行解(极点极点)的个数是有限的的个数是有限的,不会超过不会超过 个个.上述结论说明上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得线性规划的最优解可通过有限次运算在基

20、可行解中获得.第39页，共153页，编辑于2022年，星期二3.3 3.3 单纯形法单纯形法 (1)单纯形法的引入单纯形法的引入(2)表格单纯形法第40页，共153页，编辑于2022年，星期二 n jm+1 k 1 -CBTb*amnamjamm+1 0 am1bm*xm cm aknakjakm+1 akk ak1bk*xk ck a1na1ja1m+1 a1ka11b1*x1 c1 xn xjxm+1xm xk x1 b*XBCB cn cjcm+1cm ck c1 cj 单纯形表单纯形表ammmmaxZc1x1十c2x2十十cnxn a11x1a12x2十十a1nxnb1 a21x1a2

21、2x2十十a2nxnb2 am1x1am2x2十十amnxnbm xj0 (jl、2、，n)a1m第41页，共153页，编辑于2022年，星期二x3x5x400010 18000170/2100/3150/5maxZ10 x118x2 （1）5x12x2 x3170 s.t 2x13x2x4100 （2）x15x2x5150 xj0 （j1，2，3，4，5）主元第42页，共153页，编辑于2022年，星期二x3x400 x2100/2x3x5x400010 18000170/2150/3100181/5001/53010110（0 23/50 7/518 1/5）32/57/50111023/

22、513/502/532/500018/5550/2350/7150maxZ10 x118x2 （1）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）第43页，共153页，编辑于2022年，星期二x3x400 x2100/2x3x5x400010 18000170/2150/3100181/5001/530107/50111023/513/502/532/500018/5550/2350/7150 x3x1x201018150/7005/73/7540

23、/700123/711/7200/70101/72/7X*=(50/7,200/7,540/7,0,0)T Z*=4100/700032/76/7第44页，共153页，编辑于2022年，星期二例 某房地产公司欲开发一七通一平空地，总面积2500m2。公司原计划开发商业楼1000m2，住宅楼5250m2。请根据下列前提条件，确定其是否最佳开发方式。(1)根据规划要求：沿马路建商业房，为4层楼框架结构，其余为砖混住宅，为6层楼；容积率为2.5，建筑密度50%。(2)开发日期为2003年12月，建筑物完成时间不超过一年半。(3)根据预测，一年半以后商业楼平均造价为1400元/m2，砖混住宅平均造价为

24、950元/m2，不计土地成本。(4)预计建筑物完成后商业楼及住宅均可全部售出，商业楼出售当时的平均售价为2400元/m2，住宅楼出售当时的平均售价为1700元/m2。(5)物业出售时的税费为总额的5%。(6)公司投入资金不超过650万元。第45页，共153页，编辑于2022年，星期二分析：容积率总建筑面积/总占地面积建筑密度建筑基地总面积/总占地面积(1)总建筑面积25002.5=6250m2(2)建筑基地总面积250050%1250m2(3)商业楼每平方米的利润:(0.240.14一0.245%)=0.088(万元/m2)(4)住宅楼每平方米的利润:(0.17一0.095一0.175%)=0

25、.0665(万元/m2)第46页，共153页，编辑于2022年，星期二设商业楼建筑面积为x1m2;砖混住宅建筑面积为x2m2求x1、x2目标函数max Z=0.088 x10.0665 x2满足:x1x26250 x1/4+x2/61250 0.14 x1十0.095 x2650 x1、x20(1)总建筑面积 25002.5=6250m2(2)建筑基地总面积 250050%1250m2(3)商业楼每平方米的利润:(0.240.14一0.245%)=0.088(万元/元m2)(4)住宅楼每平方米的利润:(0.17一0.095一0.175%)=0.0665(万元/m2)第47页，共153页，编辑于

26、2022年，星期二为了便于计算，变换一下约束条件及目标函数。（由于在整个价值最优程序中只是相对的价值是重要的，而不是它们绝对值。绝对值的值只影响目标函数的最后值，但不影响设计变量的最优值）因此，我们可以将其变换为:x1/4+x2/61250 转变为3 x1十2 x215000 0.14 x1十0.095 x2650 转变为1.4737 x1十x26842max Z=0.088 x10.0665 x2 转变为max Z=Z/0.06651.323 x1x2max Z=0.088 x10.0665 x2 x1x26250 x1/4+x2/61250 0.14 x1十0.095 x2650 x1、x

27、20第48页，共153页，编辑于2022年，星期二数学模型max Z=1.323 x1+x2x1x262503 x1十2 x2150001.4737 x1十x26842x1、x20 x3x4x5000第49页，共153页，编辑于2022年，星期二max Z=1.323 x1+x2x1x262503 x1十2 x2150001.4737 x1十x26842x1、x201.32310006250/115000/36842/1.4737x11.3230146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.897

28、84643/0.6786=68421607/0.3214=5000第50页，共153页，编辑于2022年，星期二1.3230 x1146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=5000 x211500003.111402.11140125000.11141-1.4602012501-2.11140-0.754200-0.318000-1.1136最优解:x1=1250,x2=5000,x4=1250,x3=x50Z=6654即Z=0.

29、0665 Z=442.5（万）第51页，共153页，编辑于2022年，星期二n 例 某项目经理部有三种住宅可以承建。三种住宅每百平方米的利润分别为6000元、8000元和5000元。承建时主要考虑木工和瓦工工时的安排。由于现在瓦工空闲，应尽量多安排；而可支配的木工工时虽然仅有26000个，但不允许有任何空闲。三种住宅每百平方米需用的瓦工和木工工时列在表中。另外，公司要求至少安排12000瓦工工时。问三种住宅各承建多少平方米可使利润最大?解 设甲、乙、丙三种住宅各承建x1、x2平方米，根据问题的要求，可得下列线性规划模型第52页，共153页，编辑于2022年，星期二第53页，共153页，编辑于2

30、022年，星期二第54页，共153页，编辑于2022年，星期二第55页，共153页，编辑于2022年，星期二例 某工程的混凝土量总计1500m3；分三种标号C20，C25，C30，其需要量为400m3、600m3、500m3。今供应32.5#水泥250t、42.5#水泥200t、，水泥单价及用量见表。试选择合理的配制方案，使水泥费用最省。第56页，共153页，编辑于2022年，星期二设：由32.5#水泥配制的C20，C25，C30混凝土各为x1、x2、x3，由42.5#水泥配制的C20，C25，C30混凝土各为x4、x5、x6则32.5#水泥的总耗量为 253x1302x2362x342.5#

31、水泥的总耗量为 211x4257x5302x6目标函数：min z2065（253x1302x2362x3）2192（211x4257x5302x6）253x1302x2362x3 250211x4257x5302x6 200 x1x4400 x2x5600 x3x6 500 xi0解得：x148 x2600 x344 x4252 x50 x6486 z28337.416（元）第57页，共153页，编辑于2022年，星期二n案例:建设监理公司监理工程师配置问题n某建设监理公司(国家甲级)，侧重国家大中型项目的监理，仅在武汉市就正在监理七项工程，总投资均在5000万元以上。由于工程开工的时间不同

32、，多工程工期之间相互搭接，具有较长的连续性，2002年监理的工程量与2003年监理的工程量大致相同。n每项工程安排多少监理工程师进驻工地，一般是根据工程的投资，建筑规模，使用功能，施工的形象进度，施工阶段来决定的。监理工程师的配置数量是随之而变化的。由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的。有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地。第58页，共153页，编辑于2022年，星期二n因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建(结构)专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、

33、总图专业、合同和信息管理人员等，这就需要我们合理配置这些人力资源。为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度，按标准施工期和高峰施工期来划分。通常标准施工期需求的人数较容易确定。但高峰施工期比较难确定了。原因有两点:n(1)高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题。第59页，共153页，编辑于2022年，星期二n(2)各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费，这一点应该说主要是人为因素所造成的。n

34、因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围。另经统计测算得知，全年平均标准施工期占7个月，人年成本4万元;高峰施工期占5个月，人年成本7万元。第60页，共153页，编辑于2022年，星期二另外在高峰施工期各工地所需监理工程师的数量要求第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人

35、。求2003年:1高峰施工期公司最少配置多少个监理工程师?2监理工程师年耗费的总成本是多少?第61页，共153页，编辑于2022年，星期二n已知条件汇总：为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围。另经统计测算得知，全年平均标准施工期占7个月，人年成本4万元;高峰施工期占5个月，人年成本7万元。另外在高峰施工期各工地所需监理工程师的数量要求第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;

36、第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人。求2003年:1高峰施工期公司最少配置多少个监理工程师?2监理工程师年耗费的总成本是多少?第62页，共153页，编辑于2022年，星期二n设xi为第i工地最少配置监理工程师人数约束条件:第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人。x15x24x34x43x53x62x72 x1、x2、x3、

37、x4、x5、x6、x7 0 x1x214 x2x313 x3x411 x4x510 x5x69 x6x77 x7x17Minz=x1+x2+x3+x4+x5+x6+x7第63页，共153页，编辑于2022年，星期二2监理工程师年耗费的总成本(47/12+7 5/12）min（x1+x2+x3+x4+x5+x6+x7）第64页，共153页，编辑于2022年，星期二4 4 线性规划的对偶理论线性规划的对偶理论4.1 对偶问题4.2 对偶问题的基本性质4.3 影子价格4.4 对偶单纯形法第65页，共153页，编辑于2022年，星期二4.1 对偶问题(1)对偶问题的提出例例1 1、生产组织与计划问题、

38、生产组织与计划问题A,BA,B各生产多少各生产多少,可获最大利润可获最大利润?可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 20 2单位利润单位利润40 50306024第66页，共153页，编辑于2022年，星期二Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件如果因为某种原因，不愿意自己生产，而希望通过如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何将现有资源承接对外加工来获得收益，那么应如何确定各资源的确定各资源的使用价格使用价格？第67页，共

39、153页，编辑于2022年，星期二Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件两个原则两个原则1.所得不得低于生产的所得不得低于生产的获利获利2.要使对方能够接受要使对方能够接受设三种资源的使用单价分别为设三种资源的使用单价分别为 y1,y2,y3y1 y2 y3生产单位产品生产单位产品A A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A A的获利的获利生产单位产品生产单位产品B B的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品B B的获利的获利y1+3 y2 40 2y1

40、+2 y2+2y3 50 50第68页，共153页，编辑于2022年，星期二通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W=30y1+60 y2+24y3根据原则根据原则2，对方能够接受的价格显然是越低越好，因此此问题，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：可归结为以下数学模型：Min W=30y1+60 y2+24y3 y1+3y2 402y1+2 y2+2y3 50y1,y2,y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1,y2,y3 称为称为影子

41、价格影子价格第69页，共153页，编辑于2022年，星期二(2)对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题为其对偶问题，其中为其对偶问题，其中yi(i=1,2,m)称为称为对偶变量对偶变量。上述对偶问题称为上述对偶问题称为对称型对偶问题对称型对偶问题。原问题简记为原问题简记为(P)，对偶问题简记为，对偶问题简记为(D)第70页，共153页，编辑于2022年，星期二对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 Max Min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与

42、右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制第71页，共153页，编辑于2022年，星期二4.2 对偶问题的基本性质定理定理1 1 对偶问题的对偶就是原问题对偶问题的对偶就是原问题Max

43、 W=-Ybs.t.-YA-CY0Min Z=-CXs.t.-AX-bX 0Max Z=CXs.t.AX bX 0Min W=Ybs.t.YA C Y0对偶的定义对偶的定义对偶的定义对偶的定义第72页，共153页，编辑于2022年，星期二定理定理2 2(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解，则有的可行解，则有C bX，yX y证明：由证明：由AX b,y 0 有有 yAX b y 由由 Ay C,X 0 有有 y A X C X所以所以C X y A X yb第73页，共153页，编辑于2022年，星期二推论推论2、(P)有可行解有可行解,但无有限最优解，则但无有限最优解，

44、则(D)无可行解。无可行解。定理定理3、yX,分别为分别为(P),(D)的可行解，且的可行解，且X yC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明：对任证明：对任X，有，有CX b y=CXX最优最优推论推论1、(P),(D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。第74页，共153页，编辑于2022年，星期二定理定理4 4(主对偶定理主对偶定理)若一对对偶问题若一对对偶问题(P)(P)和和(D)(D)都有可行解，则它们都有最都有可行解，则它们都有最优解，且目标函数的最优值必相等。优解，且目标函数的最优值必相等。证明：证明：(1)当当X*和和Y*为原问题和对偶

45、问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。对偶问题有下界，也存在有限最优解。第75页，共153页，编辑于2022年，星期二(2)当当X*为原问题的一个最优解，为原问题的一个最优解，B为相应的最优基为相应的最优基,通过引入通过引入松弛变量松弛变量Xs,将问题将问题(P)转化为标准型转化为标准型令令令令所以所以Y*是对偶问题的可行解，是对偶问题的可行解，对偶问题的目标函数值为对偶问题的目标函数值为X*是原问题的最优解，原问是

46、原问题的最优解，原问题的目标函数值为题的目标函数值为第76页，共153页，编辑于2022年，星期二推论：推论：若一对对偶问题中的任意一个有最优解，则另一个也若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.1.都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；2.2.两个都无可行解；两个都无可行解；3.3.一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。第77页，共153页，编辑于2022年，星期二n从两图对比可明显看

47、到原问题无界，其对偶问题无可行解y1y2第78页，共153页，编辑于2022年，星期二n例4 已知线性规划问题max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。第79页，共153页，编辑于2022年，星期二n上述问题的对偶问题为min w=2y1+y2-y1-2y21y1+y21y1-y20y1，y20由第1约束条件，可知对偶问题无可行解；原问题虽然有可行解，但无最优解。第80页，共153页，编辑于2022年，星期二n例5 已知线性规划问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5

48、42x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。第81页，共153页，编辑于2022年，星期二n例5 已知线性规划问题 解：先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20第82页，共153页，编辑于2022年，星期二n例5 已知线性规划问题 将y1*=4/5,y2*=3/5的值代入约束条件，得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛性得 x2*=x3*=x4*=0。因y1，

49、y20；原问题的两个约束条件应取等式，故有 x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；w*=5第83页，共153页，编辑于2022年，星期二定理定理5 若若 X,Y分别为分别为(P),(D)的可行解，则的可行解，则X,Y为最为最优解的充要条件是优解的充要条件是同时同时成立成立证证:(:(必要性）必要性）原问题原问题 对偶问题对偶问题第84页，共153页，编辑于2022年，星期二 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问

50、题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 0第85页，共153页，编辑于2022年，星期二影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于格一定等于0 04.3 影子价格变量