第六节运输问题讲义 - 安徽医科大学教务处.ppt

运输问题 秦 侠 安徽医科大学卫生管理学院 Transportation Problem 管理 计划 组织 生产1 生产2 生产3 销售1 销售4 销售2 销售3 原材料1 原材料2 原材料3 原材料4 物流 第一节 运输问题的数学模型 例1：某制药公司在全国设有三个生产基地，其中某品种药的日产量为：A1厂700箱，A2厂400箱，A3厂900箱。这些生产基地每天将这些药分别运往四个地区的经销部门，各经销部门每天的需求量为：B1部门300箱，B2部门600箱，B3部门500箱，B4部门600箱。已知从每个生产基地到各销售部门每箱药品的运价如表所示，问该制药公司应如何调运，使在满足各销售部门需要的情况下，总的运输费用最少？ 表4-1 各生产基地到各销售部门每箱药品的运费 0.5 1.0 0.4 0.7 A3 0.8 0.2 0.9 0.1 A2 1.0 0.3 1.1 0.3 A1 B4 B3 B2 B1 销售部门 生产基地 （金额单位：元） 表4-2 运输表 运输问题数学模型的特点 （1）约束条件系数矩阵中元素等于0或1； （2）约束条件系数矩阵的每一列有两个非0元素，与每个变量在前 m 个约束方程和后 n 个约束方程中各出现一次相对应。 对于产销平衡的运输问题，还有以下两个特点： （3）所有的结构约束方程都是等式； （4）各产地的产量之和等于各销地的销量之和。 例1问题的运输表 设 X=（xij）为运输问题的一个解，则要求每步得到的 X 都必须是基本可行解，这就要求： （1）X 必须满足模型中的所有约束条件； （2）基变量对应的约束方程组的系数列向量线性无关； （3）解中非0变量xij的个数不能多于（m+n-1）个； （4）基变量的个数在迭代过程中应该保持为（m+n-1）个。 例1问题的一个基本可行解 （1）基变量有 m + n - 1 个； （2）一定有最优解； （3）如果 ai 和 bj 都是整数， 则一定有整数最优解。 产销平衡的运输问题，有以下3条结论： 第二节 表上作业法 一、初始基本可行解的求法 (一)最小元素法 最小元素 0.1 产量400和销量300 最小者 最小元素 0.2 最小元素 0.3 最小元素 0.4 最小元素 0.5 0.3 0.1 0.2 0.4 (二)西北角法 西北角 二、解的最优性检验 (一)闭回路法 ?11= c11- c21+ c23- c13 = 0.3 - 0.3 + 0.2 - 0. 1 = 0.1 ?31= c31-c21+c23-c13 +c14-c34 = 0.7-0.1+0.2-0.3+1.0-0.5 = 1.0 找出每一个空格(非基变量)的闭回路(只有一个顶点为空格，其他顶点均为填有数字的格)。 ?12 = c12-c32+c34-c14 = 1.1-0.4+0.5-1.0 = 0.2 ?22 = c22-c32+c34-c14+c13-c23 = 0.9-0.4+0.5-1.0+0.3-0.2= 0.1 ?24 = c24-c14+c13-c23 = 0.8-1.0+0.3-0.2 = - 0.1 ?33 = c33-c34+c14-c13 = 1.0-0.5+1.0-0.3 = 1.2 注意：在运输问题中通常目标函数是求最小值，所以这时要求所有的检验数为正值。 对于每一个非基变量，在运输表中唯一对应一条这样的闭回路。 不能出现全部顶点由填有数字的格构成的闭回路。 (二)位势法 ?ij = cij - CB B –1 Aij = cij - ( ui + vj ) 不妨设 u 2 = 0 由基变量的检验数等于0，可得到这一组等式。