【案例08】钢管订购和运输返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：Python3.11
运行环境：Intel Core i7-7700K CPU 4.2GHz, nVidia GeForce GTX 1080 Ti
本教案所涉及的数据集仅用于教学和交流使用，请勿用作商用。

最后更新：2024年2月25日

【知识点】

图论、最小费用、最短路径

【问题描述】

要铺设一条 $A_1 \rightarrow A_2 \rightarrow \cdots \rightarrow A_{15}$ 的输送天然气的主管道, 如图1 所示。经筛选后可以生产这种主管道钢管的钢厂有 $S_1, S_2,...,S_7$ 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。为方便计算，1km主管道钢管称为 $1$ 单位钢管。

图1 交通网络及管道图

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂 $S_i$ 在指定期限内能生产该钢管的最大数量为 $s_i$ 个单位，钢管出厂销价 $1$ 单位钢管为 $p_i$ 万元，见表1， $1$ 单位钢管的铁路运价见表2。

表1 各钢管厂的供货上限及销价


$i$	1	2	3	4	5	6	7
$s_i$	800	800	1000	2000	2000	2000	3000
$p_i$	160	155	155	160	155	150	160

表2 单位钢管的铁路运价


里程(km)	≤300	301～350	351～400	401～450	451～500
运价(万元)	20	23	26	29	32
里程(km)	501～600	601～700	701～800	801～900	901～1000
运价(万元)	37	44	50	55	60

1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点 $A_1, A_2,.., A_{15}$ ，而是管道全线）。

请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。

【答案与解析】

一、问题分析

问题的建模目的是求一个主管道钢管的订购和运输策略，使总费用最小。首先，问题给出了7个供选择的钢厂，选择哪些？订购多少钢管？是一个要解决的问题。其次，每一个钢厂到铺设地点大多都有多条可供选择的运输路线，应选择哪一条路线运输，取决于建模的目标。而目标总费用包含两个组成部分：订购费用和运输费用。订购费用取决于单价和订购数量，运输费用取决于往哪里运和运输路线。结合总目标的要求，可以很容易地想到应选择运费最小的路线。

从同一个钢管厂订购钢管运往同一个目的地，一旦最小运输费用路线确定，则单位钢管的运费就确定了，单位钢管的订购及运输费用=钢管单价+运输费用。因此，同一个钢管厂订购钢管运往同一个目的地的总费用等于订购数量乘以单位钢管的购运费用（单价+单位钢管运费）。因而，在制定订购与运输计划时，要分成两个子问题考虑：

（1）运输路线及运输费用的确定：钢管可以通过铁路或公路运输。公路运费是运输里程的线性函数，但是铁路运价却是一种分段的阶跃的常数函数。因此在计算时，不管对运输里程还是费用而言，都不具有可加性，只能将铁路运价（即由运输总里程找出对应费率）和公路运价分别计算后再叠加。

（2）铺设方案的设定：从钢管厂订购若干个单位的钢管运送至枢纽点 $A_1, A_2,.., A_{15}$ ，再由枢纽点按一个单位计分别往枢纽点两侧运送至最终铺设地点，计算从枢纽点开始的铺设费用。

虽然准备把问题分解为两个子问题进行处理，但最终优化时，必须作为一个综合的优化问题进行处理，否则无法得到全局最优解。

二、模型假设

一个钢管厂订购钢管可能会被运往多个铺设结点，一个铺设结点也可能获得多个钢管厂生产的钢管。
题目没有明确给出装卸费用，因此可以简单假设总是采用最经济的运输方式，且运输过程中允许多次装卸，也即公路、铁路转运不计费用。
假设铁路运输路线应该是最短路径，并且采用连续路径计价方式一定优于分段计价方式。（实际上本题中的数据并不符合这一假设，例如，650km的运价为44万元，而分成300km和350公里两段计价只需要43万元，这显然不符合实际。）

三、模型建立

