03运输问题讲稿

1、 1 1 5 5 年年 10 10月月 (transportation problem) 顺风而呼，声非加疾也，而闻者彰。顺风而呼，声非加疾也，而闻者彰。 假舆马者，非利足也，而致千里；假舟假舆马者，非利足也，而致千里；假舟 楫者，非能水也，而绝江河。君子生非楫者，非能水也，而绝江河。君子生非 异也，善假于物也。异也，善假于物也。 荀子荀子劝学劝学 前面讨论了一般线性规划问题的数学模型的建前面讨论了一般线性规划问题的数学模型的建 立和求解的方法立和求解的方法, , 但在实际工作中，往往碰到有些但在实际工作中，往往碰到有些 线性规划问题线性规划问题, , 它们的约束条件的它们的约束条件的系数矩阵

2、系数矩阵具有特具有特 殊的结构，这就使我们有可能找到比单纯形法更为殊的结构，这就使我们有可能找到比单纯形法更为 简单的求解方法简单的求解方法, , 从而节约大量的计算时间和费用。从而节约大量的计算时间和费用。 本章所讨论的运输问题就是属于这样一类特殊的线本章所讨论的运输问题就是属于这样一类特殊的线 性规划问题，它具有广泛的应用，在实践中有重要性规划问题，它具有广泛的应用，在实践中有重要 的价值。的价值。 在经济建设中，经常会遇到大宗物资中的运输在经济建设中，经常会遇到大宗物资中的运输 问题如煤炭、钢铁、木材、粮食等物资问题如煤炭、钢铁、木材、粮食等物资, ,在全国有若在全国有若 干生产基地干生

3、产基地, , 根据已有的交通网根据已有的交通网, , 应如何制定调运应如何制定调运 方案，将这些物资运到各消费地点，使总运费最小。方案，将这些物资运到各消费地点，使总运费最小。 一、运输问题典例与数学模型一、运输问题典例与数学模型 典例、线性规划模型、运输表典例、线性规划模型、运输表 二、初始基可行解二、初始基可行解 最小元素法、沃格尔法最小元素法、沃格尔法 三、非基变量的检验数三、非基变量的检验数 闭回路法、对偶变量法闭回路法、对偶变量法 四、解的调整四、解的调整 确定进基变量和离基变量，调整运量确定进基变量和离基变量，调整运量 五、产销不平衡的运输问题五、产销不平衡的运输问题 六、运输问题

4、应用六、运输问题应用建模建模 2021-6-64 某公司从三个产地某公司从三个产地 ， ， 将产品运往四个销地将产品运往四个销地 ， ， ，各产地的产量，各销地的销量，及各产地运往各销，各产地的产量，各销地的销量，及各产地运往各销 地的地的运费单价运费单价如表所示。应如何调运可使如表所示。应如何调运可使运费最小运费最小？ 1 A 2 A 1 B 2 B 3 B 3 A 4 B 销地 运费单价 产地 B1B2B3B4 产量 （吨） A13113107 A219284 A3741059 销量（吨）365620 一、运输问题典例一、运输问题典例 2 3 2 1 3 4 1 A2=4 A3=9 B1=

5、3 B2=6 B3=5 B4=6 A1=7 供应量供应量 供应地供应地运价运价 需求量需求量 需求地需求地 3 11 3 10 1 9 2 8 7 4 10 5 2021-6-66 解：解：从表中可知：总产量从表中可知：总产量 = = 总销量。这是一个产销平衡的总销量。这是一个产销平衡的 运输问题。假设运输问题。假设 表示从产地表示从产地 运往销地运往销地 的产的产 品数量，品数量， 建立如下表格：建立如下表格： ij x i j . 4 , 3 , 2 , 1; 3 , 2 , 1ji 于是可建立如下的数学模型于是可建立如下的数学模型： 销地销地 运费单价运费单价 产地产地 B1B2B3B4

6、 产量产量 （吨）（吨） A13113107 A219284 A3741059 销量（吨）销量（吨）3656 11 x 12 x 13 x 21 x 22 x 23 x 31 x 32 x 33 x 14 x 24 x 34 x 0 6=+ 5=+ 6=+ 3=+ 9=+ 4=+ 7=+ 5+10+4+7+8+2+9+1+10+3+11+3=min 343332312423222114131211 342414 332313 322212 312111 34333231 24232221 14131211 343332312423222114131211 xxxxxxxxxxxx xxx xx

7、x xxx xxx xxxx xxxx xxxxs.t. xxxxxxxxxxxxz 供应地约束供应地约束需求地约束需求地约束 （三）模型系数矩阵特征（三）模型系数矩阵特征 1.1.共有共有m+nm+n行，分别表示各产地和销地；行，分别表示各产地和销地；m m n n列，分列，分 别表示各决策变量别表示各决策变量； 2.2.每列只有两个每列只有两个1 1，其余为，其余为0 0，分别表示只有一个产，分别表示只有一个产 地和一个销地被使用。地和一个销地被使用。 分析：变量个数为分析：变量个数为1212，约束个数为，约束个数为7 7，但由于是产，但由于是产 销平衡，则约束中有一个是多余的，于是基变量

