运筹学第1章素材课件

《运筹学第1章素材课件》由会员分享，可在线阅读，更多相关《运筹学第1章素材课件（86页珍藏版）》请在装配图网上搜索。

1、运筹学运筹学主讲人：朱建明主讲人：朱建明 2014 年 9 月应用数学系应用数学系第第 1章章 线性规划线性规划线性规划的数学模型及其标准型 1线性规划问题的解和单纯形法2单纯形的基本理论（自学）3对偶问题和对偶单纯形法4灵敏度分析 5第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型一、线性规划应用举例(Liner Programming)（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？产产 品品资资 源源甲甲乙乙资源限制资源限制A AB BC C1 12

2、20 01 11 11 1300300400400250250单位利润单位利润5050100100第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型例例1 1的线性规划模型：的线性规划模型：决策变量：x1、x2分别代表甲、乙两种产品的生产 数量目标函数：max z=50 x1+100 x2约束条件：s.t.x1+x2300 2x1+x2400 不等式约束 x2 250 x1，x20 非负约束一、线性规划应用举例第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型一、线性规划应用举例(Liner Programming)例2（营养搭配问题）如果有甲、乙、丙、

3、丁四种食品，单价各不相同，都含有不同成份的维生素，其含量和单价如下表所示：若要保证每人每天维生素的最低需要量，则应如何搭配各种食品，使花的钱最少？维生素维生素甲甲乙乙丙丙丁丁每人每天需要量每人每天需要量一一二二三三100010000.60.617.517.5150015000.270.277.57.5175017500.680.680 0325032500.30.33030400040001 13030单价单价0.80.80.50.50.90.91.51.5第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型一、线性规划应用举例例3 靠近某河流有两个化工厂，流经第一化工厂的河

4、流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小。第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型一、线性规划应用举例解：解：决策变量决策变量：x x1 1、x x2 2分别代表工厂分别代表工厂1 1和工厂和工厂2

5、 2处理污水处理污水 的数量的数量(万万m m3 3)目标函数：目标函数：min min z z=1000=1000 x x1 1+800+800 x x2 2约束条件：约束条件：第一段河流（工厂1工厂2之间）：(2x1)/500 0.002第二段河流：0.8(2x1)+(1.4-x2)/7000.002此外有：x12 x21.4第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型一、线性规划应用举例例例2 2的线性规划模型：的线性规划模型：min z=1000 x1+800 x2 s.t.x1 1 0.8x1+x2 1.6 x1 2 x21.4 x1，x20 第一节第一节

6、线性规划的数学模型及其标准型线性规划的数学模型及其标准型 线性规划的数学模型的一般形式：max(min)z=c1x1+c2x2+cnxn 目标函数a11x1+a12x2+a1nxn=(,)b1a21x1+a22x2+a2nxn=(,)b2 约束条件am1x1+am2x2+amnxn=(,)bm x1，x2，xn0 模型特点：目标函数(Objective function)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型二、线性规划的标准型 LP标准型：max z=c1x1+c2x2+cnxn 目标函

7、数 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 约束条件 am1x1+am2x2+amnxn=bm x1，x2，xn0 特点：1.Zmax 2.约束条件为等号 3.变量非负 4.右端常数项大于等于零第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型二、线性规划的标准型.max z=CXs tAX=bX0111212122212.nnmmmnaaaaaaAaaa1(,.,)nCcc12.mbbbb12.nxxXxLP标准型的矩阵形式：第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型三、化非标准型为标准型1、若 mi

