初级药师报名-巴甫洛夫很忙

5.（4分）见下图，现提供一网络，并提供一初始可行流，弧旁的数字（C
ij
,f
ij
）分别代
表（容量，流量）。请找出一条增广链，请直接在图上标号。

v
2

v
1

v
4

v
6

v
5

v
3

6 ．（6分）求下图
v
1
到
v
5
的最短路。（需要写出主要的 步骤）

6
v
1

2
v
4

v
2

8
3
2
v
3

8

1
v
5

7．（3分）用奇偶点图上作业法求解下图所示的中国邮递员问题，并求出最优解的总
权？

v
1

4
v
3

3
v
5

2
v
2

8
v
4

5
v
6

1 6


8．（6分）根据下面的作业明细表绘制网络图。

表1
工 序
紧前工序
时间

9.（10分）已知如下网络计划图，计算网络的时 间参数，求网络计划的关键线路（事
项的时间请直接标于图中，工序的时间需列表给出）。
A

2
B

3
C

1
D
A，B
3
E
A，B
5
F
B
6
G
C
4
H
D
6
I
E，F
3
J
G
5

②
a
10
d
25
⑤
g
30
i
f
20
h
j
①
20
c
b
40
④
e
35
⑦
10
③ ⑥

八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）
.
(1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大
流量。（3）证明（2 ）中得到的结论。(题中k=考生学号最后一位，0
号写成10)
1、已知网络上某条链如下图，问：x为何值时，该链不是增流链，为
什么？
x＝0（1分）。此时后向边为零边，不符合增流链定义（2分）。
八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）
v
s(3,1)
v
1
(1,x)
v
3
(4,2)
v
t
.
(1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大流量。（3）证明（2）中得到的结论。(题中k=考生学号最后一位.0号
写成10)

ff
22
（1）
1x4.

x3
（3分）
（2）网路上增流链Ⅰ：（令k=1）
v
s< br>(6,3)
v
1
(1,0)
v
3
(4,2)
v
t
v
s
(6,4)
v
1
(1,1)
v< br>3
(4,3)
v
t
； 调整量θ＝1，调整后，
（2分）

网络上增流链Ⅱ：
v
s
(6 ,4)
v
1
(1,1)
v
2
(5,3)
v
3
(4,3)
v
t
调整量θ＝1。调整后，
；
v
s
(6,5)
v
1
(1,0)
v< br>2
(5,4)
v
3
(4,4)
v
t
最终网络 图如下图：
（2分）
（2分）
最大流量＝9，

f
ij

如图
。（2分） （3）由标号法求出，
V
1


v
s
,v1

，
V
1


v
2
,v< br>3
,v
4
,v
t


求出截线如图所示。
而网络上的割C=9，即
f
ij
C
ij

所以网络上流为最大流。（4分）
九(10分)、下图为一网络，网络中每条弧上的数字为该条弧的（容量，流量）。
v
2
(9,5)
(6,3)
v
5
(7,5)
(
3,3) (5,2)
(4,1)
(3,2)
(
3,2)
v

1
v
4
v
7
(1,1)
(5,1)
(7,3)
v
3
(4,0)
v
6

1(6分)、求该网络的最大流和最大流量；

2(4分)、若想增加网络的最大流量，首先应改善哪些瓶颈弧的容量？
例：设有某种肥料共 6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系
如下表所示。试求对每块田施多少 单位重量的肥料，才能使总的粮食增产最多。

粮 田
施 肥
1
1 20
2
25
3
18
4
28

2
3
4
5
6
42
60
75
85
90
45
57
65
70
73
39
61
78
90
95
47
65
74
80
85
所以最优解为2，2，0，2，最大增产量为134。
例 某工厂有100太机器，拟分四 个周期使用，在每一周期中有两种生产任务，据经验，把
1
x
1
台机器投入第 一种生产任务，则在一个周期内有台机器作废；余下的机器全部投入第
3
1
二种生产任 务，且有机器作废。在第一种任务中，每台机器可收益10个单位，而第二种
10
任务中每台机 器可收益7个单位，问怎样分配机器，能使总收益为最大？


六、某公司打算将3 千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所
分配的投资有关。各工厂在获得不 同的投资额时所能增加的利润如下表所示，问应如何分配
资金，使公司总的利润为最大（15分）
利润 投资
工厂
1
2
3
0
0
0
0
1千万
2.5
3
2
2千万
4
5
6
3千万
10
8.5
9
石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的
地，B、C、D分别为 三个必须建立油泵加压站的地区，其中的B
1
、B
2
、B
3
;C
1
、
C
2
、C
3
;D
1
、D
2
分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，
线段旁的数字为铺 设管线所需要的费用，问如何铺设管道才使总费用最小？
6 2

B

1



3

C

1



D


3
1
5 5
3
3
E

A
5
B



2

C
7 4
2 2

4 4
4
D
2

4 1 5 4

B

3
5
C

3