试议求解巧用Excel规划求解最短路径

● Excel规划求解的功能概述
Excel具有规划求解的基本功能，包括线性规划和非线性规划。对于常规的线性规划问题，Excel就可以给出求解结果。借助规划求解，可求得工作表上某个单元格中公式的最优值。规划求解将对直接或间接与目标单元格中公式相关联的一组单元格中的数值进行调整，最终在目标单元格公式中求得期望的结果。
● 加载规划求解功能
在Excel2003版本中，通过点击菜单“工具→宏→加载宏”，加载规划求解加载项，便可加载该宏。在Excel2007版本中，通过点击Office按钮，点击“Excel选项→加载项→转到Excel加载项”，然后加载规划求解加载项，便可以加载规划求解的宏。在Excel2010版本中，通过点击“文件”选项卡打开“Excel选项”对摘自：本科毕业论文答辩www.618jyw.com
话框，单击左侧“加载项”标签，在右侧单击“转到”按钮，打开“加载宏”对话框，勾选“规划求解加载项”复选框，单击“确定”按钮，即可在工具栏的“数据”选项卡中出现“分析”选项组，菜单上面就有了“规划求解”按钮。
● 案例
王老师从学校A到学校I参加会议，途中需要经过一些学校，学校之间的距离和线路已在图1中标明，请帮王老师规划一下，在不影响去学校I最短距离的情况下，顺便探访其他学校，请将路线描述出来。

1.Dijkstra算法描述及C语言函数实现

为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。即如果存在一条从i到j的最短路径（Vi...Vk，Vj），Vk是Vj前面的一个顶点，那么（Vi...Vk）也必定是从i到k的最短路径。例如，对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么通过已知可得从V0到Vj顶点的最短距离dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根据这种思路，假设存在G=，源顶点为V0，U={V0}，dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。那么可从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；更新与i直接相邻顶点的dist值（dist[j]=min{dist[j]，dist[i]+matrix[i][j]}）；直到U=V，停止。
/*Dijkstra算法代码C语言实现：*/
void DijkstraPath（MGraph g，int *dist，int *path，int v0） //v0表示源顶点
{
int i，j，k；
bool *visited=（bool *）malloc（sizeof（bool）*g.n）；
for（i=0；i{
if（g.matrix[v0][i]>0&&i！=v0）
{
dist[i]=g.matrix[v0][i]；
path[i]=v0； //path记录最短路径上从v0到i的前一个顶点
}
else
{
dist[i]=INT_MAX； //若i不与v0直接相邻，则权值置为无穷大
path[i]=-1；
}
visited[i]=false；
path[v0]=v0；
dist[v0]=0；
}
visited[v0]=true；
for（i=1；i{
int min=INT_MAX；
int u；
for（j=0；j{
if（visited[j]==false&&dist[j]{
min=dist[j]；
u=j；
}
}
visited[u]=true；
for（k=0；k{
if（visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]{
dist[k]=min+g.matrix[u][k]；
path[k]=u；
}
}
}
}

2.Excel“规划求解”功能实现最短路径

（1）可将学校A到学校I的距离与逻辑关系通过以下表表示。
（2）新建工作簿，将上表各节点的逻辑关系用下Excel工作表表示（如图2）。
“节点关系”这一栏仅用于描述各节点之间的关系，仅以B点来说（+代表此点出发，-代表以此点进），进入方向为A，出发为C、E、F。所以B=-AB+BC+BE+BF，以此类推。真正反映数量关系的是F栏的“数量（逻辑关系）”，同样以B节点为例，F19中公式关系是=-D18+D21+D22+D23，通过D栏各线段是否在最短路径（o表示“不在”，1表示“在”）上，迭代产生。最短路径设置在G31，使用公式“=SUMPRODUCT（C18：C31，D18：D31）”，通过对D栏、F栏进行规划求解来设置相应的约束条件以生成最短距离。

3.规划求解

点击“数据→规划求解”，目标单元格G31为最短路径，通过函数SUMPRODUCT（C18：C31，D18：D31）进行求和。因为选取的是最短路径，所以在“最小值”选项打标记。从下页图3可看出规划求解通过调整所指定的可更改的单元格（可变单元格）D18：D31中的值，可以从目标单元格公式中求得所需的结果。约束条件是在D18：D31中只能是0、1的两种，结束条件是节点条件的取值与目标值对应。
由于规划求解过程是一个迭代过程，有的值可能达到1E-9左右，约为0，将“是否为最短路径”和“数量（逻辑关系）”设置成数值格式，并取消“小数位”。
从上例创建模型的过程中，我们看到可以对规划求解模型中的可变单元格数值应用约束条件（约束条件：“规划求解”中设置的限制条件），约束条件可以引用其他影响目标单元格公式的单元格的值。
Excel不仅是一个小型的数据库软件，更是一个操作极为方便的工作数据表，几乎能胜任数据处理的各种要求，功能强大、使用灵活。让我们共同使用好Excel，提高工作效率。
资讯
便携办公利器——华硕PU500商务笔记本
全能轻薄的商务本
华硕PU500作为主流15.6英寸商务本，重量为1.96Kg，厚度只有22mm，拥有深色发丝拉纹设计。屏幕采用防眩光雾面屏。电源适配器体积比传统适配器小20%，加入电源插接报警，当适配器插头未完全插入时系统会自动弹出窗口报警，保护电脑安全。
动力强劲的商务本
华硕PU500采用i5-3317U处理器，配备4GB DDR3 1600MHz内存，Intel? HD Graphics 4000显示芯片。PU500采用“SSD+HDD”的混合硬盘模式（选配），既保持了SSD快速读取的优势，又具有传统机械硬盘的超高性价比。
接口配备齐全包括两个USB2.0接口、一个支持关机充电的USB

3.0接口，同时还配备投影展示常用的VGA视频输出接口，HDMI等接口。

最为安全的商务本
华硕PU500以金属支架强化硬盘周围的结构保护硬盘安全，周围辅以减震海绵垫防止笔记本电脑在运送过程中如果发生冲击或掉落，可确保数据的安全。
同时，该机型还设置了专属ASUS HDD Protection，可利用内建的重力传感器（G-sensor），侦测出加速度的变化，当加速度达到一定程度时，触发硬盘保护机制将硬盘读写磁头与硬盘盘片分离，从而保护硬盘。
ASUS HDD Protection允许用户自定义硬盘保护敏感级别，更加方便外出携带随时调整机器安全防护等级。