! Here is our primitive set of seven cities; cities/A, B1, B2, C1, C2, C3, D/;
! The Derived set \ exist between the cities; roads(cities, cities)/
A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/: w, x; endsets data:
! Here are the distances that correspond to above links; w = 2 4 3 3 1 2 3 1 1 3 4; enddata
n=@size(cities); ! The number of cities; min=@sum(roads: w*x);
@for(cities(i) | i #ne# 1 #and# i #ne# n:
@sum(roads(i,j): x(i,j)) = @sum(roads(j,i): x(j,i))); @sum(roads(i,j)|i #eq# 1 : x(i,j))=1;
运行得到非零解为：
X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路为：A-B1-C1-D，最短路长为6
(2)最小生成树问题
设无向图是连通的，且互不包有圈，则称该图为树。如果有向图中任何一点都可由某一个顶点V1到达，则称V1为图G的根。如果有向图G有根。且关于它的基础图是树，则称G为有向树。 若G是包含G的全部顶点的子图，它又是树，则称G的生成树。若图G(V,E)是一个连通赋权图，T是G的一颗生成树，T的每条边所赋权的和称为树T的权，称具有最小权的生成树为G的最小生成树。
例1-2 假设某电力公司在7个村庄之间架设电线，各村庄之间的距离如下图所示，试求出使电线总长度最小的架线方案。
''
5
解：节点1表示树根，点i与j的距离用cij表示，当两个节点之间没有线路相通时，两点之间的距离用很大的数M表示。引入0-1变量xij：xij?1(i?j)表示从i到j的边在架设线路中，xij?0(i?j)表示该边不在线路中，则架线方案可以归结为求上述赋权图的最小生成树。数学模型可表示为[5]：
nnijminz???ci?1j?1xij?n??xij?1,j?2,3,...,n,i?ji?1（p2）?n
??s.t.??x1j?1,?j?2?u1?0,1?ui?n?1,i?2,3,...,n.???uj?uk?xkj?(n?2)(1?xkj)?(n?3)xjk,k?1,...,n,j?2,...,n,j?k其中u是整数约束变量，xij是0-1变量。 Lingo求解程序：
model: sets:
city /1..7/:u;
link(city,city):dist,x; endsets
n=@size(city); data:
dist=0 3 4 7 100 100 100 3 0 3 2 4 100 100 4 3 0 100 5 7 100 7 2 100 0 2 100 6 100 4 5 2 0 1 4 100 100 7 100 1 0 2 100 100 100 6 4 2 0; enddata
min=@sum(link:dist*x); u(1)=0;
@for(link:@bin(x));
@for(city(k)|k #GT# 1:@sum(city(i)|i #ne# k:x(i,k))=1; @for(city(j)|j #gt# 1 # and # j #ne#
k:u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k););); @sum(city(j)|j # GT # 1:x(1,j))>=1;
@for(city(k)|k #gt# 1:u(k)>=1;u(k)<=n-1-(n-2)*x(1,k););
求解报告为(部分)：
Global optimal solution found at iteration: 15 Objective value: 13.00000
6
Variable Value Reduced Cost
N 7.000000 0.000000 U( 2) 1.000000 0.000000 U( 3) 2.000000 0.000000 U( 4) 2.000000 0.000000 U( 5) 3.000000 0.000000 U( 6) 4.000000 0.000000 U( 7) 5.000000 0.000000
X( 1, 2) 1.000000 3.000000 X( 2, 3) 1.000000 3.000000 X( 2, 4) 1.000000 2.000000 X( 4, 5) 1.000000 2.000000 X( 5, 6) 1.000000 1.000000 X( 6, 7) 1.000000 2.000000
从上述求解报告得到最优架设线路为1-2-3，2-4-5-6-7，总长度为13。 另一个不含圈的模型为[8]:
nnijmin??ci?1j?1nxij
s.t.?x1j?1;j?2n?xi?1i?jij?1,j?2,3,...,n
ui?uj?nxij?n?1,i?j,i,j?1,2,...,nxij?{0,1},uj?0,i,j?1,2,...,nmodel: sets:
city /1..7/:u;
link(city,city):dist,x; endsets
n=@size(city); data:
dist=0 3 4 7 100 100 100 3 0 3 2 4 100 100 4 3 0 100 5 7 100 7 2 100 0 2 100 6 100 4 5 2 0 1 4 100 100 7 100 1 0 2 100 100 100 6 4 2 0; enddata
min=@sum(link:dist*x);
@for(city(j)|j #GT# 1:@sum(city(i)|i #ne# j:x(i,j))=1;);
7
@sum(city(j)|j # GT # 1:x(1,j))>=1;
@for(link(i,j)|i #ne# j:u(i)-u(j)+n*x(i,j)<=n-1); @for(link:@bin(x)); end
得到结果和前面相同,但运行时间稍长.比前一个程序较稳定. 例题1.3 旅行商问题，又称为货郎但问题（文[1]p244例题11）。
有一个卖货郎，从某个村庄出发，通过若干个村庄一次且仅一次，最后回到原出发村庄，问应如何选择线路，使他所走的路程最短。
问题一般化。设有n个城市，以1,2,...,n表示，d(i,j)表示第i城到j城的距离，
一个推销员，从城市1出发，到其他每个城市一次且仅一次，最后回到原城市1，问应如何选择线路，使他所走的路程最短。
引入0-1变量xij：xij?1(i?j)表示选择从i城到j城，xij?0(i?j)表示i城到j城线路不在选择中，则旅行商问题数学模型可表示为[8]：
nnijmin??di?1j?1nxij
s.t.?xij?1;i?1,2,..,nj?1n?xi?1ij?1,j?1,2,3,...,n
ui?uj?nxij?n?1,i?j,i,j?2,...,nxij?{0,1},uj?0,i,j?1,2,...,n(注：这个模型中的条件和前面稍有不同)
设1，2，3，4城市之间的距离为 D(i,j) 1 2 1 0 8 2 6 0 3 7 9 4 9 7 model: sets:
city /1..4/:u;
link(city,city):dist,x; endsets
n=@size(city); data:
dist=0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0; enddata
min=@sum(link:dist*x);
3 5 8 0 8 4 6 5 5 0
8
@for(city(j):@sum(city(i)|i #ne# j:x(i,j))=1;); @for(city(i):@sum(city(j)|j # ne # i:x(i,j))=1;);
@for(link(i,j)|i #ne# j# and # i#gt#1 #and # j #gt# 1:u(i)-u(j)+n*x(i,j)<=n-1); @for(link:@bin(x)); end
运行得到：
Global optimal solution found at iteration: 4 Objective value: 23.00000
Variable Value Reduced Cost N 4.000000 0.000000
X( 1, 3) 1.000000 5.000000 X( 2, 1) 1.000000 6.000000 X( 3, 4) 1.000000 5.000000 X( 4, 2) 1.000000 7.000000
即路线为1-3-4-2-1，路长为23.
三、实验任务
问题1-1. 试求下图所示的最短路问题，弧上数字为距离：
2 1 4 1 7 1 2 3 6 4 6 3 5 3 1 5 问题1-2（最短路问题）：某公司使用一种设备，此设备在一定年限内随着时间的推移逐渐损坏。每年购买价格和不同年限的维修使用费如下表所示。假定公司在第一年开始时必须购买一台此设备，请建立此问题的网络图，确定设备更新方案，使维修费和新设备购置费的总数最小。
年份 1 2 3 4 5 价格 20 21 23 24 26
使用年限 0－1 1－2 2－3 3－4 4－5 费用 8 13 19 23 30
问题1-3 下图的最小生成树和最大生成树：
问题1-4：已知有6个村子，相互间道路的距离如下图所示，拟合建一所小学。已知A处有小学生
9