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