运输问题课件

运输问题（TransportationProblem）

在线性规划问题中，有一类特殊类型的问题－－运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。第13章运输问题（TransportationProblem）13.1物资调配问题（MaterialTransferringProblem）13.1.1运输问题及数学模型（ModelforTransportation）13.1.2用表上作业法求解运输问题（SolveTransportationProblembyTable）13.1.3运输问题的进-步讨论（FurtherDiscussionaboutTransportationProblem）13.1.4应用问题举例（Parexample）13.2网络流问题（NetworkFlowProblem）13.2.1图的基本概念（ConceptoftheDagram）13.2.2最短路（ShortPath）13.2.3最大流问题（TheMaximumFlowProblem）13.2.4最小费用最大流问题（TheMinimumCostsandMaximumFlowProblem）13.1物资调配问题

在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。13.1物资调配问题13.1.1运输问题及数学模型

本章研究单一品种物资的运输调度问题。其典型情况是：设某种物品有个产地（或供方）Ai（i=1，2，…，m），各产地的产量分别是ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n）,各销地的销量分别为bj（j=1，2，…，n）。假定从Ai（i=1，2，…，m）产地向销地Bj（j=1，2，…，n）运输单位物品的运价是。问怎样调运这些物品才能使总运费最小?1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型

这是由多个产地供应多个销地的单品种物品运输问题。为直观起见，可列出该问题的运输表（见下页）。表中的变量Xij（i=1，2，…，m；j=1，2，…，n）为由产地Ai运往销地Bj的物品数量。cij为Ai到Bj的单位运价。有时，将单位运价单独列入另一个表中，并称其为运价表。1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型1.运输问题数学模型运输单价cij销售地Bi供应量B1B2…Bnai产地AiA1c11c12…c1na1A2c21c22

…c2na2┆┆┆…┆┆Amcm1cm2

…cmnam销售量bjb1b2…bn分布变量表A1x11x12…x1nA2x21x22

…x2n┆┆┆…┆Amxm1xm2

…xmn13.1物资调配问题13.1.1运输问题及数学模型1.运输问题数学模型

如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。13.1物资调配问题13.1.1运输问题及数学模型1.运输问题数学模型产销平衡运输问题的数学模型可表示如下：其中，约束条件右侧常数ai和bj满足13.1物资调配问题13.1.1运输问题及数学模型

在上页模型中，目标函数表示运输总费用极小化；前m个约束条件的意义是：由某一产地运往各个销地的物品数量之相等于该产他的产量；中间n个约束条件指：由各产地运往某一销他的物品数量之和等于该销地的销量。1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型

该模型属于线性规划问题。单纯形法是求解线性规划问题十分有效的一般方法。因而可用单纯形法求解上述运输问题。但是，当用线性规划的单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m＝3,n＝4这样简单的运输问题，变量数目也会达到19个之多(未考虑去掉一个多余约束条件)，因而需要寻求更简便的解法。1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型（1）运输问题有有限最优解2.运输问题数学模型的特点对前述运输问题，若令其变量

其中，，则xij就是前述述运输问题的一个可行解；另一方面，其目标函数有下界。目标函数值不会趋于-∞。由此可知，运输问题必存在有限最优解。13.1物资调配问题13.1.1运输问题及数学模型（2）运输问题约束条件的系数矩阵2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型即除第i个和第m+j个分量为l外，其它分量全等于0。（2）运输问题约束条件的系数矩阵其系数列向量的结构是：2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型

由此可知，运输问题具有下述特点：（1）约束条件系数矩阵的元素等于0或1。（2）约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。对产销平衡运输问题，除上述两个特点外，还有以下特点：所有结构约束条件都是等式约束，各产地产量之和等于各销地销量之和。2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型例1：三煤矿A1，A2，A3运往B1，B2，B3，B4三个城市销售，各煤矿的供应量和需求量如下页表，各城市的需求量其间的距离(或单位运价)cij如表下页表方格中的数据所示，试建立使总运输量(或总运费)最小的运输问题数学模型。2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型2.运输问题数学模型的特点单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020A2735820A3329440需求量bj30251015808013.1物资调配问题13.1.1运输问题及数学模型解：设Xij为第i煤矿向第j城市的供应量，cij表示为第i煤矿向第j城市供应煤的单位运价。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是产销平衡运输问题。则可写出其数学模型。2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型

