管理运筹学--运输问题

1、管理运筹学管理运筹学 华国伟华国伟 Email: 北京交通大学经管学院物流管理系北京交通大学经管学院物流管理系 第三章第三章 运输问题运输问题 Transportation Problem 本节内容提要本节内容提要 3.1 运输问题的数学模运输问题的数学模 3.2 表上作业法表上作业法 3.1 运输问题的数学模型运输问题的数学模型 1 a i a m a 1 b j b n b 11 c 1j c 1 i c ij c in c mn c mj c 1m c 1n c 例：某运输问题的资料如下：例：某运输问题的资料如下： 单位 销地 运价 产地 产量 291029 13425 84257 销量

2、3846 4321 BBBB 3 2 1 A A A 一、运输问题的数学模型一、运输问题的数学模型 )4 . 3 . 2 . 1, 3 . 2 . 1(0 6 4 8 3 7 5 9 524824 371092min 342414 332313 322212 312111 34333231 24232221 14131211 343332312423 222114131211 jix xxx xxx xxx xxx xxxx xxxx xxxx xxxxxx xxxxxxZ x ij ij 约约束束条条件件： 目目标标函函数数： 为为运运量量设设 数学模型的一般形式数学模型的一般形式 已知资料

3、如下：已知资料如下： 单 销 产 量 产地 产 量 销 量 n BB 1 1 m A A m a a 1 n bb 1 mnm n cc cc 1 111 运运 价价 n ij j m 1i i ba 供需平衡供需平衡 ) ( 0 min 11 ij jijij iij m i n j ijij x babx ax xcZ 当产销平衡时，其模型如下：当产销平衡时，其模型如下： Ai的产品全部的产品全部 供应出去供应出去 Bj的需求全的需求全 部得到满足部得到满足 产销平衡的运输问题必定存最优解产销平衡的运输问题必定存最优解. 当产大于销时，其模型是：当产大于销时，其模型是： ) ( 0 min

4、 11 ij jijij iij m i n j ijij x babx ax xcZ 当产小于销时，其模型是：当产小于销时，其模型是： 0, 0, 0 )( 0 min ijjij ji ij jij iij ijij cba ba x bx ax xcZ 并假设：并假设： 1112121222nm1m2mn 1 1 1 1 1 1 n x xx xxxxxx 1 1 1 1 1 1 1 1 1 1 1 1 m n ijimj Pee 1mn 个基变量 平衡表、运价表和二为一：平衡表、运价表和二为一： 销 产 B1B2Bn产量 A1x11x12x1na1 A2x21x22x2na2 Amxm

5、1xm2xmnam 销量b1b1bn 约束条件或解可用产销平衡表表示约束条件或解可用产销平衡表表示: m i n j ijijx czmin 11 )n,j(bx )m,i (ax m i jij n j iij 1 1 1 1 )n,j;m,i (xij11 0 uivj无约束无约束 （i=1,2, ,m;j=1,2, ,n) ui vj 设设u ui,v,vj为对偶变量，对偶问题模型为为对偶变量，对偶问题模型为 n ij jj m i ii vbuaw 1 max ijji cvu m个个 n个个 特征：特征： 1 1、平衡运输问题必有可行解，也、平衡运输问题必有可行解，也 必有最优解；必

6、有最优解； 2 2、运输问题的基本可行解中应包、运输问题的基本可行解中应包 括括 m+n1 个基变量。个基变量。 . .重复重复. . ，直到找到最优解为止。，直到找到最优解为止。 步骤：步骤： . .找出找出初始基本可行解初始基本可行解（初始调运方案，一（初始调运方案，一 般般m+n-1m+n-1个数字格），用西北角法、最小元素法；个数字格），用西北角法、最小元素法； . .求出各非基变量的检验数，判别是否达到求出各非基变量的检验数，判别是否达到 最优解。如果是停止计算，否则转入下一步，用最优解。如果是停止计算，否则转入下一步，用 位势法计算；位势法计算； . .改进当前的基本可行解（确定换

