物流运输管理决策-物流运输路线决策

第三节物流运输路线优化决策0102物流运输路线类型物流运输的优化模型03最短路径问题第三节物流运输路线优化决策0405图表分析法表上作业法06供求不平衡运输模型一、物流运输路线类型运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。对分离的、单个始发点和终点的运输网络路线选择问题，最简单和直观的方法是最短路径法。（一）起讫点不同2511214106104131112396581052C1C3D1AB1B3B2D2EC2如果有多个货源地可以服务于多个目的地时，那么我们面临的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。解决这类问题常常可以运用一类特殊的线性规划方法计算，即表上作业法。（二）多起迄点产销数量及单位运价表（二）多起迄点销地产地B1B2B3B4B5产量A1137621230A2511051120A3105371440A4632111060销量3020253540150始发点又是终点的路线选择。这类问题通常在运输工具是同一部门所有的情况下发生。这类问题求解的目标是寻求访问各点的次序，以求运行时间或距离最小化。（三）起迄点重合图9-4所示是通过各点的运行路线示意图，其中图9-4（a）是不合理的运行路线，图9-4（b）是合理的运行路线。（三）起迄点重合图9-4运输路线示意图实际运输中，一些具体限制使得问题变得复杂，比如：每一地点既有货物要送又有货物要取；部分或全部地点的线路开放时间都有所限制；因车辆容量的限制或其他因素，要求先送货；司机的就餐时间和休息时间也在考虑的范围内。有了这些限制，运输路线计划和进度计划就很难找到最佳方案。实际操作中通常是求助于简单易行的方法，求得使问题解决的可行方案。（四）限制条件二、物流运输的优化模型将物品由m个起运地运到n个目的地。已知由i地运到j地的单位运费是Cij。设ai表示i地的供应量，bj表示j地的需求量。引进变量xij，它表示从i地到j地的运量。物流运输问题的数学模型可表述为：

Subjectto：

三、最短路径问题求从A到E的最短路径。2511214106104131112396581052C1C3D1AB1B3B2D2EC2三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4（D1）=d（D1→E）+f5（E）=5+0=5三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4（D2）=d（D2→E）+f5（E）=2+0=2f4(D2)=2三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（C1，D1）+f4（D1）（C1，D2）+f4（D2）f3（C1）=min3+59+2=min=min=8811最优决策C1→D1三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（C2，D1）+f4（D1）（C2，D2）+f4（D2）f3（C2）=min6+55+2=min=min=7117最优决策C2→D2f3(C2)=7三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（C3，D1）+f4（D1）（C3，D2）+f4（D2）f3（C3）=min8+510+2=min=min=121312最优决策C3→D2f3(C2)=7f3(C3)=12三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（B1，C1）+f3（C1）（B1，C3）+f3（C3）f2（B1）=min12+810+12=min=min=202022最优决策B1→C1（B1，C2）+f3（C2）14+721f3(C2)=7f3(C3)=12f2(B1)=20三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（B2，C1）+f3（C1）（B2，C3）+f3（C3）f2（B2）=min6+84+12=min=min=141416最优决策B2→C1（B2，C2）+f3（C2）10+717f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（B3，C1）+f3（C1）（B3，C3）+f3（C3）f2（B3）=min13+811+12=min=min=192123最优决策B3→C2（B3，C2）+f3（C2）12+719f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14f2(B3)=19三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8（A，B1）+f2（B1）（A，B3）+f2（B3）f1（A）=min2+211+19=min=min=192320最优决策A→B2（A，B2）+f2（B2）5+1419f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14f2(B3)=19f1(A)=19三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14f2(B3)=19f1(A)=19状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14f2(B3)=19f1(A)=19状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2

（B2，C1）C1三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14f2(B3)=19f1(A)=19状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2

（B2，C1）C1

（C1，D1）D1三、最短路径问题f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f4(D2)=2f3(C1)=8f3(C2)=7f3(C3)=12f2(B1)=20f2(B2)=14f2(B3)=19f1(A)=19状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2

（B2，C1）C1

（C1，D1）D1

