运筹学上机报告最短路问题的计算机求解

运筹学上机实验报告单

20 14 －20 15 学年第 2 学期

实验名称最短路问题的计算机求解班级实验目的姓名

日期：2015

年 5 学号

月

26 日

掌握最短路问题的计算机求解方法。

实验内容

（1）最短路问题的 lingo 编程与计算机求解步骤。（2）最短路问题计算机求解的输出结果分析。

操作步骤

（1）进入运筹学软件。（2）利用相应例题（P143 例 5-1）熟悉网络最短路问题的计算机求解步骤。（3）对求解中出现问题所进行内容在同学间相互交流，并进行总结。（4）完成上机作业（P162 习题 3），并记录步骤与结果。习题3结果：

Variable U( 1) U( 2) U( 3) U( 4) U( 5) U( 6) U( 7) W( 1, 2) W( 1, 3) W( 1, 4) W( 1, 5) W( 2, 6) W( 3, 2) W( 3, 7) W( 4, 5) W( 4, 7) Value 0.000000 -5.000000 -2.000000 3.0000 2.000000 -11.00000 -7.000000 4.000000 -2.000000 3.000000 5.000000 1.000000 7.000000 -5.000000 -1.000000 4.000000

结果显示与分析

W( 5, 7) W( 7, 2) W( 7, 6) P( 1, 2) P( 1, 3) P( 1, 4) P( 1, 5) P( 2, 6) P( 3, 2) P( 3, 7) P( 4, 5) P( 4, 7) P( 5, 7) P( 7, 2) P( 7, 6) Row 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

-3.000000 2.000000 -4.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 1.000000 1.000000 Slack or Surplus 0.000000 0.000000 0.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000但在整体从v1到

用计算机求解得出了v1到各点的最短路结果，有负权值得最短路问题的求解过程与无负权值得一致但在整体从v1到 v7的最短路无法用狄克斯拉算法求解， W （x,y）表示x到y的距离，底下的row 代表剩余变量，结果显示只有v1到各点的最短距离

实验总结

用 LINGO 求解最短路问题简单，方便，明了。在有负权的问题中，应对路线的范围着重说明，本题中 u 的范围为 free.