7、入、换改进当前的基本可行解（确定换入、换 出变量），用闭合回路法调整；出变量），用闭合回路法调整； 二、表上作业法二、表上作业法 确定确定m+n-1个基变量个基变量 空格空格 3.2 求解运输问题的算法求解运输问题的算法:表上作业法表上作业法 开开 始始 求各非基变求各非基变 量的检验数量的检验数 是否达到最优解是否达到最优解 结束结束 确定换入变量确定换入变量 与换出变量与换出变量 新的基可行解新的基可行解 求初始基可行解求初始基可行解 例一、某运输资料如下表所示：例一、某运输资料如下表所示： 单位单位 销地销地 运价运价 产地产地 产量产量 3113107 19284 741059 销量销

8、量3656 4321 BBBB 3 2 1 A A A 1 1、求初始方案：、求初始方案： 3.2.1初始基可行解的确定初始基可行解的确定西北角法 西北角发也就是从运价表的西北角位置开 始,依次安排m个产地和n个销地之间的运输 业务,从而得到一个初始调运方案的方法. 西北角法应遵循“优先安排运价表上编号 最小的产地和销地之间(即运价表的西北角 位置)的运输业务”的规则. . .西北角法西北角法( (或左上角法或左上角法):): 此法是纯粹的人为的规定此法是纯粹的人为的规定, ,没有理论依据和实际背没有理论依据和实际背 景景, ,但它易操作但它易操作, ,特别适合在计算机上编程计算特别适合在计算

9、机上编程计算, ,因而受因而受 欢迎欢迎. .方法如下：方法如下： 总的运费总的运费(3(33)3)(4(411)11)(2(29)9) (2(22)2)(3(310)10)(6(65)5)135135元元 B1B2B3B4产量产量 A17 A2 4 A39 销量销量3656 311310 192 74105 8 3 4 1 63 3 . .初始基可行解的确定初始基可行解的确定-最小元素法：最小元素法： 基本思想是就近供应，即从运价最小的地方开始供基本思想是就近供应，即从运价最小的地方开始供 应（调运），然后次小，直到最后供完为止。应（调运），然后次小，直到最后供完为止。 总的运输费用（总的运

10、输费用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元 分别计算各行、各列次小、最小运价的差值分别计算各行、各列次小、最小运价的差值, ,优先优先 在最大差值处进行供需搭配在最大差值处进行供需搭配. . 差值差值=次小次小-最小最小 步骤：步骤： 10 计算未划去行、列的差额计算未划去行、列的差额; 20 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配进行供需分配; 30 在未被划去的行、列重新计算差额在未被划去的行、列重新计算差额. (3)初始基可行解的确定初始基可行解的确定 -最大差值法

11、最大差值法(伏格尔法伏格尔法) Vogel 6 销销 产产 B1B2B3B4供量供量 A17 A24 A39 销量销量 3656 B1B2B3B4供量供量 A13113107 A219284 A3741059 销量销量3656 列差值列差值 2513 行差值行差值 0 1 1 6 3 销销 产产 B1B2B3B4供量供量 A17 A24 A3 9 销量销量 3656 B1B2B3B4 行差值行差值 A13113100 A219281 A3741052 列差值列差值 213 3 6 3 销销 产产 B1B2B3B4供量供量 A17 A24 A3 9 销量销量 3656 B1B2B3B4 行差值行

12、差值 A13113100 A219281 A374105 列差值列差值 212 5 1 2 6 3 B1B2B3B4 差值差值 A13113107 A219286 A374105 差值差值 12 销销 产产 B1B2B3B4供量供量 A17 A24 A3 39 销量销量 3656 以上方法得到的初始解为基可行解 每次行(需求)或列(供应)达到饱和 每次必划掉一行或一列 得到的元素个数必为m+n-1个 西北角法 最小元素法 最大差值法 练习 P97 3.1 3.2 ij ij0 0 （因为目标函数要求最小化）因为目标函数要求最小化） 表格中有调运量的地方为基变量表格中有调运量的地方为基变量, ,

