1、2022-8-9运输问题6-16 运输问题运输问题u 运输问题的数学模型运输问题的数学模型u 运输问题及其基的特征运输问题及其基的特征u 表上作业法表上作业法u 产销不平衡的运输问题产销不平衡的运输问题u 转转运问题运问题u 运输问题的应用运输问题的应用x2x1zo2022-8-9运输问题6-26.1 运输问题的数学模型运输问题的数学模型2022-8-9运输问题6-3考察问题考察问题 某公司经营一种产品，它下设三个加某公司经营一种产品，它下设三个加工厂和四个销售点。三个加工厂工厂和四个销售点。三个加工厂 A1,A2,A3 的产的产量分别为量分别为 7 吨，吨，5 吨，吨，9 吨；四个销售点吨；
2、四个销售点 B1,B2,B3,B4 的销量分别为的销量分别为 3 吨，吨，6 吨，吨，6 吨，吨，6 吨。从吨。从各加工厂到各销售点的每吨产品的运费如表各加工厂到各销售点的每吨产品的运费如表6.1所所示。问该公司应如何调运产品，使总运费最小。示。问该公司应如何调运产品，使总运费最小。设设 xij 为从加工厂为从加工厂 Ai 到销售点到销售点 Bj 的产品运输的产品运输量量(i=1,2,3;j=1,2,3,4)，将产销量和所有可能，将产销量和所有可能安排的运输量列于表安排的运输量列于表6.2，则上述问题可形成一个，则上述问题可形成一个数学问题。数学问题。2022-8-9运输问题6-4问题的数学形
3、式问题的数学形式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=6 x14+x24+x33=6 xij 0,i,j表表6.1 单位运价表单位运价表表表6.2 产销平衡表产销平衡表2022-8-9运输问题6-5运输问题的一般描述运输问题的一般描述 某种物资有某种物资有 m 个产地个产地(也称为也称为“发点发点”或
4、或“源源”)和和 n 个销地个销地(也称为也称为“收点收点”或或“汇汇”)，第第 i 个产地个产地 Ai 的产量为的产量为 ai，i=1,2,m，第，第 j 个销地个销地 Bj 的销量为的销量为 bj，j=1,2,n，从，从 Ai 到到 Bj 的单位物资运价为的单位物资运价为 cij。问在产销平衡的条件下，。问在产销平衡的条件下，如何确定总运费最小的物资调运方案。如何确定总运费最小的物资调运方案。设设 xij 为从产地为从产地 Ai 到销地到销地 Bj 的物资运输量，的物资运输量，则上述问题可归结为一个线性规划问题。则上述问题可归结为一个线性规划问题。2022-8-9运输问题6-6表表6.3
5、单位运价表单位运价表 销销 地地产产 地地B1B2BnA1c11c12c1nA2c21c22c2nAmcm1cm2cmn2022-8-9运输问题6-7表表6.4 产销平衡表产销平衡表 销销 地地产产 地地B1B2BnaiA1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnambjb1b2bn2022-8-9运输问题6-8运输问题的模型运输问题的模型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,j 销销地地产产地地B1
6、B2BnaiA1x11x12 x1na1A2x21x22 x2na2Amxm1xm2 xmnambjb1b2bn 销销地地产产地地B1B2 BnA1c11c12 c1nA2c21c22 c2nAmcm1cm2 cmnijijxcmin z=nj 1=mi 1=2022-8-9运输问题6-9数学模型的两种形式数学模型的两种形式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=nj 1=mi 1=ijijxcmin z=
7、nj 1=mi 1=xij 0,i,jaxiij=nj 1=mi1=s.t.,nj1=bxjij=mi 1=,=njjb1=miia1ijxnj 1=mi 1=2022-8-9运输问题6-10表表6.5 运输表运输表 销销 地地产产 地地B1B2BnaiA1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnambjb1b2bn2022-8-9运输问题6-11表表6.6 运输表运输表(综合表综合表)2022-8-9运输问题6-12表表6.7 例例6.1的运输表的运输表cijB1B2B3B4aiA1511397A2110265A384759bj3666212022-8-9运输问
8、题6-13表表6.8 例例6.1的综合运输表的综合运输表cij(xij)B1B2B3B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)58475A3(x31)(x32)(x33)(x34)9bj3666212022-8-9运输问题6-146.2 运输问题及其基的特征运输问题及其基的特征2022-8-9运输问题6-156.2.1 运输问题的解运输问题的解 与一般线性规划问题不同，产销平衡的运输问题一定与一般线性规划问题不同，产销平衡的运输问题一定存在可行解。因有存在可行解。因有 则存在可行解则存在可行解 xij 0=ai bj/
9、Q,i,j 又因又因 0 xij min ai,bj 所以运输问题必存在最优解。所以运输问题必存在最优解。=njjb1=miia1=Q2022-8-9运输问题6-16运输问题解的特性运输问题解的特性 运输问题还有一个重要的性质，若产销量运输问题还有一个重要的性质，若产销量 ai 和和 bj都是整数，则必存在整数最优解。因此，将都是整数，则必存在整数最优解。因此，将某些整数规划问题化为运输问题来求解，即便不某些整数规划问题化为运输问题来求解，即便不用整数限制条件，结果可自然满足整数要求。在用整数限制条件，结果可自然满足整数要求。在“整数规划整数规划”一章中，将会看到求解整数规划问一章中，将会看到
10、求解整数规划问题相当费事，而运输问题解的特性给求解某些整题相当费事，而运输问题解的特性给求解某些整数规划问题带来了很大方便。数规划问题带来了很大方便。2022-8-9运输问题6-176.2.2 运输问题的形式特征运输问题的形式特征 运输问题的数学模型具有下列特征：运输问题的数学模型具有下列特征：n方程组中所有变量的系数皆为方程组中所有变量的系数皆为 1和和 0；n任何一个变量任何一个变量 xij 在前在前 m 个方程中以系数个方程中以系数 1 出出现一次，在后现一次，在后 n 个方程也以系数个方程也以系数 1 出现一次；出现一次；n由于要求由于要求 ai=bj，这，这(m+n)个方程是线性个方
11、程是线性相关的。如果从中去掉一个方程相关的。如果从中去掉一个方程,剩下的剩下的(m+n-1)个方程线性无关。个方程线性无关。2022-8-9运输问题6-18运输问题的系数矩阵运输问题的系数矩阵(单模单模)或幺模或幺模x11x12 x1nx21x22 x2n xm1xm2 xmn1 1 11 1 111 1111111111m行行n行行2022-8-9运输问题6-19系数矩阵的秩系数矩阵的秩u假设假设 m,n 2，则有，则有 m+n m n，于是矩阵，于是矩阵 A 的的秩小于或等于秩小于或等于m+n。但是。但是A的秩不等于的秩不等于m+n，这，这是因为是因为 A 的前的前 m 行之和恰好等于后行
12、之和恰好等于后 n 行之和，行之和，所以所以 A 的的 m+n 行是线性相关的。因此，行是线性相关的。因此，A 的秩的秩小于或等于小于或等于 m+n-1u对于运输问题的约束方程的增广矩阵对于运输问题的约束方程的增广矩阵A（就是由（就是由矩阵矩阵A再增添一列约束方程组的右端项所组成的再增添一列约束方程组的右端项所组成的(m+n)(m+n-1)阶矩阵），也有阶矩阵），也有A的秩的秩=m+n-1.2022-8-9运输问题6-20001001000010000000000100第第 i 行行第第 m+j 行行系数矩阵列向量的结构系数矩阵列向量的结构 系数矩阵每一列的元素只有两个系数矩阵每一列的元素只有
13、两个1，其余都为，其余都为0。Pij =ei +em+j2022-8-9运输问题6-216.2.3 运输问题的基运输问题的基 同一般的线性规划问题一样，运输问同一般的线性规划问题一样，运输问题的最优解一定可以在基可行解中找到。题的最优解一定可以在基可行解中找到。因此，继考察了约束方程组的系数矩阵之因此，继考察了约束方程组的系数矩阵之后，还要进一步研究运输问题的基及其基后，还要进一步研究运输问题的基及其基变量所具有的特征。变量所具有的特征。2022-8-9运输问题6-22 由上面的讨论可知，运输问题基变量的数目由上面的讨论可知，运输问题基变量的数目应该是应该是 m+n-1 个，接下来研究怎样的个
14、，接下来研究怎样的 m+n-1 个个变量变量 可以组成基变量。或者说，怎样的可以组成基变量。或者说，怎样的 m+n-1 个变个变量量 (s=m+n-1)对应的系数列向对应的系数列向量量 (s=m+n-1)是线性无关的。是线性无关的。下面引入有关闭回路的概念，它有助于分析下面引入有关闭回路的概念，它有助于分析和解决上述问题。和解决上述问题。基变量与基向量基变量与基向量sssjijijijijijixxxxxx122111211,(s=m+n-1)ssjijijiPPP2211,ssjijijixxx2211,2022-8-9运输问题6-23闭回路及其形式闭回路及其形式cij(xij)B1B2B3
15、B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)58475A3(x31)(x32)(x33)(x34)9bj366621x1 1,x1 3,x3 3,x3 12022-8-9运输问题6-24闭回路的定义闭回路的定义 凡是能排成凡是能排成(i1,i2,is 互不相同互不相同,j1,j2,js 互不相同互不相同)形式的变量的集合称为一个形式的变量的集合称为一个闭回路闭回路，而把出现在，而把出现在(1)中的变量称为这个闭回路的中的变量称为这个闭回路的顶点顶点(或或拐角点拐角点)，相邻两顶点的连线称为闭回路的相邻两顶点的连线称为闭回
16、路的边边。(1)132222111,jijijijijijisssxxxxxx2022-8-9运输问题6-25闭回路的形式之二闭回路的形式之二 cij(xij)B1B2B3B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)58475A3(x31)(x32)(x33)(x34)9bj366621x1 1,x1 2,x3 2,x3 4,x2 4,x2 1 2022-8-9运输问题6-26cij(xij)B1B2B3B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)
17、58475A3(x31)(x32)(x33)(x34)9bj366621闭回路的形式之三闭回路的形式之三2022-8-9运输问题6-27闭回路的特点闭回路的特点 从上面几个闭回路的例子中不难看出，如果从上面几个闭回路的例子中不难看出，如果把一个闭回路的所有顶点都在表上画出，并且把把一个闭回路的所有顶点都在表上画出，并且把相邻的顶点用一条直线连接起来，就可以得到一相邻的顶点用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，条封闭的折线，折线的每一条边或者是水平的，或者是垂直的，即折线是由交替的水平和垂直或者是垂直的，即折线是由交替的水平和垂直（联接的）线段组成。另外，在表
18、中的每一行和（联接的）线段组成。另外，在表中的每一行和每一列中，至多只有闭回路的两个顶点；对一条每一列中，至多只有闭回路的两个顶点；对一条闭回路是按顺时针方向还是逆时针方向是无关紧闭回路是按顺时针方向还是逆时针方向是无关紧要的。要的。2022-8-9运输问题6-28 若有一闭回路若有一闭回路 则则 根据列向量的特征根据列向量的特征 Pij=ei+em+j 可得可得闭回路闭回路及其性质及其性质132222111-+-+-jijijijijijisssPPPPPP=0132222111-+-+-jijijijijijisssPPPPPP()+jmiee32-()+jmiee22-=()+jmiee
19、11+()+jmiee21-()+jmieess+=0()+jmiee1s1ssjijijijijijixxxxxxs32222111,2022-8-9运输问题6-29srrjijijijijijixxxxxx122111211,(6.2)122112111-,+-jijijijijijisrrPPPPPP=0闭回路与闭回路与列向量列向量 若变量组若变量组 中有一部分组成闭回路，则中有一部分组成闭回路，则(6.2)对应的列向量对应的列向量 是线性相关的。是线性相关的。性质性质6.1表明构成闭回路的变量组对应的列向量表明构成闭回路的变量组对应的列向量组是线性相关的，组是线性相关的，而向量组中有一
20、部分线性相关，则全而向量组中有一部分线性相关，则全体也体也线性相关线性相关。性质性质6.2说明：若变量组说明：若变量组(6.2)对应的列向量线性无关，对应的列向量线性无关，则该变量组一定不包含有闭回路。则该变量组一定不包含有闭回路。2022-8-9运输问题6-30 变量组变量组 对应的系数列向量组线性无关的充要条件是：变对应的系数列向量组线性无关的充要条件是：变量组量组(6.2)不包含有闭回路。不包含有闭回路。m+n-1 个变量个变量 (s=m+n-1)构成基变量的充要条件是不含闭回路。构成基变量的充要条件是不含闭回路。运输问题的基及其构成条件运输问题的基及其构成条件ssjijijixxx22
21、11,rrjijijixxx2211,(6.2)2022-8-9运输问题6-316.3 表上作业法表上作业法n表上作业法是运用单纯形法求解运输问表上作业法是运用单纯形法求解运输问题的一种形式；题的一种形式；n表上作业法的计算步骤和计算内容与单表上作业法的计算步骤和计算内容与单纯形法完全相同，只是在计算方法上有纯形法完全相同，只是在计算方法上有较大的简化，其实质仍是单纯形法；较大的简化，其实质仍是单纯形法；n表上作业法的所有计算可以在运输表上表上作业法的所有计算可以在运输表上操作，故得此名。操作，故得此名。2022-8-9运输问题6-326.3.1 初始解的求解方法初始解的求解方法2022-8-
22、9运输问题6-331.最小元素法最小元素法u最小元素法的基本思想是就近供应，这是因为运最小元素法的基本思想是就近供应，这是因为运输问题是要确定总运费最小的运输方案；输问题是要确定总运费最小的运输方案；u最小元素法的宗旨是从运价表中依次选择当前最最小元素法的宗旨是从运价表中依次选择当前最小运价的格子分配相应的运输量，由此确定初始小运价的格子分配相应的运输量，由此确定初始运输方案；运输方案；u最小元素法求得的初始解一般很接近最优解。最小元素法求得的初始解一般很接近最优解。2022-8-9运输问题6-34最小元素法算例最小元素法算例cijB1B2B3B4A151139A211026A38475 最小
23、元素法计算程序：最小元素法计算程序：(4)若若 xlk(0)=q1,则则 It+1=It-l,Jt+1=Jt(1)t=0,It=1,m,Jt=1,n 若若 xlk(0)=q2,则则 It+1=It,Jt+1=Jt-k (2)clk(t)=min cij|i It,j Jt (5)t=t+1,返回返回 (2)。(xij)B1B2B3B4aiA17A25A39bj3666(3)(2)(4)(6)(3)(3)1234566z0=85al-,bk-ljxnj 1=(0)ikxmi 1=(0)(3)xlk(0)=min =minq1,q22022-8-9运输问题6-35关于最小元素法的定理关于最小元素法
24、的定理用最小元素法得到的变量用最小元素法得到的变量 xij 的值构成一个基可行解，括号中的数则是的值构成一个基可行解，括号中的数则是基变量的值。基变量的值。u有有m+n-1个基变量；个基变量；u基变量不包含闭回路。基变量不包含闭回路。x1x2x3x42022-8-9运输问题6-362.左上角法左上角法(西北角法西北角法)u左上角法的特点是不考虑运输方案的运费，只要左上角法的特点是不考虑运输方案的运费，只要求运输量满足产销平衡便可。因此该法不依赖运求运输量满足产销平衡便可。因此该法不依赖运价表，可直接在产销平衡表上操作。价表，可直接在产销平衡表上操作。u左上角法的要点是按产地和销地的排序从前到后
25、左上角法的要点是按产地和销地的排序从前到后依次确定供销关系，即每次都是在运价表中选择依次确定供销关系，即每次都是在运价表中选择当前处在左上角的格子分配运输量，由此确定初当前处在左上角的格子分配运输量，由此确定初始运输方案；始运输方案；u左上角法的计算量较小，但求得的初始解远不如左上角法的计算量较小，但求得的初始解远不如最小元素法的好，通常与最优解相去甚远。最小元素法的好，通常与最优解相去甚远。2022-8-9运输问题6-372.左上角法左上角法(西北角法西北角法)算例算例(xij)B1B2B3B4aiA17A25A39bj3666(3)(4)(2)(3)(3)(6)z0=1352022-8-9
26、运输问题6-383.伏格尔伏格尔(Vogel)法法u伏格尔法的出现早于表上作业法，原本是一种求伏格尔法的出现早于表上作业法，原本是一种求解运输问题的近似算法，亦称解运输问题的近似算法，亦称 Vogel 近似法，简近似法，简称称 V A M。伏格尔法给出的解也是基解，因此可。伏格尔法给出的解也是基解，因此可以把它当作一种求初始解的方法。以把它当作一种求初始解的方法。u伏格尔法的出发点与最小元素法相同。由于局部伏格尔法的出发点与最小元素法相同。由于局部最优的叠加并不等于全局最优，最小元素法往往最优的叠加并不等于全局最优，最小元素法往往会顾此失彼，即为了节省一处的费用有时造成别会顾此失彼，即为了节省
27、一处的费用有时造成别处要多花几倍的运费。相比之下，伏格尔法是一处要多花几倍的运费。相比之下，伏格尔法是一种种“顾全大局顾全大局”的最小元素法。根据计算特点，的最小元素法。根据计算特点，伏格尔法也称元素差额法。伏格尔法也称元素差额法。u伏格尔法求得的初始解更接近或者就是最优解。伏格尔法求得的初始解更接近或者就是最优解。2022-8-9运输问题6-39例例6.2的初始解的初始解(最小元素法最小元素法)cij(xij)B1B2B3B4ai29107A1(5)(4)91342A2(3)(2)58425A3(3)(4)7bj3846z0=1002022-8-9运输问题6-40cij(xij)B1B2B3
28、B4ai行行差差额额29107A191342A258425A37bj384621列列差差额额212-123例例6.2的解的解(伏格尔法伏格尔法)5121123-2258221-52(3)(5)(4)(3)(1)(5)z1=882022-8-9运输问题6-41例例6.2的最优解的最优解cij(xij)B1B2B3B4ai29107A1(3)(6)91342A2(5)(0)58425A3(3)(4)7bj3846z*=832022-8-9运输问题6-42伏格尔法求解例伏格尔法求解例6.1cij(xij)B1B2B3B4ai行行 差差 额额51139A1(6)(1)722611026A2(3)(2)
29、51148475A3(6)(3)9122bj36662146114-11列列差差额额-11z*=812022-8-9运输问题6-43 最小元素法求解例最小元素法求解例6.1cij(xij)B1B2B3B4ai51139A1(4)(3)711026A2(3)(2)58475A3(6)(3)9bj3666z0=852022-8-9运输问题6-446.3.2 当前解的判别和调整当前解的判别和调整 当前解的判别仍然是依据非基变量的检验数，当前解的判别仍然是依据非基变量的检验数，检验数的计算公式为检验数的计算公式为 ij=cij-CBB-1Pij,i,j N 因为运输问题的目标函数是要求实现最小化，所因
30、为运输问题的目标函数是要求实现最小化，所以必须满足条件以必须满足条件 ij=cij-CBB-1Pij 0,i,j N 当前解就是最优解。当前解就是最优解。下面介绍两种求非基变量检验数的方法：下面介绍两种求非基变量检验数的方法：闭闭回路法和回路法和位势法。位势法。2022-8-9运输问题6-451.闭回路法闭回路法 运输问题非基变量的检验数有特定的经济含运输问题非基变量的检验数有特定的经济含义，按照这种含义计算检验数的方法称为闭回路义，按照这种含义计算检验数的方法称为闭回路法；法；当前解若不是最优解，就要对其进行调整或当前解若不是最优解，就要对其进行调整或变换。求解运输问题时，当前解的调整不必进
31、行变换。求解运输问题时，当前解的调整不必进行一般意义上的旋转变化，只要在相应的闭回路上一般意义上的旋转变化，只要在相应的闭回路上操作就可以了。操作就可以了。2022-8-9运输问题6-46数字格和空格数字格和空格 运输表中的每个格子都对应着一个变运输表中的每个格子都对应着一个变量，为了在表上能够看出哪些变量是基变量，为了在表上能够看出哪些变量是基变量、哪些变量是非基变量，可以约定：在量、哪些变量是非基变量，可以约定：在选为基变量的格子中打一个括号，把基变选为基变量的格子中打一个括号，把基变量的值填在这个括号里，并把这种格子叫量的值填在这个括号里，并把这种格子叫数字格数字格(或称开发格子或称开发
32、格子)；非基变量的值都；非基变量的值都为为 0，但这个，但这个 0 不用填，这样就把非基变不用填，这样就把非基变量对应的格子称为空格量对应的格子称为空格(或称关闭格子或称关闭格子)。2022-8-9运输问题6-47 数字格和空格示例数字格和空格示例cij(xij)B1B2B3B4ai51139A1(4)(3)711026A2(3)(2)58475A3(6)(3)9bj3666z0=85非基变量非基变量与空格与空格基变量基变量与数字格与数字格2022-8-9运输问题6-48x13,x14,x21,x23,x32,x34非基变量和非基变量和闭回路闭回路cij(xij)B1B2B3B4ai51139
33、A1x11(4)(3)711026A2(3)(2)58475A3(6)(3)9bj3666z0=85x11,x13,x14,x21,x23,x32,x34x11,x21,x23,x13,基变量组基变量组关于变量关于变量 x11的闭回路的闭回路是否含是否含闭回路闭回路2022-8-9运输问题6-49svvkijijijijlklxxxxxxvpoooo211,设运输问题的基变量组为设运输问题的基变量组为 xl k是一个非基变量，则变量组是一个非基变量，则变量组 中存在一个包含中存在一个包含xl k的的闭回路闭回路，并且这个，并且这个闭闭 回路回路是唯一的。是唯一的。非基变量对应的非基变量对应的闭
34、回路闭回路ssjijijixxx2211,s=m+n-1sssjijijijikljixxxxxx1221111,sssjijijijlkljixxxxxx1221111,2022-8-9运输问题6-50 x11,x13,x23,x21 z1=z0+c11-c13+c23-c21 11=z1-z0=c11-c13+c23-c21 =5 -3 +2 -1 =3检验数的意义检验数的意义cij(xij)B1B2B3B4ai51139A1(+1)(4-1)(3)711026A2(3-1)(2+1)58475A3(6)(3)9bj3666z0=852022-8-9运输问题6-51cij(xij)ijB1
35、B2B3B4ai51139A1 3(4)(3)711026A2(3)(2)(x24)58475A3(6)(3)9bj3666z0=85 x24,x23,x13,x14 z1=z0+c24-c23+c13-c14 24=z1-z0=c24-c23+c13-c14 =6 -2 +3 -9 =-2检验数的计算检验数的计算(闭回路法闭回路法)2022-8-9运输问题6-52检验数的计算结果检验数的计算结果(一一)cij(xij)ijB1B2B3B4ai51139A1 3 3(4)(3)711026A2(3)3(2)-258475A3 10(6)8(3)9bj3666212022-8-9运输问题6-53
36、当前解的判别当前解的判别 由最优解的判别依据可知，在计算表由最优解的判别依据可知，在计算表中若所有的检验数都大于或等于零，则表中若所有的检验数都大于或等于零，则表明对当前解作出任何改变都不会使运费下明对当前解作出任何改变都不会使运费下降，所以当前解就是最优解。反之，说明降，所以当前解就是最优解。反之，说明当前解不是最优解，需要加以调整。当前解不是最优解，需要加以调整。2022-8-9运输问题6-54当前解的调整当前解的调整 当前解的调整方法如下：当前解的调整方法如下：n选择一个负检验数选择一个负检验数(当不止一个负检验数时，当不止一个负检验数时，一般选一个最小的负检验数一般选一个最小的负检验数
37、)lk 0，以它对，以它对应的非基变量应的非基变量 xpq 作为换入变量；作为换入变量；n找出换入变量对应的找出换入变量对应的闭回路，将闭回路的闭回路，将闭回路的顶点顶点按顺序编号，换入变量按顺序编号，换入变量xlk作为第一个顶点，因作为第一个顶点，因此这条此这条闭回路闭回路的顶点分为奇数号顶点和偶数号的顶点分为奇数号顶点和偶数号顶点两类。在所有偶数号顶点中找出运输量最顶点两类。在所有偶数号顶点中找出运输量最小的顶点小的顶点 xrs 作为换出变量；作为换出变量；2022-8-9运输问题6-55当前解的调整当前解的调整(续续)n将换出变量将换出变量 xrs 的运输量作为调整量的运输量作为调整量
38、，对当，对当前解调整如下：前解调整如下：F闭回路中所有闭回路中所有奇数号顶点奇数号顶点(包括换入变量包括换入变量xpq)的运输量加上的运输量加上 ；F闭回路中所有闭回路中所有偶数号顶点偶数号顶点(包括换出变量包括换出变量 xrs)的运输量减去的运输量减去 ；F不属于不属于闭回路的变量对应的闭回路的变量对应的运输量不变。运输量不变。上述当前解的调整方法称为上述当前解的调整方法称为闭回路闭回路调整法。显调整法。显然，然，调整后的解仍是基可行解。调整后的解仍是基可行解。2022-8-9运输问题6-56cij(xij)ijB1B2B3B4ai51139A1 3 3(4)(3)711026A2(3)3(
39、2)-258475A3 10(6)8(3)9bj366621用闭回路用闭回路法对表中的解进行调整法对表中的解进行调整2022-8-9运输问题6-57cij(xij)ijB1B2B3B4ai51139A1(4)(3)711026A2(3)(2)x2458475A3(6)(3)9bj3666z0=85换入变量为：换入变量为：x24对应的对应的闭回路：闭回路：=x24,x23,x13,x14 调整量调整量：=minx23(0),x14(0)=min2,3=2换换出出变量为：变量为：x23换入、换出变量和换入、换出变量和调整量调整量2022-8-9运输问题6-58 当前解调整的算例当前解调整的算例ci
40、j(xij)ijB1B2B3B4ai51139A1(4+)(3-)711026A2(3)(2-)+58475A3(6)(3)9bj3666z0=85 xij(0)+,xij(0)+xij(0)-,xij(0)-xij(0),xij(0)xij(1)=2022-8-9运输问题6-59调整后的基可行解调整后的基可行解cij(xij)ijB1B2B3B4ai51139A1(6)(1)711026A2(3)(2)58475A3(6)(3)9bj3666z0=812022-8-9运输问题6-60检验数的计算结果检验数的计算结果(二二)cij(xij)ijB1B2B3B4ai51139A1 1 3(6)(
41、1)711026A2(3)5 2(2)58475A3 8(6)8(3)9bj366621(i,j)闭 回 路ij(1,1)(1,1)-(1,4)-(2,4)-(2,1)-(1,1)11=5-9+6-1=1(1,2)(1,2)-(1,4)-(3,4)-(3,2)-(1,2)12=11-9+5-4=3(2,2)(2,2)-(2,4)-(3,4)-(3,2)-(2,2)22=10-6+5-4=5(2,3)(2,3)-(2,4)-(1,4)-(1,3)-(2,3)23=2-6+9-3=2(3,1)(3,1)-(3,4)-(2,4)-(2,1)-(3,1)31=8-5+6-1=8(3,3)(3,3)-(
42、3,4)-(1,4)-(1,3)-(3,3)33=7-5+9-3=8122022-8-9运输问题6-612.位势法位势法2022-8-9运输问题6-62 设给定了一个初始调运方案，其基变量为设给定了一个初始调运方案，其基变量为 对应的运价为对应的运价为 引入引入 m+n 个待定的个待定的未知量未知量 u1,u2,um,v1,v2,vn，把各，把各 ui 写在运输表各写在运输表各行行 Ai 的右边，把的右边，把 vj 写在各列写在各列 Bj 的下边，并使上述各基变的下边，并使上述各基变量的运价恰好就等于它所在行的量的运价恰好就等于它所在行的 ui 与所在列的与所在列的 vj 之和。之和。即有如下
43、方程组：即有如下方程组：注意这个方程组中一共有注意这个方程组中一共有m+n个未知数，个未知数，m+n-1=s个方程。个方程。基变量对应的方程组基变量对应的方程组ssjijijixxx2211,s=m+n-1ssjijijiccc2211。,11jijicvu11=+21jijicvu22=+s1jijicvuss=+(6.3)2022-8-9运输问题6-63基变量对应的方程组举例基变量对应的方程组举例cij(xij)B1B2B3B4ui51139A1(4)(3)u111026A2(3)(2)u28475A3(6)(3)u3vjv1v2v3v4z0=85 x13,x14,x21,x23,x32,
44、x34 u1+v3=3=c13 ,u1+v4=9=c14 u2+v1=1=c21 ,u2+v3=2=c23 u3+v2=4=c32 ,u3+v4=5=c342022-8-9运输问题6-64位势的求解位势的求解cij(xij)B1B2B3B4ui51139A1(4)(3)11026A2(3)(2)8475A3(6)(3)vjz0=85 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=c3401-318272022-8-9运输问题6-65 11=c11-c1
45、3+c23-c21 =c11-(u1+v3)+(u2+v3)-(u2+v1)=c11-u1-v1=c11-(u1+v1)检验数的计算检验数的计算(位势法位势法)cij(xij)B1B2B3B4ui51139A1xij(4)(3)111026A2(3)(2)08475A3(6)(3)-3vj1728z0=852022-8-9运输问题6-66 ij=cij-CBB-1Pij ij=cij-(ui+vj)检验数的计算公式及结果检验数的计算公式及结果cij(xij)B1B2B3B4ui51139A133(4)(3)111026A2(3)3(2)-208475A310(6)8(3)-3vj1728z0=
46、852022-8-9运输问题6-67ui+vjcij(xij)ijB1B2B3B4ui51139A1(6)(1)11026A2(3)(2)8475A3(6)(3)vj2022-8-9运输问题6-68ui+vjcij(xij)ijB1B2B3B4ui51139A1(6)(1)111026A2(3)(2)-28475A3(6)(3)-3vj37282022-8-9运输问题6-69ui+vjcij(xij)ijB1B2B3B4ui258113399A1(6)(1)1117102286A2(3)(2)-2-2844-1755A3(6)(3)-3vj37282022-8-9运输问题6-70ui+vjci
47、j ij(xij)B1B2B3B4ui458113399A113(6)(1)1115100266A2(3)52(2)-20844-1755A38(6)8(3)-3vj37282022-8-9运输问题6-71表上作业法计算中的问题表上作业法计算中的问题2022-8-9运输问题6-72初始退化解的给定初始退化解的给定cij(xij)B1B2B3B4ai3763A152531A224386A33bj3322(2)(2)(3)(3)(0)(0)2022-8-9运输问题6-73ui+vjcij(xij)ijB1B2B3B4ui3763A1(3)(0)(2)02531A2(0)(2)-14386A3(3)
48、-4vj37622022-8-9运输问题6-74退化解的调整退化解的调整(=0)ui+vjcij(xij)ijB1B2B3B4ui33776623A1(3)(0)(2)1022655311A2(0)-1-2(2)-1-143328-26A35(3)68-4vj37622022-8-9运输问题6-75退化解的调整退化解的调整(不是唯一的不是唯一的)ui+vjcij(xij)ijB1B2B3B4ui33776643A1(3)(0)(2)-1002453311A221(0)(2)-3-14332806A35(3)68-4vj37642022-8-9运输问题6-76退化的最优解退化的最优解ui+vjc
49、ij(xij)ijB1B2B3B4ui33775633A1(3)(0)1(2)012553311A210(2)(0)-2-143318-16A35(3)77-4vj37532022-8-9运输问题6-776.4 产销不平衡的运输问题产销不平衡的运输问题2022-8-9运输问题6-78例例6.3 产大于销问题的运输表产大于销问题的运输表cij(xij)B1B2B3B4ai21134A1710359A257812A37bj23462022-8-9运输问题6-79产大于销的运输问题产大于销的运输问题 假若有一个虚拟的假若有一个虚拟的销地销地 Bn+1，它的销量为，它的销量为并且设并且设 xi n+1
50、(i=1 m)为从产地为从产地 Ai 到虚拟销地到虚拟销地 Bn+1 的物资运输量，即的物资运输量，即产地产地 Ai的就地储存量，的就地储存量，ci n+1=0 (i=1 m)，原，原问题可转化为平衡问题。问题可转化为平衡问题。ijijxcmin z=nj 1=mi 1=xij 0,i,js.t.mi1=axiij nj 1=,nj1=bxjij=mi 1=,=njjb1=miia1-=njjb1=miia1bn+1=2022-8-9运输问题6-80运输模型的转化运输模型的转化 假若有一个虚拟的假若有一个虚拟的销地销地 Bn+1，它的销量为，它的销量为并且设并且设 xi n+1(i=1 m)为
