第11章-图与网络

Chapter11：

图与网络模型图与网络模型11.1图与网络的根本概念11.2最短路问题11.3最小生成树问题11.4最大流问题11.5最小费用最大流问题近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥〞难题。Euler1736年证明了不可能存在这样的路线。11.1图的根本概念与模型Königsberg桥对应的图11.1图与网络的根本概念图论：图是由点和边构成，可以反映一些对象之间的关系※

图G区别于几何学中的图。这里只关心图中有多少个点、以及哪些点之间有连线。例如：在一个人群中，对相互认识这个关系我们可以用图来表示一般情况下，图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e511.1图与网络的根本概念图论：图是由点和边构成，可以反映一些对象之间的关系。一般情况以下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义： 假设用点表示研究的对象，用边表示这些对象之间的联系，那么图G可以定义为“点〞和“边〞的集合，记作：其中:V——点集E——边集※

图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。无向图定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端点，关联边，相邻假设有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。假设点vi、vj与同一条边关联，称点vi和vj相邻；假设边ei和ej具有公共的端点，称边ei和ej相邻。11.1图与网络的根本概念如果边e的两个端点相重，称该边为环如右图中边e1为环如果两个点之间多于一条边，称为多重边，如右图中的e4和e5对无环、无多重边的图称作简单图v3e7e4e8e5e6e1e2e3v1v2v4v5

环，多重边，简单图11.1图与网络的根本概念与某一个点vi相关联的边的数目称为点vi的次〔也叫做度〕，记作d(vi)右图中d(v1)＝4，d(v3)=5，d(v5)=1次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:

一个图的次等于各点的次之和。

次，奇点，偶点，孤立点11.1图与网络的根本概念图中某些点和边的交替序列，假设其中各边互不相同，且对任意vt-1和vt均相邻，称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈〔回路〕如果任意两个顶点之间至少存在一条链，称这样的图为连通图11.1图与网络的根本概念链，圈〔回路〕，连通图图的根本概念与模型二部图〔偶图〕图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图改画为(c)时清楚看出。如果我们把上面例子中的“相互认识〞关系改为“认识〞的关系，那么只用两点之间的连线就很难刻画他们之间的关系了，这时我们引入一个带箭头的连线，称为弧。相互认识用两条反向的弧表示。11.1图与网络的根本概念有向图的定义： 图D被定义为“点〞和“弧〞的集合，记作：其中:V——点集；A——弧集a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈无向图G＝(V,E)，对G的每一条边(vi,vj)相应赋予数量指标wij，称wij为边(vi,vj)上的权，称图G为赋权图赋权的有向图D=(V,A)，指定一点为发点〔vs〕，指定另一点为收点〔vt〕，称其它点为中间点，并把D中每一条弧的赋权数cij称为弧(vi,vj)的容量，这样的赋权有向图D就称为网络①②③④⑤⑥910201571419256

赋权图，网络11.1图与网络的根本概念权可以代表距离、费用、通过能力(容量)等等图的根本概念与模型

出次与入次

有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi的入次，用表示d-(vi)；vi点的出次和入次之和就是该点的次。※有向图中，所有顶点的入次之和等于所有顶点的出次之和。图的根本概念与模型图的模型应用例11.1有甲,乙,丙,丁,戊,己6名运发动报名参加A,B,C,D,E,F6个工程的比赛。下表中打√的是各运发动报告参加的比赛工程。问6个工程的比赛顺序应如何安排，做到每名运发动都不连续地参加两项比赛。ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√图的根本概念与模型解：用图来建模。把比赛工程作为研究对象，用点表示。如果2个工程有同一名运发动参加，在代表这两个工程的点之间连一条线，可得以下图。ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A图的根本概念与模型 一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一局部人同时选修D、C、A，一局部人同时选修B、C、F，一局部人同时选修B、E，还有一局部人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。思考题图的根本概念与模型AFEDCB图的根本概念与模型AFEDCB图的根本概念与模型思考题解答：

以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，如C—E—A—F—D—B，就是一个符合要求的考试课程表。11.2最短路问题

