第三章运输问题(2)

,管理运筹学,牧云志muriel2001,WELCOMETOManagementOperationsResearch,第三章运输问题,2,第三章运输问题,第三章运输问题,3,第三章运输问题,运输问题在工商管理中有着广泛的应用，是一类重要的和特殊的线性规划问题。由于这类线性规划问题在结构上有特殊性，所以有专门的解法表上作业法等，用以简便求解这类问题。本章讨论：1运输问题及其数学模型2运输问题的表上作业法3运输问题应用举例第三章习题,第三章运输问题,4,本章学习要求,本章要求：1理解运输问题的典例和数学模型。2掌握表上作业法。3掌握产销不平衡的运输问题及其应用。重点和难点：运输模型；表上作业法。,第三章运输问题,5,1运输问题及其数学模型,运输问题是线性规划问题的特例。产地：货物发出的地点。销地：货物接收的地点。产量：各产地的可供货量。销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。,第三章运输问题,6,总产量=总需求量（产销平衡）,例3.1某食品公司经销的主要产品之一是糖果，有三个加工厂A1、A2、A3，每天要把生产的糖果运往B1、B2、B3、B4四个门市部销售，已知各厂的产量（吨/天）、各门市部的销售量（吨/天）及运价（元/吨），见下表，求运费最小的调运方案。,一、运输问题的数学模型,第三章运输问题,7,(1)决策变量设从Ai到Bj的运输量为xij，(2)目标函数minz=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)约束条件产量之和等于销量之和,故要满足：供应平衡条件,x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3,销售平衡条件,x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=1,非负性约束xij0(i=1,2,3；j=1,2,3,4),建立运输问题的LP模型：,第三章运输问题,8,第三章运输问题,9,第三章运输问题,10,上述例子中决策变量mn=34=12个约束方程m+n=3+4=7个系数矩阵结构如下：,第三章运输问题,11,一般运输问题的线性规划模型假设A1，A2，Am表示某物资的m个产地；B1，B2，Bn表示某物资的n个销地；ai表示产地Ai的产量（i=1,2,m）；bj表示销地Bj的销量（j=1,2,n）；cij表示把物资从产地Ai运往销地Bj的单位运价。xij表示把物资从产地Ai运往销地Bj的运输量。如果a1+a2+am=b1+b2+bn则称该运输问题是产销平衡的；否则，称它是产销不平衡的。下面我们首先讨论产销平衡的运输问题。,第三章运输问题,12,表式运输模型,第三章运输问题,13,对于产销平衡问题可得到下列运输问题的模型：,第三章运输问题,14,第三章运输问题,15,决策变量mn约束方程m+n系数矩阵的结构如下：,第三章运输问题,16,一般模型的系数矩阵特征1、共有m+n行，分别表示各产地和销地；mn列，分别表示各变量；2、每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用（即每一个变量在前m个约束方程中出现一次，在后n个方程中出现一次）；,第三章运输问题,17,二、运输问题数学模型的特点,1、产销平衡的运输问题必有可行解，也必有最优解；,根据推论1.2,2、产销平衡运输问题的系数矩阵A的秩等于m+n-1；m+n个约束方程去掉任何一个，剩下的m+n-1个方程都是独立的；运输问题的基可行解有m+n-1个基变量。,3、如果产量ai（i=1,2,m）和销量bj（j=1,2,n）都是整数，那么任何一个基可行解是整数解。,第三章运输问题,18,产销平衡,运输问题的三种类型,第三章运输问题,19,产大于销,第三章运输问题,20,产小于销,第三章运输问题,21,2运输问题的表上作业法,表上作业法适合于产销平衡的运输问题产销不平衡问题要转化为产销平衡问题求解步骤：（1）求一个初始调运方案（初始基可行解）：在mn维产销平衡表上给出m+n-1个数字。用西北角法、最小元素法、Vogel法（2）判断当前方案是否为最优（最优性检验）：计算各非基变量的检验数，当ij0最优。用闭回路法、位势法（3）方案调整与改进：确定进基变量和离基变量，找出新的基可行解(闭回路调整法)。返回（2）,第三章运输问题,22,1、西北角法（缺点：没有考虑运价）规则：从运输问题的西北角x11开始，优先安排编号小的产地和销地的运输任务例3.2用西北角法求例3.1的一个初始调运方案首先安排A1到B1的运输任务，即从x11开始分配运输量，并使x11取尽可能大的数值。x11=mina1,b1=min5,2=2这时，A1还剩5-2=3个单位物资，将3填到a1的修正量处；B1接收到2个单位物资后，它的销量已得到满足，b1的修正量为0，A2，A3不能将物资运往B1（x21=x31=0），称第一列已饱和，划去第一列（见下表），重复上述过程,一、初始方案的确定,第三章运输问题,23,2,3,0,1,0,2,2,0,1,1,1,0,1,0,3,3,0,0,初始解为：x11=2,x12=1,x13=2,x23=1,x24=1,x34=3，其余变量为0相应的目标函数值z=62+21+32+51+41+73=50,第三章运输问题,24,西北角法的注意事项：,(1)在填入一个数时，如果行和列同时饱和，规定只划去一行或一列，这时行和列的修正量均为0.(2)在剩下最后一个空格时，只能填数（必要时可取0），并划去所在的行和列。(3)在某一行（或列）填最后一个数时，如果行和列同时饱和，则规定只划去该行（或列）。,第三章运输问题,25,2、最小元素法规则：优先安排单位运价最小的产地和销地的运输任务例3.3用最小元素法求例3.1的一个初始调运方案首先从运输表（cij）上的最小元素所处的格子开始分配（若有几个格子同时达到最小值，则任取其中一个），其余作法与西北角法基本一致。第一个最小的元素是2，在c12，c33上取到，先分配x12，并使x12取尽可能大的数值。x12=mina1,b2=min5,1=1这时，A1还剩5-1=4个单位物资，将4填到a1的修正量处；B2接收到1个单位物资后，它的销量已得到满足，b2的修正量为0，A2，A3不能将物资运往B2（x22=x32=0），称第二列已饱和，划去第二列（见下表）。在剩下的运价中找最小元素，重复上述过程。,一、初始方案的确定,第三章运输问题,26,0,4,0,1,0,2,2,0,3,0,2,0,2,2,0,初始解为：x11=2,x12=1,x14=2,x24=2,x31=0,x33=3，其余变量为0相应的目标函数值z=62+21+52+42+30+23=38,0,第三章运输问题,27,3、Vogel法（元素差额法）规则：不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列差)，也称为罚数。罚数不大，说明不能按最小运费调运时，造成的运费损失不大；罚数越大，说明不能按最小运费调运时，运费增加越多，应尽量安排用最小运费调运。,一、初始方案的确定,第三章运输问题,28,例3.4用Vogel法求例3.1的一个初始调运方案找出运输表（cij）上每行运价的最小元素和次小元素，计算其差额，填入表右边差额栏的第一列；对每列也如此处理（见下表）,1,1,1,3,6,1,1,第三章运输问题,29,在第一列差额和第一行差额中选出差额最大者，并对该最大差额所在的行（或列）中的最小元素进行分配（方法与最小元素法相同），如果出现几个相同的最大差额的行或列，则从中任取一行或一列进行分配。本例中的最大差额是6，出现在B2列，B2列中的最小元素是c12=2，先分配x12，并使x12取尽可能大的数值。x12=mina1,b2=min5,1=1这时，A1还剩5-1=4个单位物资；B2接收到1个单位物资后，它的销量已得到满足，第二列已饱和，划去第二列（见下表）。重新计算差额，重复上述过程。,第三章运输问题,30,1,1,1,3,6,1,1,1,2,1,1,3,1,1,2,2,1,5,1,1,1,2,1,2,1,2,0,0,1,2,2,初始解为：x12=1,x13=2,x14=2,x24=2,x31=2,x33=1，其余变量为0相应的目标函数值z=21+32+52+42+32+21=34,第三章运输问题,31,定义3.1闭回路,第三章运输问题,32,变量集合x11,x12,x32,x34,x24,x21是一个闭回路。,闭回路的几何特征：每一个顶点格子都是转角点；每一行（或列）若有闭回路的顶点，则有两个顶点；每两个顶点格子的连线都是水平的或垂直的；闭回路中顶点的个数必为偶数。,第三章运输问题,33,定义3.2孤立点定理3.6用最小元素法得到的初始解是运输问题的基可行解，填入数值的格子对应的是基变量。这些基变量不包含任何闭回路。（推论3.3）,例：变量集合x12,x14,x21,x24,x25,x32，x21是孤立点。因为x21是第一列的所有变量中，出现在变量集中唯一的变量。,第三章运输问题,34,二、最优性检验,判别方法是计算非基变量的检验数：ij=cijCBPij=cijCBB-1Pij运输问题的目标函数要求为最小，即当ij0视为最优。计算检验数的方法（1）闭回路法（2）位势法,第三章运输问题,35,二、最优性检验,1、闭回路法例3.5用闭回路法求例3.3中用最小元素法得到的初始基可行解对应的检验数。,从表中的每一空格出发作一条闭回路，并要求该闭回路上的其余顶点均为基变量。例如：从x13出发可以作唯一的一条闭回路x13,x33,x31,x11,0,1,2,3,2,2,非基变量x13的检验数：13=c13-c33+c31-c11=3-2+3-6=-2,第三章运输问题,36,0,1,2,3,2,2,非基变量的检验数0说明不是最优解,非基变量的检验数列入下表,非基变量x13的检验数12=-2，即让非基变量x13从0增到1，可使总运费减少2个单位。,第三章运输问题,37,二、最优性检验,2、位势法(对偶变量法)计算检验数ij=cijcBPij=cijcBB-1Pijij=cij(ui+vj)ui代表产地Ai的位势量，vj代表销地Bj的位势量。基变量的检验数为0，即ij=cijuivj=0，并令u1=0，计算各行各列的位势量。,第三章运输问题,38,二、最优性检验,2、位势法例3.6用位势法求例3.2中用西北角法得到的初始基可行解对应的检验数。（1）在表上增加一行一列，分别用来记录位势ui和vj利用基变量的检验数为0，即ij=cijuivj=0令u1=0求出ui和vj的值（2）计算非基变量的检验数,第三章运输问题,39,2,1,2,1,1,3,基变量的检验数为0，即ij=cijuivj=0,11=6u1v1=0,12=2u1v2=0,13=3u1v3=0,23=5u2v3=0,24=4u2v4=0,34=7u3v4=0,令u1=0,6,0,2,3,2,2,5,易求出v1=6，v2=2，v3=3，u2=2，v4=2，u3=5,第三章运输问题,40,u1=0，u2=2，u3=5，v1=6，v2=2，v3=3，v4=2,非基变量的检验数：,14=c14u1v4=502=3,21=c21u2v1=726=-1,22=c22u2v2=822=4,31=c31u3v1=356=-8,32=c32u3v2=952=2,33=c33u3v3=253=-6,第三章运输问题,41,三、基可行解的改进（闭回路调整法）,（1）确定进基变量检查非基变量xij的检验数ij，按minij|ij0=lk确定xlk进基。（2）确定出基变量非基变量xlk进基之后，能让它的运量增加多少呢？就要求它所在行和列的运量保持产销平衡。保持产销平衡的方法是闭回路调整法。闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90，继续前进，直到返回始点。奇偶点：始点是奇点，依次奇偶相间标注；奇点标“+”，表示运量增加量；偶点标“-”，表示运量减少量。调整量：最小可减少的运量，即偶点运量的最小值。偶点运量的最小值所在格的基变量出基。,例3.7对例3.5继续求解。,第三章运输问题,42,0,1,2,3,2,2,非基变量x13的检验数12=-2，即让非基变量x13从0增到1，可使总运费减少2个单位。x13为进基变量,第三章运输问题,43,0,1,2,3,2,2,(+),(+),(-),(-),偶点运量的最小值所在格的基变量出基。=minx11,x33=min2,3=2，x11为出基变量,x13为进基变量，从进基变量所在格开始画闭回路,在闭回路上进行调整：x13=0+=0+2=2x33=3-=32=1x31=0+=0+2=2x11=2-=22=0,第三章运输问题,44,2,1,2,1,2,调整后的解,2,再用位势法计算检验数，判断是否得到最优解。,第三章运输问题,45,1,2,2,2,1,基变量的检验数为0，即ij=cijuivj=0,12=2u1v2=0,13=3u1v3=0,14=5u1v4=0,24=4u2v4=0,31=3u3v1=0,33=2u3v3=0,令u1=0,4,0,2,3,-1,5,-1,易求出v2=2，v3=3，v4=5，u2=-1，u3=-1，v1=4,2,第三章运输问题,46,u1=0，u2=-1，u3=-1，v1=4，v2=2，v3=3，v4=5,非基变量的检验数：,11=c11u1v1=604=2,21=c21u2v1=7(-1)4=4,22=c22u2v2=8(-1)2=7,23=c23u2v3=5(-1)3=3,32=c32u3v2=9(-1)2=8,34=c34u3v4=7(-1)5=3,所有非基变量xij的检验数ij0，即得最优解。,最优解为：x*12=1,x*13=2,x*14=2,x*24=2,x*31=2,x*33=1，其余变量为0最优目标函数值z*=21+32+52+42+32+21=34,第三章运输问题,47,第三章运输问题,48,例3.8P85,已知某物资的产量、销量、运价如下表所示，用表上作业法求最优调运方案。,先用最小元素法求初始基可行解；用位势法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。,第三章运输问题,49,0,15,0,初始解为：x12=15,x21=0,x22=0,x23=15,x24=10,x31=5，其余变量为0相应的目标函数值z=215+120+70+915+2010+25=375,用最小元素法求初始基可行解,0,5,0,0,15,10,0,0,10,0,0,第三章运输问题,50,0,0,15,10,5,基变量的检验数为0，即ij=cijuivj=0,12=2u1v2=0,21=12u2v1=0,22=7u2v2=0,23=9u2v3=0,24=20u2v4=0,31=2u3v1=0,令u1=0,7,0,2,4,5,15,-5,易求出v1=7，v2=2，v3=4，v4=15，u2=5，u3=-5,用位势法求出非基变量的检验数,15,第三章运输问题,51,u1=0，u2=5，u3=-5，v1=7，v2=2，v3=4，v4=15,非基变量的检验数：,11=c11u1v1=1007=3,13=c13u1v3=2004=16,14=c14u1v4=11015=-4,32=c32u3v2=14(-5)2=17,33=c33u3v3=16(-5)4=17,34=c34u3v4=18(-5)15=8,14=-40,说明初始解不是最优解,第三章运输问题,52,(+),(+),(-),(-),偶点运量的最小值所在格的基变量出基。=minx12,x24=min15,10=10，x24为出基变量,14=-4x14为进基变量，从进基变量所在格开始画闭回路,在闭回路上进行调整：x14=0+=0+10=10 x24=10-=1010=0 x22=0+=0+10=10 x12=15-=1510=5,15,0,0,15,10,5,闭回路调整,第三章运输问题,53,5,5,0,10,调整后的解,15,再用位势法计算检验数，判断是否得到最优解。,10,第三章运输问题,54,基变量的检验数为0，即ij=cijuivj=0,12=2u1v2=0,14=11u1v4=0,21=12u2v1=0,22=7u2v2=0,23=9u2v3=0,31=2u3v1=0,令u1=0,vj,ui,5,5,0,10,15,10,0,2,11,5,7,4,-5,易求出v1=7，v2=2，v3=4，v4=11，u2=5，u3=-5,第三章运输问题,55,u1=0，u2=5，u3=-5，v1=7，v2=2，v3=4，v4=11,非基变量的检验数：,11=c11u1v1=1007=3,13=c13u1v3=2004=16,24=c24u2v4=20511=4,32=c32u3v2=14(-5)2=17,33=c33u3v3=16(-5)4=17,34=c34u3v4=18(-5)11=12,所有非基变量xij的检验数ij0，即得最优解。（唯一最优解）,最优解为：x*12=5,x*14=10,x*21=0,x*22=10,x*23=15,x*31=5，其余变量为0最优目标函数值z*=25+1110+120+710+915+25=335,第三章运输问题,56,表上作业法计算中的问题,在用闭回路法调整时，在闭回路上出现两个和两个以上的具有（-）标记的相等最小值，这时只能选择其中一个作为出基变量，这时另一个数字格必须填入0，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为（-）的取值为0的数字格，这时取调整量=0,第三章运输问题,57,四、产销不平衡问题,产销平衡的运输问题采取表上作业法求解。产销不平衡的运输问题需转化为产销平衡问题再求解。产大于销：虚设一个销地Bk(多于物资在产地存储)，其运价为0，销量(存储量)为产销量之差bk=ai-bj。产小于销：虚设一个产地Al(不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差ak=bj-ai。,第三章运输问题,58,产大于销,方法是先将原问题变成平衡问题，需假设一个销地Bn+1(实际上考虑产地的存量)，单位运价表中的单位运价为,第三章运输问题,59,思考：如果存贮需要费用（单位物资存贮费已知），该如何处理？,第三章运输问题,60,产小于销,方法是先将原问题变成平衡问题，需假设一个产地Am+1(实际上考虑销地的脱销量)，单位运价表中的单位运价为,第三章运输问题,61,思考：如果缺货要承担损失费（单位物资缺货损失费已知），该如何处理？,第三章运输问题,62,3运输问题应用举例,例3.10例3.11例3.12,第三章运输问题,63,一、短缺资源的分配问题（产销）练习1.石家庄北方研究院有一、二、三三个区，每年分别需要用煤3000、1000、2000吨，由山西盂县、河北临城两处煤矿负责供应，这两处煤矿的价格与煤的质量相同。供应能力分别为4000、1500吨，运输单价为：,由于需求大于供给，经院研究决定一区供应量可减少0200吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。解：这是一个销大于产的产销不平衡的运输问题。为了化成产销平衡运输问题，我们增加一个假想的生产点，产量为500。,第三章运输问题,64,并根据需求量(必须满足和可以不满足)将一区分成两个区，其调运量分别为2800和200；运价分别为M和0，将三区也分成两个区，其调运量分别为1700和300；运价分别为M和0，这里M代表一个很大的正数，其作用是强迫假想的生产点调运到必须满足区的调运量为0。增加后的产销平衡与运价表为：,利用表上作业法,得到最优解：x*11=1300，x*13=1000，x*14=1700，x*21=1500，x*32=200，x*35=300，其余变量都为0；最低运费z*=9220，,第三章运输问题,65,练习2.光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用如下表：,二、生产与储存问题（产销）,又已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7至8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1至6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？,第三章运输问题,66,解：这个生产存储问题可化为运输问题来考虑。把各月的生产与交货分别视为产地和销地，分别考虑如下：1）1至6月份合计生产能力(包括上年末储存量)为743台，销量为707台，产大于销36台，为此，虚设一个销地(仓库)其销量实为不安排生产的剩余生产能力(36台)；2）上年末库存103台，只有仓储费和运输费，我们把它列在序号0行里；3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4）产销平衡与运价表中，生产时间中的序号16表示16月份正常生产情况，序号