Tag Archives: 線性規劃

本文的閱讀等級：中級 美國數學家丹齊格 (George Dantzig) 於1947年提出第一個有效的線性規劃算法──單形法，或稱單純形法 (simplex method)，被後人譽為線性規劃之父。1946年丹齊格從加州大學柏克萊分校取得博士學位，次年他以數學顧問身分為美國空軍工作，經常他被要求解決一些與規劃相關的問題，譬如，如何配置預算、人力、飛機，及其他資源使達到最佳的成本效益。因為這些問題多少與經濟學有關，丹齊格跑去徵詢經濟學家科普斯曼 (Tjalling Koopmans，1975年諾貝爾經濟學獎得主)。丹齊格設想經濟學家應當早已發展出解線性規劃問題的技術，出乎意料之外，科普斯曼告訴他經濟學家也沒有線性規劃問題的系統化解法。於是在1947年的暑假，丹齊格決定自己著手尋找一個方法[1]。

， Continue reading →

本文的閱讀等級：中級 線性規劃的標準型問題具有下列形式： 其中 是一個 階矩陣， 是 維向量， 是 維向量， 是 維未知向量 (見“線性規劃 (一)：標準型問題”)。如果 無解，線性規劃問題即不成立。因為這個緣故，我們要求 ，即約束等式的數目不多於未知數的數目。如果 有線性相關的列向量 (row vector)，表示系統存在冗餘的約束條件 (可將多餘條件刪除)，譬如，，，或約束條件彼此矛盾 (此時系統無解)，譬如，，。為了避免捲入這些無謂的情況，以下假設 有 個線性獨立的列向量，即 ，且 (若 ，則 有唯一解)。

本文的閱讀等級：中級 線性規劃 (linear programming) 是一種最佳化問題。顧名思義，線性規劃的目標函數 (objective function) 是未知變數的線性函數，約束條件 (constraints) 則是包含未知變數的線性等式或不等式。儘管最佳化目標與約束條件可能因問題而有所不同，所有的線性規劃問題都可以轉換成下列標準型： 其中 ，，，是給定的實數， 是待決定的未知數。我們之所以將問題寫成標準型，主要的原因是為了執行消去法以化簡線性方程組 (消去法不適用於線性不等式)。針對標準型問題，所謂最佳化是指在滿足 (subject to) 給定的線性方程組，以及未知變數必須為非負值的條件下，尋找可使目標函數最小化的未知變數。因為約束等式可乘以 ，為便利分析，我們假設每一 。線性規劃標準型問題可以用矩陣與向量簡明地表達如下： 上式中， 是一 階矩陣， 是一 維向量， 是一 維向量， 是一 維未知向量。不等式 表示 的每一元皆非負值。本文介紹一些典型的線性規劃問題，並說明如何將給定的問題轉換成標準型。