Tag Archives: 多胞形

線性規劃 (四)：單形法

Posted on 09/27/2013 by ccjou

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

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , | 9 Comments

線性規劃 (三)：最佳基可行解定理

Posted on 08/20/2013 by ccjou

， Continue reading →

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , , | Leave a comment

多胞形

Posted on 05/20/2013 by ccjou

本文的閱讀等級：中級 在最佳化領域，多胞形 (polytope) 是一種應用廣泛的特殊凸集[1]。多胞形可以存在於任何有限維的幾何座標空間，多邊形是二維多胞形，多面體是三維多胞形， 的多胞形稱為 多胞形。淺白地說，多胞形的邊界都是平的。本文討論的多胞形限定為有界閉集，定義如下：若 是屬於 的有限向量集，凸包 稱為一多胞形。因為凸包是凸集，凸包定義的多胞形自然是一有界閉凸集 (見“凸組合、凸包與凸集”)。本文將介紹多胞形的幾何性質，並推導有界閉凸集的一個重要定理，它指引了一條解決線性規劃問題的捷徑。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , | Leave a comment