运筹学2-2(精品).ppt

《运筹学2-2(精品).ppt》由会员分享，可在线阅读，更多相关《运筹学2-2(精品).ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1表上作业法表上作业法精品课程运筹学n表表上上作作业业法法:建建立立在在运运输输费费用用矩矩阵阵的的求求解解运运输问题的方法。输问题的方法。n表表上上作作业业法法求求解解运运输输问问题题的的思思想想和和单单纯纯形形法法完完全类似：全类似：确确定定一一个个初初始始基基本本可可行行解解 根根据据最最优优性性判判别别准准则则来来检检查查这这个个基基本本可可行行解解是是不不是是最最优优的？的？如果是，则计算结束；如果是，则计算结束；如果不是，则进行换基。如果不是，则进行换基。直至求出最优解为止。直至求出最优解为止。精品课程运筹学一、初始基本可行解的确定一、初始基本可行解的确定根根据据上上面面的的讨

2、讨论论，要要求求得得运运输输问问题题的的初初始始基基本本可可行行解解，必必须须保保证证找找到到m+n1个个不不构构成成闭闭回回路路的的基基变量。变量。一般的方法步骤如下：一般的方法步骤如下：精品课程运筹学(1)在在运运输输问问题题求求解解作作业业数数据据表表中中任任选选一一个个单单元格元格xij(Ai行行Bj列交叉位置上的格列交叉位置上的格),令令 xij=minai,bj即即从从Ai向向Bj运运最最大大量量(使使行行或或列列在在允允许许的的范范围围内内尽尽量量饱饱和和，即即使使一一个个约约束束方方程程得得以以满满足足),填入填入xij的相应位置；的相应位置；精品课程运筹学(2)(2)从从 a

3、i 和和 bj 中中分分别别减减去去 xij的的值值，修修正正为为新新的的ai 和和 bj ，即即调调整整 Ai 的的拥拥有有量量及及 Bj 的需求量；的需求量；(3)(3)若若 ai=0，则则划划去去对对应应的的行行（已已经经把把拥拥有有的的量量全全部部运运走走），若若 bj=0 则则划划去去对对应应的的列列（已已经经把把需需要要的的量量全全部部运运来来），且且每每次次只只划划去去一一行行或或一一列列（即即每每次次要要去去掉掉且且只只去去掉一个约束）；掉一个约束）；精品课程运筹学(4)(4)当当最最终终的的运运输输量量选选定定时时，其其所所在在行行、列列同同时时满满足足，此此时时要要同同时时

4、划划去去一一行行和和一一列列。这这样样，运运输输平平衡衡表表中中所所有有的的行行与与列列均均被被划划去，则得到了一个初始基本可行解。去，则得到了一个初始基本可行解。否否则则在在剩剩下下的的运运输输平平衡衡表表中中选选下下一一个个变变量，返回量，返回(1)(1)。精品课程运筹学上述计算过程可用流程图描述如下上述计算过程可用流程图描述如下取未划去的单元格取未划去的单元格xij,令令xij=minai,bjai=ai-xijbj=bj-xijai=0?划去第划去第i行行划去第划去第j列列是是否否bj=0否否所所有有行行列列是是否否均均被被划划去去是是找到初始基找到初始基本可行解本可行解求运输问题的初

5、始基本可行解过程求运输问题的初始基本可行解过程注：为了方便，这注：为了方便，这里总记剩余的产量里总记剩余的产量和销量为和销量为ai,bj精品课程运筹学按照上述方法所产生的一组变量的按照上述方法所产生的一组变量的取值将满足下面条件：取值将满足下面条件：(1)所得的变量均为非负，且变量总所得的变量均为非负，且变量总数恰好为数恰好为m+n1个；个；(2)所有的约束条件均得到满足；所有的约束条件均得到满足；(3)所得的变量不构成闭回路。所得的变量不构成闭回路。精品课程运筹学 因因此此，根根据据定定理理及及其其推推论论，所所得得的的解一定是运输问题的基本可行解。解一定是运输问题的基本可行解。在在上上面面

