运筹学作业.doc

9
运 筹 学 作 业 题 集
No.1 线性规划
1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下：
产品
项目
A
B
C
D
单位产值 (元)
168
140
1050
406
单位成本 (元)
42
28
350
140
单位纺纱用时 (h)
3
2
10
4
单位织带用时 (h)
0
0
2
0.5
工厂有供纺纱的总工时7200h，织带的总工时1200h。
(1) 列出线性规划模型，以便确定产品的数量使总利润最大；
(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？（所谓一次性投入就是与产量无关的初始投资）
2、将下列线性规划化为极大化的标准形式

3、用单纯形法解下面的线性规划

No.2 两阶段法和大M法
1、用两阶段法解下面问题：

2、用大M法解下面问题，并讨论问题的解。

No.3 线性规划的对偶问题
1、写出下列线性规划问题的对偶问题：
(1) (2)

2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解
3、用对偶单纯形法求下面问题

No.4 线性规划的灵敏度分析
1、下表是一线性规划最优解的单纯形表

Cj ®
21
9
4
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
21
x1
4
1
0
1/3
2/3
0
1/3
0
x5
2
0
0
-2/3
-4/3
1
1/3
9
x2
23
0
1
1/3
-1/3
0
-2/3

zj
21
9
10
11
0
1

cj - zj
0
0
-6
-11
0
-1
原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题：
(1)资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量)
(2)求C1, C2 和C3的灵敏度范围；
(3)求Db1，Db2的灵敏度范围。
No.5 运输问题
1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始可行解，并计算其目标函数。(可不写步骤)
2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法）求出最优解。（要求列出每一步的运费矩阵和基础可行解矩阵）
销地
产地
B1
B2
B3
B4
B5
产量
A1
6
9
4
8
5
20
A2
10
6
12
8
7
30
A3
6
5
9
20
9
40
A4
2
13
6
14
3
60
销量
25
15
35
45
30

No.6 指派问题
1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h) 如下表，问如何分派工作，使总的消耗时间最少？
消耗 工作
工人
A
B
C
D
甲
3
3
5
3
乙
3
2
5
2
丙
1
5
1
6
丁
4
6
4
10
2、学生A、B、C、D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据，应如何指派最有利？
得分 课程
学生
数学
物理
化学
外语
A
89
92
68
81
B
87
88
65
78
C
95
90
85
72
D
75
78
89
96

No.7 动态规划
1、某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。
推销员
市场
0
1
2
3
4
5
6
7
8
9
1
20
32
47
57
66
71
82
90
100
110
2
40
50
60
71
82
93
104
115
125
135
3
50
61
72
84
97
109
120
131
140
150
2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12-x1)和(13-2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。
No.8 最短路问题
1、求下图中v1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值)

2、将右图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画出该树图。

No.9 网络流问题
1、求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)

No.10 随机服务系统：输入过程
1、对一服务系统进行观察，总观察时间为102.7分钟，到达系统的累计人数为40人，顾客累计的排队等待时间为44.8分钟，顾客累计的服务时间为79.6分钟，求
(1) 系统中平均排队长度；
(2)平均同时接受服务的人数。
2、某选举站对甲、乙二人进行选举，选票中只能选其中一人才有效。假设投票的人流服从泊松分布，投甲票的人的到达率为l1 =4人/小时，投乙票的人的到达率为l2 =2人/小时；再假设所有投票人的票都是有效的，而选举结果的统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半小时统计结果为：
(1)甲得三票，乙得1票的概率；
(2)总票数为5的概率；
(3)甲得全票的概率。

No.11 随机服务系统：标准服务系统
1、某自动交换台有4条外线，打外线的呼叫强度为2次/分钟，为泊松流，平均通话时长为2分钟。当4条外线全忙时，用户呼叫将遇忙音。假设用户遇忙音后立即停止呼叫。问
(1)用户拨外线遇忙的概率为多大？
(2)损失的话务量为多少？
(3)外线的利用率为多少？
(4)过负荷为100%时，外线的利用率为多少？
2、某车间机器发生故障为一泊松流，平均4台/小时。车间只有一名维修工，平均7分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障处理时间降到5分钟，但这一特殊工具的使用费用为5元/分钟。机器故障停工每台每分钟损失5元，问购置这台特殊工具是否合适？
3、有M/M/n：¥/¥/FIFO(先到先服务)系统，输入业务量为r，求：
当n=1, 2 , 3时的等待概率D，和平均逗留队长Ld 的公式。
No.12 存储论
1、某工厂每年需某种原料1000kg，一次定购费为200元，定购量Q与单价k的关系为
0 £ Q < 500kg， k1 =2元/kg
500 £ Q < 1000kg， k2 =1.5元/kg
1000 £ Q, k3 =1.2元/kg
已知原料存储费也与Q有关
0 £ Q < 500kg， Cs1 =2元/kg.年
500 £ Q < 1000kg， Cs2 =1.5元/kg.年
1000kg £ Q, Cs3 =1.2元/kg.年
求最佳订货量Qm，并求该订货量下的全年总费用C(Qm)。

