运筹学-线性规划演示教学

1、Page 1运筹学运筹学-线性规划线性规划Page 2例例2.1 某工厂在计划期内要安排某工厂在计划期内要安排、两种产品的生产，已两种产品的生产，已知生产单位产品所需的设备台时及知生产单位产品所需的设备台时及A、B两种原材料的消耗、两种原材料的消耗、资源的限制，如下表：资源的限制，如下表：问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能使工厂获利产品才能使工厂获利最多？最多？Page 3解：设生产产品解：设生产产品I和产品和产品 的产量分别为的产量分别为x1和和x2 。 则有如下模型：则有如下模型： Page 4例例2.2 某企业计划生产甲、乙两种产品。这些产品分某企业计划生

2、产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？ 设设 备备产产 品品 A B C D利润（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12Page 5解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型

3、为：Page 6例例2.3 假定一个成年人每天需要从食物中获取假定一个成年人每天需要从食物中获取3000卡热量，卡热量，55克蛋白质和克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成分以及市场价格如下表所示。养成分以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？问如何选择才能满足营养的前提下使购买食品的费用最小？序号序号食品名称食品名称热量（卡）热量（卡）蛋白质（克）蛋白质（克）钙（毫克）钙（毫克）价格（元）价格（元）1猪肉猪肉100050400102鸡蛋鸡蛋800602

4、0063大米大米9002030034白菜白菜200105002请同学们自己列出模型？请同学们自己列出模型？Page 7Page 8Page 900 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 简写为：简写为：Page 10 Page 11) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：Page 12 mnmnaaaaA1111 0 )

5、( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB1Page 135. 线性规划问题的标准形式线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特点：特点：(1) 目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3) 决策变量决策变量xj为非负。为非负。Page 14 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标

6、函数乘以(-1)(-1)，可化，可化为求极大值问题。为求极大值问题。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 变量的变换变量的变换Page 15 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然0 jxjjxx 0 jxPag

7、e 16例例2.4 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321无无约约束束xxxxxxxxxxxxxxxZ用用 替换替换 ， 且且 解解:（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以33xx 3x0,33 xxPage 17(2) 第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3) 第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去

8、剩余变量左端减去剩余变量x5，x50；(4) 第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;Page 18 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：标准形式如下：Page

9、 196. 6. 线性规划问题的解线性规划问题的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 20 可行解可行解：满足约束条件、的解为可行解。所有可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。Pag

10、e 21线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策只有两个决策变量的线性规划问题，这时可以通过图解的方法变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。探线性规划基本原理和几何意义等优点。Pag

11、e 22max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例例2.5 用图解法求解线性规划问题用图解法求解线性规划问题Page 23x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zm

12、in Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z = 2X1 + X2Page 24max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值m

