第1章线性规划模型和单纯形法

运筹学Operations Research第 1 章 线性规划模型和单纯形法Linear Programming and Simplex Method1.1 LP的数学模型 及 标准型1.2 图解法 1.3 单纯形法1. 理解什么是线性规划模型 ， 掌握线性规划在管理及生产中的应用2. 掌握线性规划数学模型的组成及其特征3. 清楚线性规划数学模型的一般表达式。1.1 线性规划 数学模型 Mathematical Model ofLinear Programming线性规划 （ Linear Programming,缩写为 LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。【 例 1.1】 最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备 A、 B上加工，需要消耗材料 C、 D， 按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表 1.1所示。已知在计划期内设备的加工能力各为 200台时，可供材料分别为 360、 300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为 40、 30、 50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？1.1.1 应用模型举例产 品资 源甲乙 丙 现 有 资 源设备 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 产品资源消耗【 解 】 设 x1、 x2、 x3 分别为甲、乙、丙三种产品的产量数学模型为：产 品资 源甲乙 丙 现 有 资源设备 A 3 1 2 200设备 B 2 2 4 200材料 C 4 5 1 360材料 D 2 3 5 300利 润 （元 /件） 40 30 50最优解 X=(50,30,10);Z=3400目标函数资源约束线性规划的数学模型由决策变量 Decision variables 目标函数 Objective function约束条件 Constraints构成。称为三个要素 。n其特征是：n1解决问题的 目标函数目标函数 是多个决策变量的 线性 函数，通常是求最大值或 最小值；n2解决问题的 约束条件约束条件 是一组多个决策变量的 线性 不等式或等式。怎样辨别一个模型是线性规划模型？【 例 1.2】 某商场决定：营业员每周连续工作 5天后连续休息 2天，轮流休息。根据统计，商场每天需要的营业员如表 1.2所示。表 1.2 营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。 星期 需要人数 星期 需要人数一 300 五 480二 300 六 600三 350 日 550四 400【 解 】 设 xj (j=1， 2， ， 7)为休息 2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为 星期需要人数星期需要人数一 300 五 480二 300 六 600三 350 日 550四 400目标函数：总人数最少约束条件：上班人数大于每天需要人数1 X1 0 C1 404 = 300 1042 X2 67 C2 301 = 300 13 X3 146 C3 350 = 350 04 X4 170 C4 400 = 400 05 X5 97 C5 480 = 480 06 X6 120 C6 600 = 600 07 X7 17 C7 550 = 550 0最优解： Z 617（ 人）【 例 1.3】 合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是 1.5， 1， 0.7（ m）， 这些轴需要用同一种圆钢来做，圆钢长度为 4 m。 现在要制造 1000辆汽车，最少要用多少圆钢来生产这些轴？ 【 解 】 这是个条材下料问题 ，设切口宽度为零。 设一根圆钢切割成甲、乙、丙三种轴的根数分别为 y1， y2， y3,则切割方式可用不等式 1.5y1+y2+0.7y34表示，求这个不等式关于 y1， y2， y3的非负整数解。象这样的非负整数解共有 10组，也就是有 10种下料方式，如表 1.3所示。表 1 3 下料方案 方案规 格1 2 3 4 5 6 7 8 9 10 需求量y1(根 ) 2 2 1 1 1 0 0 0 0 0 1000y2 1 0 2 1 0 4 3 2 1 0 1000y3 0 1 0 2 3 0 1 2 4 5 1000余料（ m）0 0.3 0.5 0.1 o.4 0 0.3 0.6 0.2 0.5设 xj ( j = 1,2,10) 为第 j种下料方案所用圆钢的根数。则用料最少数学模型 为为 :方案规 格1 2 3 4 5 6 7 8 9 10 需求量y1(根 ) 2 2 1 1 1 0 0 0 0 0 1000y2 1 0 2 1 0 4 3 2 1 0 1000y3 0 1 0 2 3 0 1 2 4 5 1000余料（ m） 0 0.3 0.5 0.1 o.4 0 0.3 0.6 0.2 0.5求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案 。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。1 X1 5002 X2 03 X3 04 X4 05 X5 06 X6 62.57 X7 08 X8 09 X9 25010 X10 0Z 812.5最优解：【 例 1.4】 配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于 28% ，锌不多于 15% ，铅恰好 10% ，镍要界于35%55% 之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表 1.4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。表 1.4 矿石的金属含量合金矿 石 锡 % 锌 % 铅 % 镍 % 杂质 费 用（元 /t ）1 25 10 10 25 30 3402 40 0 0 30 30 2603 0 15 5 20 60 1804 20 20 0 40 20 2305 8 5 15 17 55 190解 : 设 xj（ j=1,2， ， 5） 是第 j 种矿石数量，得到下列线性规划模型 矿 石 锡 % 锌 % 铅 % 镍 % 杂质 费 用（元 /t ）1 25 10 10 25 30 3402 40 0 0 30 30 2603 0 15 5 20 60 1804 20 20 0 40 20 2305 8 5 15 17 55 190注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。1 X1 02 X2 0.33333 X3 04 X4 0.58335 X5 0.6667最优解： Z=347.5第五年： (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， 整理后得到下列线性规划模型 【 解 】 设 x1： 第一年的投资； x2： 第一年的保留资金x3： 第二年新的投资； x4： 第二年的保留资金x5： 第三年新的投资； x6： 第三年的保留资金x7： 第四年新的投资 x8： 第四年的保留资金x9： 第五年的保留资金【 例 1.5】 投资问题。某投资公司在第一年有 200万元资金，每年都有如下的投资方案可供考虑采纳： “假使第一年投入一笔资金，第二年又继续投入此资金的 50% ，那么到第三年就可回收第一年投入资金的一倍金额 ”。投资公司决定最优的投资策略使第六年所掌握的资金最多。1 X1 55.28462 X2 144.71553 X3 117.07324 X4 05 X5 52.03256 X6 07 X7 208.13018 X8 09 X9 0最优解： Z 416.26万元x1： 第一年的投资； x2： 第一年的保留资金x3： 第二年新的投资； x4： 第二年的保留资金x5： 第三年新的投资； x6： 第三年的保留资金x7： 第四年新的投资 x8： 第四年的保留资金x9： 第五年的保留资金 【 例 1.6】 均衡配套生产问题。某产品由 2件甲、 3件乙零件组装而成。两种零件必须经过设备 A、 B上加工，每件甲零件在 A、 B上的加工时间分别为 5分钟和 9分钟，每件乙零件在 A、 B上的加工时间分别为 4分钟和 10分钟。现有 2台设备 A和 3台设备 B， 每天可供加工时间为 8小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间 1小时。怎样安排设备的加工时间使每天产品的产量最大。【 解 】 设 x1、 x2为每天加工甲、乙两种零件的件数，则产品的产量是设备 A、 B每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备 1小时的约束为 目标函数线性化。产品的产量 y等价于整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式【 例 1.7】 （书上 P4例 1.1-1题）饼干生产问题。某厂生产两类饼干，需搅拌机 A1， 成形机 A2 ， 烘箱 A3三种设备，每天的所需机时及机时限制，利润指标如下表，问如何制订生产计划，可使获得最高利润？【 解 】 设 x1、 x2为每天生产 、 两种饼干的产量（单位：吨），则目标函数是产品资源 每天现有工时搅拌机 A1 3 5 15成形机 A2 2 1 5烘箱 A3 2 2 11利润 /（百元 /吨） 5 4约束条件有：搅拌机约束 成形机约束烘箱约束 非负约束本 问题的数学模型【 例 1.8】 （书上 P6例 1.1-2题）运输问题。总公司收到上海 B1， 青岛B2 ， 西安 B3三家商场的电机订单，需求分别为 100台， 80台， 90-120台，现有北京 A1， 武汉 A2二个仓库，库存分别为 200台， 150台，所需运费如下表，问如何调运电机，可使总运费最少？B1 B2 B3 库存A1 15 21 18 200A2 20 25 16 150需求 100 80 90-120 【 解 】 设 xij 为从仓库 Ai 调到商场 Bj 的电机数量（ i=1,2, j=1,2,3），则目标函数是库存约束需求约束非负约束问题的数学模型小结：建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握 3个要素： 研究的问题是求什么，即设置决策变量； 问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值； 限制达到目标的条件是什么，即建立约束条件。作业： 第 1次作业 .doc1.1.2 线性规划的一般模型及标准形一般地，假设线性规划数学模型中，有 m个约束，有 n个决策变量xj, j=1,2, n， 目标函数的变量系数用 cj表示 , cj称为 价值系数