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