线性规划案例.doc

1.人力资源分配问题
例1. 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如表1所示。
班次
时间
所需人数
班次
时间
所需人数
1
6:00~10:00
60
4
18:00~22:00
50
2
10:00~14:00
70
5
22:00~2:00
20
3
14:00~18:00
60
6
2:00~6:00
30
设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的人数最少？

解：设 xi 表示第i班次时开始上班的司机和乘务人员数,
这样我们建立如下的数学模型。
目标函数： Min x1 + x2 + x3 + x4 + x5 + x6
约束条件：s.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.0000
ariable 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．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作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 + 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 ≥ 0
lingo求解
Objective value: 36.00000
Variable 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.000000
X6 8.000000 0.000000
X7 0.000000 0.000000
例3. 某储蓄所每天的营业时间为上午9:00到下午17:00，根据经验，每天不同时间段所需要的服务员的数量为：
时间段
9~10
10~11
11~12
12~13
13~14
14~15
15~16
16~17
服务人员数量
4
3
4
6
5
6
8
8
储蓄所可以雇佣全时和半时两类服务员。全时服务员每天报酬为100元，从上午9:00到下午17:00工作，但中午12:00到下午14:00之间必须安排1小时的午餐时间；储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬为40元。问：
1) 储蓄所应该如何雇佣全时和半时两类服务员？
2) 如果不能雇佣半时服务员，每天至少增加多少经费？
3) 如果雇佣半时服务员的数量没有限制，每天可以减少多少经费？
解：设x1, x2分别表示12~13，13~14进行午餐的全时服务人员，
y1，y2，y3，y4，y5分别表示9~10，10~11，11~12，12~13，13~14开始工作的半时服务人员，则问题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+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.0000
Variable 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.00000
Y5 1.000000 40.00000

2）把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(y2);@gin(y3);@gin(y4);@gin(y5);
Objective value: 1100.000
Variable 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.0000

3）把y1+y2+y3+y4+y5<3；去掉
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;
@gin(x1);@gin(x2);@gin(y1);@gin(y2);@gin(y3);@gin(y4);@gin(y5);
运用lingo求解
Objective value: 560.0000
Variable Value Reduced Cost
X1 0.000000 100.0000
X2 0.000000 100.0000
Y1 6.000000 40.00000
Y2 0.000000 40.00000
Y3 0.000000 40.00000
Y4 0.000000 40.00000
Y5 8.000000 40.00000

2. 生产计划问题
例4．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？

甲
乙
丙
资源限制
铸造工时(小时/件)
5
10
7
8000
机加工工时(小时/件)
6
4
8
12000
装配工时(小时/件)
3
2
2
10000
自产铸件成本(元/件)
3
5
4

外协铸件成本(元/件)
5
6
--

机加工成本(元/件)
2
1
3

装配成本(元/件)
3
2
2

产品售价(元/件)
23
18
16

解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。
求 xi 的利润：利润 = 售价 - 各成本之和
产品甲全部自制的利润 =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
可得到 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 ≥ 0
lingo求解
Objective value: 29400.00
Variable 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设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？
设备
产品单件工时
设备的
有效台时
满负荷时的设备费用
Ⅰ
Ⅱ
Ⅲ
A1
5
10

6000
300
A2
7
9
12
10000
321
B1
6
8

4000
250
B2
4

11
7000
783
B3
7

4000
200
原料（元/件）
0.25
0.35
0.50

售价（元/件）
1.25
2.00
2.80

解：设 xijk 表示第 j 个工序在第 k 种设备上加工的第 i 种产品的数量。建立如下的数学模型:
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

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

运用lingo求解
Objective value: 1146.514
Variable Value 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，X221=500 X122=859， X322=324，X123=571
Objective 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.0000 0.4475000
X322 324.0000 1.230400
X123 571.0000 0.3500000
例6. 双层卷焊钢管是光明制造厂1990从意大利引进的主导民用产品，生产流程为：钢带镀铜→镀铜带精剪→制管。产品广泛应用于汽车，机床，大型机械油气管制造。目前全国市场占有率为15%，年利润为350万元。为广大市场占有率，进一步提高企业知名度，为下一步上市做好准备，该厂1998年拟对双层卷焊钢管分厂实行资产经营，要求有关部门拿出一份经营报告书，要求对以下几个问题做出明确分析：
（1）最大盈利能力。
（2）生产计划。
（3）因镀铜用钢带需从比利时进口，外商要求提前一年提供订货数量，并需用外汇支付。分析如何确定钢带订货量，使外商供货，既能满足生产，又能尽量为工厂节约费用。
生产过程中各项经济指标如下：
（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元/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的订货历史上一直与直径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×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.98
X1+X2+X3+X4+X5=2800
X1≥1400
840≥X2≥280
X3≥300
X4=X2/2
200≥X5≥100
X0,X1,X2,X3,X4,X5≥0
运用lingo求解:
Objective value: 4652764.
Variable Value 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.000000

3. 套裁下料问题
例7. 某钢管零售商从钢管厂进货，将钢管按照顾客的需求切割后售出. 从钢管厂进货时得到原料钢管都是19m长.
（1）现有一客户需要50根4m长，20根6m长和15根8m长的钢管，应如何下料最节省？
（2）零售商如果采取的不同切割方式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用不同切割模式不能超过3种. 此外，该客户除需要（1）中的3种钢管外，还需要10根5m的钢管，应如何下料最节省？

问题（1）的求解
首先，确定那些切割模式是可行的. 所谓一个切割模式，就是按照客户的需要在原料钢管上安排切割的一种组合. 例如，我们可以将19m长的钢管切割成3根4m长的钢管，余料为7m，或者将19m长的钢管切割成4m，6m和8m长的钢管个一根，余料为1m.
其次，应当确定哪些切割模式是合理的. 通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸. 例如，将19m长的钢管切割成3根4m长的钢管是可行的，但余料为7m，可以进一步将7m的余料切割成4m钢管（余料3m），或者将7m的余料切割成6m钢管（余料为1m）. 在这种合理性假设下，切割模式一共有7种，如表所示.
模式
4m钢管根数
6m钢管根数
8m钢管根数
余料/m
模式1
4
0
0
3
模式2
3
1
0
1
模式3
2
0
1
3
模式4
1
2
0
3
模式5
1
1
1
1
模式6
0
3
0
1
模式7
0
0
2
3

模型建立：
决策变量：用xi表示按照第i种模式（i=1,2,…,7）切割的原料钢管的根数
目标：以切割后余料总量最少为目标，则有
Min 3x1+x2+3x3+3x4+x5+x6+3x7
以切割原料钢管的总根数最少为目标，则有
Min x1+x2+x3+x4+x5+x6+x7
约束条件：
4x1+3x2+2x3+x4+x5≥50,
X2+2x4+x5+3x6≥20,
X3+x5+2x7≥15,
运用lingo求解
第一种目标：
Objective value: 26.66667
Variable 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.000000 1.000000
X7 0.000000 1.666667
第二种目标：
Objective value: 25.00000
Variable Value Reduced Cost
X1 0.000000 0.000000
X2 15.00000