根据运输问题的数学模型求出的运输问题的解X=(xij)，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bij。前已指出运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。3.运输问题的解13.1物资调配问题13.1.1运输问题及数学模型例1的一个基可行解：3.运输问题的解单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015

808013.1物资调配问题13.1.2用表上作业法求解运输问题

表上作业法是求解运输问题的一种简便而有效的方法，其求解工作在运输表上进行。表上作业法是一种迭代法，迭代步骤为：先按某种规则找出一个初始解(初始调运方案)；再对现行解作最优性判别；若这个解不是最优解，就在运输表上对它进行调整改进，得出一个新解；再判别，再改进；直至得到运输问题的最优解为止。如前所述，迭代过程得出的所有解都要求是运输问题的基可行解。13.1物资调配问题13.1.2用表上作业法求解运输问题步骤：（1）找出初始即可行解，即在产销平衡表上分配初始调运方案，保证xij≥0，，并且xij>0的格（又称实格）必须有m+n-1个；（2）求出各非基变量的检验数σij（空格检验数），σij≥0时停止计算；σij<0时在继续调整调运方案（换基迭代法）；（3）确定进基变量（空格换入变量）和出基变量（实格调出变量），找出新的基可行解（用空格闭回路法调整）；（4）重复第1-3步，直至获得σij≥0，输出xij*和minZ=Z*为止。13.1物资调配问题13.1.2用表上作业法求解运输问题1.给出运输问题的初始基可行解(初始调运方案)

结合例1详细说明表上作业法的解题步骤:

（1）画出运输问题的求解作业表（见例1），由于，可以转入（2）；（2）找出初始基可行解（又称分配初始调运方案）。确定初始调运方案的方法很多，下面介绍三种常用的方法。13.1物资调配问题13.1.2用表上作业法求解运输问题a.最小元素法容易直观想到，为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。即对所有i和j，找出ci0j0=min(cij)，并将xi0j0=min(ai0,bj0)的物品量由Ai0供应给Bj0；若xi0j0=ai0，则产地Ai0的可供物品己用完，以后不再继续考虑这个产地，且Bj0的需求量由bj0减少为bj0-ai0。如果xi0j0=bj0

，则销地bj0的需求已全部得到满足，以后不再考虑这个销地，且Ai0的可供量由ai0减少为ai0-bj0。1.给出运输问题的初始基可行解(初始调运方案)13.1物资调配问题13.1.2用表上作业法求解运输问题a.最小元素法然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务．故称为最小元素法。1.给出运输问题的初始基可行解(初始调运方案)13.1物资调配问题13.1.2用表上作业法求解运输问题1.给出运输问题的初始基可行解(初始调运方案)最小元素法分配的初始调运方案单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020x11=20A2735820x23=10x24=10A3329440x31=10x32=25x34=5需求量bj30251015

808013.1物资调配问题13.1.2用表上作业法求解运输问题1.给出运输问题的初始基可行解(初始调运方案)b.西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角(即左上角)上空格的供销需求。13.1物资调配问题13.1.2用表上作业法求解运输问题1.给出运输问题的初始基可行解(初始调运方案)西北角法分配初始调运方案单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015

808013.1物资调配问题13.1.2用表上作业法求解运输问题1.给出运输问题的初始基可行解(初始调运方案)c.沃格尔法使用最小元素法有时按某一最小单位运价优先安排调运时，可能导致不得不采用运费很高的其它供销点对，使整个运输费用增加。对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。沃格尔法分配初始调运方案单价cij销售地Bj供应量ai行罚数B1B2B3B412345供应A1162102011⑤00x11=10x13=10地AiA2735820224④x22=20A332944011111x31=20x32=5x34=15需求量bj30251015

列罚数1213④

221③0

32100

44100

5④200

