运筹学-第1章

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

2、产 数量 目标函数： max z=50 x1+100 x2 约束条件： s.t. x1 + x2300 2x1 + x2400 不等式约束 x2 250 x1 ，x20 非负约束,一、线性规划应用举例,第一节 线性规划的数学模型及其标准型,一、线性规划应用举例 (Liner Programming),例2（营养搭配问题）如果有甲、乙、丙、丁四种食品，单 价各不相同，都含有不同成份的维生素，其含量和单价如下 表所示： 若要保证每人每天维生素的最低需要量，则应如何搭配各种 食品，使花的钱最少？,第一节 线性规划的数学模型及其标准型,一、线性规划应用举例,例3 靠近某河流有两个化工厂，流经第一化工厂

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

4、 x1+800 x2 约束条件： 第一段河流 （工厂1工厂2之间）： (2x1)/500 0.002 第二段河流：0.8(2x1) +(1.4-x2)/7000.002 此外有： x12 x21.4,第一节 线性规划的数学模型及其标准型,一、线性规划应用举例,例2的线性规划模型：,min z=1000 x1+800 x2 s.t. x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1 ，x20,第一节 线性规划的数学模型及其标准型,线性规划的数学模型的一般形式： max(min) z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn= (,) b1 a2

5、1x1+a22x2+a2nxn= (,) b2 约束条件 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 模型特点：目标函数(Objective function)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。,第一节 线性规划的数学模型及其标准型,二、线性规划的标准型,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

6、. 变量非负 4. 右端常数项大于等于零,第一节 线性规划的数学模型及其标准型,二、线性规划的标准型,LP标准型的矩阵形式：,第一节 线性规划的数学模型及其标准型,三、化非标准型为标准型,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、若约束条件

