实验5 动态规划模型编程解算
1、用Lingo软件求解下列最短路线问题：
下图是一个线路网，连线上的数字表示两点之间的距离（或费用）。

试寻求一条由A到G 距离最短（或费用最省）的路线。

见“Matlab数学建模算法全收录”P59页Lingo程序——最优值为18.
再此基础上，自己编写下列最短路径规划程序：
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
运行结果：
2、用Lingo求解下列最短路径规划程序：
如下图，求从S到T的最短路径。

设d(x,y)为城市x与城市y之间的直线距离；L(x)为城市S到城市x的最优行驶路线的路长。

模型为：
min {L(x)+d(x,y)}
L(S)=0
注释：求得最短路径为20。

代码如下：
Title Dynamic Programming;
sets:
vertex/S,A1,A2,A3,B1,B2,C1,C2,T/:L;
road(vertex,vertex)/S A1,S A2,S A3,A1 B1,A1 B2,A2 B1,A2 B2,A3 B1, A3 B2,B1 C1,B1 C2,B2 C1,B2 C2,
C1 T,C2 T/:D;
endsets
data:
D=6 3 3 6 5 8 6 7
4 6 7 8 9
5 6;
L=0,,,,,,,,;
enddata
@for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i)));
end
运行结果：
3、用Lingo 求解下列动态规划问题（经营策略问题）：建模并编程解算 某商店在未来4个月中需要利用一个仓库存储某种商品。

仓库的最大容量为1000件，每月中旬订购商品，并于下月初到货。

预计今后4个月这种商品的购价k p 和售价k q 如下表所示。

假定商店在1月初开始时仓库已存有该种商品500件，且每月市场需求不限。

问应如何计划每月的订购与销售数量，使得这4个月的总利润最大。

月份k
购价k p 售价k q
1
10
12 2 9 9 3 11 13 4
15 17
需建立整数规划模型（设(1,2,3,4)i x i =为第i 个月的订购数量，(1,2,3,4)i y i =为
第i 个月的销售数量）。

程序如下：
max =12*y1+9*y2+13*y3+17*y4-10*x1-9*x2-11*x3-15*x4; y1<=500; x1-y1<=500; x1-y1>=-500; x1-y1+x2-y2<=500; x1-y1+x2-y2>=-500; x1-y1+x2-y2+x3-y3<=500; x1-y1+x2-y2+x3-y3>=-500; x1-y1+x2-y2+x3-y3+x4-y4<=500; x1-y1+x2-y2+x3-y3+x4-y4>=-500; y2<=1000; y3<=1000; y4<=1000; Z1=500; Z2=500+x1-y1; Z3=500+x1-y1+x2-y2; Z4=500+x1-y1+x2-y2+x3-y3; Z5=500+x1-y1+x2-y2+x3-y3+x4-y4;
运行结果：。