运筹学 第3章运输问题

《运筹学 第3章运输问题》由会员分享，可在线阅读，更多相关《运筹学 第3章运输问题（47页珍藏版）》请在金锄头文库上搜索。

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

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

3、41059 收量（T）3656表3-39思路：为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个 完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1、最小元素法101. 最小元素法314633Z=43+310+31+12+64+35=86该方案总运费：（思想：就近供应）不 能 同 时 划 去 行

4、 和 列保证填 有运量 的格子 为m+n- 1表3-411最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能在其他供销点多花几倍的运费，从而使整个运输费用增加。55552. 沃格尔法沃格尔法考虑到： 一个产地的产品假如不能按照最小 运费就近供应，就考虑次小运费，这就有个差额。 如果差 额不大，当不能按最小单位运价安排运输时造成的运费损 失不大；反之，如果差额很大，不按最小运价组织运输就 会造成很大损失，故应尽量按最小单位运价安排运输。沃 格尔法就是基于这种考虑提出来的。12沃格尔法计算步骤：1) 分别算出各行、各列的最小运费与次小运费的差额。2) 从行、列中选出差额最大者，选择它所在

5、行、列中的最小元素，进行运量调整。3) 对剩余行、列再分别计算各行、列的差额。返回1)、2)。132.伏格尔法 2 5 1 3 011 表3-6 6 2 1 3 012 3 2 1 2 01 3 1 2 76 52 1表3-5Z=8514v1 若有两个以上相同的最大差值，可任取其 一。 v2 剩下一行或者一列有空格，填数字，不能 划掉。 v3 计算行差，列差时，已经划去的列或者行 不再考虑。15销产B1B2B3产量A151 812A224114A33 674销量 91011例 用伏格尔法求初始调运方案16销产B1B2B3产量A1210 12A231114A34 4销量 91011初始调运方案1

6、72.2 最优解的判别判别办法是计算空格(非基变量)的检验数,因为运输问题的目标函数是实现最小化,所以当所有空格处的检验数大于等于零时,为最优解.下面分别介绍两种计算检验数的方法:(1)闭回路法(2)(2) 位势法18 闭回路法闭回路：从空格出发画水平(或垂直)直线，遇到 填有运量的方格（数字格）可转90，然后继续前进 ，直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。销销 产产B1B2B3B4供量A1 5 27 A23 14A3 6 39 销销量 3656表3-7195 10 4 7A38 2 9 1A210 3 11 3A1B4B3B2B1 销地 产地6 334

7、31计算最小元素法得到的初始基可行解的检验数(+1)(-1)(+1)(-1)(+1)3+(-1)3+(+1)2+(-1)1=1调整后总运费增加：空格处 检验数 为1表3-8205 10 4 7A38 2 9 1A210 3 11 3A1B4B3B2B1 销地 产地6 334 31(+1)(-1)(+1)(-1)7-5+10-3+2-1=10调整后总运费增加：空格处 检验数 为10(-1)(+1)表3-921检验数表110121-12因为存在小于零的检验数,所以最小元素法给出的 方案不是最优方案.表3-10222. 位势法位势：运输问题的对偶变量称为位势。因为m个供应点n个需求点的运输问题有m+

8、n个约束 ，因此运输问题就有m+n个位势。 行位势:关于供应点Ai的约束对应的对偶变量，记为 ui, i=1,2,m。列位势:关于需求点Bj的约束对应的对偶变量，记为vj, j = 1,2,n。 23定理：运输问题变量xij的检验数证明：24位势法 求检验数的步骤:1.在表中下面和右面增加一行和一列,列中添入ui, 行中添入vj ,令u1=0, 按照 , 根据表中已有 的数字确定所有的ui及vj ; 2.计算所有空格处的检验数. 252-13010-59检验数表121-1101224=-10，当前方案 不是最优方案。最 优 方 案 判 别 准 则表3-12262.3 闭回路调整法改进方案xpq

