第四章物流运筹学运输问题

第四章物流运筹学运输问题第1页，共23页，2023年，2月20日，星期三知识目标掌握运输问题的基本形式（数学模型）掌握表上作业法的求解过程

技能目标能够结合实际情况建立运输问题的模型，并可利用表上作业法求解能够利用所学方法指导实际工作，解决实际问题第2页，共23页，2023年，2月20日，星期三第一节运输问题的数学模型建立运输问题的数学模型介绍闭回路和孤立点的概念给出运输问题数学模型的特性第3页，共23页，2023年，2月20日，星期三运输问题的数学模型s.t.(4-1)其中第4页，共23页，2023年，2月20日，星期三闭回路和孤立点的概念设E是运输问题的一组变量。如果对E中变量作适当的排列后能得到下列形式：

其中互不相同，互不相同，则称E为运输问题的一个闭回路。闭回路中的相应变量称为闭回路的顶点。设Q是运输问题一组变量，若xij为Q中的一个变量，且xij是第i行或第j列中属于Q的唯一变量，则称xij为Q的一个孤立点。第5页，共23页，2023年，2月20日，星期三运输问题数学模型的特性（1）在运输问题的m+n个等式约束方程中只有m+n-1个方程是相互独立的，而且其中任意一组m+n-1个约束方程都是相互独立的。（2）在运输问题的mn个变量中，选取m+n-1个变量构成变量组Q，则Q能成为基变量组的充要条件是：Q中不存在闭回路。（3）设Q是运输问题的一组基变量，xst为非基变量，则xst必对应一条唯一的闭回路E。E除顶点xst外，其余顶点都为基变量。（4）如果在运输问题中ai(i=1,…,m)和bj(j=1,…,n)都为整数，则任一基解中各变量的取值亦均为整数。第6页，共23页，2023年，2月20日，星期三【例4-1】现有m个发点，可供应某种物资给n个收点。发点Ai的物资供应量（发量）为ai，收点Bj

对物资的需求量（收量）为bj，且收发平衡，即。又设单位物资从Ai运往Bj的单位运价为cij。问怎样运输这些物资，以使总运费最小？第7页，共23页，2023年，2月20日，星期三第二节表上作业法初始基可行解的确定位势法求解第8页，共23页，2023年，2月20日，星期三初始基可行解的确定西北角法：西北角法按以下规则在mn个变量中选择m+n-1个基变量构成变量组Q：从运输表格的西北角x11开始，优先安排编号小的发点和收点之间的运输任务。最小元素法：最小元素法按以下规则选取m+n-1个基变量，优先安排单位运价cij小的发点Ai与收点Bj之间的运输任务。。第9页，共23页，2023年，2月20日，星期三位势法求解位势法的算法步骤：（1）应用西北角法或最小元素法求得初始基本可行解xij和相应的基本变量组Q。（2）由方程组（4-3），求得位势ui和vj。（3）计算检验数σij=cij-ui-vj，取σst=min{σst

}。（4）判断σst是否为零。若为零，则xij即为最优解，算法终止。若不为零，则确定中的闭回路E以及E+和E-第10页，共23页，2023年，2月20日，星期三（5）取。（6）取

转步骤（2）。第11页，共23页，2023年，2月20日，星期三【例4-2】给出运输问题，如表4-6所示。使用西北角法确定它的一个基可行解。表4-6

例4-2运需平衡表

Bj

AiB1B2B3B4aiA115A220A310bj1215108第12页，共23页，2023年，2月20日，星期三【例4-4】运输问题见表4-11，用最小元素法求初始基可行解。表4-11

例4-4运量及运价表

Bj

AiB1B2B3B4aiA14731020A2252610A3938425bj12161413第13页，共23页，2023年，2月20日，星期三【例4-7】求解表4-17所给的运输问题（用最小元素法求初始基可行解）。

