运筹学 第一章

1、Chapter 1 线性规划线性规划 Linear Programming Page 1 运筹学运筹学 Operations Research 2016.9.7 Chapter 1 线性规划线性规划 Linear Programming Page 2 2021年6月25日星期五2 一、运筹学（OR）发展简介 v运筹学在国外 英国称为 Operational Research 美国称为 Operations Research 起源于二战期间的军事问题，如雷达的设置、运输船 队的护航舰队的规模、反潜作战中深水炸弹的深度、 飞机出击队型、军事物资的存储等。 二战以后运筹学应用于经济管理领域（LP、计

2、算机） 1948年英国首先成立运筹学会；1952年美国成立运筹 学会。 1952年，Morse 和 Kimball出版运筹学方法 1959年成立国际运筹学联合会 Chapter 1 线性规划线性规划 Linear Programming Page 3 2021年6月25日星期五3 v运筹学在国内 中国古代朴素的运筹学思想（田忌与齐王对马、丁渭修复 皇宫） 1956年成立运筹学小组 1958年提出运输问题的图上作业法 1962年提出中国邮路问题 1964年华罗庚推广统筹方法 我国于1982年加入国际运筹学联合会，并于1999年8月组 织了第15届大会 Chapter 1 线性规划线性规划 Lin

3、ear Programming Page 4 2021年6月25日星期五4 二、运筹学的特点及研究对象二、运筹学的特点及研究对象 运筹学的定义运筹学的定义 运筹学为决策机构对所控制的业务活动作决策时，提供以运筹学为决策机构对所控制的业务活动作决策时，提供以 数量为基础的科学方法数量为基础的科学方法Morse Morse 和和 KimballKimball 运筹学是把科学方法应用在指导人员、工商企业、政府和运筹学是把科学方法应用在指导人员、工商企业、政府和 国防等方面解决发生的各种问题，其方法是发展一个科学的国防等方面解决发生的各种问题，其方法是发展一个科学的 系统模式，并运用这种模式预测、比较

4、各种决策及其产生的系统模式，并运用这种模式预测、比较各种决策及其产生的 后果，以帮助主管人员科学地决定工作方针和政策后果，以帮助主管人员科学地决定工作方针和政策英国英国 运筹学会运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中运筹学是应用分析、试验、量化的方法对经济管理系统中 人力、物力、财力等资源进行统筹安排，为决策者提供有根人力、物力、财力等资源进行统筹安排，为决策者提供有根 据的最优方案，以实现最有效的管理据的最优方案，以实现最有效的管理中国百科全书中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为现代运筹学涵盖了一切领域的管理与优化问题，称为 Management

5、 ScienceManagement Science Chapter 1 线性规划线性规划 Linear Programming Page 5 2021年6月25日星期五5 三、运筹学的工作步骤 明确问题明确问题 建立模型建立模型 设计算法设计算法 整理数据整理数据 求解模型求解模型 评价结果评价结果 简化？简化？ 满意？满意？ Yes No No v明确问题 v建立模型 v设计算法 v整理数据 v求解模型 v评价结果 Chapter 1 线性规划线性规划 Linear Programming Page 6 2021年6月25日星期五6 四、运筹学内容介绍 线性规划及单纯形法线性规划及单纯形法

6、 对偶理论及灵敏度分析对偶理论及灵敏度分析 运输问题运输问题 整数规划整数规划 动态规划动态规划 图与网络分析图与网络分析 存储论存储论 排队论（随机服务理论）排队论（随机服务理论） 决策论决策论 Chapter 1 线性规划线性规划 Linear Programming Page 7 成绩考评 平时成绩 10% 期中考核成绩 30% 期末考试成绩 60% 2021年6月25日星期五7 Chapter 1 线性规划线性规划 Linear Programming 1.1 LP的数学模型的数学模型 Mathematical Model of LP 1.2 图解法图解法 Graphical Meth

7、od 1.3 标准型标准型 Standard form of LP 1.4 基本概念基本概念 Basic Concepts 1.5 单纯形法单纯形法 Simplex Method 1.1 线性规划的线性规划的数学模型数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 10 2021年6月25日星期五10 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 线性规划通常研究资源的最优利用、设备最佳运行等线性规划通常研究资源的最优利用、设备最佳运行等 问题。例如

