第三部分运输问题

1、 运输问题与有关概念运输问题与有关概念 运输问题的求解运输问题的求解表上作业法表上作业法 问题的提出问题的提出 一般的运输问题就是要解决把某种产一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案何确定一个使得总的运输费用最小的方案. . 销地销地产地产地B1B2B3产量产量A1646200A2655300销量销量150150200例例3.1 某公司从两个产地某

2、公司从两个产地A1、A2将物品运往三个销将物品运往三个销地地B1、B2、B3，各产地的产量、各销地的销量和各各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？应如何调运可使总运输费用最小？ 解：解： 产销平衡问题：产销平衡问题： 总产量总产量 = = 总销量总销量 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量的运输量， 得到下列运输量表：得到下列运输量表： 销地销地产地产地B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200 mi

3、n f = = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 (i=1 , 2；j =1 , 2 , 3）系数矩阵 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 模型系数矩阵特征模型系数矩阵特征 1.共有共有 2+3 行，分别表示各行，分别表示各 产地产地和销地；和销地；2 3 列，分别表示各变量；列，分别表

4、示各变量； 2.每列只有两个每列只有两个 1 1，其余为，其余为 0 0，分别，分别表示只有一个产地和一个销地被使用。表示只有一个产地和一个销地被使用。 某公司从三个产地某公司从三个产地A1、A2、A3 将物品运将物品运往四个销地往四个销地B1、B2、B3、B4，各产地的产量、各各产地的产量、各销地的销量和各产地运往各销地每件物品的运费销地的销量和各产地运往各销地每件物品的运费如下表所示如下表所示销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 3 3 1 11 1 3 3 1 10 0 7 7 A A2 2 1 1 9 9 2 2 8 8 4

5、 4 A A3 3 7 7 4 4 1 10 0 5 5 9 9 销销量量 3 3 6 6 5 5 6 6 2 20 0 （产产销销平平衡衡） 问应如何调运，可使得总运输费最小问应如何调运，可使得总运输费最小? 这是一个产销平衡的运输问题，设这是一个产销平衡的运输问题，设 xij 为从产为从产地地 Ai 运往销地运往销地 Bj 的的运输量（运输量（i = 1，2，3； j = 1，2，3，4）所以此运输问题的线性规划模型如下：所以此运输问题的线性规划模型如下： Min f = 3x11+ 11x12+ 3x13+ 10 x14+ x21+ 9x22 + 2x23+ 8x24+ 7x31+ 4x

6、32+ 10 x33+ 5x34s.t. x11+ x12 + x13 + x14 = 7 x21 + x22+ x23 + x24 = 4 x31 + x32+ x33 + x24 = 9 x11 + x21 + x31 = 3 x12 + x22 + x32 = 6 x13 + x23 + x33 = 5 x14 + x24 + x34 = 6 xij 0 ( i = 1 , 2 , 3；j = 1 , 2 , 3)其系数矩阵为其系数矩阵为 ：10001000100001000100010000100010001000010001000111110000000000001111000000

7、0000001111A 共有共有 3+4 行，分别表示产地和销地；有行，分别表示产地和销地；有 3 4 列分列分别表示各变量；每列只有两个别表示各变量；每列只有两个 1，其余为，其余为 0 。 一般运输问题的提法：一般运输问题的提法： 假设假设 A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn 表示某物资的表示某物资的n个销地；个销地；ai 表示产地表示产地 Ai 的产量；的产量；bj 表示销地表示销地 Bj 的销量；的销量；cij 表示把物资从表示把物资从产地产地 Ai 运往销地运往销地 Bj 的单位运价。如果的单位运价。如果a1 + a2 + + am =

8、b1 + b2 + + bn ， 则称该运输问题为产销平衡则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论一般运问题；否则，称产销不平衡。下面，首先讨论一般运输问题。输问题。销地销地 产地产地 B1 B2 Bn 产量产量 A1 A2 Am c11 c12 c1n c21 c22 c2n cm1 cm2 cmn a1 a2 am 销量销量 b1 b2 bn 设设 xij 为从产地为从产地 Ai 运往销地运往销地 Bj 的运输量的运输量ijminjijxcf 11minmiaxtsinjij,2 , 1)(.1 njbxjmiij,2,1),(1 njmixij,2, 1,2,10

9、 对于产销平衡问题，可得到下列运输问题的模型：对于产销平衡问题，可得到下列运输问题的模型： ijminjijxcf 11minmiaxtsinjij, 2 , 1. .1 njbxjmiij, 2 , 11 njmixij,2,1, 2,10 在实际问题建模时，还会出现如下一些变化：在实际问题建模时，还会出现如下一些变化： 有时目标函数求最大，如求利润最大或营业额有时目标函数求最大，如求利润最大或营业额最大等；最大等； 当某些运输线路上的能力有限制时，模型中可当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；直接加入（等式或不等式）约束； 产销不平衡的情况。当销量大于产量时

10、可加入产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在产一个虚设的产地去生产不足的物资，这相当于在产量约束条件中加上量约束条件中加上 m 个松弛变量；当产量大于销量个松弛变量；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相时可加入一个虚设的销地去消化多余的物资，这相当于在需求约束条件中减去当于在需求约束条件中减去 n 个松弛变量。个松弛变量。运输问题求解的有关概念运输问题求解的有关概念 1、基变量的特点、基变量的特点 （1）基变量共有）基变量共有 m + n -1 个个 （2）产销平衡运输问题的）产销平衡运输问题的 m + n -1 个变量构成个变

11、量构成基变量的充分必要条件是不含闭回路基变量的充分必要条件是不含闭回路 . 运输问题是一种特殊的线性规划问题，在求解运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如时依然可以采用单纯形法的思路，如图图2-1所示所示. .由于运输规划系数矩阵的特殊性，如果直接使用由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算线性规划单纯形法求解计算, ,则无法利用这些有利则无法利用这些有利条件条件. .人们在分析运输规划系数矩阵特征的基础上人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法建立了针对运输问题的表上作业法. .在这里需要讨在这里需要讨论

12、基本可行解、检验数以及基的转换等问题论基本可行解、检验数以及基的转换等问题. .基本可行解基本可行解是否最优解是否最优解结束结束换基换基是是否否 决策变量格凡是能够排列成下列形式决策变量格凡是能够排列成下列形式 xab, xac, xdc，xde, xst , xsb （3.1） 或或 xab, xcb, xcd, xed, xst , xat (3.2) 其中，其中，a , d , , s 各不相同；各不相同；b , c , , t 各不相各不相同。我们称之为变量集合的一个闭回路，并将式同。我们称之为变量集合的一个闭回路，并将式（3.1）,（3.2）中的变量称为这个闭回路的顶点）中的变量称为

13、这个闭回路的顶点.例如，例如，x13 , x16 , x36 , x34 , x24 , x23 ； x23 , x53 , x55 , x45 , x41 , x22 ； x11 , x14 , x34 , x31 等都是闭回路。若把闭等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形回路的各变量格看作节点，在表中可以画出如下形式的闭回路：式的闭回路：闭回路示意图闭回路示意图 闭回路均为一封闭折线，它的每一条边，或闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；为水平的，或为垂直的； 闭回路的每一条边（水平的或垂直的）均有闭回路的每一条边（水平的或垂直的）均有且仅有

14、两个闭回路的顶点（变量格）。且仅有两个闭回路的顶点（变量格）。 关于闭回路有如下的一些重要结论：关于闭回路有如下的一些重要结论：根据定义可以看出闭回路的一些明显特点根据定义可以看出闭回路的一些明显特点:： 设设 xab, xac, xdc, xde, xst, xsb 是一个闭回路，那是一个闭回路，那么该闭回路中变量所对应的系数列向量么该闭回路中变量所对应的系数列向量 Pab , pac , pdc , pde , pst , psb 线性相关；线性相关； 若变量组若变量组 xab, xcd , xef , xst 中包含一个部分组中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量构成

15、闭回路，那么该变量组所对应的系数列向量 pab, pcd , pef , , pst 线性相关线性相关. 变量组变量组 xab , xcd , xef , , xst 所对应的系数所对应的系数列向量列向量 pab, pcd , pef , , pst 线性无关的充分必要条线性无关的充分必要条件是这个变量组中不包含闭回路件是这个变量组中不包含闭回路. 产销平衡运输问题的产销平衡运输问题的 m + n -1 个变量构成基个变量构成基变量的充分必要条件是它不含闭回路变量的充分必要条件是它不含闭回路.步骤如下：步骤如下： 在运输问题求解作业数据表中任选一个单元格在运输问题求解作业数据表中任选一个单元格

16、 xij ( Ai 行行 Bj 列交叉位置上的格列交叉位置上的格)，令，令 xij = min ai , bj 即考虑从即考虑从 Ai 向向 Bj 的最大运输量的最大运输量(使行或列在允许使行或列在允许的范围内尽量饱和的范围内尽量饱和, 即使一个约束方程得以满足即使一个约束方程得以满足)，填入填入 xij 的相应位置；的相应位置； 从从 ai 或或 bj 中分别减去中分别减去 xij 的值，即调整的值，即调整 Ai 的拥有的拥有量及量及 Bj 的需求量；的需求量； 若若 ai = 0，则划去对应的行（把拥有的量全部运则划去对应的行（把拥有的量全部运走），若走），若 bj = 0 则划去对应的列

17、（把需要的量全部则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；且只去掉一个约束）； 若运输平衡表中所有的行与列均被划去，则若运输平衡表中所有的行与列均被划去，则转转.按照上述方法所产生的一组变量的取值将满足下按照上述方法所产生的一组变量的取值将满足下面条件：面条件： 所得的变量均为非负，且变量总数恰好为所得的变量均为非负，且变量总数恰好为 m + n 1 个；得到了一个初始基本可行解个；得到了一个初始基本可行解.否则，否则，在剩下的运输平衡表中选下一个变量，在剩下的运输平衡表中选下一个变量， 所有的约束

18、条件均得到满足；所有的约束条件均得到满足； 所得的变量不构成闭回路所得的变量不构成闭回路. 因此，根据定理因此，根据定理3.1及其推论，所得的解一及其推论，所得的解一定是运输问题的基本可行解定是运输问题的基本可行解. 一般较常用的方法有西北角法、最小元素法一般较常用的方法有西北角法、最小元素法和差额法。下面分别举例予以说明和差额法。下面分别举例予以说明. 1、西北角法（左上角方法）、西北角法（左上角方法） 考虑例考虑例3.2 某公司从三个产地某公司从三个产地A1、A2、A3 将物品运往四个销地将物品运往四个销地B1、B2、B3、B4，各产地的各产地的产量、各销地的销量和各产地运往各销地每件物产

19、量、各销地的销量和各产地运往各销地每件物品的运费如表所示：品的运费如表所示： 销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量365620问应如何问应如何调运，可调运，可使得总运使得总运输费最小输费最小? 销销产产A1311310A21928A374105需需求求342236产销平衡表产销平衡表运价表运价表 z = 33 + 411 + 29 + 22 + 310 + 65 = 1352.最小元素法。例最小元素法。例 34（运价小者先安排）（运价小者先安排） 销销产产A17311310A241928A3974105需需求求365620132134

20、4653103产销平衡表产销平衡表运价表运价表 z= 43 +310+ 31+ 12 + 64 + 35 = 863. 差额法差额法（次小运价与最小运价之差大者先安排）（次小运价与最小运价之差大者先安排） 销销产产A1311310A21928A374105需需求求产销平衡表产销平衡表运价表运价表 2 5 1 3 01160123 2 1 2 376512 z = 53 + 210 + 31 + 18 + 64 + 35 = 85上述计算过程可用流程图描述如下（图上述计算过程可用流程图描述如下（图2-2）取未划去的单元格取未划去的单元格xij , ,令令 xij = min ai , bj ai

21、 = ai - xijbj = bj - xijai = 0?划去第划去第i i行行划去第划去第j j列列是是否否 bj = 0否否所有行列是所有行列是否均被划去否均被划去是是找到初始基找到初始基本可行解本可行解图图3-2 求运输问题的初始基本可行解过程求运输问题的初始基本可行解过程应用西北角法和最小元素法，每次填完数，都应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个任意没被划去的格内标一个 0 . 某

22、公司下属有生产一种化工产品的三个产地某公司下属有生产一种化工产品的三个产地A1、A2、A3 ,有四个销售点有四个销售点B1、B2、B3、B4 销售销售这种化工产品这种化工产品.各产地的产量、各销地的销量和各各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费产地运往各销地每吨产品的运费(百元百元)如下表所示如下表所示. 销销产产A1753859A2402948A3806375需需求求35405565195产销平衡表产销平衡表运价表运价表 问应如何调运，可使得总运输费最小问应如何调运，可使得总运输费最小? 解解：用西北角法求初始基本可行解：用西北角法求初始基本可行解 销销产产A13859A

23、22948A36375需需求求产销平衡表产销平衡表运价表运价表35400401565 z = 353 + 408 + 404 + 157 + 655 = 1015 销销产产A1753859A2402948A3806375需需求求35405565195产销平衡表产销平衡表运价表运价表23534045550540925z = 505+259+352+54+ 403+405= 885产销平衡表产销平衡表运价表运价表 销销产产A1753859A2402948A3806375需需求求35405565195 1 5 1 3 3405403352 2 42 2 42 14401525z = 353+155+

24、 259+ 404+ 403 +405= 885 1 1 1练习：求解以下列数据为单位运费的运输问题练习：求解以下列数据为单位运费的运输问题 (1) 销地销地产地产地甲甲乙乙丙丙丁丁产量产量1105672528276253934850销量销销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量12545330234175203219872045436830销量销量1015252030100(2) 销地销地产地产地甲甲乙乙丙丙 丁丁 产量产量125225350销量销量152030 35100甲甲乙乙丙丙 丁丁1056782769348 销地销地产地产地甲甲乙乙丙丙 丁丁 产量产量

25、125225350销量销量152030 35100甲甲乙乙丙丙 丁丁1056782769348 销地销地产地产地甲甲乙乙丙丙 丁丁 产量产量125225350销量销量152030 35100甲甲乙乙丙丙 丁丁1056782769348 销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量130220320430销量销量1015252030100甲甲乙乙丙丙丁丁戊戊25453341752198754368 销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量130220320430销量销量1015252030100甲甲乙乙丙丙丁丁戊戊25453341752198754368 销地销地产地产地甲甲乙乙丙丙丁丁戊戊

26、产量产量130220320430销量销量1015252030100甲甲乙乙丙丙丁丁戊戊25453341752198754368 由于目标要求极小，因此，当所有的检验由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案数都大于或等于零时该调运方案就是最优方案.1. 位势法位势法 首先给出位势概念：首先给出位势概念： 设对应设对应m + n - 1 个基变量个基变量 xij 的的系数系数 cij ，存在存在 ui , vj 满足：满足： ui + vj = cij ，i = 1, , m ； j = 1, , n . 我们称这些我们称这些 ui ,vj 为该基本可行解对应的

27、位势为该基本可行解对应的位势. 由于有由于有 m + n 个变量（个变量（ ui , vj ），），m + n - 1 个方程（基变量个数），故该方程组有解。解个方程（基变量个数），故该方程组有解。解出出 ui , vj i = 1, , m ； j = 1, , n。则检验数为：则检验数为： ij = cij - ui - vj i = 1, , m ; j = 1, , n例：例：首先求解方程组首先求解方程组u1 + v4 = c14 = 10u1 + v3 = c13 = 3 u2 + v1 = c21 = 1 u2 + v3 = c23 = 2u3 + v2 = c32 = 4 u3

28、+ v4 = c34 = 5 令令 u1 = 5 则则有有 v4 = 5 v3 = -2u2 = 4 u3=0v2=4v1= -3再求检验数：再求检验数： 11 = c11 u1 - v1 = 3 5 (-3) = 1 12 = c12 u1 v2 = 11 5 4 = 2 22 = c22 u2 v2 = 9 4 4 = 1 24 = c24 u2 v4 = 8 4 5 = 1 31 = c31 u3 - v1 = 7 0 ( 3) = 10 33 = c33 u3 v3 = 10 0 ( 2) = 12 销销产产 uiA131131073A2192842A3741059- 2需求需求365

29、620vj- 160 7121-11012 2. 加减法加减法 在运价表中在运价表中,每行或每列的元素加上或减去一个每行或每列的元素加上或减去一个数数,使基变量对应的运价变成零使基变量对应的运价变成零.所得各数即为检验数所得各数即为检验数. 510478291103113-3-7+2-6-2+1 01201010100021 (1) 找闭回路：找闭回路：以最小的负检验数对应的非基以最小的负检验数对应的非基变量为起始顶点寻找一个闭回路变量为起始顶点寻找一个闭回路. (2) 求调整量：求调整量： 闭回路上偶数次顶点运量的最闭回路上偶数次顶点运量的最小值为调整量，记作小值为调整量，记作: (3) 调

30、整：调整： 闭回路上的偶数次顶点的调运量减闭回路上的偶数次顶点的调运量减去去 ； 闭回路上的奇数次顶点的调运量加上闭回路上的奇数次顶点的调运量加上 ；非闭回路顶点的其他变量调运量不变；再去掉闭回非闭回路顶点的其他变量调运量不变；再去掉闭回路上的一个零运量路上的一个零运量. 销销产产A1527A2314A3639需需求求365620 24= 1，作，作 x24 的闭回路，调整数的闭回路，调整数=1，调整得，调整得 销销产产A143A231A363需需求求3656 510478291103113-3-7+2-6-1 0120901200020求求调整数得：调整数得：所有的检验数均为非负，因此得到最

31、优解：所有的检验数均为非负，因此得到最优解： x11 = 2 , x13 = 5 , x21 = 1 , x24 = 3 , x32 = 6 , x34 = 3 , 其余的其余的 xij = 0 .总运费为：总运费为： f = 32 + 35 + 11 + 83 + 46 + 53 = 85. 如果非基变量的检验数有等于零的时候，将出如果非基变量的检验数有等于零的时候，将出现多解的情况现多解的情况.上面的例题是多解情况上面的例题是多解情况.(或写成或写成)得最优运输方案为得最优运输方案为: 销销产产A152A231A363例例3.6 已知某运输问题的产销平衡表与单位运价表已知某运输问题的产销平

32、衡表与单位运价表如下表所示，求最优调运方案如下表所示，求最优调运方案.B1B2B3B4B5产量产量A1101520204050A22040153030100A33035405525150销量销量25115603070解：解：由伏格法：由伏格法：B1B2B3B4B5产产量量B1B2B3B4B5A1501015202040A21002040153030A31503035405525销销量量25115603070产销平衡表产销平衡表 单位运价表单位运价表55510205105501052525560105301015657010 152020402040 15 303030 354055 25-20

33、-105-30-55-10001503501500150015150最优性检验：最优性检验：所有的检验数都大于等于所有的检验数都大于等于0，则得到的最优解为如，则得到的最优解为如上表所示，没有赋值的变量都取上表所示，没有赋值的变量都取0值值.总运费为总运费为 z =50 15+10 20+60 15+30 30+15 30 +65 15+70 25=7225练习：求最小运费练习：求最小运费 销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量1101211127102610911101135912121110销量销量5657831 销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量110211310销量销量

34、56578311012111276109111059121211334112135412811352215011251012 11 12 76109 11 105 9 121211最优性检验：最优性检验：9218+310+3311000000400426所有的检验数都大于等于所有的检验数都大于等于0，所以所得指派方案为最，所以所得指派方案为最优指派方案，即：优指派方案，即： 销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量1281021551135510销量销量5657831最小运费为：最小运费为： z=212+87+110+59+511+55+59=260 1、产量大于销量的情况、产量大于销量的

35、情况对于产大于销问题，可得到下列运输问题的模型：对于产大于销问题，可得到下列运输问题的模型： ijminjijxcf 11minmiaxtsinjij,2,1.1 njbxjmiij,2,11 .,2,1;, 2, 10njmixij 某公司从两个产地某公司从两个产地A1、A2将物品运往三个将物品运往三个销地销地B1、B2、B3，各产地的产量、各销地的销量各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？ 销销产产A178131512A245112922需需求求5

36、33625 123114这里，总产量为这里，总产量为 78 + 45 = 123 ；总销量为；总销量为 53 +36 + 25 = 114 . 产销不平衡，增加一个虚设的产销不平衡，增加一个虚设的销地，得到下表销地，得到下表 销销产产A1781315120A2451129220需需求求5236259123计算过程如下：计算过程如下： 销销产产A17813 15120A24511 29220需需求求5236251012321410 012111536010111114525713151201129220121103+120000016122 2、销量大于产量的情况：、销量大于产量的情况：可得到下列运输问题的可得到下列运输问题的模型：模型：ijminjijxcf 11min