線形規劃

線形規劃是一種套用廣泛的解最佳化問題的模型，一般使用單純形法求解。單純形法的理論和計算方法都比較繁瑣，我們在這裡只介紹其基本概念。

基本介紹

• 中文名：線形規劃
• 性質：套用廣泛的解最佳化問題的模型
• 一般使用：單純形法求解
• 特點：計算比較繁瑣
• 領域：數學,計算機算法

單純形法的計算

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

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

引理

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

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