记第 $i(i=1,2,...,7)$ 个钢厂的最大供应量为 $s_i$ ，从第 $i$ 个钢厂到第 $j$ 个铺设节点 $A_j(j=1,2,...,15)$ 的订购和运输费用为 $c_{ij}$ ；用 $l_k = |A_k A_{k+1}|(k=1,2,...,14)$ 表示管道第 $k$ 段需要铺设的钢管量。 $x_{ij}$ 是从钢厂 $S_i$ 运到节点 $j$ 的钢管量， $y_j$ 是从节点 $j$ 向左铺设的钢管量， $z_j$ 是从节点 $j$ 向右铺设的钢管量。

根据题中所给数据，可以先计算出从供应点 $S_i$ 到需求点 $A_j$ 的最小购运费 $c_{ij}$ （即出厂售价与运输费用之和），再根据 $c_{ij}$ 求解总费用，总费用应包括：订购费用（已包含在 $c_{ij}$ 中），运输费用（由各厂 $S_i$ 经铁路、公路至各点 $A_j，i=1,2,...,7, j=1,2,...,15$ ，铺设管道 $A_j A_{j+1}(j=1,2,...,14)$ 的运费。

3.1 算法选择

求解最短路径的算法主要有Dijkstra算法、Floyd算法、SPFA算法、Bellman-Ford算法等。本题弧上的权（距离）都是正数，可以考虑Dijkstra算法，但由于需要求解的是任意两点之间的最短路径，因此使用Floyed-Warshall算法更合适。我们可以直接用来计算铁路、公路的最短距离 $d^{(1)}_{ij}$ 和 $d^{(2)}_{ij}$ ，以及最终的最小运费 $c_{ij}$ 。下面给出这三个量的建模过程。

3.2 运费矩阵的计算模型

购买单位钢管及从 $S_i(i=1,2,...,7)$ 运送到 $A_j(j=1,2,...,15)$ 的最小购运费用 $c_{ij}$ 的计算如下。

1. 计算铁路任意两点间的最小运输费用

由于铁路运费不是连续的，故不能直接构造铁路费用赋权图，用Floyd算法来计算任意两点间的最小运输费用。但可以首先构造铁路距离赋权图，用Floyd算法来计算任意两点间的最短铁路距离值，再依据题中的铁路运价表，求出任意两点间的最小铁路运输费用。这就巧妙地避开铁路运费不是连续的问题。

首先构造铁路距离赋权图 $G_1=(V,E_1,W_1)$ ，其中 $V=\{S_1,...,S_7,A_1,...,A_{15},B_1,...,B_{17}\} = \{v_1,v_2,...,v_{39} \}$ ，总共39个顶点的编号见图1； $W_1 = (w^{(1)}_{ij})_{39 \times 39}$ ，

$w^{(1)}_{ij} = \begin{cases} d^{(1)}_{ij}, & v_i, v_j 之间有铁路直接相连 \\ +\infty, & v_i, v_j 之间没有铁路直接相连 \\ \end{cases} \tag{1}$

式中 $d^{(1)}_{ij}$ 表示 $v_i, v_j$ 两点之间的铁路里程。

然后应用Floyd算法求得任意两点间的最短铁路距离。

根据铁路运价表，可以得到铁路费用赋权完全图 $\tilde{G_1} = (V, E_1, \tilde{W_1})$ ，其中， $\tilde{W_1} = (c^{(1)}_{ij})_{39 \times 39}$ ，这里 $c^{(1)}_{ij}$ 为第 $i,j$ 顶点间的最小铁路运输费用，若两点间的铁路距离值为无穷大，则对应的铁路运输费用也为无穷大。

2. 计算公路任意两点间的最小运输费用

构造公路费用赋权图 $G_2=(V,E_2,W_2)$ ，其中 $V$ 同上， $W_2 = (w^{(2)}_{ij})_{39 \times 39}$ ，

$w^{(2)}_{ij} = \begin{cases} 0.1d^{(2)}_{ij}, & v_i, v_j 之间有公路直接相连 \\ +\infty, & v_i, v_j 之间没有公路直接相连 \\ \end{cases} \tag{1}$

式中 $d^{(1)}_{ij}$ 表示 $v_i, v_j$ 两点之间的公路里程。

3. 计算任意两点间的最小运输费用