13、空格处为非基变空格处为非基变 量量. .基变量的检验数基变量的检验数ij ij 0,非基变量的检验数非基变量的检验数 ij ij0. 0. ij 0 表示运费增加表示运费增加. 2 2、最优解的判别（检验数的求法）：、最优解的判别（检验数的求法）： 1 jijBij cC B P 0 1 n jj j m ZZx 检验数检验数 非基变量增加一个非基变量增加一个 单位目标值的变化单位目标值的变化 （1）闭回路法）闭回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水平画水平(或垂直或垂直)直直 线线,遇到填有运量的方格遇到填有运量的方格可转可转90,然后继续前进然后继

14、续前进,直到到达出发直到到达出发 的空格所形成的闭合回路的空格所形成的闭合回路. 调运方案的任意空格存在唯一闭回路调运方案的任意空格存在唯一闭回路. 销销 产产 B1B2B3B4供量供量 A1 5 27 A23 14 A3 6 39 销量销量 3656 差值法方案差值法方案 一、最优调运方案的判定一、最优调运方案的判定 销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 3 1 4 6 3 3 最小元素法方案最小元素法方案 + - + - x11为换入变量，为换入变量，x11：01，运费的变

15、化为，运费的变化为 3- -1+2- -3=1。这个变化就是。这个变化就是x11的检验数，故的检验数，故 11=1 B1B2B3B4产量产量 A17 A24 A39 销量销量3656 3 13 6 3124 B1B2B3B4产量产量 A17 A24 A39 销量销量3656 3 13 6 312 -1 4 B1B2B3B4产量产量 A17 A24 A39 销量销量3656 3 13 6 312 1 -1 4 B1B2B3B4产量产量 A17 A24 A39 销量销量3656 3 13 6 312 1 -1 12 4 B1B2B3B4产量产量 A17 A24 A39 销量销量3656 3 13