8、个数销平衡，则约束中有一个是多余的，于是基变量个数 为为6 6，非基变量个数为，非基变量个数为12-6=612-6=6。 运输问题的一般提法是这样的：某种物资有若干个运输问题的一般提法是这样的：某种物资有若干个 产地和销地，若已知各个产地的产量、各个销地的销量产地和销地，若已知各个产地的产量、各个销地的销量 以及各产地到各销地的单位运价（或运输距离）。问应以及各产地到各销地的单位运价（或运输距离）。问应 如何组织调运，才能使总运费（或总的运输量）最省？如何组织调运，才能使总运费（或总的运输量）最省？ 将此问题更具体化，假定有将此问题更具体化，假定有m个产地，个产地，n个销地个销地 第第i产地的

9、供应量，产地的供应量，i=1，2，m。 第第j销地的需求量，销地的需求量，j=1，2，n。 从从i产地到产地到j销地的单位运费销地的单位运费 产地产地i到销地到销地j的调运数量的调运数量 为了直观起见，运输问题常用表格来表示，常用有三种表格为了直观起见，运输问题常用表格来表示，常用有三种表格: i a j b ij c ij x 10 1、产销平衡表、产销平衡表 n j j m i i ba 11 单位单位 运价运价 销销 或运距或运距 地地 产地产地 B1 B2 Bn 产产 量量 A1 A2 Am c11 c12 c1 n c21 c22 c2n cm1 cm2 cm n a1 a2 am

10、销销 量量 b1 b2 bn n j j m i i ba 11 2、单位运价表、单位运价表 3、运输表、运输表:产销平衡表和运价表合二为一产销平衡表和运价表合二为一 n j j m i i ba 11 如果如果总产量总产量= =总销量总销量, ,= =即即 a a1 1 + a + a2 2 + + a + + am m = b = b1 1 + b + b2 2 + +b + +bn n 则称该运输问题为产销平衡运输问题；否则，称产则称该运输问题为产销平衡运输问题；否则，称产 销不平衡运输问题。我们首先研究产销平衡问题。销不平衡运输问题。我们首先研究产销平衡问题。 设从设从A Ai i 到

11、到B Bj j的运输量为的运输量为x xij ij, , 总运费为 总运费为Z Z。问怎。问怎 样编制调运方案才能使总运费最少？（注意：只研样编制调运方案才能使总运费最少？（注意：只研 究单一品种物资运输问题）那么，产销平衡的运输究单一品种物资运输问题）那么，产销平衡的运输 问题的数学模型是：问题的数学模型是： minZ= （总运费极小化）（总运费极小化） = ai i=1,2,m,（产量约束，某一产地运产量约束，某一产地运 往各销地的运量之和等于该地产量往各销地的运量之和等于该地产量） = bj j=1,2,n, （销量约束，各产地运往销量约束，各产地运往 某一销地的运量之和等于该销地需求量

12、某一销地的运量之和等于该销地需求量） xij 0 非负约束非负约束 11 mn i ji j ij cx 1 n i j j x 1 m ij i x 111212122212 111212122212 111 111 111 111 111 111 ,.,.,.,., (0,.,1,.,1,.0) nnmmmn nnmmmn T ijim j xxxxxxxxx A AP PPPPPPPP Pee m 行行 n 行行 1 1、包含、包含 = =，所以系数矩阵中线性独立的列向量，所以系数矩阵中线性独立的列向量 的最大个数为（的最大个数为（该模型有该模型有m m* *n n个变量，个变量， m+

13、nm+n个约束个约束，解中基变量个数为（解中基变量个数为（m+n-1m+n-1）个。个。（ 对于平衡型的运输问题，当确定其中的对于平衡型的运输问题，当确定其中的m+n-1m+n-1个个 方程后，剩下的一个方程也就确定了方程后，剩下的一个方程也就确定了 2 2、在该模型的系数矩阵中，每列有两个元素是、在该模型的系数矩阵中，每列有两个元素是1 1，其，其 余为余为0 0。（。（2mn2mn个元素不为个元素不为0 0） 3 3、在目标函数中，由于系数、在目标函数中，由于系数0,0,且目标为极小且目标为极小, ,因此因此 目标函数有下界目标函数有下界( (不会是无界解不会是无界解),),又由于约束方程

14、组又由于约束方程组 一定有可行解（可以证明）一定有可行解（可以证明）, ,故故运输问题一定有最优运输问题一定有最优 解。解。 运输模型的特点：运输模型的特点： l 运输问题是一种特殊的线性规划问题，理运输问题是一种特殊的线性规划问题，理 论上论上, ,我们可以用单纯形法来求解运输问题的我们可以用单纯形法来求解运输问题的 解解, , 如果用单纯形法求解，先得在各约束条件如果用单纯形法求解，先得在各约束条件 上加入一个人工变量上加入一个人工变量( (以便求出初始基可行解以便求出初始基可行解) )。 因此，即使是因此，即使是 m = 3m = 3， n = 4 n = 4 这样的简单问这样的简单问

