运输问题表上作业法教学PPT课件.ppt

* * 表上作业法 表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。 表上作业法与单纯形法之间的关系： 1、表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解； 2、表上作业法中的“位势法”实质上是在求单纯形表中的检验数； 3、调运方案表中数字格的数实质上就是单纯形法中基变量的值； 4、调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。 确定初始方案 (初始基本可行解) 改进调整 （换基迭代） 否 判定是否 最 优？ 是 结 束 最优方案 表上作业法求解运输问题思路图 表上作业法步骤： 1、找出初始可行解，用最小元素法、西北角法与伏格尔法。 2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步。 3、改进当前的基本可行解(确定换入、换出变量)，用闭合回路法与位势法调整; 4、重复2、3步骤，直到找到最优解为止。 1、分别使用最小元素法和西北角法求出初始方案。 最小元素法的基本思想是“就近供应” ； 西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同 ； 伏格法尔法每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案； 1、找出最小运价，确定供求关系，最大量的供应 ； 2、划掉已满足要求的行或 (和) 列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”； 3、在剩余的运价表中重复1、2两步，直到得到初始基可行解。 最小元素法的基本步骤 B1 B2 B3 B4 产量（ai） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（bj） 3 6 5 6 例： B1 B2 B3 B4 产量（ai） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（bj） 3 6 5 6 从表中找出最小运价“1”， 最小运价所确定的供应关系为（A2，B1），在（A2，B1）的交叉格处填上“3”，并同时划去B1这一列。 3 B1 B2 B3 B4 产量（ai） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（bj） 3 6 5 6 在表的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（A2，B3），即将A2余下的1个单位产品供应给B3，划去A2行的运价，划去A2行表明A2所生产的产品已全部运出。 3 1 B1 B2 B3 B4 产量（ai） A1 3 11 3 4 10 3 7 A2 1 3 9 2 1 8 4 A3 7 4 6 10 5 3 9 销量（bj） 3 6 5 6 这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。 得到最终方案，见下表。 最后在产销平衡表上得到一个调运方案，这一方案的总运费为86个单位。 最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。 在供需关系格（i，j ）处填入一数字，刚好使第 i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。 应注意的问题 为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。 调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用西北角法确定初始调运方案 100 100 100 50 50 2