2014运筹学-03-2表上作业法

1制定初始调运方案表上作业法一般分为两个阶段第一阶段，制定初始调运方案;第二阶段，从初始调运方案出发，调整调运方案，逐步获得最优解.第二节表上作业法下面通过例题来介绍几种常用的求运输问题的初始基本可行解的方法左上角法(西北角法)例设有A1,A2和A3的产品需要运到B1,B2,B3和B4四个销地，求如何调运使总运费最少？产地销地供应B1B2B3B4A1291079x11x12x13x14A213425x21x22x23x24A384257x31x32x33x34需求384621这是一个产销平衡问题，西北角法具体步骤第一步，做产销空格表，将空格对应的产销地运费填在空格的右上角.第二步，在表中对左上角进行分配(1)如果产大于销，则在这个方格填上销量,并在表中划去这一列(2)如果销大于产，则在这个方格填上产量,并在表中划去这一行第三步，在剩下的表中，反复进行第二步.产地销地供应B1B2B3B4A1291079A213425A384257需求38462133-39-369-3-68-62××8-6-2×××5-23×4-317-166-64-3-15-2-3初始调运的运费为326923341265110作业：用西北角法求解下列问题的调运方案产地销地供应B1B2B3B4A13113107x11x12x13x14A219284x21x22x23x24A3741059x31x32x33x34需求365620最小元素法例设有A1,A2和A3的产品需要运到B1,B2,B3和B4四个销地，求如何调运使总运费最少？产地销地供应B1B2B3B4A1291079x11x12x13x14A213425x21x22x23x24A384257x31x32x33x34需求384621第一步，做产销空格表，并将空格对应的产销地运费填在空格的右上角;第二步，在表中找出运价最小的一个，对比产地和销地;(1)如果产大于销，则在该格中填上销量;(2)如果销大于产，则在该格中填上产量;第三步，在剩下的表中，反复进行第二步.下面给出具体计算过程:产地销地供应B1B2B3B4A1291079A213425A384257需求3846213××5-324×××7-43×45初始总运费为594731223442100作业：用最小元素法求解下列问题的调运方案产地销地供应B1B2B3B4A13113107x11x12x13x14A219284x21x22x23x24A3741059x31x32x33x34需求365620在确定产销关系时，不从最小元素开始，而元素差额法是在最小元素法的基础上改进的.例设有A1,A2和A3的产品需要运到B1,B2,B3和B4四个销地，求如何调运使总运费最少？元素差额法(VAM法)从运输表中各行各列的最小元素和次小元素之间的差额来确定产销关系.产地销地供应B1B2B3B4A1291079x11x12x13x14A213425x21x22x23x24A384257x31x32x33x34需求384621第一步，做产销空格表，并将空格对应的产销地运费填在空格的右上角.第二步，产销空格表上增加一行和一列作为差额行和差额列，填上对应行和对应列的最小元素和次小元素的差额.第四步，重新计算差额并进行分配，直到每一个格上都被填上数字或画×为止.第三步，在差额行和差额列中选取差额最大的一行或一列进行分配，并对该行(列)的最小元素填数，填数规则同最小元素法.初始调运方案为23597125432488B1B2B3B4差额A1291079A213425A384257384621差额5121123××212123××58222×5221×354315作业：用元素差额法求解下列问题的调运方案产地销地供应B1B2B3B4A13113107x11x12x13x14A219284x21x22x23x24A3741059x31x32x33x34需求3656202最优调运方案的判断判断一个调运方案是否是最优方案，实质是判别一个基本可行解是否为最优解.单纯形法中，最优解是根据对应的非基变量的检验数来判断的.运输问题也采用类似的方法.由单纯形法可知，最优解中非基变量一般取0那么运输问题中，哪些是非基变量呢？调运量为零(即×位置)的对应于非基变量！所以只要判别出每个空格的检验数就可以了检验数该如何求？闭回路法和位势法闭回路法由一个空格开始，沿水平方向或垂直方向前进.遇到一个有数字的格子时，则可以按前进方向的垂直方向转向前进，经过若干次后,必然回到原出发点.这样就形成了一条由水平线段和垂直线段组成的封闭折线，称为闭回路法.拐角：填有数字，并且前进方向改变的格子.检验数求法：从空格开始沿闭回路前进，空格的单位运费取正，第一个转角运费取负，第二个取正,…,然后将这些运费加起来，即空格的检验数.例求下表A2B2的一个闭回路和检验数产地销地供应B1B2B3B4A1311310743A21928431A374105963需求365620检验数:94510321第三章运输问题第二节表上作业法2最优调运方案的判断位势法如果产销地的个数很多，闭回路法应用起来非常麻烦，对于这种情况，采用位势法:第一步，做产销空格表，并作初始调运方案，表中的数字是相应的单位运价和运量.第二步，在表中增加一行vj和一列ui,使得表中的基变量的单位运价cij刚好是ui和vj的和.第三步，计算空格处的检验数:σij=cij-(ui+vj)例求下表各空格处的检验数产地销地供应B1B2B3B4A1311310743A21928431A374105963需求365620解：产地销地位势B1B2B3B4A131131043A2192831A37410563位势01219-482989-3-2121-11210此方法求出的检验数和闭回路法求的是一致的求得检验数后，就可以判断这个运输方案是否是最优的.由于运输问题的目标函数是极小化问题所以所有的检验数都是非负的时候，最优.如果有检验数为负值，该如何处理？3调整已有的调运方案就是从一个已知方案求出另一个较好的方案.实质上就是从一个基本可行解找出另一个基本可行解，使目标函数下降.具体步骤如下:第一步，选出一个检验数为负的空格(一般选具有最负值的检验数的空格，如果两个空格的检验数一样，则任选一个)，然后做选出空格的闭回路.第二步，从空格处出发，沿闭回路前进，在各奇数次拐角点的调运量中选取一个最小的调运量.第三步，在空格中填上所选的最小调运量，并使所有的奇数次拐角的调运量减去这个最小调运量，偶数次拐角的调运量加上最小调运量.产地销地位势B1B2B3B4A11321131012943A21192-1803819A3107412105-4-36-23位势18291-14+13-11相当于单纯形法的转轴运算.重新计算位势和检验数.产地销地位势B1B2B3B4A131131052A2192831A37410563位势01821-373971-2-20221912所有的检验数均已大于等于零所以此表为最优调运方案，总运费为136453210183585s产地销地需求B1B2B3B4A131131052A2192831A37410563需求204367596所有的检验数均已大于等于零所以此表为最优调运方案，总运费为136453210183585s