2-最優(yōu)化方法-線性規(guī)劃-單純形法(已修改)
2025-08-07 03:52 本頁面
【正文】 實用優(yōu)化方法 線性規(guī)劃：單純形法 線性規(guī)劃 ： 目標函數是線性的，約束條件是 線性等式或不等式 線性規(guī)劃 線性規(guī)劃的歷史 ? 淵源要追溯到 Euler、 Liebnitz、 Lagrange等 ? Gee Dantzig, Von Neumann(Princeton)和Leonid Kantorovich在 1940’s創(chuàng)建了線性規(guī)劃 ? 1947年 , Gee Dantzig發(fā)明了單純形法 ? 1979年 ， L. Khachain找到了求解線性規(guī)劃的一種有效方法 (第一個多項式時間算法 －橢球內點法 ) ? 1984年 ， Narendra Karmarkan發(fā)現了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強有力的競爭者 (投影內點法 ) ? 現在求解大規(guī)模、退化問題最有效的是 原－對偶內點法 ◎ 問題 ：確定食品數量，滿足營養(yǎng)需求，花費最?。? ◎ 變量： n種食品， m種營養(yǎng)成份； －第 j 種食品的單價 －每單位第 j 種食品所含第 i 種營養(yǎng)的數量 －食用第 j 種食品的數量 －為了健康，每天必須食用第 i 種營養(yǎng)的數量 ◎ 模型： 例 1. 食譜問題 例 2. 運輸問題 產銷 平衡 /不平衡 的運輸問題 例 3. 其它應用 ? 數據包絡分析 (data envelope analysis, DEA) ? 網絡流問題 (Network flow) ? 博弈論 (game theory)等 線性規(guī)劃的一般形式 線性規(guī)劃的標準形 (分析、算法 ) 標準形的特征： 極小化 、 等式約束 、 變量非負 向量表示： 一般形式 標準形 轉化 稱 松弛 (slack)/盈余 (surplus)變量； 自由 變量 例 5. 化成標準形 等價表示為 定義： 給定含有 n個變量， m個方程的線性方程組 Ax=b，設 B是由 A 的列組成的任一非奇異 m m子陣，則如果置 x的所有與 B無關的 nm個分量為零后，所得方程組的解是Ax=b關于基 B的 基本解 (basic solution) ，稱 x中與基 B對應的分量為 基變量 (basic variables) 退化基本解： 基本解中如果有一個或多個基變量的值為零 基本解與基變量 其中 滿秩假定： mn矩陣 A滿足 mn，且 A的行向量線性無關 ? 在滿秩假定下，方程組 Ax=b總有解，且至少有一個基本 解 基本可行解 定義 稱 的非負基本解是 標準形 的 基本可行解 (basic feasible solution)； 約束系統(tǒng) 線性規(guī)劃的基本定理 i) 若標準型有可行解，則 必有 基本可行解； ii) 若標準型有最優(yōu)解，則 必有 最優(yōu) 基本可行解。 考慮線性規(guī)劃標準形，其中 A是秩為 m的 m n階 矩陣，則以下結論成立： 基本可行解的個數 不超過 與凸性的關系 線性規(guī)劃的基本定理 (標準形 ) 基本可行解 線性方程組的基本性質 代數理論 (與 表述形式有關 )
公司管理相關推薦
鄂ICP備17016276號-1