线性规划及其基本理论

运筹学Operations Research王 慧东南大学经济管理学院电子商务系暨管理工程研究 wh_1线性规划及其基本理论p 线性规划概述p 线性规划问题p 线性规划数学模型一般模型标准模型p 线性规划解的概念可行解、最优解基阵、基解、基可行解p 线性规划的基本性质2线性规划概述p 线性规划（ Linear Programming，简记为 LP）是运筹学中的一个最重要、应用最广泛的分支。 p 线性规划及其通用解法 -单纯形法一般认为是美国学者丹捷格（ G.Dantzig）在 1947年研究美国空军军事规划时提出的。p 苏联学者康托洛维奇在 1939年解决工业生产组织与计划问题时就提出类似线性规划的模型及解法；康托洛维奇的工作当时没有被重视，但直到 1960年康托洛维奇再次发表 最佳资源利用的经济计算 一书后，才受到重视。 p 一些常见的带有 Spreadsheet的软件，如： Excel、Lotus1-2-3等，均有内置的线性规划求解功能。p 最优化问题求解软件，如： Lindo、 Lingo、 Matlab等。3线性规划问题提出 在生产管理和经营活动中经常会提出这样一类问题：如何利用有限的人力、物力、财力等资源，取得最好的效果。例如： p 配载问题一交通工具，运输几种不同体积、重量的物资，如何装配， 所运的物资最多？p 下料问题用圆钢制造长度不等的机轴，如何下料，所剩的余料最少？p 生产计划问题企业生产 A、 B两种电器产品，两种产品的市场需求状况可以确定，按当前的定价可确保所有产品均能销售出去。企业可提供的两种原材料和劳动时间的数量是有限的。产品 A与产品 B各应生产多少，可使企业总利润最大 ?4线性规划问题提出上述这些问题有如下共同特点：p 问题解决要满足一定条件，称为 约束条件 ；p 问题有多个满足条件的解决方案；p 问题解决有明确的目标要求，对应不同方案有不同目标值，可表示成 目标函数 。5何谓线性规划问题p 最优化问题我们称如下一般问题： “在一定约束条件下，求目标函数的最大或最小值 ”为最优化问题，用数学模型描述的最优化问题，称为数学规划问题。p 线性规划问题在最优化问题中，如果约束条件与目标函数均是线性的，我们就称之为线性规划问题。 6线性规划问题 的三个要素p 决策变量 n 决策 问题待定的量值称为决策变量。n 决策变量的取值有时要求非负。p 约束条件n 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。n 约束条件是决策方案可行的保障。n LP的约束条件，都是决策变量的线性函数。p 目标函数n 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。n 目标函数是决策变量的线性函数。n 有的目标要实现极大，有的则要求极小。7线性规划数学模型例例 生产计划问题生产计划问题 某厂生产甲 乙 两种产品，各自的零部件分别在 A、 B车间生产，最后都需在 C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。 3 5单位产品获利8 12361 23 23 4ABC生产能力工时单耗甲 乙产品车间8线性规划数学模型p建立数学模型的步骤：Step1 分析实际问题；Step2 确定决策变量；Step3 找出约束条件；Step4 确定目标函数；Step5 整理、写出数学模型。9【 例 1.1】 某市今年要兴建大量住宅 ,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大 (即求安排各住宅多少 m2)， 求建造方案。水泥(公斤 /m2)4000(千工日 )147000(千块 )150000(吨 )20000(吨 )110000(千元 )资源限量3.518025120大模 住宅3.019030135壁板住宅4.521011012105砖混住宅人工(工日 /m2)砖(块 /m2)钢材(公斤 /m2)造价(元 /m2)资源住宅体系线性规划问题举例10【 例 1.2】 最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备 A、 B上加工，需要消耗材料 C、 D， 按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表 1.1所示。已知在计划期内设备的加工能力各为 200台时，可供材料分别为 360、 300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为 40、 30、 50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？线性规划问题举例产 品资 源甲乙 丙 现 有 资 源设备 A 3 1 2 200设备 B 2 2 4 200材料 C 4 5 1 360材料 D 2 3 5 300利 润 （元 /件） 40 30 50产品资源消耗表11【 例 1.3】 某商场决定：营业员每周连续工作 5天后连续休息 2天，轮流休息。根据统计，商场每天需要的营业员如表 1.2所示。表 1.2 营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。 星期 需要人数 星期 需要人数一 300 五 480二 300 六 600三 350 日 550四 400线性规划问题举例12【 例 1.4】 合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是 1.5， 1， 0.7（ m），这些轴需要用同一种圆钢来做，圆钢长度为 4 m。现在要制造 1000辆汽车，最少要用多少圆钢来生产这些轴？ 线性规划问题举例13注意 ：（） 求下料方案时应注意，余料不能超过最短毛坯的长度；（）最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案 。（）如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。14【 例 1.5】 配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于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线性规划问题举例15解 : 设 xj（ j=1,2， ， 5） 是第 j 种矿石数量，得到下列线性规划模型 注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。 16【 例 1.6】 投资问题。某投资公司在第一年有 200万元资金，每年都有如下的投资方案可供考虑采纳： “假使第一年投入一笔资金，第二年又继续投入此资金的50% ，那么到第三年就可回收第一年投入资金的一倍金额 ”。投资公司决定最优的投资策略使第六年所掌握的资金最多。 线性规划问题举例17【 例 1.7】 均衡配套生产问题。某产品由 2件甲、 3件乙零件组装而成。两种零件必须经过设备 A、 B上加工，每件甲零件在 A、 B上的加工时间分别为 5分钟和 9分钟，每件乙零件在 A、 B上的加工时间分别为 4分钟和 10分钟。现有 2台设备 A和 3台设备 B， 每天每台可供加工时间为 8小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间 1小时。怎样安排设备的加工时间使每天产品的产量最大。线性规划问题举例18线性规划数学模型一般形式假定线性规划问题有 n个决策变量， m个约束条件。一般地，线性规划问题数学模型中可表示成如下形式：19线性规划数学模型标准形式p 线性规划问题的数学模型有各种不同的形式，如n 目标函数有极大化和极小化；n 约束条件有 “”、 “”和 “ ”三种情况 ；n 决策变量一般有非负性要求，有的则没有。p 为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：n 目标函数极大化，n 约束条件为等式，n 右端常数项 bi0，n 决策变量非负。20线性规划数学模型标准形式21线性规划数学模型标准形式22线性规划数学模型标准形式23线性规划数学模型标准形式24如何化线性规划标准形式25如何化线性规划标准形式例 1.8 min z = x1 +2 x2 -3 x3x1 +2 x2 - x3 52x1 +3 x2 - x3 6-x1 - x2 + x3 -2 x1 0, x3 026【 例 1.9】 将下列线性规划化为标准型 如何化线性规划标准形式27如何化线性规划标准形式28当某个变量 xj0时 ,令 x/j= xj 。 当某个约束是绝对值不等式时，将绝对值不