13.1物资调配问题13.1.2用表上作业法求解运输问题1.给出运输问题的初始基可行解(初始调运方案)

对比以上3种方法的初始调运方案，可看出，伏格尔法优于其他方法，也就是说伏格尔法确定的初始解得目标函数距离最优解目标函数最近，因而迭代运算数为最少，效率高。方法西北角法最小元素法伏格尔法目标函数Z30025022013.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验

要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量(对应于运输表中的空格)的检验数，苦有某空格的检验数为负，说明将变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全非负，则不管样变换解均能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。a.闭回路法13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验

现结合例1中用最小元素法给出的初始解，说明检验数的计算方法。其中一条闭回路a.闭回路法检验数表

销售地供应地B1B2B3B4A1σ12=6σ13=3σ14=8A2σ21=0σ22=-–3*A3σ33=8因σ22=–3<0，故知该解不是最优解，还有待调整改正。13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验

闭回路可以是一个简单的矩形，也可以是由水平和竖直边线组成的其它更为复杂的封闭多边形.a.闭回路法13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验

用闭回路法判定一个运输方案是否为最优方案，需要找出所有空格的闭回路，并计算出其检验数。当运输问题的产地和销地很多时，空格的数目很大，计算检验数的工作十分繁重，而用对偶变量法(也称位势法)就要简便得多。b.对偶变量法13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验

对于前述产销平衡运输问题，若用u1,u2,…,um分别表示前m个约束等式相应的对偶变量，用v1,v2,…,vn分别表示后n个等式约束相应的对偶变量，即有对偶变量向量：b.对偶变量法13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验这时可将该运输问题的对偶规划写成：b.对偶变量法13.1物资调配问题13.1.2用表上作业法求解运输问题线性规划问题变量xj的检验数可表示为2.解的最优性检验b.对偶变量法

由此可写出运输问题某变量xij(对应于运输表中的(Ai,Bj)格)的检验数如下：13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验b.对偶变量法

现设我们已得到了该运输问题的一个基可行解，其基变量是由于基变量的检验数等于零．故对这组基变量可写出方程组13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验b.对偶变量法

若某组解满足对偶规划的所有约束条件，即对所有i和j均有即这组对偶变量(位势)对偶可行，则互补松弛条件Y(A-C)X=0成立，从而这时得到的解分别为原运输问题及其对偶问题的最优解。若解不满足约束条件，即非基变量的检验数有负值存在，则上面得到的运输问题的解不是最优解，需要进行解的调整。13.1物资调配问题13.1.2用表上作业法求解运输问题用位势法对前述给出的运输问题的解作最优性检验。2.解的最优性检验位势计算结果ui

viv1=(0)v2=–1v3=–2v4=1供应量aiu1=11621020x11=20u2=7735820x23=10x24=10u3=3329440x31=10x32=25x34=5需求量bj30251015

13.1物资调配问题13.1.2用表上作业法求解运输问题2.解的最优性检验位势法或闭回路法计算空格的检验数结果

viui

v1=(0)v2=–1v3=–2v4=1供应量aiu1=11621020x11=20σ12=6σ13=3σ14=8u2=7735820σ21=0σ22=–3*x23=10x24=10u3=3329440x31=10x32=25σ33=8x34=5需求量bj30251015

因σ22=–3<0，故知该解不是最优解，还有待调整改正。13.1物资调配问题13.1.2用表上作业法求解运输问题解改进的具体步骤为:(1)以xij为换入变量，找出它在运输表中的闭回路；(2)以空格(Ai,Bj)为第一个奇数顶点．沿闭回路的顺(或逆)时针方向前进，对闭回路上的顶点依次编号；(3)在闭回路上的所有偶数顶点中，找出运输量最小的顶点(格子)，以该格中的变量为换出变量；3.解的改进13.1物资调配问题13.1.2用表上作业法求解运输问题3.解的改进(4)以为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于。然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。13.1物资调配问题13.1.2用表上作业法求解运输问题对例1中用最小元素法得出的解进行改进。3.解的改进调整图

