运输问题的数学模型运输问题的数学模型3.13.1 运输问题及其数学模型3.23.2 表上作业法3.3 产销不平衡的运输问题3.43.4 应用举例本章主要内容:1掌握运输问题的数学模型、系数矩阵特殊形式2掌握用西北角法、最小元素法求初始基可行解3掌握回路、位势法求解过程和表上作业法求解运输问题过程教学要求：一、 运输问题及其数学模型 在经济建设中，经常碰到物资调拨中的运输问题。例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？问题的提出: 运输问题的一般提法是：设某种物资有m m个产地和n n个销地。产地A Ai i的产量为 ；销地B Bj j的销量 。从第i i个产地向第j j个销地运输每单位物资的运价为C Cijij。 这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。1、运输问题的一般提法单位运价表 （1） 。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。 （2） 。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。 分两种情况来讨论： 若用x xijij表示从A Ai i到B Bj j的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：2、运输问题的数学模型其中，ai和bj满足： 称为产销平衡条件。将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。 上述模型是一个线性规划问题。但是其结构很特殊，特点如下：1.变量多（mn个），但结构简单。 技术系数矩阵 该系数矩阵中每列只有两个元素为1，其余的都为零。2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式 ）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。二、 表上作业法 运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是： 1.运输问题所涉及的变量多，造成单纯形表太大； 2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。 以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。表上作业法，实质上还是单纯形法。其步骤如下：1.确定一个初始可行调运方案。可以通过最小元素法、西北角法、Vogel 法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。二、表上作业法（续） 例例3.13.1 某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示 问应如何调运，可使得总运输费最小? 即初始基本可行解的确定，与一般线性规划问题不同，产销平衡运输问题总是存在可行解。1、确定初始方案 确定初始基本可行解的方法很多，一般希望方法是既简便，又尽可能接近最优解。下面介绍两种方法：最小元素法，西北角法、 Vogel 法（1）最小元素法 最小元素法的基本思想是优先满足单位运价最小的供销业务。 首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。 销产B B1 1B B2 2B B3 3B B4 4产量产量B B1 1B B2 2B B3 3B B4 4A17311310A241928A3974105需求3656201321344653103方案表运价表以此，得到一初始方案：X13=4 , X14=3， X21=3，X23=1， X32=6， X34=3（有数格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：（）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；（）如果填上一个变量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待。初始方案运费 Z0=31+64+43+12+310+35=86(元)（2）西北角法 西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。 销销产产BB1 1BB2 2BB3 3BB4 4产量产量产量产量B B1 1B B2 2B B3 3B B4 4A17311310A241928A3974105需求需求365620342236方案表运价表注注注注：应应用用西西北北角角法法和和最最小小元元素素法法，每每次次填填完完数数，都都只只划划去去一一行或一列。行或一列。 当当填填上上一一个个数数后后行行、列列同同时时饱饱和和时时，也也应应任任意意划划去去一一行行(列列)。在在饱饱和和的的列列（行行）没没被被划划去去的的格格内内标标一一个个 0 , 然然后后划划去去该列（行）。该列（行）。 例例例例3.23.2 某某公公司司下下属属有有生生产产一一种种化化工工产产品品的的三三个个产产地地A1、A2、A3 ，有有四四个个销销售售点点B1、B2、B3、B4 销销售售这这种种化化工工产产品品。各各产产地地的的产产量量、各各销销地地的的销销量量和和各各产产地地运运往往各各销销地地每每吨吨产产品品的的运费（百元）如下表所示。运费（百元）如下表所示。 销产B B1 1B B2 2B B3 3B B4 4产量产量B B1 1B B2 2B B3 3B B4 4A1753859A2402948A3806375需求35405565195 问应如何调运，可使得总运输费最小问应如何调运，可使得总运输费最小? 解：用西北角法求初始基本可行解解：用西北角法求初始基本可行解 销产B B1 1B B2 2B B3 3B B4 4产量产量B B1 1B B2 2B B3 3B B4 4A1753859A2402948A3806375需求35405565195方案表运价表35400401565(3)伏格尔法（次小运价与最小运价之差大者先安排） 销销产产BB1 1BB2 2BB3 3BB4 4产产产产量量量量BB1 1BB2 2BB3 3BB4 4A17311310A241928A3974105需求需求365620方案表运价表 2 5 1 3 01160123 2 1 2 3765122、判断当前方案是否为最优 用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。 表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。（1）闭回路法 在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。 由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。 B1B2B3B4A143A231A363 对方案表中每一空格，确定一条由空格出发的闭回路。 闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。B1B2B3B4A143A231A363 可以证明，对每一个空格都存在而且惟一存在这样一条封闭回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。B1B2B3B4A143A231A363 11=3 - 3+2 - 1=1 22= 9-2+30+54 =1 31= 7-5+103+21=10 12=11 - 10+5 - 4=2 24= 810 +3 2 =-1 33=10 - 5+10 -3=12当所有空格检验数 ij 0则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整。 若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。 ij 具有确切的经济意义，它表示由Ai往Bj增运1单位时，引起的总运输成本的变化数。B1B2B3B4A143A231A363 闭闭回回路路法法的的主主要要缺缺点点是是：当当变变量量个个数数较较多多时时，寻寻找找闭闭回回路路以及计算都会产生困难。以及计算都会产生困难。（2）位势法（对偶变量法） 对于一个调运方案的每列赋予一个值，称为列位势，记 ，对于每行赋予一个值，称为行位势，记为 则检验数为： ij = cij - ui - vj i = 1, , m ; j = 1, , n它们的值由下列方程组决定：其中， cij 是所有基变量（数字格）xij 的运价系数 。 销销产产B B1 1B B2 2B B3 3B B4 4产量产量产量产量B B1 1B B2 2B B3 3B B4 4A17311310A241928A3974105需求需求3656201321344653103方案表运价表u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1u2u3v1v3v2v4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 令u1 = 5 则有 v4 = 5 v3 = -2u2 = 4 u3=0v2=4v1= -311 = c11 u1 - v1 = 3 5 (-3) = 1 12 = c12 u1 v2 = 11 5 4 = 222 = c22 u2 v2 = 9 4 4 = 1 24 = c24 u2 v4 = 8 4 5 = -1 31 = c31 u3 - v1 = 7 0 (-3) = 10 33 = c33 u3 v3 = 10 0 (-2) = 12 再求非基变量（空格）检验数： u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 （1）在有数格上填上相应的运价 销销产产B B1 1B B2 2B B3 3B B4 4A143A231A363方案表运价表 销销产产B B1 1B B2 2B B3 3B B4 4A1310A212A345u1u2u3v1v3v2v4位势法在表上进行： (2) 设u1=0，然后根据cij=ui+vj （有数格），依次求得ui和vj的值，并填在相应的位置 销销产产B B1 1B B2 2B B3 3B B4 4A1310A212A345u1u2u3v1v3v2v4239100-1-5计算(ui+vj )表，把(ui+vj )位势和值填在表中相应位置上，并将有数格位置上的值ui+vj 加上括号以示区别。（ ） （ ）（ ）（ ）（ ）（ ）2989-3-2(ui+vj )表 销销产产B B1 1B B2 2B B3 3B B4 4A1311310A21928A374105运价表 销销产产B B1 1B B2 2B B3 3B B4 4A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5检验数表 销销产产B B1 1B B2 2B B3 3B B4 4A1A2A3（3）计算检验数表ij = cij ( ui + vj)(ui+vj )表121-110123、调整方案 若在检验数上有某空格的检验数为负，则可改进方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行调整，即在保持方案可行的条件下，尽量增加空格上的运量。 从ij 为最小负值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(这才能保证新的平衡)，其中调整量为该空格闭回路中偶数顶点的最小值。B1B2B3B4A143A231A363注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。（保证基变量个数不变）（p48）B1B2B3B4A152A231A36324= -1，作 x24 的闭回路，调整数=1，调整得再用闭回路法或位势法求各空格的检验数，B1B2B3B4A152A231A363 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余的 xij = 0 总运费为： f = 53 + 210 + 31 + 18 + 64 + 35 = 85 。 销销产产B B1 1B B2 2B B3 3B B4 4A102A221A3912表中的所有检验数都非负，故上表中的解为最优解。检验数表方案表表上作业法中需要说明的问题 （1）无穷多最优解 当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。上面的例题是多解情况 销销产产B B1 1B B2 2B B3 3B B4 4A102A221A3912B1B2B3B4A152A231A363检验数表方案表B1B2B3B4A1250A213A363调整方案表 （2）退化 当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为（m+n-1）个。表上作业法中需要说明的问题 三、 产销不平衡的运输问题 前面我们讨论的运输问题，都是产销平衡的问题，即满足 在实际问题中，产销往往是不平衡的，遇到这种情况，我们可以经过简单的处理，使其转化为产销平衡问题，然后再按前面的方法来求解。1、产量大于销量 对于产大于销问题 ，可得到下列运输问题的模型： 可增加一个假想的销地 ，其销量为： 某个产地Ai运到这个假想销地Bn+1的物资量xi,n+1，实际上就意味着将这些物资在原产地贮存，其相应的运价 ，转化为产销平衡的问题，其数学模型为： 例3-3 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 销产B B1 1B B2 2B B3 3产量产量A113151278A211292245需求533625 123114单位运价表解： 这里，总产量为 78 + 45 = 123 ；总销量为 53 +36 + 25 = 114 。产销不平衡，增加一个虚设的销地，得到下表 销产B B1 1B B2 2B B3 3B B4 4产量产量B B1 1B B2 2B B3 3B B4 4A1781315120A2451129220需求5236259123 销产B B1 1B B2 2B B3 3产量产量A113151278A211292245需求533625 1231142、产量小于销量 对于产小于销问题 可增加一个假想的产地 ，其产量为： 其相应的运费为 上述不平衡问题就转化为平衡的问题， 例3-4 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表，问：应如何调运可使总运输费用最小？ 销产B B1 1B B2 2B B3 3产产量量A113151278A211292245需求533665 123154单位运价表解: 这里，总产量小于总销量，产销不平衡，增加一个虚设的产地，得到下表 销产B B1 1B B2 2B B3 3产量产量B B1 1B B2 2B B3 3A178131512A245112922A331000需求533665 154 销产B B1 1B B2 2B B3 3产量产量A113151278A211292245需求533665 123154四、应用举例 在变量个数相等的情况下，表上作业法的计算远比单纯形法简单。解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面为几个典型的例子。 例3-5 有 A1、A2、A3 三个生产某种物资的产地，五个地区 B1、B2、B3、B4、B5 对这种物资有需求。现要将这种物资从三个产地运往五个需求地区，各产地的产量、各需求地区的需要量和各产地运往各地区每单位物资的运费如下表所示，其中 B2 地区的115个单位必须满足。问：应如何调运可使总运输费用最小？销地产地B B1 1B B2 2B B3 3B B4 4B B5 5产量A1101520204050A22040153030100A33035405525130需求25115603070280300运输费用及产量、需求量表解：由于产量小于需求量，因此设一虚设产地 A4 ,它的产量为需求量与产量的差 20，与这一项有关的运输费用一般为零。因为B2 地区的115个单位必须满足，即不能有物资从 A4 运往 B2 地区，于是取相应的费用为M（M是一个充分大的正数），以保证在求最小运输费用的前提下，该变量的值为零。销地产地B B1 1B B2 2B B3 3B B4 4B B5 5产量A1101520204050A22040153030100A33035405525130需求25115603070280300 可以建立如下产销平衡的运输费用表销地产地B B1 1B B2 2B B3 3B B4 4B B5 5产量A1101520204050A22040153030100A33035405525130A40M00020需求25115603070 例3-6 某研究院有 B1 、B2、B3 三个区。每年取暖分别需要用煤 3500 吨、1100 吨、2400 吨，这些煤都要由 A1、A2 两处煤矿负责供应，价格、质量均相同。A1、A2 煤矿的供应能力分别为 1500 吨、4000 吨，运价（元/吨）如下表。 由于需求大于供给，经院研究决定 B1 区供应量可减少 0900 吨，B2 区必须满足需求量，B3 区供应量不少于 1600 吨，试求总费用为最低的调运方案。 销地产地B B1 1B B2 2B B3 3产量产量A11751952081500A21601822154000需求量350011002400 由于 B1 区供应量可减少 0900 吨，B3 区供应量不少于 1600吨，可以把 B1 区和 B3 区分别设为两个区：一个为必须满足需求量的区域，另一个为可以调整供应量的区域。 原问题化为五个需求区域 B1、B1、B2、B3、B3 的问题，同时增加一个虚设的产地 A3 。 在运输费方面, 必须满足需求量的相应变量，运费的取值为 M ，可调整需求量的相应变量 ，运费的取值为 0，作出产销平衡的运价表解： 这是需求量大于生产量的运输问题 销地产地B B1 1B B1 1* *B B2 2B B3 3B B3 3* *产量产量A11751751952082081500A21601601822152154000A2M0MM01500需求量260090011001600800 例3-7 某公司生产某种规格的设备，由于生产与季节有关系，生产能力与成本有差异，如下表所示。某种规格设备各季节的生产能力与成本 第一季度第二季度第三季度第四季度生产能力 (台) 500700600200成本(万元/台）9.810.510.310.6 该厂年初签订的合同规定：当年一、二、三、四每个季度末分别需要提供 200、300、500、400 台这种规格的设备。如果生产出来的设备当季不交货，每台每积压一个季度需储存、维护等费用为 0.15万元。试求在完成合同的前提下，使该厂全年生产总费用为最小的决策方案。解： 设 xij ij为第 i 季度生产的第 j 季度交货的设备数目，则问题的线性规划模型为： cij ij = 第 i 季度每台的生产成本 + 0.15(j-i)（储存、维护等费用）。计算可得： c11 = 9.8 , c12 = 9.95 , c13 = 10.1 , c14 = 10.25 , c22 = 10.5 , c23 = 10.65 , c24 = 10.8 , c33 = 10.3 , c34 = 10.45 , c44 = 10.6 。于是得到目标函数： Min f = 9.8x11+9.95x12+10.1x13+ 10.25x14 + +10.5x22+10.65x23+10.8x24+10.3x33+ +10.45x34+10.6x44x11 = 200 x12 + x22 = 300 x13 + x23 + x33 = 500 x14 + x24 + x34 + x44 = 400 交货：交货：生产：生产：x11 + x12 + x13 + x14 500 x22 + x23 + x24 700 x33 + x34 600 x44 200 xij 0 i=1,2,3,4 j i由于产大于销，虚构一个销地，可构造下列产销平衡问题:各季节的生产、交货费用表 交货生产第一季度第二季度第三季度第四季度虚设交货生产能力第一季度9.89.9510.110.250500第二季度M10.510.6510.80700第三季度MM10.310.450600第四季度MMM10.60200交货量2003005004006002000 把第 i 季度生产的设备数目看作第 i 个生产厂的产量；把第 j 季度交货的设备数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。例8例3.1 某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示 问应如何调运，可使得总运输费最小?例8 在本章的例1中，如果假定每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；运往各销地的产品可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间转运。 已知各产地、销地、中间转运站及相互之间每吨产品的运价如表3-40所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。单位运价表解 ：从表看出，从A1到B2每吨产品的直接运费为11元，如从A1经A3运往B2，每吨运价为3+4=7元，可见这个问题中从每个产地到各销地之间的运输方案是很多的。(1) 由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。(2) 对扩大的运输问题建立单位运价表。方法将表中不可能的运输方案的运价用任意大的正数M代替。(3) 所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。可以规定T1，T2，T3，T4的产量和销量均为20吨。 为了把这个问题仍当作一般的运输问题处理，可以这样做：本章小结运输问题模型是一种特殊的线性规划，由于其约束条件特别简单，因此它有更简单的解法表上作业法。本章教学重点内容有：1. 运输问题的数学模型及其特点；2. 确定初始调运方案的最小元素法；3. 检验数的意义、计算方法和格式；4. 方案调整的方法；5. 把不平衡运输问题转化为标准模型的方法。表上作业法类似于单纯形法，表上作业法的步骤：第一步，确定一个初始可行调运方案。常用的方法有最小元素法、西北角法等。第二步，判别当前可行方案是否最优。常用方法有二种，一种是闭回路法，另一种称为位势法。通过这二种方法，计算出检验数，从而判别方案是否最优。第三步，方案调整。即从当前方案出发去寻找另一个更好的调运方案。