第1,2章绪论、线性规划与单纯形法ppt

1、运运 筹筹 学学( Operations Research )运 筹 帷 幄 之 中决 胜 千 里 之 外绪 论Introduction第一章（1）运筹学简述（2）运筹学的主要内容（3）本课程的教材及参考书（4）本课程的特点和要求（5）本课程授课方式与考核 （6）运筹学在经济管理中的应用本章主要内容：运筹学（运筹学（Operations Research,简写简写OR ）系统工程的最重要的理论基础之一，在美国有人把运筹系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学学称之为管理科学(Management Science)。运筹学所研究的。运筹学所研究的问题，可简单地归结为一句话

2、：问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为故有人称之为最优化技术最优化技术。运筹学的历史与发展 “运筹学思想的出现可以追溯到很早“田忌赛马” 。 齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排： 齐王 上中 下 田忌 下上 中丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工

3、程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。 国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。“运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如：1. 如何合理运用雷达有效地对付德军德空袭2. 对商船如何进行编队护航，使船队遭受德国潜艇攻击

4、时损失最少；3. 在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。 在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作生产组织与计划中的数学方法。 但当时并没有引起重视，直到1960年康特洛为奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。 线性规划提出后很快受到经济学家的重视，如：二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家

5、要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。 20世纪50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，

6、并将学会改名为“中国运筹学会”。成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态、动态规划等）规划等）图论图论存储论存储论排队论排队论对策论对策论决策分析决策分析1. 线性规划（线性规划（Linear Program）是一个成熟的分支，它有）是一个成熟的分支，它有效的算法效的算法单纯形法，主要解决生产计划问题，合理下料单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。问题，最优投资问题。2. 整数规划整数规划(Integrate Progra

7、m)：在线性规划的基础上，变：在线性规划的基础上，变量加上整数约束。量加上整数约束。3. 非线性规划非线性规划(Nonlinear Program)：目标函数和约束条件：目标函数和约束条件是非线性函数，如证券投资组合优化是非线性函数，如证券投资组合优化:如何合理投资使风险如何合理投资使风险最小。最小。4. 动态规划动态规划(Dynamic Program)：多阶段决策问题。是美国：多阶段决策问题。是美国贝尔曼于贝尔曼于1951年提出的。年提出的。5、图与网络、图与网络(Graph Theory and Network)：中国邮递员问：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。题、哥尼

8、斯堡城问题、最短路、最大流问题。6、存储论（、存储论（Inventory Theory)：主要解决生产中的库存问：主要解决生产中的库存问题，订货周期和订货量等问题。题，订货周期和订货量等问题。7、排队论、排队论(Queue Theory)：主要研究排队系统中的系统排：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。队和系统拥挤现象，从而评估系统的服务质量。8、对策论、对策论(Game Theory)：主要研究具有斗争性质的优化：主要研究具有斗争性质的优化问题。问题。9、决策分析、决策分析(Decision Analysis) ：主要研究定量化决策。：主要研究定量化决策。17

9、运筹学方法使用情况运筹学方法使用情况( (美美1983)1983)18 运筹学方法在中国使用情况运筹学方法在中国使用情况 ( (随机抽样随机抽样) )选用教材选用教材 运筹学运筹学教材编写组 （第3版）清华大学出版社参考教材参考教材运筹学基础及应用胡运权主编 哈工大出版社管理运筹学韩伯棠主编 （第2版）高等教育出版社运筹学(修订版) 钱颂迪主编 清华出版社先修课：高等数学，基础概率、线性代数特点：系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：真实系统系统分析问题描述模型建立与修改模型求解与检验结果分析与实施数据准备学科总成绩学科总成绩平时成绩平时成绩（30）课堂考勤课堂考勤

10、（50）平时作业平时作业（50）期末成绩期末成绩（70）讲授为主，结合习题作业运筹学在经济管理中的应用涉及的方面：运筹学在经济管理中的应用涉及的方面：1. 生产计划2. 运输问题3. 人事管理4. 库存管理5. 市场营销6. 财务和会计7.物流配送另外，还应用于设备维修、更新和可靠性分析，项目的选择另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。与评价，工程优化设计等。“管理运筹学管理运筹学”2.02.0版包括：线性规划、运输问题、整数规划（版包括：线性规划、运输问题、整数规划（0-10-1整数整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、规划、

11、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共决策分析、预测问题和层次分析法，共1515个子模块。个子模块。运 筹 帷 幄 之 中决 胜 千 里 之 外线性规划及单纯形法Linear Programming第一章第一章Chapter1 线性规划线性规划 (Linear Programming) LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论人工变量法 LP模型的应用1. 规划问题规划问题生产和经营管理中经常提出如何合

