《运筹学》实验7
一、实验名称：用dijkstra法求解最短路问题。
二、实验目的：
进一步理解最短路的算法，掌握用matlab软件求解最短路问题的程序。
三、实验内容。
编写最短路的dijkstra算法的程序。
四、实验步骤。
1、编写用dijkstra算法计算从起点到其余顶点的最短路的程序。
dijkstra算法步骤：
第1步：(开始)置l1=0，lj=w1j，j=2,3,…,n，p=，t=
第2步：（指出永久标号）在t中寻找一点k，使得。
置p=p∪,t=t-,若t=φ,则终止；否则转第3步。
第3步： (修改临时标号）对t中每一点j，置。
再转第2步。
2、示例1：求下图中从顶点u1到其余顶点的最短路。
用dijkstra算法计算从起点u0到其余顶点的最短路的程序：
建立网络的邻接矩阵w;
w=[0 2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;..
8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;..
inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0];
n=size(w,1);%测出邻接矩阵w的阶数；
w1=w(1,:)第1步：(开始)置l1=0，lj=w1j;
%赋初值。for i=1:n
l(i)=w1(i);%顶点1到顶点i的最短距离为l(i);
z(i)=1;%z(i)表示到顶点i的最短路上的前一个顶点；
ends=建立一个存放永久标号的数组s;
s(1)=1;%第一个顶点给予永久标号；
u=s(1);
k=1;l,%输出第一次标号的结果；
zwhile k % 更新 l(v) 和 z(v)
for i=1:n
for j=1:k
if i~=s(j)
if l(i)>l(u)+w(u,i)
l(i)=l(u)+w(u,i);
z(i)=u;
endend
endendl;z;
%求v*ll=l;
for i=1:n
for j=1:k
if i~=s(j)
ll(i)=ll(i);%若顶点i不是永久标号的，则ll(i)保持不变。
else ll(i)=inf;%若顶点i是永久标号的，则ll(i)等于无穷大。
endend
endlv=inf;
for i=1:n
if ll(i) lv=ll(i);%找出临时标号中距离最小的点，顶点号放到v中，最短距离放在lv中。
v=i;end
end s(k+1)=v;%顶点v给予永久标号。
k=k+1;
u=s(k);endl
z五、实验题目。
1、 求下图中从v1到其余各点的最短距离。
2、 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用。
现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少。
已知该种设备在每年年初的**为：
第一年第二年第三年第四年第五年。
使用不同时间设备所需维修费为：
使用年限 0－1 1－2 2－3 3－4 4－5
维修费 5 6 8 11 18
运筹学 第6次实验
运筹学 实验6 一 实验名称 用动态规划方法求解最短路问题。二 实验目的 进一步理解动态规划基本思想和基本求解方法，能借助软件求解一些具体问题。三 实验内容。1 建立最短路问题的动态递推方程。2 用lingo编写求解递推方程的程序。3 求解一个具体最短路问题。四 实验步骤。1 辅助函数。if log...
运筹学 第2次
第2次作业。一 单项选择题 本大题共40分，共 20 小题，每小题 2 分 1.运筹学要求模型的变量 参数与方程式 可以控制。a.可以组合。b.可以计算。c.可以测量。d.可以识别。2.原问题约束条件连接符号为 对偶问题的变量约束为 a.b.c.d.无约束限制。3.法的极点不是 a.可行解。b.基本...
运筹学第7章答案
7.2 1 分别用节点法和箭线法绘制表7 16的项目网络图，并填写表中的紧前工序。2 用箭线法绘制表7 17的项目网络图，并填写表中的紧后工序。表7 16表7 17 解 1 节点图 箭线图 2 节点图 箭线图 7.3根据项目工序明细表7 18 1 画出网络图。2 计算工序的最早开始 最迟开始时间和总...