2-最優(yōu)化方法-線性規(guī)劃-單純形法-預(yù)覽頁(yè)
【正文】 問(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) 基本可行解。計(jì)算 核心 計(jì)算： B1 涉及 到的計(jì)算： ， 停， 問(wèn)題 無(wú)界 ；否則，選 p 滿足 步 4 更新 B1, B1b和 ，返步 1. 基的轉(zhuǎn)換定理 左乘 該矩陣等價(jià)于對(duì)矩陣進(jìn)行 初等行變換 ！ 定理 不妨設(shè) B= . 則 aq 進(jìn)基，ap出基后所得新基 的逆 這里 ei 表示 n 維單位向量，向量 v 定義 為 相關(guān)數(shù)據(jù)的更新－ 初等行變換 設(shè) 轉(zhuǎn)軸元 是 ，即 aq 出基， ap進(jìn)基 以 為轉(zhuǎn)軸元， 轉(zhuǎn)軸后 即得新基對(duì)應(yīng)的數(shù)據(jù)！ 例 1 a2進(jìn)基 ，計(jì)算 y2. 計(jì)算表格如下： 計(jì)算 a1進(jìn)基 ，計(jì)算 y1. 得如下表格： 最優(yōu)值： 最優(yōu)解： 利用兩階段單純形過(guò)程求解 1 2 3 41 2 3 41 2 3 41 2 3 4m in 3 3. 2 0 2 2 3 3 9 2 6 0ix x x xs t x x x xx x x xx x x xx? ? ? ?? ? ? ?? ? ? ?? ? ? ??
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1