12、理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大.）例1.1 某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D 四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？ 设设 备备产产 品品 A B C D利润（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2

13、 0 4 3 有有 效效 台台 时时 12 8 16 12例1.2 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量 解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用 量分别为：x1、x2 、x3 、x42.目标函数：设总成本为z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 0

14、00 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 简写为：) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中： mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中：) (21ncccC nxxX1 mbbB16. 线性规划问题的标准形式线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj, 2 , 1,

15、 2 , 1, 0.max11 特点：(1) 目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项bi都大于或等于零(3) 决策变量xj为非负。 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。 jjxczmin也就是：令 ，可得到上式。zz jjxczzmax即 若存在取值无约束的变量 ，可令 其中：jxjjjxxx 0, jjxx 变量的变换 约束方程的转换：由不等式转换为等式。 ijijbxa0 iniinjijxbxxa称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量 常量 bi0 的变换:约束方程两边乘以

16、（1）例1.3 将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321无无约约束束xxxxxxxxxxxxxxxZ 解:（）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以用 替换 ， 且33xx 3x0,33 xx(2) 第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3) 第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z

17、达到最小值时z达到最大值，反之亦然;12334512334123351233123345max23()005() 7 () 252() 5,0 Zxxxxxxxxxxxxxxxxxxxxx xxxxx标准形式如下： 无约束2121212,0435832xxxxxxx-xminZ10 x ,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm1111654364354343435832例1.4 将线性规划问题化为标准型解： 例1.5 将线性规划问题化为标准型解：Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4

18、 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0； x2无约束 Max z = 3x15x2+5x2”8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6x4+x5= 28 4x1+2x2-2x2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0 7. 7. 线性规划问题的解线性规划问题的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnj

