西北角法
出自 MBA智库百科(https://wiki.mbalib.com/)
目錄 |
西北角法是從西北角(左上角)格開始,在格內的右下角標上允許取得的最大數;然後按行(列)標下一格的數;若某行(列)的產量(銷量)已滿足,則把該行(列)的其他格划去;如此進行下去,直至得到一個基本可行解的方法[1]。
西北角法的例子[1]
從表1中可知,總的產量=總的銷量,故產銷是平衡的。
第一步:列出運價表和調運物資平衡表。
運用表上作業法時,首先要列出被調運物資的運價表和供需平衡表(簡稱平衡表),如表1,2所示。
第二步:編製初始調運方案。
首先在表2的西北角方格(即左上角方格,對應變數x11),儘可能取最大值:
x11=min{3,7}=3
將數值3填入該方格(見表3)。由此可見x21,x31必須為0,即第一列其他各方格都不能取非零值,划去第一列。在剩下的方格中,找出其西北角方格x12,
x12=min{6,7-3}=4
將4填入它所對應方格,第一行飽和,划去該行。再找西北角方格x22,
x22=min{6-4,4}=2
將2填入x22所對應方格,於是第二列飽和,划去該列。繼續尋找西北方格為x23,
x23=min{5,4-2}=2
將2填入x23所對應方格,第二行飽和,划去該行。剩下方格的西北角方格為x33,
x33=min{5-2,9}=3
將3填入x33所對應方格,第三列飽和,划去該列。最後剩下x34方格,取x34 = 6。
這樣我們就找到了m+n-1=3+5-1=7個基變數,它們為:x11 = 3,x12 = 4,x22 = 2,x23 = 2,x33 = 3,x34 = 6。顯然它們用折線連接後不形成閉迴路。這就是西北角法所找初始基可行解,所對應的目標值為:
2×200+1×250+3×150+1×150+3×250+3×300+4×200=4000
我們找到的初始基可行解可通過各行方格中數值之和是否等於產量,各列方格中數值之和是否等於銷量來簡單驗證。
利用西北角法找初始基可行解簡單可行,但也存在問題。例如在表3中可見c35 = 4,單價高於該行其他各方格,最簡單想法是單價小的情況下多運些貨物,這樣總運費會更小些,最小元素法就改進了西北角法的缺點。
看見了