1、管管 理理 运运 筹筹 学学.1 2 2最短路问题最短路问题 例例 设备更新问题。某公司使用一台设备，在每年年初，公司就要设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。备的
2、计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表已知：设备每年年初的价格表 设备维修费如下表设备维修费如下表年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用5681118管管 理理 运运 筹筹 学学.2 2 2最短路问题最短路问题解：解： 将问题转化为最短路问题，如下图：将问题转化为最短路问题，如下图： 用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进年年初购进的设备一直使用到第的设备一直使用到第j年年初。年年初。把所有弧
3、的权数计算如下表：把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186管管 理理 运运 筹筹 学学.3 2 2最短路问题最短路问题 (继上页继上页) 把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。 最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条： v1 v3 v6和和 v1 v4 v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1) v5v622
4、30415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)管管 理理 运运 筹筹 学学.4 3 3最小生成树问题最小生成树问题 树是图论中的重要概念，所谓树就是一个无圈的连通图。树是图论中的重要概念，所谓树就是一个无圈的连通图。 图图11-11中，中，(a)就是一个树，而就是一个树，而(b)因为图中有圈所以就不因为图中有圈所以就不是树，是树， (c)因为不连通所以也不是树。因为不连通所以也不是树。图图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)管管
5、 理理 运运 筹筹 学学.5 3 3最小生成树问题最小生成树问题 给了一个无向图给了一个无向图G=(V,E)G=(V,E)，我们保留，我们保留G G的所有点，而删掉部分的所有点，而删掉部分G G的边或的边或者说保留一部分者说保留一部分G G的边，所获得的图的边，所获得的图G G，称之为，称之为G G的生成子图。在图的生成子图。在图11-1211-12中，中，(b)(b)和和(c)(c)都是都是(a)(a)的生成子图。的生成子图。 如果图如果图G G的一个生成子图还是一个树，则称这个生成子图为生成树，的一个生成子图还是一个树，则称这个生成子图为生成树，在图在图11-1211-12中，中，(c)(
6、c)就是就是(a)(a)的生成树。的生成树。 最小生成树问题就是指在一个赋权的连通的无向图最小生成树问题就是指在一个赋权的连通的无向图G G中找出一个生成中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。树，并使得这个生成树的所有边的权数之和为最小。图图11-12(a)(b)(c)管管 理理 运运 筹筹 学学.6 3 3最小生成树问题最小生成树问题一、求解最小生成树的破圈算法一、求解最小生成树的破圈算法算法的步骤：算法的步骤：1、在给定的赋权的连通图上任找一个圈。、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条、在所找的圈中去掉一个权数最大的
7、边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第为最小生成树，否则返回第1步。步。管管 理理 运运 筹筹 学学.7 3 3最小生成树问题最小生成树问题例例4 用破圈算法求图（用破圈算法求图（a）中的一个最小生成树）中的一个最小生成树v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v
8、6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图图11-13管管 理理 运运 筹筹 学学.8 3 3最小生成树问题最小生成树问题 例例5、某大学准备对其所属的、某大学准备对其所属的7个学院办公室计算机联网，这个网络的个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中可能联通的途径如下图，图中v1,v7 表示表示7个学院办公室，请设计一个学院办公室，请设计一个网络能联通个网络能联通7个学院办公室，并使总的线路长度为最短。个学院办公室，并使总的线路长度为最短。 解：此问题实际上是求图解：此问题实际
9、上是求图11-1411-14的最小生成树，这在例的最小生成树，这在例4 4中已经求得，中已经求得，也即按照图也即按照图11-1311-13的的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为1919百米。百米。 “管理运筹学软件管理运筹学软件”有专门的子程序可以解决最小生成树问题。有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图图11-14管管 理理 运运 筹筹 学学.9 4 4最大流问题最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，最大流问题：给一个带收发点的网络，其每条弧的赋权称
10、之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型一、最大流的数学模型 例例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（的变化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一样的。（容量）也是不一样的。cij的的单位为万加仑单位为万加仑/小时。如果使用这个网络系统从采地小时
11、。如果使用这个网络系统从采地 v1向销地向销地 v7运送石运送石油，问每小时能运送多少加仑石油？油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-26管管 理理 运运 筹筹 学学.10 4 4最大流问题最大流问题 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型： 设弧设弧(vi,vj)上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有：1412232514434647234335362535573646675767471214,1,2,6;1,2,70,1,2,6;1,2,712ijijijmax
12、F = fffffffffffffffffffffffffcijfij目标函数：约束条件：管管 理理 运运 筹筹 学学.11 4 4最大流问题最大流问题 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程表示个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧须等于总流出量。其后面几个约束条件表示对每一条弧(v(vi i,v,vj j) )的流量
13、的流量fij要满足流量的可行条件，应小于等于弧要满足流量的可行条件，应小于等于弧(v(vi i,v,vj j) )的容的容量量c cijij，并大于等于零，即，并大于等于零，即0 0f fijij c cijij。我们把满足守恒条件。我们把满足守恒条件及流量可行条件的一组网络流及流量可行条件的一组网络流 ffijij 称之为可行流，（即线性称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。出量最大）的称之为最大流（即线性规划的最优解）。 我们把例我们把例6 6的数据代入以
14、上线性规划模型，用的数据代入以上线性规划模型，用“管理运筹管理运筹学软件学软件”，马上得到以下的结果：，马上得到以下的结果：f f1212=5=5，f f1414=5=5，f f2323=2=2，f f2525=3=3，f f4343=2=2，f f4646=1=1，f f4747=2=2，f f3535=2=2，f f3636=2=2，f f5757=5=5，f f6767=3=3。最优值。最优值（最大流量）（最大流量）=10=10。管管 理理 运运 筹筹 学学.12 4 4最大流问题最大流问题二、最大流问题网络图论的解法二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的
15、方向，如下图对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和和(b)、(c)和和(d)的意义相同。的意义相同。 用以上方法对例用以上方法对例6的图的容量标号作改进，得下图的图的容量标号作改进，得下图vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000管管 理理 运运 筹筹 学学.13 4 4最大流问题最大流问题 求最大流的基本算法求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容）找出一条从发点到收点的路，在这条路上的每一条
16、弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络，通过这条路增加网络的流量的流量pf。（3）在这条路上，减少每一条弧的顺流容量）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流，同时增加这些弧的逆流容量容量pf，返回步骤（，返回步骤（1）。）。 用此方法对例用此方法对例6求解：求解： 第一次迭代：选择路为第一次迭代：选择路为v1 v4 v7 。弧（。弧（ v4 , v7 ）的顺流容量为）的顺流容量为2，决定了决定
17、了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图：63522241263v1v2v5v7v4v3v6000000000004202管管 理理 运运 筹筹 学学.14 4 4最大流问题最大流问题 第二次迭代：选择路为第二次迭代：选择路为v1 v2 v5 v7 。弧（。弧（ v2 , v5 ）的顺流容量为）的顺流容量为3，决定了，决定了pf=3，改进的网络流量图如下图：，改进的网络流量图如下图： 第三次迭代：选择路为第三次迭代：选择路为v1 v4 v6 v7 。弧（。弧（ v4 , v6 ）的顺流容量为）的顺流容量为1，决定了，决定了pf=1，改进的网络流量图如下图：，改进的网络流量图
18、如下图：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600000042022033333013管管 理理 运运 筹筹 学学.15 第四次迭代：选择路为第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（。弧（ v3 , v6 ）的顺流容）的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图： 第五次迭代：选择路为第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（。弧（ v2 , v3 ）的顺流容）的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改
19、进的网络流量图如下图：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205 4 4最大流问题最大流问题管管 理理 运运 筹筹 学学.16 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图：最大流量图如下图：22v1v2v5v7v4v3v6123522355 4 4最大流问题最大流
20、问题 “管理运筹学软件管理运筹学软件”中还有专门的子程序用于解决最大流问题。中还有专门的子程序用于解决最大流问题。管管 理理 运运 筹筹 学学.17 5 5最小费用最大流问题最小费用最大流问题 最小费用最大流问题：给了一个带收发点的网络，对每一条弧最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量），除了给出容量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij，要，要求一个最大流求一个最大流F，并使得总运送费用最小。，并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 由于输油管道的长短不一，所
21、以在例由于输油管道的长短不一，所以在例6中每段管道（中每段管道（ vi,vj ）除）除了有不同的流量限制了有不同的流量限制cij外，还有不同的单位流量的费用外，还有不同的单位流量的费用bij ，cij的单位为万的单位为万加仑加仑/小时，小时， bij的单位为百元的单位为百元/万加仑。如图。从采地万加仑。如图。从采地 v1向销地向销地 v7运送石运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。量和最小费用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（
22、3,2）v1v2v5v7v4v3v6(6,3)管管 理理 运运 筹筹 学学.18 5 5最小费用最大流问题最小费用最大流问题 这个最小费用最大流问题也是一个线性规划的问题。这个最小费用最大流问题也是一个线性规划的问题。 解：我们用线性规划来求解此题，可以分两步走。解：我们用线性规划来求解此题，可以分两步走。 第一步，先求出此网络图中的最大流量第一步，先求出此网络图中的最大流量F，这已在例，这已在例6中建中建立了线性规划的模型，通过管理运筹学软件已经获得结果。立了线性规划的模型，通过管理运筹学软件已经获得结果。 第二步，在最大流量第二步，在最大流量F的所有解中，找出一个最小费用的的所有解中，找出
23、一个最小费用的解，我们来建立第二步中的线性规划模型如下：解，我们来建立第二步中的线性规划模型如下： 仍然设弧（仍然设弧（vi,vj）上的流量为）上的流量为fij，这时已知网络中最大流量，这时已知网络中最大流量为为F，只要在例，只要在例6的约束条件上，再加上总流量必须等于的约束条件上，再加上总流量必须等于F的约的约束条件：束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用目标函数显然是求其流量的最小费用 。 由此得到线性规划模型如下：由此得到线性规划模型如下：(,)ijijijvvAfb管管 理理 运运 筹筹
24、学学.19 5 5最小费用最大流问题最小费用最大流问题 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;ijijijv vAijijfbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij管管 理理 运运 筹筹 学学.20 5 5最小费用最大流问题最小费用最大流问题 用管理运筹学软件，可求得如下结果：用管理运筹学软件，可求得如下结果：f f1212=4,f=
25、4,f1414=6,=6,f f2525=3,f=3,f2323=1,f=1,f4343=3,F=3,F5757=5,f=5,f3636=2,f=2,f4646=1,f=1,f4747=2,f=2,f6767=3,f=3,f3535=2=2。其最。其最优值优值( (最小费用最小费用)=145)=145。对照前面例。对照前面例6 6的结果，可对最小费用最的结果，可对最小费用最大流的概念有一个深刻的理解。大流的概念有一个深刻的理解。 如果我们把例如果我们把例7 7的问题改为：每小时运送的问题改为：每小时运送6 6万加仑的石油从万加仑的石油从采地采地v v1 1到销地到销地v v7 7最小费用是多少
26、？应怎样运送？这就变成了一最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧在给定了收点和发点并对每条弧(v(vi i,v,vj j) )赋权以容量赋权以容量c cijij及单位及单位费用费用b bijij的网络中，求一个给定值的网络中，求一个给定值f f的流量的最小费用，这个给的流量的最小费用，这个给定值定值f f的流量应小于等于最大流量的流量应小于等于最大流量F F，否则无解。求最小费用流，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的
27、约束的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量条件中的发点流量F F改为改为f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改为改为f f1212+f+f1414=f=6=f=6得到了最小费用流的线性规划的模型了。得到了最小费用流的线性规划的模型了。管管 理理 运运 筹筹 学学.21 5 5最小费用最大流问题最小费用最大流问题二、最小费用最大流的网络图论解法二、最小费用最大流的网络图论解法对网络上弧（对网络上弧（vi,vj）的（）的（cij,bij）的表示作如下改动，用）的表示作如下改动，用(b)来表示来表示(a)。用上述方法对
28、例用上述方法对例7中的图形进行改进，得图如下页：中的图形进行改进，得图如下页：vivjvivj（cij,bij ）（0,-bij ）（a）（b）（cij,bij ）（cij,bij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d）管管 理理 运运 筹筹 学学.22 5 5最小费用最大流问题最小费用最大流问题 求最小费用最大流的基本算法求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤
29、（最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。单位费用最小的路，而不是包含边数最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图图11-2811-28管管 理理 运运 筹筹 学学.23 5 5最小费用最大流问题最小费用最大流问题用上述方法对例用上述方法对例7求解：求解： 第一次迭代：找到
30、最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为第一次迭代后总流量为1，总，总费用费用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图图11-2911-29管管 理理 运运 筹筹 学学.24 5 5最小费用最大流问题最小费用最大流问题第二次迭代：找到最短路第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为第二次迭代后总流量为3，总费用
31、，总费用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图图11-3011-30管管 理理 运运 筹筹 学学.25 5 5最小费用最大流问题最小费用最大流问题第三次迭代：找到最短路第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后总流量为第三次迭代后总流量为5，总费用，总费用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(
32、0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）图图11-3111-31管管 理理 运运 筹筹 学学.26 5 5最小费用最大流问题最小费用最大流问题第四次迭代：找到最短路第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后总流量为第四次迭代后总流量为6，总费用，总费用72。(6,6)(3,4)(4,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(1,3)(6,-3)(2,-8
33、)(1,-3)（3,-2）(0,-6)(0,-4)(0,-5)（1,4）(1,-7)(3,-4)（2,-3）图图11-3211-32管管 理理 运运 筹筹 学学.27 5 5最小费用最大流问题最小费用最大流问题 第五次迭代：找到最短路第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后总流量为第五次迭代后总流量为9，总，总费用费用123。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,
34、-4)（2,-3）图图11-3311-33管管 理理 运运 筹筹 学学.28 5 5最小费用最大流问题最小费用最大流问题 第六次迭代：找到最短路第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后总流量为第六次迭代后总流量为10，总费用，总费用145。已经找不到从。已经找不到从v1到到v7的每条弧容量都大于零的路了，故的每条弧容量都大于零的路了，故已求得最小费用最大流了。已求得最小费用最大流了。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）
35、(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（2,-3）图图11-3411-34管管 理理 运运 筹筹 学学.29 5 5最小费用最大流问题最小费用最大流问题 如果对例如果对例7求一个最小费用流的问题：每小时运送求一个最小费用流的问题：每小时运送6万加仑石油从万加仑石油从v1到到v7的最小费用是多少，或者每小时运送的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代万加仑呢？我们可以从第四次迭代及图及图11-32即可得到运送即可得到运送6万加仑最小费用万加仑最小费用72百元，其运送方式通过比较图百元，其运送方式通过比较图11-28及图及图11-32即得图即
36、得图11-36所示。所示。 至于每小时运送至于每小时运送7万加仑，我们可以在图万加仑，我们可以在图11-36的基础上，再按第五次的基础上，再按第五次迭代所选的最短路运送迭代所选的最短路运送1万加仑即得最小费用：万加仑即得最小费用：72+1*17=89百元，其运送百元，其运送方式如图方式如图11-37所示。所示。35123126v1v2v5v4v3v610342v710第六次迭代第六次迭代后总流量后总流量图图11-35管管 理理 运运 筹筹 学学.30 5 5最小费用最大流问题最小费用最大流问题 123126v1v2v5v4v3v6631v7图图11-3612123126v1v2v5v4v3v6311v7图图11-37注：注：“管理运筹学软件管理运筹学软件”有专门有专门的子程序用于解决这类问题。的子程序用于解决这类问题。谢谢观看！
