西北角法

出自 MBA智库百科(https://wiki.mbalib.com/)

　　西北角法是從西北角（左上角）格開始，在格內的右下角標上允許取得的最大數；然後按行（列）標下一格的數；若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格划去；如此進行下去，直至得到一個基本可行解的方法^[1]。

　　從表1中可知，總的產量=總的銷量，故產銷是平衡的。

　　第一步：列出運價表和調運物資平衡表。

　　運用表上作業法時，首先要列出被調運物資的運價表和供需平衡表（簡稱平衡表），如表1，2所示。

　　第二步：編製初始調運方案。

　　首先在表2的西北角方格（即左上角方格，對應變數x₁₁），儘可能取最大值：

　　x₁₁=min{3,7}=3

　　將數值3填入該方格(見表3)。由此可見x₂₁,x₃₁必須為0，即第一列其他各方格都不能取非零值，划去第一列。在剩下的方格中，找出其西北角方格x₁₂，

　　x₁₂=min{6,7-3}=4

　　將4填入它所對應方格，第一行飽和，划去該行。再找西北角方格x₂₂，

　　x₂₂=min{6-4,4}=2

　　將2填入x₂₂所對應方格，於是第二列飽和，划去該列。繼續尋找西北方格為x₂₃，

　　x₂₃=min{5,4-2}=2

　　將2填入x₂3所對應方格，第二行飽和，划去該行。剩下方格的西北角方格為x₃3，

　　x₃3=min{5-2,9}=3

　　將3填入x₃₃所對應方格，第三列飽和，划去該列。最後剩下x₃₄方格，取x₃₄ = 6。

　　這樣我們就找到了m＋n-1＝3＋5-1＝7個基變數，它們為：x₁₁ = 3,x₁₂ = 4,x₂₂ = 2,x₂₃ = 2,x₃₃ = 3,x₃₄ = 6。顯然它們用折線連接後不形成閉迴路。這就是西北角法所找初始基可行解，所對應的目標值為：

　　2×200＋1×250＋3×150＋1×150＋3×250＋3×300＋4×200＝4000

　　我們找到的初始基可行解可通過各行方格中數值之和是否等於產量，各列方格中數值之和是否等於銷量來簡單驗證。

　　利用西北角法找初始基可行解簡單可行，但也存在問題。例如在表3中可見c₃₅ = 4，單價高於該行其他各方格，最簡單想法是單價小的情況下多運些貨物，這樣總運費會更小些，最小元素法就改進了西北角法的缺點。