《第二节运输问题求解表上作业法.ppt》由会员分享，可在线阅读，更多相关《第二节运输问题求解表上作业法.ppt（51页珍藏版）》请在三一文库上搜索。
1、1,第二节 运输问题求解 表上作业法,运输问题的方法表上作业法： 1、确定一个初始基本可行解； 2、根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束；如果不是，则至3 3、换基，直至求出最优解为止。,2,一、初始基本可行解的确定 根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到 m + n 1 个不构成闭回路的基变量。一般的方法步骤如下： (1)在运输问题求解作业数据表中任选一个单元格 xij ，令 xij = min ai , bj ,3,即从 Ai 向 Bj 运最大量(使行或列在 允许的范围内尽量饱和，即使一个约 束方程得以满足),填入 xij 的相应位 置
2、； (2)从 ai 或 bj 中分别减去 xij 的值，即调整 Ai 的拥有量及 Bj 的需求量；,4,(3)若 ai = 0，则划去对应的行（把拥有的量全部运走），若 bj = 0 则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）； (4)若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，转(4)。,5,上述计算过程可用流程图描述如下,6,按照上述方法所产生的一组变量的 取值将满足下面条件： (1)所得的变量均为非负，且变量总 数恰好为 m + n 1 个； (2)所有的约束条件均得到满足； (3
3、)所得的变量不构成闭回路。,7,因此，根据定理3.1及其推论，所得的解一定是运输问题的基本可行解。 在上面的方法中，xij 的选取方法并没有给予限制，若采取不同的规则来选取 xij ，则得到不同的方法，较常用的方法有西北角法、最小元素法和Vogel法。,8,1、西北角法： 从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,9,2、最小元素法： 从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已
4、满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,10,3、Vogel法： 从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤。,11,应用西北角法、最小元素法和Vogel法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。,12,表1,13,14,15,16,17,最优性检验就是检查所得到的方案是不是最
5、优方案。 检查的方法-计算检验数 由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。,二、基本可行解的最优性检验,18,1、闭回路法 以最小元素法给出的初始基本可行解方案为例，考察初始方案的一个非基变量x24。 根据初始方案，产地 A2 的产品是不运往销地 B4 的。如果现在改变初始方案，把 A2 的产品运送1 个单位给 B4 ，那么为了保持产销平衡，就必须使 x14 或 x34 减少 1 个单位；而如果 x14 减少 1 个单位，第 1 行的运输量就必须增加 1 个单位，例如 x13 增加 1 个单位，那么为了保持产销平衡，就必须使
6、x23 减少 1 个单位。,19,这个过程就是寻找一个以非基变量 x24 为起始顶点的闭回路 x24 ，x14 ，x13 ，x23 ，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。 上述调整使总的运输费用发生的变化为 8 10 + 3 2 -1 ，即总的运费减少 1 个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。,20,可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基变量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。 表4-10中用虚线画出以非基变量 x22
7、 为起始顶点的闭回路。,21,表4-10 以非基变量 x22 为起始顶点的闭回路,22,可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 2 + 3 10 + 5 4 1 即总的运费增加 1 个单位，这就说明这个调整不能改善目标值。 从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。,23,这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，称这个综合影响为该非基变量对应的检验数。 上面计算的两个非基变量的检验数为 24 = -1，22 = 1。 闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。,2
8、4,如果规定作为起始顶点的非基变量为第 1 个顶点，闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点，那么就有 ij = (闭回路上的奇数次顶点单位运费之和) - (闭回路上的偶数次顶点单位运费之和) 其中 ij 为非基变量的下角指标。,25,按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图4-11所示。,26,显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。 闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。,27,2.位势法 位势：设对应基变量x
9、ij 的 m+n-1 个 ij ， 存在ui ,vj 满足 ui+vj=cij ，i=1,2 ,m ; j=1,2 ,n . 称这些 ui , vj 为该基本可行解对应的位势。,28,由于有m + n 个变量（ ui , vj ）， m + n - 1 个方程（基变量个数）， 故有一个自由变量，位势不唯一。,利用位势求检验数： ij = cij - ui - vj i = 1, , m ; j = 1, , n,29,前例，位势法求检验数： step 1 从任意基变量对应的 cij 开始,任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj
10、 从 c14 = 10 开始 step 2 计算非基变量的检验数 ij = cij - ui - vj ；填入圆圈内,30,31,2.运输问题求解 表上作业法,闭回路法和位势法得到的表是一样的。由于检验数不都非负，故这个基本可行解不是最优解。需要找新的基本可行解，使运费不高于当前的基本可行解。,32,当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。 在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程。,2.运输问题求解 表上作业法,三、求新的基本可行解,33,（1）选负检验数中最小者 rk，那么 xrk 为主
11、元，作为进基变量（P55页图中 x24 ）; （2）以 xrk 为起点找一条闭回路，除 xrk 外其余顶点必须为基变量格（P55页图中的回路）;,2.运输问题求解 表上作业法,在运输问题的表上作业法中，换基的过程是如下进行：,34,（3）为闭回路的每一个顶点标号， xrk 为 1，沿一个方向（顺时针或逆时针）依次给各顶点标号； （4）求=Minxijxij对应闭回路上的偶数标号格= xpq那么确定xpq为出基变量，为调整量；,2.运输问题求解 表上作业法,35,（5）对闭回路的各奇标号顶点调整为：xij + ，对各偶标号顶点 调整为：xij - ，特别 xpq - = 0， xpq变为非基变量
12、。 重复(2)、(3)步，直到所有检验数均非负，得到最优解。,2.运输问题求解 表上作业法,36,37,2.表上作业法,ij 0，得到最优解 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 ; 最优值： f* = 35+102+13+81+46+53 = 85,38,四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型 m n Min f = cij xij （4-1） i=1 j=1 n s.t. xij si i = 1,2,m （4-2） j=1 m xij (=,
13、)dj j = 1,2,n (4-3） i=1 xij 0 (i=1,2,m;j=1,2,n)（4-4）,2.运输问题求解 表上作业法,39,我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题。 1.产量大于销量的情况 m n 考虑 si dj 的运输问题，得到的数学模 i=1 j=1 型为,2.运输问题求解 表上作业法,40,2.运输问题求解 表上作业法,m n Min f = cij xij i=1 j=1 n s.t. xij si i = 1,2,m j=1 m xij =dj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n),4
14、1,只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1 i= 1,2,m 即可，变为： n xij+xin+1=si i=1,2,m j=1 然后，需设一个销地B n+1,它的销量为： m n bn+1= si- dj i=1 j=1,2.运输问题求解 表上作业法,42,这里，松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量，由于实际并不运送，它们的运费为 c i n+1 = 0 i = 1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。,2.运输问题求解 表上作业法,43,例4.2:某公司从两个产地A1、A2将物品运往三个销地
15、B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,2.运输问题求解 表上作业法,44,解：增加一个虚设的销地运输费用为0,2.运输问题求解 表上作业法,45,2.销量大于产量的情况 m n 考虑sidj的运输问题，得到的数学模型为 i=1 j=1,2.运输问题求解 表上作业法,m n Min f = cij xij i=1 j=1 n s.t. xij =si i = 1,2,m j=1 m xij dj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n),46,只要在模型中的产量限制约束（后n个不等
16、式约束）中引入n个松弛变量xm+1j j = 1,2,n即可，变为： m xij+xm+1j=dj j=1,2,m i=1 然后，需设一个产地A m+1,它的销量为： n m am+1= dj- si j=1 i=1,2.运输问题求解 表上作业法,47,这里，松弛变量 x m+1j 可以视为从产地 A m+1 运往销地 B j 的运输量，由于实际并不运送，它们的运费为 c m+1j = 0 j = 1,2,n。于是，这个运输问题就转化成了一个产销平衡的问题。,2.运输问题求解 表上作业法,48,例4.3:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,2.运输问题求解 表上作业法,49,解：增加一个虚设的产地运输费用为0,2.运输问题求解 表上作业法,50,社会调查,一、调查生活中的排队现象，并进行归纳和统计。 二、线性规划的方法可以用来解决生活和工作中的哪些问题？ 三、龙泉驿的企业可能会遇到运输问题吗？你们认为有哪些企业？ 四、此外，你们认为还有哪些问题是希望用运筹学或量化办法解决的？,51,结束放映,再见！,