6、的的方方法法中中，xij 的的选选取取方方法法并并没没有有给给予予限限制制，若若采采取取不不同同的的规规则则来来选选取取 xij ，则则得得到到不不同同的的方方法法，较较常常用用的的方方法法有有西西北北角角法法和和最最小小元元素素法法。下下面面分分别举例予以说明。别举例予以说明。精品课程运筹学 1 1、初始基本可行解的确定、初始基本可行解的确定 （1 1）西北角法：西北角法：从西北角（左上角）从西北角（左上角）格开始，在格内的右下角标上允许取得的格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则若某行

7、（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解去，直至得到一个基本可行解。精品课程运筹学 （2 2）最小元素法：最小元素法：从运价最小的格开从运价最小的格开始，在格内的右下角标上允许取得的最大始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。直至得到一个基本可行解。精品课程运筹学 注注:应用

8、西北角法和最小元素法，每应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）任意划去一行（列），在保留的列（行）中没被划去的格内标一个中没被划去的格内标一个0 0。精品课程运筹学精品课程运筹学精品课程运筹学精品课程运筹学 最最优优性性检检验验就就是是检检查查所所得得到到的的方方案案是是不不是是最最优优方方案案。检检查查的的方方法法与与单单纯纯形形方方法法中中的的原原理理

9、相相同同，即即计计算算检检验验数数。由由于于目目标标要要求求极极小小，因因此此，当当所所有有的的检检验验数数都都大大于于或或等等于于零零时时该该调调运运方方案案就就是是最最优优方方案案；否否则则就就不不是是最最优优，需需要要进进行行调调整整。下下面面介介绍绍两种求检验数的方法。两种求检验数的方法。二、基本可行解的最优性检验二、基本可行解的最优性检验 精品课程运筹学1、闭回路法、闭回路法为为了了方方便便，我我们们以以上上表表给给出出的的初初始始基基本本可可行行解解方方案案为为例例，考考察察初初始始方方案案的的任任意意一一个个非非基基变变量量，比比如如x24。根根据据初初始始方方案案，产产地地A2

10、的的产产品品是是不不运运往往销销地地B4的的。如如果果现现在在改改变变初初始始方方案案，把把A2的的产产品品运运送送1个个单单位位给给B4，那那么么为为了了保保持持产产销销平平衡衡，就就必必须须使使x14或或x34减减少少1个个单单位位；而而如如果果x14减减少少1个个单单位位，第第1行行的的运运输输量量就就必必须须增增加加1个个单单位位，例例如如x13增增加加1个个单单位位，那那么么为了保持产销平衡，就必须使为了保持产销平衡，就必须使x23减少减少1个单位。个单位。精品课程运筹学这这个个过过程程就就是是寻寻找找一一个个以以非非基基变变量量x24为为起起始始顶顶点点的的闭闭回回路路x24，x1

11、4，x13，x23，这这个个闭闭回回路路的的其其他他顶顶点点均均为为基基变变量量(对对应应着着填填上上数数字字的的格格)。容容易易计计算算出出上上述述调调整整使使总总的的运运输输费费用用发发生生的的变变化化为为810+32-1，即即总总的的运运费费减减少少1个个单单位位，这这就就说说明明原原始始方方案案不不是是最最优优方方案案，可可以以进进行行调调整整以以得得到到更更好的方案。好的方案。精品课程运筹学可以证明，如果对闭回路的方向不加区别可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为不区别行进

12、方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯对每一个非基变量可以找到而且只能找到唯一的一个闭回路。一的一个闭回路。下下表表中中用用虚虚线线画画出出以以非非基基变变量量x22为为起起始始顶顶点的闭回路。点的闭回路。精品课程运筹学销地产地B1B2B3B4产量3 11 3 410 371 39 2 18 47 4 610 5 39销量365620(产销平衡)A1A2A3精品课程运筹学可可以以计计算算出出以以非非基基变变量量x22为为起起始始顶顶点点的的闭闭回路调整使总的运输费用发生的变化为回路调整使总的