8、，当任务或目标确定后，如何统筹兼顾，合理问题。例如，当任务或目标确定后，如何统筹兼顾，合理 安排，用最少的资源安排，用最少的资源 （如资金、设备、原标材料、人工、（如资金、设备、原标材料、人工、 时间等）去完成确定的任务或目标；企业在一定的资源条时间等）去完成确定的任务或目标；企业在一定的资源条 件限制下，如何组织安排生产获得最好的经济效益（如产件限制下，如何组织安排生产获得最好的经济效益（如产 品量最多品量最多 、利润最大）。、利润最大）。 线性规划线性规划（Linear Programming,缩写为LP）是运筹学的重要是运筹学的重要 分支之一，在实际中应用得较广泛，其方法也较成熟，借助分

9、支之一，在实际中应用得较广泛，其方法也较成熟，借助 计算机，使得计算更方便，应用领域更广泛和深入。计算机，使得计算更方便，应用领域更广泛和深入。 Chapter 1 线性规划线性规划 Linear Programming Page 11 2021年6月25日星期五11 【例例1.1】最优生产计划问题。某企业在计划期内计划生产甲、最优生产计划问题。某企业在计划期内计划生产甲、 乙、丙三种产品。这些产品分别需要要在设备乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需上加工，需 要消耗材料要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加，按工艺资料规定，单件产品在不同设备上加 工及所

10、需要的资源如表工及所需要的资源如表1.1所示。已知在计划期内设备的加工能所示。已知在计划期内设备的加工能 力各为力各为200台时，可供材料分别为台时，可供材料分别为360、300公斤；每生产一件甲、公斤；每生产一件甲、 乙、丙三种产品，企业可获得利润分别为乙、丙三种产品，企业可获得利润分别为40、30、50元，假定元，假定 市场需求无限制。企业决策者应如何安排生产计划，使企业在市场需求无限制。企业决策者应如何安排生产计划，使企业在 计划期内总的利润收入最大？计划期内总的利润收入最大？ 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 1.1.1 应

11、用模型举例应用模型举例 Chapter 1 线性规划线性规划 Linear Programming Page 12 2021年6月25日星期五12 产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源 设备设备A 3 1 2 200 设备设备B 2 2 4 200 材料材料C 4 5 1 360 材料材料D 2 3 5 300 利润（元利润（元/件）件） 40 30 50 表表1.1 产品资源消耗产品资源消耗 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 13

12、 产品产品 资源资源 甲甲 乙乙 丙丙现有资现有资 源源 设备设备A 3 1 2 200 设备设备B 2 2 4 200 材料材料C 4 5 1 360 材料材料D 2 3 5 300 利润（元利润（元/ 件）件） 40 30 50 2021年6月25日星期五13 321 503040maxxxxZ 000 300532 36054 200422 20023 321 321 321 321 321 xxx xxx xxx xxx xxx ， 【解解】设设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型 为：为： 1.1 线性规划的数学模型线性规划的

13、数学模型 Mathematical Model of LP 最优解最优解X=(50,30,10);Z=3400 Chapter 1 线性规划线性规划 Linear Programming Page 14 2021年6月25日星期五14 线性规划的数学模型由线性规划的数学模型由 决策变量决策变量 Decision variables 目标函数目标函数Objective function 约束条件约束条件Constraints 构成。称为三个要素构成。称为三个要素。 n其特征是：其特征是： n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数

14、，通常是求最大值或 最小值；最小值； n2解决问题的解决问题的是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。 怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？ 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 15 练习练习:饼干生产问题饼干生产问题 2021年6月25日星期五15 45 利润（百元利润（百元/吨）吨） 1122 烘箱烘箱 512 成形机成形机 1553 搅拌机搅拌机 每天现有工时每天现有工时 II型

15、饼干型饼干 I 型饼干型饼干 资源资源 单位时耗单位时耗 小时小时/吨吨 产品产品 为充分利用现有资源，该厂应如何制定生产计划，使获利最大？为充分利用现有资源，该厂应如何制定生产计划，使获利最大？ Chapter 1 线性规划线性规划 Linear Programming Page 16 设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z 表示I型和II型饼干所创造的日总利润 2021年6月25日星期五16 目标：目标： max z = 5X1 +4X2 约束条件：约束条件： 3X1 +5X2 15 （搅拌机的限制）（搅拌机的限制） 2X1 + X2 5 （成形机的限制）（成形

