2-最優(yōu)化方法-線性規(guī)劃-單純形法-免費閱讀
【正文】 實用優(yōu)化方法 線性規(guī)劃：單純形法 線性規(guī)劃 ： 目標(biāo)函數(shù)是線性的，約束條件是 線性等式或不等式 線性規(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ī)劃的一種有效方法 (第一個多項式時間算法 －橢球內(nèi)點法 ) ? 1984年 ， Narendra Karmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強有力的競爭者 (投影內(nèi)點法 ) ? 現(xiàn)在求解大規(guī)模、退化問題最有效的是 原－對偶內(nèi)點法 ◎ 問題 ：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？ ◎ 變量： n種食品， m種營養(yǎng)成份； －第 j 種食品的單價 －每單位第 j 種食品所含第 i 種營養(yǎng)的數(shù)量 －食用第 j 種食品的數(shù)量 －為了健康，每天必須食用第 i 種營養(yǎng)的數(shù)量 ◎ 模型： 例 1. 食譜問題 例 2. 運輸問題 產(chǎn)銷 平衡 /不平衡 的運輸問題 例 3. 其它應(yīng)用 ? 數(shù)據(jù)包絡(luò)分析 (data envelope analysis, DEA) ? 網(wǎng)絡(luò)流問題 (Network flow) ? 博弈論 (game theory)等 線性規(guī)劃的一般形式 線性規(guī)劃的標(biāo)準(zhǔn)形 (分析、算法 ) 標(biāo)準(zhǔn)形的特征： 極小化 、 等式約束 、 變量非負(fù) 向量表示： 一般形式 標(biāo)準(zhǔn)形 轉(zhuǎn)化 稱 松弛 (slack)/盈余 (surplus)變量； 自由 變量 例 5. 化成標(biāo)準(zhǔn)形 等價表示為 定義： 給定含有 n個變量， m個方程的線性方程組 Ax=b，設(shè) B是由 A 的列組成的任一非奇異 m m子陣，則如果置 x的所有與 B無關(guān)的 nm個分量為零后，所得方程組的解是Ax=b關(guān)于基 B的 基本解 (basic solution) ，稱 x中與基 B對應(yīng)的分量為 基變量 (basic variables) 退化基本解： 基本解中如果有一個或多個基變量的值為零 基本解與基變量 其中 滿秩假定： mn矩陣 A滿足 mn，且 A的行向量線性無關(guān) ? 在滿秩假定下，方程組 Ax=b總有解，且至少有一個基本 解 基本可行解 定義 稱 的非負(fù)基本解是 標(biāo)準(zhǔn)形 的 基本可行解 (basic feasible solution)； 約束系統(tǒng) 線性規(guī)劃的基本定理 i) 若標(biāo)準(zhǔn)型有可行解，則 必有 基本可行解； ii) 若標(biāo)準(zhǔn)型有最優(yōu)解，則 必有 最優(yōu) 基本可行解。 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中 A是秩為 m的 m n階 矩陣，則以下結(jié)論成立： 基本可行解的個數(shù) 不超過 與凸性的關(guān)系 線性規(guī)劃的基本定理 (標(biāo)準(zhǔn)形 ) 基本可行解 線性方程組的基本性質(zhì) 代數(shù)理論 (與 表述形式有關(guān) )
公司管理相關(guān)推薦
鄂ICP備17016276號-1