15、题题, , 变量数就有变量数就有1919个之多，计算起来非常复杂。个之多，计算起来非常复杂。 但由于运输问题自身的特殊性但由于运输问题自身的特殊性, ,我们使用单纯我们使用单纯 形原理形原理, ,但不用单纯形法。人们在分析运输规但不用单纯形法。人们在分析运输规 划系数矩阵特征的基础上建立了针对运输问题划系数矩阵特征的基础上建立了针对运输问题 的表上作业法。的表上作业法。 2 2 表上作业法是求解运输问题的一种简便有效的方表上作业法是求解运输问题的一种简便有效的方 法，求解工作在运输表上进行，它是单纯形法的一种法，求解工作在运输表上进行，它是单纯形法的一种 简化方法，其实质是单纯形法，也称为是运

16、输单纯形简化方法，其实质是单纯形法，也称为是运输单纯形 法，但具体计算和术语有所不同。法，但具体计算和术语有所不同。 基本可行解基本可行解 是否最优解是否最优解结束结束 换基 是是 否否 运输问题的求解思路 求解思路：求解思路：这里求解运输问题的思想和单纯形法完这里求解运输问题的思想和单纯形法完 全一样，即首先确定一个初始基本可行解，然后根据最全一样，即首先确定一个初始基本可行解，然后根据最 优性判别准则来检查这个基本可行解是不是最优的。如优性判别准则来检查这个基本可行解是不是最优的。如 果是，则计算结束；如果不是，则进行换基，直至求出果是，则计算结束；如果不是，则进行换基，直至求出 最优解为

17、止。最优解为止。 l计算步骤：计算步骤： 1 1、按照某种规则，找出初始基可行解。、按照某种规则，找出初始基可行解。（最小元素（最小元素 法、法、 2 2、检验是否最优。、检验是否最优。（闭回路法、位势法）（闭回路法、位势法） 3 3、确定换入变量和换出变量，找出新的基可行解。、确定换入变量和换出变量，找出新的基可行解。 ( (闭回路调整法闭回路调整法) ) 4 4、重复、重复2 2、3 3步，直到求得最优解为止。步，直到求得最优解为止。 注意：五个方法注意：五个方法 21 一、确定初始基本可行解（一、确定初始基本可行解（ 按照某种规则，找出初始基可行解。按照某种规则，找出初始基可行解。即在即

18、在 (m(m n) n) 产销平产销平 衡表上给出衡表上给出m+n-1m+n-1个有数字的格个有数字的格，且行和等于该产地产量，列，且行和等于该产地产量，列 和等于该销地销售量。和等于该销地销售量。（最小元素法、（最小元素法、 解释：解释：运输问题实际上有运输问题实际上有m+n-1m+n-1个基变量。在个基变量。在m mn n的产销平衡的产销平衡 表上给出表上给出m+n-1m+n-1个数字格，个数字格，其相对应的调运量的值即为基变量其相对应的调运量的值即为基变量 的值的值。 那么在该例中，应有那么在该例中，应有 3+4-1=63+4-1=6个基变量。个基变量。 1 1、最小元素法。、最小元素法

19、。基本思想：就近供应，即从单位运价基本思想：就近供应，即从单位运价 表中最小的运价开始，尽最大可能用完一个产地的产表中最小的运价开始，尽最大可能用完一个产地的产 量，或满足一个销地的销量，来确定产销关系量，或满足一个销地的销量，来确定产销关系, ,得到满得到满 足者用线划去。逐次寻找最小元素依次类推足者用线划去。逐次寻找最小元素依次类推, ,直到给出直到给出 初始方案为止。优先满足运价最低的供销业务称最小初始方案为止。优先满足运价最低的供销业务称最小 元素法。元素法。 23 解：先画出这个问题的运输表表如下解：先画出这个问题的运输表表如下 24 第一步：从单位运价表中找出最小运价为第一步：从单

