工学第6章运输问题课件

1、6 运输问题 运输问题的数学模型 运输问题及其基的特征 表上作业法 产销不平衡的运输问题 转运问题 运输问题的应用矿业系统工程电子教案x2x1zo7/27/20221运输问题6.1 运输问题的数学模型7/27/20222运输问题考察问题 例6.1 某公司经营一种产品，它下设三个加工厂和四个销售点。三个加工厂 A1 , A2 , A3 的产量分别为 7 吨，5 吨，9 吨；四个销售点 B1 , B2 , B3 , B4 的销量分别为 3 吨，6 吨，6 吨，6 吨。从各加工厂到各销售点的每吨产品的运费如表6.1所示。问该公司应如何调运产品，使总运费最小。 设 xij 为从加工厂 Ai 到销售点

2、Bj 的产品运输量 ( i=1, 2, 3; j=1, 2, 3, 4 )，将产销量和所有可能安排的运输量列于表6.2，则上述问题可形成一个数学问题。7/27/20223运输问题问题的数学形式min z =5x11+11x12+3x13+9x13 + x21+10 x22+2x23+6x24 +8x31+4x32 +7x33+5x34s.t. x11+ x12 + x13 + x14 =7 x21+ x22 + x23 + x24 =5 x31+ x32 + x33 + x34 =9 x11 + x21 + x31 = 3 x12 + x22 + x32 = 6 x13 + x23 + x33

3、 = 6 x14 + x24 + x33 = 6 xij 0 , i , j表6.1 单位运价表表6.2 产销平衡表7/27/20224运输问题运输问题的一般描述 某种物资有 m 个产地 (也称为“发点”或“源”)和 n 个销地 (也称为“收点”或“汇”) ，第 i 个产地 Ai 的产量为 ai，i =1, 2, , m，第 j 个销地 Bj 的销量为 bj，j = 1, 2, , n，从 Ai 到 Bj 的单位物资运价为 cij。问在产销平衡的条件下，如何确定总运费最小的物资调运方案。 设 xij 为从产地 Ai 到销地 Bj 的物资运输量，则上述问题可归结为一个线性规划问题。7/27/20

4、225运输问题表6.3 单位运价表7/27/20226运输问题表6.4 产销平衡表7/27/20227运输问题运输问题的模型s.t. x11+x12 +x1n=a1 x21+x22 +x2n=a2 xm1+xm2+xmn=am x11+x21 +xm1=b1 x12+x22 +xm2=b2 x1n+x2n+xmn=bn xij 0 , i , jijijxcmin z =nj1=mi1=7/27/20228运输问题数学模型的两种形式s.t. x11+x12 +x1n=a1 x21+x22 +x2n=a2 xm1+xm2+xmn=am x11+x21 +xm1=b1 x12+x22 +xm2=b

5、2 x1n+x2n+xmn=bn xij 0 , i , jijijxcmin z =nj1=mi1=ijijxcmin z =nj1=mi1=xij 0 , i , jaxiij=nj1=mi1=s.t.,nj1=bxjij=mi1=,=njjb1=miia1ijxnj1=mi1=7/27/20229运输问题表6.5 运输表7/27/202210运输问题表6.6 运输表(综合表)7/27/202211运输问题表6.7 例6.1的运输表7/27/202212运输问题表6.8 例6.1的综合运输表7/27/202213运输问题6.2 运输问题及其基的特征7/27/202214运输问题6.2.1

6、运输问题的解 与一般线性规划问题不同，产销平衡的运输问题一定存在可行解。因有 则存在可行解 xij 0 = ai bj /Q , i , j 又因 0 xij min ai ,bj 所以运输问题必存在最优解。=njjb1=miia1= Q7/27/202215运输问题运输问题解的特性 运输问题还有一个重要的性质，若产销量 ai 和 bj都是整数，则必存在整数最优解。因此，将某些整数规划问题化为运输问题来求解，即便不用整数限制条件，结果可自然满足整数要求。在“整数规划”一章中，将会看到求解整数规划问题相当费事，而运输问题解的特性给求解某些整数规划问题带来了很大方便。7/27/202216运输问题