16、6 312 1 -1 1210 4 检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。 空格闭回路检验数 (11) (12) (22) (24) (31) (33) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(22) (22)-(23)-(13)-(14)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24) (31)-(34)-(14)-(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1 10 12 检验数还存在检验数还存在负数负数, 原

17、方案不是最优方案原方案不是最优方案. 用闭回路求解检验数时,需要给每一个空格找 一条闭回路.当产销点较多时,该方法较麻烦. ui,vj自由变量自由变量 （2） 位势法位势法 标准型运输问题的对偶问题是：标准型运输问题的对偶问题是： n j jj m i ii vbuamax 11 )n,j;m,i (cvu ijji 11 XBXNXS 0CN-CBB-1N-CBB-1 -YS1-YS2-Y 检验数检验数 对偶变量值等于对偶变量值等于 原问题的检验数原问题的检验数 松弛变量松弛变量 1 1212 ( ,.,. ) () ijijBijijij ijmnij ijij cC B PcYP cu

18、uuv vv P cuv ij () ijijij cuv 基变量的检验数为零基变量的检验数为零( 基变量基变量xij)， ()0 ijijij cuv 得得m+n- -1个方程个方程,含含m+n个未知数个未知数, 令某个令某个ui ( 或或 vj)=0,可解出可解出m+n个个ui 和和vj;由此得非基变量的检验由此得非基变量的检验 数数. () ijijij cuv 1.由基变量的检验数为0, ij=cij-(ui+vj)=0, u1=0 (v1=0),得ui, vj 2. 利用 ij=cij-(ui+vj),求非基变量的检验数 可令任意的行或列的位势为可令任意的行或列的位势为0 (任意值均

19、任意值均 可可,为为0出于计算简单考虑出于计算简单考虑) 销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 3 1 4 6 3 3 位势法位势法 令令v1=0, 由由c21=1= u2 +v1，得得 u2=1 B 1 B 2 B 3 B 4 u i 311310 A 1 1928 A 2 74105 A 3 vj 0 1 1 2 0 1 1 2 8 -3 7 位势表位势表 29 8 9 -3-2 )( jiijij vuc检验数检验数 B 1 B 2 B 3 B 4 u i 311310

20、A 1 1928 A 2 74105 A 3 vj 0 1 1 2 8 -3 7 检验数表检验数表 1 2 1 -1 1012 24=-10，当前方案，当前方案 不是最优方案。不是最优方案。 1. 以以最小负检验数最小负检验数为出发点寻找一条闭回路为出发点寻找一条闭回路 . 2. 确定调整量确定调整量,调出格中调出格中最小最小的运量的运量. 2.3 改进的方法改进的方法闭回路调整法闭回路调整法 二、二、 调运方案的调整调运方案的调整 pqij j , i )(min 0 xpq为换入变量为换入变量 从从( (p,q) )空格开始画闭回路空格开始画闭回路, ,其它转角点都是填有运其它转角点都是填

21、有运 量的方格量的方格, ,并从并从( (p,q) )空格开始给闭回路上的点按空格开始给闭回路上的点按 +1+1,-1,+1,-1,-1,+1,-1编号，编号，-1-1格的最小运量格的最小运量为调整量为调整量. . 换出换出变量变量 销销地地 产产地地 B1 B2 B3 B4 产产量量 A1 A2 A3 3 6 4(+1) 1(- -1) 3(- -1) (+1) 3 7 4 9 销销量量 3 6 5 6 运价运价 B1B2B3B4产量 A1527 A2314 A3639 销量3656 新的调运方案为：新的调运方案为： 851186zz 2401 或者直接算或者直接算 需 供 B1B2B3B4

22、ui A10210 A2218 A39125 Vj -7-1-70 7 1 3 4 9 11 10 2 310 8 5 运输问题的求解表上作业法步骤小结运输问题的求解表上作业法步骤小结 第一步第一步: :确定初始基可行解（可行调运方案）确定初始基可行解（可行调运方案） 方法：最小元素法与伏格尔法方法：最小元素法与伏格尔法 第二步第二步: :判别当前可行方案是否最优判别当前可行方案是否最优 方法：闭回路法与位势法方法：闭回路法与位势法 第三步第三步: :对现有方案进行调整对现有方案进行调整 方法：闭回路法方法：闭回路法 3.2.4 表表上上作业法计算中的问题作业法计算中的问题 无穷多最优解无穷多

23、最优解 某非基变量某非基变量(空格空格)的检验数为的检验数为0. 退化退化 方案点数方案点数=产地数产地数+销地数销地数1; 同时去掉一行和一列时应添加同时去掉一行和一列时应添加0方案方案; 调整时出现两个或两个以上的最小值调整时出现两个或两个以上的最小值, 新方案中也要添加新方案中也要添加0方案方案. . .无穷多最优解：无穷多最优解：产销平衡的运输问题必定存最产销平衡的运输问题必定存最 优解优解. .如果非基变量的如果非基变量的ij0, 则该问题有无穷多最优则该问题有无穷多最优 解解. 如上例如上例: (1.1) 中的检验数是中的检验数是 0, 经过调整经过调整, 可得到另可得到另 一个最

24、优解一个最优解. 4、表上作业法计算中的问题、表上作业法计算中的问题 .退化退化: 表格中一般要有表格中一般要有(m+n-1)个数字格个数字格. 但有时但有时, 在分配运量时则需要同时划去一在分配运量时则需要同时划去一 行和一列行和一列, 这时需要补一个这时需要补一个0, 以保证有以保证有 (m+n-1)个数字格个数字格. 一般可在划去的行和列一般可在划去的行和列 的任意空格处加一个的任意空格处加一个 0 即可即可. 正常时一次只划掉同时划掉了一行和一列 此时同时划掉一行和一列, 不要补零 例例1： B1B2B3B4 A178143 A226355 A314278 2176 2 1 3 5 5

25、 2 6 8 2 1 7 6 例例2： B1B2B3 A11221 A23132 A32314 124 B1B2B3 A111 A222 A344 124 00 0 4 运输问题的扩展运输问题的扩展 本本 节节 重重 点点 供需不平衡的运输问题供需不平衡的运输问题 供不应求供不应求 供过于求供过于求 转运问题转运问题 运输问题的分类运输问题的分类 产销产销平衡平衡问题：问题：ai=bj 产销产销不平衡不平衡问题：问题： 产大于销：产大于销：ai bj 产小于销：产小于销：ai 产量产量 二、转运问题二、转运问题 出现下列问题：出现下列问题： 1. 产地与销地之间没有直达路线，货物由产地到销产地

26、与销地之间没有直达路线，货物由产地到销 地必须通过中转站转运；地必须通过中转站转运； 2. 某些产地可以输入货物，销地也可以输出货物，某些产地可以输入货物，销地也可以输出货物， 3. 产地与销地之间虽然有直达运输线，但直达运输产地与销地之间虽然有直达运输线，但直达运输 的费用（距离）比经过某些中转站的还要高。的费用（距离）比经过某些中转站的还要高。 解法：解法：无转运问题。无转运问题。 1. 根据问题求出最大可能周转量根据问题求出最大可能周转量Q； 2. 纯转运点纯转运点 产地：输出量产地：输出量Q； 销地：输入量销地：输入量Q；输入输入=输出输出 3. 兼中转站的产地兼中转站的产地Ai= 销

27、销地：输入量地：输入量Q； 产地：输出量产地：输出量Q+ai； 4. 兼中转站的销地兼中转站的销地Bj= 销销地：输入量地：输入量bj+Q； 产地：输出量产地：输出量Q； 列出各产地的输出量和各销地的输入量及各产列出各产地的输出量和各销地的输入量及各产 销地之间的运价表销地之间的运价表, 用表上作业法求解用表上作业法求解. 输出：产地；中转站输出：产地；中转站(纯纯/兼兼) 输入：销地；中转站输入：销地；中转站(纯纯/兼兼) 例例 某货物某货物, 其产地其产地A1的产量为的产量为10单位单位,A2的产量为的产量为2 单位单位, 销地销地A3、A4、A5的销量分别为的销量分别为3单位、单位、1单

28、位和单位和 8单位单位, 其中产地其中产地A2、销、销A4又可作为中转站又可作为中转站. 同时同时, 货货 物可通过纯中转站物可通过纯中转站A6进行运输进行运输. 各产地、销地及中转各产地、销地及中转 站之间的单位物资运价如表所示站之间的单位物资运价如表所示, 试求一个使总运费试求一个使总运费 最省的调运方案最省的调运方案. 销地销地 产地产地 A2A3A4A5A6 A126312 A2 03M24 A4M2031 A613270 最大可能周转量最大可能周转量 Q=a1+a2=10+2=12 A1 纯产地纯产地, 输出量输出量10; A2产地兼中转站产地兼中转站,输出量输出量2+12=14,输

29、入量输入量12; A3 纯销地纯销地, 输入量输入量3; A4销地兼中转站销地兼中转站,输出量输出量12,输入量输入量1+12=13; A5纯销地纯销地,输入量输入量8; A6纯中转站纯中转站,输出量、输入量均为输出量、输入量均为12. 根据以上情况列产销平衡表根据以上情况列产销平衡表. 销地 产地 A2A3A4A5A6输出量 A12631210 A203M2414 A4M203112 A61327012 输入量1231381248 销地 产地 A2A3A4A5A6输出量 A118110 A212214 A41212 A611112 输入量1231381248 不参加实际调运不参加实际调运 3

30、.4 应用举例应用举例 搞清搞清“产地、销地产地、销地”、“运价运价”, “产量、需求产量、需求”, 写出写出产销平衡产销平衡 表表 运输问题的要素运输问题的要素: 未知数未知数 如何设如何设 虚设虚设产地与销地产地与销地; 拆分拆分产地与销地产地与销地 例例 3. 某厂按合同规定须于每个季度末分别提供某厂按合同规定须于每个季度末分别提供 10,15,25,20台同一规格的柴油机台同一规格的柴油机.已知该厂各季度已知该厂各季度 的生产能力及生产每台柴油机的成本如下表的生产能力及生产每台柴油机的成本如下表.如果如果 生产出来的柴油机当季不交货生产出来的柴油机当季不交货,每台积压一个季度每台积压一

31、个季度 需储存、维护费用需储存、维护费用0.15万元万元.要求在完成合同的情要求在完成合同的情 况下况下,做出该厂全年费用最小的决策做出该厂全年费用最小的决策. 季度季度生产能力生产能力单位成本单位成本 I II III IV 25 35 30 10 10.8 11.1 11.0 11.3 搞清搞清“产地、销地产地、销地”、“运价运价”, “产量、需求产量、需求”, 写出写出产销平衡产销平衡 表表 未知数未知数 如何设如何设 设设xij为第为第i季度生产的用于第季度生产的用于第j季度交货的柴油机数季度交货的柴油机数. 合同要求：合同要求： 11 1222 132333 14243444 10

32、15 25 20 x xx xxx xxxx 产量约束：产量约束： 11121314 222324 3334 44 25 35 30 10 xxxx xxx xx x 第第i季度生产的用于第季度生产的用于第j季度交货的柴油机的实际成本季度交货的柴油机的实际成本 cij=生产成本生产成本+储存维护费用储存维护费用 i j IIIIIIIV I II III IV 10.810.95 11.10 11.10 11.25 11.00 11.25 11.40 11.15 11.30 44 11 4 1 4 1 m in . . 0 ijij ij iji j ijj i ij zc x xa s tx

33、b x i j IIIIIIIV产量产量 I II III IV 10.8 M M M 10.95 11.10 M M 11.10 11.25 11.00 M 11.25 11.40 11.15 11.30 25 35 30 10 销量销量10152520 i j IIIIIIIVD产量产量 I II III IV 10.8 M M M 10.95 11.10 M M 11.10 11.25 11.00 M 11.25 11.40 11.15 11.30 0 0 0 0 25 35 30 10 销量销量1015252030 例: 某玩具公司分别生产三种新型的玩具, 每月可供应 量分别为1000

34、件, 2000件,2000件，他们分别被送到甲 乙丙三个百货商店销售, 已知每月百货商店各类玩具 预期销售量为1500件, 由于经营原因, 各百货商店销售 不同玩具的盈利额不同, 又知丙百货商店要求至少供 应C玩具1000件, 而拒绝进入A种玩具, 求满足上述条 件下使总盈利额为最大的供销分配方案. 甲乙丙可供量 A B C 5 16 12 4 8 10 - 9 11 1000 2000 2000 C先满足丙1000件 甲乙丙丁可供量 A B C 5 16 12 4 8 10 - 9 11 0 0 0 1000 2000 1000 15001500500500 甲乙丙丁可供量 A B C 11

35、 0 4 12 8 6 M 7 5 0 0 0 1000 2000 1000 15001500500500 已知某运输问题的产销平衡表, 最优调运方案及单位运价 表分别如表所示, 由于从产地2至销地B的道路因故暂时封 闭, 故需对调运方案进行修正,试用尽可能简单的方法重新 找出最优调运方案. ABCDE产量 1 2 33 4 1 45 13 9 4 8 销量35463 ABCDE 1 2 3 10 2 1 20 10 20 5 10 7 9 30 10 10 6 4 10变为变为M, 计算检验数进行调整计算检验数进行调整 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示 B1B2B

36、3B4发量发量 A1 265315 A2 132112 A3 327413 收量收量 1013125 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/ /吨吨 试求出最优运输方案试求出最优运输方案. . 练习：练习： 2、如将、如将A2的发量改为的发量改为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。 13A3 12A2 510A1 B4B3B2B1 最终的运送方案最终的运送方案 总的运费总的运费 85元元/吨吨 已知资料如下表所示，问如何供电能使总的输电费已知资料如下表所示，问如何供电能使总的输电费 用为最小？用为最小？ 发电厂 发电量 A1700 A2200 A3100 城市需电量 B1500 B2250 B3100 B4150 电力供需表电力供需表 B1B2B3B4 A110523 A24312 A35634 单位输电费用单位输电费用 作业：作业： B1B2B3B4ui A1105230 A24-1-4-3-6 A350-3-2-5 vj 10523 (ui+vj) B1B2B3B4u