20、位运价表中找出最小运价为1，这表示先将，这表示先将 A2 的产品供应的产品供应 B1 。由于。由于A2 每天生产每天生产4吨，吨，B1 每天只需要每天只需要 3吨，即吨，即 A2 除每日能满足除每日能满足B1 的需要外还余的需要外还余1吨。因此在产吨。因此在产 销平衡表销平衡表 (A2 , B1) 交叉处填上交叉处填上3，表示，表示 A2 调运调运3吨给吨给B1 ， 再在单位运价表中将再在单位运价表中将B1 这一列运价划去，表示这一列运价划去，表示 B1 的需求的需求 已满足，不需要继续调运已满足，不需要继续调运 (即即x21 =3=min(a2,b1)=min(4 , 3). 第二步第二步:

21、 从上述未划去的单位运价表的元素中找出最小的从上述未划去的单位运价表的元素中找出最小的 运价运价2 ，即，即A2 把剩余的产品供应给把剩余的产品供应给B3 ；B3 每天需要每天需要5 吨吨 ，A2 只剩余只剩余 1 吨，因此在上述产销平衡表的吨，因此在上述产销平衡表的 (A2 , B3) 交交 叉处填上叉处填上 1，划去上述运价表中，划去上述运价表中A2 这一行运价，表示这一行运价，表示 A2 25 的产品已分配完毕。的产品已分配完毕。 第三步第三步: 从上述第二步所得的单位运价表未划去的元素中从上述第二步所得的单位运价表未划去的元素中 找出最小元素为找出最小元素为 3。这表示将。这表示将 A

22、1 的产品供应的产品供应 B3 ， A1 每每 天生产天生产7 吨，吨，B3 尚缺尚缺 4 吨，因此在产销平衡表的吨，因此在产销平衡表的(A1 , B3) 交叉处填上交叉处填上 4，由于，由于B3 的需求已满足，将第二步的单位的需求已满足，将第二步的单位 运价表中的运价表中的 B3 这一列运价划去。这一列运价划去。 如此，一步步进行下去，直到单位运价表中所有元素如此，一步步进行下去，直到单位运价表中所有元素 都划去为止，最终在产销平衡表上就可以得到一个初始调都划去为止，最终在产销平衡表上就可以得到一个初始调 运方案。这个方案的总运费为运方案。这个方案的总运费为 86 元，如下表元，如下表 26

23、 B1B2B3B4产量 A17 A2 4 A39 销量3656 311310 192 74105 8 3 4 1 63 3 总的运输费总的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元元 1436 6 2 5 27 销地销地 产地产地 B1B2B3B4产量产量 A1437 A2314 A3639 销量销量3656 最小元素法求解结果最小元素法求解结果 注意：注意： 1 1、在调运方案中，称填写数字处为、在调运方案中，称填写数字处为有数字的格有数字的格，它对，它对 应运输问题解中的应运输问题解中的基变量的取值基变量的取值（含填数字（含填数字0 0的格），的格），

24、为为m+n-1m+n-1个个；称不填数字处为；称不填数字处为空格空格，对应解中，对应解中非基变量非基变量。 2 2、补补“0”0”问题。问题。当在当在中间中间步骤步骤的未划去的单位运价表的未划去的单位运价表 中寻找最小元素时，发现该元素所在行的剩余产量等于中寻找最小元素时，发现该元素所在行的剩余产量等于 该元素所在列的剩余销售量。这时在产销平衡表相应的该元素所在列的剩余销售量。这时在产销平衡表相应的 位置填上一个数，而在单位运价表中就要位置填上一个数，而在单位运价表中就要同时划去一行同时划去一行 和一列和一列。为了使调运方案中有数字的格仍为（。为了使调运方案中有数字的格仍为（m+n-1m+n-

25、1） 个个( (即保证基变量的个数为即保证基变量的个数为m+n-1m+n-1个个) )，需要在，需要在同时划去同时划去 的行或列的任一空格位置添上一个的行或列的任一空格位置添上一个“0”0”（划去的行或（划去的行或 列不再考虑）列不再考虑），这个，这个“0”0”表示该变量是基变量，只不表示该变量是基变量，只不 过它取值为过它取值为0 0，即此时的调运方案是一个退化的基可行，即此时的调运方案是一个退化的基可行 解。如下例或教材表解。如下例或教材表3-123-12。 3 3、同时存在两个或两个以上相等的最小运价时，任选其一。、同时存在两个或两个以上相等的最小运价时，任选其一。 B1B2B3B4 A

26、153104 A21696 A3201057 销地销地 产地产地B1B2B3B4产量产量 A15049 A2314 A377 销量销量3584 123 4 5 6 6 例：补例：补0问题问题 在这个例子中，当在填入第三数字的格在这个例子中，当在填入第三数字的格 ( A1, B4 ) 时时, 在填入在填入 4 之后，恰好产销平衡，就必须在单位运价之后，恰好产销平衡，就必须在单位运价 表中同时划去第一行和第四列。为了使有数字的格不表中同时划去第一行和第四列。为了使有数字的格不 减少，减少，( 有数字的格的总数应为有数字的格的总数应为m + n 1个个 )可以在空可以在空 格格( A1, B1 )

27、、 ( A1, B3 ) 、 ( A2, B4 ) 、( A3, B4 )中任选中任选 一个格添加一个一个格添加一个“0”；同样，这个添加的；同样，这个添加的“0”格当格当 作基变量，取值为作基变量，取值为0。我们这里是在。我们这里是在 ( A1, B3 ) 处填处填0 （即初始调运方案是一个退化的基可行解）。（即初始调运方案是一个退化的基可行解）。 销地 产地 B1 B2 B3 B4 B5 产量 ai 销量bj B1 B2 B3 B4 B5 10 20 5 9 10 10 8 25 6 21 15 7 10 4 平衡表平衡表运价表运价表 例（参考）例（参考）此题目没有补此题目没有补0，按照规

28、则也可以做对，按照规则也可以做对 销地销地 产地产地 B1 B2 B3 B4 B5 产量产量 ai 销量销量bj B1 B2 B3 B4 B5 10 20 5 9 10 10 8 25 6 21 15 7 10 4 平衡表平衡表运价表运价表 初始基本可行解为初始基本可行解为 x12,x13,x14,x22,x31,x32,x35=1,5,3,4,3,0,5, 相应运价为：相应运价为： c12,c13,c14,c22,c31,c32,c35=20,5,9,10,1,15,4, 由此表上作业得初始调运方案的总运费为由此表上作业得初始调运方案的总运费为 Z=1x20+5x5+3x9+4x10+3x1

29、+0 x15+5x4=135（元）（元） 153 4 305 解解 1 5 23 4 4 1 5 1 6 7 初始基可行解初始基可行解最小元素法（最小元素法（1） 例例 最小元素法（最小元素法（2） 最小元素法（最小元素法（3） 最小元素法（最小元素法（4） 最小元素法（最小元素法（5） 最小元素法（最小元素法（6） 39 401 41 2 42 3 43 4 5 44 同时同时 划去划去A A3 3行和行和B B4 4列得到初始方案列得到初始方案 6 6 45 思路：思路：最小元素法的缺点是，为了节省一最小元素法的缺点是，为了节省一 处的费用，有时造处的费用，有时造成在其它地方要花多几倍的成

30、在其它地方要花多几倍的 运费。沃格尔法考虑到，一产地的产品，假如运费。沃格尔法考虑到，一产地的产品，假如 不能按最小运费就近供应，就考虑次小运费。不能按最小运费就近供应，就考虑次小运费。 这就有一个差额，差额越大，说明不能按最小这就有一个差额，差额越大，说明不能按最小 运费调运时，运费增加就越多。因此，对于差运费调运时，运费增加就越多。因此，对于差 额最大处额最大处 ，就优先采用最小运费调运。，就优先采用最小运费调运。 48 用例子来说明伏格尔法的具体实施过程，步骤如下：用例子来说明伏格尔法的具体实施过程，步骤如下： 第一步：在单位运价表中增加一行和一列，列的格位置相应第一步：在单位运价表中增

31、加一行和一列，列的格位置相应 填入该行的次小运费与最小运费之差，我们称之为行差额。行的填入该行的次小运费与最小运费之差，我们称之为行差额。行的 格位置相应填入该列的次小运费与最小运费之差，我们称之为列格位置相应填入该列的次小运费与最小运费之差，我们称之为列 差额。如此可得表差额。如此可得表 销地销地 产地产地 B1B2B3B4行差额行差额 A13113100 A219281 A3741051 列差额列差额2513 49 第二步：从行差额和列差额中选出最大者，选择它所在第二步：从行差额和列差额中选出最大者，选择它所在 的行或列中的最小元素。比较该元素所在的行和列的产的行或列中的最小元素。比较该元

32、素所在的行和列的产 量，取它们最小者填入产销平衡表相应的位置。同时在量，取它们最小者填入产销平衡表相应的位置。同时在 单位运价表中划去一行或一列。由表可知单位运价表中划去一行或一列。由表可知 B2 的列差额最大。的列差额最大。 B2 列中最小元素为列中最小元素为 4（即（即 A3 行），可确定行），可确定 A3 产品优先供应产品优先供应 B2 。 比较它们的产量和销量，可知在单位运价表中划去比较它们的产量和销量，可知在单位运价表中划去 B2 列。在产列。在产 销平衡表的销平衡表的( A3 , B2 ) 空格处填入空格处填入 6。 第三步：对上述未划去的元素再分别计算出各行、各列第三步：对上述未

33、划去的元素再分别计算出各行、各列 的差额。重复第一、二步的工作，直到给出初始解为止。的差额。重复第一、二步的工作，直到给出初始解为止。 本问题利用伏格尔方法给出的初始调运方案如下表所示。本问题利用伏格尔方法给出的初始调运方案如下表所示。 50 销地销地 产地产地B1B2B3B4产量产量 A1527 A2314 A3639 销量销量3656 51 2021-6-651 销地 产地 B1 B2 B3 B4 A1 5 2 0 0 0 7 A2 3 1 1 1 1 6 A3 6 3 1 2 2 2 2 5 1 1 1 1 3 3 2 2 20 20 3 113 10 29 47 1 10 8 5 1

34、2 34 5 6 6 总的运输费总的运输费(31)+(64) +(53) +(18)+(210)+(35)=85元元 m + n 1 m + n 1 个。）个。） 3、方法特点：方法特点：解的质量比较好，常用作求运输问题解的质量比较好，常用作求运输问题 的的近似最优解。近似最优解。一般来说，比用最小元素法所求出的一般来说，比用最小元素法所求出的 初始解更接近于最优解。在产地和销地数量不多时，初始解更接近于最优解。在产地和销地数量不多时， 此法给出的初始方案有时就是最优方案。本例用伏格此法给出的初始方案有时就是最优方案。本例用伏格 尔方法给出的初始解就是最优解。尔方法给出的初始解就是最优解。 5

35、3 54 1 55 1 56 2 57 2 58 3 4 60 61 按照上述最小元素法和沃格尔法两种方法所产按照上述最小元素法和沃格尔法两种方法所产 生的一组变量的取值将满足下面条件：生的一组变量的取值将满足下面条件： (1)(1)所得的变量均为非负，且所得的变量均为非负，且基变量总数恰好为基变量总数恰好为 （m + n 1m + n 1） 个个； (2)(2)所有的所有的约束条件均得到满足约束条件均得到满足； (3) (m + n 1 )(3) (m + n 1 )个个基变量对应的系数列向量是基变量对应的系数列向量是 线性独立的线性独立的。（所得的变量不构成闭回路）。（所得的变量不构成闭回

36、路） 因此是基可行解因此是基可行解 最优性检验就是检查所得到的方案是不是最优方最优性检验就是检查所得到的方案是不是最优方 案。检查的方法与单纯形方法中的原理相同，即计案。检查的方法与单纯形方法中的原理相同，即计 算检验数。由于目标要求极小，因此，当所有的检算检验数。由于目标要求极小，因此，当所有的检 验数都大于或等于零时该调运方案就是最优方案；验数都大于或等于零时该调运方案就是最优方案； 否则就不是最优，需要进行调整。否则就不是最优，需要进行调整。 方法方法：求各：求各非基变量的检验数非基变量的检验数，即在表上，即在表上求空格的求空格的 检验数检验数，当所有，当所有 ij ij 0 0，得到最

37、优 ，得到最优解。如果达到最优解。如果达到最优 解，则停止计算，否则，转入下一步；解，则停止计算，否则，转入下一步； 1 1、闭回路法、闭回路法 l2 2、对偶变量法、对偶变量法( (位势法位势法) ) 二、基可行解的最优性检验二、基可行解的最优性检验 1 1）某）某空格空格的闭回路的闭回路： 因为任意非基向量均可因为任意非基向量均可 表示为基向量的唯一线性组合表示为基向量的唯一线性组合) )（参考（参考P110.4P110.4） 闭回路示意图闭回路示意图 1、闭回路法（、闭回路法（cycle method） 2 2）若把闭回路的各变量格看作节点，在表中可以画出如下形式）若把闭回路的各变量格看

