g三章一节运输问题.ppt

1、,第三章 特殊的线性规划,第一节 运输问题,一、 运输问题的数学模型和特征,二、 用表上作业法求解运输问题,三、 其它运输问题的处理,第二节 0-1规划问题,第三节 指派问题,管理 计划 组织,生产1,生产2,生产3,销售1,销售4,销售2,销售3,原材料1,原材料2,原材料3,原材料4,物流,一、 运输问题的数学模型和特征,第一节 运输问题,一、 运输问题的数学模型和特征,例1：某制药公司在全国设有三个生产基地，其中某品种药的日产量为：A1厂700箱，A2厂400箱，A3厂900箱。这些生产基地每天将这些药分别运往四个地区的经销部门，各经销部门每天的需求量为：B1部门300箱，B2部门600

2、箱，B3部门500箱，B4部门600箱。已知从每个生产基地到各销售部门每箱药品的运价如表所示，问该制药公司应如何调运，使在满足各销售部门需要的情况下，总的运输费用最少？,表4-1 各生产基地到各销售部门每箱药品的运费,（金额单位：元）,例1问题的运输表,例1问题的运输表,表4-2 运输表,共有 m n 个变量,一般情况的运输问题,共有 m n 个变量,m+n 个约束方程,产销平衡,例1,运输问题数学模型的特点,（1）约束条件系数矩阵中元素等于0或1； （2）约束条件系数矩阵的每一列有两个非0元素，与每个变量在前 m 个约束方程和后 n 个约束方程中各出现一次相对应。 对于产销平衡的运输问题，还

3、有以下两个特点： （3）所有的结构约束方程都是等式； （4）各产地的产量之和等于各销地的销量之和。,设 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条结

4、论：,返回,二、 用表上作业法求解运输问题,(一)初始基本可行解初始调运方案的求法 1最小元素法,最小元素 0.1,产量400和销量300 最小者,最小元素 0.2,最小元素 0.3,最小元素 0.4,最小元素 0.5,0.3,0.1,0.2,0.4,初始方案的总运费,西北角法,西北角,300,400,200,200,300,600,300,400,100,300,600,300,（二）解的最优性检验 闭回路法求检验数,找出每一个空格(非基变量)的闭回路(只有一个顶点为空格，其他顶点均为填有数字的格)。,11= c11- c21+ c23- c13 = 0.3 - 0.1 + 0.2 - 0.

5、3 = 0.1,（+1）,（-1）,（+1）,（-1）,31= c31-c21+c23-c13 +c14-c34 = 0.7-0.1+0.2-0.3+1.0-0.5 = 1.0,（+1）,（+1）,（-1）,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

6、,注意：在运输问题中通常目标函数是求最小值，所以这时要求所有的检验数为正值。 对于每一个非基变量，在运输表中存在唯一对应一条这样的闭回路。 不能出现全部顶点由填有数字的格构成的闭回路。,位势法求检验数,ij = cij - CB B 1 Aij = cij - ( ui + vj ),不妨设 u 2 = 0,由基变量的检验数等于0，可得到这一组等式。,11 = c11 - ( u1 + v1 ) =0.3-(0.1+0.1)=0.1,24 = c24 - ( u2 + v4 ) =0.8 - ( 0+0.9 )= - 0.1,（0.1）,（- 0.1）,（0.2）,（0.1）,（1.0）,（1

7、.2）,（三）解的改进用闭回路法调整运输方案,检验新解的最优性重复上步骤直至得到最优解为止。,闭回路上偶顶点变量的最小者作为调整量，这里=100,找出检验数ij为最小负值的格子的闭回路,在满足所有约束条件的情况下，尽可能增大这个格子的xij值,调整此闭回路上其他顶点的值,闭回路上奇顶点变量加，偶顶点变量减,+100,+100,-100,-100,- 0.1,改进的解和检验数,Zmin = 0.3500 + 1.0200 + 0.1300 + 0.8100+0.4600 + 0.5300 = 850,（四）平衡运输问题 解法框图,返回,或用 闭回路法,三、其它运输问题的处理 -产销不平衡情况 （

8、见规划教材 P61 ）,#,小 结,三、线性规划的灵敏度分析,运输问题数学模型的特点,（1）约束条件系数矩阵中元素等于0或1； （2）约束条件系数矩阵的每一列有两个非0元素，与每个变量在前 m 个约束方程和后 n 个约束方程中各出现一次相对应。 对于产销平衡的运输问题，还有以下两个特点： （3）所有的结构约束方程都是等式； （4）各产地的产量之和等于各销地的销量之和。,小 结,第一节 运输问题的数学模型,（1）基变量有 m + n - 1 个； （2）一定有最优解； （3）如果 ai 和 bj 都是整数， 则一定有整数最优解。,产销平衡的运输问题，有以下3条结论：,小 结,第二节 表上作业法,一、初始基本可行解的求法 (一) 最小元素法,小 结,(二) 西北角法,二、解的最优性检验 (一) 闭回路法求检验数,(二) 位势法求检验数,找出每一个空格(非基变量)的闭回路(只有一个顶点为空格，其他顶点均为填有数字的格)。,(三) 检验,小 结,三、解的改进,找出检验