补充：线性规划的应用.ppt

1.4 线性规划的应用 一、使用线性规划方法处理实际问题一、使用线性规划方法处理实际问题 必须具备的条件必须具备的条件( (建模条件建模条件) )： n优化条件-问题的目标有极大化或问题的目标有极大化或 极小化的要求极小化的要求, ,而且能用决策变量的而且能用决策变量的 线性函数来表示。线性函数来表示。 n选择条件-有多种可供选择的可行有多种可供选择的可行 方案，以便从中选取最优方案。方案，以便从中选取最优方案。 3）限制条件-达到目标的条件是有一定限 制的（比如，资源的供应量有限度等） ，而且这些限制可以用决策变量的线性 等式或线性不等式表示出来。 此外，描述问题的决策变量相互之描述问题的决策变量相互之 间应有一定的联系，有可能建立数学关间应有一定的联系，有可能建立数学关 系，即这些系，即这些变量之间是内部相关变量之间是内部相关的。的。 二、建模步骤二、建模步骤： 第一步：设置要求解的决策变量第一步：设置要求解的决策变量。决策变决策变 量选取得当，不仅能顺利地建立模型而且能量选取得当，不仅能顺利地建立模型而且能 方便地求解方便地求解，否则很可能事倍功半。，否则很可能事倍功半。 第二步：找出所有的限制第二步：找出所有的限制，即约束条件，即约束条件， 并用决策变量的线性方程或线性不等式来表并用决策变量的线性方程或线性不等式来表 示示。当限制条件多，背景比较复杂时，可以。当限制条件多，背景比较复杂时，可以 采用图示或表格形式列出所有的已知数据和采用图示或表格形式列出所有的已知数据和 信息，以避免信息，以避免“ “遗漏遗漏” ”或或“ “重复重复” ”所造成的错误所造成的错误 。 第三步：明确目标要求，并用决策变量第三步：明确目标要求，并用决策变量 的线性函数来表示，确定对函数是取极大的线性函数来表示，确定对函数是取极大 还是取极小的要求。还是取极小的要求。 决策变量的非负要求可以根据问题的决策变量的非负要求可以根据问题的 实际意义加以确定。实际意义加以确定。 讨论：这三步的顺序可以颠倒吗？讨论：这三步的顺序可以颠倒吗？ 为什麽？为什麽？ 三、 经济管理领域中 几类典型的LP问题 经济管理领域中有大量的实际问题可以归经济管理领域中有大量的实际问题可以归 结为线性规划问题来研究，这些问题背景不结为线性规划问题来研究，这些问题背景不 同，表现各异，但数学模型却有着完全相同同，表现各异，但数学模型却有着完全相同 的形式。的形式。 尽可能多地掌握一些典型的模型不仅有尽可能多地掌握一些典型的模型不仅有 助于深刻理解线性规划本身的理论和方法，助于深刻理解线性规划本身的理论和方法， 而且有利于灵活地处理千差万别的实际问题而且有利于灵活地处理千差万别的实际问题 ，提高解决实际问题的能力。，提高解决实际问题的能力。 （一） 生产组织与计划问题 1. 1. 产品计划问题产品计划问题 2. 2. 产品配套问题产品配套问题 1、产品计划问题 问题的一般提法：问题的一般提法：用若干种原用若干种原 材料（资源）生产某几种产品，材料（资源）生产某几种产品， 原材料（或资源）供应有一定限原材料（或资源）供应有一定限 制，要求制定一个产品生产计划制，要求制定一个产品生产计划 ，使其在一定数量的资源限制条，使其在一定数量的资源限制条 件下能得到最大的收益。件下能得到最大的收益。 如果用用 ， 单位产品所需资源数（如原材料、人单位产品所需资源数（如原材料、人 力、时间等）、所得利润及可供应的资源力、时间等）、所得利润及可供应的资源 总量已知，如表所示，问应如何组织生产总量已知，如表所示，问应如何组织生产 才能使利润最大？才能使利润最大？ 产品计划问题有关信息表 设出产品的计划数，可列出这类 问题的数学模型如下： 一般的产品计划问题举例 例1-7 ： 某工厂生产A、B两种产品，均需经过两道工序 ，每生产一吨产品A需要经第一道工序加工2小时 ，第二道工序加工3小时；每生产一吨产品B需要 经第一道工序加工3小时，第二道工序加工4小时。 可供利用的第一道工序为12小时，第二道工序为24 小时。 生产产品生产产品B B的同时产出副产品的同时产出副产品C C，每生产一吨产每生产一吨产 品品B B，可同时得到可同时得到2 2吨产品吨产品C C而毋需外加任何费用；而毋需外加任何费用； 副产品副产品C C一部分可以盈利，剩下的只能报废。一部分可以盈利，剩下的只能报废。 出售产品出售产品A A每吨能盈利每吨能盈利400400元、产品元、产品B B每吨能盈每吨能盈 利利10001000元，每销售一吨副产品元，每销售一吨副产品C C能盈利能盈利300300元，而元，而 剩余要报废的则每吨损失剩余要报废的则每吨损失200200元。经市场预测，在元。经市场预测，在 计划期内产品计划期内产品C C最大销量为最大销量为5 5吨。试列出线性规划吨。试列出线性规划 模型，决定模型，决定A A、B B两种产品的产量，使工厂总的利两种产品的产量，使工厂总的利 润最大。润最大。 Y 信息整理： Y 利润与产量的关系图： Y数学模型 ： 设：x1产品A的产量， x2产品B 的产量，x3产品C的销售量，x4 产品C的报废量。依题意，可得 2、产品配套问题 例1-8 某产品由两个零件I和三个 零件II组成，每个零件均可由三个车 间各自生产，但各车间的生产效率和 总工时限制各不相同，表中给出了有 关信息。试确定各车间生产每种零件 的工作时间，使生产产品的件数最多 。 例1-8有关信息表 其中：xij表示第i个车间生产第j个零件的时间 数 注意Z是非线性表达式！ 处理： 于是得到该问题的LP模型为： (二) 合理下料问题 在加工业中，经常遇到这类问题 。 问题的一般提法是：已知某种尺寸的 棒料或板材，需要将其切割成一定数 量既定规格的几种零件毛坯，问应如 何选取合理的下料方法，使得既满足 对截出毛坯的数量要求，又使所用的 原材料最少（或废料最少）？ 解决这类问题一般有两个步骤 ： z步骤一、按照一定的思路设法列出所有的 排料方案（也称下料方案或排料图），当 方案很多，甚至无法一一列出时，通常应 先确定一些筛选原则，把明显不合理的方 案删除，仅仅考虑剩余的为数不太多的方 案； z步骤二、设xi表示按第种方案下料的棒料 根数（或板材块数）i=1,2,n，按照问题 的要求建立LP模型。 例1-9 某厂接受了一批加工定货， 客户要求加工100套钢架，每套由长2.9 米、2.1米和1.5米的圆钢各一根组成。 现在仅有一批长7.4米的棒料毛坯，问 应如何下料，使所用的棒料根数最少 ？ 最简单的处理方法：从一根棒料上截 取2.9米、2.1米和1.5米的棒料各一根，正 好配成一套钢架，100套钢架总共需要 100根棒料毛坯。每根棒料毛坯剩下0.9米 的料头,100根毛坯总共剩90米料头。 这是最好的办法吗？ 合理套裁肯定会有更好的效果。 先设法列出所有的下料方案，思路如图。 排列下料方案思路图 设设x x i i 为按第为按第i i种种方案下料的棒料根数方案下料的棒料根数， 建立LP模型如下： （三） 合理配料问题 问题的一般提法：由多种原料配置成含 有m种成分的产品，已知产品中所含各成 分的需要量及每种原料的价格，同时知道 各种原料中所含m种成分的数量，要求给 出使产品成本最低的配料方案。如：伙食 问题（也称营养问题）、饲料配比问题、 化工产品中的混合问题等都属于这类问题 。 例1-10 营养问题 要求制定一个既经济又合乎健康标准的食 谱。一个简单的例子： 现准备采购甲、乙两种食品，表中给出 了已知价格及相关的营养成分。最右栏 给出了按营养学标准每人每天的最低需 要量。问应如何采购食品才能在保证营 养要求的前提下花费最省？ 表1-2 营养问题已知数据表 设x1、x2分别为甲、乙两种食品的采购量 ，则购买两种食品的总费用为Z=1.2x1+1.9x2 ，依题意可列出下面的线性规划： 营养问题适用范围：营养问题适用范围： & 运动员集训队食谱设计； & & 幼儿园、医院等特殊群体的营养配餐 ； & 机关、学校、企业等企事业单位团体 伙食设计； & & 家庭食谱设计； 小实践选题建议小实践选题建议2 2：为所在班级同学设计为所在班级同学设计 不同要求的食谱不同要求的食谱 对不同对象的营养要求营养要求 从营养学资料和通过医生咨询得到； 各种食品的价格食品的价格 通过不同季节的市场调查获取； 一些特殊要求，比如饮食习惯、偏好等 可通过适当处理，转化为约束条件加入 模型； 资料获取渠道及特殊要求的处理建议：资料获取渠道及特殊要求的处理建议： 例例1-111-11（饲料配比问题）（饲料配比问题）某配合饲料 厂生产以鸡饲料为主的配合饲料，现准 备研制一种新的肉用仔鸡专用饲料肉用仔鸡专用饲料，所 用原料的营养成分和饲养标准见表，希 望这种新饲料能满足肉用仔鸡的喂养需 要又使总成本尽可能低，应如何设计配 比方案？ 已知各种原料的购进价1公斤分别为 :0.314(玉米)、054(豆饼)、0.22（麦麸）、 1.20（鱼粉）、0.40（骨粉）、0.50（鸡促 进素）元。 设每100公斤饲料中配给的玉米、豆 饼、麦麸、鱼粉、骨粉、鸡促进素分别 为x1、x2、x3、x4、x5、x6公斤，则 饲料配比即为x1：x2：x3：x4：x5：x6； 于是，可建立下面的线性规划：可建立下面的线性规划： 是否可以将约束条件两边分别扩大一是否可以将约束条件两边分别扩大一 个倍数再进行计算？个倍数再进行计算？ （四） 运输问题 运输问题大体上可以分为四种类型： 1、产销平衡的运输问题（也称物资调运 问题） 2、产销不平衡的运输问题 3、作物布局问题 一般提法是：在若干块土地上种植若 干种作物，已知各块土地的面积、作物 计划播种面积及单产，问如何安排种植 计划，使总产量最高？ 4、工厂布局问题 一般提法；设有n个原料产地A1、A2、A n生 产某种原料分别为ai个单位，同时又分别需要成品 bi个单位（i=1，2，n），而一个单位成品需c个 单位原料制成。若在Ai地设加工厂，则产品加工费 用为di元/单位，在Ai地设厂对生产规划有一定的限 制生产成品的数量最多为li个单位，最少为fi个 单位。原料的单位运价及成品的单位运价均为已知 ，问应在何地设厂、生产多少成品才能既满足需要 又使生产费用（包括原料和成品运费、成品加工费 ）最省？ 例1-12 某油田通过输油管道向港口输送 原油，中间有4个泵站，每段管道上的 输送能力如图所示，已知泵站没有储存 能力，求这个系统的最大输送能力。 （五）最大流量问题 泵站4 泵站3油田S 泵站2 泵站1 码头t 5 12 4 8 11 9 6 7 10 设从各点往其它点的输送量如下表所示设从各点往其它点的输送量如下表所示 出发点 到达点 输送量 S S 泵站1 泵站1 泵站2 泵站2 泵站3 泵站3 泵站