运输网络线路优化计算题（课堂PPT）

*五、运输优化方法运输网络合理优化问题*节约法优化配送运输路线问题最短路径算法*研究从各资源点向各需求点运输某种物资，考虑各点资源量和需求量限制，确定一组运输 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使总的运输费用最小。如何从许多可供选择的路线中选出最佳的运输路线的方法。求出运输网络中每一对O-D对之间的最短运输距离、最短运行时间以及最省的运输费用。*运输问题的表示网络图、线性规划模型、运输表初始基可行解西北角法、最小元素法、伏格尔法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量1、运输网络合理优化问题*2321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106*运输问题线性规划模型供应地约束需求地约束*运输问题的表格表示*西北角法思想：又称左上角法，不考虑产销两地的运输距离（或单位运费），单纯按照产销平衡表从西北角（左上角）至东南角（右下角）的方向，根据供应量和需求量，逐一分配给变量xij最大可能的数量。如果某一行或某一列同时得到满足，只划去一行（列），保留另一列（行），继续安排。初始基可行解的确定*初始基可行解—西北角法（1）81313146608001966130000*初始基可行解—西北角法（2）813131466*最小元素法思想：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始可行解为止。*初始基础可行解—最小元素法（1）*最小元素法（2）*最小元素法（3）*最小元素法（4）*最小元素法（5）*最小元素法（6）*最小元素法（6）初始可行解*2、产销不平衡的运输问题在实际问题中，往往供需(或产销)不平衡，有时供大于需，有时需大于供。这类问题的解决方法是：当供大于需时，增设一个虚拟的销地；当需大于供时，增设一个虚拟的产地；这样将不平衡的运输问题化为平衡的运输问题来解决。*销地产地B1B2B3供应量A127425A236535需求量1025156050销地产地B1B2B3B4供应量A127402510150A23650352510需求量102515(10)60供大于需增设一个虚拟的销地(B4)运价供需平衡从各个产地到虚设的销地(B4)间的单位运输费用都假设为0*销地产地B1B2B3供应量A187415A235925需求量2010204050销地产地B1B2B3供应量A18741515A235925205A3000（10)55需求量20102050供小于需增设一个虚拟的产地(A3)供需平衡从虚设的产地到各个销地间的单位运输费用都假设为0*当供应量大于需求量时：设一个假想销地DJ+1**当供应量小于需求量时：设一个假想产地OI+1*2、节约法优化配送运输路线问题假设1、配送的是同一种货物2、各个用户的坐标（x，y）即需求量均为已知3、配送中心有足够的运输能力条件1、方案能满足所有用户的要求2、不使任何一辆车超载3、每一辆车每天的总运行时间或者行驶里程不超过 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 的上限4、能够满足用户到货时间的要求*1、各客户与物流中心相连，得总费用；2、计算每两个用户间的节约里程；3、将各对用户间的节约里程排序；4、从最大节约里程的用户对开始连接，逐渐形成回路，直到达到车辆载重标准。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用户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*节约法的优点（1）一方面体现出优化运输过程，与一般方法相比缩短了运输路程；（2）体现了物流配送网络的优势，实现了企业物流活动的整合；（3）思路简单、清晰，便于执行。*节约法的缺点（1）过于强调节约路程，而没有考虑行程中的时间因素，在许多情况下，时间更能决定物流配送的成本与服务质量。（2）不能对客户的需求进行灵活多变的处理，更适合需求稳定或是需求时间不紧迫的情况，显然不能满足现代多变的市场环境。（3）既要缩短总路程，又要充分利用车辆的运输空间，减少配送车次，往往导致结果并不是总路程最短。*节约法的改进建议由以上的分析可知,节约法简便易行,同时也有一些弊端。是否可以通过改进使其成为一种最优的方法呢？撇开其他因素，只考虑运输路线是否最短，这就是不可能的。早在人们研究这一问题时就发现，即使不考虑运输工具的载运空间，而只考虑在多个节点之间寻求最短巡回路线时(运筹学中的货郎担问题)，虽然人们可以利用动态规划的方法，可是计算量太大，当节点的个数足够多时，即使利用计算机仍是不可取的，而在配送路线中还要考虑运输工具载运空间和配送时间的限制。但是，这并不意味着节约法是不可改进的，只是在配送路线选择决策时，通常考虑较优的原则，而不是最优化原则.*节约法的改进建议1)深入了解客户,加强与客户的信息交流.客户的需求是企业物流服务水平的准绳。只有深入了解客户群体，进行周密细致的研究，才能了解客户对商品的品种、规格、型号、供货期、服务收费及所需的物流增值服务等情况，并在此基础上建立客户管理档案，对未来需求进行预测，这样才能以适当向客户提供高质量的物流服务,从而使企业与客户之间建立稳定的关系，为企业迎来充裕的时间规划配送方案。*节约法的改进建议2)通过对客户需求的时间变化进行分类,增加配送的灵活性客户需求的时间变化决定了运送前的货物联合组装和对物流网络的有效利用。所以，企业应对客户进行分类，对不同的客户实施不同的配送策略与收费。按着客户需求的时间变化可把客户分两类：需求稳定或备货期较长的客户和需求变化无常或备货期较短的客户。对于前一种客户，应充分利用节约法，对其过程详细的规划，尽可能缩短配送的总过程与总的配送时间，提高设备的利用率，节约成本；对后一种客户要尽可能利用节约法原理来实施，但在必要时，为了支持企业的竞争战略，实现对客户的承诺，也可对特定客户进行单个配送。*节约法的改进建议3)节约法的实施过程，要综合考虑路程长短和时间因素。配送过程费用和服务质量取决于时间与路程的综合因素,所以应该在实施过程中综合考虑这两个因素。可以采用以下指标代替各节点间的距离的措施:中间的过程指标用:(路长÷正常速度×正常速度概率+路长÷非常速度×非常速度概率)；或者用:(非常速度路长÷非常速度+正常速度路长÷正常速度);(2)如果服务需求稳定,配送的起止时间是固定的，则中间的过程指标用:(路程长度/平均车速)。*节约法的改进建议4)配送的总体过程实际上还会受商品分拣、装卸、搬运设备和货物组装的共同影响。如果在这些环节上出现不当，如设备落后而延长备货期，管理不善增加这些过程中的商品损坏和组装错误等，都会提高成本，降低服务质量。因此，在优化配送过程，不但要优化配送路线和配送过程，还要提高配送过程其他环节的管理水平和设备的现代化水平。*最短路径算法1、采用Dijkstra算法基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应， 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号），或者是从vs到该点的最短路的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，直至求出从vs到各点的最短路。2、应用结论：如果P是D中从vs到vj的最短路，vi是中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。3、各路径上权值wij≥0*例题237184566134105275934682求从1到8的最短路径*237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},w4=1w4=1w1=04*237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},w2=2w1=0w4=1w2=2*237184566134105275934682X={1,2,4}min{c16,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},w6=3w2=2w4=1w1=0w6=3*237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},w7=3w2=2w4=1w1=0w6=3w7=3*237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},w5=6w2=2w4=1w1=0w6=3w7=3w5=6*237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8*237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+8}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10*237184566134105275934682X={1,2,3,4,5,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10*作业1运输问题的合理优化第一题第二题第三题选择题*1.（）是在一般货物运价的基础上，加上或减去一定的百分比后公布的，适用于指定地区内少数货物的运输。A.整箱货运价B.特种货物运价C.货物等级运价D.一般货物运价2.在综合运输体系中，（）是实现运输的基础。A.一体化的运输系统B.多元化的运输系统C.交通实体网络系统D.交通基础网络系统3.国际多式联运通常是以（）为运输单元的。集装箱B.卡车C.火车D.轮船4.在国际多式联运的运输组织形式中，其中是主要组织形式的是（）。A.海陆联运B.陆陆联运C.陆桥运输D.海空联运5.在国际多式联运的运输组织形式中，（）又称为空桥运输。A.海陆联运B.陆陆联运C.陆桥运输D.海空联运*6.运输提供的主要功能有（）。产品生产B.产品转移C.产品储存D.产品销售E.产品延伸7.现代交通运输主要的运输方式有（）。公路运输B.铁路运输C.航空运输D.水路运输E.管道运输8.国际多式联运的特征有（）。A.必须订立国际多式联运 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 B.全程运输必须使用国际多式联运单据C.全程运输必须使用两种或两种以上不同的运输方式D.必须是国际间的货物运输E.多式联运经营人对全程运输负责9.常见的国际多式联运运输组织形式有（）。A.海陆联运B.陆陆联运C.陆桥运输D.海空联运E.空桥运输10.以下运输方式中，在空间和时间方面具有充分的自由性，可以实现“门到门”运输的是（） A、公路运输B、铁路运输C、水路运输D、航空运输 BCABCDEABCDEAACDE*11、运输结点具有（ ）功能。这一功能将各个运输线路联结成一个系统，便各个线路通过结点变得更为贯通，并且通过转换使运输更好地衔接在一起。 A、衔接功能B、连接功能C、集结功能D、转运功能 12、（ ）深刻体现了交通运输业中的分工专业化与一体化的对立统一。 A、多式联运B、综合运输体系C、交通网络规划D、交通枢纽建设 13、集装箱多式联运这一运输链一体化形式，它的柔性主要体现在运输链的（） A、灵活性B、统一性C、多变性D、多样性  ABD*1.综合运输体系是各种运输方式的总体或总和。2.所谓陆桥运输是指采用集装箱专用列车或卡车，把横贯大陆的铁路或公路作为中间“桥梁”，使大陆两端的集装箱海运航线与专用列车或卡车连接起来的一种连贯运输方式。严格地讲，陆桥运输也是一种海陆联运形式。 3．在考虑运输优化问题时，对不平衡运输问题，一般不能转化为平衡运输问题来考虑。4.准确核算运输成本是制定运价的重要依据。5．综合运输体系的核心问题是（）。A．各种运输方式的合理分工与协调发展　B．交通科技创新C．加大综合运输体系建设的投入　D．运输市场的自由竞争ABBAAA*6．（）是国际多式联运的主要组织形式。A．海陆联运　B．陆陆联运C．海空联运　D．陆空联运7．目前世界上最长的一条陆桥运输线是（）。A．美国大陆桥B．西伯利亚大陆桥C．加拿大大陆桥D．新欧亚大陆桥8．运输市场管理活动的实施,必须采用（）。Ａ．行政手段　　　　　　　B．法律手段C．经济手段　　　　　　　D．以上三种的综合9．从运输成本的内容构成看，主要由（）构成的。A．基础设施成本　　　　B．运转设备成本C．营运成本　　　　　D．作业成本　　　E．中转成本10．优化行业结构、提高生产效率、改善经营环境和促进行业发展是（）。A．运输市场管理的任务B．运输市场管理的目标C．运输市场管理的职能D．运输市场管理的特性BADABCDA*1．在运输过程中，与每一次运输配送直接相关的费用，并与运输里程和运输量成正比的费用，称为（）。A．固定成本B．变动成本C．综合成本D．公共成本2．我国在确定运输价格时，必须遵循（）的原则。A．运输合理化B．以运输价值为基础C．政策性D．比价关系合理性3．构成国际多式联运必须具备()基本条件。A．具有一份多式联运合同和使用一份全程多式联运单证B．是省际间的货物运输C．是国际间的货物运输D．是至少两种不同运输方式的连续运输E．由一个多式联运经营人对货物运输的全程负责*1-1.某公司从两个产地A1,A2将物品运往三个销地B1，B2，B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问应如何调运，使得总运输费最小？（1）用数学规划模型表示上述问题；（2）用最小元素法确定初始可行解。*设xij表示从产地Ai调运到Bj的运输量（i=1，2；j=1，2，3），例如，x12表示从A1调运到B2的物品数量，现将安排的运输量列表如下：*根据上表可写出此问题的数学模型。满足产地产量的约束条件为：x11+x12+x13=200，x21+x22+x23=300.满足销地销量的约束条件为：x11+x21=200，x12+x22=300，x13+x23=200.*所以该运输问题的线性规划的模型如下：目标函数：minf=6x11+4x12+6x13+6x21+5x22+5x23约束条件：x11+x12+x13=200，x21+x22+x23=300，x11+x21=150，x12+x22=150，x13+x23=200.xij≥0.(i=1，2；j=1，2，3)*1-2、有三个起运站，四个目的地，供应量为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，C32=3，C33=9，C34=2.（1）用运输表和数学规划模型表示上述运输问题；（2）用西北角法或最小元素法确定其初始可行解；（3）用闭回路法求其最优调运方案。*运输表（平衡运输问题）1234供应量131455027386503239275需求量40556020175终点起点运输成本*运输问题表述为线型规划形式：min.f(x)=3X11+X12+4X13+5X14+7X21+3X22+8X23+6X24+2X31+3X32+9X33+2X34Subjectto:X11+X12+X13+X14=50X21+X22+X23+X24=50X31+X32+X33+X34=75X11+X21+X31=40X12+X22+X32=55X13+X23+X33=60X14+X24+X34=20所有Xij≥0*用单纯形法解得：X13=50，X22=40，X23=10，X31=50，X32=15，X34=20，总运费为：f(x)=50×4+40×3+10×8+40×2+15×3+20×2=565*123供应量1314502738503239100需求量405060终点起点运输成本1-3、供需不平衡问题(见下表)，3个供应点和3个需求点，但供需不平衡，供应总量大于需求总量，其差额为50，请将其转化为平衡运输问题，并求优化方案。*123虚拟点4供应量1314050273805032390100需求量40506050终点起点运输成本化为平衡运输问题引进虚拟需求点4，需求量为50，运费为0，转化为平衡运输问题，求解。*作业2最短路径算法第一题第二题*6①③②④⑤⑥⑧⑦2743631613672-1、求下图中，从1到8的最短路径*6①③②④⑤⑥⑧⑦274363161367Ps=0*6①③②④⑤⑥⑧⑦274363161367Ps=02,1*6①③②④⑤⑥⑧⑦274363161367Ps=02,1(3)(5)(9)*6①③②④⑤⑥⑧⑦274363161367Ps=02,1(5)(9)3,1(8)*6①③②④⑤⑥⑧⑦274363161367Ps=02,15,23,1(9)(8)*6①③②④⑤⑥⑧⑦274363161367Ps=02,15,23,18,3(9)(14)*6①③②④⑤⑥⑧⑦274363161367Ps=02,15,23,18,39,2(13)(14)*6①③②④⑤⑥⑧⑦274363161367Ps=02,15,23,18,39,213,6(14)*15345233355766744289982-2、假设在下图中,有9个结点组成有向网络，试求从“起点1”到达“终点9”的最短路径。*