7、为“”时， aijxj bi aijxj xn+i = bi xn+i 剩余变量(surplus variable） 举例： max z =x1+10 x2 s.t. x1 + 2x2100 x1 + x250 x1 ，x20,第一节 线性规划的数学模型及其标准型,三、化非标准型为标准型,4、若xk为无限制，则令xk=x+kx-k，其中x+kx-k0 5、若 bi 0 举例: 化下列线性规划为标准型 min z=2x1+2x24x s.t. x1 + 3x23x3-3 x1 + 2x24x380 x1、x20，x3无限制,第一节 线性规划的数学模型及其标准型,本节作业 1-4 1-10（1）,

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

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

10、+ x2300 2x1 + x2400 x2250 x1、x20,B点和C点所代表的坐标同时为最优解，即该问题有无穷多最优解,第二节 线性规划问题的解和单纯形法,一、线性规划图解法（两个决策变量）,例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 有唯一最优解,第二节 线性规划问题的解和单纯形法,一、线性规划图解法（两个决策变量）,例5 max z =x1+x2 s.t. x1 + 2x21 x1 + x22 x1、x20 问题无可行解,第二节 线性规

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

12、厂接到三份订购卷纸 的定单，其长和宽的要求如下表所示： 该厂生产1米和2米两种标准宽度的卷纸。假定纸的长度无限 制，即可以连接起来达到所需要的长度。问：应如何切割才 能使切割损失的面积最小？,第二节 线性规划问题的解和单纯形法,二、单纯形法,解：设xij是第i种标准纸按照第j种方式的切割长度。如下表:,设s1, s2, s3分别是把标准纸切成0.5米，0.7米，0.9米后的剩余长度。,第二节 线性规划问题的解和单纯形法,二、单纯形法,LP模型： Min z=0.3 X12 +0.1X13+0.3X22+0.1X23+0.1X24+0.4X25+0.2X26+0.5s1+0.7s2 +0.9 s

13、3 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个A零件和3个B零件。这两种 零件由两种不同的原材料制成，而这两种原材料的现有数额 分别是100千克和200千克。每个生产班的原材料需要量和零 件产量见下表： 问：这三个车间各应开多少班，才能使这种产品的配

14、套数达 到最大？,第二节 线性规划问题的解和单纯形法,二、单纯形法,LP的一般形式： max(min) z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= (,) b1 a21x1+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，xn0 特点： 1. Zmax 2. 约束条件为等

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

16、基及其对应的基本解 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,第二节 线性规划问题的解和单纯形法,第二节 线性规划问题的解和单纯形法,二、单纯形法,单纯形法求LP的一般步骤,步骤1：将LP化为标准型,步骤2：选定一个初始基本可行解（人工变量法）,步骤3：迭代到另外一个基本可行解，使得目标 函数值有所改进（检验数计算）,步骤4：重复步骤3，直到目标函数值不再改进时 算法停止（所

17、有检验数大于等于零）,第二节 线性规划问题的解和单纯形法,二、单纯形法,解下列线性规划问题:,例8,第二节 线性规划问题的解和单纯形法,例8(续）,第二节 线性规划问题的解和单纯形法,例8（续）,第二节 线性规划问题的解和单纯形法,单纯形表格求LP的一般步骤,2、最优性检验 若表中所有 ,则已得最优解,算法停止。 若存在检验数 ,则若 ,则原问题无解,算法停;否则转3。,1、初始表格,第二节 线性规划问题的解和单纯形法,单纯形表格求LP的一般步骤,(1) 确定进基变量 在所有负的检验数中,找出负的最大的一个,对应的变量即为进 基变量,记为 。 (2) 确定出基变量 令 则 为出基变量, 为旋转

18、元 (3) 在“基”这一列中,用进基变量替换出基变量. (4) 用初等行变换,将旋转元变成1,旋转元所在列其余元素换成0。 同样用初等行变换将检验数中相应的元素变为0。,4、重复2,3,直到计算结束。,3、列出新单纯形表,第二节 线性规划问题的解和单纯形法,二、单纯形法,例9（练习） 解下列线性规划问题：,第二节 线性规划问题的解和单纯形法,二、单纯形法（人工变量法）,例10 解下列线性规划问题（大M法）：,标准化：,第二节 线性规划问题的解和单纯形法,加入人工变量:,例10（续）,第二节 线性规划问题的解和单纯形法,例10（续）,第二节 线性规划问题的解和单纯形法,例10（续）,最优解：,最

19、优值：,第二节 线性规划问题的解和单纯形法,二、单纯形法（人工变量法）,两阶段法 第一阶段: 添加人工变量后,引入一个辅助问题.保留原约束条件,目标函数改为 ,这里 为人工变量.求这个辅助问题的解.考察下列情况: (i) 辅助问题有最优解 ,表明原问题有可行解,辅助问题的最优解即为原问题的一个可行解。 (ii) 辅助问题有最优解 , 表明原问题无可行解,即可行域为空集。 第二阶段: 去除人工变量,还原目标函数,继续求解。,第二节 线性规划问题的解和单纯形法,二、单纯形法（人工变量法）,例10 解下列线性规划问题（两阶段法法）：,第二节 线性规划问题的解和单纯形法,例10 （两阶段法续）第一阶段

20、：,第二节 线性规划问题的解和单纯形法,例10 （两阶段法续）第一阶段：,第二节 线性规划问题的解和单纯形法,例10 （两阶段法续）第一阶段：,第二阶段,换上原目标函数,并删去人工变量：,第二节 线性规划问题的解和单纯形法,例10 （两阶段法续）第二阶段：,第二节 线性规划问题的解和单纯形法,几种特殊情况 1、退化解 当最优解中有基变量取值为0时, 就称为退化解。 2、无界解 当进基变量所对应的列向量小于等于0时,则有无界解。 3、多重解(无穷多个解) 在最优表中,有非基变量对应的检验数为0,则有多重解( 无穷多个最优解)。 4、无解(无可行解) 线性规划添加人工变量后,若人工变量仍留在最优基

21、中, 则原规划问题无可行解。,本节作业 1-15 1-19（2） 1-22（1） 1-26,第二节 线性规划问题的解和单纯形法,第四节 对偶问题和对偶单纯形法,一、对偶问题的提出,例1（生产计划问题）某企业利用A、B、C三种资源，在计划 期内生产甲、乙两种产品，已知生产单位产品资源的消耗、 单位产品利润等数据如下表，问如何安排生产计划使企业利 润最大？,第四节 对偶问题和对偶单纯形法,一、对偶问题的提出,例1的LP模型： 设 x1、x2分别代表甲、乙两种产品的生产数量 max z=50 x1+100 x2 s.t. x1 + x2300 2x1 + x2400 x2 25 x1 ，x20,同样

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

23、原问题。 问题A: max z=50 x1+100 x2 s.t. x1 + x2300 2x1 + x2400 x2250 x1、x20,第四节 对偶问题和对偶单纯形法,二、对偶问题的定义,原问题：,对偶问题：,第四节 对偶问题和对偶单纯形法,二、对偶问题的定义,原问题：,对偶问题：,性质：对偶问题的对偶问题即为原问题。,矩阵形式：,第四节 对偶问题和对偶单纯形法,二、对偶问题的定义,对偶关系表,第四节 对偶问题和对偶单纯形法,二、对偶问题的定义,例2 写出下列线性规划问题的对偶问题 max z=2x1+2x24x3 s.t. x1 + 3x2 + 3x3 30 4x1 + 2x2 + 4x

24、380 x1、x2，x30,解：其对偶问题为： min w=30y1+ 80y2 s.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 s.t. y1y2 + 4y3 2 3y1+5y2 + 2y3 8 3y1 + 4y24y3=4 y10，y2无限

25、制，y30,对偶问题为：,第四节 对偶问题和对偶单纯形法,二、对偶基本定理,考虑如下线性规划问题：,第四节 对偶问题和对偶单纯形法,二、对偶基本定理,单纯形表的矩阵形式,初始表：,迭代后表：,第四节 对偶问题和对偶单纯形法,二、对偶基本定理,构造如下线性规划问题：,令 （单纯形乘子，对偶问题的最优解）,第四节 对偶问题和对偶单纯形法,二、对偶基本定理,对偶关系示意图,非最优,非最优,可行,可行,.,.,.,最优,最优,最优,最优,可行,不可行,不可行,不可行,.,.,原问题,对偶问题,第四节 对偶问题和对偶单纯形法,二、对偶基本定理,基本定理,定理1 （弱对偶性）若 是原问题的可行解， 是对偶

26、 问题的可行解，则有 。 定理2 （最优性）设 、 分别为原问题和对偶问题的 可行解。若 ，则 、 分别为原问题和对偶问 题的最优解。 定理3 （强对偶性）若原问题和对偶问题均有可行解，则两 者都有最优解，且最优值相等。,第四节 对偶问题和对偶单纯形法,三、对偶单纯形法,例4 用对偶单纯形法求如下线性规划：,最优解：,最优值：,第四节 对偶问题和对偶单纯形法,三、对偶单纯形法,对偶单纯形法的基本步骤,1、将约束条件化成小于等于约束，列出初始单纯形表。 2、 确定出基变量。选右端向量 中，负的最大的基变量 （若 ，则已得最优解）记为 。 3、 确定进基变量。若第 行系数 ，则原问题无解。 反之，

27、令 即为进基变量， 为旋转元。 4、用初等行变换，得到一个新的基，重复以上步骤直到最优。,第四节 对偶问题和对偶单纯形法,四、对偶问题的经济意义,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 0 x1、x20,例1（续）,最优解：,最优解：,影子价格：约束条件右端项增加一个单位，目标函数值的增加量（即为对偶问题的最优解）,本节作业 1-38（2）（3） 1-48 1-42,第四节 对偶问题和对偶单纯形法,第

28、 五节 灵敏度分析,一、引例,例1 某企业利用甲、乙两种原料，生产A、B、C三种产品，每 种的产品单位利润及原材料消耗定额等数据如下表，问如何 安排生产计划使企业利润最大？,第 五节 灵敏度分析,一、引例,例1的LP模型： 设x1、x2、x3分别代表A、B、C三种产品的生产数量，则 max z=4x1+3x2+2x3 max z=4x1+3x2+2x3 s.t. x1+ x330 s.t. x1+ x3+s1=30 2x1+2x2+x380 2x1+2x2+x3 +s2=80 x1 ，x20 x1 ，x2 , s1 ，s20,第 五节 灵敏度分析,一、引例,初始单纯形表：,最优单纯形表：,第 五节 灵敏度分析,二、灵敏度分析的概念,1、什么是灵敏度分析 在 LP求出最优解之后，要研究： 1）当 ci 发生变化时，最优解如何变化？ 2）当 bi 发生变化时，最优解是否变化？最优值变化多少？ 3）当 aij 发生变化时，最优解如何变化？ 2、为什么要进行敏感性分析？ 1）现实世界是动态变化的，如：市场变化，售价的变化将导致利润率的变化，进而导致目标函数系数的变化。 2）有些资源是可控的，如：是否加班？将导致可用工时的变化，进而导致右端项值的变化。 3）模型中的数据有些是估计的、近似的。 3、LP模型系数