有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题对一个赋权的图〔G或D〕中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧〔边〕的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路Dijkstra算法(双标号法〕最短路问题求最短路有两种算法:

狄克斯屈拉(Dijkstra)标号算法

逐次逼近算法假设序列{vs,v1…..vn-1,vn}是从vs到vt间的最短路，那么序列{vs,v1…..vn-1}必为从vs到vn-1的最短路。 假定v1→v2→v3→v4是v1→v4的最短路，那么v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v511.2最短路问题Dijkstra标号算法的根本思路(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v41.给出点Vs以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J，以及弧的集合3.如果B是空集，那么计算结束。①如果Vt已标号(Lt,Kt)，那么Vs到Vt的距离为Lt，而从Vs到Vt的最短路径，那么可以从Vt反向追踪到起点Vs〔根据Kt的记录〕而得到。②如果Vt未标号，那么可以断言不存在从Vs到Vt的路。11.2最短路问题Dijkstra双标号法的步骤：如果上述的弧(B)的集合不是空集，那么转下一步。4.对B中的每一条弧，计算Sij=Li+Cij。在所有的Sij中，找到其值为最小的弧。不妨设此弧为〔Vc,Vd〕，那么给此弧的终点以双标号〔Scd,c〕，返回步骤2。11.2最短路问题Dijkstra双标号法的步骤：例1.求以下图中v1到v6的最短路11.2最短路问题Dijkstra双标号法：v23527531512v1v6v5v3v4v23527531512v1v6v5v3v4〔0，s〕0+30+20+5〔2，1〕2+1〔3，1〕(3,3)3+73+5(8,4)v1到v6的最短距离为8；最短路为：v1→v3

→v4

→v6最短路问题求网络图的最短路，设图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为(i,j)

距离为dijP标号(点标号)：b(j)—起点vs到点vj的最短路长；T标号(边标号)：k(i,j)=b(i)+dij，步骤：1.令起点的标号；b(s)＝0。2.找出所有vi已标号vj未标号的弧集合B={(i,j)}如果这样的弧不存在或vt已标号那么计算结束；3.计算集合B中弧k(i，j)=b(i)+dij的标号4.选一个点标号在终点vl处标号b(l),返回到第2步。例2.求以下图v1到v7的最短路线①②③④⑤⑥⑦862523534210570862254411147510711v7已标号，计算结束。从v1到v7的最短路长是11,最短路线：v1→v4→v6

→v7P标号T标号11.2最短路问题12从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj

。注：无向图最短路的求法只将上述步骤中的弧改成边即可。11.2最短路问题例3.求以下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1

到该点的最短距离，最短路线就是红色的链。11.2最短路问题1.求从v1到v8的最短路径23718456613410527593468211.2最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路径为v1→v4→v7→v5→v8，最短距离为1011.2最短路问题2.求以下图中v1点到另外任意一点的最短路径v1v2v3v4v6v532276213311.2最短路问题v1V2V3V4V6V532276213302471411.2最短路问题例4.电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？以下图给出了甲乙两地间的交通图。权数表示两地间公路的长度〔单位：公里〕。v1（甲地）1517624431065v2v7(乙地)v3v4v5v611.2最短路问题解：这是一个求无向图的最短路的问题。v1（甲地）1517624431065v2v7(乙地)v3v4v5v611.2最短路问题(0,s)(10,1)(13,3)(14,3)(16,5)(18,5)(22,6)甲地到乙地的最短路为：例5.设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购置新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的方案，使得五年内购置费用和维修费用总的支付费用最小。〔P237E3.zdl〕设备每年年初的价格表年份12345年初价格111112121311.2最短路问题设备维修费如下表使用年数0-11-22-33-44-5每年维修费用5681118解：将问题转化为最短路问题，如以下图：用vi表示“第i年年初购进一台新设备〞,弧〔vi,vj〕表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v611.2最短路问题把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v616223041591622304131231718172311.2最短路问题年份12345年初价1111121213使用年数0-11-22-33-44-5每年维修费5681118最终得到以下图，可知，v1到v6的距离是53，最短路径有两条：v1→v3→v6和v1→v4→v6V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)11.2最短路问题树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。乒乓球单打比赛抽签后，可用图来表示相遇情况，如以下图所示。ABCDEFGH运发动11.3最小生成树问题某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科11.3最小生成树问题性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6

树：无圈的连通图即为树11.3最小生成树问题11.3最小生成树问题图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)以下图中，哪些是树？图G1={V1、E1}和图G2={V2，E2}，如果有，称G1是G2的一个子图假设有，那么称G1是G2的一个支撑子图v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5(a)v3e7e4e8e6e2e3v1v2v4v5(b)〔G图〕

子图，支撑子图11.3最小生成树问题如果G2是G1的支撑图〔生成图〕，又是树图，那么称G2是G1的生成树〔或支撑树〕。v1v2v3v4v5v1v2v3v4v5G1G211.3最小生成树问题图的生成树〔支撑树〕abcfedhgbfed11.3最小生成树问题图的生成树〔支撑树〕abcfedhgbfdg11.3最小生成树问题图的生成树〔支撑树〕bcedabcfedhg11.3最小生成树问题图的生成树〔支撑树〕abchabcfedhg11.3最小生成树问题图的生成树〔支撑树〕afdgabcfedhg11.3最小生成树问题图的生成树〔支撑树〕破圈法11.3最小生成树问题

