运筹学-第1章

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

2、12 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分别代表工厂分别代表

5、工厂1 1和工厂和工厂2 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

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

7、准型 LP标准型： 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. 右端常数项大于等于零第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型二、线性规划的标准型. . max z = CXs tAX = bX0111212122212.nnmmmnaaaaaaAaaa1(,.,)nCcc12.mbbbb12.nxxXxLP标准型的矩阵形式：第一节

8、第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型三、化非标准型为标准型1、若 min 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 剩余变量(

9、surplus variable）举例： max z =x1+10 x2 s.t. x1 + 2x2100 x1 + x250 x1 ，x20第一节第一节 线性规划的数学模型及其标准型线性规划的数学模型及其标准型三、化非标准型为标准型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） 第二节第二节 线性规划问

10、题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例例1 1的线性规划模型：的线性规划模型：决策变量：x1、x2分别代表甲、乙两种产品的生产 数量目标函数： max z=50 x1+100 x2约束条件： s.t. x1 + x2300 2x1 + x2400 x2 250 x1 ，x20 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）1、基本概念 可行解(Feasible Solution)任一满足约束条件的一组决策变量的数值； 可行域(Feasible Region)所有可行解组成的集合，也称为可行解集； 目标

11、函数等值线(Objective functionline)位于同一直线上的点，具有相同的目标函数值；2、图解法步骤(Procedure)（1）画出线性规划问题的可行域；（2）画出两条目标函数等值线；（3）平行移动目标函数等值线，使目标函数在可 行域范围内达到最优。第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例1 max Z=50 x1+100 x2 s.t. x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z* =27500BOACDz2=14000 x1 + x23002x1 + x2400 x2250该

12、问题有唯一最优解该问题有唯一最优解x x1 1=50=50；x x2 2=250=250z1=50 x1+100 x2=0第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例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点所代表的坐标点所代表的坐标同时为最优解，即该问同时为最优解，即该问题有题有无穷多最优解无穷多最

13、优解第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）例3 max z =x1+x2 s.t. x1x2 1 x1 + 2x20 x1、x20 问题有无界解 例4 min z =x1+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 问题无可行解 第二节第二节 线性规

14、划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）LP解的情况1、无可行解（LP不可行）可行域为空集2、问题有无界解（LP无界）3、唯一最优解4、无穷多最优解第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法一、线性规划图解法（两个决策变量）直观结论1、可行域可以是个凸多边形，可能无界，也可能为空。2、若线性规划问题的最优解存在，则它一定可以在可行域的某一个顶点上得到。3、若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解。4、若可行域非空有界，则一定有最优解。第二节第二节 线性规划问题的解和单纯形法线性规划问题的

15、解和单纯形法二、单纯形法例6 （切割损失问题）假定某个造纸厂接到三份订购卷纸的定单，其长和宽的要求如下表所示：该厂生产1米和2米两种标准宽度的卷纸。假定纸的长度无限制，即可以连接起来达到所需要的长度。问：应如何切割才能使切割损失的面积最小？定单号码宽（米）长（米）一二三0.50.70.9100030002000第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法解：设xij是第i种标准纸按照第j种方式的切割长度。如下表:设s1, s2, s3分别是把标准纸切成0.5米，0.7米，0.9米后的剩余长度。 宽度1米宽卷纸X11 X12 X13 2米宽卷纸X21 X22 X

16、23 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第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 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

17、+2 X24 + X25 - s2 =3000 X13+ X23 + X25+2X26- s3 =2000 Xij0, si 0, 对一切i和j第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法例7 （产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一产品，每件产品包括4个A零件和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别是100千克和200千克。每个生产班的原材料需要量和零件产量见下表：问：这三个车间各应开多少班，才能使这种产品的配套数达到最大？车间每班进料数（千克）每班产量（个数）原料1原料2 零件A零件B甲乙丙8536987

18、68594第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 LP的一般形式：max(min) z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= (,) b1a21x1+a22x2+a2nxn= (,) b2 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，x

19、n0 特点： 1. Zmax 2. 约束条件为等号 3. 变量非负 4. 右端常数项大于等于零将LP的一般形式变成LP的标准型第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 单纯形法求解LP的整体思路无穷多可行解无穷多可行解有限多可行解有限多可行解一个最优解一个最优解基本定理基本定理迭代迭代第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 基本定理以下我们总假设LP有最优解。定理 1 LP的可行域是一个凸集（凸多面体）凸集（凸多面体）。定理 2 LP的可行域的一个点是极点极点当且仅当是它是一个 基本可行解基本可行解。定理 3 LP的

20、最优解可在一个基本可行解（极点）上取到。定理 4 LP的基本可行解的个数是有限的。第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 举例：找出下列LP所有的基及其对应的基本解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化为标准型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 基基基本解基本解可行否可行否 目标值目标值对应图对应图中的点中的点

21、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/30BCDEAOABCDEOx1x22x1+3x2 =1004x1 + 2x2 =120第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 单纯形法求LP的一般步骤步骤1：将LP化为标准型步骤2：选定一个初始基本可行解（人工变量法）步

22、骤3：迭代到另外一个基本可行解，使得目标 函数值有所改进（检验数计算）步骤4：重复步骤3，直到目标函数值不再改进时 算法停止（所有检验数大于等于零）第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法解下列线性规划问题: 12231241251252515. .62245,0Max zxxxxs txxxxxxxxx基基解解345xxxz12345xxxxx例8第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 例8(续）24231242451252183351521. .46641166,0M axzxxxxs txxxxxxxxx基基解解12345

23、xxxxxz315xxx02 / 301 / 300510012 / 601 / 6004 / 601 / 61第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 例8（续）45345145245125111824251515422117. .422133422,0M axzxxxxxs txxxxxxxxx基基解解12345xxxxxz312xxx0001 / 41 / 20015 / 415 / 21001/ 41/ 20101/ 43 / 218215/27/23/2第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 单纯形表格求LP的一般步骤基基解解11

24、mmnxxxxz1mnxx100mcc11111001mmmmaaaa01mbb2 2、最优性检验 若表中所有 ,则已得最优解,算法停止。若存在检验数 ,则若 ,则原问题无解,算法停;否则转3。0jz 0jz 0jp 1、初始表格第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法 单纯形表格求LP的一般步骤 (1) 确定进基变量 在所有负的检验数中,找出负的最大的一个,对应的变量即为进 基变量,记为 。 (2) 确定出基变量令 则 为出基变量, 为旋转元 (3) 在“基”这一列中,用进基变量替换出基变量.(4) 用初等行变换,将旋转元变成1,旋转元所在列其余元素换成0。 同样用

25、初等行变换将检验数中相应的元素变为0。 kxmin|0ilikiklkbbaaalxlka 4、重复2,3,直到计算结束。3、列出新单纯形表第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法 例9（练习） 解下列线性规划问题：12312313121233252430. .324604420,0Max zxxxxxxs txxxxxxx第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法（人工变量法） 例10 解下列线性规划问题（大M法）：1212121212433. .43623,0Min zxxxxs txxxxxx12121231241

26、234433. .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（续）第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法例10（续） 0 -(1+5M)/3 M (4-7M)/3 0 0 -4

27、-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/5 -1/5 0 0 0 1 1 1 -1 3/5 6/5 0z123xxx基基解解 0 0 -1/5 0 -8/5+M

28、 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 最优解：最优值：第二节第二节 线性规划问题的解和单纯形法线性规划问题的解和单纯形法二、单纯形法（人工变量法） 两阶段法两阶段法 第一阶段第一阶段: : 添加人工变量后添加人工变量后, ,引入一个辅助问题引入一个辅助问题. .保留原约束条件保留原约束条件, ,目标函目标函数改为数改为 , ,这里这里 为人工变量为人工变量. .求这个辅助求这个辅助问题的解问题的解. .考察下列

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

30、规划问题（两阶段法法）：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 1 07/3

31、 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基基 解解 4

32、 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第二节第二节 线性规划问题的解和单纯形法线性规

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

34、期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？ 产产 品品资资 源源甲甲乙乙资源限制资源限制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 同样是上述问题，提问同样是上述问

35、题，提问：企业不安排生产，而转让 三种资源，应如何给三种资源定价？第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法一、对偶问题的提出设 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 称

36、问题B为问题A的对偶问题对偶问题，问题A为原问题原问题。 问题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原问题：原问题：对偶问题：对偶问题：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的定义

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

38、常数项第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶问题的定义例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 + 5x

39、2 + 4x3 = 80 4x1 + 2x24x3 50 x10、x20，x3无限制max w=30y1+80 y2+50y3 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基

40、基解解 zBXNXIXBCNCICIXBNI0bBXNXIX01BNC B N C1BIC BC1BC B bBXI1B N1B1B b初始表：迭代后表：第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理1111min.00 0BBBBNBIw C B bstC B B CC B N CC BC构造如下线性规划问题：min. BNIw YbstYB CYN CYC令 （单纯形乘子，对偶问题的最优解） 1BYC B第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理对偶关系示意图非最优非最优可行可行.最优最优最优最优可行不可行不可行不可行.1BC B

41、 b原问题对偶问题第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法二、对偶基本定理基本定理XYCXYbXYCXYbXY定理1 （弱对偶性）若 是原问题的可行解， 是对偶问题的可行解，则有 。 定理2 （最优性）设 、 分别为原问题和对偶问题的可行解。若 ，则 、 分别为原问题和对偶问题的最优解。定理3 （强对偶性）若原问题和对偶问题均有可行解，则两者都有最优解，且最优值相等。 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法三、对偶单纯形法1212121212min2.3 3436 23 ,0zxxstxxxxxxx x例4 用对偶单纯形法求如下线性规划：*123/5,6/

42、5xx最优解：最优值：*12/5z 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法三、对偶单纯形法 对偶单纯形法的基本步骤 1、将约束条件化成小于等于约束，列出初始单纯形表。 2、 确定出基变量。选右端向量 中，负的最大的基变量（若 ，则已得最优解）记为 。 3、 确定进基变量。若第 行系数 ，则原问题无解。 反之，令 即为进基变量， 为旋转元。 4、用初等行变换，得到一个新的基，重复以上步骤直到最优。sXrXmax|0jsrjjrjrszzaaarsab0br0rja 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法四、对偶问题的经济意义 max z=50 x1+100

43、 x2 min w=300y1+400y2+250y3 s.t. x1 + x2300 s.t. y1+ 2y2 50 2x1 + x2400 y1 + y2 + y3100 x2250 y1、y2、y3 0 x1、x20例1（续）最优解：*1250,250 xx最优解：*12350,0,50yyy影子价格：约束条件右端项增加一个单位，目标函数值的增加量（即为对偶问题的最优解） 本节作业 1-38（2）（3） 1-48 1-42 第四节第四节 对偶问题和对偶单纯形法对偶问题和对偶单纯形法第第 五节五节 灵敏度分析灵敏度分析一、引例某企业利用甲、乙两种原料，生产A、B、C三种产品，每种的产品单位

44、利润及原材料消耗定额等数据如下表，问如何安排生产计划使企业利润最大？ 产产 品品原料原料ABC供应量供应量甲甲乙乙1 12 20 02 21 11 130308080单位利润单位利润4 43 32 2第第 五节五节 灵敏度分析灵敏度分析一、引例例例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 1030