经过第（1）、（2）步的预处理，就可以将两个子网络组合成一个网络，此时两个子网络可以看成是两个完全子图。换句话说，两个结点之间可以用铁路、公路交叉运送，所以任意相邻两点间的最小运输费用为铁路、公路两者最小运输费用的最小值。

构造铁路公路的混合赋权图 $G=(V,E,W)$ ， $W = (w^{(3)}_{ij})_{39 \times 39}$ ，其中 $c^{(3)}_{ij} = \min(c^{(1)}_{ij}, c^{(2)}_{ij})$ 。

对图 $G$ 应用Floyd算法，就可以计算出所有顶点对之间的最小运输费用，最后提取需要的 $S_i(i=1,2,...,7)$ 到 $A_j(j=1,2,...,15)$ 的最小运输费用 $\tilde{c_{ij}}$ （单位：万元）见表3。

表6.11 最小运费计算结果

	$A_1$	$A_2$	$A_3$	$A_4$	$A_5$	$A_6$	$A_7$	$A_8$	$A_9$	$A_{10}$	$A_{11}$	$A_{12}$	$A_{13}$	$A_{14}$	$A_{15}$
$S_1$	170.7	160.3	140.2	98.6	38	20.5	3.1	21.2	64.2	92	96	106	121.2	128	142
$S_2$	215.7	205.3	190.2	171.6	111	95.5	86	71.2	114.2	142	146	156	171.2	178	192
$S_3$	230.7	220.3	200.2	181.6	121	105.5	96	86.2	48.2	82	86	96	111.2	118	132
$S_4$	260.7	250.3	235.2	216.6	156	140.5	131	116.2	84.2	62	51	61	76.2	83	97
$S_5$	1255.7	245.3	225.2	206.6	146	130.5	121	111.2	79.2	57	33	51	71.2	73	87
$S_6$	1265.7	255.3	235.2	216.6	156	140.5	131	121.2	84.2	62	51	45	26.2	11	28
$S_7$	1275.7	265.3	245.2	226.6	166	150.5	141	131.2	99.2	76	66	56	38.2	26	2

任意两点间的最小运输费用加上出厂售价, 得到单位钢管从任一个 $S_i(i=1,2,...,7)$ 到 $A_j (j=1,2,...,15)$ 的购买和运送最小费用 $c_{ij}$ 。

相关计算方法的Python代码如下所示。

# ch0819Anli61
import cvxpy as cp
import numpy as np
import networkx as nx
import pandas as pd

# 一、 计算各节点间的最短路径（最小费用）
# 1. 构造顶点表V
s1 = ['S'+str(i) for i in range(1,8)]   # 钢管厂S开头S[1,...,7]
s2 = ['A'+str(i) for i in range(1,16)]  # 铺设管道A开头A[1,...,15]
s3 = ['B'+str(i) for i in range(1,18)]  # 火车站B开头B[1,...,17]
V = s1 + s2 + s3                        # 构造顶点字符列表

# 2. 构造铁路赋权图G1(V, E1, W1)
# 2.1 生成图G1的顶点
G1 = nx.Graph();                        # 初始化图G1
G1.add_nodes_from(V)                    # 将顶点加入到图G1

# 2.2 生成图G1的加权边
E1 = [('B1','B3',450),('B2','B3',80),('B3','B5',1150),('B5','B8',1100),
      ('B4','B6',306),('B6','B7',195),('S1','B7',20),('S1','B8',202),
      ('S2','B8',1200),('B8','B9',720),('S3','B9',690),('B9','B10',520),
      ('B10','B12',170),('S4','B12',690),('S5','B11',462),('B11','B12',88),
      ('B12','B14',160),('B13','B14',70),('B14','B15',320),('B15','B16',160),
      ('S6','B16',70),('B16','B17',290),('S7','B17',30)]    # 初始化带权边表E1
G1.add_weighted_edges_from(E1)         # 构造铁路赋权图
d1 = nx.floyd_warshall_numpy(G1)       # 求G1各顶点的最短距离矩阵
d1 = np.array(d1)                      # 转换为array数组

