《物流运筹学方法教学课件PPT运输规划》由会员分享，可在线阅读，更多相关《物流运筹学方法教学课件PPT运输规划（130页珍藏版）》请在金锄头文库上搜索。
1、物流运筹学方法缪兴锋 教授/高级工程师 联系方法：13802924378 E-mail: wuliuxitong 广东轻工职业技术学院 2013第三章 运输规划及其应用 人们在从事生产活动中，不可避免地要进行物资调 运工作，如某时期内将生产基地的煤、钢铁、粮食等各 类物资，分别运到需要这些物资的地区。 根据各地的生产量和需求量及各地之间的运输费用 ，如何制定一个运输方案，使总的运输费用最小，这样 的问题称为运输问题。【学习目标】 知识目标 1.掌握运输问题的基本形式（数学模型）； 2.掌握运输车辆调度的方法； 3.掌握运输路线优化的图上作业法； 4.掌握制定运输方案的表上作业法。 能力目标 1
2、.能够结合实际情况建立运输问题的模型 ，并求解； 2.能够利用所学方法指导制定运输最优调 运方案，解决实际问题。任务一：运输问题的数学模型 一、运输问题数学模型 运输问题是线型规划问题的特例，它主要解决各流 向上的数量分配问题。 产地产地：货物发出的地点。 销地销地：货物接收的地点。 产量产量：各产地的可供货量。 销量销量：各销地的需求数量。 运输问题就是研究如何组织调运，既满足各销地的需 求，又使总运费最小。二、运输问题的三种类型（一）产销平衡如果v即总供应量等于 总需求量，则称为 平衡运输问题，否 则称为不平衡运输 问题。 v对于不平衡运输 问题，可通过一定 处理后，使之变为 平衡运输问题
3、。（二）产大于销v 即总供应量大于总需求 量，v 则可另外增加一个“虚构 目的地”，v 令其需求量bn+1=ai bj，并令各起运站到虚构 目的地的运费为零。v 解出后，在最优解中， 各站的供应量减去运往虚 构目的地的数值。如果（三）产小于销v 即总供应量小于总需 求量， v 则可另外增加一个“虚 构起运站”， v 令其供应量am+1=bj ai，并令其运至各目的 地的运费为零。 v 解出后，在最优解中 ，各目的地的数量应减 去虚构起运站运达的数 值。如果三、求解方法 对于运输问题，一般采用单纯形法求解，具体方 法和步骤已在前面介绍过 。 经验表明，当起运站和目的地都多于5个时，用 其他方法求
4、解比较困难或繁琐，最好用单纯形法求 解。例如: 有3个起运站，4个目的地， 供应量为 50，50，75， 需求量为 40，55，60，20， 各起运站到目的地的单位运费分别为：C11=3， C12=1， C13=4，C14=5，C21=7， C22=3， C23=8，C24=6，C31=2， C 32=3， C33=9， C34=2.运输问题可表述为： Min f(x) = 3X11+X12+4X13+5X14+7X21+3X22+ 8X23+ 6X24+2X31+3X32+9X33+2X34X11+X12+X13+X14 = 50 X21+X22+X23+X24 = 50 X31+X32+X
5、33+X34 = 75 X11+X21+X31 = 40 X12+X22+X32 = 55 X13+X23+X33 = 60 X14+X24+X34 = 20所有 Xij 0S.t. 用单纯形法解得：X13=50， X22=40， X23=10，X31=50， X32=15， X34=20，总运费为：f(x) = 504+403+108+402+153+202 = 565四、运输表与运输模式v 运输问题的线性规划表达形式是比较复杂的， v 例如10个起点站和10个终点站的运输问题至少涉及1010 100个变量， v 把运输问题表示成线性规划模型，就非常复杂，写成矩阵 形式，就是庞大的矩阵。 v
6、 使用计算机计算，也要输入数百个数据，操作非常繁杂和 困难。 v 而且我们发现，在这些矩阵元素中，大部分为0或1，这些 矩阵元素完全可以由计算程序来完成。 v 因此，提出一种运输问题应用模式，即运输表， v 凡是能表达成运输表的问题，都可以用运输模式来解决。例如上面例题可以用表格形式来表示， 如表4-1 所示：表4-1 运输表格式终点 起点1 23 4供应量1 3 1 4 5502 7 3 8 6503 2 3 9 275需求量40556020175五、 运输表作业法 简介 q计算步骤： v （一）给出初始方案 v （二）检验是否最优v （三）调整调运方案 （一）初始方案的确定 确定初始方案的
7、方法较多，有 q 1.最小元素法； q 2.左上角法（又称西北角法、或阶剃法）； q 3. 最大差额法（又称Vogel概算法）； q 4. Russell概算法等。1. 最小元素法；v 所谓“最小元素”，是指作业表中最小运价Cij. v 该法的基本思想是：“就近运给”，即先给 作业表中最 小运价那格安排运量，然后划去该运价所在行或列； v 接下去继续这样做，每次总在表中剩余运价的最小元 素那格确定运量，直至求出初始方案为止。例1： 有A1，A2，A3三座铁矿，每天要把生产的铁矿石运往B1， B2，B3，B4，四个炼铁厂。各矿的发矿量、各厂的收矿量 （百吨/天）以及各厂矿间的运价（百元/百吨）如
8、下表。 问应如何组织调运才能使总运费最少？1. 1. 用最小元素法求解用最小元素法求解 （1 1）从最小元素开始（）从最小元素开始（3 3）即）即A A1 1优先满足优先满足B B3 3 3 3个单位，个单位， B B3 3 已经满足，划去已经满足，划去B B3 3列列，（2 2）再从最小元素开始（）再从最小元素开始（4 4）即）即A A1 1优先满足优先满足B B4 4 1 1个单位个单位， A A1 1 已经满足，划已经满足，划 去去A A1 1行行，（3 3）再从最小元素开始（）再从最小元素开始（4 4）即）即A A2 2优先满足优先满足B B1 1 2 2个单位，个单位， B B1 1
9、 已经满足，已经满足，划去划去B B1 1列列，收点 发点B1B2B3B4发量A1653 34 14A24 24756A37658 3收量243413（4 4）再从最小元素开始（）再从最小元素开始（4 4）即）即A A2 2优先满足优先满足B B2 2 4 4个单位个单位， B B2 2 A A2 2已经满足，划已经满足，划 去去B B2 2列列A A2 2行行。（5 5）最后把）最后把A A3 3满足满足B B4 4 3 3个单位，个单位， 得到初始方案得到初始方案。（6 6）得到初始方案）得到初始方案：X X1313=3=3，X X1414=1=1，X X2121=2=2，X X2222=
10、4=4，X X3434=3=3总运费总运费= 3*3+4*1+4*2+4*4+8*3=61= 3*3+4*1+4*2+4*4+8*3=61（元）（元）2. 用左上角法（又称西北角法、或阶剃法） （1 1）从图的西北角开始，填入）从图的西北角开始，填入a a1 1与与b b1 1较小的值，较小的值， b b1 1=2 =2，即从即从A A1 1运给运给B B1 1（2 2吨）吨）B B1 1已经满足，划去已经满足，划去b b1 1列，并将列，并将a a1 1=4-2=2=4-2=2收点 发点B1B2B3B4发量A16 25344 A244756 A37658 3收量243413（2 2）向向a
11、a1 1，b b1 1较大方向移动一格（或向右，或向下）此时向右移动一格（较大方向移动一格（或向右，或向下）此时向右移动一格（A A1 1，B B2 2）B B2 2需要需要4 4吨，而吨，而A A1 1只有只有2 2吨，吨，A A1 1已发完，划去已发完，划去A A1 1行，并把行，并把b b2 2改成（改成（4-24-2）=2=2。例1 ： （3 3）继续进行）继续进行例1 ： （4 4） 继续进行继续进行例1 ： （5 5）继续进行）继续进行例1 ： （6 6）继续进行）继续进行例1 ：（7 7）得到初始方案得到初始方案： X X1111=2=2，X X1212=2=2，X X2222=
12、2=2，X X2323=3=3，X X2424=1=1，X X3434=3=3，总运费总运费=6*2+5*2+4*2+7*3+5*1+8*3=80=6*2+5*2+4*2+7*3+5*1+8*3=80（元）（元）3. 3. 用用最大差额法（又称Vogel概算法）求解vv 1.1.对每行每列的运价对每行每列的运价C Cijij 分别计算两最小元素之差（取分别计算两最小元素之差（取 正值），将正值），将“行差行差”记于表右侧，记于表右侧，“列差列差”记于表下端。记于表下端。vv 2. 2. 在所有行差、列差中选取一最大差额，若有几个同在所有行差、列差中选取一最大差额，若有几个同 时最大，则可任选其
13、中之一。时最大，则可任选其中之一。vv 3. 3. 在最大差额所在行（列）中选一最小运价，若有几在最大差额所在行（列）中选一最小运价，若有几 个同时最小，则可任选其一。个同时最小，则可任选其一。vv 4.4.在上步所确定的最小运价格内，确定基变量数值并画在上步所确定的最小运价格内，确定基变量数值并画 圈，然后划去其所在行或列，具体做法同最小元素法。圈，然后划去其所在行或列，具体做法同最小元素法。vv 5. 5. 对剩余未划去的行列重复上述步骤，但当只剩下最对剩余未划去的行列重复上述步骤，但当只剩下最 后一行（列）时，不在计算行（列）差，而直接按最小元后一行（列）时，不在计算行（列）差，而直接按
14、最小元 素分配运量，并划去相应的行或列。素分配运量，并划去相应的行或列。Vogel概算法（伏格法）（伏格法）-1-1Vogel概算法（伏格法）（伏格法）-2-2Vogel概算法（伏格法）（伏格法）-3-3Vogel概算法（伏格法）（伏格法）-4-4Vogel概算法（伏格法）伏格法）-5-5Vogel概算法（伏格法）（伏格法）-6-6Vogel概算法（伏格法）（伏格法）-7-7Vogel概算法（伏格法）（伏格法）-8-8Vogel概算法（伏格法）（伏格法）-9-9Vogel概算法（伏格法）（伏格法）-10-10差值法差值法初始方案如下：初始方案如下：X X1313=3=3，X X1414=1=1
15、，X X2121=2=2，X X2222=1=1，X X2424=3=3，X X3232=3=3，费用费用=3*3+4*1+4*2+4*1+5*3+6*3=58=3*3+4*1+4*2+4*1+5*3+6*3=58（元（元）Vogel概算法（伏格法）（伏格法）西北角法西北角法得到初始方案：得到初始方案：X X1111=2=2，X X1212=2=2，X X2222=2=2，X X2323=3=3，X X2424=1=1，X X3434=3=3，总运费总运费=6*2+5*2+4*2+7*3+5*1+8*3=80=6*2+5*2+4*2+7*3+5*1+8*3=80（元）（元）最小元素法最小元素法得到初始方案：得到初始方案：X X1313=3=3，X X1414=1=1，X X2121=2=2，X X2222=4=4，X X3434=3=3 总运费总运费=3*3+4*1+4*2+4*4+8*3=61=3*3+4*1+4*2+4*4+8*3=61（元）（元）三种方法比较西北角法西北角法得到初始方案得到初始方案：X X1111=2=2，X X1212=2=2，X X2222=2=2，X X2323=3=3，X X2424=1=1
