运筹学 二章四节运输问题

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