16、机的限制） 2X1 +2X2 11 （烘箱的限制）（烘箱的限制） X1 0 ， X2 0 Chapter 1 线性规划线性规划 Linear Programming Page 17 练习：运输问题练习：运输问题 2021年6月25日星期五17 应如何调运电机，即满足用户需要，又使总的运费最少？应如何调运电机，即满足用户需要，又使总的运费最少？ 运价（元运价（元/台）台）B1B2B3供应量供应量 A1152118200 A2202516150 需求量（台）需求量（台）1008090B3120 Chapter 1 线性规划线性规划 Linear Programming Page 18 设设Xij表

17、示从仓库表示从仓库Ai调到商场调到商场Bj的调拨数，（的调拨数，（i=1,2;j=1,2,3）以台为）以台为 单位，则有以下单位，则有以下LPLP模型：模型： 2021年6月25日星期五18 minZ=15x11+21x12+18x13+20 x21+25x22+16x23 S.T. x11+x12+x13200 x21+x22+x23150 x11+x21=100 x12+x22=80 x13+x2390 x13+x23120 xij0（i=1,2;j=1,2,3）(严格设严格设Xij应取整数值，这点暂不讨论应取整数值，这点暂不讨论) Chapter 1 线性规划线性规划 Linear Pr

18、ogramming Page 19 2021年6月25日星期五19 1.1.2 线性规划的一般模型线性规划的一般模型 一般地，假设线性规划数学模型中，有一般地，假设线性规划数学模型中，有m个约束，有个约束，有n个决策变量个决策变量 xj, j=1,2,n，目标函数的变量系数用，目标函数的变量系数用cj表示表示, cj称为称为价值系数价值系数。约。约 束条件的变量系数用束条件的变量系数用aij表示，表示，aij称为称为工艺系数工艺系数。约束条件右端的。约束条件右端的 常数用常数用bi表示，表示，bi称为称为资源限量资源限量。则线性规划数学模型的一般表达。则线性规划数学模型的一般表达 式可写成式可

19、写成 1 122 11112211 21 122222 1 122 max(min) (, ) (, ) (, ) 0,1,2, nn nn nn mmmnnm j Zc xc xc x a xa xa xb a xa xa xb a xaxaxb xjn 或 或 或 为了书写方便，上式也可写成：为了书写方便，上式也可写成： 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 20 2021年6月25日星期五20 1 1 max(min) (, )1,2, 0,1,

