《管理运筹学》复习题及参考答案.doc

四、把下列线性规划问题化成原则形式：

2、minZ=2x1-x2+2x3

五、按各题规定。建立线性规划数学模型
1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：

根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。 问怎样安排生产计划，使总利润最大。

2、某建筑工地有一批长度为10米的相似型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?

1． 某运送企业在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示：
起运时间
服务员数
2—6
6—10
10一14
14—18
18—22
22—2
4
8
10
7
12
4
每个工作人员持续工作八小时，且在时段开始时上班，问怎样安排，使得既满足以上规定，又使上班人数至少?

五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相称于图解法可行域中的哪一种顶点。

六、用单纯形法求解下列线性规划问题：

七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。

八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目的函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目的函数后得Z=10

Xl
X2
X3
X4

—10
b
-1
f
g
X3
2
C
O
1
1／5
Xl
a
d
e
0
1
(1)求表中a～g的值 (2)表中给出的解与否为最优解?
（1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2） 表中给出的解为最优解
第四章 线性规划的对偶理论

五、写出下列线性规划问题的对偶问题
1．minZ=2x1+2x2+4x3

六、已知线性规划问题
应用对偶理论证明该问题最优解的目的函数值不不小于25

七、已知线性规划问题
maxZ=2x1+x2+5x3+6x4

其对偶问题的最优解为Yl﹡=4，Y2﹡=1，试应用对偶问题的性质求原问题的最优解。

七、用对偶单纯形法求解下列线性规划问题：

八、已知线性规划问题

(1) 写出其对偶问题 (2)已知原问题最优解为X﹡=(2，2，4，0)T，试根据对偶理论，直接求出对偶问题的最优解。
W* = 16
第五章 线性规划的敏捷度分析
四、某工厂在计划期内要安排生产I、Ⅱ两种产品。已知生产单位产品所需的设备台时及A、B两种原料的消耗如表所示：

I
Ⅱ

设备
原材料A
原材料B
1
4
0
2
0
4
8台时
16kg
12kg
该工厂每生产一件产品I可获利2百元，每生产一件产品Ⅱ可获利3百元。
(1)单纯形迭代的初始表及最终表分别如下表I、Ⅱ所示：
x1 x2 x3 x4 x5
xB -Z
0
2 3 O 0 0
X3
X4
X5
8
16
12
1 2 1 O 0
4 0 0 1 0
0 4 0 0 1

14
0 0 -3/2 -1/8 0
Xl
X5
X2
4
4
2
1 0 0 1/4 0
0 0 -2 1/2 1
0 1 1/2 -1/8 0
阐明使工厂获利最多的产品混合生产方案。 (2)如该厂从别处抽出4台时的设备用于生产I、Ⅱ，求这时该厂生产产品I、Ⅱ的最优方案。 (3)确定原最优解不变条件下，产品Ⅱ的单位利润可变范围。 (4)该厂预备引进一种新产品Ⅲ，已知生产每件产品Ⅲ，需消耗原材料A、B分别为6kg，3kg使用设备2台时，可获利5百元，问该厂与否应生产该产品及生产多少?
(1)使工厂获利最多的产品混合生产方案：生产I产品4件，生产II产品2件，设备台时与原材料A所有用完，原材料B剩余4kg，此时，获利14百元。 (2)X*=(4，3,2，0，o)Tz*=17 (3)0≤C2≤4 (4)应生产产品Ⅲ，产量为2。

五、给出线性规划问题

用单纯形表求解得单纯形表如下，试分析下列多种条件变化下最优解(基)的变化：
xl x2 x3 x4 x5
xB -Z
-8
0 0 -3 -5 -1
xl
x2
1
2
1 0 -1 4 -1
0 1 2 -1 1
(1)分别确定目的函数中变量X1和X2的系数C1，c2在什么范围内变动时最优解不变； (2)目的函数中变量X3的系数变为6； (3)增添新的约束X1+2x2+x3≤4
解：(1)3/4≤C1≤3 2≤C2≤8 (2)X*=(2，0，1，0，0，0)T Z*=10
(3)X*=(2，1，0，0，1，0)T Z*=7 (4)X*=(0，2，0，0，0，1/3)T Z*=25/3
第六章 物资调运规划运送问题
三、判断表(a)(b)(c)中给出的调运方案能否作为表上作业法求解时的初始解，为何?
(a)

