欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

有向图最短路问题的规划数学模型

程序员文章站 2022-04-06 20:21:10
...

有向图最短路问题的规划数学模型
约束条件的目的是:求得所有可能的从顶点1到顶点n的路径
其原理如下:
s.t.1
i=1时式子值为1:与点1相连的路径一定有一条为1,即点1一定可以走出去
i=n时式子值为-1:与点n相连的路径一定有一条为-1,即一定有路径通往点n(实际上此条件可省略,由于目标min)
i≠1,n时式子值为0,:路径可以通过约束1中创造的路径延续下去,直至点n

下面为一道最短路径的题目,将通过将上述数学表达式转化为lingo代码求解

有向图最短路问题的规划数学模型

model:
sets:
cities/A,B1,B2,C1,C2,C3,D/;!城市名称;
roads(cities,cities)/A,B1 A,B2 B1,C1 B1,C2 B1,C2
B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/:w,x;!w:两城市路径的权值,x:最短路径;
endsets

data:
    w = 2  4  3  3  1  2  3  1  1  3  4;
enddata

aaa@qq.com(cities);

min = @sum(roads(i,j):w(i,j)*x(i,j));!求道路的最小权值;
@for(roads(i,j):@bin(x(i,j)));!x的01约束,x(i,j)=1说明弧位于顶点1至顶点n的路上;

@sum(roads(i,j)|i#eq#1 : x(i,j))=1;!约束1:最短路中中间点的约束;
@for(cities(i)|i#ne#1 #and# i#ne#n:@sum(roads(i,j): x(i,j))aaa@qq.com(roads(j,i):x(j,i)));!约束3:起点的约束;

end

在上述程序中, aaa@qq.com(cities)是计
算集cities的个数,这里的计算结果是n=7, 这样编
写方法目的在于提高程序的通用性.
有向图最短路问题的规划数学模型

运行结果,知道最短路径为6;
通过x(A,B1),x(B1,C1),x(C1,D)知道最短路径A——B1———C1———D

相关标签: 最短路径算法