第4章--线性规划在工商管理中的应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,第四章 线性规划在工商管理中的应用,1,人力资源分配的问题,2,生产计划的问题,3,套裁下料问题,4,配料问题,5,投资问题,2,1,人力资源分配的问题,例,1,某昼夜服务的公交线路每天各时间段内所需司机,和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并,连续工作八小时，问该公交线路怎样安排司机和乘务人员，,既能满足工作需要，又配备最少司机和乘务人员,?,3,1,人力资源分配的问题,解：设,x,i,表示第,i,班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。,目标函数：,Min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,约束条件：,s.t.,x,1,+,x,6,60,x,1,+,x,2,70,x,2,+,x,3,60,x,3,+,x,4,50,x,4,+,x,5,20,x,5,+,x,6,30,x,1,x,2,x,3,x,4,x,5,x,6,0,4,1,人力资源分配的问题,例,2,一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作,5,天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,5,1,人力资源分配的问题,解：设,x,i,(i=1,2,7),表示星期一至日开始休息的人数,这样我们建立如下的数学模型。,目标函数：,Min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,+,x,7,约束条件：,s.t.,x,1,+,x,2,+,x,3,+,x,4,+,x,5,28,x,2,+,x,3,+,x,4,+,x,5,+,x,6,15,x,3,+,x,4,+,x,5,+,x,6,+,x,7,24,x,4,+,x,5,+,x,6,+,x,7,+,x,1,25,x,5,+,x,6,+,x,7,+,x,1,+,x,2,19,x,6,+,x,7,+,x,1,+,x,2,+,x,3,31,x,7,+,x,1,+,x,2,+,x,3,+,x,4,28,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,6,一、使用线性规划方法处理实际问题 必须具备的条件,(,建模条件,),：,优化条件,-,问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。,选择条件,-,有多种可供选择的可行方案，以便从中选取最优方案。,7,3,）,限制条件,-,达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。,此外，,描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些,变量之间是内部相关,的。8,二、建模步骤,：,第一步：设置要求解的决策变量,。,决策变量选取得当，不仅能顺利地建立模型而且能方便地求解,，否则很可能事倍功半。,第二步：找出所有的限制,，即约束条件，,并用决策变量的线性方程或线性不等式来表示,。当限制条件多，背景比较复杂时，可以,采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”,所造成的错误。,9,第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。,决策变量的非负要求可以根据问题的实际意义加以确定。,讨论：这三步的顺序可以颠倒吗？,为什麽？,10,1,、产品计划问题,问题的一般提法：,用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。,11,如果,用,，,单位产品所需资源数（如原材料、人力、时间等）、所得利润及可供应的资源总量已知，如表所示，问应如何组织生产才能使利润最大？,12,产品计划问题有关信息表,13,设出产品的计划数，可列出这类问题的数学模型如下,：,14,一般的产品计划问题举例,：,某工厂生产,A,、,B,两种产品，均需经过两道工序，每生产一吨产品,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,两种产品的产量，使工厂总的利润最大。,15,信息整理：,16,利润与产量的关系图：,17,数学模型：,设：,x,1,产品,A,的产量，,x,2,产品,B,的产量，,x,3,产品,C,的销售量，,x,4,产品,C,的报废量。依题意，可得,18,2,、产品配套问题,例,1-8,某产品由两个零件,I,和三个零件,II,组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，表中给出了有关信息。试确定各车间生产每种零件的工作时间，使生产产品的件数最多。,19,例,1-8,有关信息表,其中：,x,ij,表示第,i,个车间生产第,j,个零件的时间数,注意,Z,是非线性表达式！,20,处理：,21,于是得到该问题的,LP,模型为：,22,2,生产计划的问题,例,3,某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,23,2,生产计划的问题,解：设,x,1,x,2,x,3,分别为三道工序都由本公司加工的甲、乙、丙三种,产品的件数，,x,4,x,5,分别为由外协铸造再由本公司加工和装配的甲、乙两,种产品的件数。,求,x,i,的利润：利润,=,售价,-,各成本之和,产品甲全部自制的利润,=23-(3+2+3)=15,产品甲铸造外协，其余自制的利润,=23-(5+2+3)=13,产品乙全部自制的利润,=18-(5+1+2)=10,产品乙铸造外协，其余自制的利润,=18-(6+1+2)=9,产品丙的利润,=16-(4+3+2)=7,可得到,x,i,（,i=1,2,3,4,5,）的利润分别为,15,、,10,、,7,、,13,、,9,元。,24,2,生产计划的问题,通过以上分析,可建立如下的数学模型,:,目标函数,：,Max 15,x,1,+10,x,2,+7,x,3,+13,x,4,+9,x,5,约束条件,：,5,x,1,+10,x,2,+7,x,3,8000,6,x,1,+4,x,2,+8,x,3,+6,x,4,+4,x,5,12000,3x,1,+2,x,2,+2,x,3,+3,x,4,+2,x,5,10000,x,1,x,2,x,3,x,4,x,5,0,25,2,生产计划的问题,例,4,永久机械厂生产,、,、,三种产品，均要经过,A,、,B,两,道工序加工。设有两种规格的设备,A,1,、,A,2,能完成,A,工序；有三种规格的设备,B,1,、,B,2,、,B,3,能完成,B,工序。,可在,A,、,B,的任何规格的设备上加工；,可在任意规格的,A,设备上加工，但对,B,工序，只能在,B,1,设备上加工；,只能在,A,2,与,B,2,设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,26,2,生产计划的问题,解：设,x,ijk,表示第,i,种产品，在第,j,种工序上的第,k,种设备上加工的数量。建立如下的数学模型,:,s.t.5,x,111,+10,x,211,6000,（设备,A,1,）,7,x,112,+9,x,212,+12,x,312,10000,（设备,A,2,）,6,x,121,+8,x,221,4000,（设备,B,1,）,4,x,122,+11,x,322,7000,（设备,B,2,）,7,x,123,4000,（设备,B,3,）,x,111,+,x,112,-,x,121,-,x,122,-,x,123,=0,（,产品在,A,、,B,工序加工的数量相等）,x,211,+,x212,-,x,221,=0,（,产品在,A,、,B,工序加工的数量相等）,x,312,-,x,322,=0,（,产品在,A,、,B,工序加工的数量相等）,x,ijk,0 ,i=1,2,3;j=1,2;k=1,2,3,27,2,生产计划的问题,目标函数为计算利润最大化，利润的计算公式为：,利润,=,（销售单价,-,原料单价）*产品件数,之和,-,（每台时的设备费用*设备实际使用的总台时数）之和。,这样得到目标函数：,Max(1.25-0.25)(x,111,+x,112,)+(2-0.35)x,221,+(2.80-0.5)x,312,300/6000(5x,111,+10 x,211,)-321/10000(7x,112,+9x,212,+12x,312,)-,250/4000(6x,121,+8x,221,)-783/7000(4x,122,+11x,322,)-200/4000(7x,123,).,经整理可得：,Max0.75,x,111,+0.7753,x,112,+1.15,x,211,+1.3611,x,212,+1.9148,x,312,-0.375,x,121,-0.5,x,221,-0.4475,x,122,-1.2304,x,322,-0.35,x,123,28,合理下料问题,在加工业中，经常遇到这类问题。,问题的一般提法是,：,已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件毛坯，问应如何选取合理的下料方法，使得既满足对截出毛坯的数量要求，又使所用的原材料最少（或废料最少）？,29,解决这类问题一般有两个步骤：,步骤一,、,按照一定的思路设法列出所有的,排料方案,（也称下料方案或排料图），当方案很多，甚至无法一一列出时，通常应先,确定一些筛选原则,，把明显不合理的方案删除，仅仅考虑剩余的为数不太多的方案；,步骤二,、,设,x,i,表示按第种方案下料的棒料根数（或板材块数）,i=1,2,n,，按照问题的要求建立,LP,模型,。,30,例,某厂接受了一批加工定货，客户要求加工,100,套钢架，每套由长,2.9,米、,2.1,米和,15,米的圆钢各一根组成。现在仅有一批长,7.4,米的棒料毛坯，问应如何下料，使所用的棒料根数最少？,31,最简单的处理方法：,从一根棒料上截取,2.9,米、,2.1,米和,1.5,米的棒料各一根，正好配成一套钢架，,100,套钢架总共需要,100,根棒料毛坯。每根棒料毛坯剩下,0.9,米的料头,100,根毛坯总共剩,90,米料头。,这是最好的办法吗？,合理套裁,肯定会有更好的效果。,先设法列出所有的下料方案,，思路如图。,32,排列下料方案思路图,33,设,x,i,为按第,i,种方案下料的棒料根数,，,建立,LP,模型如下：,34,3,套裁下料问题,例,5,某工厂要做,100,套钢架，每套用长为,2.9 m,2.1 m,1.5 m,的圆钢各一根。已知原料每根长,7.4 m,，问：应如何下料，可使所用原料最省？,解：共可设计下列,5,种下料方案，见下表,设,x,1,x,2,x,3,x,4,x,5,分别为上面,5,种方案下料的原材料根数。这样我们建立如下的数学模型。,目标函数：,Min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,约束条件：,s.t.,x,1,+2,x,2,+,x,4,100,2,x,3,+2,x,4,+,x,5,100,3,x,1,+,x,2,+2,x,3,+3,x,5,100,x,1,x,2,x,3,x,4,x,5,0,35,用“管理运筹学”软件计算得出最优下料方案：按方案,1,下料,30,根；按方案,2,下料,10,根；按方案,4,下料,50,根。,即,x,1,=30;,x,2,=10,；,x,3,=0,；,x,4,=50,；,x,5,=0,；,只需,90,根原材料就可制造出,100,套钢架。,注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,3,套裁下料问题,36,合理配料问题,问题的一般提法：由多种原料配置成含有,m,种成分的产品，已知产品中所含各成分的需要量及每种原料的价格，同时知道各种原料中所含,m种成分的数量，要求给出,使产品成本最低的配料方案,。如：,伙食问题,（也称营养问题）、,饲料配比问题,、化工产品中的,混合问题,等都属于这类问题。,37,例营养问题,要求制定一个既经济又合乎健康标准的食谱,。一个简单的例子：,现准备采购甲、乙两种食品，表中给出了已知价格及相关的营养成分。最右栏给出了按营养学标准每人每天的最低需要量。问应如何采购食品才能在保证营养要求的前提下花费最省？,38,表,1-2,营养问题已知数据表,39,设,x,1,、,x,2,分别为甲、乙两种食品的采购量，则购买两种食品的总费用为,Z=1.2x,1,+1.9x,2,，,依题意可列出下面的线性规划：,40,营养问题适用范围：,&,运动员集训队食谱设计；,&,幼儿园、医院等特殊群体的营养配餐；,&,机关、学校、企业等企事业单位团体伙食设计；,&,家庭食谱设计,；,小实践选题建议,2,：,为所在班级同学设计不同要求的食谱,41,对不同对象的,营养要求,从营养学资料和通过医生咨询得到；,各种,食品的价格,通过不同季节的市场调查获取；,一些,特殊要求,，比如,饮食习惯、偏好,等,可通过适当处理，转化为约束条件加入模型；,资料获取渠道及特殊要求的处理建议：,42,例（,饲料配比问题）,某配合饲料厂生产以鸡饲料为主的配合饲料，现准备研制一种新的,肉用仔鸡专用饲料,，所用原料的营养成分和饲养标准见表，希望这种新饲料,能满足肉用仔鸡的喂养需要,又使,总成本尽可能低,，应如何设计配比方案？,43,44,已知各种原料的购进价,1,公斤分别为,:0.314(,玉米,),、,054(,豆饼,),、,0.22,（麦麸）、,1.20,（鱼粉）、,0.40,（骨粉）、,0.50,（鸡促进素）元。,45,设,每,100,公斤,饲料中配给的玉米、豆饼、麦麸、鱼粉、骨粉、鸡促进素分别为,x,1,、,x,2,、,x,3,、,x,4,、,x,5,、,x,6,公斤,，则,饲料配比即为,x,1,：,x,2,：,x,3,：,x,4,：,x,5,：,x,6,；,于是，,可建立下面的线性规划：,46,47,4,配料问题,例,6,某工厂要用三种原料,1,、,2,、,3,混合调配出三种不同规格的,产品甲、乙、丙，数据如右表。,问：该厂应如何安排生产，使利,润收入为最大？,解：设,x,ij,表示第,i,种（甲、乙、丙）产品中原料,j,的含量。这样我们建立数学模型时，要考虑：,对于甲：,x,11,，,x,12,，,x,13,；,对于乙：,x,21,，,x,22,，,x,23,；,对于丙：,x,31,，,x,32,，,x,33,；,对于原料,1,：,x,11,，,x,21,，,x,31,；,对于原料,2,：,x,12,，,x,22,，,x,32,；,对于原料,3,：,x,13,，,x,23,，,x,33,；,目标函数：利润最大，利润,=,收入原料支出,约束条件：规格要求,4,个；,供应量限制,3,个。,48,4,配料问题,利润,=,总收入,-,总成本,=,甲乙丙三种产品的销售单价*产品数量,-,甲乙丙使用的原料单价*原料数量，故有,目标函数,Max 50,（,x,11,+,x,12,+,x,13,）,+35,（,x,21,+,x,22,+,x,23,）,+25,（,x,31,+,x,32,+,x,33,）,-65,（,x,11,+,x,21,+,x,31,）,-25,（,x,12,+,x,22,+,x,32,）,-35,（,x,13,+,x,23,+,x,33,）,=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,从第,1,个表中有：,x,11,0.5(,x,11,+,x,12,+,x,13,),x,12,0.25(,x,11,+,x,12,+,x,13,),x,21,0.25(,x,21,+,x,22,+,x,23,),x,22,0.5(,x,21,+,x,22,+,x,23,),49,4,配料问题,从第,2,个表中，生产甲乙丙的原材料不能超过原,材料的供应限额，故有,(,x,11,+,x,21,+,x,31,)100,(,x,12,+,x,22,+,x,32,)100,(,x,13,+,x,23,+,x,33,)60,通过整理，得到以下模型：,50,4,配料问题,例,6,（续）,目标函数：,Max z=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,s.t.0.5,x,11,-0.5,x,12,-0.5,x,13,0,（原材料,1,不少于,50%,）,-0.25,x,11,+0.75,x,12,-0.25,x,13,0,（原材料,2,不超过,25%,）,0.75,x,21,-0.25,x,22,-0.25,x,23,0,（原材料,1,不少于,25%,）,-0.5,x,21,+0.5,x,22,-0.5,x,23,0,（原材料,2,不超过,50%,）,x,11,+,x,21,+,x,31,100 (,供应量限制）,x,12,+,x,22,+,x,32,100 (,供应量限制）,x,13,+,x,23,+,x,33,60 (,供应量限制）,x,ij,0 ,i=1,2,3;j=1,2,3,51,4,配料问题,标准汽油,辛烷数,蒸汽压力,(g/cm,2,),库存量,(L),1,107.5,7.11,10,-2,380000,2,93.0,11.38,10,-2,265200,3,87.0,5.69,10,-2,408100,4,108.0,28.45,10,-2,130100,例,7.,汽油混合问题。一种汽油的特性可用两种指标描述，用,“,辛烷数,”,来定量描述其点火特性，用,“,蒸汽压力,”,来定量描述其挥发性。某炼油厂有,1,、,2,、,3,、,4,种标准汽油，其特性和库存量列于表,4-6,中，将这四种标准汽油混合，可得到标号为,1,，,2,的两种飞机汽油，这两种汽油的性能指标及产量需求列于表,4-7,中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使,2,号汽油满足需求，并使得,1,号汽油产量最高？,飞机汽油,辛烷数,蒸汽压力,(g/cm,2,),产量需求,1,不小于,91,不大于,9.96,10,-2,越多越好,2,不小于,100,不大于,9.96,10,-2,不少于,250000,表,4-6,表,4-7,52,4,配料问题,解：设,x,ij,为飞机汽油,i,中所用标准汽油,j,的数量,(L),。,目标函数为飞机汽油,1,的总产量：,库存量约束为：,产量约束为飞机汽油,2,的产量：,由物理中的分压定律，可得有关蒸汽压力的约束条件：,同样可得有关辛烷数的约束条件为：,53,4,配料问题,综上所述，得该问题的数学模型为：,54,4,配料问题,由管理运筹学软件求解得：,55,5,投资问题,例,8,某部门现有资金,200,万元，今后五年内考虑给以下的项目投资。已知：项,目,A,：从第一年到第五年每年年初都可投资，当年末能收回本利,110%,；项目,B,：从第,一年到第四年每年年初都可投资，次年末能收回本利,125%,，但规定每年最大投资额,不能超过,30,万元；项目,C,：需在第三年年初投资，第五年末能收回本利,140%,，但规,定最大投资额不能超过,80,万元；项目,D,：需在第二年年初投资，第五年末能收回本,利,155%,，但规定最大投资额不能超过,100,万元。,据测定每万元每次投资的风险指数如右表：,问：,a,）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？,b,）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在,330,万元的基础上使得其投资总的风险系数为最小？,解：,1,）,确定决策变量：连续投资问题,设x,ij,(i=1,5,，,j=1,4),表示第,i,年初投资于,A(j=1),、,B(j=2),、,C(j=3),、,D(j=4),项目的金额。这样我们建立如下的决策变量：,A x,11,x,21,x,31,x,41,x,51,B x,12,x,22,x,32,x,42,C,x,33,D,x,24,56,2,）约束条件：,第一年：,A,当年末可收回投资，故第一年年初应把全部资金投出去，于是,x,11,+,x,12,=200,；,第二年：,B,次年末才可收回投资，故第二年年初有资金,1.1,x,11,，于是,x,21,+,x,22,+,x,24,=1.1,x,11,；,第三年：年初有资金,11,x,21,+1.25,x,12,，于是,x,31,+,x,32,+,x,33,=1.1,x,21,+1.25,x,12,；,第四年：年初有资金,1.1,x,31,+1.25,x,22,，于是,x,41,+,x,42,=1.1,x,31,+1.25,x,22,；,第五年：年初有资金,1.1,x,41,+1.25,x,32,，于是,x,51,=1.1,x,41,+1.25,x,32,；,B,、,C,、,D,的投资限制：,x,i2,30(i=1,、,2,、,3,、,4),，,x,33,80,，,x,24,100,3,）目标函数及模型：,a),Max z=1.1,x,51,+1.25,x,42,1.4,x,33,+1.55,x,24,s.t.,x,11,+,x,12,=200,x,21,+,x,22,+,x,24,=1.1,x,11,；,x,31,+,x,32,+,x,33,=1.1,x,21,+1.25,x,12,；,x,41,+,x,42,=1.1,x,31,+1.25,x,22,；,x,51,=1.1,x,41,+1.25,x,32,；,x,i2,30(i=1,、,2,、,3,、,4),，,x,33,80,，,x,24,100,x,ij,0 (i=1,、,2,、,3,、,4,、,5,；,j=1,、,2,、,3,、,4,）,5,投资问题,57,b),所设变量与问题,a,相同，目标函数为风险最小，有,Min f=,x,11,+,x,21,+,x,31,+,x,41,+,x,51,+3(,x,12,+,x,22,+,x,32,+,x,42,)+4,x,33,+5.5,x,24,在问题,a,的约束条件中加上,“,第五年末拥有资金本利在,330,万元,”,的条件，,于是模型如下：,Min f=(,x,11,+,x,21,+,x,31,+,x,41,+,x,51,)+3(,x,12,+,x,22,+,x,32,+,x,42,)+4,x,33,+5.5,x,24,s.t.,x,11,+,x,12,=200,x,21,+,x,22,+,x,24,=1.1,x,11,；,x,31,x,32,+,x,33,=1.1,x,21,+1.25,x,12,；,x,41,+,x,42,=1.1,x,31,+1.25,x,22,；,x,51,=1.1,x,41,+1.25,x,32,；,x,i2,30(i=1,、,2,、,3,、,4),，,x,33,80,，,x,24,100,1.1,x,51,+1.25,x,42,+1.4,x,33,+1.55,x,24,330,x,ij,0 (i=1,、,2,、,3,、,4,、,5,；,j=1,、,2,、,3,、,4,）,5,投资问题,例,某油田通过输油管道向港口输送原油，中间有,4,个泵站，每段管道上的输送能力如图所示，已知泵站没有储存能力求这个系统的最大输送能力。,最大流量问题,泵站,4,泵站,3,油田,S,泵站,2,泵站,1,码头,t,5 12,4,8 11,6,7,10,设从各点往其它点的输送量如下表所示,出发点,到达点,输送量,S,S,泵站,1,泵站,1,泵站,2,泵站,2,泵站,3,泵站,3,泵站,4,泵站,1,泵站,2,泵站,3,码头,t,泵站,3,泵站,4,泵站,4,码头,t,码头,t,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,x,9,依题意：,目标函数,为,输送原油的总量,；,约束条件有两类,:,一类是管道上的流量约束；,另一类是每个中间泵站上的平衡约束,，即,中间泵站上的原油流入量和流出量相等,根据上述分析建立线性规划模型如下：,62,1,号泵站平衡约束,2,号泵站平衡约束,3,号泵站平衡约束,4,号泵站平衡约束,相应弧上的约束,