求支撑树的方法：破圈法和避圈法生成树〔支撑树〕

求支撑树的方法：破圈法和避圈法11.3最小生成树问题v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5

求支撑树的方法：破圈法和避圈法11.3最小生成树问题避圈法最小生成树问题：在一个赋权的、连通的、无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小11.3最小生成树问题图的最小生成树〔支撑树〕1.在给定的赋权的连通图上任找一个圈2.在所找的圈中去掉一个权数最大的边〔如果有两条或两条以上的边都是权数最大的边，那么任意去掉其中一条〕。3、如果所余下的图已不包含圈，那么计算结束，所余下的图即为最小生成树，否那么返回第1步。求解最小生成树的破圈算法v1v2v4v5v6435215878破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v3边数＝n-1=511.3最小生成树问题图的最小生成树〔支撑树〕6v1v2v3v4v5v643521MinC(T)=1511.3最小生成树问题图的最小生成树〔支撑树〕树与图的最小树避圈法: 去掉G中所有边，得到n个孤立点；然后加边。加边的原那么为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15v1v7v4v3v2v5v620159162532817412336练习：应用破圈法求最小树11.3最小生成树问题v1v7v4v3v2v5v62015916253281741233611.3最小生成树问题v1v7v4v3v2v5v620159162532817412311.3最小生成树问题v1v7v4v3v2v5v620159162532817412311.3最小生成树问题v1v7v4v3v2v5v6159162532817412311.3最小生成树问题v1v7v4v3v2v5v6159162532817412311.3最小生成树问题v1v7v4v3v2v5v69162532817412311.3最小生成树问题v1v7v4v3v2v5v69162532817412311.3最小生成树问题v1v7v4v3v2v5v692532817412311.3最小生成树问题v1v7v4v3v2v5v692532817412311.3最小生成树问题v1v7v4v3v2v5v6932817412311.3最小生成树问题v1v7v4v3v2v5v6932817412311.3最小生成树问题v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=5711.3最小生成树问题树与图的最小树练习：应用避圈法求最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57课堂练习：3749346321MinC(T)=12MinC(T)=15254173314475答案：11.3最小生成树问题34122323242MinC(T)=12213638534567454321MinC(T)=1811.3最小生成树问题例6.用破圈算法求图〔a〕中的一个最小生成树11.3最小生成树问题v1331728541034v7v6v5v4v2v3(a)7v6v5v4v2v3(b)v133725434v7v6v5v4v2v31(c)v13372434v7v6v5v4v2v31(d)v4v1337234v7v6v5v2v31(e)v133723v7v6v5v4v2v31(f)例7.某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如以下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短(P242E5.treemin)。11.3最小生成树问题v1331728541034v7v6v5v4v2v3图11-14

此问题实际上是求图11-14的最小生成树，这在例6中已经求得，即按照图(f)的设计，可使此网络的总的线路长度为最短，为19百米。网络的最大流如何制定一个运输方案使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。网络的最大流根本概念：1.容量网络：对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。s①②③④t4844122679网络的最大流2.网络的最大流

是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。假设fij=0，称为零流。满足以下条件的一组流称为可行流。

容量限制条件。容量网络上所有的弧满足：0≤fij≤cij

中间点平衡条件。假设以v(f)表示网络中从s→t的流量，那么有：网络的最大流结论：任何网络上一定存在可行流。〔零流即是可行流〕网络最大流问题： 指满足容量限制条件和中间点平衡的条件下，使v(f)值到达最大。v563522241263v1v2v7v4v3v6图11-2611.4最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型例8.某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一局部如以下图所示。由于管道的直径的变化，它的各段管道〔vi,vj〕的流量cij〔容量〕是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？(P243E6.maxflow)v563522241263v1v2v7v4v3v6图11-2611.4最大流问题

我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，那么有(P243E6.maxfpow)：一、最大流的数学模型11.4最大流问题

