管理运筹学--运输问题讲解

《管理运筹学--运输问题讲解》由会员分享，可在线阅读，更多相关《管理运筹学--运输问题讲解（119页珍藏版）》请在金锄头文库上搜索。

1、管理运筹学 华国伟 Email:huaguowei 北京交通大学经管学院物流管理系 第三章 运输问题 Transportation Problem 本节内容提要 3.1 运输问题的数学模 3.2 表上作业法 3.1 运输问题的数学模型 A A1 1 A A i i A A mm 产地产地产量产量销地销地 B B1 1 B B j j B Bn n 销量销量 例：某运输问题的资料如下： 单位 销地 运价 产地 产量 291029 13425 84257 销量3846 一、运输问题的数学模型 数学模型的一般形式 已知资料如下： 单 销 产 量 产地 产 量 销 量 运 价 供需平衡 当产销平衡时，

2、其模型如下： Ai的产品全部 供应出去 Bj的需求全 部得到满足 产销平衡的运输问题必定存最优解. 当产大于销时，其模型是： 当产小于销时，其模型是： m n 平衡表、运价表和二为一： 约束条件或解可用产销平衡表表示: uivj无约束 （i=1,2, ,m;j=1,2, ,n) ui vj 设ui,vj为对偶变量，对偶问题模型为 m个 n个 特征： 1、平衡运输问题必有可行解，也 必有最优解； 2、运输问题的基本可行解中应包 括 m+n1 个基变量。 .重复. ，直到找到最优解为止。 步骤： .找出初始基本可行解（初始调运方案，一 般m+n-1个数字格），用西北角法、最小元素法 ； .求出各非

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

4、1、求初始方案： 3.2.1初始基可行解的确定西北角法 西北角发也就是从运价表的西北角位置 开始,依次安排m个产地和n个销地之间的 运输业务,从而得到一个初始调运方案的 方法. 西北角法应遵循“优先安排运价表上编号 最小的产地和销地之间(即运价表的西北 角位置)的运输业务”的规则. .西北角法(或左上角法): 此法是纯粹的人为的规定,没有理论依据和实际背 景,但它易操作,特别适合在计算机上编程计算,因而受 欢迎.方法如下： 总的运费(33)(411)(29) (22)(310)(65)135元 B1B2B3B4产量 A17 A2 4 A39 销量3656 311310 192 74105 8

5、3 4 1 63 3 .初始基可行解的确定-最小元素法： 基本思想是就近供应，即从运价最小的地方开始供 应（调运），然后次小，直到最后供完为止。 总的运输费用（31）（64） （43）（12）（310）（35）86元 分别计算各行、各列次小、最小运价的差值,优先在 最大差值处进行供需搭配. 差值=次小-最小 步骤： 10 计算未划去行、列的差额; 20 找出最大差额对应的最小元素cij进行供需分配; 30 在未被划去的行、列重新计算差额. (3)初始基可行解的确定 -最大差值法(伏格尔法) Vogel 6 销销 产产 B1B2B3B4供量 A17 A24 A39 销销量 3656 B1B2B3

6、B4供量 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 行差值值 A13113100 A219281 A374105 列差值值 212 5 1 2 6 3 B1B2B3B4 差值值 A13113107 A219286 A374105 差值值

7、12 销销 产产 B1B2B3B4供量 A17 A24 A3 39 销销量 3656 以上方法得到的初始解为基可行解 每次行(需求)或列(供应)达到饱和 每次必划掉一行或一列 得到的元素个数必为m+n-1个 西北角法 最小元素法 最大差值法 练习 P97 3.1 3.2 ij0 （因为目标函数要求最小化） 表格中有调运量的地方为基变量,空格处为非基变 量.基变量的检验数ij0,非基变量的检验数 ij0. ij 0 表示运费增加. 2、最优解的判别（检验数的求法）： 检验数 非基变量增加一个 单位目标值的变化 （1）闭回路法 闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直 线,遇到填有运

8、量的方格可转90,然后继续前进,直到到达出发 的空格所形成的闭合回路. 调运方案的任意空格存在唯一闭回路. 销销 产产 B1B2B3B4供量 A1 5 27 A23 14 A3 6 39 销销量 3656 差值法方案 一、最优调运方案的判定 3 1 4 6 3 3 最小元素法方案 + - + - x11为换入变量，x11：01，运费的变化为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产

9、量 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 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

