第三部分运输问题

§3.1运输问题与有关概念§3.2运输问题的求解—表上作业法本章主要内容第三章运输问题§3.1运输问题模型及有关概念问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案.销地产地B1B2B3产量A1646200A2655300销量150150200例3.1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：销地产地B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij0(i=1,2；j=1,2,3）系数矩阵111000000111100100010010001001模型系数矩阵特征1.共有2+3行，分别表示各产地和销地；23列，分别表示各变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。例3.2某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示销地产地B1B2B3B4产量A13113107A219284A3741059销量365620（产销平衡）问应如何调运，可使得总运输费最小?解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3；j=1，2，3，4）所以此运输问题的线性规划模型如下：Minf=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x24=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3；j=1,2,3)其系数矩阵为：100010001000010001000100001000100010000100010001111100000000000011110000000000001111A共有3+4行，分别表示产地和销地；有34列分别表示各变量；每列只有两个1，其余为0。一般运输问题的提法：假设A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物资的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。如果a1+a2+…+am=b1+b2+…+bn，则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论一般运输问题。销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am销量b1b2…bn解：设xij为从产地Ai运往销地Bj的运输量ijminjijxcf11minmiaxtsinjij,,2,1)(..1njbxjmiij,,2,1),(1njmixij,,2,1,,2,10对于产销平衡问题，可得到下列运输问题的模型：ijminjijxcf11minmiaxtsinjij,,2,1..1njbxjmiij,,2,11njmixij,,2,1,,2,10在实际问题建模时，还会出现如下一些变化：①有时目标函数求最大，如求利润最大或营业额最大等；②当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；③产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在产量约束条件中加上m个松弛变量；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在需求约束条件中减去n个松弛变量。运输问题求解的有关概念1、基变量的特点（1）基变量共有m+n-1个（2）产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路.运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图2-1所示.由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算,则无法利用这些有利条件.人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法.在这里需要讨论基本可行解、检验数以及基的转换等问题.基本可行解是否最优解结束换基是否图2-1运输问题的求解思路定义3.1决策变量格凡是能够排列成下列形式xab,xac,xdc，xde,…,xst,xsb（3.1）或xab,xcb,xcd,xed,…,xst,xat(3.2)其中，a,d,…,s各不相同；b,c,…,t各不相同。我们称之为变量集合的一个闭回路，并将式（3.1）,（3.2）中的变量称为这个闭回路的顶点.例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x22；x11,x14,x34,x31等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：闭回路示意图①闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；②闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。关于闭回路有如下的一些重要结论：根据定义可以看出闭回路的一些明显特点:：①设xab,xac,xdc,xde,…,xst,xsb是一个闭回路，那么该闭回路中变量所对应的系数列向量Pab,pac,pdc,pde,…,pst,psb线性相关；②若变量组xab,xcd,xef,…,xst中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量pab,pcd,pef,…,pst线性相关.定理3.1变量组xab,xcd,xef,…,xst所对应的系数列向量pab,pcd,pef,…,pst线性无关的充分必要条件是这个变量组中不包含闭回路.推论产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是它不含闭回路.§3.2运输问题求解——表上作业法步骤如下：①在运输问题求解作业数据表中任选一个单元格xij(Ai行Bj列交叉位置上的格)，令xij=min{ai,bj}一、初始基本可行解的确定即考虑从Ai向Bj的最大运输量(使行或列在允许的范围内尽量饱和,即使一个约束方程得以满足)，填入xij的相应位置；②从ai或bj中分别减去xij的值，即调整Ai的拥有量及Bj的需求量；③若ai=0，则划去对应的行（把拥有的量全部运走），若bj=0则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；④若运输平衡表中所有的行与列均被划去，则转②.按照上述方法所产生的一组变量的取值将满足下面条件：①所得的变量均为非负，且变量总数恰好为m+n–1个；得到了一个初始基本可行解.否则，在剩下的运输平衡表中选下一个变量，②所有的约束条件均得到满足；③所得的变量不构成闭回路.因此，根据定理3.1及其推论，所得的解一定是运输问题的基本可行解.一般较常用的方法有西北角法、最小元素法和差额法。下面分别举例予以说明.1、西北角法（左上角方法）例3.3考虑例3.2某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：销地产地B1B2B3B4产量A13113107A219284A3741059销量365620问应如何调运，可使得总运输费最小?销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620342236产销平衡表运价表z=3×3+4×11+2×9+2×2+3×10+6×5=1352.最小元素法。例3．4（运价小者先安排）销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103产销平衡表运价表z=4×3+3×10+3×1+1×2+6×4+3×5=863.差额法（次小运价与最小运价之差大者先安排）销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620产销平衡表运价表251301160123212376512z=5×3+2×10+3×1+1×8+6×4+3×5=85上述计算过程可用流程图描述如下（图2-2）取未划去的单元格xij,令xij=min{ai,bj}ai’=ai-xijbj’=bj-xijai’=0?划去第i行划去第j列是否bj’=0否所有行列是否均被划去是找到初始基本可行解图3-2求运输问题的初始基本可行解过程注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个0.例3.5某公司下属有生产一种化工产品的三个产地A1、A2、A3,有四个销售点B1、B2、B3、B4销售这种化工产品.各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费(百元)如下表所示.销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195产销平衡表运价表问应如何调运，可使得总运输费最小?解：用西北角法求初始基本可行解销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195产销平衡表运价表35400401565z=35×3+40×8+40×4+15×7+65×5=1015销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求35405565195产销平衡表运价表23534045550540925z=50×5+25×9+35×2+5×4+40×3+40×5=885产销平衡表运价表销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求354055651951513340540335224224214401525z=35×3+15×5+25×9+40×4+40×3+40×5=885111练习：求解以下列数据为单位运费的运输问题(1)销地产地甲乙丙丁产量1105672528276253934850销量15203035100销地产地甲乙丙丁戊产量12545330234175203219872045436830销量1015252030100(2)销地产地甲乙丙丁产量125225350销量15203035100甲乙丙丁1056782769348销地产地甲乙丙丁产量125225350销量15203035100甲乙丙丁1056782769348销地产地甲乙丙丁产量125225350销量15203035100甲乙丙丁1056782769348销地产地甲乙丙丁戊产量130220320430销量1015252030100甲乙丙丁戊25453341752198754368销地产地甲乙丙丁戊产量130220320430销量1015252030100甲乙丙丁戊25453341752198754368销地产地甲乙丙丁戊产量130220320430销量1015252030100甲乙丙丁戊25453341752198754368二、基本可行解的最优性检验由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案.1.位势法首先给出位势概念：设对应m+n-1个基变量xij的系数cij，