# 2.3 按照各顶点间的最短距离计算运输费用C1
c1 = np.ones(d1.shape)*np.inf
c1[d1==0] = 0; c1[(d1>0) & (d1<=300)] = 20;
c1[(d1>300) & (d1<=350)]=23; c1[(d1>350) & (d1<=400)]=26
c1[(d1>400) & (d1<=450)]=29; c1[(d1>450) & (d1<=500)]=32
c1[(d1>500) & (d1<=600)]=37; c1[(d1>600) & (d1<=700)]=44
c1[(d1>700) & (d1<=800)]=50; c1[(d1>800) & (d1<=900)]=55
c1[(d1>900) & (d1<=1000)]=60; 
ind=(d1>1000) & (d1<np.inf)
c1[ind] = 60+5*np.ceil(d1[ind]/100-10)

# 3. 构造铁路赋权图G2(V, E2, W2)
# 3.1 生成图G2的顶点
G2 = nx.Graph()
G2.add_nodes_from(V)
E2 = [('A1','A2',104),('A2','B1',3),('A2','A3',301),('A3','B2',2),
      ('A3','A4',750),('A4','B5',600),('A4','A5',606),('A5','B4',10),
      ('A5','A6',194),('A6','B6',5),('A6','A7',205),('A7','B7',10),
      ('S1','A7',31),('A7','A8',201),('A8','B8',12),('A8','A9',680),
      ('A9','B9',42),('A9','A10',480),('A10','B10',70),('A10','A11',300),
      ('A11','B11',10),('A11','A12',220),('A12','B13',10),('A12','A13',210),
      ('A13','B15',62),('A13','A14',420),('S6','A14',110),('A14','B16',30),
      ('A14','A15',500),('A15','B17',20),('S7','A15',20)]    # 初始化带权边表E2
G2.add_weighted_edges_from(E2)  # 构造公路赋权图
c2 = nx.to_numpy_array(G2)      # 导出图G2的邻接矩阵
c2 = np.array(c2)               # 转换为array数组

# 3.3 按照各顶点间的最短距离计算运输费用C1
c2[c2==0] = np.inf

# 4. 计算任意两点间的最小运费
# 4.1 初始化多重图的权重(计算既有公路，又有铁路的两个子图任意两点间的最小费用，取两者中小者)
c3 = np.minimum(c1, 0.1*c2)

# 4.2 根据去重后的图的权重，重新计算两个子图合成后的新图的任意两点间的最短路径
G3 = nx.Graph(c3)
c4 = nx.floyd_warshall_numpy(G3)            # 求最短距离矩阵
c5 = c4[:7, 7:22]   #提出7行15列的运费数据，即邻接矩阵中S-A之间的最短距离

# 5. 输出结果
# 5.1 输出各顶点间的最短距离
f = pd.ExcelWriter('../Data/Project03/project03.xlsx')
pd.DataFrame(c5).to_excel(f, 'Distance', index=True, header=True)
# f.close()
print(pd.DataFrame(c5))

      0      1      2      3      4      5      6      7      8      9   \
0  170.7  160.3  140.2   98.6   38.0   20.5    3.1   21.2   64.2   92.0   
1  215.7  205.3  190.2  171.6  111.0   95.5   86.0   71.2  114.2  142.0   
2  230.7  220.3  200.2  181.6  121.0  105.5   96.0   86.2   48.2   82.0   
3  260.7  250.3  235.2  216.6  156.0  140.5  131.0  116.2   84.2   62.0   
4  255.7  245.3  225.2  206.6  146.0  130.5  121.0  111.2   79.2   57.0   
5  265.7  255.3  235.2  216.6  156.0  140.5  131.0  121.2   84.2   62.0   
6  275.7  265.3  245.2  226.6  166.0  150.5  141.0  131.2   99.2   76.0   

      10     11     12     13     14  
0   96.0  106.0  121.2  128.0  142.0  
1  146.0  156.0  171.2  178.0  192.0  
2   86.0   96.0  111.2  118.0  132.0  
3   51.0   61.0   76.2   83.0   97.0  
4   33.0   51.0   71.2   73.0   87.0  
5   51.0   45.0   26.2   11.0   28.0  
6   66.0   56.0   38.2   26.0    2.0

3.2 总费用的数学规划模型

1. 目标函数

