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

第三章 运输问题;运输问题的一般形式 设某种物资共有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，其数据如下表所示，问应如何调运，才能使总运费最省? ;建立模型;运输问题的数学模型（3）;运输问题的特征（1）;运输问题的特征（2）;约束条件稀疏矩阵的秩≤m+n-1;表上作业法（1）;确定初始基可行解——最小元素法 基本思想：“就近供应” 方法 （1）找到运费表中的最小元素，建立供应关系，产大于销时在运费表中划去销列；产小于销时在运费表上划去产行；产等于销时在运费表上划去销列和产行。 （2）在剩余的运费表中继续寻找最小元素，重复步骤（1），直到最后。;确定初始基可行解——伏格尔（Vogel)法 基本思路：元素差额法，在一行（或一列）中，算出最小元素和次小元素的差额，如果差额很大，则优先用最小元素所对应的供应关系供应。 方法： （1）分别计算各行和各列的最小运费和次小运费差额，并填入表中； （2）从行或列的差额中，选择最大者，则该行或列则应该优先满足最小元素供应关系； （3）建立供应关系，产大于销时在运费表中划去销列；产小于销时在运费表上划去产行；产等于销时在运费表上划去销列和产行； （4）在剩余的运费表中继续计算差额，重复步骤（1）、（2），直到最后。;最优解判断——闭合回路法 方法 （1）从一个空格（非基变量）出发，水平或垂直划线，碰到数字格（基变量）则可以转90o，继续划线，直到回到起始格，形成闭合回路。 （2）计算该空格（非基变量）的检验数； （3）重复（1）、（2），得到所有空格的检验数； （4）如果检验数中有小于0的数，说明还没有达到最优解。 注意（1）划线时的旋转方向，一定要形成闭合回路。 （2）闭合回路是唯一的。 （3）闭合回路的顶点，除了起始点为空格（非基变量）外，其他顶点均为非空格（基变量）;最优解判断——位势法 运输问题的对偶问题 ;运输问题检验数的计算公式;求解ui和vj;基可行解的改进方法 （1）选择检验数为负数???且最小的空格（非基变量）为换入变量，并作闭合回路； （2）在与换入变量同行和同列的其他闭合回路顶点中，选择取值最小的格（基变量）为换出变量； （3）将换出变量的运输量全部转加给换入变量，闭合回路的其他顶点作相应调整。; 运输问题解的讨论 有无穷多最优解 空格（非基变量）的检验数全部大于等于0，并且某个空格（非基变量）的检验数为0。 退化 （1）确定初始可行基时 如果确定供需关系两点的供应量等于需求量，这时要划去一行和一列，导致最终得到的基可行解中数字格的数量小于m+n-1。 解决方法：在划去的去一行或一列上的任一空格点上0，使基可行解中数字格的数量保持为m+n-1 （2）在基可行解改进过程中 闭回路上出现两个和两个以上的具有（-1）标记的相等的最小值。这时，一个数字格（基变量）调整为空格，而其它数字格调整为0 ;两类特殊的运输问题（1）;两类特殊的运输问题（2）;两类特殊的运输问题（3）;两类特殊的运输问题（4）;可用表上作业法求解的其它问题;;;第十章 图与网络分析;图论研究的起源（1）;图论研究的起源（2）;图的基本概念（1）;图的基本概念（2）;图的基本概念（3）;;图的基本概念（4）;图的基本概念（5）;图的基本概念（6）;图的基本概念（7）;图的基本概念（8）;;问题实例 有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛.下表中打∨的是各运动员报名参加的比赛项目.问六个项目的比赛顺序如何安排，才能做到每名运动员都不连续地参加两项比赛. ;图的基本概念（9）;图的基本概念（10）;图的基本概念（11）;图的基本概念（12）;树的概念和性质（1）; 树的概念和性质（2）;; 树的概念和性质（3）; 树的概念和性质（4）; 树的概念和性质（5）;;实例