《运筹学》实验6
一、实验名称：用动态规划方法求解最短路问题。
二、实验目的：
进一步理解动态规划基本思想和基本求解方法，能借助软件求解一些具体问题。
三、实验内容。
1、 建立最短路问题的动态递推方程。
2、 用lingo编写求解递推方程的程序。
3、 求解一个具体最短路问题。
四、实验步骤。
1．辅助函数。
if(logical_condition,true_result,false_result)
if函数将评价一个逻辑表达式logical_condition，如果为真，返回true_ result，否则返回false_result。
例求解最优化问题。
其lingo**如下：
model:
min=fx+fy;
fx=@if(x #gt# 0, 100,0)+2*x;
fy=@if(y #gt# 0,60,0)+3*y;
x+y>=30;
end2、示例（最短路问题） 给定n个点组成集合，由集合中任一点到另一点的距离用表示，如果到没有弧联结，则规定，又规定，指定一个终点，要求从点出发到的最短路线。这里我们用动态规划方法来做。用所在的点表示状态，决策集合就是除以外的点，选定一个点以后，得到效益并转入新状态，当状态是时，过程停止。
显然这是一个不定期多阶段决策过程。
定义是由点出发至终点的最短路程，由最优化原理可得。
这是一个函数方程，用lingo可以方便的解决。
最短路问题；
model:
sets:cities/1..10/: f; !10个城市；
roads(cities,cities)/
/: d, p;
endsets
data:d=
enddata
f(10)=0;
@for(cities(i) |i #lt#
f(i)=@min(roads(i,j): d(i,j)+f(j)))
!显然，如果p(i,j)=1,则点i到点10的最短路径的第一步是i --j，否则就不是。
由此，我们就可方便的确定出最短路径；
@for(roads(i,j):
p(i,j)=@if(f(i) #eq# d(i,j)+f(j),1,0));
end计算的部分结果为：
feasible solution found at iteration0
variablevalue
f( 1) 17.00000
f( 2) 11.00000
f( 3) 15.00000
f( 4) 8.000000
f( 5) 13.00000
f( 6) 11.00000
f( 7) 5.000000
f( 8) 7.000000
f( 9) 9.000000
f( 10) 0.000000
p( 1, 2) 1.000000
p( 1, 3) 0.000000
p( 2, 4) 1.000000
p( 2, 5) 0.000000
p( 2, 6) 0.000000
p( 3, 4) 1.000000
p( 3, 5) 0.000000
p( 3, 6) 0.000000
p( 4, 7) 0.000000
p( 4, 8) 1.000000
p( 5, 7) 1.000000
p( 5, 8) 0.000000
p( 5, 9) 0.000000
p( 6, 8) 1.000000
p( 6, 9) 0.000000
p( 7, 10) 1.000000
p( 8, 10) 1.000000
p( 9, 10) 1.000000
五、实验题目。
1、 求下图中从u1到其余各点的最短距离和最短路径。
运筹学 第7次实验
运筹学 实验7 一 实验名称 用dijkstra法求解最短路问题。二 实验目的 进一步理解最短路的算法，掌握用matlab软件求解最短路问题的程序。三 实验内容。编写最短路的dijkstra算法的程序。四 实验步骤。1 编写用dijkstra算法计算从起点到其余顶点的最短路的程序。dijkstra算...
运筹学 第2次
第2次作业。一 单项选择题 本大题共40分，共 20 小题，每小题 2 分 1.运筹学要求模型的变量 参数与方程式 可以控制。a.可以组合。b.可以计算。c.可以测量。d.可以识别。2.原问题约束条件连接符号为 对偶问题的变量约束为 a.b.c.d.无约束限制。3.法的极点不是 a.可行解。b.基本...
运筹学实验
1.9题。解 设表示名司机和乘务人员第k班次开始上班，由题意有，c 1 1 1 1 1 1 a 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 lb 0 0 0 0 0 0 b 60 70 60 50 2...