10、)-(14)-(24) (31)-(34)-(14)-(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1 10 12 检验数还存在负数, 原方案不是最优方案. 用闭回路求解检验数时,需要给每一个空格 找一条闭回路.当产销点较多时,该方法较麻 烦. ui,vj自由变量 （2） 位势法 标准型运输问题的对偶问题是： XBXNXS 0CN-CBB-1N-CBB-1 -YS1-YS2-Y 检验数 对偶变量值等于 原问题的检验数 松弛变量 基变量的检验数为零(基变量xij)， 得m+n-1个方程,含m+n个未知数, 令某个ui ( 或 vj)=0,

11、可解出m+n个ui 和vj;由此得非基变量的检验数 . 1.由基变量的检验数为0, ij=cij-(ui+vj)=0, u1=0 (v1=0),得ui, vj 2. 利用ij=cij-(ui+vj),求非基变量的检验 数 可令任意的行或列的位势为0 (任意值均 可,为0出于计算简单考虑) 3 1 4 6 3 3 位势法 令v1=0, 由c21=1= u2 +v1，得 u2=1 0 1 1 2 0 1 1 2 8 -3 7 位势表 29 8 9 -3-2 检验数 0 1 1 2 8 -3 7 检验数表 1 2 1 -1 1012 24=-10，当前方案 不是最优方案。 1. 以最小负检验数为出发

12、点寻找一条闭回 路. 2. 确定调整量,调出格中最小的运量. 2.3 改进的方法闭回路调整法 二、 调运方案的调整 pqij j , i )(min = bj 产小于销：ai 产量 二、转运问题 出现下列问题： 1. 产地与销地之间没有直达路线，货物由产地到销 地必须通过中转站转运； 2. 某些产地可以输入货物，销地也可以输出货物， 3. 产地与销地之间虽然有直达运输线，但直达运输 的费用（距离）比经过某些中转站的还要高。 解法：无转运问题。 1. 根据问题求出最大可能周转量Q； 2. 纯转运点 产地：输出量Q； 销地：输入量Q；输入=输出 3. 兼中转站的产地Ai= 销地：输入量Q； 产地：

13、输出量Q+ai； 4. 兼中转站的销地Bj= 销地：输入量bj+Q； 产地：输出量Q； 列出各产地的输出量和各销地的输入量及各产 销地之间的运价表, 用表上作业法求解. 输出：产地；中转站(纯/兼) 输入：销地；中转站(纯/兼) 例 某货物, 其产地A1的产量为10单位,A2的产量为2单 位, 销地A3、A4、A5的销量分别为3单位、1单位和8 单位, 其中产地A2、销A4又可作为中转站. 同时, 货物 可通过纯中转站A6进行运输. 各产地、销地及中转站 之间的单位物资运价如表所示, 试求一个使总运费最 省的调运方案. 销销地 产产地 A2A3A4A5A6 A126312 A2 03M24 A

14、4M2031 A613270 最大可能周转量 Q=a1+a2=10+2=12 A1 纯产地, 输出量10; A2产地兼中转站,输出量2+12=14,输入量12; A3 纯销地, 输入量3; A4销地兼中转站,输出量12,输入量1+12=13; A5纯销地,输入量8; A6纯中转站,输出量、输入量均为12. 根据以上情况列产销平衡表. 销地 产地 A2A3A4A5A6输出量 A12631210 A203M2414 A4M203112 A61327012 输入量1231381248 销地 产地 A2A3A4A5A6输出量 A118110 A212214 A41212 A611112 输入量1231

15、381248 不参加实际调运 3.4 应用举例 搞清“产地、销地”、“运价”, “产量、需求”, 写出产销平衡表 运输问题的要素: 未知数 如何设 虚设产地与销地 ; 拆分产地与销地 例 3. 某厂按合同规定须于每个季度末分别提供 10,15,25,20台同一规格的柴油机.已知该厂各季度 的生产能力及生产每台柴油机的成本如下表.如果 生产出来的柴油机当季不交货,每台积压一个季度 需储存、维护费用0.15万元.要求在完成合同的情 况下,做出该厂全年费用最小的决策. 季度生产产能力单单位成本 I II III IV 25 35 30 10 10.8 11.1 11.0 11.3 搞清“产地、销地”

16、、“运价”, “产量、需求”, 写出产销平衡表 未知数 如何设 设xij为第i季度生产的用于第j季度交货的柴油机数. 合同要求：产量约束： 第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 目标函数：目标函数： 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 IIII