运筹学 第3章运输问题

1、Chapter3 运输问题( Transportation Problem ),运输问题的数学模型 表上作业法 运输问题的应用,本章主要内容：,2,从m个发点 向n个收点 发送某种货物. 发点的发 量为 ， 收点的收量为 。由 运 往 单位货物的运费为 ，问如何调配， 才能使运费最省？,问题的提出,3,表1 产销平衡表,上述数据可以汇总于表格中,如下:,表2 单位运价表,4,运输问题的数学模型,设xij代表为从第i个产地调运给第j个销地的物资 的数量.在产销平衡的条件下，即 使总的运费支出最小，可以表为以下数学形式：,5,运输问题的约束方程组系数矩阵及特征,矩阵A是一个m+n行mn列的矩阵，它

2、的秩为m+n-1。 运输问题应该有m+n-1个基变量。 3. xij的系数列向量为：,6,表上作业法,7,表上作业法的基本思路：,确定初始调运方案 最优性检验 改进方案,8,1 确定初始基可行解,运输问题确定初始基可行解，就是求出运输问题的初始调运方案.,确定初始基可行解的方法有 最小元素法 伏格尔法,9,【例2-1】 某公司经销甲产品,下设3个加工厂A1、A2、A3，产品分别运往销售点B1、B2、B3、B4，各工厂的日产量和各销售点的日需求量及各工厂到各销售点的运价如下表所示：（运输问题供需平衡表和运价表如下），求总运费最少的调运方案。,表3-3,10,思路：为了减少运费，应优先考虑单位运价

3、最小(或运距最短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。 由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。,1、最小元素法,11,1. 最小元素法,3,1,4,6,3,3,（思想：就近供应）,不能同时划去行和列,保证填有运量的格子为m+n-1,表3-4,12,最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能在其他供销点多

4、花几倍的运费，从而使整个运输费用增加。,2. 沃格尔法,沃格尔法考虑到： 一个产地的产品假如不能按照最小运费就近供应，就考虑次小运费，这就有个差额。 如果差额不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果差额很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。,13,沃格尔法计算步骤： 1) 分别算出各行、各列的最小运费与次小运费的差额。 2) 从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。 3) 对剩余行、列再分别计算各行、列的差额。返回1)、2)。,14,2.伏格尔法, 2 5 1 3,

5、0 1 1,表3-6, ,6, 2 1 3, 0 1 2,3, 2 1 2, 0 1, , ,3, 1 2, 7 6, ,5,2,1,表3-5,Z=85,15,1 若有两个以上相同的最大差值，可任取其一。 2 剩下一行或者一列有空格，填数字，不能划掉。 3 计算行差，列差时，已经划去的列或者行不再考虑。,16,例 用伏格尔法求初始调运方案,17,初始调运方案,18,2.2 最优解的判别,判别办法是计算空格(非基变量)的检验数,因为运 输问题的目标函数是实现最小化,所以当所有空格处 的检验数大于等于零时,为最优解.,下面分别介绍两种计算检验数的方法: 闭回路法 (2) 位势法,19,闭回路：从空

6、格出发画水平(或垂直)直线，遇到填有运量的方格（数字格）可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。,调运方案的任意空格一定存在唯一闭回路。,表3-7,20,5,10,4,7,A3,8,2,9,1,A2,10,3,11,3,A1,B4,B3,B2,B1,销地产地,6,3,3,4,3,1,计算最小元素法得到的初始基可行解的检验数,(+1),(-1),(+1),(-1),(+1)3+(-1)3+(+1)2+(-1)1=1,调整后总运费增加：,空格处检验数为1,表3-8,21,5,10,4,7,A3,8,2,9,1,A2,10,3,11,3,A1,B4,B3,B2,B1,销地产地,6