20、2, n jj j n ijji j j Zc x a xbim xjn 或 在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 21 2021年6月25日星期五21 线性规划一般模型的结构线性规划一般模型的结构 目标函数目标函数 ：max，min 约束条件约束条件：,=, 变量符号变量符号：0, unr,0 unr, 0)(X b),(AX. t . s XCzmax(min) T

21、 说明：说明： 线性规划模型由三部分构成：目标函数、约束条件和变线性规划模型由三部分构成：目标函数、约束条件和变 量符号。量符号。 任何实际问题严格来讲是非线性的。在实际建模时应任何实际问题严格来讲是非线性的。在实际建模时应 明确什么样的特性使我们可以做出线性性质的假定。明确什么样的特性使我们可以做出线性性质的假定。 第二章第二章 线性规划线性规划 Chapter 1 线性规划线性规划 Linear Programming Page 22 2021年6月25日星期五22 【例例1.2】某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天， 轮流休息。根

22、据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示。 表表1.2 营业员需要量统计表营业员需要量统计表 商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员 最少。最少。 星期星期需要人数需要人数星期星期需要人数需要人数 一一300五五480 二二300六六600 三三350日日550 四四400 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 23 2021年

23、6月25日星期五23 【解解】 设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上班天后星期一到星期日开始上班 的营业员，则这个问题的线性规划模型为的营业员，则这个问题的线性规划模型为 7 ,2, 1,0 550 600 480 400 350 300 300 min 76543 65432 54321 74321 76321 76521 76541 7654321 jx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxxxxZ j 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 星星 期

24、期 需要需要 人数人数 星星 期期 需要需要 人数人数 一一300五五480 二二300六六600 三三350日日550 四四400 Chapter 1 线性规划线性规划 Linear Programming Page 24 2021年6月25日星期五24 1 1 X1X10 0 C1C1404404 =300300104104 2 2 X2X26767 C2C2301301 =3003001 1 3 3 X3X3146146 C3C3350350 =3503500 0 4 4 X4X4170170 C4C4400400 =4004000 0 5 5 X5X59797 C5C5480480 =

25、4804800 0 6 6 X6X6120120 C6C6600600 =6006000 0 7 7 X7X71717 C7C7550550 =5505500 0 最优解：最优解： Z617（人）（人） Chapter 1 线性规划线性规划 Linear Programming Page 25 2021年6月25日星期五25 【例例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这 些轴的规格分别是些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长），这些轴需要用同一种圆钢来做，圆钢长 度为度为

26、4 m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？ 【解解】这是一个条材下料问题这是一个条材下料问题 ，设切口宽度为零。，设切口宽度为零。 设一根圆钢切割成甲、设一根圆钢切割成甲、 乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式 1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样 的非负整数解共有的非负整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。

27、 表表13 下料方案下料方案 方方 案案 规格规格 1234 5678910需求量需求量 y1(根根) 221 11 0 00001000 y2 102 10 4 32101000 y3 010 23 0 12451000 余料（余料（m） 00.30.5 0.1o.4 00.30.60.20.5 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 26 2021年6月25日星期五26 设设xj(j=1,2,10)为第为第j种下料方案所用圆钢的根数。则用料最少种下料

28、方案所用圆钢的根数。则用料最少 数学模型数学模型 求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛 坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长 的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案 。如果方案较多，用计。如果方案较多，用计 算机编程排方案，去掉余料较长的方案，进行初选。算机编程排方案，去掉余料较长的方案，进行初选。 102 , 1, 0 100054232 10002342 100022 min 10987542 9876431

29、54321 10 1 ，jx xxxxxxx xxxxxxx xxxxx xZ j j j 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 方案方案 规格规格 1234 5678910需求量需求量 y1(根根) 221 11 0 00001000 y2 102 10 4 32101000 y3 010 23 0 12451000 余料（余料（m）00.30.5 0.1o.4 00.30.60.20.5 Chapter 1 线性规划线性规划 Linear Programming Page 27 2021年6月25日星期五27 1 1 X1X1500

30、500 2 2 X2X20 0 3 3 X3X30 0 4 4 X4X40 0 5 5 X5X50 0 6 6 X6X662.562.5 7 7 X7X70 0 8 8 X8X80 0 9 9 X9X9250250 1010 X10X100 0 Z812.5 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 28 2021年6月25日星期五28 【例例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格配料问题。某钢铁公司生产一种合金，要求的成分规格 是：锡不

31、少于是：锡不少于28%，锌不多于，锌不多于15%，铅恰好，铅恰好10%，镍要界于，镍要界于 35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级之间，不允许有其他成分。钢铁公司拟从五种不同级 别的矿石中进行冶炼，每种矿物的成分含量和价格如表别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。所示。 矿石杂质在冶炼过程中废弃，现要求每吨合金成本最低的矿物数矿石杂质在冶炼过程中废弃，现要求每吨合金成本最低的矿物数 量。假设矿石在冶炼过程中，合金含量没有发生变化。量。假设矿石在冶炼过程中，合金含量没有发生变化。 表表1.4 矿石的金属含量矿石的金属含量 合金合金 矿石矿石 锡锡%锌锌%

32、铅铅%镍镍%杂质杂质费用（元费用（元/t ） 12510102530340 240003030260 301552060180 4202004020230 585151755190 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 29 2021年6月25日星期五29 解解: 设设xj（j=1,2，5）是第）是第j 种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模 型型 注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种注意，矿石在实际冶炼时金属

33、含量会发生变化，建模时应将这种 变化考虑进去，有可能是非线性关系。配料问题也称配方问题、变化考虑进去，有可能是非线性关系。配料问题也称配方问题、 营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t ） 12510102530340 240003030260 301552060180 4202004020230 585151755190 12345 1245 1345 135 12345 12345

34、 12 min340260180230190 0.250.40.20.080.28 0.10.150.20.050.15 0.10.050.150.1 0.250.30.20.40.170.55 0.250.30.20.40.170.35 0.70.7 Zxxxxx xxxx xxxx xxx xxxxx xxxxx xx 345 0.40.80.451 0,1,2,5 j xxx xj Chapter 1 线性规划线性规划 Linear Programming Page 30 2021年6月25日星期五30 1 1 X1X10 0 2 2 X2X20.33330.3333 3 3 X3X30

35、 0 4 4 X4X40.58330.5833 5 5 X5X50.66670.6667 最优解：最优解： Z=347.5 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 31 2021年6月25日星期五31 【例例1.5】投资问题。某投资公司在第一年有投资问题。某投资公司在第一年有200万元资金，每年都有如下的万元资金，每年都有如下的 投资方案可供考虑采纳：投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继假使第一年投入一笔资金，第二年又继 续投入此资

36、金的续投入此资金的50%，那么到第三年就可回收第一年投入资金的一，那么到第三年就可回收第一年投入资金的一 倍金额倍金额”。投资公司决定最优的投资策略使第六年所掌握的资金最。投资公司决定最优的投资策略使第六年所掌握的资金最 多。多。 第五年：第五年：x7/2+x9=x8+2x5 第一年：第一年：x1+x2=200(万元万元) 第二年：第二年：(x1/2 +x3)+x4=x2 第三年第三年(x3/2+x5)+x6=x4+2x1 第四年：第四年：(x5/2+x7)+x8=x6+2x3 到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型，整理后得到下列线性规划模型 1

37、.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 【解解】设设 x1：第一年的投资；：第一年的投资； x2：第一年的保留资金：第一年的保留资金 x3：第二年新的投资；：第二年新的投资； x4：第二年的保留资金：第二年的保留资金 x5：第三年新的投资；：第三年新的投资； x6：第三年的保留资金：第三年的保留资金 x7：第四年新的投资：第四年新的投资 x8：第四年的保留资金：第四年的保留资金 x9：第五年的保留资金：第五年的保留资金 Chapter 1 线性规划线性规划 Linear Programming Page 32 2021年6月25日星期五32

38、 79 12 1234 13456 35678 5789 max2 200 2220 42220 42220 4220 0,1,2,9 j Zxx xx xxxx xxxxx xxxxx xxxx xj 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 1 1 X1X155.284655.2846 2 2 X2X2144.7155144.7155 3 3 X3X3117.0732117.0732 4 4 X4X40 0 5 5 X5X552.032552.0325 6 6 X6X60 0 7 7 X7X7208.1301208.1301 8 8 X

39、8X80 0 9 9 X9X90 0 最优解：最优解：Z 416.26万元万元 x1：第一年的投资；：第一年的投资； x2：第一年的保留资金：第一年的保留资金 x3：第二年新的投资；：第二年新的投资；x4：第二年的保留资金：第二年的保留资金 x5：第三年新的投资；：第三年新的投资； x6：第三年的保留资金：第三年的保留资金 x7：第四年新的投资：第四年新的投资 x8：第四年的保留资金：第四年的保留资金 x9：第五年的保留资金：第五年的保留资金 Chapter 1 线性规划线性规划 Linear Programming Page 33 2021年6月25日星期五33 【例例1.6】均衡配套生产问

40、题。某产品由均衡配套生产问题。某产品由2件甲、件甲、3件乙零件组装而成。件乙零件组装而成。 两种零件必须经过设备两种零件必须经过设备A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工时上的加工时 间分别为间分别为5分钟和分钟和9分钟，每件乙零件在分钟，每件乙零件在A、B上的加工时间分别为上的加工时间分别为4分分 钟和钟和10分钟。现有分钟。现有2台设备台设备A和和3台设备台设备B，每天可供加工时间为，每天可供加工时间为8小时。小时。 为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不 超过另一种设备总时间超过另一种

41、设备总时间1小时。怎样安排设备的加工时间使每天产品的小时。怎样安排设备的加工时间使每天产品的 产量最大。产量最大。 【解解】 设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是 ) 3 1 , 2 1 min( 21 xxy 设备设备A、B每天加工工时的约束为每天加工工时的约束为 6083109 608245 21 21 xx xx 要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约小时的约 束为束为 60)109()45 2121 xxxx（ 1.1 线性规划的数学模型线性规划的数学模

