《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第五章 运输问题》由会员分享，可在线阅读，更多相关《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第五章 运输问题（32页珍藏版）》请在金锄头文库上搜索。
1、第五章 运输问题,第一节 运输问题的特点 第二节 表上作业法 第三节 产销不平衡的运输问题,第一节 运输问题的特点,(1)xij的系数非零即1。 (2)A的每个列向量，都是只有2个分量是1。 (3)矩阵=(A|b)的前m行之和减去后n行的和等于零。,第二节 表上作业法,一、初始解的求法 二、最优解的检验 三、位势法 四、几个注意的问题,第二节 表上作业法,表 5-1,一、初始解的求法,1.基可行解的特征 2.确定初始解,1.基可行解的特征,1.基可行解的特征,1.基可行解的特征,2.确定初始解,表 5-4,2.确定初始解,表 5-5,2.确定初始解,表 5-6,二、最优解的检验,1.闭回路法
2、2.基可行解的调整,1.闭回路法,1.闭回路法,2.基可行解的调整,表 5-11,三、位势法,表 5-12,三、位势法,表 5-13,三、位势法,表 5-14,三、位势法,表 5-15,四、几个注意的问题,前面已经指出，运输表中的实格必须保持m+n-1个。因此，在求解初始解时，若遇到填一个实格(最后一次填写除外)要同时划去一个产量和一个销量时，那么在紧挨所填实格的下方或右方的一格填一个“0”表示这也是个实格，所得到的基可行解是退化解。,第三节 产销不平衡的运输问题,前面讲的表上作业法，是以产销平衡，即 mi=1ai=n j=1bj 为前提的。但是实际问题中往往会出现产大于销或产小于销这样不平衡
3、的问题。,第三节 产销不平衡的运输问题,当产大于销时，即 mi=1ain j=1bj 可以虚设一个销地，如将工厂仓库看做一个销地，这个虚销地的销量为mi=1ai-n j=1bj,类似地，当mi=1ain j=1bj时，可以虚设一个产地，这个虚地的产量等于m j=1bj-n i=1ai。,第三节 产销不平衡的运输问题,通过虚设销地或产地，使不平衡的运输问题化为平衡的运输问题。从虚设产地到各销地的距离或单位运价定为零。因为本来就是不存在的运输。对于从各产地到虚设销地的运费或距离也应为零。,第三节 产销不平衡的运输问题,例2 有三个化肥厂供应四个地区农用化肥。假设等量的化肥在这些地区使用效果相同。各化肥厂的年产量、各地区的需要量和各厂到各地的单位运价如表5-16所示。求总运费最省的调运方案。,例2,例2,表 5-16,表 5-17,例2,表 5-18,例2,表 5-19,例2,表 5-20,例2,表 5-21,例2,表 5-22,例2,