2、推导连续进货、允许缺货模型的最佳订货量Q0和最佳订货周期T0的公式。
附录：爱尔兰损失表 En(A)
n B
0.005
0.01
0.05
0.1
0.2
0.3
1
0.005
0.010
0.053
0.111
0.250
0.429
2
0.105
0.153
0.381
0.595
1.000
1.449
3
0.349
0.455
0.899
1.271
1.930
2.633
4
0.701
0.869
1.525
2.045
2.945
3.891
5
1.132
1.361
2.218
2.881
4.010
5.189
6
1.622
1.909
2.960
3.758
5.109
6.514
7
2.157
2.501
3.738
4.666
6.230
7.857
8
2.730
3.128
4.543
5.597
7.369
9.213
9
3.333
3.783
5.370
6.546
8.522
10.579
10
3.961
4.461
6.216
7.511
9.685
11.953
11
4.610
5.160
7.076
8.487
10.857
13.333
12
5.279
5.876
7.950
9.474
12.036
14.719
13
5.964
6.607
8.835
10.470
13.222
16.109
14
6.663
7.352
9.730
11.473
14.413
17.503
15
7.376
8.108
10.633
12.484
15.608
18.899
16
8.100
8.875
11.544
13.500
16.807
20.300
17
8.834
9.652
12.461
14.522
18.010
21.702
18
9.578
10.437
13.385
15.548
19.216
23.105
19
10.331
11.230
14.315
16.579
20.424
24.510
20
11.092
12.031
15.249
17.613
21.635
25.917
21
11.860
12.838
16.189
18.651
22.848

22
12.635
13.651
17.132
19.692
24.064

23
13.416
14.470
18.080
20.737
25.281

24
14.204
15.295
19.031
21.784
26.499

25
14.997
16.125
19.985
22.833
27.720

26
15.795
16.959
20.943
23.885
28.941

27
16.598
17.797
21.904
24.939
30.164

28
17.406
18.640
22.867
25.995
31.388

29
18.218
19.487
23.833
27.053
32.614

30
19.034
20.337
24.802
28.113
33.840

31
19.854
21.191
25.773
29.174
35.067

32
20.678
22.048
26.746
30.237
36.295

33
21.505
22.909
27.721
31.301
37.524

34
22.336
23.772
28.698
32.367
38.754

35
23.169
24.638
29.677
33.434
39.985

36
24.006
25.507
30.657
34.503
41.216

37
24.846
26.378
31.640
35.572
42.448

38
25.689
27.252
32.624
36.643
43.680

39
26.534
28.129
33.609
37.715
44.913

40
27.382
29.007
34.596
38.787
46.147

习题课1
1、某工厂生产用2单位A和1单位B混合而成的成品出售，市场无限制。A和B可以在该工厂的3个车间中的任何车间生产，生产每单位的A和B在各车间消耗的工时如下表。
消耗工时
车间1
车间2
车间3
A
2
1
1.5
B
1
2
1.5
可用工时
100
120
100
试建立使成品数量最大的线性规划模型。
2、某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配方规定了这三种饮料中A和C的极限成分，具体见下表，
饮料品种
规 格
每升售价(元)
需求量
甲 (1)
A≥60％，C≤20％
6.80
1500
乙 (2)
A≥15％，C≤60％
5.70
3000
丙 (3)
C≤50％
4.50
无限制
A、B、C三种原料每月的供应量和每升的价格如下表。

供应量(升/月)
价格(元/升)
A
2000
7.00
B
2500
5.00
C
1200
4.00
饮料甲、乙、丙分别由不同比例的A、B、C调兑而成，设调兑后不同成分的体积不变，求最大收益的生产方案。
3、将下列线性规划化为标准形式

4、求上题的对偶规划。
习题课2
1．用连续型动态规划求解下题

2．求下面网络的中心和中位点（图中每条边上标的是两点间的距离）。
3．存货问题
（1）某小型超市洗发水日销售量为几何分布 px=p(1–p)x, x=0,1,2,…。缺货损失费为每瓶1元，当日售不出去经计算损失0.1元，若p=0.5，问最佳日进货量为多少？
（2）某小型超市食用油日销售量为负指数分布，日均销售量统计值为100公斤，当a=1, b=0.25，求最佳日进货量。
（3）若食用油日销售量为正态分布，均值为100，方差49，a, b同上，求最佳日进货量。
标准正态分布表：
Z
F(Z)
Z
F(Z)
Z
F(Z)
0.00
0.500000
0.95
0.828944
1.70
0.955434
0.50
0.691463
1.00
0.841345
1.80
0.964070
0.60
0.725747
1.10
0.864334
1.90
0.971283
0.70
0.758036
1.20
0.884930
2.00
0.977250
0.75
0.773373
1.30
0.903200
2.25
0.987776
0.80
0.788145
1.40
0.919243
2.50
0.993790
0.85
0.802338
1.50
0.933193
2.75
0.997020
0.90
0.815940
1.60
0.945201
3.00
0.998650