运筹学第三章运输问题

1、运输问题运输问题Transportation Problem主要内容主要内容运输问题及其数学模型运输问题及其数学模型运输问题的表上作业法运输问题的表上作业法运输问题运输问题 把货物从一系列起始地（把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）（如仓库、顾客）如何分析这类问题？如何分析这类问题？例例1 某公司从两个产地某公司从两个产地A A1 1、A A2 2将物品运往三个销地将物品运往三个销地B B1 1、B B2 2、B B3 3，各产地的产量、各销地的销量和各，各产地的产量、各销地的销量

2、和各产地运往各销地每件物品的单位运费如下表所产地运往各销地每件物品的单位运费如下表所示，应如何调运可使总运输费用最小？示，应如何调运可使总运输费用最小？如何设置变量？111213212223111213212223112112221323min646655200300150. .1502000,1,2,1,2,3ijzxxxxxxxxxxxxxxstxxxxxij一般运输模型 销地销地 产地产地B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量销量b1b2bnQ一般运输问题的数学模型一般运输问题的数学模型 m nMin z = cij xij

3、 i = 1 j = 1 n s.t. xij = ai i = 1,2,m j = 1 m xij = bj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n)运输问题数学模型的特点运输问题数学模型的特点运输问题是否一定有运输问题是否一定有最优解最优解？运输问题模型的运输问题模型的系数矩阵系数矩阵的特征的特征运输问题运输问题解的形式解的形式 1 1、平衡运输问题必有可行解，也必有最优解；、平衡运输问题必有可行解，也必有最优解； 2 2、运输问题的基可行解中应包括、运输问题的基可行解中应包括 m+n1 个基变量。个基变量。运输问题的其它形式运输问题的其它

4、形式 总供应量总供应量总需求量的情形总需求量的情形 目标函数最大化的情形，如目标是追求利润目标函数最大化的情形，如目标是追求利润或收入时，只需将或收入时，只需将目标函数目标函数改为改为maxmax即可即可 某些路线的运输能力有一定限制的情形某些路线的运输能力有一定限制的情形 某些运输路线中断情形，如由于自然灾害或某些运输路线中断情形，如由于自然灾害或劳动纠纷导致的劳动纠纷导致的 删除变量删除变量，单位运价改为，单位运价改为运输问题的表上作业法运输问题的表上作业法建模建模给出初始的给出初始的基可行解基可行解判断是否为最优判断是否为最优解的改进解的改进 运输表运输表 最小元素法、西北角法、最小元素

5、法、西北角法、沃格尔法沃格尔法 闭回路法、位势法闭回路法、位势法 解的改进解的改进运输表运输表 销地销地 产地产地B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量销量b1b2bnQ初始调运方案初始调运方案（初始的基可行解）（初始的基可行解）最小元素法最小元素法西北角法西北角法沃格尔法沃格尔法最小元素法最小元素法 销地销地 产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656最小元素法最小元素法 销地销地 产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量365

6、6314363总的运输费用（总的运输费用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元最小元素法最小元素法优先满足所有优先满足所有单位运价最小单位运价最小的位置的的位置的最大最大运量运量要求要求消掉产地或销地（消掉一行或一列）消掉产地或销地（消掉一行或一列）再优先满足再优先满足剩余的单位运价最小剩余的单位运价最小的位置的的位置的最大运量要求最大运量要求西北角法西北角法 销地销地 产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656总的运费总的运费(3(33)3)(4(4

7、11)11)(2(29)9)(2(22)2)(3(310)10)(6(65)5)135135元元342236沃格尔法沃格尔法 销地销地 产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656633512总的运费总的运费(3(35)5)(10(102)2)(1(13)3)(8(81)1)(4(46)6)(5(53)3)8585元元沃格尔法沃格尔法罚数如何计算罚数如何计算行罚数、列罚数是否等价行罚数、列罚数是否等价消掉行或列后罚数是否应该重新计算消掉行或列后罚数是否应该重新计算相等的罚数如何选取相等的罚数如何选取初始调运方案的比较初始调运方案的比较最小元素

