第4章 线性规划问题的应用及计算机求解

管理运筹学1第四章线性规划问题的应用及计算机求解§4.1人力资源管理的问题§4.2生产计划的问题§4.3套裁下料问题§4.4配料问题§4.5投资问题管理运筹学2§4.1人力资源管理的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030管理运筹学3§4.1人力资源管理的问题解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0运筹学软件求解结果：x1=50，x2=20，x3=50，x4=0，x5=20，x6=10，一共需要司机和乘务人员150人管理运筹学4§4.1人力资源管理的问题例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28管理运筹学5§4.1人力资源管理的问题解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2,x3,x4,x5,x6,x7≥0管理运筹学软件求解结果：x1=12，x2=0，x3=11，x4=5，x5=0，x6=8，x7=0，最少配备售货员36人问：假如直接设xi为星期i开始上班的人数，结果一样么？管理运筹学6§4.2生产计划的问题•例3某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：用线性规划制订使总利润最大的生产计划。每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18管理运筹学7§4.2生产计划的问题解：设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1，x2，x3，x4≥0求解得：x1=294.12，x2=1500，x3=0，x4=58.82可获得最大利润z=12737.06元产品产品甲产品乙产品丙产品丁利润（元/件）5.247.308.344.18注意注意：最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果管理运筹学8§4.2生产计划的问题例4．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816管理运筹学9§4.2生产计划的问题解：设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4，x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和单位产品甲全部自制的利润=23-(3+2+3)=15单位产品乙全部自制的利润=18-(5+1+2)=10单位产品丙的利润=16-(4+3+2)=7单位产品甲铸造外协，其余自制的利润=23-(5+2+3)=13单位产品乙铸造外协，其余自制的利润=18-(6+1+2)=9可得到单位产品xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。管理运筹学10§4.2生产计划的问题通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0管理运筹学软件求解结果：x1=1600，x2=0，x3=0，x4=0，x5=600，此时，公司生产获得最大利润为29400管理运筹学11§4.2生产计划的问题例5．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？产品单件工时设备ⅠⅡⅢ设备的有效台时满负荷时的设备费用A15106000300A2791210000321B1684000250B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.80管理运筹学12§4.2生产计划的问题解：设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量。建立如下的数学模型:s.t.5x111+10x211≤6000（设备A1）7x112+9x212+12x312≤10000（设备A2）6x121+8x221≤4000（设备B1）4x122+11x322≤7000（设备B2）7x123≤4000（设备B3）x111+x112-x121-x122-x123=0（Ⅰ产品在A、B工序加工的数量相等）x211+x212-x221=0（Ⅱ产品在A、B工序加工的数量相等）x312-x322=0（Ⅲ产品在A、B工序加工的数量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3管理运筹学13§4.2生产计划的问题目标函数为计算利润最大化，利润的计算公式为：利润=[（销售单价-原料单价）*产品件数]之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数：Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312–300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得：Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123管理运筹学软件求解结果：x111=1200，x112=230.049，x211=0，x212=500，x312=324.138，x121=0，x221=500，x122=858.620，x322=324.138，x123=571.428，工厂可获得最大利润1146.6005元管理运筹学14§4.3套裁下料问题例6．某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：枚举法共可列出下列8种下料方案，见下表设x1,x2,…,x8分别为上面8种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7+x8约束条件：s.t.2x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥100x1+x3+3x4+2x6+3x7+4x8≥100x1，x2，…x8≥0方案1方案2方案3方案4方案5方案6方案7方案82.9m211100002.1m021032101.5m10130234合计7.37.16.57.46.37.26.66.0剩余料头0.10.30.901.10.20.81.4管理运筹学15•用“管理运筹学”软件计算得出最优下料方案：按方案1下料10根；按方案2下料50根；按方案4下料30根。即x1=10;x2=50；x4=30；其余为0；只需90根原材料就可制造出100套钢架，此时料头16米。•注意：本题方案初选的时候可以去掉3、5、8，即料头太多的方案。§4.3套裁下料问题管理运筹学16§4.3套裁下料问题•另一种解法以下料最省为目标函数Minf=0.1x2+0.2x3+0.3x4+0.8x8s.t.2x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100x1+x3+3x4+2x6+3x7+4x8=100x1，x2，…x8≥0计算结果相同管理运筹学17§4.4配料问题例7．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035解：设xij表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。管理运筹学18§4.4配料问题•利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有目标函数Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33约束条件：从第1个表中有：x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)管理运筹学19