物流配送3-4(1).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/7/19 Sunday,#,2026/11/15,物流配送3_4(1),Content,商品运输的优化模型,单纯形法,图表分析作业法,商品供求不均衡运输模型,商品运输优化模型,A1,A2,Ai,Am,产地,B1,B2,Bj,Bn,销地,a1,发运量,需求量,a2,ai,am,b1,b2,bj,bn,单位运价 C,ij,运输里程L,ij,商品运输优化模型,根据上述条件，则各变量应满足,总产量与总销量平衡,商品运输优化模型,合理化方案还需要满足,总运费最低,运输吨公里（里程）最小,Content,商品运输的优化模型,单纯形法,图表分析作业法,商品供求不均衡运输模型,单纯形法,Content,商品运输的优化模型,单纯形法,图表分析作业法,商品供求不均衡运输模型,图表分析作业法,图表分析法,图上作业法,表上作业法,图表分析作业法,图表分析作业法,图表分析法,Step 1：根据产销量编制商品产销平衡表,Step 2：绘制交通示意图,Step 3：制定商品运输方案,Step 4：将结果填入产销平衡表,图表分析作业法,例：,有一种商品从A地运出40吨，从B地运出70吨，从C地运出30吨，从D地运出60吨，供给a、b、c三地的数量分别为70吨、80吨、50吨。,Step 1,图表分析作业法,Step 2,70,a,40,A,70,B,80,b,60,D,50,c,30,C,方框表示运入地，圆框表示运出地,Step 3,(40),(30),(30),(20),(60),(20),图表分析作业法,Step 4,图表分析法适用于产销关系简单的情况,图表分析作业法,图上作业法,两个关键概念,对流：在一段线路上有同一种物资往返运输,10,10,10,10,A1,A2,B1,B2,(10),(10),迂回：在环状线路上走大半圈,没有对流和迂回现象的运输方案是使运力最省的最优方案,A,a,b,c,d,图表分析作业法,图上作业法,目的：克服对流和迂回这两种由于运输力安排不合理所出现的浪费现象。,原则,流向画右方，对流不应当,里圈、外圈分别算，要求不过半圈长,如若超过半圈长，应甩运量最小段,反复求算最优方案,分类,不含回路的调运方案（重点检查对流现象）,含回路的调运方案（重点检查迂回现象）,图表分析作业法,图上作业法,不含回路的调运方案,从各端点开始，按“各端点供需归邻站”的原则进行调配。,流向箭头画在道路走向的右边，可以方便地检查对流情况。,90,40,70,50,40,60,30,70,50,E,D,丙,甲,A,B,乙,C,丁,(40),(100),(70),(40),(70),(10),(50),(10),例：不考虑距离,图表分析作业法,图上作业法,不含回路的调运方案,例：最终方案（不考虑距离）,图表分析作业法,图上作业法,含回路的调运方案（三步寻优方案）,1.假定里程最长的一段没有货流通过，在该段破圈，变成不含回路调运。,2.检查迂回情况，无迂回则达到最优，否则转入第3步。由于流向画在道路的右边，所以圈内和圈外都画有流向，如果圈内和圈外流向的总长度（不能出现对流）都不超过回路总长度的一半，就表明这个回路上没有迂回现象。,3.改变去段破圈方式，甩掉大于总长度一半的圈中的最小运量路段，补上原来破圈的路段，再转第2步。,图表分析作业法,图上作业法,含回路的调运方案（例）,最远距离，在该处破圈,图表分析作业法,图上作业法,含回路的调运方案（例）,150,80,130,110,100,160,170,100,B,A,D,C,a,d,c,b,(150),(20),(100),(10),(90),(70),(100),图表分析作业法,图上作业法,含回路的调运方案（例）,计算回路总长度的一半、内圈长度和外圈长度,存在迂回,图表分析作业法,图上作业法,含回路的调运方案（例）,内圈长度大于总长度一半，甩掉内圈中运量最小的路段，调整方案,150,80,130,110,100,160,170,100,B,A,D,C,a,d,c,b,(130),(20),(80),(90),(70),(30),(80),图表分析作业法,图上作业法,含回路的调运方案（例）,再次计算内圈长度和外圈长度,不存在迂回现象,图表分析作业法,图上作业法,含回路的调运方案（例）,最终方案,图表分析作业法,图上作业法,练习：用图上作业法求出最佳调运方案,A,4,C,1,2,B,3,（3）,（2）,（3）,（3）,（1）,（1）,（1）,7,5,4,3,3,4,2,4,图表分析作业法,表上作业法,Step 1：绘制产销平衡表,Step 2：找出初始的基可行解（最小元素法、左上角法、Vogel法）,Step 3：判别基可行解是否是最优解（霍撒克法则，即位势法）,Step 4：非最优的基可行解的改进（闭回路调整法）,给出初始调运方案,最优性检验,调整上述方案,是,否,图表分析作业法,表上作业法,初始方案的确定（找初始基可行解）,最小费用法（最小元素法）找初始基可行解,步骤1：以运费最小的格子作为开端,步骤2：对该格子的供求量和需求量作比较，以较小的一个作为运量,如供应量超过需求量，下一格移到同一行运费次小的格子；如需求量超过供应量，下一格移到同一列运费最小的格子,图表分析作业法,表上作业法,最小费用法（最小元素法）找初始基可行解,300,50,50,50,50,250,250,550,250,300,300,100,100,500,500,图表分析作业法,表上作业法,最小费用法（最小元素法）找初始基可行解（续）,图表分析作业法,表上作业法,初始方案的确定（找初始基可行解）,左上角法（西北角法）找初始基可行解,步骤1：以运输表左上角（西北角）的格子作为开端,步骤2：对该格子的供求量和需求量作比较，以较小的一个作为运量,步骤3：如供应量超过需求量，下一格移到同一行相邻格子；如需求量超过供应量，下一格移到同一列相邻格子,步骤4：如果需求量等于供应量，下一格移到对角线上相邻格子,图表分析作业法,表上作业法,左上角法（西北角法）找初始基可行解,30,20,20,40,30,10,10,60,20,40,40,图表分析作业法,表上作业法,左上角法（西北角法）找初始基可行解（续）,图表分析作业法,表上作业法,最优性检验,霍萨克法则（位势法）检验是否最优方案,有运量的运价 等于相应的行位势 与列位势 之和,空格里检验数 等于原表相应格的运价 减去行位势 与列位势 之和,（1）,（2）,图表分析作业法,表上作业法,最优性检验,霍萨克法则（位势法）检验是否最优方案,步骤1：取出与原方案中分配有运量的格相对应的运价表的数列，形成位势表。,步骤2：在有运量的运价个数较多的行或列的位势设置为“0”，并根据公式（1）依次求出各行、列位势。,步骤3：根据公式（2），用空格运价减所在行、列位势，求出没有运量的各空格的检验数。,步骤4：若各检验数都,0，则表示是最优方案，否则进行调整。,图表分析作业法,表上作业法,最优性检验,霍萨克法则（位势法）检验是否最优方案,0,5,4,7,-2,-5,5,7,-4,0,2,7,3,9,4,2,0,0,-2,1,1,图表分析作业法,表上作业法,闭回路法调整方案,3,基本原理（例）：,假如乙的物资运1吨给A，总的运费如何变动？由于供应平衡，乙必须少运1吨给C，而甲就必须多运1吨给C，同时甲少运1吨给B，则丁必须多运1吨给B，最后丁必须少运1吨给A。变动的结果是运费增加2元。,图表分析作业法,表上作业法,闭回路法调整方案,步骤1：从出现负值的空格出发，沿行或列方向，遇到有运量的格转90度，形成一个封闭的回路，依次标上+、-号。,步骤2：将所有标有负号的转角格中的运量最小值作为调整数，标有正号的加上基数，标有负号的减去基数。,步骤3：再用霍撒克法则检验，若所有的检验数,0，则表示是最优方案，否则再进行调整,图表分析作业法,表上作业法,闭回路法调整方案,-2,（）,（）,（）,（）,（）,（）,图表分析作业法,表上作业法,闭回路法调整方案,（）,（）,（）,（）,（）,（）,50,300,450,150,250,图表分析作业法,表上作业法,比较初始方案与最优方案的运费,初始方案运费6400元,优化方案运费6000元,图表分析作业法,表上作业法,练习：给出运输表如下，用最小费用法和左上角法分别求出初始调运方案，并用霍撒克法则检验，用闭回路法调整，最后得出最优方案。,Vogel（沃格尔法，又称差额法）,沃格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。,或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小的方格中。,例题：,一般地，Vogel法求初始方案质量最好，最接近最优解；最小元素法次之；左上角法最差。,用Vogel法求初始方案时，如果最大罚数有两个或以上，可取最大罚数所在行或列的,各最小运价的最小者,，确定有运量的格所获得的初始调运方案质量最好。,使用表上作业法的技巧确定初始方案,使用表上作业法的技巧调运方案的调整改进,若调运方案存在多个负检验数，应以,绝对值最大的负检验数,对应空格作为进基变量。若绝对值最大的负检验数对应空格超过一个时，应选择,可增加调运量最多,的绝对值最大的负检验数，将其对应空格作为进基变量。,Content,商品运输的优化模型,单纯形法,图表分析作业法,商品供求不均衡运输模型,商品供求不均衡运输模型,运输问题中产销不平衡时,产销或供过于求，则增加一个假想的销售点，运费为0，作为新销地。,产销的情况,5,0,0,0,25,175,商品供求不均衡运输模型,产销的情况,175,虚拟D,0,0,0,0,25,商品供求不均衡运输模型,练习：三个城市每年需分别供应电力320，250和350单位。由，电站提供，它们的最大可供电量分别为400，450单位。单位费用如表所示。由于需求量大于可供量，决定城市A的供应量可减少030单位，城市B的供应量不变，城市C的供应量不少于270单位，试求总费用最低的分配方案（将可供电量用完）,商品供求不均衡运输模型,商品供求不均衡运输模型,M,M,M,0,0,