第4章-物资运输和调运问题课件

第四章第四章 物资运输与调运问题物资运输与调运问题4.1 物流运输系统概述4.1.1 运输的概念 运输就是用设备和工具将物品从一地点向另一地点运送的物流活动。运输是物流的核心业务之一，也是物流系统的一个重要功能。运输的一种特殊形式是配送，运输和配送的关系为：所有物品的移动都是运输，而配送则专指短距离、小批量、有组织、有固定渠道的运输。而配送可能还包括装卸、包装等环节，因此，配送和运输是你中有我、我中有你的关系。从社会经济的角度：运输缩小了物质交流的空间，扩大了社会经济活动的范围并实现再次范围内物资价值的平均化、合理化从社会生产的角度：运输时人类社会生产和生活中不可缺少的方面企业物流运输系统主体运输流程厂商 批发者 零售业者运输特征运输手段工厂物流中心物流中心配送中心配送中心店铺店铺店铺大量、大单位、批量水路运输铁路运输大型货车运输大型货物运输铁路运输（集装箱）水路运输（集装箱）中型货车运输小型货车水路运输铁路运输大型货车运输水路运输铁路运输大型货物运输大型货车运输水路运输铁路运输水路运输（集装箱）大型货车运输水路运输铁路运输铁路运输（集装箱）水路运输（集装箱）大型货车运输水路运输铁路运输大型货物运输铁路运输（集装箱）水路运输（集装箱）大型货车运输水路运输铁路运输中型货车运输大型货物运输铁路运输（集装箱）水路运输（集装箱）大型货车运输水路运输铁路运输小型货车中型货车运输大型货物运输铁路运输（集装箱）水路运输（集装箱）大型货车运输水路运输铁路运输水路运输铁路运输水路运输大型货车运输铁路运输水路运输大型货物运输大型货车运输铁路运输水路运输铁路运输（集装箱）大型货物运输大型货车运输铁路运输水路运输水路运输（集装箱）铁路运输（集装箱）大型货物运输大型货车运输铁路运输水路运输中型货车运输水路运输（集装箱）铁路运输（集装箱）大型货物运输大型货车运输铁路运输水路运输小型货车中型货车运输水路运输（集装箱）铁路运输（集装箱）大型货物运输大型货车运输铁路运输水路运输运输的发展单个运输方式多种运输方式的综合运输与商品生产、流通相结合的综合物流物流运输系统的功能1）创造物资的空间效用，将物资由供应地转移）创造物资的空间效用，将物资由供应地转移到需求者手中，满足用户的需求。到需求者手中，满足用户的需求。2）物资运输是物流系统的主要支柱之一。）物资运输是物流系统的主要支柱之一。3）在物流各个子系统中，运输子系统影响和决）在物流各个子系统中，运输子系统影响和决定着其它子系统。定着其它子系统。4）运输费用构成了物流费用的主要部分（约占）运输费用构成了物流费用的主要部分（约占30）。）。5）运输时间构成了物流时间的重要部分。）运输时间构成了物流时间的重要部分。4.1.2 运输方式及其特点按运输设备及运输工具区分按运输线路区分按运输的作用区分按运输的协作程度区分（一）按运输设备及运输工具区分铁路：长距离运行、重载、高速、成本低铁路：长距离运行、重载、高速、成本低公路：门到门运输、灵活性强公路：门到门运输、灵活性强水路：运输量大、运价低、周期长水路：运输量大、运价低、周期长航空：快速、及时航空：快速、及时管道运输：成本低、维修易、只适于特定对象管道运输：成本低、维修易、只适于特定对象，只适合流体、气体运输只适合流体、气体运输上述五种运输方式各有优缺点，选择时应综合考虑，上述五种运输方式各有优缺点，选择时应综合考虑，扬长避短，充分发挥每种运输方式的优势。运输方式扬长避短，充分发挥每种运输方式的优势。运输方式的选择应满足运输的基本要求，即经济性、迅速性、的选择应满足运输的基本要求，即经济性、迅速性、安全性和便利性。由于运输对象、运输距离和运输时安全性和便利性。由于运输对象、运输距离和运输时限的不同，对以上四方面要求的程度也不同限的不同，对以上四方面要求的程度也不同。（二）按运输线路区分干线运输支线运输城市内运输厂内运输（三）按运输的作用区分集货运输配送运输（四）按运输的协作程度区分一般运输联合运输多式联运4.1.3 运输工具1、铁路运输工具铁路机车：蒸汽、内燃、电力铁路车辆平车平车敞车敞车棚车棚车罐车罐车漏斗车漏斗车保温及冷藏车保温及冷藏车特种车特种车2、公路运输工具普通货车轻型货车：2t以下中型货车：28t之间重型货车：8t以上厢式货车专用车辆自卸车牵引车和挂车3、水路运输工具主要包括船、驳、舟、阀物流领域使用的货船主要有：集装箱船散装船油船液化气船滚装船载驳船冷藏船运木船4.1.4运输线路公路：组成部分：路基、路面、桥梁、涵洞、隧道、防护工程、排水设备、山区特殊构造物等级：高速公路；一级四级公路铁路：组成部分：路基、桥隧、轨道空运航线：固定航线（国内、国际）、非固定航线水运航线国际大洋航线、地区性的国际航线、沿海航线定期航线、非定期航线近洋航线、远洋航线4.1.5货物运输分类按货物的营运方式不同分为：整车运输零担运输联合运输集装箱运输按货物的类别不同分为：普通货物运输特种货物运输按运送速度不同分为：一般货物运输快件运输特快专运（递）4.1.6 集装箱运输集装箱的概念：任何一种容器只要满足下述条件，就可称为集装箱：能长期的反复使用，具有足够的强度途中转运不用移动箱内货物，可以直接换装可以进行快速装卸，并可从一种运输工具直接方便地换装到另一种运输工具便于货物的装满和卸空集装箱运输的优点提高货运速度，加快运输工具及货物资金的周转减少货损、货差，提高货运质量简化货物包装，节约货物包装费用，减少运杂费用车船周转加快，装卸费减少，劳动条件改善，运输成本降低不受气候影响，实现了定点、定期运输及装卸作业集装箱运输的基本活动集装箱运输流程中对货物或货物的载体（集装箱）所进行的各种操作，包括位置的移动与集装箱的连接与分离，由这些基本活动可构成一个完整的集装箱运输流程。主要有：与货物、集装箱联接和分离有关的装箱、拆箱、拼箱与使集装箱发生位移的运输活动有关的活动，主要包括海上运输与内陆集疏运对集装箱体进行操作的活动集装箱交接活动集装箱运输体系集集装装箱箱运运输输系系统统海上运输系统海上运输系统内陆集疏运系统内陆集疏运系统港站系统港站系统干线运输干线运输支线运输支线运输铁路集疏运系统铁路集疏运系统公路集疏运系统公路集疏运系统水路集疏运系统水路集疏运系统码头系统码头系统堆场系统堆场系统货运站系统货运站系统4.1.7 国际多式联运是指由多式联运经营人使用两种或两种以上的不同运输方式，将货物运至目的地的国际货物运输以集装箱运输或集装箱货物为主体从某种意义上讲，多式联运就是集装箱多式联运。它通常是以集装箱为运输单元，将不同的运输方式有机地组合在一起构成连续的、综合性的一体化货物运输，通过一次托运、一次计费、一份单证、一次保险，由各运输区段的承运人共同完成货物的全程运输，即将货物的全程运输作为一个完整的单一运输过程来安排国际多式联运的特征必须订立国际多式联运合同全程运输必须使用国际多式联运单据必须使用两种或两种以上不同的运输方式必须是国际间的货物运输多式联运经营人对全程运输负责国际多式联运的运输组织形式海陆联运陆桥运输海空联运4.2 物流运输系统规划概述运输的主要功能是：产品在价值链中的来回移动运输的主要目的是：以最低的时间、财务和环境资源成本，将产品从原产地移动到规定地点；且产品损坏的费用也是最低的。因此，运输成本和运输速度是运输问题中至关重要的因素。4.2.1 运输系统的关键因素（1）运输成本定义：两个地理位置间运输所支付的款项，以及行政管理和维持运输中的存货有关的费用。物流系统的规划设计应利用能将系统总成本降到最低限度的运输注意：费用最低的运输不一定等于最低注意：费用最低的运输不一定等于最低的总成本物流的总成本物流（2）运输速度定义：指为完成特点的运输任务所花费的时间运输速度与成本的关系：运输速度越快、承运商收取的实际费用越高运输服务越快，可用存货越少，可利用的运输间隔时间越短因此，需要合理选择运输。因此，需要选择合理的运输方式，平衡服务速度和运输成本此外，还需要保持物流运输的一致性和物流节点的匹配程度。（3）物流运输的一致性物流运输的一致性是指：在若干次装运中，履行某一次特定运输所需的时间与原定时间或与前几次运输所需时间的一致性。是物流运输可靠性的表现如第一次花了2天，第二次花了6天，则这种变化会使物流作业产生问题：如需要增加安全储备存货、影响双方的义务和风险等（4）与物流节点的匹配程度由于物流运输系统是衔接各物流节点的桥梁，因此，要求要实现与物流节点的匹配，良好对接。如：公路集装箱运输车辆的规格必须与散货堆场的集装箱规格一致等4.2.2运输系统规划与设计的内容确定运输战略 要对运输系统所处的环境进行分析，结合国家政策、市场发展、系统综合以及物流节点的情况，确定运输战略和方向。确定运输路线 当物流节点相对稳定时，可形成不同的运输路线，体现为线路上节点的数目、先后顺序的不同。（运筹学）选择运输方式 明确运输战略、选定运输路线时，选择适当的运输方式；可选择单一的，也可选择多种运输方式的联运运输过程控制 运输过程中，空间变动性，使得对运输过程的控制远远高于对固定物流节点的控制。主要依赖于信息技术（GPS系统，GIS系统等）4.2.3 物流运输系统规划和设计的重点合理化运输 由于运输是物流中最重要的功能要素之一，物流合理化在很大程度上依赖于运输合理化运输合理化的影响因素很多，起决定性作用的有五方面的因素，称做合理运输的“五要素”:1运输距离。2运输环节。3运输工具。4运输时间。5运输费用。运输合理化的途径v运输网络合理配置运输网络合理配置v选择最佳运输方式（及运输工具）选择最佳运输方式（及运输工具）v提高运行效率提高运行效率v推进共同（协同）运输推进共同（协同）运输v实行高效现代化运输方法（新的运输模式）实行高效现代化运输方法（新的运输模式）根据经营战略和销售政策等因素决定费用时间车辆运行率、装载率费用、时间考虑到包装、装卸等环节的配合及其制约因素7/9/202434Copyright:SysCon我国运输现状v发展不平衡；交通运输基本设施落后发展不平衡；交通运输基本设施落后v物流量大，流通距离较长物流量大，流通距离较长v流通网络密度东南大于西北流通网络密度东南大于西北v物的流向南向大于北向、东向大于西向物的流向南向大于北向、东向大于西向v运输效率逐年提高、运输方式分工趋向运输效率逐年提高、运输方式分工趋向合理、协调、有序合理、协调、有序7/9/202435Copyright:SysCon4.2.4物流运输系统规划的总目标满足客户服务，用最低的运输成本连接供货地点和客户物流系统所需服务的对象、反应时间服务过程中的其他如：时间限制、采购地点、物料流动量因此，其优化模型可以用以下模型来表示：最小化：总运输成本约束条件：客户服务政策、运输能力等平衡运输速度和运输成本平衡运输成本以及服务质量（可靠性）主要的问题和方法：1.物资调运问题2.运输路径规划问题4.3 物资调运问题及其模型4.3.1 物资调运问题物资调运问题的提出：大宗物资的调运，如煤、钢铁、木材、粮食等，在全国若干生产基地，如何根据已有的交通网络指定调运方案，保证将这些物资运到各消费地点，且总费用最小。物资调运问题：研究如何以最小的总费用，把某种商品从若干个供应地运至若干个需求地4.3.2 物资调运问题的一般模型某某种种物物资资有有若若干干产产地地和和销销地地，现现在在需需要要把把这这种种物物资资从从各各个个产产地地运运到到各各个个销销地地。已已知知各各产产地地的的产产量量和和各各销销地地的的销销量量以以及及各各产产地地到到各各销销地地的的单单位位运运价价（或或运运距距），问问应应如如何何组组织织调调运，才能使运，才能使总运费（或总运输量）最省总运费（或总运输量）最省？单位单位根据具体问题选择确定根据具体问题选择确定。表表4-1有关信息有关信息单位单位运价运价销销或或运运距距地地产地产地B1B2Bn产产量量A1A2 Amc11c12c1nc21c22c2ncm1cm2cmna1a2 am销销量量b1b2bn2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106调运问题的网络图表示若各地的总供应量等于总需求量，即称为产销平衡问题若总供应量不等于总需求量，则称为产销不平衡问题产销平衡问题的数学模型产销平衡问题的数学模型 设设xij为为从从产产地地Ai运运往往销销地地Bj的的物物资资数数量量（i=1，m；j=1，n），由由于于从从Ai运运出出的的物资总量应等于物资总量应等于Ai的产量的产量ai，因此因此xij应满足：应满足：同理，运到同理，运到Bj的物资总量应该等于的物资总量应该等于Bj的销量的销量bj，所以所以xij还应满足：还应满足：总运费为：总运费为：运输问题的数学模型运输问题的数学模型（4-1）例4-1 调运问题建模 3个工厂向四个销售地点销售，如表，如何调运？供应地约束需求地约束解答二、运输问题的特点与性质二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构约束方程组的系数矩阵具有特殊的结构写出式（写出式（4-1）的系数矩阵）的系数矩阵Am=3行行n=4行行式（式（4-1）的系数矩阵）的系数矩阵A，形式如下：形式如下：m行行n行行矩阵的元素均为矩阵的元素均为1或或0；每一列只有两个元素为每一列只有两个元素为1，其余元素均为，其余元素均为0；列向量列向量Pij=(0,，0，1，0，,0,1,0,0)T，其中两个元素其中两个元素1分别处于第分别处于第i行和第行和第m+j行。行。将该矩阵分块，特点是：将该矩阵分块，特点是：前前m行构成行构成m个个mn阶矩阵阶矩阵，而且，而且第第k个矩阵只有第个矩阵只有第k行元素全为行元素全为1，其余元素全为其余元素全为0（k=1，m）；后后n行构成行构成m个个n阶单位阵阶单位阵。2.运输问题的基变量总数是运输问题的基变量总数是m+n-1可证明系数矩阵可证明系数矩阵A及其增广矩阵的秩都是及其增广矩阵的秩都是m+n-1通过初等行变换，系数矩阵的秩为3+4-1=6 增广矩阵为通过初等行变换，系数矩阵的秩为3+4-1=6 可可以以证证明明：m+n个个约约束束方方程程中中的的任任意意m+n-1个个都都是线性无关的是线性无关的。可证明系数矩阵可证明系数矩阵A及其增广矩阵的秩都是及其增广矩阵的秩都是m+n-1因此，运输问题的基变量总数是因此，运输问题的基变量总数是m+n-1定义定义4.1凡是能排成凡是能排成(4-2)或或(4-3)形形式式的的变变量量集集合合称称为为一一个个闭闭回回路路,并并称称式式中中变变量量为为该该闭闭回回路路的的顶顶点点；其其中中互互不不相同相同,互不相同。互不相同。3.m+n-1个变量构成基变量的个变量构成基变量的充要条件充要条件是是它们不构成它们不构成闭回路闭回路。X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例例4-2设设m=3，n=4，决策变量决策变量xij表示从产地表示从产地Ai到销地到销地Bj的调运量，列表如下，给出闭回路的调运量，列表如下，给出闭回路在表中的表示法在表中的表示法用折线连接起来的顶点变量用折线连接起来的顶点变量。练习练习4-1请给出闭回路请给出闭回路和和在表中的表示法。在表中的表示法。X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34练习练习4-2下面的折线构成的封闭曲线连接的顶下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？点变量哪些不可能是闭回路？为什麽？（a）（b）（c）（d）（e）表表中中的的折折线线构构成成一一条条封封闭闭曲曲线线，且且所所有有的的边都是边都是水平水平或或垂直垂直的；为什麽？的；为什麽？表表中中的的每每一一行行和和每每一一列列由由折折线线相相连连的的闭闭回回路的顶点路的顶点只有两个只有两个；为什麽？；为什麽？每条折线的两端都有一个下标相同i1is,j1js互不相同有关闭回路的一些重要结果有关闭回路的一些重要结果定定理理4-1设设是是一一个个闭闭回回路路，则则该该闭闭回回路路中中的的变变量量所所对对应应的的系系数数列列向向量量具具有有下下面面的的关系：关系：注意：注意：列向量列向量Pij=(0,0,1,0,0,1,0,0)T中两中两个元素个元素1分别处于第分别处于第i行和第行和第m+j行，直接计算行，直接计算即可得到结果。即可得到结果。定定理理的的证证明明可可借借助助定定理理4-1和和高高等等代代数数中中“向向量量组组中中，若若部部分分向向量量线线性性相相关关，则则整整个个向向量量组组就就线线性性相相关关”的的定理得到。定理得到。定理定理4-2若变量组若变量组中中有有一一个个部部分分组组构构成成闭闭回回路路，则则该该变变量组对应的系数列向量线性相关。量组对应的系数列向量线性相关。4.4 运输问题的求解方法求解的基本方法单纯形法表上作业法 由于问题的特殊形式而采由于问题的特殊形式而采用的更简洁、更方便的方法用的更简洁、更方便的方法4.4.1运输问题的表上作业法运输问题的表上作业法一一、表表上上作作业业法法的的基基本本思思想想是是:先先设设法法给给出出一一个个初初始始方方案案,然然后后根根据据确确定定的的判判别别准准则则对对初初始始方方案案进进行行检检查查、调调整整、改改进进，直直至至求求出出最优方案最优方案，如图，如图4-1所示。所示。表表上上作作业业法法和和单单纯纯形形法法的的求求解解思思想想完完全全一一致致，但是具体作法更加简捷。但是具体作法更加简捷。确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否判定是否判定是否最最优？优？是是结结束束最优方案最优方案图图4-1运输问题求解思路图运输问题求解思路图二、二、初始方案的确定初始方案的确定1、作业表（产销平衡表）、作业表（产销平衡表）初始方案就是初始基本可行解。初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量将运输问题的有关信息表和决策变量调调运量结合在一起构成运量结合在一起构成“作业表作业表”（产销平衡表产销平衡表）。）。表表4-2是三个产地、四个销地的运输问题作业表。是三个产地、四个销地的运输问题作业表。表表4-2运输问题作业表（产销平衡表）运输问题作业表（产销平衡表）其中其中xij是决策变量，表示待确定的从第是决策变量，表示待确定的从第i个产个产地到第地到第j个销地的调运量，个销地的调运量，cij为从第为从第i个产地到个产地到第第j个销地的单位运价或运距。个销地的单位运价或运距。2、确定初始方案的步骤：、确定初始方案的步骤：（1）选择一个）选择一个xij，令，令xij=minai，bj=将具体数值填入将具体数值填入xij在表中的位置；在表中的位置；（2）调调整整产产销销剩剩余余数数量量：从从ai和和bj中中分分别别减减去去xij的的值值，若若ai-xij=0，则则划划去去产产地地Ai所所在在的的行行，即即该该产产地地产产量量已已全全部部运运出出无无剩剩余余，而而销销地地Bj尚尚有有需需求求缺缺口口bj-ai；若若bj-xij=0，则则划划去去销销地地Bj所所在在的的列列，说说明明该该销销地地需需求求已已得得到到满满足足，而而产产地地Ai尚尚有有存余量存余量ai-bj；（3）当当作作业业表表中中所所有有的的行行或或列列均均被被划划去去，说说明明所所有有的的产产量量均均已已运运到到各各个个销销地地，需需求求全全部部满满足足，xij的的取取值值构构成成初初始始方方案案。否否则则，在在作作业业表表剩剩余余的的格子中格子中选择选择下一个决策变量，返回步骤（下一个决策变量，返回步骤（2）。）。按按照照上上述述步步骤骤产产生生的的一一组组变变量量必必定定不不构构成成闭闭回回路路，其其取取值值非非负负，且且总总数数是是m+n-1个个，因此构成因此构成运输问题的基本可行解运输问题的基本可行解。对对xij的的选选择择采采用用不不同同的的规规则则就就形形成成各各种种不不同同的的方方法法，比比如如每每次次总总是是在在作作业业表表剩剩余余的的格格子子中中选选择择运运价价（或或运运距距）最最小小者者对对应应的的xij，则则构构成成最最小小元元素素法法，若若每每次次都都选选择择左左上上角角格格子子对应的对应的xij就形成就形成西北角法西北角法（也称（也称左上角法左上角法）。）。初始方案的选择方法最小元素法：直观地想，为了减少运费，有限考虑单位运价最小（距离最短）的供销业务西北角法：优先满足左上角（西北角）上空格的供销需求沃尔格（Vogel）法例4-1 调运问题建模 3个工厂向四个销售地点销售，如表，如何调运？初始基础可行解最小元素法（1）最小元素法（2）最小元素法（3）最小元素法（4）最小元素法（5）最小元素法（6）得到初始调运方案为：得到初始调运方案为：x11=1，x14=13，x21=2，x22=13x23=12，x31=19，最小元素法：初始基础可行解西北角法813131466得到初始调运方案为：得到初始调运方案为：x11=14，x21=8，x22=6x33=6，x34=13，西北角法：三、最优性检验三、最优性检验检查当前调运方案是不是最优方案的过程就检查当前调运方案是不是最优方案的过程就是最优性检验。是最优性检验。检查的方法：检查的方法：计算非基变量计算非基变量（未填上数值的（未填上数值的格，即空格）格，即空格）的检验数的检验数（也称为（也称为空格的检验空格的检验数数），若全部大于等于零，则该方案就是最），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。优调运方案，否则就应进行调整。常用方法：闭回路法和对偶变量法（位势法）常用方法：闭回路法和对偶变量法（位势法）1、闭回路法、闭回路法以以确确定定了了初初始始调调运运方方案案的的作作业业表表为为基基础础，以以一个非基变量作为起始顶点，寻求闭回路。一个非基变量作为起始顶点，寻求闭回路。该该闭闭回回路路的的特特点点是是：除除了了起起始始顶顶点点是是非非基基变变量量外外（空空格格），其其他他顶顶点点均均为为基基变变量量（对对应应着着填上数值的格）。填上数值的格）。可可以以证证明明，如如果果对对闭闭回回路路的的方方向向不不加加区区别别，对对于于每每一一个个非非基基变变量量而而言言，以以其其为为起起点点的的闭闭回回路路存在且唯一存在且唯一。约约定定作作为为起起始始顶顶点点的的非非基基变变量量为为偶偶数数次次顶顶点点，其其它它顶顶点点从从1开开始始顺顺次次排排列列，那那麽麽，该该非非基基变变量量xij的检验数：的检验数：=（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）（4-6）调调销地销地运运量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销量量 100 150 200 450100100100150例例例例4-24-2初始调运方案中以初始调运方案中以初始调运方案中以初始调运方案中以X X1212(X(X2121)为起点的闭回路为起点的闭回路为起点的闭回路为起点的闭回路非基变量非基变量X12的检验数：的检验数：非基变量非基变量X21的检验数：的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经经济济含含义义：在在保保持持产产销销平平衡衡的的条条件件下下，该该非非基基变变量量增增加加一一个个单单位位运运量量而而成成为为基基变变量量时时目目标函数值的变化量标函数值的变化量。2、位势法、位势法以例以例4-2初始调运方案为例，设置初始调运方案为例，设置位势变位势变量量和和，在初始调运方案表的基础上，在初始调运方案表的基础上增加一行和一列（见下页表格）。增加一行和一列（见下页表格）。然后构造下面的方程组：然后构造下面的方程组：（4-7）例例4-2初始调运方案位势变量对应表初始调运方案位势变量对应表 调调销地销地运运量量产地产地 B1 B2 B3产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销量量 100 150 200 450位势变量位势变量vj v1 v2 v3100100100150位势位势变量变量uiu1u2方程组的特点：方程组的特点：方方程程个个数数是是m+n-1=2+3-1=4个个，位位势势变变量量共共有有m+n=2+3=5个个，通通常常称称ui为为第第i行行的的位位势势，称称vj为第为第j列的位势；列的位势；初初始始方方案案的的每每一一个个基基变变量量xij对对应应一一个个方方程程-所所在在行行和和列列对对应应的的位位势势变变量量之之和和等等于于该该基基变量对应的运距（或运价）变量对应的运距（或运价）：ui+vj=cij；计算非基变量计算非基变量xij检验数的公式检验数的公式ij=cij-（ui+vj）（4-8）在在式式（4-7）中中，令令u1=0，则则可可解解得得v1=90，v3=100，u2=-25，v2=90，于是于是12=c12-（u1+v2）=70-（0+90）=-2021=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。与前面用闭回路法求得的结果相同。位势法计算非基变量位势法计算非基变量xij检验数的公式检验数的公式ij=cij-（ui+vj）（4-8）=（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）（4-6）闭回路法计算非基变量闭回路法计算非基变量xij检验数的公式：检验数的公式：总结：检验数计算的两种方法总结：检验数计算的两种方法四、方案调整四、方案调整当当至至少少有有一一个个非非基基变变量量的的检检验验数数是是负负值值时时，说说明明作作业业表表上上当当前前的的调调运运方方案案不不是是最最优优的的，应应进行调整。进行调整。若若检检验验数数ij小小于于零零，则则首首先先在在作作业业表表上上以以xij为为起始变量作出闭回路起始变量作出闭回路，并，并求出调整量求出调整量：ij=min该闭回路中该闭回路中奇数次奇数次顶点调运量顶点调运量xij调调销地销地运运量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销量量 100 150 200 450100100100150+-继续上例，因继续上例，因继续上例，因继续上例，因 1212=-20=-20，画出以画出以画出以画出以x x1212为起始变量的闭回为起始变量的闭回为起始变量的闭回为起始变量的闭回路路路路 计算调整量：计算调整量：=Min（100，150）=100。按照下面的方法调整调运量：按照下面的方法调整调运量：闭闭回回路路上上，奇奇数数次次顶顶点点的的调调运运量量减减去去，偶偶数数次次顶顶点点（包包括括起起始始顶顶点点）的的调调运运量量加加上上；闭闭回路之外的变量调运量不变。回路之外的变量调运量不变。得到新的得到新的调运方案运方案：调调销地销地运运量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销量量 100 150 200 450100100200 50重复上面的步骤，直至求出最优调运方案：重复上面的步骤，直至求出最优调运方案：调调销地销地运运量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销量量 100 150 200 450150 50200 50结结 果果最优调运方案是：最优调运方案是：x11=50，x12=150，x21=50，x23=200相应的最小总运输量为：相应的最小总运输量为：Zmin=9050+70150+8050+75200=34000（吨公里）吨公里）现在，在用西北角法确定例现在，在用西北角法确定例4-1初始调初始调运方案的基础上，分别用闭回路法和运方案的基础上，分别用闭回路法和位势法计算位势法计算：+5非基变量xij的检验数zij-cij闭回路法(1)12=c12-c22+c21-c11=7-4+8-6=5+5闭回路法(2)13=c13-c23+c21-c11=5-2+8-6=5+5+5闭回路法(3)14=c13-c33+c32-c23+c21-c11=3-6+10-2+8-6=7+7+5+5闭回路法(4)24=c24-c34+c33-c23=7-6+10-2=9+9+5+7+5闭回路法(5)31=c31-c21+c23-c33=5-8+2-10=-11-11+5+7+9+5闭回路法(6)32=c32-c22+c23-c33=9-4+2-10=-3-3+5+7+9-11非基变量xij的检验数zij-cij对偶变量法(1)由于位势变量为7，调运量方格为6，令v4=0对偶变量法(2)u3+v4=c34u3=6对偶变量法(3)u3+v3=c33v3=4对偶变量法(4)u2+v3=c23u2=-2对偶变量法(5)u2+v2=c22v2=6对偶变量法(6)u2+v1=c21v1=10对偶变量法(7)u1+v1=c11u1=-4对偶变量法(8)c12-z12=c12-（u1+v2）=7-（(-4)+6）=5+5对偶变量法(9)c13-z13=c13-（u1+v3）=5-（(-4)+4）=5+5+5对偶变量法(10)c14-z14=c14-u1-v4=3-(-4)-0=7+7+5+5对偶变量法(11)c24-z24=c24-（u2+v4）=7-(-2)-0=9+9+5+5+7对偶变量法(12)c31-z31=c31-（u3+v1）=5-（6+10）=-11-11+5+5+7+9对偶变量法(13)c32-z32=c32-（u3+v2）=9-（6+6）=-3-3+5+5+7+9-11选择进基变量,确定离基变量x31进基,minx21,x33=min8,6=6,x33离基-3-5-5-7-9-11调整运量,重新计算检验数,确定进基、离基变量x14进基,minx11,x34=min14,13=13,x34离基+11+5+5-4-2+8调整运量,重新计算检验数所有cij-zij0,得到最优解。Minz=61+313+82+413+212+519=142+11+5+5+4+8+2一、产销不平衡的运输问题一、产销不平衡的运输问题供供大于求大于求供不应求供不应求增加虚拟销地增加虚拟销地增加虚拟销地增加虚拟销地增加虚拟产地增加虚拟产地增加虚拟产地增加虚拟产地产销平衡的运输问题产销平衡的运输问题对应的运距（或运价）对应的运距（或运价）？转化转化4.5 运输问题的进一步讨论二、转运问题二、转运问题特特点点是是所所调调运运的的物物资资不不是是由由产产地地直直接接运运送送到销地，而是经过若干中转站送达。到销地，而是经过若干中转站送达。求求解解思思路路：转转化化成成一一个个等等价价的的产产销销平平衡衡运运输输问问题题，再再用用表表上上作作业业法法求求出出最最优优调调运运方方案。案。如何转化如何转化？第第一一步步，将将产产地地、转转运运点点、销销地地重重新新编编排排，转运点既作为产地又作为销地；转运点既作为产地又作为销地；第第二二步步，各各地地之之间间的的运运距距（或或运运价价）在在原原问问题题运运距距（运运价价）表表基基础础上上进进行行扩扩展展：从从一一地地运运往往自自身身的的单单位位运运距距（运运价价）记记为为零零，不不存存在在运运输输线线路路的的则则记记为为M（一一个个足足够够大大的正数）；的正数）；第第三三步步，由由于于经经过过转转运运点点的的物物资资量量既既是是该该点点作作为为销销地地的的需需求求量量，又又是是该该点点作作为为产产地地时时的的供供应应量量，但但事事先先又又无无法法获获取取该该数数量量的的确确切切值值，因因此此通通常常将将调调运总量作为该数值的上界运总量作为该数值的上界。对于产地和销地也作类似的处理。对于产地和销地也作类似的处理。本章小结运输问题概述运输系统规划概述及其目标物资调运问题及其一般模型物资调运问题的求解方法表上作业法及其步骤确定初始可行方案（最小元素法、西北角法）最优性检验（闭回路法、位势法）解的改进案例分析加拿大太平洋铁路公司：完善铁路运量规划的方法问题描述加拿大太平洋公司是一个完全一体化运作且技术领先的一级铁路网络，为加拿大、美国东部和中西部提供铁路运输和多式联运服务。北美货运铁路基本采用“以吨位为基础的批运方式”，即在货物积累到一定量时列车才能发车。这一方式试图通过最大限度地利用列车的装载量来使发车总数最小。但实践表明，这一方式妨碍了高效率地使用车组人员、机车和设备，并且它还使得运输周期不确定，在当前运输业竞争日益激烈、服务水平提高很快的情况下，这种不可靠性成为铁路运输服务争夺市场份额的一大弱点。如何处理这种不可靠性？寻找新的发车方案呢？可用的运筹学中的时序安排的约束条件等具体技术。可用的运筹学中的时序安排的约束条件等具体技术。解决方案 加拿大太平洋铁路公司转而采取为铁路所有作业都确定一个固定时间表的方法。该公司利用multi modal 应用软件系统，开发出一个非常适合于交通行业的运作计划。（1）运筹团队建立了一个模型，对每一个车皮的行程和编组计划继续优化，并决定将其放在哪个车次中。（指派）（2）团队成员细致地审查该计划，找出日发车批量的波动规律，并为最大量和最小量的时间制定应急计划。（3）利用基于最短路径技术的算法，multi modal 独有的multi rail 程序可以找到减少装备运行里程数、列车运行里程数和列车运行时间的方法，从而降低运作成本，减少在途中时间，是托运人获得更加可靠的运输服务。成效评价加拿大太平洋铁路公司的运作理念和方式的转变，成本降低了2.85亿美元以上，使其服务更加可靠，大大增加了其收益率。加拿大太平洋铁路公司的总裁Robert Ritchie说：我们开除了这个行业中最好的铁路行程计划模型最终为我们的客户带来了效能和生产率的提高以及更好的服务。然而，我们的工作不会就此止步从中，我们认识到：在收益管理和合同谈判等领域，我们还有那么多机会，我们将不断地寻找新的改进方法，对我们未来的成功，运筹学和管理科学将发挥至关重要的作用。