线性规划案例

1、1.人力资源分配问题例1. 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如表1所示。班次时间所需人数班次时间所需人数16:0010:0060418:0022:0050210:0014:0070522:002:0020314:0018:006062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的人数最少？解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s

2、.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0运用 lingo求解：Objective value: 150.0000ariable Value Reduced Cost X1 60.00000 0.000000 X2 10.00000 0.000000 X3 50.00000 0.000000 X4 0.000000 0.000000 X5 30.00000 0.000000 X6 0.000000 0.000000例2一家中型的百货商场，它对售货员的需求经过统

3、计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28解：设 xi ( i = 1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5

4、+ x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0lingo求解Objective value: 36.00000Variable Value Reduced Cost X1 12.00000 0.000000 X2 0.000000 0.3333333 X3 11.00000 0.000000 X4 5.000000 0.000000 X5 0.000000 0.00

5、0000 X6 8.000000 0.000000 X7 0.000000 0.000000例3. 某储蓄所每天的营业时间为上午9:00到下午17:00，根据经验，每天不同时间段所需要的服务员的数量为：时间段9101011111212131314141515161617服务人员数量43465688储蓄所可以雇佣全时和半时两类服务员。全时服务员每天报酬为100元，从上午9:00到下午17:00工作，但中午12:00到下午14:00之间必须安排1小时的午餐时间；储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬为40元。问：1) 储蓄所应该如何雇佣全时和半时两类服务员

6、？2) 如果不能雇佣半时服务员，每天至少增加多少经费？3) 如果雇佣半时服务员的数量没有限制，每天可以减少多少经费？解：设x1, x2分别表示1213，1314进行午餐的全时服务人员， y1，y2，y3，y4，y5分别表示910，1011，1112，1213，1314开始工作的半时服务人员，则问题1的模型如下所示：min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5;x1+x2+y1>4;x1+x2+y1+y2>3;x1+x2+y1+y2+y3>4;x2+y1+y2+y3+y4>6;x1+y2+y3+y4+y5>5;x1+

7、x2+y3+y4+y5>6;x1+x2+y4+y5>8;x1+x2+y5>8;y1+y2+y3+y4+y5<3;gin(x1);gin(x2);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);Objective value: 820.0000Variable Value Reduced Cost X1 3.000000 100.0000 X2 4.000000 100.0000 Y1 0.000000 40.00000 Y2 2.000000 40.00000 Y3 0.000000 40.00000 Y4 0.000000 40.000

8、00 Y5 1.000000 40.000002）把y1+y2+y3+y4+y5<3；修改为y1+y2+y3+y4+y5=0；min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5;x1+x2+y1>4;x1+x2+y1+y2>3;x1+x2+y1+y2+y3>4;x2+y1+y2+y3+y4>6;x1+y2+y3+y4+y5>5;x1+x2+y3+y4+y5>6;x1+x2+y4+y5>8;x1+x2+y5>8;y1+y2+y3+y4+y5=0;gin(x1);gin(x2);gin(y1);gin

9、(y2);gin(y3);gin(y4);gin(y5);Objective value: 1100.000Variable Value Reduced Cost X1 5.000000 0.000000 X2 6.000000 0.000000 Y1 0.000000 100.0000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000 Y5 0.000000 100.00003）把y1+y2+y3+y4+y5<3；去掉min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5

10、;x1+x2+y1>4;x1+x2+y1+y2>3;x1+x2+y1+y2+y3>4;x2+y1+y2+y3+y4>6;x1+y2+y3+y4+y5>5;x1+x2+y3+y4+y5>6;x1+x2+y4+y5>8;x1+x2+y5>8;gin(x1);gin(x2);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);运用lingo求解Objective value: 560.0000Variable Value Reduced Cost X1 0.000000 100.0000 X2 0.000000 100.00

11、00 Y1 6.000000 40.00000 Y2 0.000000 40.00000 Y3 0.000000 40.00000 Y4 0.000000 40.00000 Y5 8.000000 40.000002. 生产计划问题例4某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限制铸造工时(小时/件)510

12、78000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56-机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和 产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸

13、造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润 =16-(4+3+2)=7 可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。通过以上分析,可建立如下的数学模型:目标函数： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0lingo求解Objective value: 29400.00Varia

14、ble Value Reduced Cost X1 1600.000 0.000000 X2 0.000000 2.000000 X3 0.000000 13.10000 X4 0.000000 0.5000000 X5 600.0000 0.000000例5永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工； 可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？ 设

15、备产品单件工时设备的有效台时满负荷时的设备费用2791210000321B1684000250B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.80解：设 xijk 表示第 j 个工序在第 k 种设备上加工的第 i 种产品的数量。建立如下的数学模型: s.t. 5x111 + 10x211 6000 （ 设备 A1 ） 7x112 + 9x212 + 12x312 10000 （ 设备 A2 ） 6x121 + 8x221 4000 （ 设备 B1 ） 4x122 + 11x322 7000 （ 设备

16、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目标函数为计算利润最大化，利润的计算公式为： 利润 = （销售单价 - 原料单价）* 产品件数之和 -（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数： Max(1.25-0.25)(x111+x112)+