9、为换入变量从(p,q)空格开始画闭回路，其它转角点都是 填有运量的方格，并从(p,q)空格开始给闭回路上 的点按+1，-1，+1，-1编号，-1格的最小运量为 调整量。表3-1327找到最小调整量以后,按照闭回路上的正、负 号，分别加上和减去此值，得到新的运输方案。销销 产产B1B2B3B4供量A1 5 27 A23 14 A3 6 39销销量 3656再用闭回路法或者位势法求检验数，得到下 表:表3-1428销销 产产B1B2B3B4供量A102 7 A22 14 A39 129销销量 3656这时所有的检验数都非负，表中的解就是最优解.表3-1529销销 产产B1B2B3B4供量A137

10、6 45 A224 3 22 A34 38 53销销量 3322例 求该运输问题的最优解30v表上作业法的计算步骤：分析实际问题列出产销平 衡表及单位运价表确定初始调运方案（最小 元素法或伏格尔法）求检验数闭回路或位势法所有检验数0找出绝对值最大的负检验数，用闭合 回路调整，得到新的调运方案得到最优方案， 算出总运价31表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负 ，在继续迭代时，取它们中任一变量为换入变量均可使目标函 数值得到改善，但通常取ij0中最小者对应的变量为换入变量 。（2）无穷多最优解产销平衡的运输问题必定存最优解。如果非

11、基变量的ij0， 则该问题有无穷多最优解。32 退化解： 表格中一般要有(m+n-1)个数字格。但有时在分配运量 时则需要同时划去一行和一列，这时需要补一个0，以保证 有(m+n-1)个数字格作为基变量。一般可在划去的行和列的 任意空格处加一个0即可。 利用进基变量的闭回路对解进行调整时，标有负号的 最小运量（超过2个最小值）作为调整量，选择任意一个最 小运量对应的基变量作为换出变量，而经调整后，得到退化 解。这时另一个数字格必须填入一个“0”以示它为基变量。33销地 产地B1B2B3B4产量A116A210A322 销量81412141241148310295116(0)(2)(9)(2)(

12、1)(12)8 812124 42 28 81414如下例中11检验数是 0，经过调整，可得到另一个最优解。 其中绿色是非基变量检验数，红色为分配量。34销地 产地B1B2B3B4产量A17A24A39 销量365620114431377821063 34 41 16 606 6在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34例：用最小元素法求初始可行解35第三节 产销不平衡的运输问题及其求解方法表上作业法是以产销平衡为前提的：实际中，往往遇到产销不平衡的运输问题1.产大于销（供过于求）2.销大于产（供不应求）36产销不平衡运输问题向产销平衡运输问题的转化产大于销的运输问

13、题：数学模型37设xi n+1 是产地Ai 的储存量，化成标准形其中引入虚拟的销地(储存地)（需求量为 ），并令 各个产地到虚拟销地的单位运费为0。38产小于销的运输问题：引入一个虚拟的产地（产量等于 ），并令该虚拟产地到各销地的单位运费为0。39总供应量为19千吨，而总需求量为15千吨例2： A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、 B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分 别为7千吨、5千吨和7千吨；四个城市今年的蔬菜需求量分别 为2千吨、3千吨、4千吨和6千吨；从每个蔬菜产地平均运输1 千吨蔬菜到各个城市的单位费用(万元)见下表，你能否替他 们编制一个总运

14、费最省的蔬菜调运方案？ 单位运费B1B2B3B4供应量A1211347A2103595A378127需求量234640需求地生产产地B1B2B3B4B5供应应量 A12113407A21035905A3781207需求量2346400-220430825723343222387最优解中x15=2, x25=2，表示两个产地没有运出去的蔬菜量 。41假如例2中各产地的蔬菜总产量不是19千吨，而是 12千吨，就成了一个供不应求的运输问题。 单位运费B1B2B3B4供应量A1211343A2103594A378125需求量2346单位运费B1B2B3B4供应量A1211344A2103593A378125A400003需求量2346引入一个虚拟产地42例3 设有三个化肥厂供应四个地区的农用化肥。假定等量的 化肥在这些地区使用效果相同，已知各化肥厂年产量，各地 区年需要量及从各个化肥厂到各地区单位化肥的运价如下表 所示，试决定使总运费最省的化肥调拨方案。需求地区化肥厂IIIIIIIV产量 （万吨）A1613221750B1413191560C192023-50最低需求（ 万吨）3070 010最高需求（ 万吨）507030不限43这是一个产销不平