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

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

2、,第三步，在剩下的表中，反复进行第二步,3,3-3,9-3,6,9-3-6,8-6,2,8-6-2,5-2,3,4-3,1,7-1,6,6-6,4-3-1,5-2-3,初始调运的运费为,作业： 用西北角法求解下列问题的调运方案,最小元素法,例 设有A1, A2和A3的产品需要运到B1, B2, B3和B4四个销地，求如何调运使总运费最少,第一步，做产销空格表，并将空格对应的产销地运费填在空格的右上角,第二步，在表中找出运价最小的一个，对比产地和销地,1) 如果产大于销，则在该格中填上销量,2) 如果销大于产，则在该格中填上产量,第三步，在剩下的表中，反复进行第二步,下面给出具体计算过程,3,5

3、-3,2,4,7-4,3,4,5,初始总运费为,作业： 用最小元素法求解下列问题的调运方案,在确定产销关系时，不从最小元素开始，而,元素差额法是在最小元素法的基础上改进的,例 设有A1, A2和A3的产品需要运到B1, B2, B3和B4四个销地，求如何调运使总运费最少,元素差额法(VAM法,从运输表中各行各列的最小元素和次小元素,之间的差额来确定产销关系,第一步，做产销空格表，并将空格对应的产销地运费填在空格的右上角,第二步，产销空格表上增加一行和一列作为差额行和差额列，填上对应行和对应列的最小元素和次小元素的差额,第四步，重新计算差额并进行分配，直到每一个格上都被填上数字或画为止,第三步，

4、在差额行和差额列中选取差额最大的一行或一列进行分配，并对该行(列)的最小元素填数，填数规则同最小元素法,初始调运方案为,5,1,2,1,1,2,3,2,1,2,1,2,3,5,8,2,2,2,5,2,2,1,3,5,4,3,1,5,作业： 用元素差额法求解下列问题的调运方案,2 最优调运方案的判断,判断一个调运方案是否是最优方案，实质是判别一个基本可行解是否为最优解,单纯形法中，最优解是根据对应的非基变量的检验数来判断的. 运输问题也采用类似的方法,由单纯形法可知，最优解中非基变量一般取0,那么运输问题中，哪些是非基变量呢,调运量为零(即位置)的对应于非基变量,所以只要判别出每个空格的检验数就

5、可以了,检验数该如何求,闭回路法和位势法,闭回路法,由一个空格开始，沿水平方向或垂直方向前进. 遇到一个有数字的格子时，则可以按前进方向的垂直方向转向前进，经过若干次后,必然回到原出发点,这样就形成了一条由水平线段和垂直线段组成的封闭折线，称为闭回路法,拐角：填有数字，并且前进方向改变的格子,检验数求法：从空格开始沿闭回路前进，空格的单位运费取正，第一个转角运费取负，第二个取正, , 然后将这些运费加起来，即空格的检验数,例 求下表A2B2的一个闭回路和检验数,检验数,第三章 运输问题,第二节 表上作业法,2 最优调运方案的判断,位势法,如果产销地的个数很多，闭回路法应用起来非常麻烦，对于这种

6、情况，采用位势法,第一步，做产销空格表，并作初始调运方案，表中的数字是相应的单位运价和运量,第二步，在表中增加一行vj和一列ui , 使得表中的基变量的单位运价cij刚好是ui和vj的和,第三步，计算空格处的检验数: ij=cij-(ui+vj,例 求下表各空格处的检验数,解,0,1,2,1,9,4,8,此方法求出的检验数和闭回路法求的是一致的,求得检验数后，就可以判断这个运输方案是否是最优的,由于运输问题的目标函数是极小化问题,所以所有的检验数都是非负的时候，最优,如果有检验数为负值，该如何处理,3 调整已有的调运方案,就是从一个已知方案求出另一个较好的方案,实质上就是从一个基本可行解找出另一个基本可行解，使目标函数下降,具体步骤如下,第一步，选出一个检验数为负的空格(一般选具有最负值的检验数的空格，如果两个空格的检验数一样，则任选一个)，然后做选出空格的闭回路,第二步，从空格处出发，沿闭回路前进，在各奇数次拐角点的调运量中选取一个最小的调运量,第三步，在空格中填上所选的最小调运量，并使所有的奇数次拐角的调运量减去这个最小调运量，偶数次拐角的调运量加上最小调运量,1-1,4+1,3-1,1,相当于单纯形法的转轴运算,重新计算位势和检验数,0,1,8,2