第二节
表上作业法 (1) (2)
(3) (4) (5)
2.西北角法
西北角法的基本思想是给产销平衡表左上角的变量分配运输量,以确定产销关系,依此类推,一直到给出初始可行方案为止。
求解步骤如下:
1°先决定产销平衡表左上角变量
的值。令这个变量取尽可能大的值,即
,在这个变量对应的数字格填上变量所取的值。
2°若 ,则在第L行空格处打“×”,这些空格不再赋值;若 ,则在第K列空格处打“×”,这些空格不再赋值;若 = ,则在行的空格处打“×”后,就不能在列的空格处打“×”,反之,若在列的空格处打“×”,就不在行空格处打“×”。
3°对表上没有打“×”的地方重复1°,2°步,直到所有格子都有标记止。
可以证明,用西北角法确定的初始方案是运输问题的一个初始基可行解,它也恰好包含m+n-1个数字格。
用西北角法确定例1的初始调运方案过程如下:
表3-3
|