最短路问题（二）

四、最短路径的线性规划方法

【问题分析】

在图G=(V,E)中，求起点vs到终点vt的一条最短路。设vs到vt的最短路径所在链为L，对E中每条边(u,v)来说，它要么在L上，要么不在L上，因此可以设置变量：

1. 如图3所示，起点为vs，与之相连的边有k条，有且仅有一条边在L上；
2. 如图4所示，终点为vt，与之相连的边有k条，有且仅有一条边在L上；
3. 如图5所示，若点u不在L上，则边(vi,u)都不在L上，（u,vj)也不在L上；
4. 如图5所示，若u在L上，以u为终点的k条边只有一条边在L上；以u为起点的m条边也只有一条边在L上。

【符号设置】

• G=(V,E,D)：给定网络图,V为顶点集，E为边集, D为距离的权矩阵；
• Vs：最短路径起点；
• Vt：最短路径的终点；
• （u,v)：E中的边；
• d(u,v)；边(u,v)的权（距离）；
• L：连接vs和vt的最短路径；
• 

【建立模型】

1. 如图3所示，针对起点vs，有
2. 如图4所示，针对终点vt，有
3. 如图5所示，针对中间点u，有
4. 目标：L链的权（距离）和
5. 其它约束：

【数学模型】

案例3

求如图1所示的v1到v8的最短距离。

（步骤如上）

编写Lingo模型，计算得到最优解为：

x(v1,v2)=1;

x(v2,v5)=1;

x(v5,v7)=1;

x(v7,v8)=1.

sets:
dian/v1 v2 v3 v4 v5 v6 v7 v8/:;
bian(dian,dian)/v1,v2 v1,v3 v2,v4 v2,v5 v3,v4 v3,v5
 v4,v6 v4,v7 v5,v6 v5,v7 v6,v7 v6,v8 v7,v8/:x,d;
endsets
data:
d=4 6 5 4 4 7 9 7 5 6 5 4 1;
enddata
min=@sum(bian:d*x);
@for(bian:@bin(x));
@sum(bian(i,j)|i#eq#1:x(i,j))=1;
@sum(bian(i,j)|j#eq#8:x(i,j))=1;
@for(dian(k)|k#ne#1#and#k#ne#8:
@sum(bian(k,j):x(k,j))=@sum(bian(i,k):x(i,k)));

v1到v8最短路径为v1-v2-v5-v7-v8,距离为15.

案例4：设备更新问题

张先生打算购买一辆新轿车，轿车的售价12万人民币，轿车购买后，每年的各种保险、养护费等如表1.如果5年内，张先生将轿车售出，并购买新车，5年内的二手车销售价格如表2。请帮助张先生设计一种购买轿车方案，使5年内用车的总费用最少。

表1  轿车的维护费用

表2  二手车的售价

【模型假设】

1. 张先生任何一年年初都可以卖掉旧车买新车；
   
2. 只是计算当前5年内的费用。

【符号设置】

1. Cij表示第i年年初到第j-1年结束(第j年年初)的购车总消费
2. Cij=在第i年开始到第j-1年的结束的轿车维护费用 +第i年开始购买新车的购买费-在第j-1年年末卖出二手车的销售收入
3. xij   表示第i年年初购买新车，第j年年初（j-1年年末）换车，

其中，i=1,2,3,4,j=2,3,4,5,6.

【问题分析】

(凡是设备更新问题，均可以化为最短路径问题)

由于跨越5年，用6个点表示每个年的起始。用任意两点的连线表示从起点到终点所包含的年的花费，这样就构成了汽车消费费用网络图，如图5所示。

权系数的计算

C12=12+2-7=7,

C13=12+2+4-6=12,

C14=12+2+4+5-2=21,

C15=12+2+4+5+9-1=31,

同理，有

C16=12+2+4+5+9+12-0=44,

C23=7,C24=12,C25=21,C26=31,

C34=7,C35=12,C36=2

C45=7,C46=12,

C56=7,

将所计算数据反映在网络图如下

【数学模型】

【计算结果】

X(1,3)=1         x(3,4)=1         x(4,6)=1

即先用两年，再换车用一年，再换车用两年。最小费用为31万。

sets:
dian/1..6/:;
link(dian,dian)/1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 2,6 3,4 3,5 3,6 4,5 4,6 5,6/:c,x;
endsets
data:
c=7 12 21 31 44 7 12 21 31 7 12 21 7 12 7;
enddata
min=@sum(link:c*x);n=@size(dian);
@sum(link(i,j)|i#eq#1:x(i,j))=1;
@sum(link(i,j)|j#eq#n:x(i,j))=1;
@for(dian(i)|i#ne#1#and#i#ne#n:@sum(link(i,j):x(i,j))=@sum(link(j,i):x(j,i)));
@for(link(i,j):@bin(x(i,j)));