38、作节点，在表中可以画出如下形式 的闭回路：的闭回路： （几种常见形式）（几种常见形式） 65 表表3-153-15（以非基变量（以非基变量 x x22 22 为起始顶点的闭回路） 为起始顶点的闭回路） 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量产量 3 3 11 11 3 3 4 4 10 10 3 3 7 7 1 1 3 3 9 9 2 2 1 1 8 8 4 4 7 7 4 4 6 6 10 10 5 5 3 3 9 9 销量销量3 36 65 56 6 20(20(产销平衡产销平衡) ) A1 A2 A3 66 空空 格格闭闭 回回 路路 (A1 , B1)

39、(1,1) (1,3) (2,3) (2,1)(1,1) (A1 , B2)(1,2) (1,4) (3,4) (3,2)(1,2) (A2 , B2)(2,2) (2,3) (1,3) (1,4) (3,4) (3,2) (2,2) (A2 , B4)(2,4) (2,3) (3,3) (1,4)(2,4) (A3 , B1)(3,1) (3,4) (1,4) (1,3) (2,3) (2,1) (3,1) (A3 , B3)(3,3) (3,4) (1,4) (1,3) (3,3) 3)3)显然，闭回路上一组变量对应约束条件的系数列向显然，闭回路上一组变量对应约束条件的系数列向 量线性相关

