管理运筹学02-7运输问题

1、Transportation Model第四节运输问题一、运输问题及其数学模型二、表上作业法求解运输问题三、产销不平衡的运输问题及应用运输问题及其数学模型问题的提出运输问题：产地、销地、产量、销量例1有A1，A2，A3三座铁矿，每天要把生产的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？3运输问题及其数学模型(百元/百吨 )4z 总运费（百元）xij Ai运给Bj的铁矿石数量（百吨）B1B2B3B4产量A1 A2 A3632575843297523销量2314运输问题及其数学模型(百元/百吨 )5B1B2B3B4

2、产量A16x113x122x135x145A27x215x228x234x242A33x312x329x337x343销量2314运输问题及其数学模型数学模型为:min z = 6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34x11+x12+x13+x14x21+x22+x23+x24= 5= 2x31+x32+x33+x34 = 3x11+x21+x31= 2= 3= 1s.t.x12+x22+x32x13+x23+x24j =1, 2, 3, 4 )+x33x14( i =1, 2, 3;+x34 = 4xij06运输模

3、型的特点：(1) 它有mn个变量，m+n个约束方程(2) 其系数阵具有特殊的结构1111m=3行111111111A =11111n=4行1111117运输问题及其数学模型表式模型 产销平衡的运输问题: ai=bj 产大于销的运输问题: aibj 产小于销的运输问题: aibj8B1B2Bn产量A 1c11x11c12x12c1nx1na1A 2c21x21c22x22c2nx2na2Amcm1xm1cm2xm2cmnxm nam销量b1b2bn ai bj运输问题及其数学模型1、运输问题的网络图、线性规划模型及运输表设有同一种货物从m个供应地1，2，m运往n个需求地1，2，n。第i个供应地的

4、供应量（Supply） 0) ，第j个需求地的需求量（Demand）为 si (si 0)。每单位货物从供应地i运到需求地j的为 d j (d j运价为 cij 。求一个使总运费最小的运输方案。如果从任一供应地到任一需求地都有道路通行，这样的运输问题称为完全的运输问题；如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先考虑完全的、供求平衡的运输问题。运输问题及其数学模型d1c11 c1 j c1n ci1cij右图是运输问题的网络表示形式。1s11sid jijcincm1cmjcmnsmmdnn运输问题及其数学模型运输问题也可以用线性规划表示。设 xij为从供应地i运往需

5、求地j的运量，则总运费最小的线性规划问题如下式所示。min z = c11x11 + c12 x12 + + c1n x1n+ c21x21 + c22 x22+ + c2n x2n + + cm1xm1 + cm2 xm2 + + cmn xmn= s1= s2x11 + x12+ + x1nx21 +x22 + +x2nstxn1 + xn2+ xn1+ xn2+ + xmn= sm= d1= d2+ x21x11+ x22x12+ x2n+ xmn= dnx1n 0,1 i m,1 j nxij运输问题及其数学模型运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变

6、量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是供应地的供应量约束，后n个约束是需求地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题及其数学模型在运输问题线性规划模型中，令X = (x11, x12 , x1n , x21, x22 , x2n ,., xm1, xm2 ,xmn )C = (c11, c12 , c1n , c21, c22 , c2n , cm1 , cm 2 ,cmn ) 111L111Lm行LLLL1 11LA= 111O111On列OOOO1 11On列n列n列n列b = (s1 , s

7、2 , , sm , d1 , d2 , , dn )则运输问题的线性规划可以写成：运输问题及其数学模型完全的运输问题系数矩阵A中，列向量 pij中只有两个元素是1，其他元素都是0。第一个1位于矩阵的第i行，第二个1位于矩阵的第m+j行。这个列向量可以表示为两个单位向量之和，即 0 0 0 1 1 0 第i行LLL= = + = ei+ em+ jpijLLL第m + j行 1 0 1 0 0 0 运输问题及其数学模型12n运输问题除了用网络表示及线性规划表示外， 还可以用运输表表示， 见右表。运输表是一个m行n列的表格，每一行对应于一个供应地，每1s12s2一列对应于一个需求地。运输表共有m

8、n个格子，每个格子对应于从一个供应地出发到一个需求地的运输路线。msmdndd12c11c12c1nx11x12x1nc21c22c2 nx21x22x2ncm1cm 2cmnxm1xm 2xmn运输问题及其数学模型上页表中，每一格的左上角小方格内的数字表明从相应的供应地i到需求地j的运价cij，每一格右下角表明从相应的供应地i到需求地j的运量 xij。表右方表明各供应地的供应量si，表下方表明各需求地的需求量d j。每一行运量之和表示从该供应地运往各需求地的运量之和，它应该等于该供应地的供应量；同样，每一列运量之和表示从各供应地运往该需求地的运量之和，它应该等于该需求地的需求量。运输问题及其

9、数学模型 运输问题约束矩阵的性质分别将A的前m行和后n行相加，得到两个相同的mn维向量，其中的元素都是1。即A矩阵的m+n个行向量是线性相关的， 因此A矩阵的秩m+n。运输问题分别从供应地1、2、m到需求地n的m条边以及从供应地1分别到需求地1、2、n-1的n-1条边，一共有m+n-1条边。这m+n-1条边组成运输问题约束矩阵A中的m+n-1个列向量，这些列向量在A矩阵中的子矩阵是一个m+n行， m+n-1列的矩阵 11L1111Lm行LLLL1 11LA= 111O111On行OOOO1 11On列n列n列n列(1,n )1( 2,n) L ( m,n)(1,1) L (1,n-1)11L1

10、m行O删除矩阵B的最后一行，得到1B=1On行可以看出，这是一个上三角矩阵，显然，秩Bm+n-1。由m+n-1=秩B秩A0。由于单纯形叠代在每一步都满足互补松弛条件，因此对于基变量xij0，相应的对偶约束条件ui+vj cij的松弛变量一定等于0，即ui+vj = cij由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1个等式约束，只要先确定一个对偶变量的值，就可以由m+n-1个等式约束确定其余m+n-1个 对偶变量的值。不妨设vn=0，逐个递推求得ui和vj。求出ui、vj的值以后，就可以进一步计算各非基变量的检验数zij- cij =ui+vj- cij 。表上作业法求解运输问题3

11、. 解的改进（1） 确定进基变量由单纯形法原理可以知道，凡检验数zij-cij0的非基变量都可以进基。通常总是选取检验数中最小的对应变量进基。（2） 确定离基变量为保证改进后的解仍为基本可行解，需要保证所有变量的非负性。因此，改进的方法就是从检验数为负数的空格出发，作一条除该空格外其余顶点均为有数字格组成的闭合回路。在这条闭回路上，按对运量作最大可能的调整。表上作业法求解运输问题例 改进表中用最小元素法得到的初始基本可行解。由表可知，x34的检验数是-2，因此可以作为进基变量。选取 变量x34作为进基变量，以其所在的空格为出发点作闭合回路。123430124550342515203184选取变

12、量x34作为进基变量相应的闭合回路10119151511413121694511819710311413121325表上作业法求解运输问题将其改进为新的基本可行解。 则x34增加的同时，x14减少， x12增加，x32增加。为保证变量的非负性，能够减少的最大数量为14。此时，x14减少到0，是出基变量。得到新的基本可行解见下表123410119153012-115152131216945751045118710503453114414131213254222515203184改进后的基本可行解表上作业法求解运输问题上表给出的调运方案是否为最优呢？还需要对这个方案的空格处（非基变量）求出检验数。

13、由于表中x13的检验数为-1，因此对上表进行改进。得到下表。计算表中的检验数。12341101191530311515131216945265104531187105032016141413121325432225152031最优基本可行解84由于检验数表2-38中的所有检验数大于等于0。因此上表是最优方案。表上作业法求解运输问题最优解的目标函数值为z=1015+915+945+820+716+1014+132 5=1427。需要指出的是，有时在闭合回路调整中，在需要减小运量的地方有两个以上相等的最小数，这样调整时原先空格处填上了这个最小数，而有两个以上最小数的地方成了空格。为了保证基变量的个

14、数是m+n-1个，就要把最小数的空格之一变为空格，其余均补填0，补填0的格为有数字格， 对应的变量是基变量。产销不平衡的运输问题及应用mn1供给大于需求的情况，即 si dii=1i=1mni in+1增加一个虚设的需求地，它的需求量为s -d。i=1i=1新增从各供应地到该需求地的运输路线（1，n+1），（2，n+1），（m，n+1），这些运输路线上的运价全部等于0，即c1，n+1=c2，n+1=cm，n+1=0， 这样就将供给大于需求的的问题转化为供求平衡的问题。在新的问题中，从供应地i到新设的需求地n+1的运量，实际上就是存储在供应地i没有运出的数量。新得到的供求平衡的运输问题的最优解，

15、实际上就是各供应地存储多少、运出多少、运往何地，使总运价最低。产销不平衡的运输问题及应用例 设一个供求不平衡的运输问题如下左图。相应的供求平衡问题如图1，2。图1 供求不平衡的运输问题图2 供求不平衡的运输问题产销不平衡的运输问题及应用由于需求地4是虚拟的，因此对应的运价设为0。供求平衡问题的运输表以及最优解如下：123411522510101010调整后的运输表及最优解及检验数表85604105371090102510产销不平衡的运输问题及应用已获得最优解。这个最优解的含义是：从供应地1到需求地2的运量为10，到需求地3 的运量为5，供应量没有剩余；从供应地2 到需求地1的运量为10，到需求

16、地3的运量为5，供应量剩余10；最小运费为 min z=510+65+710+95=195.mn2供给小于需求的情况，即 si dii=1i =1当市场的总需求量大于总供给量时，可以仿照供给大于需求的情况处理。即增加一个假想的mn供应地，产量等于供应不足的部分，即 di- si 。i=1i=1由于假想的供应地并不存在，相应运价就等于0。不限最高最低507060运输模型的应用短缺资源的分配问题自来水分配问题引水管理费水库区甲乙丙丁供水量16013022017050A14013019015060B19020023050C3070010160110301602 005 021059基 本 需求额 外

17、 需求运输模型的应用自来水分配问题的规范表式运输模型60引水区管理费水库甲乙丙丁供水量甲1甲2丁1丁2A160 16013022017017050B140 14013019015015060C190 190200230MM50D (虚)M0M0M050需 求 量302070301050210运输模型的应用 自来水分配问题的最优方案表61分配量区水库甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050脱销302050需求量302070301050210运输模型的应用转运问题面粉转运问题设有A1、A2、A3三个面粉加工厂，每天分别将3、4、3吨面粉运往B1、B2两个糕点厂，而B1

18、、B2每 天分别需要4、6吨面粉。在面粉厂与糕点厂之间有T1、 T2两个中继站。各地间每吨面粉的运价如下表所示。应如何调运使总运费最低？62运输模型的应用63终点始点面 粉 厂中继站糕点厂A1A2A3T1T2B1B2面粉厂A1 A2 A3324223523268137114中继站T1T23523267252糕点厂B1 B2642399运输模型的应用转运站既是始点，又是终点的运地。转化成为有7个假想产地Ai 、7个假想销地Bj的新问题。虚设一个统一转运量t，应有t max ( ai ， bj)12本例故可取作 ai = bj = 10t = 10假想产地Ai的产量ai+t， Ai 是转运站a =ai ，64否则i运输模型的应用假想销地Bj 的销量bj+t， Bj 是转运站b =bj ，否则j本例取作ai = ai + 10bj = bj+ 10虚设 xi