7、6.2.2 运输问题的形式特征 运输问题的数学模型具有下列特征：方程组中所有变量的系数皆为 1和 0 ；任何一个变量 xij 在前 m 个方程中以系数 1 出现一次，在后 n 个方程也以系数 1 出现一次；由于要求 ai = bj ，这 (m+n) 个方程是线性相关的。如果从中去掉一个方程 ,剩下的 (m+n-1) 个方程线性无关。7/27/202217运输问题运输问题的系数矩阵(单模)或幺模m行n行7/27/202218运输问题系数矩阵的秩假设 m , n 2，则有 m +n m n ，于是矩阵 A 的秩小于或等于m+n。但是A的秩不等于m +n ，这是因为 A 的前 m 行之和恰好等于后

8、n 行之和，所以 A 的 m +n 行是线性相关的。因此，A 的秩小于或等于 m + n -1对于运输问题的约束方程的增广矩阵A（就是由矩阵A再增添一列约束方程组的右端项所组成的(m+n)(m+n-1)阶矩阵），也有A的秩 = m+n-1.7/27/202219运输问题001001000010000000000100第 i 行第 m+j 行系数矩阵列向量的结构 系数矩阵每一列的元素只有两个1，其余都为0。 Pij = ei + em+j7/27/202220运输问题6.2.3 运输问题的基 同一般的线性规划问题一样，运输问题的最优解一定可以在基可行解中找到。因此，继考察了约束方程组的系数矩阵之

9、后，还要进一步研究运输问题的基及其基变量所具有的特征。 7/27/202221运输问题 由上面的讨论可知，运输问题基变量的数目应该是 m+n -1 个，接下来研究怎样的 m +n -1 个变量 可以组成基变量。或者说，怎样的 m +n -1 个变量 (s =m+n-1) 对应的系数列向量 (s =m+n-1) 是线性无关的。 下面引入有关闭回路的概念，它有助于分析和解决上述问题。基变量与基向量sssjijijijijijixxxxxx122111211, (s =m+n-1)ssjijijiPPP2211,ssjijijixxx2211,7/27/202222运输问题闭回路及其形式x1 1 ,

10、 x1 3 , x3 3 , x3 17/27/202223运输问题闭回路的定义 定义6.1 凡是能排成 ( i1 , i2 , , is 互不相同, j1 , j2 , , js 互不相同 ) 形式的变量的集合称为一个闭回路，而把出现在(1) 中的变量称为这个闭回路的顶点(或拐角点)，相邻两顶点的连线称为闭回路的边。(1)132222111,jijijijijijisssxxxxxx7/27/202224运输问题闭回路的形式之二 x1 1 , x1 2 , x3 2 , x3 4 , x2 4 , x2 1 7/27/202225运输问题闭回路的形式之三7/27/202226运输问题闭回路的

11、特点 从上面几个闭回路的例子中不难看出，如果把一个闭回路的所有顶点都在表上画出，并且把相邻的顶点用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的，即折线是由交替的水平和垂直（联接的）线段组成。另外，在表中的每一行和每一列中，至多只有闭回路的两个顶点；对一条闭回路是按顺时针方向还是逆时针方向是无关紧要的。7/27/202227运输问题 性质6.1 若有一闭回路 则 证 根据列向量的特征 Pij = ei + em+j 可得闭回路及其性质132222111-+-+-jijijijijijisssPPPPPP= 0132222111-+-+-jijijijiji

12、jisssPPPPPP()+jmiee32-()+jmiee22-= ()+jmiee11+()+jmiee21-()+jmieess+ += 0()+jmiee1s1ssjijijijijijixxxxxxs32222111,7/27/202228运输问题srrjijijijijijixxxxxx122111211,(6. 2)122112111- , , ,+-jijijijijijisrrPPPPPP = 0闭回路与列向量 性质6.2 若变量组 中有一部分组成闭回路，则(6. 2)对应的列向量 是线性相关的。 证 性质6.1表明构成闭回路的变量组对应的列向量组是线性相关的，而向量组中有一

