F(n)=0; @for(cities(i) | i #lt# n: F(i)=@min(roads(i,j): D(i,j)+F(j)); ); !显然，如果P(i,j)=1,则点i到点n的最 短路径的第一步是i --> j，否则就不是。 由此，我们就可方便的确定出最短 路径; @for(roads(i,j): P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0) ); end
• • • • •
x12+x23+x24+x25+x26=2 x13+x23+x34+x35+x36=2 x14+x24+x34+x35+x36=2 x15+x25+x35+x45+x56=2 x16+x26+x36+x46+x56=2
• 因为每个城市只去一次，所以其中任何一 个城市的必有且仅有一条进入路线和一条 出去的路线。 • 求解：为了方便解题，给上面六个城市进 行编号，如下表（因为北京是起点， 将其 标为1）
• 设变量xij。如果xij=1,则表示城市i与城市j直 接相连（即先后紧接到达关系），否则若 xij=0，则表示城市i与城市j不相连。 • 特别说明：xij和xji是同一变量，都表示城市 i与城市j是否有相连的关系。这里取其中xij (I<j)的变量。
• 题目:从北京乘 飞机到东京、 纽约、墨西哥 城、伦敦、巴 黎五个城市做 旅游，每个城 市去且仅去一 次，再回到北 京，问如何安 排旅游线路， 使总旅程最短。 各城市之间的 航线距离如下 表：
伦敦 墨西 纽约 巴黎 北京 东京 哥 伦敦 墨西 56 哥 纽约 35 21 56 35 21 21 57 51 78 60 70
36
68
68
巴黎 21
北京 51 东京 60
Байду номын сангаас
57
78 70
36
68 68 51 61
51
61
13
13
• 由于每个城市去且仅去一次，最终肯定是 形成一个圈的结构，这就导致了这六个城 市其中有的两个城市是直接相连的，另外 也有两个城市是不连接的。这就可以考虑 设0-1变量，如果两个城市紧接着去旅游的 则为1，否则为0。
• 目标函数：min z=51*x12+78*x13+68*x14+51*x15+13*x1 6+56*x23+35*x24+21*x25+60*x26+21*x3 4+57*x35+70*x36+36*x45+68*x46+61*x5 6
• 变量xij为0-1变量 @bin(xij) • 最短旅程路线中，每一个城市都要和其他 两个城市相连接，即有一个进入路线和一 个出去路线，所以含第i个城市的所有变量 xij和xji之和为2。所以又有如下的约束 • 城市1(北京)有且仅有一个进入路线和一个 出去路线,所以和它连接的路线条数为2 • x12+x13+x14+x15+x16=2
roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10 /: D, P; endsets
• data: • D= • 6 5 • 3 6 9 • 7 5 11 • 9 1 • 8 7 5 • 4 10 • 5 • 7 • 9; • enddata
• 定义f(i)是由Pi点出发至终点PN的最短路程， 由最优化原理可得
{cij f ( j )}, i 1, 2, , N 1 f (i) min j f (N ) 0
• • • • • • •
•
!最短路问题; model: data: n=10; enddata sets: cities/1..n/: F; !10 个城市;
最短路问题
• 给定N个点Pi，i=1,2，…,n,组成集合{Pi},集 合中任一点Pi到另一点Pj的距离用Cij表示， 如果Pi到Pj没有弧联结，则规定Cij=+∞，又 规定Cii=0(1≤i≤N)，指定一个终点PN，要 求从Pi点出发到PN的最短路线。
• 动态规划:用所在的点Pi表示状态，决策集 合就是除Pi以外的点，选定一个点Pj以后， 得到效益Cij并转入新状态Pj，当状态是PN 时，过程停止。显然这是一个不定期多阶 段决策过程。