重新调整调运方案，现再用位势法或闭回路法求这个新解各非基变量的检验数，结果示于下页表中。由于所有非基变量的检验数全非负，故这个解为最优解。13.1物资调配问题13.1.2用表上作业法求解运输问题3.解的改进

viui

v1=(0)v2=–1v3=–2v4=1供应量aiu1=11621020x11=20σ12=6σ13=0σ14=8u2=7735820σ21=2x22=10x23=10σ24=3u3=3329440x31=10x32=15σ33=5x34=15需求量bj30251015

位势法或闭回路法计算新检验数结果13.1物资调配问题13.1.2用表上作业法求解运输问题4.需要说明的几个问题（1）若运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常δij<0取中最小者对应的变量为换入变量;（2）当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重(无穷多)最优解;13.1物资调配问题13.1.2用表上作业法求解运输问题（3）当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭化工作进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格子中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为m+n-1个。4.需要说明的几个问题13.1物资调配问题13.1.3运输问题的进—步讨论

上—节讲述的运输问题的算法，是以总产量等于总销量(产销平衡)为前提的。实际上在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作业法求解，就需将产销不平衡运输问题化为产销平衡运输问题。1.产销不平衡的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论如果总产量大于总销量，即这时的数学模型是1.产销不平衡的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论

为借助于产销平衡时的表上作业法求解，可增加一个假想的销地Bn+1，由于实际上它不存在，因而由产地Ai(i=1,2,…,m)调运到这个假想销地的物品数量xi,n+1(相当于松弛变量)，实际上是就地存贮在Ai的物品数量。就地存贮的物品不经运输，故其单位运价ci,n+1(i=1,2,…,m)。1.产销不平衡的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论若令假想销地的销量为bn+1，且则模型变为1.产销不平衡的运输问题对应的运输表见下页。13.1物资调配问题13.1.3运输问题的进—步讨论1.产销不平衡的运输问题

总销量大于总产量的情形可仿照上述类似处理，即增加一个假想的产地Am+1，它的产量等于

由于这个假想的产地并不存在，求出的由它发往各个销地的物品数量，实际上是各销地所需物品的欠缺额，显然有13.1物资调配问题13.1.3运输问题的进—步讨论

在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运到某个中间转运站(可能是另外的产、销地或中间转运仓库)，然后再转运到销售地。有时，经转运比直接运到目的地更为经济。总之，很多情况下，在决定运输方案时有必要把转运也考虑进去。显然．考虑转运将使运输问题变得更为复杂。

2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论2.有转运的运输问题(a)无转运(b)包含转运13.1物资调配问题13.1.3运输问题的进—步讨论

假定m个产地A1,A2,…,Am和n个销地B1,B2,…,Bn都可以作为中间转运站使用，从而发送物品的地点相接收物品的地点都有m+n个。这样一来，我们就得到了一个扩大了的运输问题。2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论为建立其数学模型，令：ai：第个i产地的产量(净供应量)；bj：第j个销他的销量(净需要量)；xij：由第i个发送地运到第j个接收地的物品数量；cij：由第i个发送地到第j个接收地的单位运价；ti：第i个地点转运物品的数量；ci：第i个地点转运单位物品的费用。2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论现将产地和销地统一编号，并把产地排在前面，销地排在后面，则有假定为平衡运输问题，即有2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论根据前面对平衡运输问题的讨论，可得该扩大了的运输问题的数学模型如下：2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论在上述模型中:(a)指的是：第i个产地发送到各个地方的物品数量之和，等于该产地的产量加上经它转运的物品数量；(b)的意义同上，但由于它们原为销地，不生产物品，故约束条件的右侧常数仅为该地的转运量；(c)和(d)的意义为由各地运到第j地的物品数量之和，前者等于其转运量，后者等于净需要量加上转运量。2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论将上述模型中的各约束等式右侧的或移到等号左侧，然后在各式等号两端分别加上Q，并今，则可把模型写成：2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论2.有转运的运输问题

要特别注意，在此模型中，对所有i=j，cij=-ci。由于目标函数中这一项为常数，它不影响求最优解，在优化过程中可不予考虑。该模型的运输表和运价表见下页。当不考虑转运费时，可令。13.1物资调配问题13.1.3运输问题的进—步讨论2.有转运的运输问题运输表

