-线性规划的应用.ppt

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