42、型 Mathematical Model of LP Chapter 1 线性规划线性规划 Linear Programming Page 34 2021年6月25日星期五34 目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于 21 3 1 , 2 1 xyxy 整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式 60)109()45( 60)109()45( 2121 2121 xxxx xxxx 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 1 2 12

43、12 12 12 12 m a x 1 2 1 3 549 6 0 91 01 4 4 0 466 0 466 0 0 Zy yx yx xx xx xx xx yxx 、 Chapter 1 线性规划线性规划 Linear Programming Page 35 2021年6月25日星期五35 1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的 几个应用例子几个应用例子 2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征 3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。 1.1 线性规划的数学模型线性规划的数学模型 Mathemat

44、ical Model of LP 下一节：图解法下一节：图解法 1.2 图解法图解法 Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 37 2021年6月25日星期五37 通常用于求解含有两个决策变通常用于求解含有两个决策变 量的线性规划问题。量的线性规划问题。 所求一般模型的线性规划问所求一般模型的线性规划问 题无需化成标准模型。题无需化成标准模型。 线性规划的图解法线性规划的图解法 第二章第二章 线性规划线性规划 Chapter 1 线性规划线性规划 Linear Programming Page 38 max z=5

45、x1+4x2 s.t. 3x1+ 5x215 2x1+ x25 2x1+ 2x211 x1 0, x20 2021年6月25日星期五38 目标函数等值线目标函数等值线 最优解最优解 0 x1 x2 Z=0 Z=4 O A B C x2 = -5/4 x1 + 1/4 z (10/7,15/7) max z=110/7 5 3 5 5/2 11/2 11/2 可行域可行域 1.2 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 39 2021年6月25日星期五39 图解法的步骤：图解法的步骤： 1.求可

46、行解集合。求可行解集合。分别求出满足每个约束包括变量非负要求的分别求出满足每个约束包括变量非负要求的 区域，其交集就是可行解集合，或称为区域，其交集就是可行解集合，或称为可行域可行域； 2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点（c1,c2)，矢，矢 量的方向就是目标函数增加的方向，称为梯度方向，再作一量的方向就是目标函数增加的方向，称为梯度方向，再作一 条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形； 3.求最优解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函

