Page 191 - 数学建模算法与应用

第七章 动态规划研究

例 用 lingo 求解例 1 最短路线问题。
model：
Title Dynamic Programming；
sets：

vertex/A，B1，B2，C1，C2，C3，C4，D1，D2，D3，E1，E2，E3，F1，
F2，G/：L；
road(vertex，vertex)/A B1，A B2，B1 C1，B1 C2，B1 c3，B2 C2，B2 C3，B2 C4，
C1 D1，C1 D2，C2 D1，C2 D2，C3 D2，C3 D3，C4 D2，C4 D3，

D1 E1，D1 E2，D2 E2，D2 E3，D3 E2，D3 E3，
E1 F1，E1 F2，E2 F1，E2 F2，E3 F1，E3 F2，F1 G，F2 G/：D；
endsets
data：

D=5 3 1 3 6 8 7 6
6 8 3 5 3 3 8 4
2 2 1 2 3 3
3 5 5 2 6 6 4 3；

L=0，，，，，，，，，，，，，，，；
enddata
@for(vertex(i)|i#GT#1：L(i)=@min(road(j，i)：L(j)+D(j，i)))；
end

一个问题用动态规划方法求解，可首先建立起动态规划的数学模型：
1. 将过程划分成不同的阶段。
2. 正确选择状态变量 xk ，既能描述过程状态，又能满足无后效性，同时确

定状态集合为 xk 。
3. 选择决策变量为 uk ，确定允许决策集合为 uk (xk ) 。
4. 写出状态转移的方程。
5. 确定阶段指标 vk ( xk uk ) 及指标函数 Vkn 的形式。
,

181