----第三章_运输问题.pptVIP

③、 基可行解改进的方法——闭回路调整法 3.3、产销不平衡的运输问题及其求解方法 产量大于销量 销大于产 例3.4 * * 第三章 运输问题 运输问题 约束条件的系数矩阵具有特殊的结构，有更为简单的求解方法，从而节约大量的计算时间和费用。 产地-------- m个 , Ai表示，i=1,2,???,m； 产量 ai , i=1,2,???,m bn ?????? b2 b1 销量 am cmn ?????? cm2 cm1 Am ?????? ?????? ?????? ?????? ?????? ?????? a2 c2n ?????? c22 c21 A2 a1 c1n ?????? c12 c11 A1 产量 Bn ?????? B2 B1 销地 产地 表3.1 要求使总运费最小的调运方案。 Cij:----- 从Ai到Bj运输单位物资的运价 销售地-----n个，Bj 表示，j=1,2,???,n； 销售量 bj，j=1,2,???,n， 3.1、运输问题的数学模型 产销平衡运输问题 数学模型 解: 假设 xij 表示从Ai到 Bj 的运量,则所求的数学模型为: 总产量等于其总销量，即 LP问题--------m?n个变量，m + n个约束条件. 单纯形法求解，在每个约束上加入一个人工变量 若 m =4，n = 5，变量个数就有29个之多，非常复杂。 基本概念 闭回路 凡是能排成 互不相同，且 形成的变量的集合 顶点---出现在闭回路中的变量 闭回路的边--相邻两个变量用一条直线相连 例3.1 设 m = 3，n = 4，表3.2 x34 x32 A3 x24 x21 A2 x12 x11 A1 B4 B3 B2 B1 销地 产地 x11、 x12、 x32、 x34、 x24、 x21 构成一个闭回路。 x34 x32 A3 A2 x14 x12 A1 B4 B3 B2 B1 销地 产地 如果把一个闭回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的,每一行或一列由折线相连的闭回路的顶点只有2个。 定理3.1： m+n-1个变量 构成基变量的充分必要条件是它不包含有任何闭回路。 比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。 求解运输问题的一种简化方法，实质是单纯形法。 （1）找初始基可行解----即在 (m?n) 产销平衡表上给出m+n -1个数字格--不能构成闭回路，且行和等于产量，列和等于销售量； （2）求非基变量检验数---在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步； （3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。 （4）重复（2）、（3）步，直到求得最优解为止。 2、 表上作业法 基本思想----就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。 （1） 确定初始基可行解 ① 方法一：最小元素法 例3.2 某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。 表3.5 6 5 6 3 销量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 产量 B4 B3 B2 B1 销地 产地 填上3---表示示 A2 调运3吨给B1， (即x21 =3=min(a2,b1)=min(4 , 3)) 将B1 这一列运价划去，需求已满足，不需要继续调运 。 第二步: 从未划元素中找最小的运价2 ---填上 1 (即x23=1) ，划去A2 这一行运价，表示 A2的产品已分配完毕。 如此，直到单位运价表中所有元素都划去为止。 得到一个初始调运方案，表3.7 3 解：第一步：最小运价为1 1 方案的总运费为 86 元 6 5 6 3 销量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 产量 B4 B3 B2 B1 运价表 6 5 6 3 销量 9 3 6 A3 4 1 3 A2 7 3 4 A1 产量 B4 B3 B2 B1 表3.7 两种特殊情况： 一 、有多个元素同时达到最小，任选一个作