8、n z=CTX此时可令：z=f，则 min z max-f 这样处理所得最优解不变举例：min z=x1x2 s.t.2x1+x2=2 x1+x2=1 x1，x20、第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型三、化非标准型为标准型2、若约束条件为“”时，aijxjbi aijxj+xn+i=bi xn+i 松弛变量(slack variable)3、若约束条件为“”时，aijxj bi aijxj xn+i=bi xn+i 剩余变量(surplus variable）举例：max z=x1+10 x2 s.t.x1+2x2100 x1+x250 x1，x20第一节第

9、一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型三、化非标准型为标准型4 4、若xk为无限制，则令xk=x+kx-k，其中x+kx-k05、若 bi 0举例:化下列线性规划为标准型 min z=2x1+2x24x s.t.x1+3x23x3-3 x1+2x24x380 x1、x20，x3无限制第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型 本节作业 1-4 1-10（1）第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例例1 1的线性规划模型：的线性规划模型：决策变量：x1、x2分别代表甲、乙两种产品的生

10、产 数量目标函数：max z=50 x1+100 x2约束条件：s.t.x1+x2300 2x1+x2400 x2 250 x1，x20 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）1、基本概念 可行解(Feasible Solution)任一满足约束条件的一组决策变量的数值；可行域(Feasible Region)所有可行解组成的集合，也称为可行解集；目标函数等值线(Objective functionline)位于同一直线上的点，具有相同的目标函数值；2、图解法步骤(Procedure)（1）画出线性规划问题的可行域；（2）画出两条目

11、标函数等值线；（3）平行移动目标函数等值线，使目标函数在可 行域范围内达到最优。第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例1 max Z=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2250 x1、x20 x2x1z*=27500BOACDz2=14000 x1+x23002x1+x2400 x2250该问题有唯一最优解该问题有唯一最优解x x1 1=50=50；x x2 2=250=250z1=50 x1+100 x2=0第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解

12、法（两个决策变量）例2 max Z=50 x1+50 x2 s.t.x1+x2300 2x1+x2400 x2250 x1、x20 x2x1z1=50 x1+50 x2=0BOACDx1+x23002x1+x2400 x2250z*=27500z2=15000B B点和点和C C点所代表的坐标点所代表的坐标同时为最优解，即该问同时为最优解，即该问题有题有无穷多最优解无穷多最优解第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例3 max z=x1+x2 s.t.x1x2 1 x1+2x20 x1、x20 问题有无界解 例4 min z=x1+

13、x2 s.t.x1x2 1 x1+2x20 x1、x20 有唯一最优解111z=32z=5OA2x1xx1x2 1x1+2x20第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例5 max z=x1+x2 s.t.x1+2x21 x1+x22 x1、x20 问题无可行解 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）LP解的情况1、无可行解（LP不可行）可行域为空集2、问题有无界解（LP无界）3、唯一最优解4、无穷多最优解第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一

14、、线性规划图解法（两个决策变量）直观结论1、可行域可以是个凸多边形，可能无界，也可能为空。2、若线性规划问题的最优解存在，则它一定可以在可行域的某一个顶点上得到。3、若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解。4、若可行域非空有界，则一定有最优解。第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法例6（切割损失问题）假定某个造纸厂接到三份订购卷纸的定单，其长和宽的要求如下表所示：该厂生产1米和2米两种标准宽度的卷纸。假定纸的长度无限制，即可以连接起来达到所需要的长度。问：应如何切割才能使切割损失的面积最小？定单号码宽（米）长

15、（米）一二三0.50.70.9100030002000第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法解：设xij是第i种标准纸按照第j种方式的切割长度。如下表:设s1,s2,s3分别是把标准纸切成0.5米，0.7米，0.9米后的剩余长度。宽度1米宽卷纸X11 X12 X13 2米宽卷纸X21 X22 X23 X24 X25 X26 需求0.50.70.9 2 0 0 0 1 0 0 0 12 2 1 0 00 1 0 2 1 00 0 1 0 1 2100030002000剩余宽度 0 0.3 0.10 0.3 0.1 0.1 0.4 0.2第二节第二节 线性规

16、划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 LP模型：Min z=0.3 X12+0.1X13+0.3X22+0.1X23+0.1X24+0.4X25+0.2X26+0.5s1+0.7s2 +0.9 s3 S.t.2 X11+4 X21+2 X22+2 X23+X24-s1=1000 X12+X12+2 X24+X25-s2 =3000 X13+X23+X25+2X26-s3 =2000 Xij0,si 0,对一切i和j第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法例7（产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一产品，每件产品包括4个

17、A零件和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别是100千克和200千克。每个生产班的原材料需要量和零件产量见下表：问：这三个车间各应开多少班，才能使这种产品的配套数达到最大？车间每班进料数（千克）每班产量（个数）原料1原料2 零件A零件B甲乙丙853698768594第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 LP的一般形式：max(min)z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=(,)b1a21x1+a22x2+a2nxn=(,)b2 am1x1+am2x2+amnxn=(,)bm x1，x

18、2，xn0 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1，x2，xn0 特点：1.Zmax 2.约束条件为等号 3.变量非负 4.右端常数项大于等于零将LP的一般形式变成LP的标准型第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 单纯形法求解LP的整体思路无穷多可行解无穷多可行解有限多可行解有限多可行解一个最优解一个最优解基本定理基本定理迭代迭代第二节第二节

19、 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 基本定理以下我们总假设LP有最优解。定理 1 LP的可行域是一个凸集（凸多面体）凸集（凸多面体）。定理 2 LP的可行域的一个点是极点极点当且仅当是它是一个 基本可行解基本可行解。定理 3 LP的最优解可在一个基本可行解（极点）上取到。定理 4 LP的基本可行解的个数是有限的。第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 举例：找出下列LP所有的基及其对应的基本解 max z=6x1+4x2 2x1+3x2100 4x1+2x2120 x1、x20解：化为标准型 max z=6x1+4x2+0

20、 x3+0 x4 2x1+3x2+x3 =100 4x1+2x2 +x4 =120 x1、x2，x3，x4 0第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 基基基本解基本解可行否可行否 目标值目标值对应图对应图中的点中的点B1=(P1，P2)B2=(P1，P3)B3=(P1，P4)B4=(P2，P3)B5=(P2，P4)B6=(P3，P4)X1=(20，20，0，0)TX2=(30，0，40，0)TX3=(50，0，0，80)TX4=(0，60，80，0)TX5=(0，100/3，0，160/3)TX6=(0，0，100，120)T 200180400/30BCDEAOA

21、BCDEOx1x22x1+3x2=1004x1+2x2 =120第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 单纯形法求LP的一般步骤步骤1：将LP化为标准型步骤2：选定一个初始基本可行解（人工变量法）步骤3：迭代到另外一个基本可行解，使得目标 函数值有所改进（检验数计算）步骤4：重复步骤3，直到目标函数值不再改进时 算法停止（所有检验数大于等于零）第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法解下列线性规划问题:12231241251252515.62245,0Max zxxxxs txxxxxxxxx基基解解345xxxz1

22、2345xxxxx例8第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 例8(续）24231242451252183351521.46641166,0M axzxxxxs txxxxxxxxx基基解解12345xxxxxz315xxx02/301/300510012/601/6004/601/61第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 例8（续）45345145245125111824251515422117.422133422,0M axzxxxxxs txxxxxxxxx基基解解12345xxxxxz312xxx0001/41/20015/41

23、5/21001/41/20101/43/218215/27/23/2第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 单纯形表格求LP的一般步骤基基解解11mmnxxxxz1mnxx100mcc11111001mmmmaaaa01mbb2 2、最优性检验 若表中所有 ,则已得最优解,算法停止。若存在检验数 ,则若 ,则原问题无解,算法停;否则转3。0jz 0jz 0jp 1、初始表格第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 单纯形表格求LP的一般步骤(1)确定进基变量 在所有负的检验数中,找出负的最大的一个,对应的变量即为进 基变量,记为 。(2)确

24、定出基变量令 则 为出基变量,为旋转元 (3)在“基”这一列中,用进基变量替换出基变量.(4)用初等行变换,将旋转元变成1,旋转元所在列其余元素换成0。同样用初等行变换将检验数中相应的元素变为0。kxmin|0ilikiklkbbaaalxlka 4、重复2,3,直到计算结束。3、列出新单纯形表第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 例9（练习）解下列线性规划问题：12312313121233252430.324604420,0Max zxxxxxxs txxxxxxx第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法（人工变

25、量法）例10 解下列线性规划问题（大M法）：1212121212433.43623,0Min zxxxxs txxxxxx12121231241234433.43623,0Max zxxxxstxxxxxxx xx x 标准化：第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 加入人工变量:基基 4 1 0 0 M M 3 1 0 0 1 0 4 3-1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxxz564xxx12561251236124123456433.43623,0Max zxxMxMxxxxs txxxxxxxxxxxxx 例10（续）第二

26、节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（续）0-(1+5M)/3 M(4-7M)/3 0 0 -4-2M 1 1/3 00 1/3 0 05/3-1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2z164xxx基基解解4-7M 1-4M M 0 0 0-9M 3 1 0 0 1 0 4 3-1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxx564xxxz第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（续）0 0 0 1/5 -7/5+M M -18/5 1 0 0-1/5 2/5 0 0 1 0 3

27、/5 -1/5 0 0 0 1 1 1 -1 3/5 6/5 0z123xxx基基解解 0 0 -1/5 0 -8/5+M 1/5+M -18/5 1 0 1/5 03/5 -1/5 0 1-3/5 0 -4/5 3/5 0 0 1 1 1 -1 3/5 6/5 0123456xxxxxx124xxxz*(3/5,6/5)TX*18/5z 最优解：最优值：第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法（人工变量法）两阶段法两阶段法 第一阶段第一阶段:添加人工变量后添加人工变量后,引入一个辅助问题引入一个辅助问题.保留原约束条件保留原约束条件,目标函目标函数改为数

28、改为 ,这里这里 为人工变量为人工变量.求这个辅助求这个辅助问题的解问题的解.考察下列情况考察下列情况:(i)(i)辅助问题有最优解辅助问题有最优解 ,表明原问题有可行解表明原问题有可行解,辅助问辅助问题的最优解即为原问题的一个可行解。题的最优解即为原问题的一个可行解。(ii)(ii)辅助问题有最优解辅助问题有最优解 ,表明原问题无可行解表明原问题无可行解,即可即可行域为空集。行域为空集。第二阶段第二阶段:去除人工变量去除人工变量,还原目标函数还原目标函数,继续求解。继续求解。12minhwrrr*0w ir*0w 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法

29、（人工变量法）例10 解下列线性规划问题（两阶段法法）：1212121212433.43623,0Min zxxxxs txxxxxx第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（两阶段法续）第一阶段：基基 0 0 0 0 1 1 0 3 1 0 0 1 0 4 3-1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxxw564xxx56125123612412345633.43623,0Min wxxxxxs txxxxxxxxxxxxx第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（两阶段法续）第一阶段：0 -5/3

30、 1 07/3 0 -2 1 1/3 00 1/3 0 05/3-1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2w164xxx基基解解 -7 -4 1 0 0 0-9 3 1 0 0 1 0 4 3-1 0 0 1 1 2 0 1 0 0 3 6 3123456xxxxxx564xxxw第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（两阶段法续）第一阶段：基基解解 0 0 0 0 1 1 0 1 01/5 03/5 -1/5 0 1-3/50-4/5 3/5 0 0 1 1 1 -1 3/5 6/5 0123456xxxxxx124xxxw基基 解

31、解 4 1 0 0 0 1 01/5 0 0 1-3/50 0 0 1 1 3/5 6/5 01234xxxxz124xxx 第二阶段,换上原目标函数,并删去人工变量：第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（两阶段法续）第二阶段：基基 解解 0 0 0 1/5 -18/5 1 0 0-1/5 0 1 0 3/5 0 0 1 0 3/5 6/5 01234xxxxz123xxx基基 解解 0 0 -1/5 0 -18/5 1 01/5 0 0 1-3/50 0 0 1 1 3/5 6/5 01234xxxxz124xxx第二节第二节 线性规划问题的解和单纯形法线

32、性规划问题的解和单纯形法 几种特殊情况1、退化解当最优解中有基变量取值为0时,就称为退化解。2、无界解 当进基变量所对应的列向量小于等于0时,则有无界解。3、多重解(无穷多个解)在最优表中,有非基变量对应的检验数为0,则有多重解(无穷多个最优解)。4、无解(无可行解)线性规划添加人工变量后,若人工变量仍留在最优基中,则原规划问题无可行解。本节作业 1-15 1-19（2）1-22（1）1-26 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法一、对偶问题的提出（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产

33、甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？产产 品品资资 源源甲甲乙乙资源限制资源限制A AB BC C1 12 20 01 11 11 1300300400400250250单位利润单位利润5050100100第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法一、对偶问题的提出 例例1 1的的LPLP模型：模型：设 x1、x2分别代表甲、乙两种产品的生产数量 max z=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2 25 x1，x20 同样是上述问题，提问同样是上述问题，提问：企业不安排生产

34、，而转让 三种资源，应如何给三种资源定价？第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法一、对偶问题的提出设 y1、y2、y3分别代表A、B、C三种资源的价格（最低转让净收入），则LP模型为：min w=300y1+400y2+250y3 s.t.y1+2y2 50 y1+y2+y3 100 y1、y2、y3 0例1（续）第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法一、对偶问题的提出 问题B:min w=300y1+400y2+250y3 s.t.y1+2y2 50 y1+y2+y3 100 y1、y2、y3 0 称问题B为问题A的对偶问题对偶问题，问题A为原问题原问

35、题。问题A:max z=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2250 x1、x20第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的定义1 1221112111121max.,0nnnmmmnnmnzc xc xc xaaaxbstaaaxbxx11221121111121min.,0mmmnnmnmnmwb yb yb yaaaycstaaaycyy原问题：原问题：对偶问题：对偶问题：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的定义原问题：原问题：对偶问题：对偶问题：max.0z CXstAXbXmin.

36、0wYbstYACY性质：对偶问题的对偶问题即为原问题。矩阵形式：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的定义对偶关系表原问题原问题（或对偶问题）（或对偶问题）对偶问题对偶问题（或原问题）（或原问题）目标函数目标函数max zmin w目标函数目标函数变量变量n个个00无约束无约束n个个=约束条件约束条件约束条件约束条件m个个=m个个00无约束无约束变量变量约束条件右端常数项约束条件右端常数项目标函数变量系数目标函数变量系数目标函数变量系数目标函数变量系数约束条件右端常数项约束条件右端常数项第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的

37、定义例2 写出下列线性规划问题的对偶问题 max z=2x1+2x24x3 s.t.x1+3x2+3x3 30 4x1+2x2+4x380 x1、x2，x30解：其对偶问题为：min w=30y1+80y2s.t.y1 +4y2 2 3y1 +2y2 2 3y1 +4y2 4 y1、y20第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的定义例3 写出下列线性规划问题的对偶问题 min z=2x1+8x24x3 s.t.x1+3x2 3x3 30 x1+5x2+4x3=80 4x1+2x24x3 50 x10、x20，x3无限制max w=30y1+80 y2+50y3

38、s.t.y1y2+4y3 2 3y1+5y2+2y3 8 3y1+4y24y3=4 y10，y2无限制，y30对偶问题为：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理max.0z CXstAXbXmax.(,),0BBNNIIBNIBNIz C XC XC XXstB N IXbXX XX考虑如下线性规划问题：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理单纯形表的矩阵形式 基基 解解z基基解解 zBXNXIXBCNCICIXBNI0bBXNXIX01BNC B N C1BIC BC1BC B bBXI1B N1B1B b初始表：迭代后

39、表：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理1111min.00 0BBBBNBIw C B bstC B B CC B N CC BC构造如下线性规划问题：min.BNIw YbstYB CYN CYC令 （单纯形乘子，对偶问题的最优解）1BYC B第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理对偶关系示意图非最优非最优可行可行.最优最优最优最优可行不可行不可行不可行.1BC B b原问题对偶问题第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理基本定理XYCXYbXYCXYbXY定理1（弱对偶性）若 是原

40、问题的可行解，是对偶问题的可行解，则有 。定理2（最优性）设 、分别为原问题和对偶问题的可行解。若 ，则 、分别为原问题和对偶问题的最优解。定理3（强对偶性）若原问题和对偶问题均有可行解，则两者都有最优解，且最优值相等。第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法三、对偶单纯形法1212121212min2.3 3436 23 ,0zxxstxxxxxxx x例4 用对偶单纯形法求如下线性规划：*123/5,6/5xx最优解：最优值：*12/5z 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法三、对偶单纯形法 对偶单纯形法的基本步骤 1、将约束条件化成小于等于约束，列

41、出初始单纯形表。2、确定出基变量。选右端向量 中，负的最大的基变量（若 ，则已得最优解）记为 。3、确定进基变量。若第 行系数 ，则原问题无解。反之，令 即为进基变量，为旋转元。4、用初等行变换，得到一个新的基，重复以上步骤直到最优。sXrXmax|0jsrjjrjrszzaaarsab0br0rja 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法四、对偶问题的经济意义 max z=50 x1+100 x2 min w=300y1+400y2+250y3 s.t.x1+x2300 s.t.y1+2y2 50 2x1+x2400 y1+y2+y3100 x2250 y1、y2、y3

42、0 x1、x20例1（续）最优解：*1250,250 xx最优解：*12350,0,50yyy影子价格：约束条件右端项增加一个单位，目标函数值的增加量（即为对偶问题的最优解）本节作业 1-38（2）（3）1-48 1-42 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法第第 五节五节 灵敏度分析灵敏度分析一、引例某企业利用甲、乙两种原料，生产A、B、C三种产品，每种的产品单位利润及原材料消耗定额等数据如下表，问如何安排生产计划使企业利润最大？产产 品品原料原料ABC供应量供应量甲甲乙乙1 12 20 02 21 11 130308080单位利润单位利润4 43 32 2第第 五节五

43、节 灵敏度分析灵敏度分析一、引例例例1 1的的LPLP模型：模型：设x1、x2、x3分别代表A、B、C三种产品的生产数量，则max z=4x1+3x2+2x3 max z=4x1+3x2+2x3s.t.x1+x330 s.t.x1+x3+s1=30 2x1+2x2+x380 2x1+2x2+x3 +s2=80 x1，x20 x1，x2,s1，s20第第 五节五节 灵敏度分析灵敏度分析一、引例初始单纯形表：初始单纯形表：基基解解12312xxxssz12ss4320 01 0 1 1 02 2 1 0 103080基基解解12312xxxssz12xx001/21 3/21 0 1 1 00 1

44、1/21 1/21503010最优单纯形表：最优单纯形表：第第 五节五节 灵敏度分析灵敏度分析二、灵敏度分析的概念 1、什么是灵敏度分析 在 LP求出最优解之后，要研究：1）当 c ci i 发生变化时，最优解最优解如何变化？2）当 b bi i 发生变化时，最优解最优解是否变化？最优值最优值变化多少？3）当 a aijij 发生变化时，最优解最优解如何变化？2、为什么要进行敏感性分析？1）现实世界是动态变化动态变化的，如：市场变化，售价的变化将导致利润率的变化，进而导致目标函数系数目标函数系数的变化。2）有些资源是可控可控的，如：是否加班？将导致可用工时的变化，进而导致右端项值右端项值的变化

45、。3）模型中的数据有些是估计的、近似近似的。3、LP模型系数变化后的处理方法 1）重新求解麻烦，除了最优解外，其他额外价值信息无法获得。2）灵敏度分析简单有效。第第 五节五节 灵敏度分析灵敏度分析三、灵敏度分析的依据 计算的主要依据 基基 解解z基基解解 zBXNXIXBCNCICIXBNI0bBXNXIX01BNC B N C1BIC BC1BC B bBXI1B N1B1B b初始表：迭代后表：第第 五节五节 灵敏度分析灵敏度分析四、灵敏度分析的具体计算例1的最优解和最优值：*12330,10,0 xxx最优解：最优值：*150z 针对例1，我们考虑下列灵敏度分析：1、目标函数系数（价值系

46、数）的变化问题问题1）C产品的单位利润增加0.4个单位，最优解和最优值是否会改变？增加1个单位又如何？2）A产品的单位利润增加1个单位，最优解和最优值是否会改变？减少1个单位又如何？第第 五节五节 灵敏度分析灵敏度分析四、灵敏度分析的具体计算2、右端项值（资源）的变化问题：问题：1）对偶问题的最优解和最优值分别是多少？2）第一约束条件和第二约束条件的影子价格分别是多少？3）甲原料的供应量增加10个单位，总利润将增加多少？若增加20个单位又如何？第第 五节五节 灵敏度分析灵敏度分析四、灵敏度分析的具体计算3、约束条件左边变量系数（技术系数）的变化问题：问题：1）C产品对甲原料的单位消耗定额减少0

47、.4个单位，最优解是否变化？2）C产品对甲原料的单位消耗定额减少1个单位，最优解是否变化？第第 五节五节 灵敏度分析灵敏度分析四、灵敏度分析的具体计算4、加入新的决策变量问题：问题：1）若该企业经研究，开发出第四种产品D，它的单位利润为5，对原料甲、乙的单位消耗分别为2和3，试问工厂是否应生产D，以取得最大利润？2）产品D的单位利润提高到6.5，又如何？第第 五节五节 灵敏度分析灵敏度分析四、灵敏度分析的具体计算5、增加新的约束条件问题：问题：1）若企业进一步考虑产品A、B、C对某种原料丙的消耗，每生产1单位产品A、B、C分别需原料丙2、1、3单位，而原料丙的供应量是75单位，则新最优解是什么

48、？2）若原料丙的供应量只有60单位，则又如何？第第 五节五节 灵敏度分析灵敏度分析四、进一步的思考思考：思考：考虑多系数同时变化，最优解和最优值如何变化？问题：问题：1）A产品的单位利润增加1个单位，同时C产品的单位利润增加0.4个单位，则最优解如何变化？2）甲原料和乙原料的供应量同时增加10个单位，则最优值如何变化？3）等等。本节作业 1-58 第第 五节五节 灵敏度分析灵敏度分析 Lingo软件的简单介绍 补充内容补充内容人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。