40、。因此，在运输问题的基可行解迭代过程量线性相关。因此，在运输问题的基可行解迭代过程 中，中，不允许出现不允许出现全部顶点由填数字格构成的闭回路全部顶点由填数字格构成的闭回路。 推论：推论：产销平衡运输问题的产销平衡运输问题的 m + n -1 m + n -1 个变量构成个变量构成 基变量的充分必要条件是它不含闭回路。基变量的充分必要条件是它不含闭回路。 这个推论给出了运输问题基解的重要性质，因为利这个推论给出了运输问题基解的重要性质，因为利 用它来判断用它来判断 m+n-m+n-1 1个变量是否构成基变量比直接判断个变量是否构成基变量比直接判断 这些变量所对应的系数列向量组是否线性无关要简单

41、这些变量所对应的系数列向量组是否线性无关要简单 和直观。和直观。 2021-6-668 4）闭回路计算检验数的方法及经济解释）闭回路计算检验数的方法及经济解释 闭回路法计算检验数：闭回路法计算检验数：就是对于代表非基变量的空格就是对于代表非基变量的空格 （其调运量为零），把它的调运量调整为（其调运量为零），把它的调运量调整为1 1，由于产销平衡的，由于产销平衡的 要求要求, ,必须对这个空格的闭回路中的各顶点的调运量加上或减必须对这个空格的闭回路中的各顶点的调运量加上或减 少少1 1。最后计算出由。最后计算出由这些变化给整个运输方案的总运输费带来这些变化给整个运输方案的总运输费带来 的变化。以

42、这个变化的数值，作为各空格（非基变量）的检的变化。以这个变化的数值，作为各空格（非基变量）的检 验数。验数。 2021-6-669 销地 产地 B1 B2 B3 B4 产量 A1 （+） 4 （-） 3 7 A2 （-） 3 1 （+） 4 A3 63 9 销量 3 6 5 6 10 8 5 3 11 3 10 29 47 1 从非基变量从非基变量 出发，找到一个闭回路如上表所示。回路有四出发，找到一个闭回路如上表所示。回路有四 个顶点，除个顶点，除 外，其余都为基变量。外，其余都为基变量。 调整调运量：调整调运量： ，运费增加了，运费增加了3 3元；元； ，运费减少，运费减少3 3元元 ，运

