补充线性规划应用.pptx

《补充线性规划应用.pptx》由会员分享，可在线阅读，更多相关《补充线性规划应用.pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3）限限制制条条件件-达达到到目目标标的的条条件件是是有有一一定定限限制制的的（比比如如，资资源源的的供供应应量量有有限限度度等等），而而且且这这些些限限制制可可以以用用决决策策变变量量的的线线性性等等式或线性不等式表示出来。式或线性不等式表示出来。此此外外，描描述述问问题题的的决决策策变变量量相相互互之之间间应应有有一一定定的的联联系系，有有可可能能建建立立数数学学关关系，即这些系，即这些变量之间是内部相关变量之间是内部相关的。的。第1页/共42页 二、建模步骤二、建模步骤：第第一一步步：设设置置要要求求解解的的决决策策变变量量。决决策策变变量量选选取取得得当当，不不仅仅能能顺顺利利地地建建

2、立立模模型型而而且且能方便地求解能方便地求解，否则很可能事倍功半。，否则很可能事倍功半。第第二二步步：找找出出所所有有的的限限制制，即即约约束束条条件件，并并用用决决策策变变量量的的线线性性方方程程或或线线性性不不等等式式来来表表示示。当当限限制制条条件件多多，背背景景比比较较复复杂杂时时，可可以以采采用用图图示示或或表表格格形形式式列列出出所所有有的的已已知知数数据据和信息，以避免和信息，以避免“遗漏遗漏”或或“重复重复”所造成的错误。所造成的错误。第2页/共42页 第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意

3、义加以确定。讨论：这三步的顺序可以颠倒吗？为什麽？第3页/共42页三、三、经济管理领域中经济管理领域中 几类几类典型的典型的LPLP问题问题 经经济济管管理理领领域域中中有有大大量量的的实实际际问问题题可可以以归归结结为为线线性性规规划划问问题题来来研研究究，这这些些问问题背景不同，表现各异，但数学模型却有着完全相同的形式。题背景不同，表现各异，但数学模型却有着完全相同的形式。尽尽可可能能多多地地掌掌握握一一些些典典型型的的模模型型不不仅仅有有助助于于深深刻刻理理解解线线性性规规划划本本身身的的理理论论和和方方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。法，而且有利于灵

4、活地处理千差万别的实际问题，提高解决实际问题的能力。第4页/共42页（一）（一）生产组织与计划问题生产组织与计划问题1.产品计划问题2.产品配套问题第5页/共42页1、产品计划问题 问题的一般提法：用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。第6页/共42页 如果用 ，单位产品所需资源数（如原材料、人力、时间等）、所得利润及可供应的资源总量已知，如表所示，问应如何组织生产才能使利润最大？第7页/共42页产品计划问题有关信息表第8页/共42页设出产品的计划数，可列出这类问题的数学模型如下：第9页/

5、共42页一般的产品计划问题举例例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元元、产产品品

6、B B每每吨吨能能盈盈利利10001000元元，每每销销售售一一吨吨副副产产品品C C能能盈盈利利300300元元，而而剩剩余余要要报报废废的的则则每每吨吨损损失失200200元元。经经市市场场预预测测，在在计计划划期期内内产产品品C C最最大大销销量量为为5 5吨吨。试试列列出出线线性性规规划划模模型型，决决定定A A、B B两两种种产产品品的的产产量量，使使工工厂厂总总的的利利润润最大。最大。第10页/共42页Y信息整理：第11页/共42页Y利润与产量的关系图：第12页/共42页Y数学模型：设：x1产品A的产量，x2产品B的产量，x3产品C的销售量，x4产品C的报废量。依题意，可得第13页

7、/共42页2、产品配套问题 例1-8某产品由两个零件I和三个零件II组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，表中给出了有关信息。试确定各车间生产每种零件的工作时间，使生产产品的件数最多。第14页/共42页例1-8有关信息表其中：xij表示第i个车间生产第j个零件的时间数注意Z是非线性表达式！第15页/共42页处理：第16页/共42页于是得到该问题的LP模型为：第17页/共42页 (二二)合理下料问题合理下料问题 在加工业中，经常遇到这类问题。问题的一般提法是：已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件毛坯，问应如何选取合理的下料方法

8、，使得既满足对截出毛坯的数量要求，又使所用的原材料最少（或废料最少）？第18页/共42页解决这类问题一般有两个步骤：z步骤一、按照一定的思路设法列出所有的排料方案（也称下料方案或排料图），当方案很多，甚至无法一一列出时，通常应先确定一些筛选原则，把明显不合理的方案删除，仅仅考虑剩余的为数不太多的方案；z步骤二、设xi表示按第种方案下料的棒料根数（或板材块数）i=1,2,n，按照问题的要求建立LP模型。第19页/共42页例1-9某厂接受了一批加工定货，客户要求加工100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成。现在仅有一批长7.4米的棒料毛坯，问应如何下料，使所用的棒料根数最