17、(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运用lingo求解Objective value: 1146.514Variable Value

18、 Reduced Cost X111 1200.000 0.000000 X112 230.0493 0.000000 X211 0.000000 0.3101897 X212 500.0000 0.000000 X312 324.1379 0.000000 X121 0.000000 0.2530095 X221 500.0000 0.000000 X122 858.6207 0.000000 X322 324.1379 0.000000 X123 571.4286 0.000000近似有X111=1200，X112=230，X211=0，X212=500，X312=324， X121=0，

19、X221=500 X122=859， X322=324，X123=571Objective value: 1146.362利用整数规划Objective value: 1146.362 Variable Value Reduced Cost X111 1200.000 -0.7500000 X112 230.0000 -0.7753000 X211 0.000000 -1.150000 X212 500.0000 -1.361100 X312 324.0000 -1.914800 X121 0.000000 0.3750000 X221 500.0000 0.5000000 X122 859.

20、0000 0.4475000 X322 324.0000 1.230400 X123 571.0000 0.3500000例6. 双层卷焊钢管是光明制造厂1990从意大利引进的主导民用产品，生产流程为：钢带镀铜镀铜带精剪制管。产品广泛应用于汽车，机床，大型机械油气管制造。目前全国市场占有率为15%，年利润为350万元。为广大市场占有率，进一步提高企业知名度，为下一步上市做好准备，该厂1998年拟对双层卷焊钢管分厂实行资产经营，要求有关部门拿出一份经营报告书，要求对以下几个问题做出明确分析：（1）最大盈利能力。（2）生产计划。（3）因镀铜用钢带需从比利时进口，外商要求提前一年提供订货数量，并需用

21、外汇支付。分析如何确定钢带订货量，使外商供货，既能满足生产，又能尽量为工厂节约费用。生产过程中各项经济指标如下：（1）钢带镀铜：废品率为1%，废品回收扣除废品镀铜过程中各项生产费用后净收入为1000元/t。职工工资实行计件工资，合格品675元/t，钢带8000元/t。（2）镀铜带精剪：废品率为2%，废品回收扣除废品镀铜精剪过程中各项生产费用后净收入为零。职工工资实行计件工资，合格品900元/t。（3）制管：废品率：直径4.76为8%，直径6为8.5%，直径8为9%，直径12为10.5%，废品回收扣除废品镀铜，精剪，制管过程中各项生产费用后净收入为700元/t。职工工资实行计件工资，合格品900

22、元/t。 售价情况：直径4.76: 16000元/t; 直径6: 16100元/t; 直径8: 16000元/t;直径10: 16100元/t; 直径12: 16300元/t; 折旧： 200万元。生产费用：合格钢管1200元/t。企业管理费：1000元/t。特殊说明：（1）钢带镀铜后镀膜很薄，镀铜带与钢带质量可近似认为一致。（2）生产过程中废料很少，可忽略不计。销售部门经过严密的市场分析后，结合明年的订货情况给厂长以下信息：1998年共需我厂钢管2800t，其中直径4.76的不少于50%；直径6的至少占10%，至多占30%;直径8的有300t老主顾订货，必须予以满足；直径10的订货历史上一直

23、与直径6有联动关系，一般为直径6的一半；直径12的属于冷门产品，一年必须有100t备货，但市场预测绝对不会突破200t。解：设直径4.76、6、8、10 和12 的钢管的需求量分别是X1，X2，X3，X4，X5。钢带的供给量为X0。则：钢管销售收入Y1 为：Y1=16000X1+16100X2+16000X3+16100X4+16300X5废品回收收入Y2 为：Y2=10X0+（0.087X1+0.093X2+0.099X3+0.117X5）×700钢带成本C1 为：C1=8000X0职工工资C2 为：C2=X0×0.99×675+X0×0.99

24、5;0.98×900+（X1+X2+X3+X4+X5）×900则净利润Y0 为：Y0=Y1+Y2-C1-C2-2000000-（X1+X2+X3+X4+X5）×2200（目标函数）约束条件：1.086957X1+1.092896X2+1.111111X3+X4+1.117318X5=X0×0.99×0.98X1+X2+X3+X4+X5=2800X11400840X2280X3300X4=X2/2200X5100X0,X1,X2,X3,X4,X50运用lingo求解:Objective value: 4652764.Variable Value

25、Reduced Cost Y0 4652764. 0.000000 Y1 0.4493000E+08 0.000000 Y2 188857.6 0.000000 C1 0.2497411E+08 0.000000 C2 7331981. 0.000000 X1 1400.000 0.000000 X2 666.6667 0.000000 X3 300.0000 0.000000 X4 333.3333 0.000000 X5 100.0000 0.000000 X0 3121.764 0.0000003. 套裁下料问题例7. 某钢管零售商从钢管厂进货，将钢管按照顾客的需求切割后售出. 从钢管厂

26、进货时得到原料钢管都是19m长. （1）现有一客户需要50根4m长，20根6m长和15根8m长的钢管，应如何下料最节省？（2）零售商如果采取的不同切割方式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用不同切割模式不能超过3种. 此外，该客户除需要（1）中的3种钢管外，还需要10根5m的钢管，应如何下料最节省？问题（1）的求解首先，确定那些切割模式是可行的. 所谓一个切割模式，就是按照客户的需要在原料钢管上安排切割的一种组合. 例如，我们可以将19m长的钢管切割成3根4m长的钢管，余料为7m，或者将19m长的钢管切割成4m，6m和8m长的钢管个一根，余料为1m. 其

27、次，应当确定哪些切割模式是合理的. 通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸. 例如，将19m长的钢管切割成3根4m长的钢管是可行的，但余料为7m，可以进一步将7m的余料切割成4m钢管（余料3m），或者将7m的余料切割成6m钢管（余料为1m）. 在这种合理性假设下，切割模式一共有7种，如表所示.模式4m钢管根数6m钢管根数8m钢管根数余料/m模式14003模式23101模式32013模式41203模式51111模式60301模式70023模型建立：决策变量：用xi表示按照第i种模式（i=1,2,7）切割的原料钢管的根数目标：以切割后余料总量最少为目标，则有Min

28、 3x1+x2+3x3+3x4+x5+x6+3x7以切割原料钢管的总根数最少为目标，则有Min x1+x2+x3+x4+x5+x6+x7约束条件：4x1+3x2+2x3+x4+x550,X2+2x4+x5+3x620,X3+x5+2x715,运用lingo求解第一种目标：Objective value: 26.66667Variable Value Reduced Cost X1 0.000000 1.666667 X2 11.66667 0.000000 X3 0.000000 1.666667 X4 0.000000 2.666667 X5 15.00000 0.000000 X6 0.0

29、00000 1.000000 X7 0.000000 1.666667第二种目标：Objective value: 25.00000Variable Value Reduced Cost X1 0.000000 0.000000 X2 15.00000 0.000000 X3 0.000000 0.000000 X4 0.000000 0.2500000 X5 5.000000 0.000000 X6 0.000000 0.2500000 X7 5.000000 0.000000问题（2）求解模型建立：由于不同的切割模式不超过3种，可以用xi表示按照第i种模式（i=1,2,3）切割的原料钢管的

30、根数，显然它们应当是非负整数. 设所使用的第i种切割模式下每根原料钢管生产4m，5m，6m和8m长的钢管数量分别为r1i，r2i，r3i，r4i（非负整数）.决策目标：以切割原料钢管总根数最少为目标，即目标为Min x1+x2+x3约束条件：为满足客户的需求，应有R11x1+r12x2+r13x350,R21x1+r22x2+r23x310,R31x1+r32x2+r33x320,R41x1+r42x2+r43x315,每一种切割模式必须可行，合理，所以每根钢管的成品量不能超过19m，也不能少于16m，则有16 4 r11+5r21+6r31+8r4119,16 4 r12+5r22+6r32

31、+8r4219,16 4 r13+5r23+6r33+8r4319.运用lingo求解Local optimal solution found. Objective value: 28.00000Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R

32、23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000例8. 某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压成的，为圆柱状，包括罐身、上盖和下底。罐身高10cm，上盖和下底的直径均为5cm。该公司使用两种不同规格的镀锡板原料，规格1的镀锡板为正方形，边长24cm；规格2的镀锡板为长方形，长32cm ，宽28cm；由于生产设

33、备和生产工艺的限制，规格1的镀锡板只能按模式1、2、3冲压，规格2的镀锡板只能按模式4冲压(见图)，使用模式1、2、3、4进行冲压所需时间分别为1.5秒、2秒、1秒和3秒模式二模式一模式四模式三该公司每周工作40小时，每周可供使用的规格1、2的镀锡板原料分别为5万张和2万张，目前每只易拉罐的利润为0.1元，原料余料损失为0.001元/cm2(如果周末有罐身、上盖或下底不能配套成易拉罐出售，也看成是余料损失)。公司应如何安排每周的生产？问题分析：与钢管下料问题不同的是，这里的切割模式已经确定，只需要计算各种模式下的余料损失. 已知上盖与下底的直径d=5cm, 可得其面积为, 周长为，于是模式一的

34、余料损失为。同理可以计算其他模式下的余料损失，如表所示：罐身个数底，盖个数余料损失/cm2冲压时间/s模式一110222.61.5模式二24183.32模式三016261.81模式四45169.53问题目标应是易拉罐的利润扣除原料余料损失后的净利润最大；约束条件除每周工作时间的原料数量外，还要考虑罐身和盖、底的配套组装模型建立：决策变量：用xi表示按第i种模式冲压的次数(i=1,2,3,4) y1表示一周生产的易拉罐个数 y2表示不配套的罐身个数 y3表示不配套的盖(底)个数决策目标(设每周生产的易拉罐全部售出)：净利润最大净利润=利润四种冲压模式的余料损失不配套造成的原料损失决策目标(设每周生产的易拉罐全部售出)：maxZ=0.1y10.001(222.6