13、部分线性相关，则全体也线性相关。 性质6.2说明：若变量组(6. 2)对应的列向量线性无关，则该变量组一定不包含有闭回路。7/27/202229运输问题 定理6.1 变量组 对应的系数列向量组线性无关的充要条件是：变量组(6. 2)不包含有闭回路。 推论6.1 m + n -1 个变量 (s =m+n-1) 构成基变量的充要条件是不含闭回路。运输问题的基及其构成条件ssjijijixxx2211,rrjijijixxx2211,(6. 2)7/27/202230运输问题6.3 表上作业法表上作业法是运用单纯形法求解运输问题的一种形式；表上作业法的计算步骤和计算内容与单纯形法完全相同，只是在计算

14、方法上有较大的简化，其实质仍是单纯形法；表上作业法的所有计算可以在运输表上操作，故得此名。7/27/202231运输问题6.3.1 初始解的求解方法7/27/202232运输问题1. 最小元素法最小元素法的基本思想是就近供应，这是因为运输问题是要确定总运费最小的运输方案；最小元素法的宗旨是从运价表中依次选择当前最小运价的格子分配相应的运输量，由此确定初始运输方案；最小元素法求得的初始解一般很接近最优解。7/27/202233运输问题最小元素法算例 最小元素法计算程序： (4) 若 xlk(0)=q1, 则 It+1=It - l , Jt+1=Jt(1) t = 0, It=1,m, Jt=1

15、,n 若 xlk(0)=q2, 则 It+1=It , Jt+1=Jt - k (2) clk(t) = min cij | iIt , jJt (5) t = t +1 , 返回 (2) 。(3)(2)(4)(6)(3)(3)1234566z0=85al - , bk - ljxnj1=(0)ikxmi1=(0)(3) xlk(0)=min = minq1, q27/27/202234运输问题关于最小元素法的定理 定理6.2 用最小元素法得到的变量 xij 的值构成一个基可行解，括号中的数则是基变量的值。有m + n -1个基变量；基变量不包含闭回路。x1x2x3x47/27/202235运

16、输问题2. 左上角法(西北角法)左上角法的特点是不考虑运输方案的运费，只要求运输量满足产销平衡便可。因此该法不依赖运价表，可直接在产销平衡表上操作。左上角法的要点是按产地和销地的排序从前到后依次确定供销关系，即每次都是在运价表中选择当前处在左上角的格子分配运输量，由此确定初始运输方案；左上角法的计算量较小，但求得的初始解远不如最小元素法的好，通常与最优解相去甚远。7/27/202236运输问题2. 左上角法(西北角法)算例(3)(4)(2)(3)(3)(6)z0=1357/27/202237运输问题3.伏格尔(Vogel)法伏格尔法的出现早于表上作业法，原本是一种求解运输问题的近似算法，亦称

17、Vogel 近似法，简称 V A M。伏格尔法给出的解也是基解，因此可以把它当作一种求初始解的方法。伏格尔法的出发点与最小元素法相同。由于局部最优的叠加并不等于全局最优，最小元素法往往会顾此失彼，即为了节省一处的费用有时造成别处要多花几倍的运费。相比之下，伏格尔法是一种“顾全大局” 的最小元素法。根据计算特点，伏格尔法也称元素差额法。伏格尔法求得的初始解更接近或者就是最优解。7/27/202238运输问题例6.2的初始解(最小元素法)7/27/202239运输问题212-123例6.2的解(伏格尔法)5121123-2258221-52(3)(5)(4)(3)(1)(5)z1 = 887/27

18、/202240运输问题例6.2的最优解7/27/202241运输问题伏格尔法求解例6.17/27/202242运输问题 最小元素法求解例6.17/27/202243运输问题6.3.2 当前解的判别和调整 当前解的判别仍然是依据非基变量的检验数，检验数的计算公式为 ij = cij - CBB-1Pij , i , j N 因为运输问题的目标函数是要求实现最小化，所以必须满足条件 ij = cij - CBB-1Pij 0 , i , j N 当前解就是最优解。 下面介绍两种求非基变量检验数的方法：闭回路法和位势法。7/27/202244运输问题1.闭回路法 运输问题非基变量的检验数有特定的经济

19、含义，按照这种含义计算检验数的方法称为闭回路法； 当前解若不是最优解，就要对其进行调整或变换。求解运输问题时，当前解的调整不必进行一般意义上的旋转变化，只要在相应的闭回路上操作就可以了。7/27/202245运输问题数字格和空格 运输表中的每个格子都对应着一个变量，为了在表上能够看出哪些变量是基变量、哪些变量是非基变量，可以约定：在选为基变量的格子中打一个括号，把基变量的值填在这个括号里，并把这种格子叫数字格 (或称开发格子) ；非基变量的值都为 0，但这个 0 不用填，这样就把非基变量对应的格子称为空格(或称关闭格子)。7/27/202246运输问题 数字格和空格示例非基变量与空格基变量与数

