实验一：最短路径求解
实验目的：利用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』）。
点击“求解”可得规划目标。
实验一：最短路径求解
实验目的：利用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』）。
点击“求解”可得规划目标。