1、在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件：发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。2、对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我们把满足守恒条件及流量可行条件的一组网络流{fij}称之为可行流，〔即线性规划的可行解〕，可行流中一组流量最大〔也即发出点总流出量最大〕的称之为最大流〔即线性规划的最优解〕。11.4最大流问题一、最大流的数学模型二、最大流问题的网络图论解法对网络上弧的容量的表示作改进。对一条弧〔vi,vj)的容量我们用一对数cij,0标在弧〔vi,vj)上，cij靠近vi点，0靠近vj点，表示从vi到vj容许通过的容量为cij，而从vj到vi容许通过的容量为0，这样我们可以省去弧的方向了。如以下图:(a)和(b)、(c)和(d)的意义相同。vivjcij0（b）vivj（a）cijcijvivj（cji）（c）vivjcijcji（d）11.4最大流问题63522241263v1v2v5v7v4v3v60000000000011.4最大流问题二、最大流问题的网络图论解法用以上方法对例8的图的容量标号作改进，得以下图：〔1〕找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，那么已经求得最大流。〔2〕找出这条路上各条弧的最小的顺流的容量pf，从而通过这条路增加网络的流量pf。〔3〕在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤〔1〕。****为了使算法更快捷有效，我们一般在步骤〔1〕中尽量选择包含弧数最少的路。11.4最大流问题二、最大流问题的网络图论解法根本算法步骤：①第一次迭代：选择路为v1→v4→v7。弧〔v4,v7〕的顺流容量为2，决定了pf=2，改进的网络流量图如以下图：63522241263v1v2v5v7v4v3v60000000000042022第一次迭代后的总流量211.4最大流问题二、最大流问题的网络图论解法用此方法对例8求解：②第二次迭代：选择路为v1→v2→v5→v7。弧〔v2,v5〕的顺流容量为3，决定了pf=3，改进的网络流量图如以下图：635222413v1v2v5v7v4v3v6000000004202203330355第二次迭代后的总流量11.4最大流问题二、最大流问题的网络图论解法③第三次迭代：选择路为v1→v4→v6→v7。弧〔v4,v6〕的顺流容量为1，决定了pf=1，改进的网络流量图如以下图：222413v1v2v5v7v4v3v600000042022033333013166第三次迭代后的总流量11.4最大流问题二、最大流问题的网络图论解法④第四次迭代：选择路为v1→v4→v3→v6→v7。弧〔v3,v6〕的顺流容量为2，决定了pf=2，改进的网络流量图如以下图：22233v1v2v5v7v4v3v611000203203335031200213388第四次迭代后的总流量111.4最大流问题二、最大流问题的网络图论解法⑤第五次迭代：选择路为v1→v2→v3→v5→v7。弧〔v2,v3〕的顺流容量为2，决定了pf=2，改进的网络流量图如以下图：22v1v2v5v7v4v3v6101202033350120213315002020510第五次迭代后的总流量1011.4最大流问题二、最大流问题的网络图论解法经过第五次迭代后在图中已经找不到从发点到收点的一条路——路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。最大流量图如以下图：22v1v2v5v7v4v3v612352235511.4最大流问题二、最大流问题的网络图论解法11.5最小费用最大流问题一个带收发点的网络，对每一条弧〔vi,vj〕，除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。(6,6)(3,4)(5,7)(2,5)(2,4)〔2,3〕(4,4)(1,3)(2,8)〔3,2〕v1v2v5v7v4v3v6(6,3)22v1v2v5v7v4v3v612352235511.5最小费用最大流问题

例8最大流问题可能有多种解法，如：12v1v2v5v7v4v3v6123632345解1解2一、最小费用最大流的数学模型例9.由于输油管道的长短不一，所以在例6中每段管道〔vi,vj〕除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如以下图所示。从采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量的最小费用(P249E7.mcmf)。11.5最小费用最大流问题(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)

第1步，建立最大流的数学模型：一、最小费用最大流的数学模型11.5最小费用最大流问题

一、最小费用最大流的数学模型11.5最小费用最大流问题

第2步，建立求最小费用的数学模型：一、最小费用最大流的数学模型一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定流量f的最小费用，这个给定流量f应小于等于最大流量F，否那么无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。11.5最小费用最大流问题二、最小费用最大流问题的网络图论解法对网络上弧〔vi,vj〕的〔cij,bij〕的表示作如下改动11.5最小费用最大流问题vivj（cij,bij）（0,-bij）（b）vivj（a）（cij,bij）（cij,bij）vivj（cji,bji）（c）（cij,bij）vivj（cji,bji）（0,-bij)（0,-bji)（d）11.5最小费用最大流问题二、最小费用最大流问题的网络图论解法用以上方法对例9的图形进行改进，得以下图：(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.5最小费用最大流问题二、最小费用最大流问题的网络图论解法最小费用最大流的根本算法：在对弧的标号作了改进的网络图上求最小费用最大流的根本算法，与求最大流的算法根本一样，不同的只是：****在步骤〔1〕中要选择一条总的单位费用最小的路，而不是包含边数最小的路。用上述方法对例9求解：①第一次迭代：找到最短路v1

→v4

→v6

→v7。第一次迭代后总流量为1，决定了pf=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第一次迭代后的总流量11.5最小费用最大流问题二、最小费用最大流问题的网络图论解法②第二次迭代：找到最短路v1

→v4

→v7。第二次迭代后总流量为3，总费用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-3033第二次迭代后的总流量11.5最小费用最大流问题