摘要：图论是应用十分广泛的运筹学分支，用网络图来解决资源分配的问题不仅可以简化求解过程而且丰富了求解方法。在深入分析Dijkstra算法的基础上，实现了基于网络图的资源分配问题的求解和图形表示。
关键词：资源分配；网络图；Dijkstra算法；最短路径
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11255-02
1 引言
图论是运筹学中有着广泛应用的一个分支，借助于图与网络模型及其分析技术可以成功解决很多管理问题。用网络图来解决资源分配的问题不仅可以简化求解过程而且丰富了求解方法，本文根据网络图的资源分配问题的算法分析，用计算机语言（Delphi 7.0）实现了基于网络图的资源分配问题的求解和图形表示。
2 网络图的基本概念
一个图是由一些点及一些点之间的连线组成，它可以反映一些对象之间的关系。边是两点之间不带箭头的连线。弧是两点之间带箭头的连线。
无向图是由点及边构成的图，记为G=(V,E)，V、E分别是G的点集合和边集合。一条连接点Vi和Vj的边记为[Vi,Vj](或[Vj,Vi])。
有向图是由点及弧所构成的图，记为D=[V,A]，V、A分别是D的点集合和弧集合。一个方向是从Vi指向Vj的弧记为（Vi,Vj）。
现实生活中的许多问题用图形来描述可能更方便。例如，点可表示城市，连线表示一条铁路，或者用点表示通信站，而连线表示通信线路。图1表示了各作战阵地之间是否可通及之间距离的关系。
图1 作战阵地之间的网络图
3 基本算法分析
3.1 最短路问题
已知一个网络图D＝(V,E)，最短路问题就是寻求一条从起点S到终点T的路，使路上的总权和最小。Dijkstra算法是解决这类资源分配问题的一种算法。
3.2 Dijkstra算法的基本思想
求最短路的标号算法是1959年由E.W.Dijkstra首先提出来的，故称为Dijkstra算法。它是目前公认的较成熟的算法，但仅适用弧权C(E)≥0的情况。此算法不仅求出了由始点S到终点Ｔ的最短路(S,T)，而且也给出了从S到T的所有其他顶点的最短路。
Dijkstra算法的基本思想是：
若(vs,v1,v2,…,vk)是从vs到vk的最短路，则{(vs,v1,v2,…,vi)}是从vs到vi的最短路。
3.3 Dijkstrs算法的步骤
(1)求出从至所有后续节点nk的全部路径，并计算每条路径的长度Crk。
(2)设P1和 P2为从至nk的两条不同路径l(P1) ≠l(P2)， 是否成立?若是，则转入第三步；若否，则转入第四步。
(3)求L(pg ):=max{l(P1);l(P2)}, 令M:=M∪{pg}。
(4)求 l(Pp):=min{l(Pt)|Pt?埸M}。
(5) l(Pp)是否成立？若是，则转入第六步；若否，则停止计算，从至nk无最少费用路径。
(6)设P1和P2为从至nk的两条不同路径，l(P1) ≠l(P2)是否成立？若是，则转入第三步；若否，则转入第四步。设l(Pp)为最短路径Pp的长nj=ns，是否成立？若是，则停止计算，从至nk的最少费用路径由l(Pp)为路径Pp的长度给定；若否，则转入第七步。
(7)求从nj到不在路径Pp上的后续节点njq的所有路径，同时计算路径的长度l(,…,nj,njq):=l(Pp)+Cijq，令M:=M∪{Pp}，转至第二步。
其中：l(Pp)、l(P2)表示至nk的两条不同路径的长度，M表示原有节点的集合，nj、ns分别表示原有节点和最终节点。
4 程序设计
4.1 程序设计思想
在给定资源、阶段数及指标函数值之后，通过计算得出最优分配方案及最优值，同时用网络图的形式表示出所有分配方案及最优方案。
4.2 程序流程图分析
流程图如图2所示。
4.3 程序关键模块分析
4.3.1 将输入的指标函数矩阵转化为网络图的矩阵的模块
该模块是将输入的指标函数矩阵转化为网络图的矩阵。例如：有一个3阶段1个资源的问题，其指标函数矩阵（如图1），将形成一个节点为（资源+1）*（阶段-1）+2的网络图（如图3）。
图2 程序设计流程图
图3 3阶段1个资源的网络图
有向图的矩阵表示如下：
其中，程序算法规定：节点到本身节点用0表示，不通路用一个很大的数M来表示。
4.3.2 最短路问题两顶点间路径计算模块
a. 假设
给定一单连通图N，其中非负权C表示弧的长度或费用，找出到ns的最短或最小费用路径，集合M开始定义为M：={}。
b. 实现原理
从始点出发，依次确定由此节点至任意其他节点的最短路径，直到找出至终点ns的最短路径为止。
c. 算法步骤
(1)列出中间计算过程表，用来表示每步的计算结果，如表1所示。
表1 最短路径计算过程表
(2)确定所有的节点 nk(j)∈Ns(nj)，使得Ns(nj)?埸M，?坌nj≠ns(下标j表示原有的节点nj)。
(3)求出所有的路径Pk(j)=(Pj,nk(j)) ?坌n∈M及其长度l(Pk(j)):=l(Pp)+Cik(j)。
(4)求l(Pq(p)):=min{l(pk(j))}并在表中的节点nq下写出路径(,…,np,nq)及长度l(qj)，且M:=M∪(Pq)。
(5)nq=ns是否成立？是，停止计算。从至ns的最少费用路径为l(Pg) 的长度。若否，则去掉节点np∈Ns(nj)转至第六步。
(6)Ns(nj)= nj是否成立？是，停止计算。从至ns无最少费用路径。否，转至第三步。
4.3.3 当最优值取最大时的算法分析
以上的表示是最优值取最小的计算分析。如果最优值需要取最大时，用一个极大的数M（如M可取100）减去上述网络图中的指标函数值a,b,c,d,e,f作为本边上的指标函数值来计算，即把最优值为长转化为最短计算，最后再用M(100)的阶段倍减去最短值即可得最长值，而最优路径不会改变。
5 计算结果
笔者用Delphi 7.0实现了基于网络图的资源分配问题的求解和图形表示。通过输入指标函数矩阵及目标函数类型（如图4所示），计算机显示的网络图与输入的相应，节点上的数字表示这阶段开始时的状态，边上的数据表示最优线路在这一阶段分配的资源数对应的指标函数值，最优路径以红色表示出（如图5所示）。
图4 网络图输入界面
图5 网络图显示界面
通过实例的计算，系统实现了资源分配问题的计算，算出的结果与手工计算的结果完全相同，大大提高了效率，给解决资源分配这类问题带来了高效、安全的保证。系统能够显示出资源分配问题的网络图模型及最优线路，为用户更加深入的了解此分配方案提供了内部依据。不足之处是，系统只对过程函数为和的这一类型的资源分配问题进行了实现，计算的动态规划类型很有限，需要进一步把算法稍作更改和优化来克服此类缺点。
参考文献：
[1]张俊学. 作战运筹学[M]. 解放军出版社,2000.1.
[2]刘建永，等. 运筹学算法于编程实现——Delphi实现[M]. 清华大学出版社,2004.9.
[3]熊义杰. 运筹学教程[M]. 国防工业出版社,2004.9.
[4]徐培德, 等. 军事运筹学基础[M]. 国防科技大学出版社,2003.10.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
