西北角法
从西北角开始得到可行解的方法
西北角法是从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数;然后按行(列)标下一格的数;若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去;如此进行下去,直至得到一个基本可行解的方法。
简介
西北角法是从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数;然后按行(列)标下一格的数;若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去;如此进行下去,直至得到一个基本可行解的方法。
西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则。
举例
从表1中可知,总的产量=总的销量,故产销是平衡的。
第一步:列出运价表和调运物资平衡表。
运用表上作业法时,首先要列出被调运物资的运价表和供需平衡表(简称平衡表),如表1,2所示。
第二步:编制初始调运方案。
首先在表2的西北角方格(即左上角方格,对应变量),尽可能取最小值:
将数值3填入该方格(见表3)。由此可见必须为0,即第一列其他各方格都不能取非零值,划去第一列。在剩下的方格中,找出其西北角方格,
将4填入它所对应方格,第一行饱和,划去该行。再找西北角方格,
将2填入所对应方格,于是第二列饱和,划去该列。继续寻找西北方格为,
将2填入所对应方格,第二行饱和,划去该行。剩下方格的西北角方格为,
将3填入所对应方格,第三列饱和,划去该列。最后剩下方格,取。
这样我们就找到了m+n-1=3+4-1=6个基变量,它们为:
显然它们用折线连接后不形成闭回路。这就是西北角法所找初始基可行解。
利用西北角法找初始基可行解简单可行,但也存在问题。例如在表3中可见,单价高于该行其他各方格,最简单想法是单价小的情况下多运些货物,这样总运费会更小些,最小元素法就改进了西北角法的缺点。
参考资料
最新修订时间:2022-08-25 13:31
目录
概述
简介
举例
参考资料