图论网络规划

图论网络规划图论网络规划图论网络规划图论练习汪帆23土规12021某城市要建立一个消防站,为该市所属的七个区服务,如图所示,问应设在那个区,才能使它至最远区的路径最短。图5、1、1城市点线模型图解:分析:要求建立的消防站离最远区的路径最短,即要求出任意两点间最优路径,而后从最优路径中选取最大值中的最小值。具体方法则要运用Warshall-Foryd算法求出该图的路由表,从而根据路由表中的最优路线,寻求V1-V7到每一点的最优路径,并比较各路径中最长路径的大小,择取最小值即为题中之所问。(1),建立权矩阵:A=[03infinfinfinfinf;302inf1、82、5inf;Inf2062infinf;Infinf603infinf;Inf1、82304inf;Inf2、5infinf401、5;Infinfinfinfinf1、50](2),运用Warshall-Foryd算法,调用floyd(A)函数,求出该图的路由表(程序详见附录5、1):表5、1、1任意两点间最优路径表(路由表)V1V2V3V4V5V6V7V10357、84、85、57V23024、81、82、54V3520524、56V47、84、850378、5V54、81、823045、5V65、52、54、57401、5V77468、55、51、50(3),结果分析:上述矩阵为对称阵,主对角线为0,即消防站所建立的位置。其具体涵义为:消防站建立在Vi处时对应各个城市的最短路径,如此可以建立表5、1、2:图论网络规划全文共1页，当前为第1页。表5、1、2各点建立消防站的最远城市及其两者距离表图论网络规划全文共1页，当前为第1页。消防站点最远城市两者距离V1V47、8V2V24、8V3V76V4V78、5V5V75、5V6V57V7V48、5从表5、12可以瞧出,比较最远距离,不难瞧出,当消防站点选在V2城市时,其离最远城市的最优距离为最优:4、8。故而,应将消防站建立在V2城市。2某矿区有七个矿点,如图所示,已知各矿点每天的产矿量,现要从这七个矿点选一个来建造矿厂,问应选在哪个矿点,才能使各矿点所产的矿运到选矿厂所在地的总运力(千吨公里)最小。图5、2、1矿区点线模型图解:分析:总运力与两个因素有关:矿点与矿厂的距离、矿点产矿量,且都就是正比的关系,故而应当把矿点与矿厂的距离L与矿点产矿量X的成绩当做运力,进而将运力当做权矩阵的元,运用Warshall-Foryd算法求出该图的路由表,从而根据路由表中的最优路线,寻求V1-V7到每一点的最优路径,再将最优路径加总,进而寻求7个预设厂址中的最优路径总值的最小值的点即为所求矿厂点。(1),距离矩阵:L=产量矩阵:(2),权矩阵(运算程序见附录5、1):图论网络规划全文共2页，当前为第2页。i=1:7图论网络规划全文共2页，当前为第2页。(3),运用Warshall-Foryd算法,调用floyd(A)函数,求出该图的路由表(程序详见附录5、2、2):表5、2、1厂址预设及总运力V1V2V3V4V5V6V7总运力V1062026321016110V29014202641083V3134061281457V427182006101697V52112141041062V617822252406102V718、59、523、526、525、51、50105(4),结果分析由表5、2、1可知,厂址预设与该址到各个矿区的最优路径表清晰而明朗,并在表中最后一栏中的总运力可以观察出:当把V3设为矿厂时,其总运力最小,为57。故而应当选取V3矿区建立矿厂。附录5、1function[D,R]=floyd(A)D=A;n=length(D);fori=1:nforj=1:nR(i,j)=i;endendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(k,j);endendend图论网络规划全文共3页，当前为第3页。hl=0;图论网络规划全文共3页，当前为第3页。fori=1:nifD(i,i)<0hl=1;break;endendif(hl==1)fprintf(