（1）从钢管厂到各枢纽点 $A_1, A_2,..., A_{15}$ 的总购运费用为 $\sum^7_{i=1} \sum^{15}_{j=1} c_{ij} x_{ij}$ 。

（2）铺设管道不仅只运输到枢纽点，而是要运送并铺设到全部管线，注意到将总量为 $y_j$ 的钢管从枢纽点往左运到每单位铺设点，其运费应为第一公里、第二公里、直到第 $y_j$ 公里的运费之和，即为：

$0.1 \times (1+2+...+y_j) = \frac{0.1}{2} y_j(y_j + 1). \tag{2}$

从枢纽点 $A_j$ 往右也一样，对应的铺设费用为：

$0.1 \times (1+2+...+z_j) = \frac{0.1}{2} z_j(z_j + 1). \tag{3}$

总的铺设费用为：

$\frac{0.1}{2} \sum^{15}_{j=1} [y_j(y_j + 1) + z_j(z_j + 1)]. \tag{4}$

因而，总购运费用为：

$\sum^7_{i=1} \sum^{15}_{j=1} c_{ij} x_{ij} + \frac{0.1}{2} \sum^{15}_{j=1} [y_j(y_j + 1) + z_j(z_j + 1)].\tag{5}$

2. 约束条件：

（1）根据钢管厂生产能力约束或购买限制，判断是否从第 $i$ 个钢管厂订购钢管，于是可以知道所需要的总钢管数量，应该等于每个参与生产钢管的钢管厂所生产的钢管总数，于是有：
$\sum^{15}_{j=1} x_{ij} \in \{0\} \bigcup [500, s_i], i=1,2,...,7.$

（2）购运量应等于铺设量
$\sum^{7}_{i=1} x_{ij} = z_j + y_j, j=1,2,...,15.$

（3）枢纽点间距约束：从两个相邻枢纽点分别往右、往左铺设的总单位钢管数应等于其间距，即：
$z_j + y_{j+1} = |A_j A_{j+1}| = l_j, j=1,2,...,14.$

（4）端点约束：从 $A_1$ 枢纽点只能往右铺，不能往左铺；从枢纽点 $A_{15}$ 只能往左铺，不能往右铺，故：
$y_1 = 0, z_{15} = 0$

（5）非负约束：
$x_{ij} \geq 0, y_j \geq 0, z_j \geq 0, i=1,2,...,7, j=1,2,...,15.$

综上所述，总费用最小化问题的数学规划模型为：
$\min \sum^7_{i=1} \sum^{15}_{j=1} c_{ij} x_{ij} + \frac{0.1}{2} \sum^{15}_{j=1} [y_j(y_j + 1) + z_j(z_j + 1)]$

$s.t. \begin{cases} \sum^{15}_{j=1} x_{ij} \in \{0\} \bigcup [500, s_i], i=1,2,...,7. \\\\ \sum^{7}_{i=1} = z_j + y_j, j=1,2,...,15. \\\\ z_j + y_{j+1} = |A_j A_{j+1}| = l_j, j=1,2,...,14. \\\\ y_1 = 0, z_{15} = 0 \\\\ x_{ij} \geq 0, y_j \geq 0, z_j \geq 0, i=1,2,...,7, j=1,2,...,15. \\ \end{cases} \tag{6}$

四、模型求解

使用计算机求解上述数学规划时，需要对约束条件(6)中的第一个非线性约束
$\sum^{15}_{j=1} x_{ij} \in \{0\} \bigcup [500, s_i], i=1,2,...,7. \tag{7}$

进行处理。引进 $0-1$ 变量：

$t_{i} = \begin{cases} 1, & 钢管厂i生产 \\\\ 0, & 钢管厂i不生产 \end{cases}.\tag{8}$

把约束条件(7)转化为线性约束：
$500 t_i \leq \sum^{15}_{j=1} x_{ij} \leq s_i t_i, i=1,2,...,7 \tag{9}$

利用Python软件求得总费用的最小值为127.8632亿。具体的订购和运输方案见表4 所示。

表4 钢管订购和运输方案

