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

第1页，共23页，编辑于2022年，星期二 知识目标 掌握运输问题的基本形式（数学模型） 掌握表上作业法的求解过程 技能目标 能够结合实际情况建立运输问题的模型，并可利用表上作业法求解 能够利用所学方法指导实际工作，解决实际问题 第2页，共23页，编辑于2022年，星期二 第一节 运输问题的数学模型 建立运输问题的数学模型 介绍闭回路和孤立点的概念 给出运输问题数学模型的特性 第3页，共23页，编辑于2022年，星期二 运输问题的数学模型 s.t. (4-1) 其中 第4页，共23页，编辑于2022年，星期二 闭回路和孤立点的概念 设E是运输问题的一组变量。如果对E中变量作适当的排列后能得到下列形式： 其中 互不相同， 互不相同，则称E为运输问题的一个闭回路。闭回路中的相应变量称为闭回路的顶点。 设Q是运输问题一组变量，若xij为Q中的一个变量，且xij是第i行或第j列中属于Q的唯一变量，则称xij为Q的一个孤立点。 第5页，共23页，编辑于2022年，星期二 运输问题数学模型的特性 （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页，编辑于2022年，星期二 【例4-1】现有m个发点 ， 可供应某种物资给n个收点 。 发点Ai的物资供应量（发量）为ai，收点Bj 对物资的需求量（收量）为bj，且收发平衡， 即 。又设单位物资从Ai运往Bj的单 位运价为cij。问怎样运输这些物资，以使总运 费最小？ 第7页，共23页，编辑于2022年，星期二 第二节 表上作业法 初始基可行解的确定 位势法求解 第8页，共23页，编辑于2022年，星期二 初始基可行解的确定 西北角法：西北角法按以下规则在mn个变量中选择m+n-1个基变量构成变量组Q：从运输表格的西北角x11开始，优先安排编号小的发点和收点之间的运输任务。 最小元素法：最小元素法按以下规则选取m+n-1个基变量，优先安排单位运价cij小的发点Ai与收点Bj之间的运输任务。。 第9页，共23页，编辑于2022年，星期二 位势法求解 位势法的算法步骤： （1）应用西北角法或最小元素法求得初始基本可行解xij和相应的基本变量组Q。 （2）由方程组（4-3），求得位势ui和vj。 （3）计算检验数σij=cij-ui-vj，取σst=min{σst }。 （4）判断σst是否为零。 若为零，则xij即为最优解，算法终止。 若不为零，则确定 中的闭回路E以及E+和E- 第10页，共23页，编辑于2022年，星期二 （5）取 。 （6）取 转步骤（2）。 第11页，共23页，编辑于2022年，星期二 【例4-2】给出运输问题，如表4-6所示。 使用西北角法确定它的一个基可行解。 表4-6 例4-2运需平衡表 Bj Ai B1 B2 B3 B4 ai A1 15 A2 20 A3 10 bj 12 15 10 8 第12页，共23页，编辑于2022年，星期二 【例4-4】运输问题见表4-11， 用最小元素法求初始基可行解。 表4-11 例4-4运量及运价表 Bj Ai B1 B2 B3 B4 ai A1 4 7 3 10 20 A2 2 5 2 6 10 A3 9 3 8 4 25 bj 12 16 14 13 第13页，共23页，编辑于2022年，星期二 【例4-7】求解表4-17所给的运输问题 （用最小元素法求初始基可行解）。 Bj Ai B1 B2 B3 B4 ai A1 4 7 3 10 25 A2 2 5 2 6 10 A3 9 3 8 4 25 bj 12 16 14 18 表4-17 例4-7运输表 第14页，共23页，编辑于2022年，星