13、ax Z=34.2是唯一的。是唯一的。可行域可行域Page 25min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此点是唯一最优解此点是唯一最优解Page 26 006346321212121xxxxxxxx、246x1x2246无界解无界解( (无最优解无最优解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min

14、 Zx1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)0,050305.140221212121 xxxxxxxxmax Z=3x1+4x2例例1.7Page 28学习要点：学习要点：1. 通过图解法了解线性规划有几种解的形式。通过图解法了解线性规划有几种解的形式。 (1)唯一最优解唯一最优解：一定对应于可行域的顶点； (2)无穷多最优解：无穷多最优解：多重解； (3)无界解：无界解： 即无最优解的情况，原因：缺少必要的约束条件； (4)无可行解：无可行解：即可行域为空集，原因：出现了相互矛盾的约束条件。Page 29学习要点：学习要点：2. 作图的关键

15、有三点：作图的关键有三点： (1) 可行解区域要画正确可行解区域要画正确 (2) 目标函数增加的方向不能画错目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动目标函数的直线怎样平行移动Page 30学习要点：学习要点：3.结论结论 (1)当线性规划问题的可行域非空时，它是有界或当线性规划问题的可行域非空时，它是有界或无解凸多边形。无解凸多边形。 (2)若线性规划问题存在最优解，它一定在可行域若线性规划问题存在最优解，它一定在可行域的某个顶点获得。的某个顶点获得。 (3)若在两个顶点同时得到最优解，则它们连线上若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最

16、优解。的任意一点都是最优解，即有无穷多最优解。Page 311.1.单纯形法的基本思路单纯形法的基本思路 基本思路：从可行域中某一个顶点开始，判断此顶点是否从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是是最优解，如不是, ,则再找另一个使得其目标函数值更优的顶则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。判断出线性规划问题无最优解为止。Page 321.单纯

17、形法的基本概念 基：设A为约束条件的mn阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 45例例2.8 用单纯形法求解用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：解：将数学模型化为标准形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。

18、可作为初始基变量，列单纯形表计算。Page 46cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 47学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤Page 48人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，

19、很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大的变量称为人工变量，构成的可行基称为人工基，用大MM法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。为人工变量法。Page 49例例2

20、.9 用大用大M法解下列线性规划法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Page 50故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型： 7 , 2 , 1, 012210243423max732

21、153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 Page 51cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx5

22、8-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 52解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性

23、规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。Page 53单纯性法小结单纯性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极

24、小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单纯单纯形法形法不不处处理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不处处理理约束条约束条件两端件两端同乘以同乘以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M停止停止A Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika对对任任一一)0( lklkiiaab 计计算算lkx

25、x替替换换基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解Page 55一般而言，一个经济、管理问题凡是满足以下条一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下

26、实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述Page 56 人力资源分配问题人力资源分配问题 例例2.10 某昼夜服务的公交线路每天各时间段内所需司机某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030 设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时

27、，小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少备司机和乘务人员的人数减少?Page 57解：设解：设xi表示第表示第i班次时开始上班的司机和乘务人员人数。班次时开始上班的司机和乘务人员人数。 0,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此问题最优解：此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。Page

28、 58 例例2.11某公司面临一个是外包协作还是自行生产的问题。该公司生某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和丙三种产品各生产多少件？甲、乙两种产品

29、的铸造中，由本公司铸造和由外包协作各应多少件？由外包协作各应多少件？甲乙丙资 源 限 制铸 造 工 时 (小 时 /件 )51078000机 加 工 工 时 (小 时 /件 )64812000装 配 工 时 (小 时 /件 )32210000自 产 铸 件 成 本 (元 /件 )354外 协 铸 件 成 本 (元 /件 )56-机 加 工 成 本 (元 /件 )213装 配 成 本 (元 /件 )322产 品 售 价 (元 /件 )2318162. 生产计划问题生产计划问题Page 59 解：设解：设 x x1 1, ,x x2 2, ,x x3 3 分别为三道工序都由本公司加工的甲、乙、丙三

30、种分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，产品的件数，x x4 4, ,x x5 5 分别为由外协铸造再由本公司加工和装配的甲、乙两分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。种产品的件数。 求求 x xi i 的利润：利润的利润：利润 = = 售价售价 - - 各成本之和各成本之和 产品甲全部自制的利润产品甲全部自制的利润 =23-(3+2+3)=15=23-(3+2+3)=15 产品甲铸造外协，其余自制的利润产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13=23-(5+2+3)=13 产品乙全部自制的利润产品乙全部自制的利润 =18-(5+1+2

31、)=10=18-(5+1+2)=10 产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9=18-(6+1+2)=9 产品丙的利润产品丙的利润 =16-(4+3+2)=7=16-(4+3+2)=7 可得到可得到 x xi i （i = 1,2,3,4,5i = 1,2,3,4,5） 的利润分别为的利润分别为 1515、1010、7 7、1313、9 9 元。元。Page 60通过以上分析通过以上分析, ,可建立如下的数学模型可建立如下的数学模型: :目标函数目标函数： Max 15Max 15x x1 1 + 10 + 10 x x2 2 + 7 + 7x

32、x3 3 + 13 + 13x x4 4 + 9 + 9x x5 5 约束条件约束条件： 5 5x x1 1 + 10 + 10 x x2 2 + 7 + 7x x3 3 8000 8000 6 6x x1 1 + 4 + 4x x2 2 + 8 + 8x x3 3 + 6 + 6x x4 4 + 4 + 4x x5 5 12000 12000 3 3x x1 1 + 2 + 2x x2 2 + 2 + 2x x3 3 + 3 + 3x x4 4 + 2 + 2x x5 5 10000 10000 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0Pa

33、ge 612. 生产计划问题生产计划问题例例2.12. 某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工两道工序加工。设序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，有上完成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B工序。已知产品工序。已知产品可在可在A、B任何一种任何一种设备上加工；产品设备上加工；产品可在任何规格的可在任何规格的A设备上加工，但完成设备上加工，但完成B工序时，只能在工序时，只能在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试加工。加工单位产品所

34、需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。安排最优生产计划，使该厂获利最大。Page 62设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费（单位小时）（单位小时）27910 000321B168124000250B247000783B37114000200原料费（每件）原料费（每件）0.250.350.5售价（每件）售价（每件）1.252.002.8Page 63解：设解：设xijk表示产品表示产品i在工序在工序j的设备的设备k上加工的数量。约束条上加工的数量。约束条件有：件有：）（上加工的数量相等）上加工的数量相等），在工序在工

35、序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品设备设备设备设备）（设备（设备）（设备（设备设备设备3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijkPage 64目标是利润最大化，即利润的计算公式如下：

36、目标是利润最大化，即利润的计算公式如下： 5131)()(ii该该设设备备实实际际使使用用台台时时每每台台时时的的设设备备费费用用该该产产品品件件数数销销售售单单价价原原料料单单价价利利润润带入数据整理得到：带入数据整理得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx Page 65因此该规划问题的模型为：因此该规划问题的模型为： ）（3,2,1;2,1;3,2,104000770001144000861000012976000105.35.0

37、23.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijkPage 66 例例2.132.13某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圆的圆钢各一根。已知原料每根长钢各一根。已知原料每根长7.4 m7.4 m，问：应如

38、何下料，可使所用原料最省？，问：应如何下料，可使所用原料最省？ 解：解： 共可设计下列共可设计下列5 5 种下料方案，见下表种下料方案，见下表 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 03. 套裁下料问题套裁下料问题Page 67 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的

39、原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 03. 套裁下料问题套裁下料问题Page 68用用“管理运筹学管理运筹学”软件计算得出最优下料方案：按方案软件计算得出最优下料方案：按方案1下料下料30根；按方案根；按方案2下下料料10根；按方案根；按方案4下料下料50根。根。 即即 x1=30; x2=10； x3=0； x4=50； x5=0； 只需只需90根

40、原材料就可制造出根原材料就可制造出100套钢架。套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。优方案。如果用等于号，这一方案就不是可行解了。Page 69 例例2.142.14某工厂要用三种原料某工厂要用三种原料1 1、2 2、3 3混合调配出三种不同规格的产品混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该

41、厂应如何安排生产，使利润收入为最大？甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）110065210025360354. 配料问题配料问题Page 70 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31；

42、 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。Page 71利润利润=总收入总收入-总成本总成本=甲乙丙三种产品的销售单价甲乙丙三种产品的销售单价*产品数量产品数量-甲乙丙使甲乙丙使用的原料单价用的原料单价*原料数量，故有原料数量，故有目标函数Max 50Max 50（x x1111+ +x x1212+ +x x1313）+35+35（x x2121+ +x x2222+ +x x2323）+25+25（x x3131+ +x x3232+ +x x33

43、33）-65-65（x x1111+ +x x2121+ +x x3131）- -2525（x x1212+ +x x2222+ +x x3232）-35-35（x x1313+ +x x2323+ +x x3333）= -15= -15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 约束条件： 从第从第1个表中有：个表中有： x x11110.5(0.5(x x1111+ +x x1212+ +x x1313) ) x x12120.25(0.25(x x111

44、1+ +x x1212+ +x x1313) ) x x21210.25(0.25(x x2121+ +x x2222+ +x x2323) ) x x22220.5(0.5(x x2121+ +x x2222+ +x x2323) )Page 72 从第从第2个表中，生产甲乙丙的原材料不能超过原个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有材料的供应限额，故有 ( (x x1111+ +x x2121+ +x x3131)100)100 ( (x x1212+ +x x2222+ +x x3232)100)100 ( (x x1313+ +x x2323+ +x x3333)60)

45、60 通过整理，得到以下模型：通过整理，得到以下模型：Page 73（续）（续）目标函数：目标函数：Max z = -15Max z = -15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 约束条件：约束条件： s.t. 0.5 s.t. 0.5 x x1111-0.5 -0.5 x x12 12 -0.5 -0.5 x x1313 0 0 （原材料（原材料1 1不少于不少于50%50%） -0.25-0.25x x1111+0.75+0.75x x1212 -

46、0.25 -0.25x x1313 0 0 （原材料（原材料2 2不超过不超过25%25%） 0.750.75x x2121-0.25-0.25x x2222 -0.25 -0.25x x2323 0 0 （原材料（原材料1 1不少于不少于25%25%） -0.5 -0.5 x x2121+0.5 +0.5 x x2222 -0.5 -0.5 x x2323 0 0 （原材料（原材料2 2不超过不超过50%50%） x x1111+ + x x2121 + + x x3131 100 ( 100 (供应量限制）供应量限制） x x1212+ + x x2222 + + x x3232 100

47、( 100 (供应量限制）供应量限制） x x1313+ + x x2323 + + x x3333 60 ( 60 (供应量限制）供应量限制） x xijij 0 , i = 1,2,3; j = 1,2,3 0 , i = 1,2,3; j = 1,2,3Page 74 例例2.152.15某部门现有资金某部门现有资金200200万元，今后五年内考虑给以下的项目投资。已知：万元，今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第五年每年年初都可投资，当年末能收回本利：从第一年到第五年每年年初都可投资，当年末能收回本利110%110%；项目项目B B：从第一年到第四年每年年初

48、都可投资，次年末能收回本利：从第一年到第四年每年年初都可投资，次年末能收回本利125%125%，但规定每年最，但规定每年最大投资额大投资额不能超过不能超过3030万元；万元；项目项目C C：需在第三年年初投资，第五年末能收回本利：需在第三年年初投资，第五年末能收回本利140%140%，但规定最大投资额不能超过，但规定最大投资额不能超过8080万元；万元；项目项目D D：需在第二年年初投资，第五年末能收回本利：需在第二年年初投资，第五年末能收回本利155%155%，但规定最大投资额不能超过，但规定最大投资额不能超过100100万元。万元。 据测定每万元每次投资的风险指数如下表：据测定每万元每次投

49、资的风险指数如下表：问：a a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330330万元的万元的基础上使得其投资总的风险系数为最小？基础上使得其投资总的风险系数为最小？项目风险指数（次/万元）A1B3C4D5.55. 投资问题投资问题Page 75 解：解： 1 1）确定决策变量：连续投资问题）确定决策变量：连续投资问题 设 xij ( i = 15，j =

50、 14)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24Page 762 2）约束条件：）约束条件：第一年：第一年：A A当年末可收回投资，故第一年年初应把全部资金投出去，于是当年末可收回投资，故第一年年初应把全部资金投出去，于是 x x1111+ + x x12 12 = 200= 200；第二年：第二年：B B次年末才可收回投资，故第二年年初有资金次年末才可收回投资，故第二年年初有资金1.1 1.1 x x1111，于是

51、，于是 x x21 21 + + x x2222+ + x x2424 = = 1.11.1x x1111；第三年：年初有资金第三年：年初有资金 1.11.1x x2121+ 1.25+ 1.25x x1212，于是，于是 x x31 31 + + x x3232+ + x x3333 = 1.1 = 1.1x x2121+ 1.25+ 1.25x x1212；第四年：年初有资金第四年：年初有资金 1.11.1x x3131+ 1.25+ 1.25x x2222，于是，于是 x x41 41 + + x x4242 = 1.1 = 1.1x x3131+ 1.25+ 1.25x x2222；第

52、五年：年初有资金第五年：年初有资金 1.11.1x x4141+ 1.25+ 1.25x x3232，于是，于是 x x51 51 = 1.1= 1.1x x4141+ 1.25+ 1.25x x3232； B B、C C、D D的投资限制：的投资限制： x xi2 i2 30 ( i =1 30 ( i =1、2 2、3 3、4 )4 )，x x3333 80 80，x x2424 100 100 3 3）目标函数及模型：）目标函数及模型：a) Max z = 1.1Max z = 1.1x x5151+ 1.25+ 1.25x x4242+ 1.4+ 1.4x x33 33 + 1.55+

53、 1.55x x24 24 s.t. s.t. x x1111+ + x x12 12 = 200= 200 x x21 21 + + x x2222+ + x x2424 = 1.1 = 1.1x x1111； x x31 31 + + x x3232+ + x x3333 = 1.1 = 1.1x x2121+ 1.25+ 1.25x x1212； x x41 41 + + x x4242 = 1.1 = 1.1x x3131+ 1.25+ 1.25x x2222； x x51 51 = 1.1= 1.1x x4141+ 1.25+ 1.25x x3232； x xi2 i2 30 ( i

54、 =1 30 ( i =1、2 2、3 3、4 )4 )，x x3333 80 80，x x2424 100 100 x xijij 0 ( i = 1 0 ( i = 1、2 2、3 3、4 4、5 5；j = 1j = 1、2 2、3 3、4 4） Page 77一、灵敏度分析的含义与内容一、灵敏度分析的含义与内容1.1.灵敏度分析的含义灵敏度分析的含义 灵敏度分析：灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）参数（系数）ci、aij、bi变化时，对最优解产生的影响。变化时，对最优解产生的影响。2.2.灵敏

55、度分析的作用（意义）灵敏度分析的作用（意义） 1 1）因为线性规划中的）因为线性规划中的cici、aijaij、bibi这些系数都是估计值和预测值，不这些系数都是估计值和预测值，不一定非常准确；一定非常准确； 2 2）即使这些系数值在某一时刻是精确值，它们也会随着市场条件的）即使这些系数值在某一时刻是精确值，它们也会随着市场条件的变化而变化，不会一成不变的。变化而变化，不会一成不变的。 那么如果这些系数变了，线性规划已经求出的最优解会不会变化那么如果这些系数变了，线性规划已经求出的最优解会不会变化呢？我们需要不要重新求解呢？有了灵敏度分析，我们就不必为了应付呢？我们需要不要重新求解呢？有了灵敏

56、度分析，我们就不必为了应付这些变化而不停地建立新的模型和求其新的最优解了；也不会由于系数这些变化而不停地建立新的模型和求其新的最优解了；也不会由于系数的估计和预测的精确性而对所求得的最优解存有不必要的怀疑。的估计和预测的精确性而对所求得的最优解存有不必要的怀疑。3.3.灵敏度分析的内容灵敏度分析的内容 Page 78x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1例例2.1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (

57、D) x2 0 (E)得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500二、目标函数中的系数二、目标函数中的系数 ci 的灵敏度分析的灵敏度分析Page 79x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADEPage 80二、目标函数中的系数二、目标函数中的系数 ci ci 的灵敏度分析的灵敏度分析 考虑例考虑例2.12.1的情况，的情况， c ci i 的变化只影响目标函数等值线的斜率，的变化只影响目标函数等值线的斜率，目标函数目标函数

58、 z = 50 xz = 50 x1 1 + 100 x+ 100 x2 2 在在 z = xz = x2 2 (x(x2 2 = z = z 斜率为斜率为0 0 ) ) 到到 z = xz = x1 1 + x+ x2 2 (x(x2 2 = -x= -x1 1 + z + z 斜斜率为率为 -1-1 ) )之间时，原最优解之间时，原最优解 x x1 1 = 50= 50，x x2 2 = 100 = 100 仍是最优解。仍是最优解。一般情况：一般情况： z = cz = c1 1 x x1 1 + c+ c2 2 x x2 2 写成斜截式写成斜截式 x x2 2 = - (c = - (c1 1 / c/ c2 2 ) x ) x1 1 + z / c+ z / c2 2 目标函数等值线的斜率为目标函数等值线的斜率为 - (c- (c1 1 / c/ c2 2 ) ) ， 当当 -1 -1 - (c- (c1 1 / c/ c2 2 ) ) 0 0 （* *）