2-最優(yōu)化方法-線性規(guī)劃-單純形法(參考版)
2024-08-06 03:52本頁(yè)面
【正文】 如果 停；得最優(yōu)解 . 步 0 給定 BFS及對(duì)應(yīng)的 B1。實(shí)用優(yōu)化方法 線性規(guī)劃：?jiǎn)渭冃畏? 線性規(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ī)劃的一種有效方法 (第一個(gè)多項(xiàng)式時(shí)間算法 －橢球內(nèi)點(diǎn)法 ) ? 1984年 ， Narendra Karmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)有力的競(jìng)爭(zhēng)者 (投影內(nèi)點(diǎn)法 ) ? 現(xiàn)在求解大規(guī)模、退化問(wèn)題最有效的是 原－對(duì)偶內(nèi)點(diǎn)法 ◎ 問(wèn)題 ：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最小？ ◎ 變量： n種食品， m種營(yíng)養(yǎng)成份； －第 j 種食品的單價(jià) －每單位第 j 種食品所含第 i 種營(yíng)養(yǎng)的數(shù)量 －食用第 j 種食品的數(shù)量 －為了健康，每天必須食用第 i 種營(yíng)養(yǎng)的數(shù)量 ◎ 模型： 例 1. 食譜問(wèn)題 例 2. 運(yùn)輸問(wèn)題 產(chǎn)銷 平衡 /不平衡 的運(yùn)輸問(wèn)題 例 3. 其它應(yīng)用 ? 數(shù)據(jù)包絡(luò)分析 (data envelope analysis, DEA) ? 網(wǎng)絡(luò)流問(wèn)題 (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)形 等價(jià)表示為 定義： 給定含有 n個(gè)變量， m個(gè)方程的線性方程組 Ax=b，設(shè) B是由 A 的列組成的任一非奇異 m m子陣，則如果置 x的所有與 B無(wú)關(guān)的 nm個(gè)分量為零后，所得方程組的解是Ax=b關(guān)于基 B的 基本解 (basic solution) ，稱 x中與基 B對(duì)應(yīng)的分量為 基變量 (basic variables) 退化基本解： 基本解中如果有一個(gè)或多個(gè)基變量的值為零 基本解與基變量 其中 滿秩假定： mn矩陣 A滿足 mn，且 A的行向量線性無(wú)關(guān) ? 在滿秩假定下，方程組 Ax=b總有解，且至少有一個(gè)基本 解 基本可行解 定義 稱 的非負(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é)論成立： 基本可行解的個(gè)數(shù) 不超過(guò) 與凸性的關(guān)系 線性規(guī)劃的基本定理 (標(biāo)準(zhǔn)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1