二章四节运输问题.ppt

第四节运输问题,3.1运输问题及其数学模型3.2表上作业法3.3产销不平衡的运输问题3.4应用举例,本章主要内容:,1掌握运输问题的数学模型、系数矩阵特殊形式2掌握用西北角法、最小元素法求初始基可行解3掌握回路、位势法求解过程和表上作业法求解运输问题过程,教学要求：,一、运输问题及其数学模型,在经济建设中，经常碰到物资调拨中的运输问题。例如煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？,问题的提出:,运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为；销地Bj的销量。从第i个产地向第j个销地运输每单位物资的运价为Cij。这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。,1、运输问题的一般提法,单位运价表,（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。,分两种情况来讨论：,若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：,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.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示,问应如何调运，可使得总运输费最小?,即初始基本可行解的确定，与一般线性规划问题不同，产销平衡运输问题总是存在可行解。,1、确定初始方案,确定初始基本可行解的方法很多，一般希望方法是既简便，又尽可能接近最优解。下面介绍两种方法：最小元素法，西北角法、Vogel法,（1）最小元素法,最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。,1,3,2,1,3,4,4,6,5,3,10,3,方案表,运价表,以此，得到一初始方案：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=31+64+43+12+310+35=86(元),（2）西北角法,西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。,3,4,2,2,3,6,方案表,运价表,注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行(列)。在饱和的列（行）没被划去的格内标一个0,然后划去该列（行）。,例3.2某公司下属有生产一种化工产品的三个产地A1、A2、A3，有四个销售点B1、B2、B3、B4销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。,问应如何调运，可使得总运输费最小?,解：用西北角法求初始基本可行解,方案表,运价表,35,40,0,40,15,65,(3)伏格尔法（次小运价与最小运价之差大者先安排）,方案表,运价表,2513,011,6,012,3,212,3,76,5,1,2,2、判断当前方案是否为最优,用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。,（1）闭回路法,在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。,对方案表中每一空格，确定一条由空格出发的闭回路。闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。,可以证明，对每一个空格都存在而且惟一存在这样一条封闭回路。,计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。,11=3-3+2-1=122=9-2+30+54=131=7-5+103+21=10,12=11-10+5-4=224=810+32=-133=10-5+10-3=12,当所有空格检验数ij0,则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整。,若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。,ij具有确切的经济意义，它表示由Ai往Bj增运1单位时，引起的总运输成本的变化数。,闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算都会产生困难。,（2）位势法（对偶变量法）,对于一个调运方案的每列赋予一个值，称为列位势，记，对于每行赋予一个值，称为行位势，记为,则检验数为：ij=cij-ui-vji=1,m;j=1,n,它们的值由下列方程组决定：其中，cij是所有基变量（数字格）xij的运价系数。,1,3,2,1,3,4,4,6,5,3,10,3,方案表,运价表,u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4,u1,u2,u3,v1,v3,v2,v4,u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5,令u1=5则有v4=5,v3=-2,u2=4,u3=0,v2=4,v1=-3,11=c11u1-v1=35(-3)=1,12=c12u1v2=1154=2,22=c22u2v2=944=1,24=c24u2v4=845=-1,31=c31u3-v1=70(-3)=10,33=c33u3v3=100(-2)=12,再求非基变量（空格）检验数：,u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4,u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5,（1）在有数格上填上相应的运价,方案表,运价表,u1,u2,u3,v1,v3,v2,v4,位势法在表上进行：,(2)设u1=0，然后根据cij=ui+vj（有数格），依次求得ui和vj的值，并填在相应的位置,u1,u2,u3,v1,v3,v2,v4,2,3,9,10,0,-1,-5,计算(ui+vj)表，把(ui+vj)位势和值填在表中相应位置上，并将有数格位置上的值ui+vj加上括号以示区别。,（）,（）,（）,（）,（）,（）,2,9,8,9,-3,-2,(ui+vj)表,运价表,u1,u2,u3,v1,v3,v2,v4,2,3,9,10,0,-1,-5,检验数表,（3）计算检验数表,ij=cij(ui+vj),(ui+vj)表,1,2,1,-1,10,12,3、调整方案,若在检验数上有某空格的检验数为负，则可改进方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行调整，即在保持方案可行的条件下，尽量增加空格上的运量。,从ij为最小负值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(这才能保证新的平衡)，其中调整量为该空格闭回路中偶数顶点的最小值。,注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。（保证基变量个数不变）（p48）,24=-1，作x24的闭回路，调整数=1，调整得,再用闭回路法或位势法求各空格的检验数，,x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余的xij=0,总运费为：f=53+210+31+18+64+35=85。,表中的所有检验数都非负，故上表中的解为最优解。,检验数表,方案表,表上作业法中需要说明的问题,（1）无穷多最优解当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。上面的例题是多解情况,检验数表,方案表,调整方案表,（2）退化当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为（m+n-1）个。,表上作业法中需要说明的问题,三、产销不平衡的运输问题,前面我们讨论的运输问题，都是产销平衡的问题，即满足在实际问题中，产销往往是不平衡的，遇到这种情况，我们可以经过简单的处理，使其转化为产销平衡问题，然后再按前面的方法来求解。,1、产量大于销量,对于产大于销问题，可得到下列运输问题的模型：,可增加一个假想的销地，其销量为：某个产地Ai运到这个假想销地Bn+1的物资量xi,n+1，实际上就意味着将这些物资在原产地贮存，其相应的运价，转化为产销平衡的问题，其数学模型为：,例3-3某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,单位运价表,解：这里，总产量为78+45=123；总销量为53+36+25=114。产销不平衡，增加一个虚设的销地，得到下表,2、产量小于销量,对于产小于销问题,可增加一个假想的产地，其产量为：其相应的运费为上述不平衡问题就转化为平衡的问题，,例3-4某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表，问：应如何调运可使总运输费用最小？,单位运价表,解:这里，总产量小于总销量，产销不平衡，增加一个虚设的产地，得到下表,四、应用举例,在变量个数相等的情况下，表上作业法的计算远比单纯形法简单。解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面为几个典型的例子。,例3-5有A1、A2、A3三个生产某种物资的产地，五个地区B1、B2、B3、B4、B5对这种物资有需求。现要将这种物资从三个产地运往五个需求地区，各产地的产量、各需求地区的需要量和各产地运往各地区每单位物资的运费如下表所示，其中B2地区的115个单位必须满足。问：应如何调运可使总运输费用最小？,运输费用及产量、需求量表,解：由于产量小于需求量，因此设一虚设产地A4,它的产量为需求量与产量的差20，与这一项有关的运输费用一般为零。因为B2地区的115个单位必须满足，即不能有物资从A4运往B2地区，于是取相应的费用为M（M是一个充分大的正数），以保证在求最小运输费用的前提下，该变量的值为零。,可以建立如下产销平衡的运输费用表,例3-6某研究院有B1、B2、B3三个区。每年取暖分别需要用煤3500吨、1100吨、2400吨，这些煤都要由A1、A2两处煤矿负责供应，价格、质量均相同。A1、A2煤矿的供应能力分别为1500吨、4000吨，运价（元/吨）如下表。由于需求大于供给，经院研究决定B1区供应量可减少0900吨，B2区必须满足需求量，B3区供应量不少于1600吨，试求总费用为最低的调运方案。,由于B1区供应量可减少0900吨，B3区供应量不少于1600吨，可以把B1区和B3区分别设为两个区：一个为必须满足需求量的区域，另一个为可以调整供应量的区域。原问题化为五个需求区域B1、B1、B2、B3、B3的问题，同时增加一个虚设的产地A3。,在运输费方面,必须满足需求量的相应变量，运费的取值为M，可调整需求量的相应变量，运费的取值为0，作出产销平衡的运价表,解：这是需求量大于生产量的运输问题,例3-7某公司生产某种规格的设备，由于生产与季节有关系，生产能力与成本有差异，如下表所示。,某种规格设备各季节的生产能力与成本,该厂年初签订的合同规定：当年一、二、三、四每个季度末分别需要提供200、300、500、400台这种规格的设备。如果生产出来的设备当季不交货，每台每积压一个季度需储存、维护等费用为0.15万元。试求在完成合同的前提下，使该厂全年生产总费用为最小的决策方案。,解：设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。,于是得到目标函数：,Minf=9.8x11+9.95x12+10.1x13+10.25x14+10.5x22+10.65x23+10.8x24+10.3x33+10.45x34+10.6x44,x11=200 x12+x22=300 x13+x23+x33=500 x14+x24+x34+x44=400,交货：,生产：,x11+x12+x13+x14500 x22+x23+x24700 x33+x34600 x44200 xij0i=1,2,3,4ji,由于产大于销，虚构一个销地，可构造下列产销平衡问题:,各季节的生产、交货费用表,把第i季度生产的设备数目看作第i个生产厂的产量；把第j季度交货的设备数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。,例8例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示,问应如何调运，可使得总运输费最小?,例8在本章的例1中，如果假定,每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；运往各销地的产品可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与