文档介绍：第四章运输问题
运输问题的数学模型
运输问题求解——表上作业法
物流配送应用实例
知识目标
掌握运输问题的基本形式(数学模型)
掌握表上作业法的求解过程
技能目标
能够结合实际情况建立运输问题的模型,并可利用表上作业法求解
能够利用所学方法指导实际工作,解决实际问题
第一节运输问题的数学模型
建立运输问题的数学模型
介绍闭回路和孤立点的概念
给出运输问题数学模型的特性
运输问题的数学模型
.
(4-1)
其中
闭回路和孤立点的概念
设E是运输问题的一组变量。如果对E中变量作适当的排列后能得到下列形式:
其中互不相同, 互不相同,则称E为运输问题的一个闭回路。闭回路中的相应变量称为闭回路的顶点。
设Q是运输问题一组变量,若xij为Q中的一个变量,且xij是第i行或第j列中属于Q的唯一变量,则称xij为Q的一个孤立点。
运输问题数学模型的特性
(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)都为整数,则任一基解中各变量的取值亦均为整数。
【例4-1】现有m个发点,
可供应某种物资给n个收点。
发点Ai的物资供应量(发量)为ai,收点Bj
对物资的需求量(收量)为bj,且收发平衡,
即。又设单位物资从Ai运往Bj的单
位运价为cij。问怎样运输这些物资,以使总运
费最小?
第二节表上作业法
初始基可行解的确定
位势法求解
初始基可行解的确定
西北角法:西北角法按以下规则在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=min{σst }。
(4)判断σst是否为零。
若为零,则xij即为最优解,算法终止。
若不为零,则确定中的闭回路E以及E+和E-