9、少？第20页/共42页 最简单的处理方法：从一根棒料上截取2.9米、2.1米和1.5米的棒料各一根，正好配成一套钢架，100套钢架总共需要100根棒料毛坯。每根棒料毛坯剩下0.9米的料头,100根毛坯总共剩90米料头。这是最好的办法吗？合理套裁肯定会有更好的效果。先设法列出所有的下料方案，思路如图。第21页/共42页排列下料方案思路图第22页/共42页设xi为按第i种方案下料的棒料根数，建立LP模型如下：第23页/共42页 （三）（三）合理配料问题合理配料问题 问题的一般提法：由多种原料配置成含有m种成分的产品，已知产品中所含各成分的需要量及每种原料的价格，同时知道各种原料中所含m种成分的数量

10、，要求给出使产品成本最低的配料方案。如：伙食问题（也称营养问题）、饲料配比问题、化工产品中的混合问题等都属于这类问题。第24页/共42页例1-10营养问题 要求制定一个既经济又合乎健康标准的食谱。一个简单的例子：现准备采购甲、乙两种食品，表中给出了已知价格及相关的营养成分。最右栏给出了按营养学标准每人每天的最低需要量。问应如何采购食品才能在保证营养要求的前提下花费最省？第25页/共42页表1-2营养问题已知数据表第26页/共42页设x1、x2分别为甲、乙两种食品的采购 量，则 购 买 两 种 食 品 的 总 费 用 为Z=1.2x1+1.9x2，依题意可列出下面的线性规划：第27页/共42页

11、营养问题适用范围：&运动员集训队食谱设计；&幼儿园、医院等特殊群体的营养配餐；&机关、学校、企业等企事业单位团体伙食设计；&家庭食谱设计；小小实实践践选选题题建建议议2 2：为为所所在在班班级级同同学学设设计计不同要求的食谱不同要求的食谱第28页/共42页对不同对象的营养要求从营养学资料和通过医生咨询得到；各种食品的价格通过不同季节的市场调查获取；一些特殊要求，比如饮食习惯、偏好等可通过适当处理，转化为约束条件加入模型；资料获取渠道及特殊要求的处理建议：第29页/共42页 例1-11（饲料配比问题）某配合饲料厂生产以鸡饲料为主的配合饲料，现准备研制一种新的肉用仔鸡专用饲料，所用原料的营养成分和

12、饲养标准见表，希望这种新饲料能满足肉用仔鸡的喂养需要又使总成本尽可能低，应如何设计配比方案？第30页/共42页第31页/共42页已知各种原料的购进价1公斤分别为:0.314(玉米)、054(豆饼)、0.22（麦麸）、1.20（鱼粉）、0.40（骨粉）、0.50（鸡促进素）元。第32页/共42页 设每100公斤饲料中配给的玉米、豆饼、麦麸、鱼粉、骨粉、鸡促进素分别为x1、x2、x3、x4、x5、x6公斤，则饲料配比即为x1：x2：x3：x4：x5：x6；于是，可建立下面的线性规划：第33页/共42页是否可以将约束条件两边分别扩大一个倍数再进行计算？是否可以将约束条件两边分别扩大一个倍数再进行计算

13、？第34页/共42页（四）（四）运输问题运输问题运输问题大体上可以分为四种类型：1、产销平衡的运输问题（也称物资调运问题）2、产销不平衡的运输问题3、作物布局问题一般提法是：在若干块土地上种植若干种作物，已知各块土地的面积、作物计划播种面积及单产，问如何安排种植计划，使总产量最高？第35页/共42页4、工厂布局问题 一般提法；设有n个原料产地A1、A2、An生产某种原料分别为ai个单位，同时又分别需要成品bi个单位（i=1，2，n），而一个单位成品需c个单位原料制成。若在Ai地设加工厂，则产品加工费用为di元/单位，在Ai地设厂对生产规划有一定的限制生产成品的数量最多为li个单位，最少为fi个

14、单位。原料的单位运价及成品的单位运价均为已知，问应在何地设厂、生产多少成品才能既满足需要又使生产费用（包括原料和成品运费、成品加工费）最省？第36页/共42页例1-12 某油田通过输油管道向港口输送原油，中间有4个泵站，每段管道上的输送能力如图所示，已知泵站没有储存能力，求这个系统的最大输送能力。（五）最大流量问题（五）最大流量问题第37页/共42页泵站4泵站3油田S泵站2泵站1码头t5 12 48 119 6 7 10第38页/共42页 设从各点往其它点的输送量如下表所示 出发点 到达点 输送量SS泵站1泵站1泵站2泵站2泵站3泵站3泵站4泵站1泵站2泵站3码头t泵站3泵站4泵站4码头t码头tx1x2x3x4x5x6x7x8x9第39页/共42页依题意：目标函数为输送原油的总量；约束条件有两类:一类是管道上的流量约束；另一类是每个中间泵站上的平衡约束，即中间泵站上的原油流入量和流出量相等 根据上述分析建立线性规划模型如下：第40页/共42页1号泵站平衡约束2号泵站平衡约束3号泵站平衡约束4号泵站平衡约束相应弧上的约束第41页/共42页感谢您的观看！第42页/共42页