钢厂	生产量	A2	A3	A4	A5	A6	A7	A8	A9	A10	A11	A12	A13	A14	A15
$S_1$	800	0	0	319	15	200	266	0	0	0	0	0	0	0	0
$S_2$	800	179	321	0	0	0	0	300	0	0	0	0	0	0	0
$S_3$	1000	0	187	149	0	0	0	0	664	0	0	0	0	0	0
$S_4$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
$S_5$	1015	0	0	0	600	0	0	0	0	0	415	0	0	0	0
$S_6$	1516	0	0	0	0	0	0	0	0	351	0	86	333	621	165
$S_7$	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

# 二、求解目标函数，生成最有订购计划及最小总费用
# 1. 初始化变量
s = np.array([800, 800, 1000, 2000, 2000, 2000, 3000])  # 各钢管厂的生产上限
p = np.array([160, 155, 155, 160, 155, 150, 160])       # 各钢管厂钢管的单价
b = np.array([104, 301, 750, 606, 194, 205, 201,        # 各钢管结点间的距离
              680, 480, 300, 220, 210, 420, 500])       
c = np.tile(p, (15,1)).T + c5                           # 每单位钢管的购买+运输费用

# 2. 定义待优化的变量，
# x: 从钢管厂Si运到需求点Aj的钢管量
# y: 从需求点Aj往左铺设的钢管量
# z: 从需求点Aj往右铺设的钢管量
# t: 布尔变量，判断钢管厂Si是否进行生产
x = cp.Variable((7,15), integer=True)  #调整为整型
y = cp.Variable(15, pos=True); 
z = cp.Variable(15, pos=True)
t = cp.Variable(7, integer=True)

# 3. 定义目标函数
obj = cp.Minimize(cp.sum(cp.multiply(c, x))+0.05*cp.sum(y**2+y+z**2+z))

# 4. 定义约束条件
con = [500*t<=cp.sum(x,axis=1), cp.sum(x,axis=1)<=cp.multiply(s,t),
       cp.sum(x,axis=0)==y+z, y[1:]+z[:-1]==b,
       y[0]==0, z[14]==0,t>=0, t<=1, x>=0]

# 5. 定义求解问题并进行求解
prob = cp.Problem(obj, con);
prob.solve(solver='CPLEX')

# 6. 输出结果
print('总运费（最优值）：', prob.value); 
print('各钢管厂运输到各节点的钢管量（最优解）：\n', x.value)
sx = np.sum(x.value, axis=1)
pd.DataFrame(c).to_excel(f, 'TotalCost', index=True, header=True)
pd.DataFrame(x.value).to_excel(f, 'Scheme', index=True, header=True)
f.close()

总运费（最优值）： 1278631.6
各钢管厂运输到各节点的钢管量（最优解）：
 [[ -0.  -0.  -0. 319.  15. 200. 266. -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.]
 [ -0. 179. 321.  -0.  -0.  -0.  -0. 300.  -0.  -0.  -0.  -0.  -0.  -0.   0.]
 [ -0.  -0. 187. 149.  -0.  -0.  -0.  -0. 664.  -0.  -0.  -0.  -0.  -0.  -0.]
 [ -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.]
 [ -0.  -0.  -0.  -0. 600.  -0.  -0.  -0.  -0.  -0. 415.  -0.  -0.  -0.  -0.]
 [ -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0. 351.  -0.  86. 333. 621.  165.]
 [ -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  -0.  0.]]

五、分析与讨论

对于本题常见的问题包括：

只针对题目所给数据用"凑"的方法算出结果，没有给出解决此类问题的一般模型；
对铁路和公路混合运输网络处理不当，没能正确求出运费矩阵；
对“一个钢厂如果承担制造这种钢管，至少需要生产500个单位”这个要求处理不当，得到的至少具备最优。

【拓展练习】乡村建设问题

已知有6个村庄，各村的小学生人数如表1所示。各村间的距离如图1所示。现计划建造一所医院和一所小学，问医院应建在哪个村庄才能使最远村庄的人到医院看病所走的路最短？又问小学建在哪个村庄才能使得所有学生上学走的总路程最短？

村庄	$v_1$	$v_2$	$v_3$	$v_4$	$v_5$	$v_6$
小学生人数/个	50	40	60	20	70	90

【案例08】钢管订购和运输 返回首页