第二章2.5线性规划的应用.ppt

一、使用线性规划方法处理实际问题 必须具备的条件(建模条件)：,优化条件-问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。选择条件-有多种可供选择的可行方案，以便从中选取最优方案。,1.5 线性规划的应用,3）限制条件-达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的。,二、建模步骤：,第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。,第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。,三、管理领域中 几类典型的LP问题,（一）生产组织与计划问题,1.产品计划问题2.产品配套问题3.人力资源问题,1、产品计划问题,问题的一般提法：用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。,如果用，单位产品所需资源数（如原材料、人力、时间等）、所得利润及可供应的资源总量已知，根据有关信息，问应如何组织生产才能使利润最大？,产品计划问题有关信息表,设出产品的计划数，可列出这类问题的数学模型如下：,2、人力资源问题,例1-13 某商场对一周内客流量进行统计分析，按照服务定额得知一周中每天售货人员需求量。若售货员每周工作5天，休息2天，并要求休息时间是连续的，商场应如何安排售货人数，才能够既满足工作需要，又使配备的售货人员最少？,设：x为星期i开始休息的人数，星期日记为x7，则每一天工作的人数应为下一日开始休息的人员直至由下一日算起的第5个工作日，亦即非当日、前天休息的人员总和。,3、产品配套问题,例1-9 某产品由两个零件I和三个零件II组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，根据有关信息，试确定各车间生产每种零件的工作时间，使生产产品的件数最多。,例1-9有关信息表,其中：xij表示第i个车间生产第j个零件的时间 注意Z是非线性表达式！,处理,把,Y,的表达式改写成两个不等式增添到约束条件中去,于是得到该问题的LP模型为：,(二)合理下料问题,在加工业中，经常遇到这类问题。问题的一般提法是：已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件毛坯，问应如何选取合理的下料方法，使得既满足对截出毛坯的数量要求，又使所用的原材料最少（或废料最少）？,解决这类问题一般有两个步骤：,步骤一、按照一定的思路设法列出所有的排料方案（也称下料方案或排料图），当方案很多，甚至无法一一列出时，通常应先确定一些筛选原则，把明显不合理的方案删除，仅仅考虑剩余的为数不太多的方案；步骤二、设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米料头。这是最好的办法吗？,合理套裁肯定会有更好的效果。先设法列出所有的下料方案，思路如图。,7.4,设xi为按第i种方案下料的棒料根数，建立LP模型如下：,（三）合理配料问题,问题的一般提法：由多种原料配置成含有m种成分的产品，已知产品中所含各成分的需要量及每种原料的价格，同时知道各种原料中所含m种成分的数量，要求给出使产品成本最低的配料方案。伙食问题（也称营养问题）、饲料配比问题、化工产品中的混合问题等都属于这类问题。,例、营养问题,要求制定一个既经济又合乎健康标准的食谱 一个简单的例子：现准备采购甲、乙两种食品，表中给出了已知价格及相关的营养成分。最右栏给出了按营养学标准每人每天的最低需要量。问应如何采购食品才能在保证营养要求的前提下花费最省？,营养问题已知数据表,如何设置决策变量？,设x1、x2分别为甲、乙两种食品的采购量，则购买两种食品的总费用为Z=1.2x1+1.9x2，依题意可列出下面的线性规划：,作业,某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米，带轻型炸弹时每升汽油可飞行3千米。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4千米）外，起飞和降落每次各消耗100升。有关数据如表所示。为了使摧毁敌方军事目标的可能性最大，应如何确定飞机轰炸的方案，要求建立这个问题的线性规划模型。,