7. 设有一个外贸公司计划在1至4月份从事某种商品的经营。已知它的仓库最多可存储1000件这种商品，该公司开业时有存货500件，根据预测，该种商品从1至4月份进价和售价如表7-25所示。问如何安排进货量和销售量，使该公司获得最大利润（假设四月底库存为零）。
表7-25 月份 进价（百元/件） 售价（百元/件） 1 10 12 2 9 9 3 11 13 4 15 17 8. 某人外出旅游，需将5种物品装入包裹，包裹容量有限，总重量不能超过13公斤，物品的单件重量及价值如表7-26所示。试问如何装这些物品使总价值最大？
表7-26
物品 单件重量（kg） 单件价值（元） A 7 9 B 5 4 C 4 3 D 3 2 E 1 0.5 9. 某厂设计一种电子设备，由三种元件D1，D2，D3组成，已知这三种元件的价格和可靠性如表7-27所示。要求在设计中所使用元件的费用不超过105元，试问应如何设计使设备的可靠性达到最大（不考虑重量的限制）。
表7-27
元件 D1 D2 D3 单价（元） 30 15 20 可靠性 0.9 0.8 0.5 21
第八章 习 题
1. 用破圈法和避圈法求下图的最小生成树 V2 13 V3 5 12 11 16 19 7
V6 9 V4 7 V1
11 8
V8
21
V5 10 4 V7
7 V9
图8—28
2.求下列各图的最小生成树
４ ５ ３ ２ ３ ２ １
９ ３ ６ １ ８ 1 ５ ４ ２ ７ １ ２ ４ ２ ３
４ ５ ３ ６
（1）
８ （2） ６ ３ ４ ２ ５
２ ７ ７ １ ３ ４
５ ３ ２ ４
７ （3）
图8—29
3．写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。
V1
V4 V2
V1 VV2 V3
6 V5 V5 V4 V3 (1)
(2)
图8—30
22
4．用标号法求图8—30中从v1到各顶点的最短距离
V2 2 V1
3 6 5 V3 7 V4 5 2 V5 2 1 3 1 V6 4 V7
4 3 1
V8 6 V9 7 3 V10
4 8 V11
3 7
图8—31
5．已知8个村镇，相互间距离如下表所示,已知1号村镇离水源最近，为5公里，问从水源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修，水管要求在各村镇处分开）。
各村镇间距离 （单位：千米） 到 从 1 2 3 4 5 6 7 2 1.5 3 2.5 1.0 4 1.0 2.0 2.5 5 2.0 1.0 2.0 2.5 6 2.5 3.0 2.5 1.5 3.0 7 3.5 2.5 2.0 1.5 1.8 0.8 8 1.5 1.8 1.0 1.0 1.5 1.0 0.5
6．用标号法求下面网络的最大流. 4 9
10 10
V1 10 15
8 6 12
8
8 12 18 14
15 6 Vt
13 图8——32
23
2
8 3 3 4 Vt 5 2 V1 3
3 5 5 4
4 图8——33
7．求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量.
(3,4) (5,6) (6,6) (7,4) (3,2)
V1 Vt V1 (2,3) (5,1) (4,1)
(4,19) (8,2) (9,2) (10,5)
(2,3)
(1)
(2) 图8——34
8.求解图8—35中所示的中国邮递员问题（A点是邮局所在地）
3 2 4 A
2 2 2 2 4 4 2 3
5 5
2 2 3 2 4 图8—35
(1,1) Vt
24
9．如图8—35，发点S1，S2分别可供应10和15个单位，收点T1和T2可接收10个个单位，求最大流，边上的数为cij。 v1 3 7 S1
2 2 T1
4 6 3 S2
4 T2
6 8 v2 图8——36 25
和25