47、数直线， 直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。 一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动 1.2 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 40 2021年6月25日星期五40 x1 x2 O 1020 30 40 10 20 30 40 (3,4) (15,10) 最优解最优解X=(15,10)

48、最优值最优值Z=85 402 21 xx 305 . 1 21 xx 0, 0 305 . 1 402 21 21 21 xx xx xx 练习例练习例1.7 21 43maxxxZ 1.2 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 41 2021年6月25日星期五41 246 x1 x2 2 4 6 最优解最优解X=(3,1) 最优值最优值Z=5 (3,1) 00 63 4 63 21 21 21 21 xx xx xx xx 、 min Z=x1+2x2 例例1.8 (1,2) 1.2 图解

49、法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 42 2021年6月25日星期五42 2 46 x1 x2 2 4 6 X（ （2）（ （3,1） X（ （1）（ （1,3） (5,5) 00 63 4 63 21 21 21 21 xx xx xx xx 、 min Z=5x1+5x2 例例1.9 有无穷多个最优解有无穷多个最优解 即具有多重解即具有多重解,通解为通解为 01 ,)1 ( )2() 1 ( XXX 当当=0.5时时 =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2

50、 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 43 2021年6月25日星期五43 246 x1 x2 2 4 6 (1,2) 00 63 4 63 21 21 21 21 xx xx xx xx 、 无界解无界解(无最优解无最优解) max Z=x1+2x2例例1.10 1.2 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 44 2021年6月25日星期五44 x1 x2 O 102030 40 10

51、 20 30 40 50 50 0,0 50 305 .1 402 21 21 21 21 xx xx xx xx 无可行解无可行解 即无最优解即无最优解 max Z=10 x1+4x2例例1.11 1.2 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 45 2021年6月25日星期五45 由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式种形式： 1.有唯一最优解有唯一最优解(例例1.7例例1.8) 2.有多重解有多重解(例例1.9) 3.有无界解有无界解(例例1.10) 4.无

52、可行解无可行解(例例1.11) 1、2情形为有最优解情形为有最优解 3、4情形为无最优解情形为无最优解 1.2 图解法图解法 The Graphical Method Chapter 1 线性规划线性规划 Linear Programming Page 46 2021年6月25日星期五46 1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式 2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动 1.2 图解法图解法 The

53、 Graphical Method 下一节：线性规划的标准型下一节：线性规划的标准型 1.3 线性规划的标准型线性规划的标准型 Standard form of LP Chapter 1 线性规划线性规划 Linear Programming Page 48 2021年6月25日星期五48 v线性规划问题的标准型 mi njx bxa ts xcZ j n j ijij n j jj , 2 , 1 , 2 , 1, 0 . max 1 1 特点：特点： (1) 目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程，且右端常数项约束条件都为等式方程，且

54、右端常数项bi都大于或等于零都大于或等于零 (3) 决策变量决策变量xj为非负。为非负。 Chapter 1 线性规划线性规划 Linear Programming Page 49 2021年6月25日星期五49 通常设通常设A的秩的秩r（A）= m，且，且m n。 即即AX=b中所包含的中所包含的 m个方程式彼此个方程式彼此 独立，没有多余方程，且方程个数小独立，没有多余方程，且方程个数小 于未知量个数。于未知量个数。 Chapter 1 线性规划线性规划 Linear Programming Page 50 2021年6月25日星期五50 q约束条件是不等式转化为等式：“”约束约束 加上松

55、弛变加上松弛变 量量 “”约束约束 减去松弛变量减去松弛变量 q极小化目标函数转化为极大化：极小化目标函数转化为极大化：目标函数系数变号 q变量没有符号限制（变量没有符号限制（unr）转化为变量非负：）转化为变量非负： 没有符号限制的变量用两个非负变量的差表示 q变量为非正转化为变量非负变量为非正转化为变量非负 用添加负号的变量替换原变量，设新变量为正 q右端资源向量为非正（右端资源向量为非正（b 0） 在资源向量所在方程式两边同乘负号 将一般型转化为标准型将一般型转化为标准型 第二章第二章 线性规划线性规划 Chapter 1 线性规划线性规划 Linear Programming Page

56、 51 2021年6月25日星期五51 【例例1.12】将下列线性规划化为标准型将下列线性规划化为标准型 321 3minxxxZ 无符号要求、 321 321 321 321 00 )3(523 )2(3 ) 1 (82 xxx xxx xxx xxx 【解解】（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也取正值也 可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0, 33333 xxxxx其中 1.3 线性规划的标准型线性规划的标准型 Standard form of LP Chapter 1 线性规划线性规划 Linear Programmi

57、ng Page 52 2021年6月25日星期五52 (3)第二个约束条件是第二个约束条件是号，在号，在号号 左左 端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变。也称松驰变 量量 321 3minxxxZ 无符号要求、 321 321 321 321 00 ) 3(523 )2(3 ) 1 (82 xxx xxx xxx xxx 1.3 线性规划的标准型线性规划的标准型 Standard form of LP (2) 第一个约束条件是第一个约束条件是号，在号，在左端左端 加入松驰变量加入松驰变量 (slack variable) x4， x40,化为

58、等式；化为等式； (4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入松左边加入松 驰变量驰变量x6，x60，同时两边乘以，同时两边乘以1。 （5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到 max Z=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。 Chapter 1 线性规划线性规划 Linear Programming Page 53 2021年6月25日星期五53 综合起来得到下列标准型综合起来得到下列标准型 3321 33maxxxxxZ 0 5)(2

59、3 3 82 6543321 63321 53321 43321 xxxxxxx xxxxx xxxxx xxxxx 、 1.3 线性规划的标准型线性规划的标准型 Standard form of LP Chapter 1 线性规划线性规划 Linear Programming Page 54 2021年6月25日星期五54 当某个变量当某个变量xj0时时,令令x/j=xj 。 当某个约束是绝对值不等式当某个约束是绝对值不等式 时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束 974 321 xxx 将其化为两个不等式将其化为两个不等

60、式 974 974 321 321 xxx xxx 再加入松驰变量化为等式。再加入松驰变量化为等式。 1.3 线性规划的标准型线性规划的标准型 Standard form of LP Chapter 1 线性规划线性规划 Linear Programming Page 55 2021年6月25日星期五55 【例例1.13】将下例线性规划化为标准型将下例线性规划化为标准型 无约束、 21 1 21 21 4 5 |max xx x xx xxZ 【解解】 此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。 令令 0 00 00 0 0 00 00 0 22 2 2 2 22