接收地供应地

供应地

销售地发送量1…mm+1…m+n供应地1x11…x1mx1,m+1…x1,m+nQ+a1……………………mxm.,1…xmmxm,m+1…xm,m+nQ+am销售地m+1xm+1,1…xm+1,mxm+1,m+1…xm+1,m+nQ……………………m+nxm+n,1xm+1,n+mxm+n,m+1…xm+n,m+nQ接收量Q…QQ+bm+1…Q+bm+n13.1物资调配问题13.1.3运输问题的进—步讨论2.有转运的运输问题运价表

接收地供应地

供应地

销售地发送量1…mm+1…m+n供应地1-c1…c1mc1,m+1…c1,m+nQ+a1……………………mcm.,1…-cmcm,m+1…cm,m+nQ+am销售地m+1cm+1,1…cm+1,mcm+1…cm+1,m+nQ……………………m+ncm+n,1cm+n,mvm+n,m+1…-cm+nQ接收量Q…QQ+bm+1…Q+bm+n13.1物资调配问题13.1.3运输问题的进—步讨论

例2：已知A1，A2，A3三个饮料厂生产同一规格的饮料，用相同价格供应B1，B2，B3三个销售网点销售。有两个转运站T1，T2，并且产品运输可以在各产地，各销售地及各转运站之间转运。已知各产地、销地、中转站相互之间每吨货物的单位运价和产量，见下页表。2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论2.有转运的运输问题各产地、销地、中转站之间的关系产地转运站销售地产量A1A2A3T1T2B1B2B3产地A1862━410830A2851395910A3654228720转运站T12148463T2━328232销售地B149242━5B2105863━4B38973254销售量15351013.1物资调配问题13.1.3运输问题的进—步讨论（1）对扩大的运输问题建立运价表。对于没有运输路线的去任意大的正数M；对自己运输的运价cij=0。（2）所有转运站的转运量等于销量，即Q=30+20+10=15+35+10=60,取T1，T2的产量与运量均为60t。（3）在原来的产量与销量的数值在加上调运量，三个产地的产量为90t，70t，80t,销量均为60t；三个销量为75t,95t,70t,产量均为60t.如下页表所示。2.有转运的运输问题13.1物资调配问题13.1.3运输问题的进—步讨论用表上作业法求解的最优方案2.有转运的运输问题

运量销售地产量A1A2A3T1T2B1B2B3产地A160151590A2551570A3602080T15451060T2402060B16060B26060B36060销售量606060606075957013.1物资调配问题13.1.3运输问题的进—步讨论实际最优方案及最优运输路线如图，最小费用为300。2.有转运的运输问题A1A2A3B1B2B3T1T2301510201515202051013.2网络流问题13.2.1图的基本概念有八种颜料A、B、C、D、P、R、S、T要放进贮藏室保管。出于安全原因，下列各组颜料不能贮在同一室内：A—R，A—C，A—T，R—P，P—S，S—T，T—B，B—D，D—C，R—S，R—B，P—D，S—C，S—D，问贮存这八种颜料至少需要多少间贮藏室。13.2网络流问题13.2.1图的基本概念供应链是指供货商、生产企业、客户、以及供货商的供货商、客户的客户、……所组成的一个网络。某家电公司生产电脑的工厂有多个，分布在国内不同的地区；公司在国内的各个省市都设有经营部，负责当地销售，这时可以表示出电脑在工厂与经营部以及经营部之间的运输情况。13.2网络流问题13.2.1图的基本概念有5名学生要参加6门课程的考试，大家选修的课程不同，并且考试的门数也不相同，这种情况也可以用图来表示。13.2网络流问题13.2.1图的基本概念

在一个图中．记点的集合为V(要求V是非空集)，边的集合为E，将这个图记为：G(V,E)。这儿对点表示从点vi到点vj的单向边，表示vi与vj之间的无向边。所以，无向边等价于两条有向边。13.2网络流问题13.2.1图的基本概念

