第8讲最短路问题

数学建模与数学实验网络优化

最短路问题

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。

对于科学研究，市场和社会生活中许多关于管理、组织与计划中的优化问题，都可以用图论的理论和方法来加以解决。例如，1、各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题。2、在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小问题。图论介绍3、在组织生产中，如何使各工序衔接好，才能使生产任务完成得既快又好。4、在现有交通网络中，如何使调运的物资数量多且费用最小。实验目的实验内容2．会用MATLAB软件求最短路1．了解最短路的算法及其应用1．图论的基本概念2．最短路问题及其算法3．最短路的应用4．建模案例：最优截断切割问题5．实验作业图论的基本概念一、图的概念1．图的定义2．顶点的次数

3．子图二、图的矩阵表示1．关联矩阵2．邻接矩阵返回定义有序三元组G=(V,E,)称为一个图,如果：图的定义定义定义常用术语：（１）端点相同的边称为环．（２）若一对顶点之间有两条以上的边联结，则这些边称为重边．（３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边

称为相邻的边．（４）边和它的端点称为互相关联的．

（５）既没有环也没有重边的图，称为简单图．（６）任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n

为顶点的数目．（7）若V=XUY,X∩Y=Ø,且X中任两顶点不相邻，Y中任两顶点不相邻，则称G为二元图；若X中每一顶点皆与Y中一切顶点相邻，则G称为完备二元图，记为Km,n，其中m,n分别为X与Y的顶点数目．返回完备图二元图完备二元图顶点的次数例在一次聚会中，认识奇数个人的人数一定是偶数.返回子图返回关联矩阵注：假设图为简单图邻接矩阵注：假设图为简单图赋权图最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路基本概念树及其性质定义连通且不含圈的无向图称为树G1G2G3树树叶分枝点树枝不是树森林定理

设G是具有n个顶点的图，则下述命题等价：1)G是树（G无圈且连通）；2)G无圈，且有n-1条边；3)G连通，且有n-1条边；4)G无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即G为最小连通图）；6)G中任意两顶点间有唯一一条路.最短路问题主要内容及应用：最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.最短路问题的两种方法：Dijkstra和Floyd算法.1)

求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.固定起点的最短路假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．

因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．基本思想：最短路是一条路径，且最短路的任一段也是最短路。算法步骤：

MATLAB(road1)

12

34

5

6

7