BjAiB1B2B3B4aiA14731025A2252610A3938425bj12161418表4-17例4-7运输表第14页，共23页，2023年，2月20日，星期三第三节物流配送应用实例【例4-8】运输问题如表4-21所示，试建立该问题的运输模型。表4-21

例4-8运输表

Bj

AiB1B2B3aiA145210A268315bj876第15页，共23页，2023年，2月20日，星期三【例4-9】（不平衡运输问题）若发点的发量必须运走，具体信息如表4-24，试建立运输模型。

表4-24

例4-9运量及运价表

Bj

AiB1B2B3aiA142310A256415A334520101010最低需求量第16页，共23页，2023年，2月20日，星期三本章小结本章首先介绍了一般平衡物资运输问题及其模型，依据单纯形法的基本原理，给出了求解平衡运输问题的直观方法——表上作业法。讨论了非平衡运输问题向平衡运输问题的转换。最后，介绍了运输模型在物流配送领域中的应用。本章的重点是求解平衡运输问题的表上作业法原理及其具体计算方法。其中，初试调运方案的确定、调运方案优劣性检验、调运方法的改进是掌握该方法的难点。第17页，共23页，2023年，2月20日，星期三案例分析案例加拿大太平洋铁路公司：完善铁路运量规划的方法1．问题描述加拿大太平洋铁路公司是一个完全一体化运作且技术领先的一级铁路网络，为加拿大、美国东部和中西部提供铁路运输和多式联运服务。北美货运铁路基本采用“以吨位为基础的批运”方式，即在货物积累到一定量时列车才能发车。这一方式试图通过最大限度地利用列车的装载量来使发车总数最小。但实践表明，这一方式妨碍了高效率地利用车组人员、机车和设备，并且它还使得运输周期不确定，在当前运输业竞争日益激烈、服务水平提高很快的情况下，这种不可靠性成为铁路运输服务争夺市场份额的一大弱点。要找到一个更好的替代方法，需要利用到运筹学中的时序安排的约束条件等具体技术。第18页，共23页，2023年，2月20日，星期三2．解决方案加拿大太平洋铁路公司转而采取为铁路所有作业都确定一个固定时间表的方法。该公司利用MultiModal应用软件系统，开发出一个非常适合于交通行业的运作计划。（1）运筹团队建立了一个模型，对每一个车皮的行程和编组计划进行优化，并决定将其放在哪个车次中。（2）团队成员细致地审查该计划，找出日发车批量的波动规律，并为最大量和最小量的时间制定应急计划。（3）利用基于最短路径技术的算法，MultiModal独有的MultiRail程序可以找到减少装备运行里程数、列车运行里程数和列车运行时间的方法，从而降低运作成本，减少在途中时间，是托运人获得更加可靠的运输服务。第19页，共23页，2023年，2月20日，星期三3．成效评价加拿大太平洋铁路公司的运作理念和方式的转变，成本降低了2.85亿美元以上，使其服务更加可靠，大大增加了其收益率。加拿大太平洋铁路公司的总裁RobertRitchie说：“我们开出了这个行业中最好的铁路行程计划模型——最终为我们的客户带来了效能和生产率的提高以及更好的服务。然而，我们的工作不会就此止步——从中，我们认识到：在收益管理和合同谈判等领域，我们还有那么多机会，我们将不断地寻找新的改进方法，对我们未来的成功，运筹学和管理科学将发挥至关重要的作用。”第20页，共23页，2023年，2月20日，星期三问题利用你所学运筹学知识，提出自己的合理化建议与改进方法，以增加管理效益。第21页，共23页，2023年，2月20日，星期三实训设计【实训目标】

掌握运输问题模型的建立和表上作业法解法。【实训内容与要求】

在企业内部根据历史数据和调研获得运输平衡表和单位运价表。在安排工作时，能用数学语言描述完成运输任务的各种限制条件。建立相应的产销平衡运输问题模型，并利用表上作业法求解，给出最优运输方案。【成果与检验】

能