Bl
B2
B3
B4
B5
B6
产量
Al
20
10

30
A2

30
20

50
A3

10
10
50
5
75
A4

20
20
销量
20
40
30
10
50
25

(b) (c)

Bl
B2
B3
B4
B5
B6
产量

Bl
B2
B3
B4
产量
Al

30

30
Al

6
5
11
A2
20
30

50
A2
5
4

2
11
A3

10
30
10

25
75
A3

5
3

8
A4

20

20
销量
5
9
9
7

销量
20
40
30
10
50
25

(a)可作为初始方案； (b)中填有数字的方格数少于9(产地数+销地数－1)，不能作为初始方案；
(c)中存在以非零元素为顶点的闭回路，不能作为初始方案
四、已知某运送问题的产销平衡表。单位运价表及给出的一种调运方案分别见表(a)和(b)，判断给出的调运方案与否为最优?如是阐明理由；如否。也阐明理由。
表(a)产销平衡表及某一调运方案 单位运价表
销地
产地

Bl

B2

B3

B4

B5

B6

产量
l
30
20

50
A2

30
10

40
A3

10
40
10

60
A4

20
11
31
销量
30
50
20
40
30
11

五、给出如下运送问题
销
运价
产
B1
B2
B3
B4
产量
Al
5
3
10
4
90
A2
1
6
9
6
40
A3
20
10
5
7
70
销量
30
50
80
40
200
(1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检查数，并检查该方案与否为最优方案

六、用表上作业法求给出的运送问题的最优解

甲
乙
丙
丁
产量
1
10
6
7
12
4
2
16
0
5
9
9
3
5
4
10
10
4
销量
5
2
4
6

甲
乙
丙
丁
产量
1
1
2
1

4
2

3
6
9
3
4

4
销量
5
2
4
6

在最优调运方案下的运送费用最小为118。
第七章 整数规划
四、用分枝定界法求解下列整数规划问题：(提醒:可采用图解法)
maxZ=40x1+90x2

五、用割平面法求解

六、下列整数规划问题

阐明能否用先求解对应的线性规划问题然后四舍五入的措施来求得该整数规划的一种可行解。
答：不考虑整数约束，求解对应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令x1=3，x2=x3=0，其中第2个约束无法满足，故不可行。
七、若某钻井队要从如下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10对应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件：
(1)在s1，s2，S4中至多只能选择两个； (2)在S5，s6中至少选择一种；(3)在s3，s6，S7，S8中至少选择两个； 试建立这个问题的整数规划模型

八、有四项工作要甲、乙、丙、丁四个人去完毕．每项工作只容许一人去完毕。每个人只完毕其中一项工作，已知每个人完毕各项工作的时间如下表。问应指派每个人完毕哪项工作，使总的消耗时间至少?
工作
人
I
Ⅱ
Ⅲ
Ⅳ
甲
乙
丙
丁
15
19
6
19
18
23
7
21
2l
22
16
23
24
18
19
17

第八章 图与网络分析
四、计算题
1．下图是6个都市的交通图，为将部分道路改导致高速公路，使各个都市均能通达，又要使高速公路的总长度最小，应怎样做?最小的总长度是多少?

2．对下面的两个连通图，试分别求出最小树。

3、 第1题中的交通图，求都市A到D沿公路走的最短路的路长及途径。

4．对下面两图，试分别求出从起点到终点的最短路线。

5．分别求出下面两图中从发点到收点的最大流。每条有向边上的数字为该边的容量限制。

6．下面网络中，点①，②是油井，点⑥是原油脱水处理厂，点③、④、⑤是泵站，各管道的每小时最大通过能力(吨／小时)如有向边上的标注。求从油井①、②每小时能输送到脱水处理厂的最大流量。
(提醒：虚设一种发点S，令有向边(S，1)，(S，2)的容量为∞)。

十一章
1、 需求：需求就是库存的输出。
2、 存贮费：一般是指每存贮单位物资单位时间所需花费的费用。
3、 缺货损失费：一般指由于中断供应影响生产导致的损失赔偿费。
4、 订货批量Q：存贮系统根据需求，为补充某种物资的库存而向供货厂商一次订货或采购的数量。
5、 订货间隔期T：两次订货的时间间隔可订货协议中规定的两次进货之间的时间间隔。
6、 记账间隔期R：指库存记账制度中的间隔记账制所规定的时间。
十二章