【摘要】：本章主要阐述了三类问题,均可以用线性规划模型进行表达。最小树就是存在于无向图中的权最小的树。破圈法和避圈法是寻找最小树的主要方法,在求解过程中应注意,圈可能是立体的,求得的最小树方案可能不是唯一的。其一般用于管路铺设及管线布置优化问题,这与最短路问题存在明显区别。本章中只阐述了权为非负的最短路问题的求解方法——狄克斯特拉标号算法。
图论中的图是由点和边(弧)构成的,与几何图形不同,点与点之间的边(弧)只表示相互的关系,并不是实际距离。本章主要阐述了三类问题,均可以用线性规划模型进行表达。
(1)最小树问题。
在图论中,树是无圈连通图。最小树就是存在于无向图中的权(一般指距离)最小的树。破圈法和避圈法是寻找最小树的主要方法,在求解过程中应注意,圈可能是立体的,求得的最小树方案可能不是唯一的。其一般用于管路铺设及管线布置优化问题,这与最短路问题存在明显区别。
(2)最短路问题。
最短路就是指一定网络中两结点间一条距离最小的路,不仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用等。最短路问题可用来解决路径优化和设备更新等实际问题。本章中只阐述了权为非负的最短路问题的求解方法——狄克斯特拉标号算法。(www.xing528.com)
(3)最大流问题。
最大流问题是一类应用极为广泛的问题,例如交通网络中的人流、车流、货物流,供水网络中的水流,金融系统中的现金流。最大流问题是一个特殊的线性规划问题,就是在容量网络中,寻找流量最大的可行流。在寻找增广链(可以扩充流量的路)的过程中,应先对前向弧标号,若前向弧均不能标号,再考虑对后向弧标号。
(4)最小树方法和最短路方法常用来改进(优化)方案,即在现有方案中找到总权最小的方案,在保证完成任务的前提下,减少材料和施工成本或者交通成本;最大流方法常用来发现问题,先使用标号法找到最大流,然后通过最小割集找到网络“瓶颈”,提出改善思路,目标是让决策者知道,可以通过改进哪一段弧上的容量来增加整个网络流量。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
