实验一最短路径求解|最短路径求解

实验一：最短路径求解

实验目的：利用Excel 线性规划求解最短路径。

实验环境：Microsoft Excel2003，Windows XP。

实验注意事项：

实验内容：使用线性规划工具求解图1.1网络拓扑图中s 点到t 点间的最短路径。

图1.1 网络拓扑图

实验步骤：

1. 添加“规划求解”项，可通过“工具” “加载宏”加入该项功能。

2. 将网络拓扑图转化成关联矩阵

A 矩阵表示各节点与各边的连接关系，若边e i 与节点v i 无关联则在此单元为0；若边e i 表示从节点v i 流出为1，若边e i 表示从节点v i 流入为-1。

列出各弧长向量W ：

A 矩阵与向量W 可完整描述出网络拓扑结构。

3. 根据Bellman 方程和约束条件进行求解

约束条件：若形成两点之间的最短路径，则起点s 必有一出路径，终点t 必有一入路径，其他中间节点必然有一进一出的路径。

Bellman 方程中Xi 向量为求解目标，Xi 代表此边是否在最短路径上，如在最短路径上取值为1，若不在取值为0。

4. 使用Excel 线性规划求解，选择主菜单的“工具” “规划求解”即可进入“规划求解

参数”定义窗口；

其中目标单元格为Wi ×Xi ，可变单元格为Xi ，约束条件为Xi ≤1，且为整数；

AXi 表示向量值为Bellman 方程中所示（这里为方便求解，特将s 点的AXs 值-1，将t 点的AXt 值+1，这样约束向量AXi=『0，0，0，0』）。

点击“求解”可得规划目标。