71117408 梅洛瑜
Lingo 解决动态规划
给定一个网络,从点铺设一条煤气管道到点,必须经过五个中间站,第一站可以在中选择,
其余类似。能用管道相连的两站之间的距离已经给定;如果两点之间没有连线,则表示这两
点之间不能铺设管道。要求选择一条由到的管道铺设路线,使总距离最短。
令
n
表示由某点至终点
A
6
之间的阶段数。例如从
A
0
至
A
6
是 6 个阶段,从
A
1
至
A
6
是 5 个阶段。
令
s
表示在任一阶段所处的状态,
s
称为状态变量。例如若在第三阶段的开始点是
A
2
则称所处的状态为
A
2
。
令
x
n
(s)
为决策变量,它表示当状态处于 s,还有 n 个阶段时所选择的一个决策。在
各个阶段上选择的决策组成的总体称为一个策略。
令
f
n
(s)
表示现在处在状态 s(即在点 s 上)还有 n 个阶段时,由 s 至终点
A
6
的最短距
离。
令 d
(s,x
n
)
表示点 s 到点
x
n
的距离。
则可构造 n 阶段的最优值与 n-1 阶段的最优值之间的递推关系如下:
1.模型输入
使用 LINGO 求解此动态规划问题,LINGO 程序如下:
评论0