最短路问题的Lingo求解.ppt

最短路问题的Lingo求解 设图共有个节点 其赋权图的邻接矩阵为 表示节点到的权值为 当为有向图时 当为无向图时 和分别由图得到 通常不一样 当 表示节点与节点不连通 令 假设图的所有权值现求节点到节点的最短路 其线性规划模型为 模型一 决策变量 设 目标函数为寻找一条节点到节点的通路 使其上权值和最小 故目标函数为 1 对节点恰有一条路出去 却不能有路回来 故有 且 2 对节点恰有一条路到达 却不能有路出去 故有 3 对除起始点和目标点之外 其它点进入和出去的路是一样多 可都为0 则 且 4 对不通的路不取 约束为 总的线性规划模型为 图1无向图最短路示意图 示例演示 例1现有11个点的无向图见图14 1 求点1到点11的最短路 其Lingo实现程序为 model sets point 1 11 u road point point W X endsetsdata W 0 2 8 1 0 0 0 0 0 0 0 2 0 6 0 1 0 0 0 0 0 0 8 6 0 7 5 1 2 0 0 0 0 1 0 7 0 0 0 9 0 0 0 0 0 1 5 0 0 3 0 2 9 0 0 0 0 1 0 3 0 4 0 6 0 0 0 0 2 9 0 4 0 0 3 1 0 0 0 0 0 2 0 0 0 7 0 9 0 0 0 0 9 6 3 7 0 1 2 0 0 0 0 0 0 1 0 1 0 4 0 0 0 0 0 0 0 9 2 4 0 enddata min sum road i j w i j x i j 最短路 for point i i ne 1 and i ne 11 sum point k x k i sum point j x i j sum point j j ne 1 x 1 j 1 起始点要出去 sum point k k ne 1 x k 1 0 不能回到起始点 sum point k k ne 11 x k 11 1 要到达目标点 sum point j j ne 11 x 11 j 0 目标点不能出去 for road i j x i j W i j 不能到达的路不考虑 for road i j bin x i j end结果为minZ 13x 1 2 1x 2 5 1 x 5 6 1x 6 3 1x 3 7 1x 7 10 1x 10 9 1x 9 11 1故路径为1 2 5 6 3 7 10 9 11 模型二 不必考虑起始点不回去 结束点不出去 统一考虑所有中间点不出现圈 添加约束为 总模型为 其Lingo实现程序为 model sets point 1 11 road point point W X endsetsdata W 0 2 8 1 0 0 0 0 0 0 0 2 0 6 0 1 0 0 0 0 0 0 8 6 0 7 5 1 2 0 0 0 0 1 0 7 0 0 0 9 0 0 0 0 0 1 5 0 0 3 0 2 9 0 0 0 0 1 0 3 0 4 0 6 0 0 0 0 2 9 0 4 0 0 3 1 0 0 0 0 0 2 0 0 0 7 0 9 0 0 0 0 9 6 3 7 0 1 2 0 0 0 0 0 0 1 0 1 0 4 0 0 0 0 0 0 0 9 2 4 0 enddata min sum road i j w i j x i j 最短路 n size point for point i i ne 1 and i ne 11 sum point k x k i sum point j x i j sum point j j ne 1 x 1 j 1 起始点要出去 sum point k k ne 11 x k 11 1 要到达目标点 for road i j u i