20、字格7/27/202247运输问题x13 , x14 , x21 , x23 , x32 , x34非基变量和闭回路x11 , x13 , x14 , x21 , x23 , x32 , x34x11 , x21 , x23 , x13 , 基变量组关于变量 x11的闭回路是否含闭回路7/27/202248运输问题svvkijijijijlklxxxxxxvpoooo211, 定理6.3 设运输问题的基变量组为 xl k是一个非基变量，则变量组 中存在一个包含xl k的闭回路，并且这个闭 回路是唯一的。非基变量对应的闭回路ssjijijixxx2211,s = m + n -1sssjijij

21、ijikljixxxxxx1221111,sssjijijijlkljixxxxxx1221111,7/27/202249运输问题 x11 , x13 , x23 , x21 z1= z0 + c11 - c13 + c23 - c21 11 = z1 - z0 = c11 - c13 + c23 - c21 = 5 - 3 + 2 - 1 = 3检验数的意义7/27/202250运输问题 x24 , x23 , x13 , x14 z1= z0 + c24 - c23 + c13 - c14 24 = z1 - z0 = c24 - c23 + c13 - c14 = 6 - 2 + 3 -

22、 9 = -2检验数的计算(闭回路法)7/27/202251运输问题检验数的计算结果(一)7/27/202252运输问题当前解的判别 由最优解的判别依据可知，在计算表中若所有的检验数都大于或等于零，则表明对当前解作出任何改变都不会使运费下降，所以当前解就是最优解。反之，说明当前解不是最优解，需要加以调整。7/27/202253运输问题当前解的调整 当前解的调整方法如下：选择一个负检验数 (当不止一个负检验数时，一般选一个最小的负检验数 ) lk 0 ，以它对应的非基变量 xpq 作为换入变量；找出换入变量对应的闭回路，将闭回路的顶点按顺序编号，换入变量xlk作为第一个顶点，因此这条闭回路的顶点

23、分为奇数号顶点和偶数号顶点两类。在所有偶数号顶点中找出运输量最小的顶点 xrs 作为换出变量；7/27/202254运输问题当前解的调整(续)将换出变量 xrs 的运输量作为调整量 ，对当前解调整如下：闭回路中所有奇数号顶点(包括换入变量xpq)的运输量加上 ；闭回路中所有偶数号顶点(包括换出变量 xrs)的运输量减去 ；不属于闭回路的变量对应的运输量不变。 上述当前解的调整方法称为闭回路调整法。显然，调整后的解仍是基可行解。7/27/202255运输问题用闭回路法对表中的解进行调整7/27/202256运输问题换入变量为： x24对应的闭回路： = x24 , x23 , x13 , x14

24、 调整量 ： =minx23(0), x14 (0)=min2,3=2换出变量为： x23换入、换出变量和调整量7/27/202257运输问题 当前解调整的算例cij(xij)sijB1B2B3B4ai51139A1 (4+q )(3-q )711026A2(3)(2-q )+q58475A3(6)(3)9bj3666z0=85 xij(0) + , xij(0)+ xij(0) - , xij(0) - xij(0) , xij(0) xij(1) =7/27/202258运输问题调整后的基可行解7/27/202259运输问题检验数的计算结果(二)7/27/202260运输问题2. 位势法7

25、/27/202261运输问题 设给定了一个初始调运方案，其基变量为 对应的运价为 引入 m + n 个待定的未知量 u1, u2 , um , v1, v2 , vn，把各 ui 写在运输表各行 Ai 的右边，把 vj 写在各列 Bj 的下边，并使上述各基变量的运价恰好就等于它所在行的 ui 与所在列的 vj 之和。即有如下方程组： 注意这个方程组中一共有m+n个未知数，m+n-1=s个方程。基变量对应的方程组ssjijijixxx2211,s = m + n -1ssjijijiccc2211。,11jijicvu11=+21jijicvu22=+s1jijicvuss=+ (6. 3)7/