43、费增加，运费增加2 2元；元； ，运费减少，运费减少1 1元元 调整后，调整后，总运费增加总运费增加：3-3+2-1=13-3+2-1=1元。元。 说明如果让说明如果让 为基变量，运费就会增加，其增加值为基变量，运费就会增加，其增加值1 1作为作为 的的检验数检验数， 1 11 x 1 23 x 1 13 x 11 x 1 21 x 11 x 11 x 11 x (1)(1) 同样，可以计算出以非基变量同样，可以计算出以非基变量 x x22 22 为起始顶点的闭回路调 为起始顶点的闭回路调 整使总的运输费用发生的变化为整使总的运输费用发生的变化为9 2 + 3 10 + 5 4 9 2 + 3

44、 10 + 5 4 1 1 ，即总的运费增加，即总的运费增加 1 1 个单位，这就说明这个调整不能改个单位，这就说明这个调整不能改 善目标值。善目标值。 从上面的讨论可以看出，从上面的讨论可以看出，当某个非基变量增加一个单位时，当某个非基变量增加一个单位时， 有若干个基变量的取值受其影响。有若干个基变量的取值受其影响。 这样，利用单位产品变化（运输的单位费用）可计这样，利用单位产品变化（运输的单位费用）可计 算出它们对目标函数的综合影响，其作用与线性规划算出它们对目标函数的综合影响，其作用与线性规划 单纯形方法中的检验数完全相同。故也称这个单纯形方法中的检验数完全相同。故也称这个综合影综合影

45、响响为该非基变量对应的检验数。为该非基变量对应的检验数。闭回路方法原理就是闭回路方法原理就是 通过寻找闭回路来找到非基变量的检验数。通过寻找闭回路来找到非基变量的检验数。 检验数：检验数：非基变量增加一个单位引起的成本变化量非基变量增加一个单位引起的成本变化量 按上述作法，按上述作法，可计算出表中的所有非基变量的检验可计算出表中的所有非基变量的检验 数，把它们填入相应位置的方括号内数，把它们填入相应位置的方括号内，如下表所示。，如下表所示。 71 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量产量 A A1 1 3 3 (1)(1) 1111 (2)(2) 3 3 4

46、 4 10 10 3 3 7 7 A A2 21 1 3 3 9 9 (1) 2 2 1 1 8 8 (-1) 4 4 A A3 37 7 (10)(10) 4 4 6 6 10 10 (12)(12) 5 5 3 3 9 9 销量销量3 36 65 56 6 20(20(产销平衡产销平衡) ) 初始基本可行解及检验数初始基本可行解及检验数 72 空空 格格闭闭 回回 路路检验数检验数 (A1 , B1)(1,1) (1,3) (2,3) (2,1)(1,1)1 (A1 , B2)(1,2) (1,4) (3,4) (3,2)(1,2)2 (A2 , B2)(2,2) (2,3) (1,3)

47、(1,4) (3,4) (3,2) (2,2) 1 (A2 , B4)(2,4) (2,3) (3,3) (1,4)(2,4)-1 (A3 , B1)(3,1) (3,4) (1,4) (1,3) (2,3) (2,1) (3,1) 10 (A3 , B3)(3,3) (3,4) (1,4) (1,3) (3,3)12 在一个闭回路上，如果规定作为起始顶点在一个闭回路上，如果规定作为起始顶点 的非基变量（空格）为第的非基变量（空格）为第 1 1 个顶点，闭回路个顶点，闭回路 的其他顶点依次为第的其他顶点依次为第 2 2 个顶点、第个顶点、第 3 3 个顶个顶 点点，那么就有，那么就有 ij i

48、j = ( = (闭回路上的奇数次顶点单位运费之闭回路上的奇数次顶点单位运费之 和和) - () - (闭回路上的偶数次顶点单位运费之和闭回路上的偶数次顶点单位运费之和) ) 其中其中 ij ij 为非基变量的下角指标。为非基变量的下角指标。 5 例例：非基变量非基变量xij的检验数的检验数cij -zij闭回路法闭回路法(1) 5 闭回路法闭回路法(2) 5 5 闭回路法闭回路法(3) 75 5 闭回路法闭回路法(4) 9 57 5 闭回路法闭回路法(5) -11 57 9 5 闭回路法闭回路法(6) -3 57 9 -11 80 收收点点 发发点点 B1B2B3B4发发量量 A16 25

49、2344 A244 27 35 16 A37658 3 3 收收量量243413 81 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 82 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 83 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 84 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344

50、 A244 27 35 16 A37658 3 3 收收量量243413 85 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 86 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 87 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 88 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A24

51、4 27 35 16 A37658 3 3 收收量量243413 89 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 90 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 91 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 92 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27

52、 35 16 A37658 3 3 收收量量243413 93 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 94 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 95 收收点点 发发点点 B1B2B3B4发发量量 A16 25 2344 A244 27 35 16 A37658 3 3 收收量量243413 96 收点收点 发点发点 B1 B2 B3 B4 发量发量 A1 6 2 5 2 3(-5) 4(

53、-2) 4 A2 4 (-1) 4 2 7 3 5 1 6 A3 7(-1) 6(-1) 5(-5) 8 3 3 收量收量 2 4 3 4 13 显然，当所有非基变量的检验数均大于或等于显然，当所有非基变量的检验数均大于或等于 零时，调运方案就是最优方案，因为此时对现行方零时，调运方案就是最优方案，因为此时对现行方 案作任何调整都将导致总的运输费用增加。案作任何调整都将导致总的运输费用增加。 闭回路法的主要缺点是：闭回路法的主要缺点是：用闭回路法求检验数用闭回路法求检验数 时，需要给每一空格找一条闭回路。当产销点很多时，需要给每一空格找一条闭回路。当产销点很多 时，寻找闭回路以及计算两方面都会

