第三章 运输问题.pptx

第三章运输问题;问题的提出

一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。;经典运输问题——单一品种物资的运输调度问题;网络表示;如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。;二、运输问题数学模型的特点

运输问题一定有最优解；基变量的个数：m+n-1。

运输问题约束条件的系数矩阵：;运输问题具有下述特点：

(1)约束条件系数矩阵的元素等于0或1；

(2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。

;例1某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元／t)示于表3-2中，要求研究产品如何调运才能使总运费最小?;该问题的数学模型：

;一、表上作业法的基本思想和步骤：

1.基本思想：同单纯形法的基本思想;二、表上作业法的步骤

（1）寻找初始基可行解；

最小元素法、西北角法、沃格尔法

（2）求出非基变量检验数（空格的检验数），判断是否为最优解；

闭回路法、位势法

（3）换基改进，找到新的基可行解

闭回路调整法

（4）重复（2）（3）;1.最小元素法

从运价最小的格开始，在格内的左下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。;;2.西北角法

从西北角（左上角）格开始，在格内的左下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。;

;3.沃格尔法

（1）罚数=次小费用-最小费用

（2）找出最大的罚数行或列所对应的最小费用优先安排。

???3）重复计算步骤（1）和（2）;;最优性检验：检查所得到的方案是不是最优方案。

检查的方法与单纯形方法中的原理相同，即计算检验数。

因运输问题目标要求极小，故当所有的空格（即非基变量）的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。

下面介绍两种求检验数的方法：闭回路法和对偶变量法。

;§2用表上作业法求解运输问题;1.闭回路法（结合最小元素法的初始解）;位势（定义）：设有一个基可行解，对应m+n-1个基变量{xij}，对于每个基变量的下标（i、j），存在ui,vj满足ui+vj=cij,i=1,2,..,m;j=1,2,…,n，称这些ui,vj为该基本可行解对应的位势。;2.对偶变量法（位势法）

;设对偶变量向量为

;检验数公式推导：

由σj=Cj-CBB-1Pj=Cj-YPj，因此，

σij=Cij-CBB-1Pij=Cij-YPij

=Cij-(u1,u2,…,um,v1,v2,…,vn)Pij

=Cij-(ui+vj)

当xij为基变量时

σij=Cij-(ui+vj)=0

由此，任选一个对偶变量为0（因为变量数比独立方程多一个），可求出其余所有的ui，vj。再根据σij=Cij-(ui+vj)求出所有非基变量的检验数。;销地

产地;解

的

最

优

性

检

验;（+2）;需要注意的问题

（一）多个空格（非基变量）的检验数为负，任一个都可作为换入变量。一般σij0中最小的对应变量作为换入变量。

（二）最优解时，如果有某非基变量的检验数为0，则说明该运输问题有无穷多最有解。

（三）退化解。在安排运量时，同时划掉了一行和一列，导致基变量个数少一个，因此，需要在被划的一行或者列任意位置补一个0.;产销不平衡的运输问题

有转运的运输问题;1.当产大于销时，即;2.当销大于产时，即;32;33;34;35;本章结束