8返回w=[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1whilek<nfori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendll=l;fori=1:nforj=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;fori=1:nifll(i)<lvlv=ll(i);v=i;endend

s(k+1)=vk=k+1u=s(k)endlzMATLAB(road1)w=[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);

fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1

whilek<nfori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendend

%求vll=l;fori=1:nforj=1:kifi==s(j)ll(i)=inf;%S中位点值取为无穷大endendend

lv=min(ll);%求ll的最小值v=find(ll==lv);%最小值所在位置

s(k+1)=vk=k+1u=s(k)

endlzMATLAB(road1new)使用Dijkstra应注意：1.可以求任意两点间的最短路。2.最短路不唯一，但最短路值相等。3.弧值非负，只能求最小，不能求最大。设起点为1，终点为n，引入0-1变量xij,边(i,j)在最短路上，则xij=1，对起点和终点以外的任意一个顶点，如果说明从i出发的所有边中必然有一条在最短路上，即最短路经过该顶点，则从其它顶点到该顶点的边中必然有一条边在最短路上，所以有最短路问题的0-1规划法对于顶点1和顶点n，则必然满足：0-1规划的最短路模型为22233122232231232例求下图点P0到点P11的最短距离。Model:sets:cities/P0,P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11/;roads(cities,cities)/P0,P1P0,P4P1,P2P1,P5P4,P8P4,P5P2,P3P2,P6P8,P9P5,P9P5,P6P9,P10P6,P10P10,P11P6,P7P3,P7P7,P11/:w,x;endsetsdata:!Herearethedistancesthatcorrespondtoabovelinks;w=12223332221223232;Enddatan=@size(cities);min=@sum(roads:w*x);@for(cities(i)|i#ne#1#and#i#ne#n:@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));@sum(roads(i,j)|i#eq#1:x(i,j))=1;@sum(roads(i,j)|j#eq#n:x(i,j))=1;@for(roads:@bin(x));end最短路的Lingo程序

Globaloptimalsolutionfound.Objectivevalue:

8.000000VariableValueReducedCostN12.000000.000000W(P0,P1)1.0000000.000000W(P0,P4)2.0000000.000000W(P1,P2)2.0000000.000000W(P1,P5)2.0000000.000000W(P4,P8)3.0000000.000000W(P4,P5)3.0000000.000000W(P2,P3)3.0000000.000000W(P2,P6)2.0000000.000000W(P8,P9)2.0000000.000000W(P5,P9)2.0000000.000000W(P5,P6)1.0000000.000000W(P9,P10)2.0000000.000000W(P6,P10)2.0000000.000000W(P10,P11)3.0000000.000000W(P6,P7)

2.0000000.000000

W(P3,P7)3.0000000.000000W(P7,P11)2.0000000.000000

X(P0,P1)1.0000000.000000X(P0,P4)0.0000000.000000X(P1,P2)0.0000000.000000

X(P1,P5)1.0000000.000000X(P4,P8)0.0000000.000000X(P4,P5)0.0000002.000000X(P2,P3)0.0000000.000000X(P2,P6)0.0000001.000000X(P8,P9)0.0000004.000000X(P5,P9)0.0000002.000000

X(P5,P6)1.0000000.000000X(P9,P10)0.0000000.000000X(P6,P10)0.0000001.000000X(P10,P11)0.0000000.000000

X(P6,P7)1.0000000.000000X(P3,P7)0.0000003.000000

X(P7,P11)1.0000000.000000即P0到P11的最短距离为8，路径为P0—P1—P5—P6—P7—P11.注：这种模型算法只能计算起点到终点的最短距离.每对顶点之间的最短路1．求距离矩阵的方法2．求路径矩阵的方法3．查找最短路路径的方法（一）算法的基本思想（三）算法步骤（二）算法原理算法的基本思想算法原理——求距离矩阵的方法算法原理——

求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．)(nRi

j算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：算法步骤D:d(i,j)为i到j的距离．R：r(i,j)为i到j之间的插入点．输入带权邻接矩阵W插入v1插入v2插入v3插入v4插入v5

MATLAB

(road2(floyd))function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendR

fork=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)=k;endendendkDRend主程序road2.m：a=[09inf3inf;902inf7;inf2024;3inf20inf;inf74inf0];[D,R]=floyd(a)5657536411423练习求以下网络图中从顶点到其余各顶点的最短路。主程序：w=[0526infinfinf;inf0infinf3infinf;inf30574inf;infinfinf0inf64;infinfinfinf0inf5;infinfinfinf101;infinfinfinfinfinf0];[D,R]=floyd(w)结果：D=0526767Inf0InfInf3Inf8Inf305545InfInfInf0764InfInfInfInf0Inf5InfInfInfInf101InfInfInfInfInfInf0R=1234636123456512346661234667123456712345671234567一、可化为最短路问题的多阶段决策问题二、选址问题1．中心问题2．重心问题返回可化为最短路问题的多阶段决策问题返回

选址问题--中心问题MATLAB(road3(floyd))S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=10,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6为最小,故应将消防站设在v3处.R=1222222123336622355225554555333456622255676666667

选址问题--重心问题可见，在第3或第5个矿点建造矿厂都可以使运力达到最小值70。(example3）输入：D=[0358778.5;3025445.5;5203267.5;8530156.5;7421045.5;7465401.5;8.55.57.56.55.51.50];Q=[3271614]';M=D*Qzuixiao=min(M)k=find(M==zuixiao)输出：M=13278709270106130zuixiao=70k=35实验作业

生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率.生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会.可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益.某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增.若生产产品过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费C3=0.4元.假定生产率每调整一次带有固定的调整费C1=1万元，问：工厂应如何制定当年的生产策略，使工厂的总损失最小？P119习题1答案：D=03545352510350152030254515010203535201001025