运筹学-03-2表上作业法教学教材.ppt

《运筹学-03-2表上作业法教学教材.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1制定初始调运方案表上作业法一般分为两个阶段第一阶段，制定初始调运方案;第二阶段，从初始调运方案出发，调整调运方案，逐步获得最优解.第二节表上作业法下面通过例题来介绍几种常用的求运输问题的初始基本可行解的方法左上角法(西北角法)例设有A1,A2和A3的产品需要运到B1,B2,B3和B4四个销地，求如何调运使总运费最少？产地销地供应B1B2B3B4A1291079x11x12x13x14A213425x21x22x23x24A384257x31x32x33x34需求384621这是一个产销平衡问题，西北角法具体步骤第一步，做产销空格表，将空格对应的产销地

2、运费填在空格的右上角.第二步，在表中对左上角进行分配(1)如果产大于销，则在这个方格填上销量,并在表中划去这一列(2)如果销大于产，则在这个方格填上产量,并在表中划去这一行第三步，在剩下的表中，反复进行第二步.产地销地供应B1B2B3B4A1291079A213425A384257需求38462133-39-369-3-68-62××8-6-2×××5-23×4-317-166-64-3-15-2-3初始调运的运费为作业：用西北角法求解下列问题的调运方案产地销地供应B1B2B3B4A13113107x11x12x13x14A219284x21x22x2

3、3x24A3741059x31x32x33x34需求365620最小元素法例设有A1,A2和A3的产品需要运到B1,B2,B3和B4四个销地，求如何调运使总运费最少？产地销地供应B1B2B3B4A1291079x11x12x13x14A213425x21x22x23x24A384257x31x32x33x34需求384621第一步，做产销空格表，并将空格对应的产销地运费填在空格的右上角;第二步，在表中找出运价最小的一个，对比产地和销地;(1)如果产大于销，则在该格中填上销量;(2)如果销大于产，则在该格中填上产量;第三步，在剩下的表中，反复进行第二步.

4、下面给出具体计算过程:产地销地供应B1B2B3B4A1291079A213425A384257需求3846213××5-324×××7-43×45初始总运费为作业：用最小元素法求解下列问题的调运方案产地销地供应B1B2B3B4A13113107x11x12x13x14A219284x21x22x23x24A3741059x31x32x33x34需求365620在确定产销关系时，不从最小元素开始，而元素差额法是在最小元素法的基础上改进的.例设有A1,A2和A3的产品需要运到B1,B2,B3和B4四个销地，求如何调运使总运费最少？元素差额法(VAM法)从运

5、输表中各行各列的最小元素和次小元素之间的差额来确定产销关系.产地销地供应B1B2B3B4A1291079x11x12x13x14A213425x21x22x23x24A384257x31x32x33x34需求384621第一步，做产销空格表，并将空格对应的产销地运费填在空格的右上角.第二步，产销空格表上增加一行和一列作为差额行和差额列，填上对应行和对应列的最小元素和次小元素的差额.第四步，重新计算差额并进行分配，直到每一个格上都被填上数字或画×为止.第三步，在差额行和差额列中选取差额最大的一行或一列进行分配，并对该行(列)的最小元素填数，填数规则同最小

6、元素法.初始调运方案为B1B2B3B4差额A1291079A213425A384257384621差额5121123××212123××58222×5221×354315作业：用元素差额法求解下列问题的调运方案产地销地供应B1B2B3B4A13113107x11x12x13x14A219284x21x22x23x24A3741059x31x32x33x34需求3656202最优调运方案的判断判断一个调运方案是否是最优方案，实质是判别一个基本可行解是否为最优解.单纯形法中，最优解是根据对应的非基变量的检验数来判断的.运输问题也采用类似的方法.由单纯形法可

7、知，最优解中非基变量一般取0那么运输问题中，哪些是非基变量呢？调运量为零(即×位置)的对应于非基变量！所以只要判别出每个空格的检验数就可以了检验数该如何求？闭回路法和位势法闭回路法由一个空格开始，沿水平方向或垂直方向前进.遇到一个有数字的格子时，则可以按前进方向的垂直方向转向前进，经过若干次后,必然回到原出发点.这样就形成了一条由水平线段和垂直线段组成的封闭折线，称为闭回路法.拐角：填有数字，并且前进方向改变的格子.检验数求法：从空格开始沿闭回路前进，空格的单位运费取正，第一个转角运费取负，第二个取正,…,然后将这些运费加起来，即空格的检验数.例求下表

8、A2B2的一个闭回路和检验数产地销地供应B1B2B3B4A1311310743A2192843