3-运输问题

《3-运输问题》由会员分享，可在线阅读，更多相关《3-运输问题（55页珍藏版）》请在金锄头文库上搜索。

1、运筹学4,讲课教师：赵晋都,太原理工大学经济管理学院,第三章 运输问题,3.1 供求平衡的运输规划问题 3.2 供求不平衡运输问题的解法 3.3 运输问题的应用举例,一、供求平衡运输问题,供求平衡运输问题及其数学模型 例3-1 供求平衡运输问题 数学模型 表上作业法 求初始基本可行解 计算检验数及最优解检验 调整求新解 解的退化问题,3.1供求平衡运输问题的数学模型,例3-1设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表1-23所示，试安排一个运费最低的运输计划。,供求平衡的运

2、输问题：供：50+60+50=160需：40+40+60+20=160,数学模型,模型特点 m+n个等式约束不是相互独立的，但是任意m+n-1个约束都是相互独立的； 因为约束方程中，独立的方程的个数为m+n-1个，所以基本可行解中，基变量的个数为m+n-1个，非基变量的数量为系数矩阵的结构非常特殊，每列只有两个元素为1，其余均为0,表上作业法运输问题的单纯形法,求解步骤 确定初始可行解 求空格检验数，检验最优解 调整（换基、求新解）可行解 重复作上述2、3两步，直至求得最优解。,确定初始可行解方法一：西北角法,确定初始可行解方法一：西北角法,初始基本可行解,确定供应关系时，在运输表上每填上一个

3、数字，就在表中划去一行或者一列，而运输表中共有m行n列，总共可以划n+m条线，但是当填上最后一个数字时，同时划去一行和一列，所以表中有数字的单元格的个数为m+n-1个，代表着m+n-1个基变量，这些基变量之间是线性无关的，因此构成了运输问题的基本可行解。,用西北角法确定初始基本可行解，简单，但是离最优解较远，并不是一个好的寻找最优解的方法 最小元素法，也称为最小费用法，其基本思想是“就近供应”，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基本可行解为止。,确定初始可行解方法二：最小元素法,计算检验数方法一：闭合回路法,从空格出发，遇到数字格，折直角向前，直到回到出发点。

4、 从每一空格出发，一定存在并可以找到唯一的闭回路,计算检验数方法一：闭合回路法,(+),(),(),(),(+),(+),计算检验数（闭合回路法）,对于空格（1，4）其它的空格,计算检验数方法一：闭合回路法,注意，检验数为零，不要忘记写了。非基变量的检验数为零?,计算检验数方法二：位势法,位势法,根据数字格（基变量所在的格）求U和V，然后对空格（非基变量所在的格）求检验数,计算检验数方法二：位势法,方程 共有m+n-1个方程，但有m+n个变量，一般令 。因此可求得这些变量。 我们称 分别为产地位势和销地位势。 本例：,解得：因而可计算得,计算检验数方法二：位势法,只对数字格（基变量所在的格）求

5、U和V，对空格求检验数,检验数空格对应的运价 对应的U与V之和,调整基本解（换基迭代）闭合回路法,取负检验数中绝对值最大的空格作回路(入基变量)。 从空格开始依次给回路顶点格标“+”和“” 找出“”格中运量最小者（出基变量），作为调整量，将每个“+”格的运量加上该调整量，每个“”格的运量减去该调整量。 即得新的基本可行解。 再计算空格检验数和调整基本解，直到检验数非负为止。,(),(),(+),(+),例3-1 西北角法初始解的调整,(),调整的结果,继续求检验数(闭合回路法或位势法),继续求检验数,调整,调整后,最优解（运费=980）,最优解无穷多和解的退化问题,因为 ，因此最优解有无穷多个

6、。如何求其它最优解？ 出现零的数字格，即为解的退化问题 在求初始解时，若供求余量相等，则引进一个零数字格； 在调整时，若有两个及以上相同最小运量的“”格，调整后，将出现零数字格。 如何添零数字格？（分两种情况考虑）,1.确定初始解时的退化问题,初始解时的退化问题,这个0，不能少，否则基本可行解的数量不足m+n-1个,2.调整引起的退化问题,2.调整引起的退化问题,二、供求不平衡运输问题的解法,供大于求的情况 求大于供的情况 都应化为供求平衡问题后再求解,供大于求的情况,数学模型M个供应单元 N个需求单元,特点与处理办法,特点处理办法：设置一个虚销售点n+1，使且 ，因而化为平衡问题。,结果,求

7、大于供,数学模型M个供应单元 N个需求单元,特点与处理办法,特点处理办法：增加一个虚产地m+1，使且 ，化为平衡问题。,结果,供求不平衡运输问题的例子,供求不平衡，供求，虚设一个供应地A3，令其提供虚的产量22202,供求不平衡运输问题的例子,由于从虚的供应地进行调运是无意义的，因此在使用最小元素法确定初始方案时，不考虑A3行,供求不平衡运输问题的例子,供求不平衡运输问题的例子,(),(),(+),(+),供求不平衡运输问题的例子,三、运输问题的应用举例,例 供求不平衡问题 按最低需求量计算是供大于求，首先增加一个销地将销地4增加一个分部 按最高需求量计算是可能求大于供，增加一产地4。,例3-2 物资调度问题,三个化肥厂，供应给四个地区，运价如表1-36所示，但第三化肥厂不能向第四个地区运送，求总运费最少的调运方案。,化不平衡为平衡问题,对第四需求点的最大供应量：160-100=60吨 按最大需求计算，需求为：150+60=210吨 因此设置虚的第四供应点，供应量：50吨,初始可行解和检验数,第一次调整,最优解：总运费=2460,习题,P 82，习题3.1 表3.38,