第二十四讲运筹学模型（8）——图论模型（续）

yunjiang

< align=left>　　本讲继续讨论图论模型，主要讨论最小树问题和最短路问题两个模型。看以下两个例子。
　　<B>例5</B> 设有七个单位要求煤气公司为其铺设煤气管道，经施工单位测量，七个单位间可通管道的路线长度如<a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/01.htm#" target="_blank" ><FONT color=#0000cc>表4－16</FONT></A>所示.其中单位A距煤气公司供应网最近，为1.5km.现拟铺设地下管道，并经A与供应网连通，铺设费用为25元/m，试协助施工单位进行施工路线设计，使得费用最少，求出最小费用值.
（其中的“－”表示其间无直达路线.）
　　关于最小树问题先介绍一点相关知识.通俗地讲，一个图中若有几个顶点及其边的交替序列形成闭回路，我们就说这个图有圈；若图中所有顶点间都有边相连接，就称该图是连通的；若两个顶点间有不止一条边连接，则称该图具有多重边.
　　一个图被称为是<U>树</U>是指该图是连通的无圈的简单图.图4—9是几个树图的例子.它们都具有以下特点：任意两顶点之间都可通过边连接起来，任何两顶点之间有且仅有一条边，不存在任何顶点与边的交替序列能形成闭回路；一旦再任意在两顶点间加一条边就立刻形成且形成一个圈；任意去掉一条边，立刻使图不连通.因此，具有相同顶点的图中，树形图的边数是最少的.这就提示我们，在研究涉及边长之和最短问题时，应该立刻想到树.
　　<IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image004.jpg">
　　图4—9</P>
< align=left> </P>
< align=left><IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/51.gif"></P>

yunjiang

<>　　回到我们的例子.为解决问题，先建立问题的图论模型 以七个单位为研究对象，其间有直达路线则连一条边，在相应的边旁标以相应的路长，便构成一个网络赋权图模型如图; 可见其中充满了圈，于是从中寻求树（顶点数相同）便成为关键.</P><>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image006.jpg"> </P><>                   图4—10</P><P>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image008.jpg"> </P><P>                    图4—11</P><P>　　先看A、B、C、D四个顶点形成的图4－11（a）. 该图总边长为19。            
　　在保证通气条件下，这个路线的费用最贵.因为如果按照图4—11（b）的树形图铺设，保证通气条件下，总费用仅为14（km）的费用.而按树形图4—11（C）铺设，则费用只有8（km）的费用.换句话讲，在相同顶点情形下，构成的树的总权数大小也有区别。因此自然提出了最小赋权树，简称最小树的概念：在具有相同顶点的树中，总赋权数最小的树称为最小树.在本例，我们要寻求的就是上述图模型中的最小树.</P>

yunjiang

<>　　最小树的求法有两种，一种称为“避圈法”，一种是“破圈法”，两法各具优缺点，但它们具有共同的特征——去掉图中的圈并且每次都是去掉圈中边权较大的边。这里仅介绍破圈法，就本例说明如下：<></P><></P><a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/03.htm#" target="_blank" ><FONT color=#0000cc>图4-12</FONT></A></P><P><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/1.gif"><P></P>
　　用破圈法求最小树时，先从图中任取一圈，去掉该圈的一条最大边；然后重复这个步骤，直到无圈为止。使用破圈法求解本例的过程如图4-12所示.<a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/03.htm#" target="_blank" ><FONT color=#0000cc>最优方案为</FONT></A><P></P>
　　最小树长为13（km）。再通过A与供应网联接，总长度为14.5km，因此总费用为<P></P>
　　25×14.5×10<SUP>3</SUP>=36.25(万元)<P></P></P>

yunjiang

