《管理运筹学》实验五
货郎担问题
某快递公司在 A点,需要给 B,C,D,E,F 五个快递点送货。 各点之间的距离如图所示。应如何设计一条行驶路线, 使送货车通过每一快递点所行驶的距离最少。
A 4 2.2 1.6 1.8 C 1.5 E 2.8 4.2 2.8
6
B 3
2.6
D
F
中国邮路问题
v1 是邮局所在地。请帮邮递员设计一条投递线路 (从邮局出发,将邮件投递到他管辖的所有街道, 最后回到邮局),使总路长最短。
v1 5 v2 5 9
7
2
v834源自v7 36v94 v4
4
v6 4
v3
4
v5
最小费用最大流问题
由于输油管道的长短不一,所以每段管道(vi,vj) 除了有不同的流量限制 cij 外,还有不同的单位流量的 费用 bij,cij 的单位为万加仑/小时,bij 的单位为百元/ 万加仑。从采地 v1 向销地 v7 运送石油,怎样运送才 能运送最多的石油并使得总的运送费用最小?求出每 小时的最大流量及最大流量的最小费用。
某大学准备对其所属的 7 个学院办公室进行计算 机联网,这个网络可能联通的途径如图 所示,图中 v1,…,v7 表示 7 个学院办公室,请设计一个网络能联通 7 个学院办公室,并使总的线路长度最短。
最大流问题
某石油公司拥有一个管道网络,使用这个网络可 以把石油从采地运送到一些销售点。由于管道直径的 变化,它的各段管道(vi,vj)的流量 cij(容量)也是 不一样的。cij 的单位为万加仑/小时。如果使用这个网 络系统从采地 v1 向销地 v7 运送石油,问每小时能运 送多少加仑石油?
图与网络实验
1、最短路问题 2、最小树问题 3、最大流问题 4、最小费用最大流问题 5、货郎担问题 6、中国邮路问题
最短路问题
电信公司准备在甲、乙两地沿路架设一条光缆 线,问如何架设使其光缆线路最短?下图给出了甲 乙两地间的交通图。权数表示两地间公路的长度 (单位:km)。
最小生成树问题