26、27/202262运输问题基变量对应的方程组举例 x13 , x14 , x21 , x23 , x32 , x34 u1+ v3 = 3 = c13 , u1+ v4 = 9 = c14 u2+ v1 = 1 = c21 , u2+ v3 = 2 = c23 u3+ v2 = 4 = c32 , u3+ v4 = 5 = c347/27/202263运输问题位势的求解cij(xij)B1B2B3B4ui51139A1(4)(3)11026A2(3)(2)8475A3(6)(3)vjz0=85 x13 , x14 , x21 , x23 , x32 , x34 u1+ v3 = 3 = c13

27、 , u1+ v4 = 9 = c14 u2+ v1 = 1 = c21 , u2+ v3 = 2 = c23 u3+ v2 = 4 = c32 , u3+ v4 = 5 = c3401-318277/27/202264运输问题 11 = c11 - c13 + c23 - c21 = c11 - ( u1+v3) + ( u2+v3) - ( u2+v1) = c11 - u1- v1 = c11 - ( u1+v1)检验数的计算(位势法)7/27/202265运输问题 ij = cij - CBB-1Pij ij = cij - ( ui + vj )检验数的计算公式及结果7/27/202

28、266运输问题7/27/202267运输问题7/27/202268运输问题7/27/202269运输问题7/27/202270运输问题表上作业法计算中的问题7/27/202271运输问题初始退化解的给定(2)(2)(3)(3)(0)(0)7/27/202272运输问题7/27/202273运输问题退化解的调整( = 0)7/27/202274运输问题退化解的调整( 不是唯一的)7/27/202275运输问题退化的最优解7/27/202276运输问题6.4 产销不平衡的运输问题7/27/202277运输问题例6.3 产大于销问题的运输表7/27/202278运输问题产大于销的运输问题 假若有一个

29、虚拟的销地 Bn+1，它的销量为并且设 xi n+1 ( i = 1 m ) 为从产地 Ai 到虚拟销地 Bn+1 的物资运输量，即产地 Ai的就地储存量，ci n+1= 0 ( i = 1 m )，原问题可转化为平衡问题。ijijxcmin z =nj1=mi1=xij 0 , i , js.t.mi1=axiij nj1=,nj1=bxjij=mi1=,=njjb1=miia1-=njjb1=miia1bn+1 =7/27/202279运输问题运输模型的转化 假若有一个虚拟的销地 Bn+1，它的销量为并且设 xi n+1 ( i = 1 m ) 为从产地 Ai 到虚拟销地 Bn+1 的物资

30、运输量，即产地 Ai的就地储存量，ci n+1= 0 ( i = 1 m )，原问题可转化为平衡问题。ijijxcmin z =nj1=mi1=xij 0 , i , jnj1=bxjij=mi1=,-=njjb1=miia1bn+1 =bn+1=xi n+1mi1=ijxnj1=+ xi n+1 = ai, i =1 m7/27/202280运输问题ijijxcmin z =nj1=mi1=xij 0 , i , jnj1=bxjij=mi1=,bn+1=xi n+1mi1=ijxnj1=+ xi n+1 = ai, i =1 m7/27/202281运输问题转化后的平衡问题 ijijxcm

31、in z =nj1=mi1=xij 0 , i , js.t.nj1=bxjij=mi1=,ijxnj1=+ xi n+1 = aibn+1=xi n+1mi1=ijijxcmin z =n+1j1=mi1=xij 0 , i , jxijn+1j1=mi1=s.t.ai=,n +1j1=bxjij=mi1=,7/27/202282运输问题产大于销的运输问题举例7/27/202283运输问题产大于销的运输问题举例(续)7/27/202284运输问题销大于产的运输问题 假若有一个虚拟的产地 Am+1，它的产量为并且设 xm+1 j ( j = 1 n ) 为从虚拟产地 Am+1 到销地 Bj 的物资缺货量，即销地 Bj 的自给储存量，cm+1 j = 0 ( j = 1 n )，原问题可转化为平衡问题。ijijxcmin z =nj1=mi1=xij 0 , i , js.t.mi1=axiij =nj1=,jijnj1=b x mi1=,=njjb1=miia1 -=miia1=njjb1