<>　　<b>例6</b>  最短路问题的数学模型<></P>
　　最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点v<SUB>s</SUB>和一个终点v<SUB>t</SUB>，求v<SUB>s</SUB>到v<SUB>t</SUB>的一条路，使路长最短（即路的各边权数之和最小）。<></P>
　　许多实际问题都归结为最短路问题，例如两地间的管道铺设，线路安装，道路修筑，运路选取等等；再如工厂布局，设备更新等问题也可转化为最短路问题。<P></P>
　　这里介绍求最短路的常用算法：<P></P>
　　狄克斯屈（E.D.Dijkstra）双标号法<P></P>
　　该法是狄克斯屈在1959年提出的，适用于所有权数均为非负（即一切<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image018.gif"> </SUB>  <I normal">w<SUB>ij</SUB></I>表示顶点<I normal">v<SUB>i</SUB></I>与<I normal">v<SUB>j</SUB></I>的边的权数）的网络，能够求出网络的任一点<I normal">v<SUB>s</SUB></I>到其它各点的最短路，为目前求这类网络最短路的最好算法。<P></P>
　　该法在施行中，对每一个点<I normal">v<SUB>j</SUB></I>都要赋予一个标号，并分为固定号<I normal">P</I>（<I normal">v<SUB>j</SUB></I>）和临时标号<I normal">T</I>（<I normal">v<SUB>j</SUB></I>）两种，其含义如下：<P></P>
<I normal">　　P</I>（<I normal">v<SUB>j</SUB></I>）——从始点<I normal">v<SUB>s</SUB></I>到<I normal">v<SUB>j</SUB></I>的最短路长；<P></P>
<I normal">　　T</I>（<I normal">v<SUB>j</SUB></I>）——从始点<I normal">v<SUB>s</SUB></I>到<I normal">v<SUB>j</SUB></I>的最短路长上界。<P></P>
　　一个点<I normal">v<SUB>j</SUB></I>的标号只能是上述两种标号之一。若为T标号，则需视情况修改，而一旦成为P标号，就固定不变了。<P></P>
　　开始先给始点<I normal">v<SUB>s</SUB></I>标上P标号0，然后检查点<I normal">v<SUB>s</SUB></I>，对其一切关联边（<I normal">v<SUB>s</SUB></I>,<I normal"> v<SUB>j</SUB></I>）的终点<I normal">v<SUB>j</SUB></I>，给出<I normal">v<SUB>j</SUB></I>的T标号w<SUB>ij</SUB>；再在网络的已有T标号中选取最小者，把它改为P标号。以后每次都检查刚得到P标号那点，按一定规则修改其一切关联边终点的T标号，再在网络的所有T标号中选取最小者并把它改为P标号。这样，每次都把一个T标号点改为P标号点，因为网络中总共有n个结点，故最多只需n-1次就能把终点<I normal">v<SUB>t</SUB></I>改为P标号。这意味着已求得了<I normal">v<SUB>s</SUB></I>到<I normal">v<SUB>t</SUB></I>的最短路。<P></P>
　　狄克斯屈标号法的计算步骤如下：<P></P>
　　1° 令S={<I normal">v<SUB>s</SUB></I>}为固定标号点集，<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image020.gif"> </SUB>为临时标号点集，再令<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image022.gif"> </SUB><P></P>
</B>　　2°检查点<I normal">v<SUB>i</SUB></I>，对其一切关联边（<I normal">v<SUB>i</SUB></I>,<I normal"> v<SUB>j</SUB></I>）的终点<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image024.gif"> </SUB>,</B>计算并令<P></P>
<SUB>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image026.gif"> </SUB><P></P>
　　3°从一切<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image027.gif"> </SUB></B>中选取并令<P></P>
<SUB>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image029.gif"> </SUB><P></P>
　　选取相应的弧（<I normal">v<SUB>i</SUB></I>,<I normal"> v<SUB>r</SUB></I>）。再令<P></P>
<SUB>　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image031.gif"> </SUB><P></P>
　　4°若<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image033.gif"> </SUB></B>，则停止，<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image035.gif"> </SUB></B>即<I normal">v<SUB>s</SUB></I>到<I normal">v<SUB>j</SUB></I>的最短路长，特别<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image037.gif"> </SUB></B>即<I normal">v<SUB>s</SUB></I>到<I normal">v<SUB>t</SUB></I>的最短路长，而已选出的弧即给出<I normal">v<SUB>s</SUB></I>到各点的最短路；否则令<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image039.gif"> </SUB>，返2°。<P></P>
<B normal">　　</B>注意：若只要求<I normal">v<SUB>s</SUB></I>到某一点<I normal">v<SUB>t</SUB></I>的最短路，而没要求<I normal">v<SUB>s</SUB></I>到其他各点的最短路，则上述步骤4°可改为<P></P>
　　4°若r=t则结束，<B normal"><SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image041.gif"> </SUB></B>即为所求最短路长；否则令<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image043.gif"> </SUB>，返2°.</P>

yunjiang

　为熟悉算法，现就上一讲图4-10的网络图讨论。<></P>
　　在图4-10所示网络中，先给始点①的三条关联边的终点②，③，④临时标号：<></P>
　　点②：<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image045.gif"> </SUB><></P>
　　点③：<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image047.gif"> </SUB><P></P>
　　点④：<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/sxjm24.files/image049.gif"> </SUB><P></P>
　　从中选出最小标号T（2）=3，把它改变为固定标号P（2）=3，然后选出相应的弧（1，2）如图4-13（a）所示。图中每点旁圆括号内的数字为固定标号，无括号的数字为临时标号。粗箭线即所选取的弧（1，2）。以后每次都检查刚得到固定标号那点，对其所有关联边的终点修改临时标号，然后从一切临时标号中选出最小的把它改为固定标号，同时选出相应的弧，具体过程如<a href="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_24/htm/06.htm#" target="_blank" ><FONT color=#0000cc>图4-13</FONT></A>所示。 <P></P>
　　从图4-13(f)可以看出，从点①到⑦的最短路有两条：<P></P>
　　①→②→④→⑤→⑥→⑦<P></P>
　　①→②→⑤→⑥→⑦<P></P>
　　最短路长均为10。该图实际上给出了点①到各点的最短路。<P></P>
　　注：请注意最小树与最短路的区别。<P></P><P></P>

duanshumo

谢谢你的帖子

跳跳

谢谢

coeeoc

谢谢

cnpliuzuming

好东西呀

Mars000

谢谢