min
(V i ,V j ) E n
w
ij
xij
n
(P1)
1, i 1 s .t . xij x ji 1, i n j 1 j 1 0, i 1, n (V i ,V j ) E (V j ,V i ) E xij 0, (Vi ,V j ) E
年份 年初价格
使用年限
2 11
0-1
3 12
1-2 3 2-3 5
4 12
3-4 8
5 13
4-5 12 5-6 18
年维修费用 2
注：第一年使用净值为8的老设备(相当于第一年购买费为8)，
w12 8 3 11
w13 8 3 5 16
w35 12 2 3 17
其中 E 为有向图的所有弧的集合, wij 为弧(Vi,Vj)的权.
例题 1-1 在下图中,用点表示城市,现有 A， B1， B2， C1，C2，C3，D 共 7 个城市，点与点之间的连线表示 城市间有道路相连，连线旁的数字表示道路的长度。 现计划从城市 A 到称市 D 铺设一条天然气管道， 请设 计出最小价格管道铺设方案。
min
ij ij (Vi ,V j )E n n
w x
1, i 1 s.t. xij x ji 1, i n j 1 j 1 0, i 1, n (Vi ,V j )E (V j ,Vi )E xij 0, (Vi ,V j ) E
0.000000 1.000000 1.000000
由最终的输出结果知最优方案为：v1-v3-v6， 最短路长为38,即第一年使用已有1年役龄的旧 设备,一直使用到第3年初购买新设备,然后一直 使用到第5年底.5年内设备的维修费用和设备的 购买费用最少为38.
年份 年初价格
2 11
3 120-1
1-2 3
2-3 5
3-4 8
4-5 12
5-6 18
年维修费用 2
第一年开始使用的有一年役龄的老设备其净值为8, 令：v 1：表示第一年开始使用的有一年役龄的老设备其净值为8; Vi : 第i年初购买一台新设备； (Vi,Vj)表示第I年初购买一新设备一直使用到第j-1年底。 W ij表示第I年初的购买费及使用到第j-1年底的维修费之和； 问题转化为从v1到v6(第5年底)的最短路。 注：第一年使用净值为8的老设备(相当于第一年购买费为8)，
Global optimal solution found. Objective value: Total solver iterations: Variable Value N 6.000000 X( V1, V2) X( V1, V3) X( V3, V6)
38.00000 0 Reduced Cost 0.000000 0.000000 0.000000 0.000000
sets: nodes/v1, v2, v3, v4, v5, v6/; lines(nodes, nodes)/ v1,v2 v1,v3 v1,v4 v1,v5 v1,v6 v2,v3 v2,v4 v2,v5 v2,v6 v3,v4 v3,v5 v3,v6 v4,v5 v4,v6 v5,v6/:w, x; endsets min wij xij data: (Vi ,V j )E w = 11 16 24 26 54 13 16 21 29 14 17 22 14 17 15; 1, i 1 n n enddata s.t. xij x ji 1, i n n=@size(nodes); j 1 j 1 0, i 1, n (Vi ,V j )E (V j ,Vi )E min=@sum(lines: w*x); xij 0, (Vi ,V j ) E @for(nodes(i) | i #ne# 1 #and# i #ne# n: @sum(lines(i,j): x(i,j)) = @sum(lines(j,i): x(j,i))); @sum(lines(i,j)|i #eq# 1 : x(i,j))=1; @sum(lines(i,j)|j #eq# 6 : x(i,j))=1;
(2)最小生成树问题 设无向图是连通的，且互不包有圈，则称该图为树。如果 有向图中任何一点都可由某一个顶点 V1 到达，则称 V1 为图 G 的根。如果有向图 G 有根。且关于它的基础图是树，则称 G 为有向树。 若 G 是包含 G 的全部顶点的子图，它又是树，则称 G 的生 成树。 若图 G(V , E ) 是一个连通赋权图， T 是 G 的一颗生成树， T 的每条边所赋权的和称为树 T 的权，称具有最小权的生成 树为 G 的最小生成树。 v2
model: sets: city /1..7/:u; link(city,city):dist,x; n n endsets min z cij xij n=@size(city); i 1 j 1 data: n dist=0 3 4 7 100 100 100 xij 1, j 2,3,..., n, i j 3 0 3 2 4 100 100 i 1 4 3 0 100 5 7 100 n 7 2 100 0 2 100 6 s.t. x1 j 1, 100 4 5 2 0 1 4 j 2 100 100 7 100 1 0 2 u1 0,1 ui n 1, i 2,3,..., n. 100 100 100 6 4 2 0; enddata u j uk xkj (n 2)(1 xkj ) (n 3) x jk , k 1,..., n, j 2,..., n, j k 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)*(1x(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););
min z cij xij
i 1 j 1 n n
n xij 1, j 2,3,..., n, i j i 1 n s.t. x1 j 1, j 2 u1 0,1 ui n 1, i 2,3,..., n. u j uk xkj (n 2)(1 xkj ) (n 3) x jk , k 1,..., n, j 2,..., n, j k
从上述求解报告得到最优架设线路 为1-2-3，2-4-5-6-7，总长度为13。
例题
某公司有一台已使用一年的设备,每年年底,公司
就要考虑下一年度是购买新设备还是继续使用这台旧设 备.若购买新设备,就要支出一笔购置费;若继续使用旧设 备,则要支付维修费,而且随着使用年限的延长而增加.已 知这种设备每年年初的购置价格,见下表 1,而第一年开 始使用的有一年役龄的老设备其净值为 8,不同使用年限 的维修费用见下表 2,试制定一个 5 年内设备的使用或更 新计划,使 5 年内设备的使用维修费和设备购置费的总支 出最小(化为最短路问题或建立优化模型求解)
sets: cities/A, B1, B2, C1, C2, C3, D/; roads(cities, cities)/ A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 m i n w ij xij C1,D C2,D C3,D/: w, x; (V i ,V j ) E endsets data: 1, i 1 n n w = 2 4 3 3 1 2 3 1 1 3 4; s .t . xij x ji 1, i n enddata j 1 j 1 0, i 1, n (V i ,V j ) E (V j ,V i ) E n=@size(cities); xij 0, (Vi ,V j ) E 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;
实验１、用Lingo求解最短路、 最小树问题
(1)最短路问题 假设有向图有 n 个顶点。现需要求从顶 点 V1 到顶点 Vn 的最短路。设决策变量为 xij ，当 xij 1 ，说明弧 (Vi,Vj)位于顶点 V1 到顶点 Vn 的最短路上;否则 xij 0 ， 则求 V1 到 Vn 的最短路的数学模型为：



Variable
Value N U( 2) U( 3) U( 4) U( 5) U( 6) U( 7) X( 1, 2) X( 2, 3) X( 2, 4) X( 4, 5) X( 5, 6) X( 6, 7)
Reduced Cost 7.000000 0.000000 1.000000 0.000000 2.000000 0.000000 2.000000 0.000000 3.000000 0.000000 4.000000 0.000000 5.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 3.000000 3.000000 2.000000 2.000000 1.000000 2.000000