7、,3,3,4,3,1,(+1),(-1),(+1),(-1),7-5+10-3+2-1=10,调整后总运费增加：,空格处检验数为10,(-1),(+1),表3-9,22,检验数表,1,10,12,1,-1,2,因为存在小于零的检验数,所以最小元素法给出的方案不是最优方案.,表3-10,23,2. 位势法,位势：运输问题的对偶变量称为位势。 因为m个供应点n个需求点的运输问题有m+n个约束，因此运输问题就有m+n个位势。,行位势:关于供应点Ai的约束对应的对偶变量，记为 ui, i=1,2,m。 列位势:关于需求点Bj的约束对应的对偶变量，记为vj, j = 1,2,n。,24,定理：运输问题变

8、量xij的检验数,证明：,25,位势法求检验数的步骤:,1.在表中下面和右面增加一行和一列,列中添入ui,行中添入vj ,令u1=0, 按照 , 根据表中已有的数字确定所有的ui及vj ;,2.计算所有空格处的检验数.,26,2,-1,3,0,10,-5,9,检验数表,1,2,1,-1,10,12,24=-10，当前方案 不是最优方案。,最优方案判别准则,表3-12,27,2.3 闭回路调整法改进方案,从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。,表3-13,28,找到最小调整量以后,按

9、照闭回路上的正、负号，分别加上和减去此值，得到新的运输方案。,再用闭回路法或者位势法求检验数，得到下表:,表3-14,29,这时所有的检验数都非负，表中的解就是最优解.,表3-15,30,例 求该运输问题的最优解,31,表上作业法的计算步骤：,32,表上作业法计算中的问题：,（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。 （2）无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。,33, 退化解： 表格中一般要有(m+n-1)个数字格

10、。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。 利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量，选择任意一个最小运量对应的基变量作为换出变量，而经调整后，得到退化解。这时另一个数字格必须填入一个“0”以示它为基变量。,34,12,4,11,4,8,3,10,2,9,5,11,6,(0),(2),(9),(2),(1),(12),8,12,4,2,8,14,如下例中11检验数是 0，经过调整，可得到另一个最优解。,其中绿色是非基变量检验数，红色为分配量。,

11、35,11,4,4,3,1,3,7,7,8,2,10,6,3,4,1,6,0,6,在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34,例：用最小元素法求初始可行解,36,第三节 产销不平衡的运输问题及其求解方法,表上作业法是以产销平衡为前提的：,实际中，往往遇到产销不平衡的运输问题,1.产大于销（供过于求）,2.销大于产（供不应求）,37,产销不平衡运输问题向产销平衡运输问题的转化,产大于销的运输问题：,数学模型,38,设xi n+1 是产地Ai 的储存量，化成标准形,其中,引入虚拟的销地(储存地)（需求量为 ），并令各个产地到虚拟销地的单位运费为0。,39,产小于销的运输

12、问题：,引入一个虚拟的产地（产量等于 ）， 并令该虚拟产地到各销地的单位运费为0。,40,总供应量为19千吨，而总需求量为15千吨,例2： A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分别为7千吨、5千吨和7千吨；四个城市今年的蔬菜需求量分别为2千吨、3千吨、4千吨和6千吨；从每个蔬菜产地平均运输1千吨蔬菜到各个城市的单位费用(万元)见下表，你能否替他们编制一个总运费最省的蔬菜调运方案？,41,0,0,-2,2,0,4,3,0,8,2,5,7,2,3,8,7,最优解中x15=2, x25=2，表示两个产地没有运出去的蔬菜量。,42,假如例2中各产地的蔬菜总产量不是19千吨，而是12千吨，就成了一个供不应求的运输问题。,引入一个虚拟产地,43,例3 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各个化肥厂到各地区单位化肥的运价如下表所示，试决定使总运费最省的化肥调拨方案。,44,这是一个产销不平衡的运输问题，总产量160万吨，四个地区的最低需求量为110万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于总产量。为了求得平衡，在产销平衡表中增加一个假想的