《LP在管理中的应用》PPT课件.ppt

1,第四章线性规划在工商管理中的应用,4.1人力资源分配的问题4.2生产计划的问题4.3套裁下料问题4.4配料问题4.5投资问题,2,4.1人力资源分配的问题,例1某昼夜服务的公交线路,每天各班次所需司机和乘务人员数如下：,设：司机和乘务人员分别在某时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能完成工作，且雇佣的司机和乘务人员总数最少?,3,例1求解思路,1、目标函数：任务已定，求每天上班总人数之和最小。要用最少的人力资源完成规定的乘运任务。,3、约束条件：每两个班次人数之和不少于bi,2、决策变量(Xi)：需要决策是各个班次的上班人数。已知在第i时间段（当班）次工作的人数应包括第i-1班次时开始上班的人员数和第i班次时开始上班的人数。,4,例1LP模型,解：设xi表示第i班次时开始上班的司机和乘务人员数.可建立如下的数学模型。目标函数：Minf=x1+x2+x3+x4+x5+x6约束条件：s.t.x6+x160(6点到10所需人数）x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60,用软件的最优解：x1=50，x2=20，x3=50，x4=0，x5=20，x6=10,5,例2某中型的百货商场，它对售货员的需求经过统计分析如下表所示。,4.1人力资源分配的问题,注意，为了保证售货员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问:应该如何安排售货员的作息，既满足工作需要，又使所需总售货员的人数最少？,6,例2求解思路,目标函数：总雇员最少(等价于轮休雇员总人数最少),决策变量：周内每天休班的人数（Xi),约束条件：凡不休班的售货员都上班以满足岗位的需要,7,例2数学模型,Minf=x1+x2+x3+x4+x5+x6+x7s.t.x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7+x125x5+x6+x7+x1+x219x6+x7+x1+x2+x331x7+x1+x2+x3+x428x1,x2,x3,x4,x5,x6,x70,最优解：X=（12，0，11，5，0，8，0）,MinZ=36人,解：设xi(i=1,2,7)表示星期一至日开始休息的人数,可建立如下的数学模型。,目标函数：,约束条件,见41页图4-1,8,4.2生产计划的问题,例3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,9,例3求解思路,设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，并设x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。,1、求目标函数系数Ci(不同产品的利润),利润=售价-各项成本,X1的系数:甲产品全部自制的利润C1=23-,-3,3,-2,=15,10,X4的系数:甲产品铸造外协其余自制的利润C4=23-(5+2+3)=13,11,同理得：,得:xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元,X3:丙产品的利润C3=16-(4+3+2)=7,X2:乙产品全部自制的利润C2=18-(5+1+2)=10,X5:乙产品铸造外协其余自制的利润C5=18-(6+1+2)=9,12,例3数学模型,通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10 x2+7x3+13x4+9x5约束条件：5x1+10 x2+7x38000(铸造工时)（机加工工时）6x1+4x2+8x3+6x4+4x512000（装配工时）3x1+2x2+2x3+3x4+2x510000 x1,x2,x3,x4,x50,优化结果见教材第43页，,maxZ=29400,x1=1600，X5=600，其它：Xi=0,13,4.2生产计划的问题,问：为使该厂获得最大利润，应如何制定产品加工方案？,产品可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序则只能在B1设备上加工；只能在A2与B2设备上加工。有关数据如表：,例4某机械厂生产、三种产品，均要经过A、B两道工序加工。设备A1、A2能完成A工序；B1、B2、B3设备能完成B工序。,14,决策变量：各类产品生产数量(同一产品因在不同的工序设备上加工工时消耗不同视作不同产品类型）；因为要考虑到工序以及设备类型的约束，不妨用Xijk表示不同品种、工序、设备生的产量。,一、设置决策变量：,求解,15,5x111+10 x2116000（设备A1）7x112+9x212+12x31210000（设备A2）6x121+8x2214000（设备B1）4x122+11x3227000（设备B2）7x1234000（设备B3）x111+x112-x121-x122-x123=0（产品在A、B工序加工的数量相等）x211+x212-x221=0（产品在A、B工序加工的数量相等）x312-x322=0（产品在A、B工序加工的数量相等）xijk0,i=1,2,3;j=1,2;k=1,2,3,二、设置约束方程（各类工序、设备约束）,当设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量时。可建立如下约束方程:,16,由于目标函数是求利润最大化，所以目标函数中系数计算公式为：利润=(销售单价-原料单价）*该种类产品件数-(每台时的设备费用*设备实际使用的总台时数）这样可写出如下目标函数：MaxZ=(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).（注意x111+x112-x121-x122-x123=0等）经整理可得：MaxZ=0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123,三、目标函数：不同产品类型与纯利润乘积之和最大,产品在第一工序A的总产量,经过A、B两道工序的量与经过A工序的量相等？,产品全部经B工序第一种设备,17,Z=Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123,s.t.5x111+10 x2116000（设备A1）7x112+9x212+12x31210000（设备A2）6x121+8x2214000（设备B1）4x122+11x3227000（设备B2）7x1234000（设备B3）x111+x112-x121-x122-x123=0（产品在A、B工序加工的数量相等）x211+x212-x221=0（产品在A、B工序加工的数量相等）x312-x322=0（产品在A、B工序加工的数量相等）xijk0,i=1,2,3;j=1,2;k=1,2,3,计算结果见教材P45,例4完整模型,18,4.3套裁下料问题,例5某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？,解题思路：套裁下料问题，关键是预设计下料方案不妨设计下列5种下料方案，见表4-5,19,设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minf=x1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x4100(长2.9m的不少于100)2x3+2x4+x5100(长为2.1m的需求量)3x1+x2+2x3+3x5100(1.5m需求量)x1,x2,x3,x4,x50,例5求解思路,20,用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,套裁下料问题求解结果,21,4.4配料问题,例6-1某工厂要用三种原料（编号为1、2、3，表4-7）混合调配出三种不同规格的产品（甲、乙、丙），数据如表4-6。,表4-6,表4-7,问：该厂应如何安排生产，使利润收入为最大？,22,设xij表示第i种产品（甲、乙、丙）中，第j原料的含有量。因此，不同规格产品的产量可由相应的决策变量之和求出：甲产量：x1.=x11+x12+x13；甲产品的总量为其构成的3种原料用量之和，同理：乙产量：x2.=x21+x22+x23；丙产量：x3.=x31+x32+x33；因为，某种原料的用量为相关产品含该种原料量之和：原料1用量：x.1=x11+x21+x31；（各相关决策变量含第1种原料量的和）原料2用量：x.2=x12+x22+x32；原料3用量：x.3=x13+x23+x33；,例6-1求解思路,规格要求约束4个；供应量限制约束3个。,目标函数：利润最大，（利润=总收入总原料支出）,约束条件：,23,例6-1数学模型,MaxZ=（50 x1.+35x2.+25x3.）-（65x.1+25x.2+35x.3）=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33,见表4-6中要求,规格约束：,目标函数:利润=产品销售单价*产品数量之和-原料单价*原料量之和。即：,24,(x11+x21+x31)100(x12+x22+x32)100(x13+x23+x33)60,生产甲乙丙的原材料不能超过原材料的供应限额因此还应有以下约束：,原料供应约束：,因为,25,例6-1完整LP模型,目标函数：Maxz=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33s.t.0.5x11-0.5x12-0.5x130（原材料1不少于50%）-0.25x11+0.75x12-0.25x130（原材料2不超过25%）0.75x21-0.25x22-0.25x230（原材料1不少于25%）-0.5x21+0.5x22-0.5x230（原材料2不超过50%）x11+x21+x31100(供应量限制）x12+x22+x32100(供应量限制）x13+x23+x3360(供应量限制）xij0,i=1,2,3;j=1,2,3,计算结果见P48，-3,某公司长期饲养某种动物，已知这些动物的生长对饲料中的蛋白质、矿物质、维生素这三种营养成分特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该公司能买到五种不同的饲料原料，每种原料每公斤所含的上述成分及成本如下表所示，试为公司制定相应的饲料配方，以满足动物生长的营养需要，并使所用原料的总成本最低。,配料问题例6-2,设Xi为混合饲料中所含的第i种原料的量（决策变量）,例6-2求解思路,1、设置决策变量：,3、确定约束条件：因每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，所以应满足如下的约束条件：,2、确定目标函数,x1,x50,St.,例6-2LP完整模型,29,汽油混合问题。汽油的特性可用两种指标描述，一般用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-8中。,表4-8,例7.配料问题（续）,30,若将这四种标准汽油混合可得到标号为1，2的两种飞机用汽油，这两种汽油的性能指标及产量需求列于表4-9中。,问题：应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？,表4-9,例7续,31,例7求解思路,解：设xij为第i种飞机汽油用第j标准汽油的数量(L)。,1、库存约束：,2号飞机汽油产量,3蒸汽压力的约束:混合气体的压强容积的乘积=各组成气体压强与容积乘积之和,目标函数（求1号飞机汽油的总产量最大）,（1号标准汽油库存）,（2号标准汽油库存）,由此可写出不同混合汽油的压力的约束条件：,MaxZ=,St.,2、产量约束：,32,同样可得有关辛烷数的约束条件为：,对两个压力约束经条件整理后为：,1号飞机汽油气体压强9.96*10-2，因此有：,(7.11*x11+11.38*x12+5.69*x13+28.45*x14)*10-2/(x11+x12+x13+x14)9.96*10-2,同理可列出2号飞机汽油的压力约束：,33,例7数学完整模型,34,例7求解结果,由管理运筹学软件求解得：,35,4.5投资问题,问题：1、应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？,D项目：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。,C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；,B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；,A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；,例8某部门现有资金200万元，今后五年内考虑给以下的项目投资：,问题2、应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,另：据测定每万元每次投资的风险指数如下表,37,设xij(i=15，j=14)表示第i年初投资于j=1(A)、j=2(B)、j=3(C)、j=4(D)项目的金额。这样可写出如下的1）决策变量：Ax11x21x31x41x51(x1)(x2)Bx12x22x32x42Cx33(x10)Dx24,解：1、连续投资问题,例8求解思路,38,第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi230(i=1、2、3、4)，x3380，x24100,例8约束条件,39,Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；x1230(i=1、2、3、4)，x3380，x24100 xij0(i=1、2、3、4、5；j=1、2、3、4）,例8数学模型,连续投资风险最小问题续,所设变量与问题1相同，目标函数为风险最小，有：,目标函数,Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24,41,在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是完整模型如下：Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi230(i=1、2、3、4)，x3380，x241001.1x51+1.25x42+1.4x33+1.55x24330 xij0(i=1、2、3、4、5；j=1、2、3、4）,连续投资风险最小问题续,