《图论中几个典型问题的求解.ppt》由会员分享，可在线阅读，更多相关《图论中几个典型问题的求解.ppt（161页珍藏版）》请在金锄头文库上搜索。
1、图论中几个典型问题的求解1 图的基本概念图图是是一一种种直直观观形形象象地地描描述述已已知知信信息息的的方方式式，它它使使事事物物之之间间的的关关系系简简洁洁明明了了，是是分分析析问问题题的的有有用用工工具具，很很多多实实际际问问题题可可以以用用图来描述。图来描述。一、一、图的定义图的定义 图图论论是是以以图图为为研研究究对对象象的的数数学学分分支支，在在图图论论中中，图由一些点和点之间的连线所组成图由一些点和点之间的连线所组成 称称图图中中的的点点为为顶顶点点（节节点点），称称连连接接顶顶点点的的没没有方向的线段为边，称有方向的线段为弧有方向的线段为边，称有方向的线段为弧用用V=v1,v2,
2、 表表示示全全体体顶顶点点的的集集合合，用用 E=e1,e2, 表表示示全全体体边边的的集集合合，如如果果对对于于E中中的的任任一一条条边边ek，在在V中中都都有有一一对对顶顶点点(vi,vj)和和它它对对应应，则则称称由由V和和E组组成成的的集集体体为为一一个个图图，记记为为G=V,E，简写为，简写为G二、基本概念二、基本概念 点点与与边边相相连连接接称称为为关关联联，与与边边e关关联联的的顶顶点点称称为为该该边边的的端端点点，与与同同一一条条边边关关联联的的两两个个顶顶点点称称为为相相邻邻顶顶点点，与与同同一一个个顶顶点点关关联联的的边边称称为为相相邻邻边边具具有有相相同同顶顶点点的的边边
3、称称为为平平行行边边，两两个个端端点点重重合合的的边边称称为为环环所所有有线线段段都都没没有有方方向向的的图图称称为为无无向向图图，所所有有线线段段都都有有方方向向的的图图称称为为有有向向图图，既既有有边边也也有有弧弧的的图图称称为为混混合合图图在在无无向向图图中中，没没有有环环和和平平行行边边的的图图称称为为简简单单图图，任任意意两两个个顶顶点点之之间间都都有有一一条条边边相相连连的的简简单单图图称称为为完完全全图图任任意意两两个个顶顶点点之之间间有且只有一条弧相连的有向图称为有且只有一条弧相连的有向图称为竞赛图竞赛图在在无无向向图图中中与与顶顶点点v关关联联的的边边的的数数目目（环环算算两
4、两次次）称称为为该该顶顶点点的的度度（或或次次数数），记记为为d(v)。度度为为奇奇数数的的顶顶点点叫叫做做奇奇点点，度度为为偶偶数数的的顶顶点点叫叫做做偶偶点点。在在有有向向图图中中，从从顶顶点点v引引出出的的边边的的数数目目称称为为该该顶顶点点的的出出度度，记记为为d+(v)，从从顶顶点点v引引入入的的边边的的数数目目称称为为该该顶顶点点的的入入度度，记记为为d-(v)，而而d(v)d+(v)+d-(v)称为称为v的的次数次数。在在图图中中，两两个个顶顶点点u和和v之之间间由由顶顶点点和和边边构构成成的的交交错错序序列列（使使u和和v相相通通）称称为为链链（通通道道），没没有有重重复复边边
5、的的通通道道称称为为迹迹，起起点点与与终终点点重重合合的的通通道道称称为为闭闭通通道道，不不重重合合的的称称为为开开通通道道，没没有有重重复复顶顶点点（必必然然边边也也不不重重复复）的的开开通通道道称称为为路路，起起点点与与终终点点重重合合的的路路称称为为圈圈（回回路路）包包含含奇奇数数个个顶顶点点（或或边边）的的圈圈称称为为奇奇圈圈，包包含含偶偶数数个个顶顶点点（或或边边）的的圈圈称称为为偶偶圈圈。如如果果顶顶点点u和和v之之间间存存在在一一条条路路，则则称称u和和v是是连连通通的的，任任意意两两个个顶顶点点都都连连通通的的图图称称为为连连通通图图无无圈圈的的连连通通图图称称为为树树，如如果
6、果一一棵棵树树T包含了图包含了图G的所有顶点，称的所有顶点，称T为为G的的生成树生成树如如果果图图G的的每每条条边边e都都对对应应一一个个实实数数C(e)，称称C(e)为为该该边边e的的权权，称称图图G为为赋赋权权图图通通常常称称赋赋权权的有向图为网络的有向图为网络图图中中边边e6和和e7是是平平行行边边，e9是是环环，顶顶点点v4是是悬悬挂点，边挂点，边e4是悬挂边是悬挂边2 最短路问题最最短短路路问问题题是是图图论论应应用用的的基基础础，很很多多实实际际问问题题，如如线线路路的的布布设设、运运输输规规划划、运运输输网网络络最最小小费费用用流流等等问问题题，都都可可以以通通过过建建立立最最短
7、短路路模模型型来来求求解解。有有些些有有深深度度的的图图与与网网络络优优化化问问题题，如如旅旅行行售售货货商商、中中国国邮邮递递员员等等问问题题，需需要要在在首首先先求求出出任任意意两两点点之之间最短路的基础上解决。间最短路的基础上解决。一、最短路的概念一、最短路的概念给给定定一一个个连连通通的的赋赋权权图图G=V,E，设设R是是连连接接节节点点vi和和vj的的一一条条路路，该该路路的的权权定定义义为为路路中中所所有有各各边边权权之之和和，如如果果路路R在在所所有有连连接接节节点点vi和和vj的的路路中权最小，则称它为中权最小，则称它为vi和和vj间的最短路。间的最短路。二、任意两点之间的最短
8、路二、任意两点之间的最短路(Floyd算法算法) Floyd算算法法利利用用距距离离矩矩阵阵进进行行迭迭代代运运算算，可可以以一一次次性性地地求求出出任任意意两两点点之之间间的的最最短短路路，该该方方法法的的思思路路有有创创意意，计计算算量量小小，编编程程较较简简单单，又又称称矩矩阵阵求解法。求解法。1算法原理算法原理 设设A=aijmn n是是图图的的权权矩矩阵阵（也也称称带带权权邻邻接接矩矩阵阵），其其中中aij是是图图上上连连接接顶顶点点i和和j的的边边的的权权，如如果果两两顶顶点点之之间间没没有有直直接接相相连连的的边边（即即两两顶顶点点不不相相邻），则邻），则aij=。令令矩矩阵阵D
9、(0)=A，作作为为迭迭代代的的初初始始矩矩阵阵，从从它它出出发发按按照照一一定定规规则则求求D(1)，又又由由D(1)按按照照类类似似的的规规则则求求D(2)，依依此此类类推推进进行行迭迭代代直直至至求求出出D(n)，设设矩阵矩阵D(m)的元素为的元素为dij(m)，迭代规则为：，迭代规则为： 上上式式表表示示dij(1)在在dij(0)以以及及从从顶顶点点vi经经过过顶顶点点v1到到vj的的权权之之和和di1(0)+d1j(0)两两者者之之中中选选择择最最短短长长度度。依此规则迭代。依此规则迭代。上上式式表表示示dij(2)在在dij(1)以以及及从从顶顶点点vi经经过过顶顶点点v2到到v
10、j的的权权之之和和di2(1)+d2j(1)两两者者之之中中选选择择最最短短长长度度。依此类推，迭代公式为依此类推，迭代公式为 ：上上式式表表示示dij(m)在在dij(m-1)以以及及从从顶顶点点vi经经过过顶顶点点vm到到vj的的权权之之和和dim(m-1)+dmj(m-1)两两者者之之中中选选择择最最短短长长度。当度。当m=n时结束迭代。时结束迭代。 2程序设计程序设计 先编写先编写Flody算法的子程序（函数）如下：算法的子程序（函数）如下：Function D,R=floyd(a)n=size(a,1); D=a; % D是初始矩阵是初始矩阵for i=1:n for j=1:n R
11、(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); %在循环中进在循环中进行矩阵迭代行矩阵迭代 R(i,j)=R(i,k); % R是路径矩阵是路径矩阵 end end endendD,R %输出最短路矩阵和最短路的路径矩阵。输出最短路矩阵和最短路的路径矩阵。以以上上程程序序是是通通用用程程序序，只只需需输输入入初初始始距距离离矩矩阵阵，就就能能输输出出最最短短路路矩矩阵阵以以及及最最短短路路的的路路径径矩矩阵阵，将将程序以文件名程序以文件名floyd.m存盘。存盘。
12、例例1 以以2007年年研研究究生生数数学学建建模模竞竞赛赛C题题为为例例，已已知知16个个邮邮政政支支局局的的初初始始距距离离矩矩阵阵，求求任任意意两两个个节点之间的最短路。节点之间的最短路。解：编写主程序如下：解：编写主程序如下：a=0, 27, 44, 17, 11, 27, 42, inf, inf, inf, 20, 25, 21, 21, 18, 27, inf;inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0; D,R=floyd(a);输输入入数数据据中中的的inf表表示示无无穷穷大大（两两个个顶顶点点之之间
13、间没有边直接相连）。没有边直接相连）。运运行行以以上上程程序序，求求得得最最短短路路矩矩阵阵D和和最最短短路路的的路径矩阵。路径矩阵。此处省略结果。此处省略结果。 3 最小生成树一、一、 最小生成树的概念最小生成树的概念树树是是图图论论中中的的一一种种简简单单而而重重要要的的图图，连连通通并并且且无无圈圈的的无无向向图图称称为为树树，常常用用T表表示示。树树有有以以下下性性质：质：(1) 树中任意两点之间有唯一路径；树中任意两点之间有唯一路径；(2) 树的边数等于顶点数减树的边数等于顶点数减1；(3) 在树中删去任意一条边就不连通；在树中删去任意一条边就不连通；(4) 在在树树中中任任意意两两
14、个个不不相相邻邻的的顶顶点点间间添添加加一一条条边，则恰好产生一个圈。边，则恰好产生一个圈。具具有有n个个顶顶点点的的无无向向连连通通图图是是树树的的充充分分必必要要条条件件是是它它有有n-1条条边边连连通通图图G的的子子图图T，如如果果它它的的顶顶点点集集与与G的的顶顶点点集集相相同同，且且T为为树树，则则称称T是是图图G的的生生成成树树，又又称称支支撑撑树树。如如果果图图的的边边有有权权（对对应应于于边边的的实实数数），则则生生成成树树上上各各边边权权的的总总和和称称为为生生成成树树的的权权，生生成成树树并并不不唯唯一一，权权达达到到最最小小的的生生成成树树称称为为最最小小生生成成树树(M
15、inimal Spanning Tree，简称简称MST)，最小生成树不一定唯一，最小生成树不一定唯一最最小小生生成成树树是是网网络络优优化化中中的的一一个个重重要要问问题题，在在网网络络设设计计中中有有广广泛泛的的应应用用，例例如如如如何何修修筑筑一一些些公公路路把把若若干干个个城城镇镇连连接接起起来来且且总总里里程程最最短短；如如何何架架设设通通讯讯网网络络将将若若干干个个地地区区连连接接起起来来且且总总费费用用最最省省；如如何何修修筑筑水水渠渠将将水水源源和和若若干干块块待待灌灌溉溉的的土土地地连连接接起起来来且且总总距距离离最最短短等等等等这这些些应应用用问问题题通通称称为为最最优连线
16、问题，其实质是寻找图的最小生成树优连线问题，其实质是寻找图的最小生成树二、二、Prim（普里姆）算法（普里姆）算法求求图图的的最最小小生生成成树树最最常常用用的的算算法法有有两两种种：Prim（普普里里姆姆）算算法法和和Kruskal（克克罗罗斯斯克克尔尔）算法，这两种方法都由贪婪法的思想发展而来。算法，这两种方法都由贪婪法的思想发展而来。贪贪婪婪法法又又称称贪贪心心法法，该该法法总总是是做做出出在在当当前前看看来来最最好好的的选选择择，也也就就是是说说该该算算法法并并不不从从整整体体最最优优考考虑虑，它它所所做做出出的的选选择择只只是是在在某某种种意意义义上上的的局局部部最最优优选选择择。虽
17、虽然然贪贪婪婪算算法法不不能能对对所所有有问问题题都都得得到到整整体体最最优优解解，但但是是它它对对某某些些问问题题能能够够得得到到整整体体最最优优解解，例例如如图图的的固固定定起起点点的的最最短短路路问问题题，最最小小生生成成树树问问题题。有有时时候候，即即使使贪贪婪婪算算法法不不能能得得到到整整体体最最优解，但其结果却是整体最优解的很好近似。优解，但其结果却是整体最优解的很好近似。Prim算算法法的的思思路路是是：把把所所有有顶顶点点分分成成部部分分（两两个个集集合合），一一个个用用S表表示示（该该集集合合中中的的顶顶点点都都涂涂成成红红色色），另另一一个个用用V-S表表示示（该该集集合合
18、中中的的顶顶点点都都涂涂成成白白色色），开开始始时时S中中只只有有一一个个顶顶点点v1，其其余余顶顶点点都都是是白白色色，在在一一个个端端点点为为红红色色，另另一一个个端端点点为为白白色色的的边边中中选选取取权权最最小小的的边边，将将该该边边涂涂红红（表表示示入入选选最最小小生生成成树树）并并且且把把该该边边的的白白色色端端点点也也涂涂红红（表表示示移移入入S中中）这这个个过过程程一一直直进进行行下下去去，S中中的的端端点点越越来来越越多多，直直到到所所有有顶顶点点都都涂涂成成红色为止，或者说红色边达到红色为止，或者说红色边达到n-1条为止。条为止。从从Prim算算法法的的思思路路中中可可以以
19、看看出出，该该算算法法的的关关键键是是如如何何找找出出连连接接红红点点和和白白点点的的所所有有边边中中找找出出权权最最小小的的边边。若若G为为完完全全图图，当当前前有有k个个红红点点，则则有有n-k个个白白点点，有有k(n-k)条条连连接接红红、白白点点的的边边，为为了了在在如如此此众众多多的的边边中中找找到到权权最最小小的的边边，可可以以分分两两步步走走，对对每每一一个个白白点点，先先从从连连接接该该点点至至k个个红红点点的的k条条中中找找出出权权最最小小的的边边作作为为候候选选边边，然然后后对对n-k个白点，从个白点，从n-k条候选边中找出权最小的边。条候选边中找出权最小的边。实现实现Pr
20、im算法的算法的Matlab编程思路如下：编程思路如下：(1) 设设第第一一个个红红点点是是节节点点v1。构构建建初初始始候候选选边边的的权权矩矩阵阵B。该该矩矩阵阵有有3行行，第第一一行行表表示示当当前前红红点点，开开始始时时第第一一个个红红点点是是v1，故故第第一一行行都都是是1，第第二二行行表表示示白白点点，开开始始时时白白点点的的序序号号是是2,3,n，第第三三行行表表示示连连接接红红点点和和白白点点的的边边的的权权值值。当当前前入入选选最最小小生生成成树树的的最最短短边边将将从从该该矩矩阵阵中中产产生生。初初始始最小生成树最小生成树T是空集。是空集。(2) 对对B矩矩阵阵的的第第3行
21、行排排序序，即即对对候候选选边边的的权权值值进进行行排排序序，选选取取最最短短边边（权权值值最最小小的的边边），把把该该边边涂涂红红（选选入入最最小小生生成成树树的的边边集集T），该该边边的的白白色端点也涂成红色。色端点也涂成红色。(3) 将将(2)选选出出的的边边移移出出B（不不参参与与下下一一轮轮竞竞选选），即即将将它它从从B矩矩阵阵中中删删除除。当当前前有有n-2个个白白点点（两两个个红红点点），对对每每个个白白点点都都有有到到两两个个红红点点的的两两条条边边，通通过过比比较较这这两两者者的的大大小小，选选出出权权值值小小的的边边，放放入入B矩矩阵阵的的相相应应位位置置上上，由由此此构构
22、建建新新的的候候选选边边矩矩阵阵B，此时，此时B矩阵的有矩阵的有n-2列。列。(4) 对对新新的的B矩矩阵阵重重复复(2)和和(3)，T中中的的边边将将越越来来越越多多，B矩矩阵阵的的列列数数越越来来越越少少，当当选选入入T中中的红色边达到的红色边达到n-1条时结束运算，输出条时结束运算，输出T。按照以上思路编写按照以上思路编写Matlab程序如下：程序如下：function T,e=prim(a)T=; % T为最小生成树的边集，开始为空集。为最小生成树的边集，开始为空集。e=0; % e是最小生成树的长度，开始为是最小生成树的长度，开始为0。v=1; %v表示第一个红点是表示第一个红点是1
23、号顶点。号顶点。n=size(a,1); %n是是总总顶顶点点数数，它它等等于于初初始始距距离离矩阵矩阵a的列数。的列数。c=2:n; % c代表所有白点，开始是代表所有白点，开始是2,3,n。for j=2:n b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j);end%以以上上一一段段程程序序生生成成3行行n-1列列的的矩矩阵阵，存存储储初初始始候候选选边边及及其其权权值值信信息息，该该矩矩阵阵的的第第一一行行都都是是1，表表示示第第一一个个红红色色点点是是1号号顶顶点点，第第二二行行表表示示白白色色点点依依次次为为2,3,n，第第三三行行表表示示所所有有连连接
24、接红红点点和白点的边的权值和白点的边的权值while size(T,2)n-1 %只只要要最最小小生生成成树树的的边边数数小于小于n-1就循环就循环m,i=min(b(3,:); %从从候候选选边边中中找找出出权权值值最最小小的的边边（其其值值存存入入变变量量m，序号为，序号为i）T(:,size(T,2)+1)=b(:,i);%当当前前最最短短边边（含含起起点点、终终点点和和权权值值3个个树树中中）存入存入T中当前列，表示入选最小生成树中当前列，表示入选最小生成树 e=e+b(3,i); %累计最小生成树的长度累计最小生成树的长度 v=b(2,i); %把把新新入入选选最最小小生生成成树树的
25、的边边的的白白色色端点变成当前红点端点变成当前红点t=find(c=b(2,i); c(t)= ; %把把该该点点从从白白点点集集合中移出去合中移出去b(:,i)= ; %把该边从候选边中删除把该边从候选边中删除 for j=1:length(c) d=a(v,b(2,j); if d0 & a(i,j)1，(2) 如如果果线线路路从从j到到k，则则uk=uj+1，且且避避免免来来回回重重复和圈，约束条件为复和圈，约束条件为:ujuk+xkj-(n-2)(1-xkj)+(n-3)xjk，1kn， 2jn jk；最优连线最优连线( (最小生成树最小生成树) ) 转化为整数规划：转化为整数规划：例
26、例3 假假设设某某电电力力公公司司计计划划在在七七个个村村庄庄之之间间架架设设电电线线，各各村村庄庄之之间间的的距距离离如如图图所所示示试试求求出出使电线总长度最小的架线方案使电线总长度最小的架线方案2. LINGO程序程序编写编写LINGO程序如下：程序如下：MODEL:sets: city / 1.7/: u;! 定义定义7个城市个城市; link( city, city): dist, x; !距离矩阵和决策变量距离矩阵和决策变量;endsets n = size( city);data: !dist是距离矩阵是距离矩阵;dist =0 3 4 7 100 100 100 3 0 3 2
27、 4 100 100 4 3 0 100 5 7 100 7 2 100 0 2 100 6 100 4 5 2 0 1 4 100 100 7 100 1 0 2100 100 100 6 4 2 0;!这里可改为你要解决的问题的数据这里可改为你要解决的问题的数据;enddata min = sum( link: dist * x); !目标函数目标函数; U(1)=0; for( link: bin( x); !定义定义X为为01变量变量; FOR(city( K)|K #GT# 1:sum( city( I)| I #ne# K: x( I, K) = 1; for(city( J)|
28、J#gt#1 #and# J #ne# K: u(J)=u(K)+X(K,J)-(N-2)*(1-X(K,J)+(N-3)*X(J,K); ); );sum( city( J)| J #GT# 1: x( 1, J) = 1; for(city(K) | K #gt# 1:U(K)=1; U(K)=N-1-(N-2)*X(1,K););end计算结果：目标函数值计算结果：目标函数值(最优连线的长度最优连线的长度)为为13，最优连线的构成如图所示最优连线的构成如图所示41235674 旅行商问题一、一、 旅行商问题的基本概念旅行商问题的基本概念旅旅行行商商问问题题（又又称称货货郎郎担担问问题题，
29、traveling salesman problem，简简称称TSP问问题题）是是典典型型的的组组合合优优化化问问题题，并并且且是是一一个个NP完完全全难难题题，其其提提法法为为：有有n个个城城市市，相相互互之之间间的的旅旅行行费费用用（或或距距离离）为为已已知知，有有一一个个旅旅行行推推销销商商，从从某某个个基基点点城城市市出出发发，要要遍遍访访其其余余n-1个个城城市市至至少少一一次次，最最后后回回到到出出发发点点，试试找找出出总总费费用用最最小小（或或总总路路程程最最短短）的旅行路线。的旅行路线。称称能能够够到到每每个个城城市市至至少少一一次次的的回回路路为为旅旅行行商商回路，其中费用最
30、少者为最优旅行商回路回路，其中费用最少者为最优旅行商回路. 在在图图论论中中，经经过过所所有有顶顶点点恰恰好好一一次次的的圈圈（路路）称称为为哈哈密密顿顿圈圈（路路），简简称称H圈圈（H路路），存存在在H圈的图称为哈密顿图，简称圈的图称为哈密顿图，简称H图。图。旅旅行行商商问问题题是是指指在在赋赋权权图图上上经经过过每每个个顶顶点点至至少少一一次次，且且总总长长度度（路路径径上上权权的的总总和和）达达到到最最小小的的闭闭通通路路。在在加加权权的的连连通通无无向向图图中中，权权最最小小的的H圈圈简简称称最最优优H圈圈；经经过过每每个个顶顶点点至至少少一一次次且且权权最最小小的的闭闭通通路路称称为
31、为最最优优旅旅行行商商回回路路。注注意意：最最优优H圈圈与与最最优优旅旅行行商商回回路路两两者者是是有有区区别别的的，最最优优H圈圈只只允允许许经经过过每每个个顶顶点点恰恰好好一一次次，而而最最优优旅旅行行商商回回路路允许经过某些顶点一次以上。允许经过某些顶点一次以上。定定理理1 在在加加权权图图G=（V，E）中中，若若对对任任意意顶顶点点x,y,z（zx,zy），都都满满足足w(x,y)w(x,z)+w(y,z)（三三角角形形的的两两边边之之和和大大于于等等于于第第三三边边，称称为为三三角角不不等等式式），则则该该图图的的最最优优哈哈密顿圈也是最优旅行商回路。密顿圈也是最优旅行商回路。 对对
32、于于连连通通的的非非完完全全赋赋权权图图G，先先求求出出任任意意两两点点之之间间的的最最短短路路，然然后后用用最最短短路路作作为为每每一一条条边边的的权权，构构造造一一个个以以V为为顶顶点点集集的的完完全全图图G=（V，E），容容易易证证明明，在在如如此此构构造造出出来来的的图图G中中，各各边边的的权权自自然然满满足足三三角角不不等等式式，故故在在加加权权图图G中中寻寻求求最最优优旅旅行行商商回回路路的的问问题题就就可可以以转转化化为为在在图图G中中寻寻求求最最优哈密顿圈的问题。优哈密顿圈的问题。寻寻找找最最优优哈哈密密顿顿圈圈和和最最优优旅旅行行商商回回路路是是图图论论中中的的典典型型问问题
33、题，而而且且是是一一个个NP完完全全难难题题。问问题题的的求求解解没没有有多多项项式式时时间间算算法法，除除了了穷穷举举法法，目目前前还还没没有有寻寻找找最最优优解解的的算算法法，随随着着顶顶点点数数的的增增加加，运运算算所所需需时时间间呈呈指指数数级级增增长长，当当顶顶点点数数较较大大时时，求求出出最最优优解解所所需需时时间间可可能能是是难难以以忍忍受受的的。可可行行的的方方法法是是用用近近似似算算法法，力力争争在在较较短短时时间间寻寻找找接接近近最最优优解的近似最优解。解的近似最优解。旅旅行行商商问问题题得得到到了了许许多多学学者者的的关关注注和和长长期期研研究究，提提出出了了多多种种近近
34、似似算算法法，例例如如分分支支定定界界法法、遗遗传传算算法法、模模拟拟退退火火法法、蚁蚁群群算算法法、神神经经网网络络方方法法、粒粒子子群群优优化化算算法法、重重绕绕最最小小生生成成树树法法、二二次次逐逐边边修修正法等。正法等。二、用二、用LINGOLINGO求解求解TSPTSP问题的方法一问题的方法一1. 把最优哈密顿圈问题转化为把最优哈密顿圈问题转化为0-1线性规划线性规划 将将任任意意两两点点之之间间的的最最短短路路作作为为两两点点之之间间边边的的权权构构造造完完全全图图G。引引入入0-1整整数数变变量量xij(且且ij)：若若xij=1则边则边i-j在回路中，而在回路中，而xij0则表
35、示否。则表示否。目标函数目标函数首首先先必必须须满满足足约约束束条条件件：对对每每个个城城市市访访问问一一次次且且仅仅一一次次。从从城城市市i出出发发一一次次(到到其其它它城城市市去去),表示为表示为从某个城市到达从某个城市到达j一次且仅一次，表示为：一次且仅一次，表示为：以以上上建建立立的的模模型型类类似似于于指指派派问问题题的的模模型型，对对TSP问题只是必要条件，并不充分。问题只是必要条件，并不充分。例例如如，用用图图示示路路线线连连接接六六个个城城市市，满满足足以以上上两两个个约约束束条条件件，但但这这样样的的路路线线出出现现了了两两个个子子回回路，两者之间不通，不构成整体巡回路线。路
36、，两者之间不通，不构成整体巡回路线。为为此此需需要要考考虑虑增增加加充充分分的的约约束束条条件件以以避避免免产产生子巡回。生子巡回。下面介绍一种方法：下面介绍一种方法：增增加加变变量量u ui i,i,i=2,3,n=2,3,n，（它它的的大大小小可可以以取取正正整整数数：例例如如从从起起点点出出发发所所达达到到的的城城市市u=2,u=2,依依此类推）。此类推）。312456附加约束条件：附加约束条件：ui-uj+nxijn-1,i=1,n，j=2,n，且且ij 。下下面面证证明明：(1)任任何何含含子子巡巡回回的的路路线线都都必必然然不不满满足足该约该约束条件束条件（不管（不管ui如何取值）
37、如何取值）；(2)全全部部不不含含子子巡巡回回的的整整体体巡巡回回路路线线都都可可以以满满足足该约该约束条件束条件（只要（只要ui取适当值）取适当值）。用用反反证证法法证证明明(1),假假设设存存在在子子巡巡回回，则则至至少少有有两两个个子子巡巡回回。那那么么（必必然然）至至少少有有一一个个子子巡巡回回中中不不含起点城市含起点城市1，如上图中的，如上图中的4564，则必有，则必有 u4-u5+nn-1，u5-u6+nn-1，u6-u4+nn-1，把把这这三三个个不不等等式式加加起起来来得得到到nn-1，不不可可能能，故故假假设设不不能能成成立立。而而对对整整体体巡巡回回，因因为为附附加加约约束
38、束中中j2,不包含起点城市不包含起点城市1，故不会发生矛盾。，故不会发生矛盾。对对于于整整体体巡巡回回路路线线，只只要要ui取取适适当当值值，都都可可以以满满足足该约该约束条件束条件：()对对于于总总巡巡回回上上的的边边，xij=1, ui可可取取访访问问城城市市i的的顺顺序序数数，则则必必有有ui-uj-1，约约束束条条件件ui-uj+nxijn-1变成：变成：-1+n n-1，必然成立。必然成立。()对对于于非非总总巡巡回回上上的的边边，因因为为xij=0 ，约约束束条条件件ui-uj+nxijn-1变成变成-1n-1，肯定成立。肯定成立。综综上上所所述述，该该约约束束条条件件只只限限止止
39、子子巡巡回回，不不影影响响其其它它，于于是是TSP问问题题转转化化成成了了一一个个整整数数线线性性规规划划问问题题。求最优哈密顿圈可以表示为规划：求最优哈密顿圈可以表示为规划：2. LINGO程序程序!旅行售货员问题旅行售货员问题;model:sets: city / 1.17/: u;! 定义定义17个城市个城市; link( city, city): dist, ! 距离矩阵距离矩阵; x; !决策变量决策变量;endsets n = size( city);data: !距离矩阵距离矩阵;C =0 16.3 11.9 10.1 28 12.9 6 20.6 28.4 22.2 20.8
40、35.7 22.1 30.2 23.7 27.8 3616.3 0 12.2 26.4 23.9 8.8 10.3 36.9 40.1 32.2 16.7 31.6 14.7 22.8 7.4 11.5 19.711.9 12.2 0 22 36.1 21 5.9 32.5 40.3 34.1 28.9 43.8 26.9 35 19.6 17.6 25.810.1 26.4 22 0 20.4 23 16.1 10.5 18.3 12.1 15.2 28.1 32.2 38.4 33.8 37.9 46.128 23.9 36.1 20.4 0 15.1 34 24 16.2 8.3 7.2
41、 7.7 24.3 18 31.3 35.4 32.912.9 8.8 21 23 15.1 0 18.9 33.5 31.3 23.4 7.9 22.8 9.2 17.3 16.2 20.3 28.56 10.3 5.9 16.1 34 18.9 0 26.6 34.4 28.2 26.8 41.7 25 33.1 17.7 21.8 3020.6 36.9 32.5 10.5 24 33.5 26.6 0 7.8 15.7 25.7 31.7 42.7 42 44.3 48.4 56.628.4 40.1 40.3 18.3 16.2 31.3 34.4 7.8 0 7.9 23.4 23
42、.9 40.5 34.2 47.5 51.6 49.122.2 32.2 34.1 12.1 8.3 23.4 28.2 15.7 7.9 0 15.5 16 32.6 26.3 39.6 43.7 41.220.8 16.7 28.9 15.2 7.2 7.9 26.8 25.7 23.4 15.5 0 14.9 17.1 25.2 24.1 28.2 36.435.7 31.6 43.8 28.1 7.7 22.8 41.7 31.7 23.9 16 14.9 0 18.4 10.3 25.7 33.4 25.222.1 14.7 26.9 32.2 24.3 9.2 25 42.7 40
43、.5 32.6 17.1 18.4 0 8.1 7.3 26.2 2330.2 22.8 35 38.4 18 17.3 33.1 42 34.2 26.3 25.2 10.3 8.1 0 15.4 23.1 14.923.7 7.4 19.6 33.8 31.3 16.2 17.7 44.3 47.5 39.6 24.1 25.7 7.3 15.4 0 18.9 20.327.8 11.5 17.6 37.9 35.4 20.3 21.8 48.4 51.6 43.7 28.2 33.4 26.2 23.1 18.9 0 8.236 19.7 25.8 46.1 32.9 28.5 30 5
44、6.6 49.1 41.2 36.4 25.2 23 14.9 20.3 8.2 0;!这里可改为你要解决的问题的数据这里可改为你要解决的问题的数据;enddata !目标函数目标函数; min = sum( link: dist * x); FOR( city( K): !进入城市进入城市K; sum( city( I)| I #ne# K: x( I, K) = 1; !离开城市离开城市K; sum( city( J)| J #ne# K: x( K, J) = 1; ); !保证不出现子圈保证不出现子圈; for(city(I)|I #gt# 1: for( city( J)| J#gt
45、#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)=n-1); ); !限限制制u的的范范围围以以加加速速模模型型的的求求解解，保保证证所所加加限限制并不排除制并不排除掉掉TSP问题的最优解问题的最优解; for(city(I) : u(I)=n-1 ); for( link: bin( x);!定义定义X为为01变量变量;end计算结果：计算结果：目标函数值：目标函数值：159.3路线：路线：1 17 73 3161617171414131315152 26 6111112125 510109 98 84 41 1因因为为以以上上规规划划是是线线性性规规划划，所所以以
46、求求解解不不费费时时，当当顶顶点点数数为为2030个个时时，一一般般几几分分钟钟就就可可以以得得到最优解。到最优解。利利用用LINGO软软件件的的强强大大优优化化能能力力，不不必必研研究究旅旅行行商商问问题题的的算算法法，通通过过编编写写不不太太复复杂杂的的LINGO程程序序，能能够够较较快快地地解解决决实实际际问问题题，达达到到事半功倍的效果。事半功倍的效果。 三、用三、用LINGOLINGO求解求解TSPTSP问题的方法二问题的方法二1. 对城市排序，找出最优排序对城市排序，找出最优排序在在现现实实中中的的城城市市交交通通图图中中，有有些些城城市市之之间间有有直直接接道道路路，有有些些则则
47、没没有有，如如果果两两点点之之间间没没有有直直接接的的通通路路，则则两两点点之之间间的的距距离离取取最最短短路路（经经过过其其它它点点），即即用用任任意意两两点点之之间间的的最最短短路路Cij作作为为图图的的距距离离矩矩阵阵，构构成成一一个个完完全全图图G，其其任任意意一一对对顶顶点点都都有有一一条条边边相相连连。图图G的的最最优优旅旅行行商商回回路路等等价价于于图图G的的最最优优哈哈密密顿顿圈圈，此此时时形形式式上上的的环环形巡回路线实际上个别点有可能不止经过一次。形巡回路线实际上个别点有可能不止经过一次。设设某某个个城城市市为为旅旅行行的的出出发发地地和和终终点点（相相当当于于总总部部所所
48、在在地地），旅旅行行者者从从该该城城市市出出发发到到其其它它n个个城城市市各各一一次次且且仅仅一一次次，最最后后回回到到出出发发地地。我我们们把把行行进进路路线线分分成成n步步，每每一一步步到到一一个个城城市市（第第n+1步步返返回回出出发发地地），于于是是一一条条旅旅行行路路线线就就相相当当于于n个个城城市市的的一一种种排排列列，n个个城城市市共共有有n!种种排排列列方方式式。排排序序不不同同则则总总里里程程（或或费费用用）可可能能不不同同，总总里里程程（或或总总费费用用）最最小小的的排排序序就就是是我我们们要要寻寻找的最优路线。找的最优路线。引引入入0-1型型决决策策变变量量Xkj，下下标
49、标k表表示示旅旅行行的的步步数数，下下标标j表表示示到到达达哪哪一一个个城城市市，Xkj=1表表示示旅旅行行者者第第k个个目目的的地地（到到达达点点）是是城城市市j，Xkj=0则则表表示示否否。用用lj表表示示总总部部到到各各城城市市的的距距离离，用用Cij表表示示城市城市i与城市与城市j之间的最短路。之间的最短路。从出发地到第从出发地到第1个点的路程为个点的路程为从最后一个点返回出发地的里程为从最后一个点返回出发地的里程为 假假设设在在第第k步步到到达达城城市市i，在在第第k+1步步达达到到城城市市j，即，即Xki=Xk+1,j=1，则走过的里程为：，则走过的里程为： CijXkiXk+1,
50、j从第从第1点到第点到第n点走过的总里程为点走过的总里程为目标函数为目标函数为约束条件有以下约束条件有以下2条：条：(1) 每一步到达一个城市，即每一步到达一个城市，即(2) 每一个城市必须到一次且只需一次，即每一个城市必须到一次且只需一次，即综综上上所所述述，可可以以把把最最优优哈哈密密顿顿圈圈问问题题转转化化成成如下非线性如下非线性0-1 规划规划以上规划中允许包含其它约束条件。以上规划中允许包含其它约束条件。用用LINGO可以求解该规划，举例如下。可以求解该规划，举例如下。某某县县邮邮局局和和10个个乡乡镇镇支支局局组组成成该该县县的的邮邮政政运运输输网网络络，已已知知县县局局到到各各支
51、支局局的的距距离离和和支支局局之之间间的的距距离离矩矩阵阵（数数据据在在程程序序中中）。用用一一辆辆邮邮车车完完成成邮邮件件运运输输任任务务，邮邮车车从从县县局局出出发发到到各各支支局局去去一一次次且且只只需需一一次次，最最后后回回到到县县局局，求求总总路路程程最最短的行驶路线。短的行驶路线。解解：本本题题是是“旅旅行行商商”问问题题。可可以以用用上上面面介介绍的方法求解。绍的方法求解。编写编写LINGO程序如下：程序如下：MODEL:SETS: CITY/1.10/: JL; STEP/1.10/; LINE( STEP, CITY): X; LINKS(CITY,CITY):C;ENDSE
52、TSDATA: JL=71,56,27,30,28,26,15,9,30,27; C= 0,15,44,47,64,83,86,75,93,98 15,0,29,32,49,68,71,60,78,83 44,29,0,20,37,53,42,31,49,54 47,32,20,0,17,36,42,39,60,57 64,49,37,17,0,19,37,37,58,55 83,68,53,36,19,0,18,35,56,47 86,71,42,42,37,18,0,24,38,29 75,60,31,39,37,35,24,0,21,26 93,78,49,60,58,56,38,21,
53、0,29 98,83,54,57,55,47,29,26,29,0;ENDDATAFOR( LINE : BIN( X); M1=SIZE(STEP); FOR(CITY(I): SUM(STEP(N): X(N,I) = 1);FOR(STEP(N):SUM(CITY(I):X(N,I)=1);L1=SUM(CITY(I):(X(1,I)+X(M1,I)*JL(I);LX=SUM(STEP(N)|N#LT#M1:SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J);MIN=L1+LX;END在程序运行前需要对在程序运行前需要对LINGO的参数作必要的设置。的参数作必要的
54、设置。对对于于非非线线性性规规划划，LINGO提提供供两两种种求求解解方方法法，一一种种是是“Global Solver”（称称为为全全局局优优化化求求解解器器），另另一一种种是是“Multistart Solver”（称称为为多多起起点点算算法法），全全局局优优化化求求解解器器优优点点是是确确保保找找到到全全局局最最优优解解，缺缺点点是是有有时时需需要要较较长长运运行行时时间间。多多起起点点算算法法的的优优点点是是节节省省运运行行时时间间，但但不不能能保保证证找找到到的的解解就就是是全全局局最最优优解解，设设置置起起点点数数多多一些往往找到的解就是全局最优解。一些往往找到的解就是全局最优解。
55、点点击击菜菜单单“Options”，再再打打开开全全局局优优化化求求解解器器“Global Solver”选选 项项 ， 可可 以以 选选 或或 不不 选选 “Global Solver”，当当选选择择多多起起点点算算法法“Multistart Solver”时时，需需要要设设置置起起点点数数，若若选选择择“Solver Decides”表表示示由由LINGO决定。决定。对对以以上上程程序序，我我们们选选择择“Global Solver”，点点击击菜菜单单“Options”，在在全全局局优优化化求求解解器器“Global Solver”选选项框内打项框内打“”，再点击，再点击“确定确定”。运行
56、以上程序，费时运行以上程序，费时4分多钟，得到最优解：分多钟，得到最优解：目标函数值（总路程）目标函数值（总路程）260公里公里邮车的行驶路线为：邮车的行驶路线为：县局县局8910765412389107654123县局县局四、四、 多旅行商（多旅行商（MTSP）问题）问题1. 多旅行商问题的概念多旅行商问题的概念在在现现实实中中问问题题中中，有有时时候候不不是是由由一一人人走走遍遍所所有有点点，而而是是由由几几个个人人分分工工合合作作，每每个个人人只只到到其其中中部部分分城城市市，每每个个点点都都有有人人来来过过一一次次且且只只需需一一次次，事事先先不不指指定定谁谁到到哪哪些些点点，求求出出
57、使使总总路路程程最最小的旅行规划（每个人的行走路线）。小的旅行规划（每个人的行走路线）。例例如如邮邮路路规规划划中中，为为了了在在允允许许的的时时间间内内完完成成邮邮件件运运输输任任务务，县县局局的的邮邮车车往往往往不不止止1辆辆，而而是是用用若若干干辆辆邮邮车车分分工工运运输输，只只要要保保证证每每个个支支局局有有邮邮车车来来过过即即可可，为为了了节节省省行行驶驶费费用用，需需要要规规划划几辆邮车的最佳路线。这就是多旅行商问题。几辆邮车的最佳路线。这就是多旅行商问题。多多旅旅行行商商问问题题的的提提法法如如下下：有有n+1个个城城市市，相相互互间间的的路路程程（或或旅旅行行费费用用）为为已已
58、知知，有有k个个旅旅行行商商都都从从总总部部所所在在城城市市出出发发，赴赴其其它它城城市市旅旅行行推推销销，分分工工遍遍历历其其余余n个个城城市市，即即每每个个城城市市各各有有任任意意一一名名旅旅行行商商来来过过一一次次且且仅仅一一次次，最最后后都都回回到到出发地，目标是总路程最短或总费用最省。出发地，目标是总路程最短或总费用最省。多多旅旅行行商商问问题题在在物物流流配配送送、邮邮路路优优化化等等方方面面具具有有较较高高的的实实用用价价值值，而而在在现现实实问问题题中中，研研究究对对象象往往往往不不是是单单纯纯的的旅旅行行商商问问题题，而而要要考考虑虑各各种种约约束束条条件件，例例如如时时间间
59、约约束束、载载重重量量约约束束等等等等。研研究究这这一一类类带带约约束束条条件件的的多多旅旅行行商商问问题题具具有有很很强的现实意义。强的现实意义。 在在现现实实的的多多旅旅行行商商问问题题中中，往往往往带带有有约约束束条条件，例如时间约束、载重量约束等等。件，例如时间约束、载重量约束等等。带带约约束束条条件件的的多多旅旅行行商商问问题题具具有有广广泛泛现现实实意意义义，且且是是极极具具挑挑战战性性的的难难题题，我我们们仍仍然然把把它它转转化为化为0-1非线性规划并编成非线性规划并编成LINGO程序来求解。程序来求解。实例实例某某县县邮邮政政局局管管辖辖16个个支支局局，已已知知县县局局到到各
60、各支支局局的的距距离离以以及及16个个支支局局之之间间的的距距离离矩矩阵阵。寄寄达达各支局和各支局收寄的邮件各支局和各支局收寄的邮件(袋袋)如下表所示：如下表所示：县邮局和各支局分布图县邮局和各支局分布图每每一一辆辆邮邮车车最最多多装装载载65袋袋邮邮件件，邮邮车车的的运运行行成成本本为为3元元/ /公公里里。试试用用最最少少邮邮车车，并并规规划划邮邮车车的行驶路线使总费用最省。的行驶路线使总费用最省。分析分析：首首先先考考虑虑最最少少邮邮车车数数量量，由由题题目目所所给给表表中中数数据据，寄寄达达16个个支支局局的的邮邮件件总总数数为为176袋袋，从从各各支支局局收收寄寄的的邮邮件件总总数数
61、为为170袋袋，每每一一辆辆邮邮车车最最多多容容纳纳65袋袋邮邮件件，至至少少需需要要176/652.7辆辆邮邮车车，由由于于邮邮车车数数量量为为整整数数，故故最最少少需需要要3辆辆邮邮车车。如如果果3辆辆邮邮车车能能够够完完成成邮邮件件运运输输任任务务，则则3辆辆车车就就是是邮邮车数量的最优解。车数量的最优解。 运运输输费费用用与与行行驶驶里里程程成成正正比比，总总里里程程最最短短对对应应总总费费用用最最省省。把把16个个支支局局放放在在一一起起作作为为一一个个整整体体考考虑虑，找找出出3条条邮邮路路，每每条条邮邮路路都都从从县县局局出出发发，到到若若干干支支局局进进行行卸卸装装，最最后后回
62、回到到县县局局。各各邮邮车车路路过过的的支支局局数数量量未未知知，合合理理安安排排各各邮邮车车的的行行驶驶路路线线，由由3辆辆邮邮车车分分别别承承包包运运输输，在在满满足足运运载载量量约约束束前前提提下下，把把3条条巡巡回回路路线线的的总总里里程程最最小小作作为为优优化化的的目目标标。该该问问题题相相当当于于附附带带约约束束条条件件的多旅行商模型。的多旅行商模型。2. 0-1规划模型规划模型引引入入0-1型型决决策策变变量量Xkj,Ykj,Zkj，分分别别表表示示3辆辆邮邮车车第第k步步到到达达支支局局j，下下标标k表表示示邮邮车车行行走走的的步步数数，下下标标j表表示示到到达达哪哪一一个个支
63、支局局，当当决决策策变变量量Xkj,Ykj,Zkj等等于于1时时分分别别表表示示某某邮邮车车第第k个个装装卸卸点点是是支支局局j，等等于于0时时表表示示否否。设设各各邮邮车车管管辖辖的的支支局局数数量量分分别别为为m1,m2,m3，则则m1+m2+m3=16。约束条件有以下约束条件有以下3条：条：(1) 任何一辆车在任何一步到达一个支局任何一辆车在任何一步到达一个支局 ，即，即(2) 任任何何一一个个支支局局必必须须有有一一辆辆邮邮车车到到达达一一次次且只需要一次，即且只需要一次，即 (3) 在在邮邮车车行行进进的的任任何何路路段段上上，装装载载的的邮邮件件不超过不超过65袋。袋。 设设寄寄达
64、达各各支支局局的的邮邮件件量量为为Pj，各各支支局局收收寄寄的的邮邮件件量量为为Qj。 装装载载量量是是动动态态变变化化的的，以以第第1辆辆邮邮车为例，出发时的装载量为车为例，出发时的装载量为到第到第1个支局卸装以后，装载量变为个支局卸装以后，装载量变为在行驶过程中，装载量的递推公式为在行驶过程中，装载量的递推公式为约束条件为约束条件为综综上上所所述述，建建立立多多旅旅行行商商问问题题的的0-1规规划划模模型型如下：如下：装载量的计算公式为：装载量的计算公式为：3. LINGO程序程序编写编写LINGO程序如下：程序如下：MODEL:SETS: STATION/1.16/: JL,P,Q; S
65、TEPX/1.6/:WX; STEPY/1.5/:WY; STEPZ/1.5/:WZ; LINEX( STEPX, STATION): X; LINEY( STEPY, STATION): Y; LINEZ( STEPZ, STATION): Z; LINKS(STATION,STATION):C;ENDSETSDATA: JL=27 36 17 11 24 31 44 40 30 20 25 21 21 18 27 36; P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14; Q=9,14,5,10,9,10,13,9,15,9,6,7,13,15,10
66、,16; C= 0 31 27 38 51 58 71 67 57 47 52 48 21 41 52 61 31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63 27 19 0 14 27 34 47 49 39 29 42 38 38 29 38 44 38 33 14 0 13 20 33 35 25 15 33 32 32 15 24 30 51 27 27 13 0 9 21 37 26 26 43 45 45 28 29 38 58 32 34 20 9 0 13 32 32 35 47 52 52 35 33 42 71 45 47 33
67、21 13 0 19 30 39 50 65 65 48 44 40 67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21 57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13 47 47 29 15 26 35 39 20 10 0 18 36 41 14 9 18 52 61 42 33 43 47 50 31 20 18 0 23 46 25 14 23 48 57 38 32 45 52 65 54 43 36 23 0 27 22 33 42 21 52 38 32 45 52 65 61 51 41 4
68、6 27 0 39 48 57 41 48 29 15 28 35 48 34 24 14 25 22 39 0 11 20 52 56 38 24 29 33 44 25 14 9 14 33 48 11 0 9 61 63 44 30 38 42 40 21 13 18 23 42 57 20 9 0;ENDDATAFOR( LINEX : BIN( X); FOR( LINEY : BIN( Y); FOR( LINEZ : BIN( Z);M1=SIZE(STEPX); M2=SIZE(STEPY);M3=SIZE(STEPZ); FOR(STATION(I): SUM(STEPX(N
69、): X(N,I)+SUM(STEPY(N): Y(N,I)+SUM(STEPZ(N): Z(N,I) = 1);FOR(STEPX(N):SUM(STATION(I):X(N,I)=1);FOR(STEPY(N):SUM(STATION(I):Y(N,I)=1);FOR(STEPZ(N):SUM(STATION(I):Z(N,I)=1);WX0=SUM(STATION(I):P*SUM(STEPX(N):X(N,I); WY0=SUM(STATION(I):P*SUM(STEPY(N):Y(N,I); WZ0=SUM(STATION(I):P*SUM(STEPZ(N):Z(N,I);WX(1
70、)=WX0-SUM(STATION(J):(P(J)-Q(J)*X(1,J);WY(1)=WY0-SUM(STATION(J):(P(J)-Q(J)*Y(1,J);WZ(1)=WZ0-SUM(STATION(J):(P(J)-Q(J)*Z(1,J);FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-SUM(STATION(J):(P(J)-Q(J)*X(N,J);FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-SUM(STATION(J):(P(J)-Q(J)*Y(N,J);FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-SUM(STA
71、TION(J):(P(J)-Q(J)*Z(N,J);WX0=65; WY0=65; WZ0=65;FOR(STEPX(N):WX(N)=65); FOR(STEPY(N):WY(N)=65); FOR(STEPZ(N):WZ(N)1），可可以以用用Edmonds算算法法解解决决，其其基基本本思思路路为为：首首先先将将奇奇点点配配对对，使使配配对对以以后后各各对对之之间间距距离离的的总总和和（两两点点之之间间的的距距离离按按照照最最短短路路计计算算）达达到到最最小小（称称为为最最佳佳配配对对）,求求最最佳佳配配对对的的方方法法可可以以用用匈匈牙牙利利法法或或0-1规规划划法法等等方方法法（可可以
72、以用用Lingo实实现现）。然然后后把把每每一一对对点点之之间间的的最最短短路路作作为为边边添添加加到到原原图图中中,使使之之成成为为欧欧拉拉图图G *，找出找出G *的欧拉巡回就是原图的最佳巡回。的欧拉巡回就是原图的最佳巡回。算法步骤如下：算法步骤如下：(1) 用用Floyd算算法法求求出出所所有有奇奇点点之之间间的的最最短短路路径径和距离矩阵。和距离矩阵。(2) 用用匈匈牙牙利利法法或或0-1规规划划法法求求出出所所有有奇奇点点之之间间的最佳配对。的最佳配对。(3) 在在原原图图上上添添加加最最佳佳配配对对所所包包含含的的两两两两顶顶点点之间的最短路得到欧拉图之间的最短路得到欧拉图G *。
73、(4) 用用Fleury算算法法确确定定一一个个G *的的欧欧拉拉巡巡回回，这这就是就是G的最优巡回。的最优巡回。 三、三、Fleury算法的算法的Matlab程序程序 设设图图是是连连通通无无向向图图，如如果果所所有有顶顶点点都都是是偶偶点点，则则该该图图是是欧欧拉拉图图，必必然然存存在在欧欧拉拉巡巡回回，如如果果恰恰好好有有两两个个奇奇次次顶顶点点，则则称称该该图图为为半半欧欧拉拉图图，必必然然存存在在起起点点在在奇奇点点（两两个个奇奇点点中中的的一一个个）且且终终点点在在另另一一个个奇奇点点的的欧欧拉拉道道路路。这这两两种种情情况况下下都都可可用用fleury算法确定一条欧拉巡回或者欧拉
74、道路。算法确定一条欧拉巡回或者欧拉道路。按按照照fleury算算法法的的思思路路编编写写Matlab程程序序。主主要要程程序序arEuler根根据据图图的的边边集集确确定定是是否否为为欧欧拉拉图图、半半欧欧拉拉图图或或非非欧欧拉拉图图，如如果果是是欧欧拉拉图图则则用用fleury算算法法找找到到一一条条欧欧拉拉巡巡回回路路线线（欧欧拉拉图图的的欧欧拉拉巡巡回回不不止止一一条条，输输出出的的是是其其中中的的一一条条），如如果果是是半半欧欧拉拉图图则则返返回回一一条条欧欧拉拉道道路路，其其起起点点在在两两个个奇奇点点之之一一，终终点是另一个奇点。点是另一个奇点。function eu,cEu=ar
75、Euler(E)%输输入入参参数数E是是图图的的边边集集（m行行2列列矩矩阵阵，每每一一行行的的两两个个数数字字代代表表一一条条边边的的两两个个顶顶点点，共共有有m条条边边），输输出出参参数数eu有有三三种种结结果果：若若为为欧欧拉拉图图则则eu=1；半半欧欧拉拉图图则则eu=0.5；否否则则eu=0。输输出出参参数数cEu是是m行行1列矩阵，表示欧拉巡回或欧拉道路中边的序列。列矩阵，表示欧拉巡回或欧拉道路中边的序列。eu = 0; % eu的初始值为的初始值为0cEu=; % cEu开始时为空集开始时为空集ncV=arComp(E); % 调调用用函函数数arComp确确定定图图的的分枝构成
76、，判断是否连通分枝构成，判断是否连通 if max(ncV)1, % 表表示示有有2个个或或以以上上互互不不连连通通的的部分部分 return % 不是连通图就返回不是连通图就返回endn=max(max(E(:,1:2); % n是图的顶点总数是图的顶点总数m=size(E,1); % m是边的总数是边的总数for i=1:n b(i)=0; for j=1:m if E(j,1)=i|E(j,2)=i b(i)=b(i)+1; end endend% b表示各顶点的度数表示各顶点的度数rp=rem(b,2); % 各顶点的度数除各顶点的度数除2取余数，偶点取余数，偶点的余数为的余数为0，奇
77、点的余数为，奇点的余数为1srp=sum(rp); % srp是是rp的总和的总和switch srp case 0, % 若余数的总和为若余数的总和为0，则所有顶点为偶，则所有顶点为偶点，原图是欧拉图点，原图是欧拉图 eu=1; case 2, % 恰好有两个奇点，原图是半欧拉图恰好有两个奇点，原图是半欧拉图 eu=0.5; otherwise, % 否则是非欧拉图否则是非欧拉图 returnend% 以下程序寻找一条欧拉巡回或欧拉道路以下程序寻找一条欧拉巡回或欧拉道路 if srp=0, % 对于欧拉图对于欧拉图 v1=1; % 把第一个顶点作为欧拉巡回的起点把第一个顶点作为欧拉巡回的起点
78、 else % 对于半欧拉图对于半欧拉图 v1=find(rp); %先找出奇点先找出奇点 v1=v1(1); % 把第一个奇点作为欧拉道路的起把第一个奇点作为欧拉道路的起点点 end vc=v1; % vc是当前顶点是当前顶点 m=size(E,1); % m是边的总数是边的总数 E1=E(:,1:2), 1:m; % E1代表候选边集，开代表候选边集，开始时它的前两列与始时它的前两列与E相同，第三列表示边的顺序号相同，第三列表示边的顺序号% 以下是以下是Fleury算法算法 while isempty(E1), %若若E1非空则循环非空则循环 evc=find(E1(:,1)=vc)|(E
79、1(:,2)=vc); % 找出找出与当前顶点与当前顶点vc关联的边关联的边 levc=length(evc); % 统计与当前顶点统计与当前顶点vc关联的边关联的边的总数的总数 if levc=1, % 只有一条路只有一条路 cEu=cEu;E1(evc,3); % 把新的边加入欧拉把新的边加入欧拉巡回或欧拉道路中巡回或欧拉道路中 vcold=vc; vc=sum(E1(evc,1:2)-vc; % vc为新的当前点为新的当前点 E1=E1(setdiff(1:size(E1,1),evc),:); % 删除删除孤立顶点孤立顶点 E2=E1(:,1:2); E2gv=E2vcold; E2(
80、E2gv)=E2(E2gv)-1; E1(:,1:2)=E2; if vcvcold, vc=vc-1; end if v1vcold, v1=v1-1; end else % 从顶点从顶点vc出发有若干条路可供选择出发有若干条路可供选择 for k=1:levc, E2=E1(setdiff(1:size(E1,1),evc(k),:); ncv=arComp(E2); % 确确定定E2的的互互不不相相连连的的分枝数目分枝数目 nco=max(ncv); if (max(ncv)=1), % 此此时时E2为为连连通通图图，即即选选中的边不是割边（桥）中的边不是割边（桥） cEu=cEu;E1
81、(evc(k),3); % 把把该该边边加加入入欧欧拉巡回或欧拉道路中拉巡回或欧拉道路中 vc=sum(E1(evc(k),1:2)-vc; % vc为新的当前点为新的当前点 E1=E2; break; end end end endreturn在在fleury算算法法过过程程中中，每每次次预预选选一一条条边边，需需要要判判断断它它是是否否为为当当前前子子图图的的割割边边，为为此此先先假假定定把把该该边边从从当当前前边边集集中中删删去去，然然后后判判断断余余下下的的子子图图是是否否连连通通，若若不不连连通通，则则选选中中的的边边是是当当前前子子图图的的割割边边，若若仍仍然然连连通通，则则不不是
82、是割割边边，可可以以把把该该边边加加入入巡巡回回中。中。在在程程序序arEuler中中，通通过过调调用用函函数数arComp来来确确定定图图的的互互不不连连通通的的分分枝枝数数，根根据据它它的的返返回回结结果果判判定图的连通性。定图的连通性。function ncV=arComp(E,n)%功功能能是是确确定定图图的的互互不不连连通通的的分分枝枝数数目目。输输入入参参数数E是是图图的的边边集集，它它使使m行行2列列矩矩阵阵，每每一一行行的的两两个个数数字字代代表表一一条条边边的的两两个个顶顶点点，共共有有m条条边边，n是是图图的的顶顶点点数数，该该参参数数不不是是必必须须的的，可可以以省省略略
83、，此此时时默默认认n=max(max(E)，但但是是，假假如如最最末末尾尾的的顶顶点是孤立的点，则该参数不能省略。点是孤立的点，则该参数不能省略。%输输出出参参数数ncV是是n行行1列列向向量量，每每个个数数字字代代表表相相应应顶顶点点的的互互不不连连通通的的分分枝枝数数目目，由由ncV可可以以判判断断图图的的连连通通性性，若若max(ncV)1，则则图图有有2个个以以上上互互不不连连通的分枝。通的分枝。m,n1,E1 = arValidation(E); % 验验证证数数据据的的有有效性效性E2=E1(:,1:2);E1(:,2 1); % E2的的行行数数是是E1的的两两倍倍，新新增增加加
84、的的行行由由原原来来各各边边的的两两个个顶顶点点交交换换次次序得到序得到Dec,Ord=arDecOrd(E2); % 对对有有向向图图E2进进行行分解分解ncV=sum(Dec*diag(1:size(Dec,2),2); % 互互不不相连的分枝数相连的分枝数if (nargin1)&(nn1), % 最后的孤立顶点最后的孤立顶点 ncV=ncV;1:n-n1+max(ncV);endreturn在在 程程 序序 arComp中中 ， 通通 过过 调调 用用 函函 数数arValidation(E)来确任数组来确任数组E的有效性。的有效性。function m,n,newE = arVali
85、dation(E);%输输入入参参数数E与与前前面面相相同同，输输出出参参数数m是是图图的的边边数数，n1是是图图的的顶顶点点数数，数数组组newE的的第第一一和和第第二二列列等同于输入数据等同于输入数据E，第三列是各边的权重。，第三列是各边的权重。 se=size(E); % se是数组是数组E的大小（行数和列数）的大小（行数和列数）m=se(1);if se(2)0);for k=1:n, Ak=(Ak*A0); As=As|Ak;endA=As;T,ir,jc=unique(A.*A,rows);Dec=T;Ord=A(ir,ir);ns=size(Ord,1);for it=1:ns*
86、(ns-1)/2 Mlow=tril(Ord,-1); is,js,Mw=find(Mlow); if isempty(is) break; end num=1:ns; num(is(1)=js(1); num(js(1)=is(1); Ord=Ord(num,num); Dec=Dec(:,num);endreturn例例1 求下图中的一条欧拉巡回。求下图中的一条欧拉巡回。解解：该该图图有有9个个顶顶点点、14条条边边，各各顶顶点点的的度度数数均为偶数，是一个欧拉图。在均为偶数，是一个欧拉图。在Matlab中输入中输入E=1,2;2,3;1,4;2,4;2,5;3,6;4,5;4,7;5,8
87、;5,6;6,9;6,8;7,8;8,9;%E代代表表图图的的边边集集，它它有有14行行2列列，每每一一行行是是连连接接一一条条边边的的两两个个顶顶点点，各各边边的的编编号号从从1到到14依依次次排列。排列。运行运行eu,cEu=arEuler(E);结果为结果为eu=1（说明该图是欧拉图）。（说明该图是欧拉图）。cEu = 1 2 6 10 5 4 7 9 12 11 14 13 8 3它它代代表表一一条条欧欧拉拉巡巡回回依依次次经经过过的的边边的的序序列列，它它 所所 经经 过过 的的 顶顶 点点 序序 列列 依依 次次 为为123652458698741。注注：一一般般说说来来，一一个个
88、欧欧拉拉图图中中的的欧欧拉拉巡巡回回不不止止一一条条（各各条条巡巡回回的的总总路路程程相相等等），本本程程序序的的结果给出其中的一条结果给出其中的一条 三、中国邮递员问题的求解实例三、中国邮递员问题的求解实例 前前面面已已经经讲讲过过，对对于于欧欧拉拉图图，可可以以直直接接用用Fleury算算法法找找出出一一条条欧欧拉拉巡巡回回路路线线；对对于于半半欧欧拉拉图图，可可以以先先求求出出奇奇点点u和和v之之间间的的最最短短路路径径P，令令G*=GP，则则G *为为欧欧拉拉图图，然然后后用用Fleury算算法法来来确确定定一一个个G *的的欧欧拉拉巡巡回回，它它就就是是原原图图G的的最优巡回。最优巡
89、回。当当G有有2n个个奇奇点点（n1），可可以以用用Edmonds算算法解决，步骤如下：法解决，步骤如下：(1) 用用Floyd算算法法求求出出所所有有奇奇点点之之间间的的最最短短路路径和距离矩阵。径和距离矩阵。(2) 用用匈匈牙牙利利法法或或0-1规规划划法法求求出出所所有有奇奇点点之之间的最佳配对。间的最佳配对。(3) 在在原原图图上上添添加加最最佳佳配配对对所所包包含含的的两两两两顶顶点之间的最短路得到欧拉图点之间的最短路得到欧拉图G *。(4) 用用Fleury算算法法确确定定一一个个G *的的欧欧拉拉巡巡回回，这就是这就是G的最优巡回。的最优巡回。以以上上步步骤骤的的关关键键是是找找
90、出出2n个个奇奇点点的的最最佳佳配配对对，举例如下。举例如下。例例2 下下图图是是某某区区街街道道示示意意图图，各各边边的的长长度度数数据据见见下下表表。现现在在需需要要对对每每条条街街道道都都巡巡视视到到（至至少走一次），求一条总路程最短的巡回路线。少走一次），求一条总路程最短的巡回路线。边长边长数据数据解解：该该图图有有42个个顶顶点点和和62条条边边，有有26个个顶顶点点为为奇奇点点，因因而而它它不不是是欧欧拉拉图图，为为了了寻寻找找最最优优巡巡回，需要先求回，需要先求26个奇点的最佳配对。个奇点的最佳配对。先先用用Floyd算算法法求求出出所所有有42个个顶顶点点之之间间的的最最短短路
91、距离和路径。程序如下路距离和路径。程序如下：E=1 2 10261 4 402 注注：每每一一行行代代表表一一条条边边（两两个个顶顶点和边长），此处省略点和边长），此处省略59行行40 39 198;for i=1:42 for j=1:42 if j=i a(i,j)=0; else a(i,j)=inf; end endendfor k=1:62 i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)=E(k,3);endD,R=floyd(a);然然后后求求26个个奇奇点点的的最最优优配配对对，这这可可以以用用Lingo求解，编写程序如下：求解，编写程序如下：MOD
92、EL:SETS:dot/2,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20,22,24,25,26,28,29,30,36,40,41/; LINKS(dot,dot)| &2 # GT # &1:C,X; ENDSETSDATA: C=1319 1065 651 650 939 1228 1463 1500 1213 617 895 1590 1709 1377 1033 1112 1652 1761 1853 1418 1832 2124 2151 2479 1687254 668 1173 1462 1751 198 181 402 1140 1418 2
93、113 453 601 945 1635 2175 2284 597 1941 2355 868 1463 1498 2104414 919 1208 1497 1732 435 148 886 1164 1859 679 347 691 1381 1921 2030 823 1687 2101 1094 1689 1724 1850505 794 1083 1318 849 562 472 750 1445 1058 726 382 967 1507 1616 1202 1273 1687 1473 2005 2103 1541289 578 813 1354 1067 471 245 94
94、0 1563 1231 887 462 1002 1111 1707 768 1182 1978 2005 2333 1541289 524 1643 1356 760 534 651 1852 1520 1176 504 828 886 1996 594 1008 2267 2197 2525 1733235 1932 1645 1049 823 362 2141 1809 1465 793 706 597 2285 883 890 2556 2486 2814 20222167 1880 1284 1058 163 2376 2044 1700 1028 507 398 2520 1105
95、 691 2766 2658 2986 2194306 1321 1599 2294 272 505 849 1571 2111 2220 416 1877 2291 687 1282 1317 20081034 1312 2007 531 199 543 1265 1805 1914 675 1571 1985 946 1541 1576 1702360 1411 1203 871 527 577 1117 1226 1347 883 1297 1618 1534 1862 10701101 1563 1231 887 217 757 866 1707 523 937 1978 1894 2
96、222 14302282 1950 1606 884 344 235 2426 942 528 2603 2495 2823 2031332 676 1398 1938 2047 144 1704 2118 415 1010 1045 1824344 1066 1606 1715 476 1372 1786 747 1342 1377 1503722 1262 1371 820 1028 1442 1091 1623 1721 1159540 649 1542 306 720 1813 1729 2057 1265109 2082 598 184 2259 2151 2479 16872191
97、 707 293 2368 2260 2588 17961848 2262 271 866 901 1680414 1711 1603 1931 11392075 1967 2295 1503595 630 1409360 832792;ENDDATA MIN=SUM(LINKS:C*X); FOR(LINKS:BIN(X); FOR(dot(I):SUM(LINKS(J,K)| J #EQ# I #OR# K #EQ# I:X(J,K)=1); END运行以上程序，得到最优配对结果为：运行以上程序，得到最优配对结果为：2与与6、4与与12、5与与13、8与与9、10与与11、14与与15、1
98、7与与25、18与与26、19与与20、22与与28、24与与29、30与与36、40与与41。在在原原图图62条条边边的的基基础础上上增增加加13条条边边，得得到到如如图图所所示示的的图图形形，它它有有42个个顶顶点点和和75条条边边，是是欧欧拉图。拉图。对对该该图图运运行行运运行行eu,cEu=arEuler(E)，其其中中输输入入参参数数E是是75行行2列列矩矩阵阵（代代表表75条条边边），得得到到一一条条欧欧拉拉巡巡回回如如图图所所示示，总总里里程为程为25983 该该 巡巡 回回 路路 线线 所所 经经 过过 的的 顶顶 点点 序序 列列 为为 ：12311109872（经经过过7）
99、 654121351319206714158923242517111016172542413732211415222328292429343328(经经 过过23)222120191826273130394041403536313233383736（经过（经过31）3026181241。6 最大流问题一、问题的描述一、问题的描述设设有有一一批批物物资资，要要从从A市市通通过过公公路路网网络络（内内含含一一些些中中转转站站）运运往往B市市，已已知知每每段段公公路路的的运运输输能能力力有有限限制制（流流量量限限制制），问问应应如如何何安安排排运运输输方方案案，才才能能使使总总运运量量最最大大？这这
100、就就是是网网络络最最大大流流问题问题假假设设有有一一个个有有向向网网络络，对对应应每每一一条条弧弧(vi,vj)有有一一个个非非负负的的权权Cij，表表示示该该弧弧的的容容量量（流流量量限限制制）图图中中有有两两个个特特殊殊顶顶点点：一一个个称称为为发发点点,又又称称源源，记记为为s，它它只只有有出出弧弧而而没没有有入入弧弧，即即只只有有流流出出而而没没有有流流进进；另另一一个个称称为为收收点点,又又称称汇汇，记记为为t，它它只只有有入入弧弧而而没没有有出出弧弧，即即只只有有流流进进而而没没有流出有流出定定义义实实值值函函数数f，该该函函数数对对应应各各弧弧的的取取值值为为f(i,j)，表表示
101、示流流过过弧弧i j的的流流量量，假假设设f满满足足以以下下三三个个条条件：件：(1) 对每条弧，流量不超过弧的容量，即对每条弧，流量不超过弧的容量，即称为流量限制；称为流量限制；(2) 发点发点 s 流出的总量等于收点流出的总量等于收点 t 流进的总量；流进的总量；(3) 对对于于除除了了发发点点和和收收点点之之外外的的其其他他任任意意中中间间点点，流流入入该该点点的的总总量量等等于于流流出出该该点点的的总总量量，称称为为流量守恒规则流量守恒规则称函数称函数f为流函数，简称流（可行流）。为流函数，简称流（可行流）。 令令如如果果fv达达到到了了最最大大，则则称称它它是是运运输输网网络络的的最
102、最大流大流实实例例：下下图图是是从从发发货货地地到到目目的的地地的的有有向向运运输输网网络络，称称点点为为发发点点（源源），点点为为收收点点（汇汇），有有向向边边（弧弧）旁旁边边的的数数字字是是该该弧弧的的流流量（运输能力）限制，求量（运输能力）限制，求的最大流的最大流 一个运输网络图一个运输网络图 二、数学模型二、数学模型 对对每每一一条条弧弧(顶顶点点i到到j)，定定义义f(i,j)为为该该弧弧上上从从顶顶点点i到到顶顶点点j的的流流量量，用用Cij表表示示其其上上的的流流量量限限制制则则对对任任意意一一个个中中转转点点，流流进进与与流流出出相相等等，但但顶顶点点只只有有流流出出，顶顶点点
103、只只有有流流进进，并并且且两两者者大大小小相相等等(方方向向相相反反)，如如果果我我们们在在图图上上虚虚拟拟一一条条从从的的弧弧，其其流流量量不不受受限限制制，并并假假设设从从流流到到的的总总量量又又从从该该虚虚拟拟弧弧上上返返回回，整整个个网网络络系系统统构构成成一一个个封封闭闭的的不不停停流流动动的的回回路路，则对任意顶点都满足流进等于流出则对任意顶点都满足流进等于流出 目目标标函函数数是是max f(n,1)，n是是收收点点，1是是发发点点.约束条件有两条：约束条件有两条：(1)对每个顶点，流进等于流出，即对每个顶点，流进等于流出，即等等式式左左边边的的求求和和是是对对所所有有以以顶顶点
104、点i为为终终点点的的边边进进行行，右右边边的的求求和和是是对对所所有有以以顶顶点点i为为起起点点的的边边进行进行(2)对每条弧，流量不超过其限制值，即对每条弧，流量不超过其限制值，即 完整的模型为：完整的模型为：编写编写LINGO程序如下：程序如下：MODEL: SETS: CHSH/1.6/;LINKS(CHSH,CHSH)/1,2 1,3 2,4 2,5 3,4 3,5 4,6 5,6 6,1/:C,F;!该集合列出有弧相连的顶点对，与每一条弧一该集合列出有弧相连的顶点对，与每一条弧一一对应，一对应，6,1是虚拟弧是虚拟弧; ENDSETS DATA:C=16,20,10,10,6,6,1
105、0,16,1000;!虚拟弧上的流量不受限制虚拟弧上的流量不受限制(很大的数很大的数); ENDDATA MAX=F(6,1); !目标函数目标函数; FOR(LINKS(I,J):F(I,J)=C(I,J); !流流量量限限制制;FOR(CHSH(I):SUM(LINKS(J,I):F(J,I)=SUM(LINKS(I,J):F(I,J); !每个顶点的流进等于流出每个顶点的流进等于流出;END求解得到结果，最大流为求解得到结果，最大流为26，运输方案，运输方案: 弧1-2 1-3 2-4 2-5 3-4 3-5 4-6 5-6 虚拟弧6-1流量141241066101626三、最小费用最大
106、流三、最小费用最大流 前前面面介介绍绍了了网网络络最最大大流流问问题题及及其其求求解解方方法法，它它不不涉涉及及费费用用问问题题，有有时时在在实实际际问问题题中中，网网络络中中各各条条弧弧(边边)上上的的运运输输费费用用(单单价价)不不相相同同，因因而而在在满满足足最最大大流流的的情情况况下下(运运输输方方案案不不唯唯一一)，要要求求费费用用最最小小的的最最大大流流，称称为为最最小小费费用用最最大大流流问问题题下面看一个具体实例下面看一个具体实例 例例：图图示示网网络络的的每每一一条条弧弧上上括括号号内内有有两两个个数数字字，前前一一个个数数字字代代表表该该弧弧上上的的最最大大流流量量，后后一
107、一个个数数字字是是单单位位运运费费用用uij表表示示弧弧(i,j)上上的最大流量，用的最大流量，用cij表示运输单价。表示运输单价。 351246先先用用求求最最大大流流的的方方法法求求出出该该网网络络从从顶顶点点1到到顶点顶点6的最大流为的最大流为14，运输方案如下表所示：，运输方案如下表所示：最最小小费费用用是是在在满满足足最最大大流流情情况况下下找找出出费费用用最最小小的的运运输输方方案案，故故下下一一步步是是把把求求出出的的最最大大流流作作为为约约束束条条件件，即即把把f(6,1)=14作作为为约约束束条条件件，目目标函数改成标函数改成弧1-2 1-3 2-3 2-4 3-5 4-3
108、4-6 5-4 5-66-1流量77259050914编写编写LINGO程序如下：程序如下：MODEL: SETS: CHSH/1.6/; LINKS(CHSH,CHSH)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,4 5,6 6,1/:C,U,F; !6,1 是是虚虚拟拟弧弧，U为为流流量量限限制制，C为为费费用用，F为为实际流量实际流量; ENDSETS DATA: U=8,7,5,9,9,2,5,6,10,15; C=2,8,5,2,3,1,6,4,7,8 ; ENDDATA N=SIZE(CHSH); F(6,1)=14; !把上一步求出的最大流作为约束条把上一步求出
109、的最大流作为约束条件件; MIN=SUM(LINKS(I,J)|I#LT#N:C(I,J)*F(I,J); FOR(LINKS(I,J):F(I,J)=U(I,J); FOR(CHSH(I):SUM(LINKS(J,I):F(J,I)=SUM(LINKS(I,J):F(I,J);END运运行行该该程程序序，得得到到最最小小费费用用为为205，最最小小费费用用下的最大流运输方案如下表所示下的最大流运输方案如下表所示注注：满满足足最最大大流流时时的的运运输输方方案案可可以以有有多多种种，表中所列方案是费用最小的方案。表中所列方案是费用最小的方案。 弧1-21-32-32-43-54-34-65-45-6虚拟弧6-1流量86179250914