19、ijijnjjj线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。 可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn系数矩阵(m04010换出行将3化为15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011最优解为：X*=(18,4,0,0)T,目标函数值为z*=318+44=70.例例1.13 用单纯形法求解用单纯形法求解 02053115232.2max321321321321

20、xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出x4、x5可作为初始基变量，列单纯形表计算。cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 2021/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9-1/9-7/3j 学习要点：1. 线性规划解的概念以及3个基本定理2. 熟练掌握线性规划问题的标准化

21、3.熟练掌握单纯形法的解题思路及求解步骤人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为的变量称为人工变量人工变量，构成的可行基称为，构成的可行基称为人工基人工基，用，用大大MM法法或或两阶段法两阶段法求解，这种用人工变量作

22、桥梁的求解方法称求解，这种用人工变量作桥梁的求解方法称为为人工变量法人工变量法。例例1.10 用大用大M法解下列线性规划法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：123671234612351237max3243 4 2 10

23、 22 10,1,2,7jZxxxMxMxxxxxxxxxxxxxxxjL其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。 cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/

24、5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j 例例1.11 用大用大M法解下列线性规划法解下列线性规划12312312313123max3 2114232 +10Zxxxxxxxxxxxxxx、 、解：首先将数学模型化为标准形式1231234123513max3 2114232 10,1,2,5jZxxxxxxxxxxxxxxjL系数矩阵中不存在单位矩阵，无法建立初始单纯形表。故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：123456712

25、3412356137max3 3 11 -4 2 + 3 2 10,1,2,7jZxxxxxMxMxxxxxxxxxxxxxxjL+0 +0 其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。 Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x31-2010001Z-M-11-1+M00

26、-M0-3M+1j Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3 用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。 第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：1111 11111 1min00 nn mnnnnmmnnn mmxxxxa xa

27、xxba xaxxbLLLMMOL1 0 n mxxL 对上述模型求解（单纯形法），若=0,说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。第一阶段的线性规划问题可写为：67123412356137min 2 =11 42 3 2 1 xxxxxxxxxxxxxx127 ,0 x xx，第一阶段单纯形法迭代的过程见下表（注意：没有化为极大化问题）Cj0000011CBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-2010001146-1-301000 x4103-20100-11x610100-11-210

28、 x31-201000110-1001030 x4123001-22-50 x210100-11-20 x31-201000000000011 第二阶段： 在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例： x,x ,x x x x xx xxx xxx x xxxZmax 0123241123721731653214321321，cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x141001/3-2/3-1x210100-1-1

29、x390012/3-4/3Z2000-1/3-1/3第二阶段：54321003xxxxxZmax 最优解为（4 1 9 0 0），目标函数 Z = 2 通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有非零人非零人工变量工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。 无可行解 C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6

30、/1-3/1 Z -7M -6-4M -15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1- Z Z -3+M 0 -3-M 0 -M -2 0 2-M -3-M-2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例运算到检验数全负为止，仍含有人工变量，无可行解。 无最优解与无可行解是两个不同的概念。

31、无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为无有限最优解，或无界解。 判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解 无最优解C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z022001= 20因 但 所以原问题无最

32、优解1-1P=01-2 退化 即计算出的 （用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。 为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则（摄动法原理）： 当存在多个 时，选下标最小的非基变量为换入变量；(2) 当值出现两个以上相同的最小值时，选下标最小的基变量为换出变量。0j000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130

33、-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。可得最优解maxZ=，X1,0,1,0,3T 无穷多最优解 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：非基变量检验数，所以有无穷多最优解。C 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -

34、10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -14= 0解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。单纯性法小结单纯性法小结:建建立立模模型型变量个数变量个数变量取值变量取值约束条件约束条件目标函数目标函数新

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

36、基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解一般而言，一个经济、管理问题凡是满足以下条一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述常见问题常见问题合理利用线材问题：如何下料使用材最

37、少。配料问题：在原料供应量的限制下如何获取最大利润。投资问题：从投资项目中选取方案，使投资回报最大。产品生产计划：合理利用人力、物力、财力等，使获利最大。劳动力安排：用最少的劳动力来满足工作的需要。运输问题：如何制定调运方案，使总运费最小。 (1)设立决策变量； (2)明确约束条件并用决策变量的线性等式或不等式表示； (3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）； (4)根据决策变量的物理性质研究变量是否有非负性。建立线性规划模型的过程可以分为四个步骤：例10. 合理利用线材问题。现要做。现要做100套钢架，每套需套钢架，每套需用长为用长为2.9m，2.1m和

38、和1.5m的元钢各一根。已知原料的元钢各一根。已知原料长长7.4m，问应如何下料，使用的原材料最省。，问应如何下料，使用的原材料最省。表1-11解：若在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。见表1-11。为了得到为了得到100套钢架，需要混合使用各种下料方案。设按套钢架，需要混合使用各种下料方案。设按方方案下料的原材料根数为案下料的原材料根数为x1,方案为方案为x2，方案为

39、方案为x3，方案为方案为x4,方案为方案为x5。根据表。根据表1-11的方案，可列出以下数学模型：的方案，可列出以下数学模型：0,1003231002210028 . 03 . 02 . 01 . 00min54321532154342154321xxxxxxxxxxxxxxxxxxxxz在以上约束条件中加入人工变量在以上约束条件中加入人工变量x6,x7,x8；然后用表；然后用表1-12进行进行计算。计算。表1-12cj00.10.20.30.8-M-M - -MiCBXBbx1x2x3x4x5x6x7x8-M-M-Mx6x7x810010010010320102 21200101000100

40、01100/1100/3 cj-zj4M-0.1+3M-0.2+4M-0.3+3M-0.8+4M000第第1次计算次计算cj 0 0.1 0.2 0.3 0.8 -M -M -M i CB XB b x1 x2 x3 x4 x5 x6 x7 x8 -M -M 1 x6 x7 x1 200/3 100 100/3 0 0 1 5/3 0 1/3 -2/3 2 2/3 1 2 0 -1 1 1 1 0 0 0 1 0 -1/3 0 1/3 200/3 100/2 cj-zj 0 -0.1+5/3M -0.2+4/3M -0.3+3M -0.8 0 0 -4/3M 第第2次计算次计算最终计算表（第最

41、终计算表（第3次计算）次计算）由计算得到最优下料方案是：按方案下料30根；方案下料10根；方案下料50根。即需90根原材料可以制造100套钢架。有非基变量的检验数为零，所以存在多重最优解 。cj00.10.20.30.8-M-M-MiCBXBbx1x2x3x4x5x6x7x80.1-0.30 x2x4x1105030001100-111010-9/101/313/103/50-1/5-3/101/31/10-1/502/5 cj-zj 0000-0.74-M+0.06-M+0.12-M-0.02某工厂要用三种原材料某工厂要用三种原材料C、P、H混合调配出三种不同规格的混合调配出三种不同规格的产

42、品产品A、B、D。已知产品的规格要求，产品单价，每天能供。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表应的原材料数量及原材料单价，分别见表1-13和表和表1-14。该厂。该厂应如何安排生产，使利润收入为最大应如何安排生产，使利润收入为最大? 表1-13例例1111 配料问题配料问题 产品名称产品名称规规 格格 要要 求求单价（元单价（元/kg/kg）A A原材料原材料C C不少于不少于50%50%原材料原材料P P不超过不超过25%25%5050B B原材料原材料C C不少于不少于25%25%原材料原材料P P不超过不超过50%50%3535D D不限不限2525

43、表表1-14表明这些原材料供应数量的限额。加入到产品表明这些原材料供应数量的限额。加入到产品A、B、D的原材料的原材料C总量每天不超过总量每天不超过100kg，P的总量不超过的总量不超过100kg，H总量不超过总量不超过60kg。原材料名称 每天最多供应量（kg） 单价/(元/kg) C 100 65 P 100 25 H 60 35 表1-14根据表根据表1-13有：有：)391 (21,41,41,21BBBBAAAAPCPC这里 AC+AP+AH=A； BC+BP+BH=B (1-40)将(1-40)逐个代入(1-39)并整理得到0214121041414304143410212121H

44、PCHPCHPCHPCBBBBBBAAAAAA解：解： 如以如以AC表示产品表示产品A中中C的成分，的成分，AP表示产品表示产品A中中P的成分，依次类推。的成分，依次类推。由此得约束条件由此得约束条件AC+BC+DC100AP+BP+DP100AH+BH+DH60在约束条件中共有9个变量，为计算和叙述方便，分别用x1,x9表示。令x1=Ac, x2=Ap, x3=AH,x4=BC, x5=BP, x6=BH,x7=DC, x8=DP, x9=DH.约束条件可表示为：约束条件可表示为：0,601001000212121041414304143410212121919638527416546543

45、21321xxxxxxxxxxxxxxxxxxxxxxx目标函数n目的是使利润最大，即产品价格减去原材料的价格为最大。目的是使利润最大，即产品价格减去原材料的价格为最大。n产品价格为：产品价格为：50(x1+x2+x3)产品产品A 35(x4+x5+x6) 产品产品B 25(x7+x8+x9) 产品产品Dn原材料价格为：原材料价格为：65(x1+x4+x7)原材料原材料C 25(x2+x5+x8) 原材料P 35(x3+x6+x9) 原材料H为了得到初始解，在约束条件中加入松弛变量x10 x16，得到数学模型：例例11的线性规划模型的线性规划模型0,6010010002121210414143

46、04143410212121010401030152515max18109116963158521474113654126541132110321161514131211109754321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz约束条件目标函数最优解最优解n用单纯形法计算，经过四次迭代，得最优解为：用单纯形法计算，经过四次迭代，得最优解为： x1=100,x2=50,x3=50n这表示：需要用原料这表示：需要用原料C为为100kg，P为为50kg，H为为50kg，构，构成产品成产品A。n即每天只生产产品即每天只生产产品A为为200kg，分别

47、需要用原料，分别需要用原料C为为100kg，P为为50kg，H为为50kg。n从最终计算表中得到，总利润是从最终计算表中得到，总利润是z=500元元/天。天。例例12 优化安排问题优化安排问题 某快递公司下设一个快件分拣部，处理每天到达和外寄某快递公司下设一个快件分拣部，处理每天到达和外寄的快件。根据统计资料及经验预测，每天各时段快件数量的快件。根据统计资料及经验预测，每天各时段快件数量如下表所示。如下表所示。180时段时段到达快件数到达快件数时段时段到达快件数到达快件数10：00以前500014:00-15:00300010:00-11:00400015:00-16:00400011:00-

48、12:00300016:00-17:00450012:00-13:00400017:00-18:00350013:00-14:00250018:00-19:002500清华大学出版社181快件分拣由机器操作，分拣效率为每台快件分拣由机器操作，分拣效率为每台500件件/h,每台机器操作每台机器操作时需要配一名职工。共有时需要配一名职工。共有11台机器。分拣部一部分是全日制台机器。分拣部一部分是全日制职工，上班时间分别为：职工，上班时间分别为：10:00-18:00,11:00-19:00和和12：00-20:00，每人每天工资，每人每天工资150元，另一部分是非全日制职工，每元，另一部分是非全日

49、制职工，每天上班天上班5小时，分别为小时，分别为13:00-18:00,14:00-19:00,15:00-20:00，每人每天工资每人每天工资80元。快件处理的规则是：从每个整点起可处元。快件处理的规则是：从每个整点起可处理该整点前到达的快件，例如从理该整点前到达的快件，例如从11：00起可处理起可处理10:00前和前和10：00-11:00之间到达的快件，之间到达的快件，13:00起可整理所有这之前到达的起可整理所有这之前到达的等。因快件有时间性要求，凡是等。因快件有时间性要求，凡是12:00前到达的快件必须在前到达的快件必须在14:00以前处理完；以前处理完；15:00以前到达的，必须在以前到达的，必须在17：00以前处理以前处理完；全部快件在当天完；全部快件在当天20:00以