运输网络线路优化计算题.ppt

《运输网络线路优化计算题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、五、运输优化方法运输网络合理优化问题*节约法优化配送运输路线问题最短路径算法*研究从各资源点向各需求点运输某种物资，考虑各点资源量和需求量限制，确定一组运输方案，使总的运输费用最小。如何从许多可供选择的路线中选出最佳的运输路线的方法。求出运输网络中每一对O-D对之间的最短运输距离、最短运行时间以及最省的运输费用。运输问题的表示网络图、线性规划模型、运输表初始基可行解西北角法、最小元素法、伏格尔法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量1、运输网络合理优化问题2321341运输问题网络图s

2、2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106运输问题线性规划模型供应地约束需求地约束运输问题的表格表示西北角法思想：又称左上角法，不考虑产销两地的运输距离（或单位运费），单纯按照产销平衡表从西北角（左上角）至东南角（右下角）的方向，根据供应量和需求量，逐一分配给变量xij最大可能的数量。如果某一行或某一列同时得到满足，只划去一行（列），保留另一列（行），继续安排。初始基可行解的确定初始基可行解—西北角法（1）81313146608001966

3、130000初始基可行解—西北角法（2）813131466最小元素法思想：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始可行解为止。初始基础可行解—最小元素法（1）最小元素法（2）最小元素法（3）最小元素法（4）最小元素法（5）最小元素法（6）最小元素法（6）初始可行解2、产销不平衡的运输问题在实际问题中，往往供需(或产销)不平衡，有时供大于需，有时需大于供。这类问题的解决方法是：当供大于需时，增设一个虚拟的销地；当需大于供时，增设一个虚拟的产地；这样将不平衡的运输问题化为平衡的运输问题

4、来解决。销地产地B1B2B3供应量A127425A236535需求量1025156050销地产地B1B2B3B4供应量A127402510150A23650352510需求量102515(10)60供大于需增设一个虚拟的销地(B4)运价供需平衡从各个产地到虚设的销地(B4)间的单位运输费用都假设为0销地产地B1B2B3供应量A187415A235925需求量2010204050销地产地B1B2B3供应量A18741515A235925205A3000（10)55需求量20102050供小于需增设一个虚拟的产地(A3)供

5、需平衡从虚设的产地到各个销地间的单位运输费用都假设为0当供应量大于需求量时：设一个假想销地DJ+1当供应量小于需求量时：设一个假想产地OI+12、节约法优化配送运输路线问题假设1、配送的是同一种货物2、各个用户的坐标（x，y）即需求量均为已知3、配送中心有足够的运输能力条件1、方案能满足所有用户的要求2、不使任何一辆车超载3、每一辆车每天的总运行时间或者行驶里程不超过规定的上限4、能够满足用户到货时间的要求1、各客户与物流中心相连，得总费用；2、计算每两个用户间的节约里程；3、将各对用户间的节约里程排序；4、从最大节约

6、里程的用户对开始连接，逐渐形成回路，直到达到车辆载重标准。5、将已连接的客户从剩余的节约里程排序中去掉；6、再从剩下的节约里程集合中继续以上过程，直到全部用户都连接起来。求解步骤节约量Sij=2d0i+2d0j–（d0i+d0j+dij）=d0i+d0j–dijPiPjd0id0jdij基本思想中心0用户1用户2用户3用户4用户5中心09用户161012137141771087173用户2用户3用户4用户516例题中心0用户1用户2用户3用户4用户5中心09用户161012137141771087173用户2用户3用户

7、4用户516S12=9+6-7=8S13=9+10-14=5S14=9+12-17=4S15=9+13-7=15S23=6+10-7=9S24=6+12-8=10S25=6+13-10=9S34=10+12-3=19S35=10+13-17=6S45=12+13-16=9节约量Sij=2d0i+2d0j–（d0i+d0j+dij）=d0i+d0j–dij（1）3-4（2）1-5（3）2-4（3-4-2）（4）2-3、4-5、2-5（5）0-3-4-2-5-1-0用户1854159109619用户2用户3用户4用户59节

8、约法的优点（1）一方面体现出优化运输过程，与一般方法相比缩短了运输路程；（2）体现了物流配送网络的优势，实现了企业物流活动的整合；（3）思路简单、清晰，便于执行。节约法的缺点（1）过于强调节约路程，而没有考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。（2）不能对客户的需求进行灵活多变的处理，更适合需求稳