1
一、问题重述
1.1、问题一 :若网络中边上的数据为对应该条边的地下管道铺设费用,问如何
选择铺设路线使得地下管道的铺设总费用达到最小
1.2、问题二 :若边上的权为管道长度,现要从 v1 到每个 vi(i=1,⋯,10)铺
设一条专用电缆,问如何布线才能使所用的电缆线总长度最短?
v1
v4 5
6 24
5
v8 4
8
3
9 6
85
7
102 5
1
3
v2
v6
v3
v7v5
v9 v10
二、模型的建立与求解
2.1 问题一
对于问题一,它实际是最小生成树问题, 即要求以 1v 为根到每一个顶点都有一条
边相连,并且使得总权值最小。把图中的所有顶点放在集合 V 中,把所有的边
放在 E中,构成一个网络 G=(V,E)。所以建立最小生成树问题的 0-1整数规划
模型,并用 prim 算法编写程序进行求解。
2.1.1模型:最小生成树问题的 0-1整数规划模型
1)