線形規劃

單純形法求解比較繁瑣，雖然現在已有多種實用軟體，使用起來仍不方便。因此，對於各種具體問題，又產生了一些較為簡單的演演算法。例如，對運輸模型，有表上作業法，圖上作業法等。這裡我們介紹指派問題的演演算法。

設有n項任務需要n個人去承擔，每人只能承擔一項任務。又設第 i個人完成第j項任務所需成本為 Cij，要決定如何指派任務使總成本為最低。這類問題稱為指派問題。可以將它化為線形規劃問題來解。但是由於問題的特殊性，可以有較為簡單的解法。這種解法的根據是下列引理。

引理：若從係數矩陣（Cij）的某一行（或列）各元素中分別減去同一個數，得到新矩陣（bij），那麼以（bij）為係數矩陣求得的最優解和用原係數矩陣求得的最優解相同。

` 利用這個引理，可使原係數矩陣變換為含有許多零元素而其他元素為正的矩陣而最優解不變。如果我們能在其中找到 n個位於不同行不同列的零元素，設它們位於（1,j2），（2,j2），...，（n,jn），那麼指派第 i個人完成第 ji項任務，其成本為零，當然就得出最優解。