（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E三、最短路径问题总结一个假设——设想已求出Vs到Vt的最短路P为：Vs,…,Vj,…,Vk,…,Vt，根据最短路的性质，从Vs沿P到Vj或Vk的路，就是Vs到Vj或Vk的最短路，这就是说，P不仅是起点Vs到终点Vt的最短路，而且，由Vs到P上任意中间点的最短路也在P上。因此，为了求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后逐步扩展到终点Vt。一个含义——求出的每个节点的状态值代表的是起点到该节点的最短距离。一个原则——求各节点的状态值时，只能利用和该节点有直接连线并且已求出状态值的前节点确定。三、最短路径问题总结求下图所示网络从发点V1到收点V7的最短路径及距离。三、最短路径问题总结P247【例9-3】，确定一条从起点A至终点J的最短运输路线。A起点9084841386690120501321261324812615048156348BEICFHGDJ终点四、图表分析法图表分析法是在分区产销平衡所确定的供销区域内，按照生产地与消费地的地理分布，根据有利于生产、有利于市场供给、近产近销的原则，应用交通路线示意图和商品产销平衡表找出产销之间经济合理的商品运输路线。四、图表分析法P252【例9-5】有一种商品从A地运出40吨，从B地运出70吨，从C地运出30吨，从D地运出60吨，供给a、b、c三地的数量分别为70吨、80吨、50吨，应用图表分析法选择该商品的合理运输路线。四、图表分析法解：（1）编制商品产销平衡表如下商品产销平衡表ABCD调入量a70b80c50调出量40703060200四、图表分析法（2）绘制交通示意图，如下图所示。四、图表分析法（3）制定商品运输方案，如下图所示。四、图表分析法（4）结果填入平衡表，如下表所示。平衡表ABCD调入量a403070b206080c203050调出量40703060200五、表上作业法例：某公司有三个生产同类产品的加工厂（产地），其产量分别为8吨、5吨和11吨，生产的产品由四个销售点（销地）出售，其销量分别为4吨、7吨、6吨和7吨，各加工厂到各销售点的单位运价（元/吨）如下表所示，问产品如何调运才能使总运费最小？单位（元/吨）销产B1B2B3B4A1412411A221039A385116五、表上作业法表上作业法求解运输问题的步骤：先给出一个初始解（初始调运方案），然后对它进行最优性判别，若它不是最优解，就设法进行调整和改进，从而得出新解，再判别，再改进，直至得到最优解为止。给出初始方案：最小元素法、西北角法等方案的最优性检验和改进：闭回路法、位势法目标函数值为：

Z＝5×4＋3×11＋4×2＋1×3＋7×5＋4×6＝123元（一）求初始解——最小元素法411005503704403300课堂练习例2：用最小元素法求出下列运输问题的初始调运方案表4-6销地

产地B1B2B3B4产量（吨）A131131070A2192840A37410590销量（吨）30605060运价（元）（一）求初始解另法——Vogel法具体做法：先计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值，并称其为罚数，再从罚数最大的行或列中找出单位运价最小者，优先满足其供销关系。此种方法可以克服最小元素法有时为了优先考虑某一最小元素，却可能使其他供销点的运输费用大大增加的缺陷。一般来说，Vogel法给出的初始方案质量较好，常用来作为最优方案的近似解。（二）最优解的判定—位势法首先要求出空格（非基变量）的检验数，若全部检验数均大于等于0，则当前基本可行解就是最优解，否则要调整改进，求得一个新的基本可行解。（二）最优解的判定—位势法415743基变量非基变量总运费为：

Z＝123元（二）最优解的判定—位势法作一个新表，表中除表明单位运价外，在下面增加一位势行，右侧增加一位势列。为了指名该运输方案已填入数字的格（即基变量所在的格），在这些格中标以黑色圆点。（二）最优解的判定—位势法计算位势，求各行和各列的位势。求法：对于基变量，ui＋vj＝cij，为了计算简单，常任设某一位势等于0；本例设u2＝0。023110-49（二）最优解的判定—位势法计算非基变量的检验数求法：对于非基变量格，作一位势表，计算各非基变量格的检验数cij-(ui+vj)，填入下表。023110-49121-11012（二）最优解的判定—位势法调整步骤：取检验数负数最小的格A2B4格调整；调整量θ＝min{1，3}＝1；闭回路上的单数格＋θ，双数格－θ，其他格不变。415743121－112101062（二）最优解的判定—位势法得到一个新的可行解：目标函数总运费为：

Z＝6×4＋2×11＋4×2＋1×9＋7×5＋4×6＝122元<123元，比原方案要优化。416742（二）最优解的判定—位势法重复前面的步骤，求新解非基变量的检验数：计算位势，求各行和各列的位势。ui＋vj＝cij，设u1＝0。0411-2-5410（二）最优解的判定—位势法此时，所有检验数都非负，可知这个解为最优解，为最优方案。计算非基变量的检验数计算各非基变量格的cij-(ui+vj)，填入下表。0411-2-54100221912表上作业法小结基变量个数：m+n-1。闭回路的做法：从检验数为负值的方格出发，沿水平或垂直方向，遇有运量格转90度，形成一个封闭的回路。闭回路的顶点除这个方格之外，其他均应由填有数字的格组成。而且每一个空格都存在唯一一条闭回路。最优解判断：当所有非基变量的检验数均非负时，这时的方案即为最优方案。当达到最优解时，如果发现某非基变量的检验数为0，则最优方案可能不唯一。课堂练习例2：求出下列运输问题的最优调运方案表4-6销地

产地B1B2B3B4产量（吨）A131131070A2192840A37410590销量（吨）30605060运价（元）初始方案确定—最小元素法（二）最优解的判定—位势法030101004040030600303003030方案的最优性检验和改进—位势法。（二）最优解的判定—位势法30104060303003-1210-