运筹学课件：第三章 运输问题[1].ppt

第三章 运输问题;运输问题的数学模型（1）;建立模型;运输问题的一般形式 设某种物资共有m个产地A1,A2,…,Am，其产量分别为a1,a2,…,am，另有n个销地B1,B2,…,Bn，其销量分别为b1,b2,…,bn，已知由产 地Ai (i=1,2,…,m)运往销地Bj的(j=1,2,…,n)的单位运价为cij，其数据如下表所示，问应如何调运，才能使总运费最省? ;建立模型;运输问题的数学模型（5）;运输问题的特征（1）;运输问题的特征（2）;约束条件稀疏矩阵的秩≤m+n-1;表上作业法（1）;实例 某公司经销某种产品，有三个加工厂，日产量分别为：A1为7吨、 A2为4吨、A3为9吨；有四个销售点，日销售量分别为： B1为3吨、 B2为6吨、 B3为5吨、 B4为6吨。已知从各工厂到各销售点的运价如下表，求如何调运使总运费最小？;确定初始基可行解——最小元素法 基本思想：“就近供应” 方法 （1）找到运费表中的最小元素，建立供应关系，产大于销时在运费??中划去销列；产小于销时在运费表上划去产行；产等于销时在运费表上划去销列和产行。 （2）在剩余的运费表中继续寻找最小元素，重复步骤（1），直到最后。;确定初始基可行解——伏格尔（Vogel)法 基本思路：元素差额法，在一行（或一列）中，算出最小元素和次小元素的差额，如果差额很大，则优先用最小元素所对应的供应关系供应。 方法： （1）分别计算各行和各列的最小运费和次小运费差额，并填入表中； （2）从行或列的差额中，选择最大者，则该行或列则应该优先满足最小元素供应关系； （3）建立供应关系，产大于销时在运费表中划去销列；产小于销时在运费表上划去产行；产等于销时在运费表上划去销列和产行； （4）在剩余的运费表中继续计算差额，重复步骤（1）、（2），直到最后。;最优解判断——闭合回路法 方法 （1）从一个空格（非基变量）出发，水平或垂直划线，碰到数字格（基变量）则可以转90o，继续划线，直到回到起始格，形成闭合回路。 （2）计算该空格（非基变量）的检验数； （3）重复（1）、（2），得到所有空格的检验数； （4）如果检验数中有小于0的数，说明还没有达到最优解。 注意（1）划线时的旋转方向，一定要形成闭合回路。 （2）闭合回路是唯一的。 （3）闭合回路的顶点，除了起始点为空格（非基变量）外，其他顶点均为非空格（基变量）;基可行解的改进方法 （1）选择检验数为负数，且最小的空格（非基变量）为换入变量，并作闭合回路； （2）在与换入变量同行和同列的其他闭合回路顶点中，选择取值最小的格（基变量）为换出变量； （3）将换出变量的运输量全部转加给换入变量，闭合回路的其他顶点作相应调整。;最优解判断——位势法 运输问题的对偶问题 ;运输问题检验数的计算公式;求解ui和vj; 运输问题解的讨论 有无穷多最优解 空格（非基变量）的检验数全部大于等于0，并且某个空格（非基变量）的检验数为0。 退化 （1）确定初始可行基时 如果确定供需关系两点的供应量等于需求量，这时要划去一行和一列，导致最终得到的基可行解中数字格的数量小于m+n-1。 解决方法：在划去的去一行或一列上的任一空格点上0，使基可行解中数字格的数量保持为m+n-1 （2）在基可行解改进过程中 闭回路上出现两个和两个以上的具有（-1）标记的相等的最小值。这时，一个数字格（基变量）调整为空格，而其它数字格调整为0 ;表上作业法（9）;;;两类特殊的运输问题（1）;;实例 ;两类特殊的运输问题（2）;;两类特殊的运输问题（3）;;;两类特殊的运输问题（4）;;;求解分析 （1）产量等于销量，所以该问题为一平衡运输问题； （2）有三个产地、四个销地、四个中转站，且每个点之间可以相互运输，所以该问题可以转化为11个产地和11个销地的平衡运输问题； （3）目标是实现运费最小，所以不会出现互无来回倒运的现象，即转运的数量不会大于各产地的产量和，因此可设转运数量为各产地的产量和Q； （4）将产地Ai即看作产地也看作销地，则Ai的产量为Q+ai；销量为Q； （5）将销地Bj即看作销地也看作产地，则Bj的销量为bj；产量为Q； （6）中转站即是产地也是销地，产量为Q，销量为Q （7）根据以上分析，将该问题转化为一个平衡运输问题。 ;;可用表上作业法求解的其它问题