8、法最小元素法西北角法西北角法沃格尔法沃格尔法一般情况下总运费较小一般情况下总运费较小便于计算机求解便于计算机求解最直观的求解表现最直观的求解表现最优调运方案？最优调运方案？检验检验最优解的判别最优解的判别闭回路法闭回路法位势法位势法检验数，基变量检验数，非基变量检验数检验数，基变量检验数，非基变量检验数所有非基变量检验数？所有非基变量检验数？最优最优闭回路法闭回路法闭回路是在已给出调运方案闭回路是在已给出调运方案的运输表上的运输表上从一个空格出发，从一个空格出发，沿水平或垂直方向前进，遇沿水平或垂直方向前进，遇到有数字的格直行或转到有数字的格直行或转9090度度，这样继续下去，直至回到出这样继

9、续下去，直至回到出发的那个空格，由此形成的发的那个空格，由此形成的封闭折线叫做闭回路。封闭折线叫做闭回路。每一个空格存在唯一的闭回每一个空格存在唯一的闭回路。路。311310431928317410563闭回路闭回路XX433X1XX6X3XX433X1XX6X3XX433X1XX6X3XX433X1XX6X3XX433X1XX6X33113 10192874 105121-110闭回路法闭回路法XX433X1XX6X3+1-1+1-1XX523X01X6X3X初始调运方案初始调运方案改进调运方案改进调运方案闭回路法闭回路法对于代表非基变量的空格（其调运量为零），对于代表非基变量的空格（其调运

10、量为零），把它的调运量调整为把它的调运量调整为1，由于产销平衡的要求，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量我们必须对这个空格的闭回路的顶点的调运量加上或减少加上或减少1。最后计算出由这些变化给整个运输方案的总运最后计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则零，则已求得最优解，否则继续迭代继续迭代找出最优找出最优解。解。位势法位势法 对运输表上的每一行赋予一个数值对运输表上的每一行赋予一个数值ui

11、，对每一列赋，对每一列赋予一个数值予一个数值vj，它们的数值是由，它们的数值是由基变量基变量xij的检验数的检验数 所决定的所决定的 非基变量非基变量xij的检验数就可以用公式的检验数就可以用公式 求出求出0ijijijcuv（）ijijijcuv（）位势法位势法 销地销地产地产地 B1 B2 B3 B4 ui A1311310 X X 4 3 A21928 3 X 1X A374105 X 6 X 3 vj 3 10-59-12121-110120运量调整运量调整存在检验数存在检验数ij0，因此可以进行运量调整（即解的改，因此可以进行运量调整（即解的改进），使得总运费有所降低进），使得总运费

12、有所降低Min （ij0 ）xij画出其闭回路，在闭回路顶点上进行画出其闭回路，在闭回路顶点上进行运量调整运量调整选取所有偶数顶点的选取所有偶数顶点的min （xij ），令所有奇数顶点增加），令所有奇数顶点增加该运量，偶数顶点减少该运量，在为零的偶数顶点中选该运量，偶数顶点减少该运量，在为零的偶数顶点中选一对其所在格打叉，保证基变量的个数始终为一对其所在格打叉，保证基变量的个数始终为m+n-1个个310 4 328 1X12341250 x产销不平衡的运输问题产销不平衡的运输问题模型模型表上作业的实现表上作业的实现B1B2B3B4销量销量A12113470A21035950A3781270产产量量20304060B540000150190例：存在退化例：存在退化B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125运输问题应用运输问题应用有三个产地有三个产地A1-3A1-3，生产同一种物品，使用者为，生产同一种物品，使用者为B1-3B1-3，单位运价见下表。由于销售需要和客观条件的限制，单位运价见下表。由于销售需要和客观条件的限制，产地产地A1A1至少要发出至少要发出6 6个单位，最多能生产个单位，最多能生产1111个单位；产个单位；产地地A2A2必须发出必须发出7 7单位的产品；单位的产品；A3A3至少要发出至少要发出4 4个