在一个图G中．如果所有的边都是无向的，则称G为无向图；否则，即至少有一条边是有向的，则称G是有向图。由于无向边可以等价为两条有向边，所以，下面就对有向图给出一些概念。13.2网络流问题13.2.1图的基本概念

若边，则称(u,v)是e的端点，也称u,v是相邻的，称e是点u及v点。的关联边。若图G中，某个边e的两个端点相同，则称e是环；若两个点之间有多于一条的边，则称这些边为多重边。一个无环、无多重边的图称为简单图，一个无环、但有多重边的图称为多重图。13.2网络流问题13.2.1图的基本概念

给定一个图G=(V,E)，设是G中的一个点边交错的序列，如果这个序列对均有，则称该序列为从vi1到vik的一条路。若路的第一个点和最后一个点相同，即vi1=vik，则称之为回路。13.2网络流问题13.2.1图的基本概念

若在路中，点互不相同，则称这条路为初等路。一条回路中，若除vi1外其他点互不相同，则称之为初等回路。在路中，若所含的互不相同，则称之为简单路。既是简单路，又是回路的路，称之为简单回路。13.2网络流问题13.2.1图的基本概念试运用上述概念分析下面的简单网络图。13.2网络流问题13.2.1图的基本概念

给定两个图G(V,E)及G’(V’,E’)，如果，则称G’是G的一个子图。进而，若，则称G’是G的一个支撑子图。子图支撑子图13.2网络流问题13.2.1图的基本概念

在图G中，如果从点u到点v有路，则称从点u可以到达点v。如果对图G中的任意两个点，从u都可以到达v,则称G是连通图；否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通子图。13.2网络流问题13.2.1图的基本概念

一个没有回路的连通图称为树。设图G(V,E)是图G’(V’,E’)的支撑子图，如果图G’是一个树，则称G’是G的一个支撑树。13.2网络流问题13.2.2最短路

已知如图所示的交通网络图，每条边上的数字表示通过这条路所需要的费用。某公司将仓库建在了v1处，现在需要通过这个交通图，将货物运送到销售地v7去，求使交通总费用最小的运货路线。1.问题的提出13.2网络流问题13.2.2最短路1.问题的提出

给定一个赋权有向图G(V,E)，其中，即对图G中的每一条边,有相应的权值w(e)，简记为wij。vs,vt是G中给定的两个点。设P是G中从vs至vt的一条路，定义路P的权值是P中所有边的权值之和，记为w(P)。最短路问题就是在所有从vs至vt的路中，求一条权值最小的路，即求一条从vs至vt的路P0，使称P0是从vs至vt的最短路。路P0的权值也称为从vs至vt的距离,记为。13.2网络流问题13.2.2最短路

显然，在最短路问题中，可以假定相应的图是简单图。因为如果G中有环，可以删掉环；如果G中有多重边，可以根据问题的具体含义删掉多余的边，使得任意两点之间只剩下一条边，或者将多重边合并为一条．而将多重边的权值相加之和作为合并后的边的权值。这样做不会影响以上最短路问题的实质。1.问题的提出13.2网络流问题13.2.2最短路

最短路问题大量地出现于实际问题中，如管道铺设(陆袖管道、天然气管道等等)，运输线路安排，厂区布局，以及计算机网络(包括因特网)中通信线路的选择(路由算法)等等。最短路问题的算法也常作为解决其他优化问题的基本工具。1.问题的提出13.2网络流问题13.2.2最短路

由动态规划的最优性原理，我们知道，如果P是G中从vs至vt的最短路，vi是P中的一个点，那么，从vs出发沿P到vi的路也是从vs到vi的最短路。因为如果这个结论不成立，假设Q是从vs至vi的最短路，令P’是从vs沿Q到vi，再从vi沿P到vt的路，那么P’的权值就比P的权值小，这与P是从vs至vt的最短路矛盾。2.最短路的一般算法13.2网络流问题13.2.2最短路