13、运输费用发生的变化为92+310+541即即总总的的运运费费增增加加1个个单单位位，这这就就说说明明这这个个调调整整不能改善目标值。不能改善目标值。从从上上面面的的讨讨论论可可以以看看出出，当当某某个个非非基基变变量量增增加加一一个个单单位位时时，有有若若干干个个基基变变量量的的取取值值受受其其影响。影响。精品课程运筹学这这样样，利利用用单单位位产产品品变变化化（运运输输的的单单位位费费用用）可可计计算算出出它它们们对对目目标标函函数数的的综综合合影影响响，其其作作用用与与线线性性规规划划单单纯纯形形方方法法中中的的检检验验数数完完全全相相同同。故故也也称称这这个个综综合合影影响响为为该该非非

14、基基变变量量对对应应的的检检验验数数。上上面面计计算算的的两两个个非非基基变变量量的的检检验验数数为为 24=-1，22=1。闭闭回回路路方方法法原原理理就就是是通通过过寻寻找找闭回路来找到非基变量的检验数。闭回路来找到非基变量的检验数。精品课程运筹学如如果果规规定定作作为为起起始始顶顶点点的的非非基基变变量量为为第第1个个顶顶点点，闭闭回回路路的的其其他他顶顶点点依依次次为为第第2个个顶顶点点、第第3个顶点个顶点，那么就有，那么就有 ij=(闭闭回回路路上上的的奇奇数数次次顶顶点点单单位位运运费费之之和和)-(闭回路上的偶数次顶点单位运费之和闭回路上的偶数次顶点单位运费之和)其中其中ij 为

