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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第四章 线性规划在工商管理中的应用,1,人力资源分配的问题,2,生产计划的问题,3,套裁下料问题,4,配料问题,5,投资问题,1,1,人力资源分配的问题,例,1,某昼夜服务的公交线路每天各时间段内所需司机,和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并,连续工作八小时，问该公交线路怎样安排司机和乘务人员，,既能满足工作需要，又配备最少司机和乘务人员,?,2,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,3,1,人力资源分配的问题,例,2,一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作,5,天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,4,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,31x,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,5,2,生产计划的问题,例,3,某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,6,2,生产计划的问题,解：设,x,1,x,2,x,3,分别为三道工序都由本公司加工的甲、乙、丙三种,产品的件数，,x4,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,元。,7,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,3,x,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,8,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,设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,9,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,+,x,212,-,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,10,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,11,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,4100,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,12,用“管理运筹学”软件计算得出最优下料方案：按方案,1,下料,30,根；按方案,2,下料,10,根；按方案,4,下料,50,根。,即,x,1,=30;,x,2,=10,；,x,3,=0,；,x,4,=50,；,x,5,=0,；,只需,90,根原材料就可制造出,100,套钢架。,注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,3,套裁下料问题,13,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,个。,14,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,),15,4,配料问题,从第,2,个表中，生产甲乙丙的原材料不能超过原,材料的供应限额，故有,(,x,11,+,x,21,+,x,31,)100,(,x,12,+x,22,+,x,32,)100,(,x,13,+,x,23,+,x,33,)60,通过整理，得到以下模型：,16,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,17,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,4081004,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,18,4,配料问题,解：设,x,ij,为飞机汽油,i,中所用标准汽油,j,的数量,(L),。,目标函数为飞机汽油,1,的总产量：,库存量约束为：,产量约束为飞机汽油,2,的产量：,由物理中的分压定律，可得有关蒸汽压力的约束条件：,同样可得有关辛烷数的约束条件为：,19,4,配料问题,综上所述，得该问题的数学模型为：,20,4,配料问题,由管理运筹学软件求解得：,21,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,22,2,）约束条件：,第一年,：,A,当年末可收回投资，故第一年年初应把全部资金投出去，于是,x,11,+,x,12,=200,；,第二年,：,B,次年末才可收回投资，故第二年年初有资金,11,x,11,，,于是,x,21,+,x,22,+,x,24,=1.1,x,11,；,第三年：年初有资金,1.1,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,、,23,、,4,、,5,；,j=1,、,2,、,3,、,4,）,5,投资问题,23,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,投资问题,24,