由此可知，从vs至vj的最短路，也是从vs到达其路径上各个点的最短路，利用动态规划的基本思想，很容易得到下面的最优方程。对，记；对。则以上的最优方程可等价地写为：2.最短路的一般算法13.2网络流问题13.2.2最短路2.最短路的一般算法算法：最短路算法步骤1：设节点数为n,s=1;步骤2：开始时，令。步骤3；令t=t+1，步骤4：判断对所有的与是否相等。不成立，转入步骤3；若全都相等，则算法终止，表示vs到vj的最短路的权值。13.2网络流问题13.2.2最短路2.最短路的一般算法

若想进一步求从v1到各点的最短路，我们可以利用动态规划法中的方法，按计算顺序反推之，逐步求出v1到各个点的最优路线。或者，也可以给每一个点都设一个λ值：；在迭代过程中，如果则把这时的修改为i*。迭代终止时，根据各点λ值，从后往前依次递推，得到从vs到各点的最短路。13.2网络流问题13.2.2最短路2.最短路的一般算法

由动态规划的理论可知，是在至多包含t-1个中间点的限制条件下，从vs至vj的最短路的权。若，表示从s到j之间不存在一条至多包含t-1个中间点的路。因此，当存在j，使时，该图为不连通图。13.2网络流问题13.2.2最短路2.最短路的一般算法由动态规划理论易知以下定理成立。定理：若上算法进行到某一步时，例如第k步时，有则是vs至vj的最短路的权值。以上定理说明算法在终止时得到的是最短路的权值。13.2网络流问题13.2.2最短路练习：求下图所示的赋权有向图中从v1到各点的最短路。2.最短路的一般算法13.2网络流问题13.2.2最短路

Dijkstra方法的基本思想是从vs出发，逐步地探寻最短路。在执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短的权值(称为该点的P标号)、或者是从vs到该点的最短路的权值的上界(称为该点的T标号)，方法的每一步是去修改每一个点的了标号，并且把某一个具T标号的点改变为具P标号的点，从而使G中具P标号的点的数量多一个，这样，就可以求出从vs到各点的最短路。3.一种常用的方法：Dijkstra算法13.2网络流问题13.2.2最短路3.一种常用的方法：Dijkstra算法

Dijkstra方法的具体步骤：(1)令，对每一个，令(2)如果，算法终止，这时，对每个则转入下一步。(3)考察每个使的点vj，如果，修改，把修改为k;否则转入下一步。13.2网络流问题13.2.2最短路3.一种常用的方法：Dijkstra算法(4)令，即点vji是T标号值最小的点；如果，则把的T标号变为P标号，且令把i换成i+1，转入步骤2；否则，算法终止，这时，对每—个，而对每—个。13.2网络流问题13.2.2最短路用Dijkstra方法去求图中从v1到各个点的最短路。3.一种常用的方法：Dijkstra算法13.2网络流问题13.2.3最大流问题1.模型与基本结论水力输送图

一个输送方案13.2网络流问题13.2.3最大流问题1.模型与基本结论

给定一个有向图G(V,E)，我们在图G中指定一点，称为发点，记作vs

；并指定另外一个点作为收点．记作vt

；其余的点是中间点。如果图G中的每一条边都对应有一个最大通过能力，称为边的容量，我们用表示。通常，我们把这样的图G称为网络，记作。同前面一样，这里仅考虑简单图。13.2网络流问题13.2.3最大流问题1.模型与基本结论

称定义在边集合置上的任意一个函数为网络G上的一个流，其中表示边上的流量，这是因为每条边的流量不能超过该边的最大通过能力，这个条件也称之为“容量限制条件”。可简写为fij。13.2网络流问题13.2.3最大流问题1.模型与基本结论

对每个点，流出这点的量与流人这点的量的差．称为是该点的净输出量，也称为是该点的流量。显然，点的流量与流f有关。在流f下，点i的流量为：在实际的流量问题中，对发点vs来说常常是输出多于输人，因此其流量是正的。13.2网络流问题13.2.3最大流问题1.模型与基本结论

对收点vt来说，则常常是输入大于输出，即流量是负的；我们这里仅考虑平衡系统，即发点的净输出量与收点的净输入量相等，因此有：由于中间点只起过渡的作用，所以要求中间点处的流出量等于流入量，即其流量为零，也即对每个有：以上式子被称之为“平衡条件”。13.2网络流问题13.2.3最大流问题