15、非基变量的下角指标。为非基变量的下角指标。精品课程运筹学 按按上上述述作作法法，可可计计算算出出表表中中的的所所有有非非基基变变量量的的检检验数，把它们填入相应位置的方括号内，如下图所示。验数，把它们填入相应位置的方括号内，如下图所示。销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量产量A A1 13 3 1 11111 2 23 3 4 41010 3 37 7A A2 21 1 3 39 9 1 12 2 1 18 8-1-14 4A A3 37 7 10 104 4 6 6101012125 5 3 39 9销量销量3 36 65 56 620(20(产销平衡产销平衡

16、)初始基本可行解及检验数初始基本可行解及检验数精品课程运筹学 显显然然，当当所所有有非非基基变变量量的的检检验验数数均均大大于于或或等等于于零零时时，现现行行的的调调运运方方案案就就是是最最优优方方案案，因因为为此此时时对对现现行行方方案案作作任任何何调调整整都都将将导导致致总总的运输费用增加。的运输费用增加。闭闭回回路路法法的的主主要要缺缺点点是是：当当变变量量个个数数较较多多时时，寻寻找找闭闭回回路路以以及及计计算算两两方方面面都都会会产产生生困难。困难。精品课程运筹学 当当非非基基变变量量的的检检验验数数出出现现负负值值时时，则则表表明明当当前前的的基基本本可可行行解解不不是是最最优优解

17、解。在在这这种种情情况况下下，应应该该对对基基本本可可行行解解进进行行调调整整，即即找找到到一一个个新新的的基基本本可可行行解解使使目目标标函函数数值值下下降降，这这一一过过程程通通常常称称为为换换基基(或主元变换或主元变换)过程。过程。三、求新的基本可行解三、求新的基本可行解精品课程运筹学 （1 1）选负检验数中最小者）选负检验数中最小者 rk，那么那么xrk为主元，作为进基变量（上图中为主元，作为进基变量（上图中x24）;（2 2）以以 xrk为起点找一条闭回路，除为起点找一条闭回路，除xrk外其余外其余顶点必须为基变量格（上页图中顶点必须为基变量格（上页图中的回路）的回路）;在运输问题的

18、表上作业法中，换基的过在运输问题的表上作业法中，换基的过程是如下进行：程是如下进行：精品课程运筹学（3）为闭回路的每一个顶点标号，）为闭回路的每一个顶点标号，xrk为为1，沿一个方向（顺时针或逆时针）依次给，沿一个方向（顺时针或逆时针）依次给各顶点标号；各顶点标号；（4）求）求 =minxij xij对应闭回路上的偶对应闭回路上的偶数标号格数标号格=xpq 那么确定那么确定xpq为出基变量，为出基变量，为调整量；为调整量；精品课程运筹学 （5 5）对闭回路的各奇标号顶点调整为：）对闭回路的各奇标号顶点调整为：xij+，对各偶标号顶点对各偶标号顶点调整为：调整为：xij-，特别特别 xpq-=0

19、，xpq变为非变为非基变量。基变量。重复重复(2)(2)、(3)(3)步，直到所有检验数均步，直到所有检验数均非负，得到最优解。非负，得到最优解。精品课程运筹学 ij0，得到最优解得到最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余其余xij=0;最优值：最优值：f*=35+102+13+81+46+53=85精品课程运筹学四、产销不平衡问题的处理四、产销不平衡问题的处理在在实实际际中中遇遇到到的的运运输输问问题题常常常常不不是是产产销销平衡的，而是下列的一般运输问题模型平衡的，而是下列的一般运输问题模型mnminf=cij xij（1）i=1j=1 ns.t

20、.xij sii=1,2,m （2）j=1 m xij(=,)djj=1,2,n(3）i=1 xij 0(i=1,2,m;j=1,2,n)（4）精品课程运筹学我们可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。1.产量大于销量的情况mn考虑si dj 的运输问题，得到的数学模i=1j=1型为精品课程运筹学m nminf=cij xiji=1j=1ns.t.xij sii=1,2,mj=1m xij=dj j=1,2,ni=1xij0(i=1,2,m;j=1,2,n)精品课程运筹学只只要要在在模模型型中中的的产产量量限限制制约约束束（前前m个不等式约束）中引

21、入个不等式约束）中引入m个松弛变量个松弛变量xi,n+1i=1,2,m 即可，变为：即可，变为：n xij+xin+1=sii=1,2,m j=1然后，需设一个销地然后，需设一个销地Bn+1,它的销量为：它的销量为：m nbn+1=si-dji=1j=1精品课程运筹学这里，松弛变量xi n+1可以视为从产地A i运往销地Bn+1的运输量，由于实际并不运送，它们的运费为 ci n+1=0i=1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。精品课程运筹学 例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所

22、示，问：应如何调运可使总运输费用最小？精品课程运筹学 解：增加一个虚设的销地运输费用为解：增加一个虚设的销地运输费用为0 0精品课程运筹学2.销量大于产量的情况销量大于产量的情况m n考虑考虑 si dj 的运输问题，得到的数学模型为的运输问题，得到的数学模型为i=1j=1m nMinf=cij xiji=1j=1 n s.t.xij=sii=1,2,mj=1m xij djj=1,2,ni=1xij0(i=1,2,m;j=1,2,n)精品课程运筹学只只要要在在模模型型中中的的产产量量限限制制约约束束（后后n个个不不等等式式约约束束）中中引引入入n个个松松弛弛变变量量xm+1jj=1,2,n即

23、可，变为：即可，变为：m xij+xm+1j=djj=1,2,mi=1然后，需设一个产地然后，需设一个产地A m+1,它的销量为：它的销量为：n m am+1=dj-sij=1 i=1精品课程运筹学这这里里，松松弛弛变变量量x m+1,j可可以以视视为为从从产产地地A m+1运运往往销销地地Bj的的运运输输量量，由于实际并不运送，它们的运费为由于实际并不运送，它们的运费为c m+1,j=0j=1,2,n。于于是是，这这个个运运输输问问题题就就转转化化成成了了一一个个产产销销平平衡衡的的问题。问题。精品课程运筹学 例例:某公司从两个产地某公司从两个产地A A1 1、A A2 2将物品运往将物品运往三个销地三个销地B B1 1、B B2 2、B B3 3，各产地的产量、各销地各产地的产量、各销地的销量和各产地运往各销地每件物品的运费的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费如下表所示，问：应如何调运可使总运输费用最小？用最小？精品课程运筹学 解：增加一个虚设的产地运输费用为解：增加一个虚设的产地运输费用为0 0精品课程运筹学