1、第四章第四章 运输问题运输问题运输问题的数学模型运输问题的数学模型 运输问题求解运输问题求解表上作业法表上作业法物流配送应用实例物流配送应用实例知识目标知识目标n掌握运输问题的基本形式（数学模型）n掌握表上作业法的求解过程 技能目标技能目标n能够结合实际情况建立运输问题的模型，并可利用表上作业法求解n能够利用所学方法指导实际工作，解决实际问题第一节 运输问题的数学模型n建立运输问题的数学模型n介绍闭回路和孤立点的概念n给出运输问题数学模型的特性 运输问题的数学模型11minmnijijijzc x11,1,1,0,1,;1,nijijmijjiijxaimxbjnximjn11mnijijab
2、s.t.(4-1)其中闭回路和孤立点的概念n设E是运输问题的一组变量。如果对E中变量作适当的排列后能得到下列形式：其中 互不相同，互不相同，则称E为运输问题的一个闭回路。闭回路中的相应变量称为闭回路的顶点。n设Q是运输问题一组变量，若xij为Q中的一个变量，且xij是第i行或第j列中属于Q的唯一变量，则称xij为Q的一个孤立点。1 11222231,sssi ji ji ji ji ji jxxxxxx12,siii12,sjjj运输问题数学模型的特性（1）在运输问题的m+n个等式约束方程中只有m+n-1个方程是相互独立的，而且其中任意一组m+n-1个约束方程都是相互独立的。（2）在运输问题的
3、mn个变量中，选取m+n-1个变量构成变量组Q，则Q能成为基变量组的充要条件是：Q中不存在闭回路。（3）设Q是运输问题的一组基变量，xst为非基变量，则xst必对应一条唯一的闭回路E。E除顶点xst外，其余顶点都为基变量。（4）如果在运输问题中ai(i=1,m)和bj(j=1,n)都为整数，则任一基解中各变量的取值亦均为整数。【例4-1】现有m个发点 ，可供应某种物资给n个收点 。发点Ai的物资供应量（发量）为ai，收点Bj 对物资的需求量（收量）为bj，且收发平衡，即 。又设单位物资从Ai运往Bj的单 位运价为cij。问怎样运输这些物资，以使总运 费最小？1,imAAA1,jnBBB11mn
4、ijijab第二节 表上作业法n初始基可行解的确定 n位势法求解初始基可行解的确定西北角法：西北角法按以下规则在mn个变量中选择m+n-1个基变量构成变量组Q：从运输表格的西北角x11开始，优先安排编号小的发点和收点之间的运输任务。最小元素法：最小元素法按以下规则选取m+n-1个基变量，优先安排单位运价cij小的发点Ai与收点Bj之间的运输任务。位势法求解位势法的算法步骤：（1）应用西北角法或最小元素法求得初始基本可行解xij和相应的基本变量组Q。（2）由方程组（4-3），求得位势ui和vj。（3）计算检验数ij=cij-ui-vj，取st=minst。（4）判断st是否为零。若为零，则xij
5、即为最优解，算法终止。若不为零，则确定 中的闭回路E以及E+和E-stQx（5）取 。（6）取 转步骤（2）。min|pqijijdxxxE,ijijijijijijxdxExxdxEx 其他 stpqQQxx【例4-2】给出运输问题，如表4-6所示。使用西北角法确定它的一个基可行解。表表4-6 例例4-2运需平衡表运需平衡表 Bj AiB1B2B3B4aiA115A220A310bj1215108【例4-4】运输问题见表4-11，用最小元素法求初始基可行解。表表4-11 例例4-4运量及运价表运量及运价表 Bj AiB1B2B3B4aiA14731020A2252610A3938425bj1
6、2161413【例4-7】求解表4-17所给的运输问题（用最小元素法求初始基可行解）。Bj AiB1B2B3B4aiA14731025A2252610A3938425bj12161418表表4-17 例例4-7运输表运输表第三节 物流配送应用实例【例4-8】运输问题如表4-21所示，试建立该问题的运输模型。表4-21 例4-8运输表 Bj AiB1B2B3aiA145210A268315bj876iAia【例4-9】（不平衡运输问题）若发点的发量必须运走，具体信息如表4-24，试建立运输模型。表表4-24 例例4-9运量及运价表运量及运价表 Bj AiB1B2B3aiA142310A25641
7、5A334520101010最低需求量本章小结n本章首先介绍了一般平衡物资运输问题及其模型，依据单纯形法的基本原理，给出了求解平衡运输问题的直观方法表上作业法。讨论了非平衡运输问题向平衡运输问题的转换。最后，介绍了运输模型在物流配送领域中的应用。n本章的重点是求解平衡运输问题的表上作业法原理及其具体计算方法。其中，初试调运方案的确定、调运方案优劣性检验、调运方法的改进是掌握该方法的难点。案例分析n案例案例 加拿大太平洋铁路公司：完善铁路运量规划的方法n1 问题描述 加拿大太平洋铁路公司是一个完全一体化运作且技术领先的一级铁路网络，为加拿大、美国东部和中西部提供铁路运输和多式联运服务。北美货运铁
8、路基本采用“以吨位为基础的批运”方式，即在货物积累到一定量时列车才能发车。这一方式试图通过最大限度地利用列车的装载量来使发车总数最小。但实践表明，这一方式妨碍了高效率地利用车组人员、机车和设备，并且它还使得运输周期不确定，在当前运输业竞争日益激烈、服务水平提高很快的情况下，这种不可靠性成为铁路运输服务争夺市场份额的一大弱点。要找到一个更好的替代方法，需要利用到运筹学中的时序安排的约束条件等具体技术。n2 解决方案 加拿大太平洋铁路公司转而采取为铁路所有作业都确定一个固定时间表的方法。该公司利用Multi Modal应用软件系统，开发出一个非常适合于交通行业的运作计划。（1）运筹团队建立了一个模
9、型，对每一个车皮的行程和编组计划进行优化，并决定将其放在哪个车次中。（2）团队成员细致地审查该计划，找出日发车批量的波动规律，并为最大量和最小量的时间制定应急计划。（3）利用基于最短路径技术的算法，Multi Modal独有的Multi Rail程序可以找到减少装备运行里程数、列车运行里程数和列车运行时间的方法，从而降低运作成本，减少在途中时间，是托运人获得更加可靠的运输服务。n3 成效评价 加拿大太平洋铁路公司的运作理念和方式的转变，成本降低了2.85亿美元以上，使其服务更加可靠，大大增加了其收益率。加拿大太平洋铁路公司的总裁Robert Ritchie说：“我们开出了这个行业中最好的铁路行
10、程计划模型最终为我们的客户带来了效能和生产率的提高以及更好的服务。然而，我们的工作不会就此止步从中，我们认识到：在收益管理和合同谈判等领域，我们还有那么多机会，我们将不断地寻找新的改进方法，对我们未来的成功，运筹学和管理科学将发挥至关重要的作用。”n问题问题 利用你所学运筹学知识，提出自己的合理化建议与改进方法，以增加管理效益。实训设计【实训目标【实训目标】掌握运输问题模型的建立和表上作业法解法。【实训内容与要求【实训内容与要求】在企业内部根据历史数据和调研获得运输平衡表和单位运价表。在安排工作时，能用数学语言描述完成运输任务的各种限制条件。建立相应的产销平衡运输问题模型，并利用表上作业法求解，给出最优运输方案。【成果与检验【成果与检验】能够建立相应的运输问题模型，利用表上作业法求解，得出最优运输方案。某企业有以下运输问题，发量、收量以及单位运价如表4-48所示。试给出最优调运方案及最小费用。实训设计n 仓库工厂B1B2B3发量A187415A235925收量202010