同时满足“容量限制条件”和“平衡条件”的网络流f就称为可行流。可行流总是存在的。比如令所有边的流量，就得到了一个可行流，其流量称此可行流为零流。最大流问题就是求一个可行流使其流量达到最大，即1.模型与基本结论13.2网络流问题13.2.3最大流问题1.模型与基本结论

在网络中，设是点集的两个互不相交的子集，我们把始点在S，终点在T中的所有边构成的集合，记作(S,T)，即若点集V被剖分为两个非空集合V1和，使，则称边集是分离vs和vt的截集，也称为割集。给定一个满足条件的集合V1，就可以得到一个截集。13.2网络流问题13.2.3最大流问题1.模型与基本结论

引理：如果对于一个可行流f*，网络中有一个截集使，则f*必是最大流，而必定是G的所有截集中，容量最小的一个，即最小截集。给定一个可行流，我们把网络中流量的边称为饱和边；把的边称为非饱和边。把的边称为零流边，的边称为非零流边。13.2网络流问题13.2.3最大流问题1.模型与基本结论

先不考虑网络图G中有向边的方向，将其视为一个无向图G’。设μ是图G’中从发点vs到收点vt的一条路；把路μ放回到有向图G中，根据方向的一致性，路上所有的边被分成了两类：若边的方向与路μ的方向一致，则称之为前向边。前向边的全体记作

。另一类是边的方向与路μ的方向相反的边，称之为后向边。后向边的全体记作

。13.2网络流问题13.2.3最大流问题1.模型与基本结论

给定一个可行流f，μ是一条从vs到vt的路，若它满足下列两个条件，则称μ为关于可行流f的一条增广链，（1）对边，有，即中的每一条边都是非饱和边；（2）对边，有，即中的每一条边都是非零流边。引理：若f*是网络G中的最大流，则G中不存在关于f*的增广链。13.2网络流问题13.2.3最大流问题定理1：可行流f*是G中最大流，当且仅当G中不存在关于f*的增广链。定理（最大流量小截定理)2：在任意一个网络G中，从vs到vt的最大流量等于分离vs和vt的最小截集的容量。1.模型与基本结论13.2网络流问题

在寻求实际问题中的最大流时，其基本思路与上面分析的相同：从一个可行流f出发(若网络中没有给定f，则可以设f是零流)。经过标号过程和调整过程，这种方法称之为标号法。2.寻求最大流的标号法13.2.3最大流问题13.2网络流问题标号过程:

在这个过程中，对网络中的各点进行标号，标号后的点又分为已检查的点和未检查的点两种。每个标号点的标号内容包含两部分：第一个标号表明它的前一步是哪一点以方便找出增广链；第二个标号是为确定增广链的调整量θ，改进f用的。2.寻求最大流的标号法13.2.3最大流问题13.2网络流问题2.寻求最大流的标号法13.2.3最大流问题

从vs开始，先给vs标上(0,+∞)，这时vs成为标号而未检查的点；其余的都是未标号的点。然后对网络中各未标号点按照下列步骤进行标号。一般地，取一个标号而未检查的点vi，对所有的末标号点vj，做以下的工作：

第一步，若边(vi,vj)上的fij<cij，则给vj标号。这里vi表示vj的标号从点vi得来,。这时vj成为标号而未检查的点。13.2网络流问题2.寻求最大流的标号法13.2.3最大流问题

第二步，若边(vj,vi)上的fji>0，则给vj标号。标号中意义同上；但，这时vj成为标号而未检查的点。这时vi是标号且已检查过的点。在标号过程中，G中的有些点有可能被标上多个标号。有的标号可能来自第一步，有的可能来自第二步，这时，保留l(vj)由第一步得到的标号；若从第一步得到的标号也有多个，则保留值最大的一个作为标号。这样可以加快找到最大流的速度。13.2网络流问题

然后取另一个标号而未检查的点．重复上述步骤，一