54、产生困难。时，寻找闭回路以及计算两方面都会产生困难。 在运输问题的数学模型中（在运输问题的数学模型中（P P98 98），设 ），设u u1 1 ，u u2 2， u um m ( (与 与 前前m m个等式对应个等式对应) )， ，v v1 1 ，v v2 2 v vn n ( (与后与后n n个等式对应个等式对应) )分分 别为对应运输问题的别为对应运输问题的m+nm+n个约束条件的对偶变量。步骤个约束条件的对偶变量。步骤 如下：如下： step1 step1 从任意从任意基变量（填数字格）基变量（填数字格）对应的对应的 c cij ij开始 开始, ,利利 用公式用公式c cij ij=

55、u =ui i+v+vj j 依次找出依次找出(m+n-1)(m+n-1)个个u ui i,v,vj j；任意给出一任意给出一 个个u ui i或或v vj j 值，推算出其它位势值。值，推算出其它位势值。称这些称这些u ui i,v,vj j为该基为该基 本可行解对应的位势；（本可行解对应的位势；（填数字格中按填数字格中按c cij ij=u =ui i+v+vj j确立确立 ui i,vj j ，方程组的解称为位势，方程组的解称为位势） step2step2 计算计算非基变量（空格）非基变量（空格）的检验数：的检验数： ij ij=c =cij ij- - （u ui i+v+vj j），

56、），填入括号内填入括号内 2.2.位势法（位势法（dual variable method,dual variable method,对偶变量法）对偶变量法） 第一步：第一步：在表上增加一行和一列，列中填入行位势在表上增加一行和一列，列中填入行位势ui ， 行中填入列位势行中填入列位势vj 。 按按 ui + vj = cij ( i , j ) 基变量指标集，列出方程组基变量指标集，列出方程组 先令先令u1= 0 ，由，由u1 + v3 = c13 = 3 可得可得v3 = 3 ，由，由u1 + v4 = c14 = 10 可得可得v4 = 10；在；在v4 = 10时，由时，由u3 + v

57、4 = c34 = 5 可得可得 u3 = -5 。以。以 此类推可确定所有的此类推可确定所有的 ui 、vj 的值。的值。 100 销地销地 产地产地 B1B2B3B4行位势行位势 ui A1 3 11 3 4 10 3 0 A2 1 3 9 2 1 8 -1 A3 7 4 6 10 5 3 -5 列位势列位势 vj 29310 初始基本可行解及位势值初始基本可行解及位势值 第二步：按第二步：按 ij = cij (ui + vj ) ,( i , j ) 非基变量指标集，非基变量指标集， 计算所有的空格检验数计算所有的空格检验数。如：。如： 11 = c11 (u1 + v1 ) =3 (

58、 0 + 2 ) = 1 12 = c12 (u1 + v2 ) = 11 - ( 0 + 9 ) = 2 这些计算可直接在表上进行。为了方便，特设计这些计算可直接在表上进行。为了方便，特设计 计算表，如下表。右上角框内的数为单位运价。计算表，如下表。右上角框内的数为单位运价。 102 销地销地 产地产地 B1B2B3B4行位势行位势 ui A1 3 (1) 11 (2) 3 (0) 10 (0) 0 A2 1 (0) 9 (1) 2 (0) 8 (-1) -1 A3 7 (10) 4 (0) 10 (12) 5 (0) -5 列位势列位势 vj 29310 在上表中还有负的检验数，说明还未得

59、到最优解，还得进一步在上表中还有负的检验数，说明还未得到最优解，还得进一步 进行改进。进行改进。 103 B1B2B3B4ui A1 A2 A3 vj 311310 192 74105 8 注意：基变量的检验数注意：基变量的检验数 i j=Ci j -（ui+vj）=0 4 3 63 1 3 例：位势法求检验数例：位势法求检验数 104 B1B2B3B4ui A1 A2 A3 vj 311310 192 74105 8 令令u1=0 u1+v3=3 u1+ v4 =10 u2+ v3=2 u2+v1=1 u3+v2=4 u3+ v4=5 4 3 63 1 3 105 l2l10l3l9lvj

60、l-5 lA3 l-1lA2 l0 lA1 luilB4lB3lB2lB1 4 3 6 3 1 3 当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案，说明现行方案 为最优方案，否则目标成本还可以进一步减小。为最优方案，否则目标成本还可以进一步减小。 注意：非基变量的检验数注意：非基变量的检验数 i j=ci j -（ui+vj） 11=c11 -（u1+v1）=3-(0+2)=1 31=c31 -（u3+v1）=7-(2-5)=10 24=c24 -（u2+v4）=8-(10-1)=-1 22=c22 -（u2+v2）=9-(9-1)=1 12=c12 -（u1+v2）=1