管理运筹学讲义第7讲运输问题

1中山大学南方学院工商管理系王甜源第7讲运输问题2运输问题及其数学模型表上作业法产销不平衡的运输问题目录3在线性规划问题中，有一类特殊类型的问题－－运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。4但是由于在运输问题的数学模型中，约束方程的系数矩阵具有特殊的结构。因此，存在一种比单纯形法更为简便的方法——表上作业法。表上作业法通过定制的运输表确定最优调运方案，但其本质仍然是单纯形法，其主要步骤是：首先需要确定一个初始调运方案（初始基本可行解），然后检验现行调运方案（现行基本可行解）是否最优，若非最优，则需对现行调运方案（现行基本可行解）进行改进等几个阶段。只是表上作业法对单纯形法作了适当的修改，从而提高了计算的效率。5运输问题的一般提法是：某种物质（粮食、棉花、煤炭等）有m个产地，其产量是；有n个销地,其销量（或需求量）是。现在需要把这种物质从m个产地运送到n个销地。若从运到的单位运价为。又限定产销平衡，即，问应如何制定调运方案可使总费用最小？iA(i=1,2m)ia(i=1,2m)jB(j=1,2n)jb(j=1,2n)iAjBmniji=1j=1a=b运输问题及其数学模型6上述已知条件可用下面的表格来表示。销量产量销地产地1B2BnB1A2AmA1b2bnb1mc2mcmnc21c22c2nc11c12c1nc1a2amaminjjiba117如果用代表从第ｉ产地运往第ｊ销地的物质单位数量（i=1，2m；j＝1，2n），Ｚ为总运费，那么求解上述使总运费最小的运输问题。可以用下列数学模型描述：ijxmnijiji=1j=1nijij=1mijji=1ijminZ=cxx=ai=1,2m.x=bj=1,2n..x0,i=1,2,,m;j=1,2,,n从每一个产地运往各个销地的物质数量之和等于该产地的产量从各个产地运往每一个销地的物质数量之和等于该销地的销量使总运费达到最小运输量非负8运输问题的线性规划模型具有特殊的结构，其约束方程组的系数矩阵A具有如下形式：m×n个决策变量，m＋n个约束条件。经证明：产销平衡的运输问题的非零变量为m+n-1个。具体证明如下：11121n21222nm1m2mnxxxxxxxxxA=111111111111m行n行111111nijij=1mijji=1x=ai=1,2m.x=bj=1,2n.ijx911121n21222nm1m2mnxxxxxxxxxA=111111111111m行n行111111该矩阵的元素全部为0或1。每一列只有2个元素为1，其余为0。若用表示决策变量的系数列向量，则在中第i个和第m＋j个元素为1，其余为0。我们也可以用两个单位向量之和来表示。即：其中和分别为第i个元素和第m＋j个元素为1的单位向量。ijPijim+jP=e+eiem+je10通过对运输问题的数学模型约束矩阵Ａ的特殊结构作进一步分析，还可以发现矩阵Ａ的秩为m＋n－1，即Ｒ(Ａ)＝m+n-1。这是因为系数矩阵A的前m个行向量之和减去后n个行向量之和恰好为零向量。即矩阵Ａ的m＋n个行向量线性相关。因此Ｒ(Ａ)m＋n。再将矩阵A的第2,3,…m+n行与所对应的列的交叉处的元素构成一个m＋n－1阶子式。11111111D=11nm-1m-1n11121n21222nm1m2mnxxxxxxxxx111111111111111111•表上作业法是单纯形法在求解运输问题的一种简便方法。•单纯形法与表上作业法的关系：（1）用最小元素法或伏格尔法找出初始基可行解（2）用闭回路法求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同表上作业法换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否13确定初始基本可行解求运输问题的初始基本可行解有多种方法。在此我们只介绍最小元素法和伏格尔法两种方法。为了确定初始基本可行解，首先必须画出运输问题的基本表格。即调运表和运价表。销地产地产量销量销地产地1B2BnB1A2AmA1b2bnb2ama1A2AmA1B2BnB11c12c1nc21c22c2nc1mc2mcmnc调运表运价表14在实际计算中，为了方便通常将调运表和运价表合二为一，综合为下列运输表。销地产地产量c11c12c1nc21c22c2ncm1cm2cmn销量1B1A2AmA2BnB1b2bnb1a2ama运输表151，最小元素法最小元素法的基本思路是以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开始确定供销关系。若产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。反之，若产量小于销售量。则把加工厂的日产量全部分配给对应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。依次类推，逐步推出初始方案。由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始基本可行解通常比较接近最优解。经过若干次调整即可求得最优解。运输问题•最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格——即一组可行解，这里叫初始基。运输问题最小元素法例141228543961111104814121482210163214321AAABBBB销量产量822010100614868000060运输问题最小元素法例141228543961111104814121482210163214321AAABBBB销量产量821014682466811632410514280z最小元素法缺点：会出现顾此失彼（运费差额问题）考虑运价差19例2，某公司经销甲产品。下设三个加工厂Ａ1，Ａ2，Ａ3，每天把产品分别运往四个销地Ｂ1，Ｂ2，Ｂ3，Ｂ4。各加工厂的日产量，各销地的日销量以及从各加工厂运送单位产品至各销售地的运价如下表：销地产地B1B2B3B4日产量（吨）A13113107A219284A3741059日销量（吨）3656单位：千元/吨问该公司应如何确定调运方案，在满足各销地需求量的前提下可使得总运费最小？206563销量（吨）951047A3482913A27103113A1产量（吨）B4B3B2B1销售地加工厂①为了用最小元素法确定初始基本可行解，可先画出综合运输表。然后按以下步骤确定初始调运方案。①从全部单位运价中找出最低单位运价（若有两个以上最低单位运价，则可在其中任选其一）。然后比较最低运价所对应的加工厂的日产量和销地的日销量，并且确定第一笔供销关系。-3216563销量（吨）951047A34821913A27103113A1产量（吨）B4B3B2B1销售地加工厂①-3②在未被划去的单位运价中再找寻最低运价，比较最低运价对应的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确定供销关系。基本原则与①中描述过程相同。②-1226563销量（吨）95310467A34821913A2710334113A1产量（吨）B4B3B2B1销售地加工厂①-3-1重复步骤②可逐个确定从加工厂到销地的供销关系。基本原则是在空格内内每填入一个调运量必须划去一行或一列。填入最后一个调运量后则同时划去一行和一列．这样在运输表中共计填入了m＋n－1个数字。这些数字对应了一个初始基本可行解。④-6③-4⑤②-3236563销量（吨）95310467A34821913A2710334113A1产量（吨）B4B3B2B1销售地加工厂①-3-1③-6④-4⑤②-3131421233234x=4,x=3,x=3,x=1,x=6,x3所填入的m＋n－1＝3＋4－1＝6个数字为对应初始基本可行解的6个初始基变量的值。即对应的总运费为Z＝4×3＋3×10＋3×1＋1×2＋6×4＋3×5＝86（千元）24必须补充说明的是：利用最小元素法确定初始调运方案过程中，可能出现最低单位运价对应的产地的产量和销地的销量恰好相等的情形。此时在运输表中填入一个数字后，必须同时划去产地所在行和销地所在列，这和每填入一个数字只划一条直线的基本原则相违背（最后一个数字除外）。这时我们称运输问题出现了退化。为了使运输表中有m＋n－1个数字格。需要添加一个“0”调运量，它的位置可在同时划去的那行或那列的任一空格处。这个“0”调运量是不可缺少的。因为运输问题的基本解中基变量的个数必须是m＋n－1个。不能多，也不能少。出现了数字为0的数字格只是说明在初始基本可行解中有一个基变量为零。即该初始基本可行解是退化解。252，伏格尔法（Vogel）最小元素法给定初始调整方案是以局部观点考虑运价最低者优先的原则。这可能造成整体的不合理。因为可能存在这样的情形：某单位运价在整个单位运价表中可能并不是最低的，但是它在所在行（或所在列）中是最低运价，而且它与同行（或同列）中的次最低运价相差非常显著。因此就该行（或该列）而言，如果我们不慎采用了次最低运价，而不是最低运价，那么总运费就会惩罚性地增加。我们通常把每行或每列的次最低运价与最低运价之差额称为罚金成本（Penaltycost）。为了避免在总运费总增加过多的罚金成本。伏格尔法确定初始基本可行解的基本思路是：罚金成本最高的行或列中运价最低者优先考虑。即：罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。伏格尔法思路：•结合例1说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量行罚数①04-4=0第一次•结合例1说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量行罚数①013-2=1第一次•结合例1说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量行罚数①011第一次•结合例1说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量行罚数①011列罚数4-2=22153①第一次•结合例1说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量行罚数①011列罚数2153①1480优先安排销地，否则运价会更高2B下次不考虑该列第一次第二次•结合例1说明这种方法。行罚数②012列罚数213②优先安排销地，否则运价会更高4B84814121482210163214321AAABBBB4122854396111110销量产量148006下次不考虑该行•结合例1说明这种方法。行罚数③01列罚数212③84814121482210163214321AAABBBB4122854396111110销量产量148006下次不考虑该列802第三次运输问题•结合例1说明这种方法。行罚数④76列罚数12④84814121482210163214321AAABBBB4122854396111110销量产量1480068024120下次不考虑该列第四次