50人，B处40人，C处60人，D处20人，E处70人，F处90人，问小学应建在哪一个村子，使学生上学最方便（走的总路程最短）。
四、实验报告要求
实验报告要求包含下面几个部分： (1) 阐述实验目的； (2) 问题； (3 数学模型 (4 计算程序 (5 计算结果;
(6 分析、检验和结论; (7 心得体会;
10
实验二：Lingo求解最大流、最小费用流问题 一、实验目的
通过本实验熟悉Lingo软件中的集合、运算、编辑等命令,了解最大流和最小费用的数学规划模型；能利用最大流和最小费用流的思想建立实际问题的数学模型，并利用Lingo求解。
二、问题及其Lingo软件求解 (1)最大流问题
假设有一个有向网络图G(V,E)，对于每条弧(Vi,Vj)有一个非负的权cij，称为该弧的
容量。图中有两个点，一个称为发点，记为S，它只有出弧，没有入弧，即只有流出而没有流入；另一个称为收点，记为t，它只有入弧，而没有出弧，即只有流入而没有流出。这样的网络称为运输网络。
对于运输网络，是定义实值函数f，对于每条弧(Vi,Vj)，有一个值f(i,j)与之对应，
f(i,j)表示弧(Vi,Vj)上的流量。假设f(i,j)满足下列条件：
（1）对每条弧，流量不超过容量，即0?f(i,j)?cij。 （2）发点S流出的总量等于收点t流入的总量；
（3）对于除发点和收点之外的任一点，流入该点的总量等于流出该点的流量； 则称该函数为网络图G(V,E)上的一个可行流。令V(f)??i?Vf(s,i)，称V(f)为可行流f
的流量。若存在一个可行流f，使得V(f)最大，则称可行流f为最大流。 最大流的数学模型为：
minv(f)??v(f),i?s?（p3） ???f(i,j)??f(j,i)???v(f),i?t
s.t.?j?Vj?V?0,i?s,t????0?f(i,j)?cij,(vi,vj)?E例题2-1 现需要将城市S的石油通过管道运送到城市t,中间有4个中转站v1,v2,v3和v4, 城市合中转站的连接以及管道的容量如下图所示,求城市s到城市t的最大流.
11
解：现求上述问题的最大流，根据上述数学模型，给出Lingo模型如下：
model: sets:
nodes/s,1,2,3,4,t/; arcs(nodes, nodes)/
s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; endsets data:
c = 8 7 5 9 9 2 5 6 10; enddata max=flow;
@for(nodes(i) | i #ne# 1 #and# i #ne# @size(nodes): @sum(arcs(i,j):f(i,j)) - @sum(arcs(j,i):f(j,i))=0); @sum(arcs(i,j)|i #eq# 1 : f(i,j)) = flow; @for(arcs: @bnd(0, f, c));
运行得到求解报告为：
Global optimal solution found at iteration: 0 Objective value: 14.00000
Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000
故最大流为：
f(s,1)=7, f(s,2)=7, f(1,2)=2, f(1,3)=5, f(2,4)=9, f(3,2)=0,
f(3,t)=5, f(4,3)=0, f(4,t)=9.流量为v（f）=14。最大流网络见下图。
V1
（9，5） V3
（5，5）
t
7） （8， （5，2）（2，0）s （7，7） 8 （6，0） （10，9）
（9，9）
12
上面程序用到了稀疏集的方法。若用邻接矩阵的方法，程序可推广到复杂网络。 Lingo模型为： sets:
nodes/s,1,2,3,4,t/;
arcs(nodes, nodes): p, c, f; endsets data:
p = 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0; c = 0 8 7 0 0 0 0 0 5 9 0 0 0 0 0 0 9 0 0 0 2 0 0 5 0 0 0 6 0 10 0 0 0 0 0 0; enddata max = flow;
@for(nodes(i) | i #ne# 1 #and# i #ne# @size(nodes):
@sum(nodes(j): p(i,j)*f(i,j)) = @sum(nodes(j):p(j,i)*f(j,i)) ); @sum(nodes(i):p(1,i)* f(1,i)) = flow; @for(arcs:@bnd(0, f, c));
注;上面程序中矩阵P为邻接矩阵，当两点无弧时，定义弧的容量为0。 (2)最小费用最大流问题
例题2-2 在上面例题3中，由于输油管道的长短不一，每条输油管道上的单位石油的运输费用也不相同，因此，除考虑输油管道的最大流外，还需考虑输油管道的输送石油的总费用，现求最小费用最大流。 下面给出了带有费用的运输网络，其中第一个数字表示网络容量，第二个数字表示网络的单位费用。
V1 （9，2） V3 2） （8，s （5，6）
t
（5，5）（2，1） 8 （6，4） （10，7）
（7，8） （9，3）
解：假设f(i,j)表示弧(Vi,Vj)上的流量，cij为弧(Vi,Vj)的单位运费，uij为弧(Vi,Vj)的容量，di表示节点Vi的净流量，则最小费用最大流可表示为如下数学规划问题：
13
min（p4）
?c(i,j)?Eijfij??f(i,j)??f(j,i)?di ?j?Vs.t.?j?V??0?f(i,j)?uij,(vi,vj)?E其中
?v(f),i?s?di???v(f),i?t
?0,i?s,t?当取v(f)为最大流时，由规划问题（p4）求到的最大流，就是最小费用最大流。上述问题的Lingo程序为：
sets:
nodes/s,1,2,3,4,t/:d; arcs(nodes, nodes)/
s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; endsets data:
d = 14 0 0 0 0 -14;
c = 2 8 5 2 3 1 6 4 7; u = 8 7 5 9 9 2 5 6 10; enddata
min=@sum(arcs:c*f);
@for(nodes(i) | i #ne# 1 #and# i #ne# @size(nodes): @sum(arcs(i,j):f(i,j)) - @sum(arcs(j,i):f(j,i))=d(i)); @sum(arcs(i,j)|i #eq# 1 : f(i,j))=d(1); @for(arcs:@bnd(0,f,u));
运行得到求解报告：
Global optimal solution found at iteration: 3
Objective value: 205.0000
Variable Value Reduced Cost F( S, 1) 8.000000 -1.000000 F( S, 2) 6.000000 0.000000 F( 1, 2) 1.000000 0.000000 F( 1, 3) 7.000000 0.000000 F( 2, 4) 9.000000 0.000000 F( 3, 2) 2.000000 -2.000000 F( 3, T) 5.000000 -7.000000
14