西北角法

更新时间:2022-08-25 13:31

西北角法是从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数;然后按行(列)标下一格的数;若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去;如此进行下去,直至得到一个基本可行解的方法。

简介

西北角法是从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数;然后按行(列)标下一格的数;若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去;如此进行下去,直至得到一个基本可行解的方法。

西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则。

举例

从表1中可知,总的产量=总的销量,故产销是平衡的。

第一步:列出运价表和调运物资平衡表。

运用表上作业法时,首先要列出被调运物资的运价表和供需平衡表(简称平衡表),如表1,2所示。

第二步:编制初始调运方案。

首先在表2的西北角方格(即左上角方格,对应变量),尽可能取最小值:

将数值3填入该方格(见表3)。由此可见必须为0,即第一列其他各方格都不能取非零值,划去第一列。在剩下的方格中,找出其西北角方格,

将4填入它所对应方格,第一行饱和,划去该行。再找西北角方格,

将2填入所对应方格,于是第二列饱和,划去该列。继续寻找西北方格为,

将2填入所对应方格,第二行饱和,划去该行。剩下方格的西北角方格为,

将3填入所对应方格,第三列饱和,划去该列。最后剩下方格,取。

这样我们就找到了m+n-1=3+4-1=6个基变量,它们为:

显然它们用折线连接后不形成闭回路。这就是西北角法所找初始基可行解。

利用西北角法找初始基可行解简单可行,但也存在问题。例如在表3中可见,单价高于该行其他各方格,最简单想法是单价小的情况下多运些货物,这样总运费会更小些,最小元素法就改进了西北角法的缺点。

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}