2-最優(yōu)化方法-線性規(guī)劃-單純形法-wenkub.com
2024-08-02 03:52 本頁(yè)面
【正文】 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中 A是秩為 m的 m n階 矩陣，則以下結(jié)論成立： 基本可行解的個(gè)數(shù) 不超過(guò) 與凸性的關(guān)系 線性規(guī)劃的基本定理 (標(biāo)準(zhǔn)形 ) 基本可行解 線性方程組的基本性質(zhì) 代數(shù)理論 (與 表述形式有關(guān) ) 設(shè)計(jì)算法 極點(diǎn) 凸集理論 幾何理論 (與表述形式 無(wú)關(guān) ) 直觀理解 凸性 (凸集及性質(zhì) ) 幾何解釋 ：連接集合中任兩點(diǎn)的線段仍含在該集合中 性質(zhì) 定義 是凸集 (convex set)，如果對(duì) S中任意 兩 點(diǎn) x , y 和 (0,1)中的任一數(shù) 滿足 ?一些重要的凸集 有限個(gè)閉半空間的交集 多面集 (polyhedral convex set): 推廣 平面上：多邊形 注： 任一線性規(guī)劃的可行集是 多面集 ！ 超平面 (hyperplane): 正 /負(fù)閉半空間： 極點(diǎn) 幾何上 ：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開(kāi)線段上的點(diǎn) 定義 稱凸集 C中的點(diǎn) x 是 C的極點(diǎn)，如果存在 C 中的點(diǎn) y, z 和某 ，有 則必有 y=z. 極點(diǎn)與基本可行解的等價(jià)性定理 推論： i) 若 K非空，則至少有一個(gè)極點(diǎn) . ii) 若線性規(guī)劃有最優(yōu)解，則必有一個(gè)極點(diǎn)是最優(yōu)解 . iii) Ax=b對(duì)應(yīng)的約束集 K最多有有限個(gè)極點(diǎn) . 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中 A是秩為 m的 m n 矩陣，令 則 x是 K 的極點(diǎn)， 當(dāng)且僅當(dāng) x是線性規(guī)劃的基本可行解 . （線性規(guī)劃基本定理的幾何形式） 例 2. K 有 2個(gè)極點(diǎn) 有 3個(gè)基本解， 2個(gè) 可行 K 有 3個(gè)極點(diǎn) 有 3個(gè)基本解， 均可行 例 1. 例 3. Subject to 5個(gè)極點(diǎn) －極點(diǎn) 線性規(guī)劃解的 幾何特征 唯一 解 (頂點(diǎn) )！ 線性規(guī)劃解的 幾何特征 ? 無(wú)界 ：沒(méi)有有限最優(yōu)解 ? 不可行 ：沒(méi)有可行解 無(wú)解 可行集： 多邊形 (二維 ) → 多邊集 (高維空間 ) 給出 有效的代數(shù)刻畫(huà) 和 嚴(yán)謹(jǐn)?shù)膸缀蚊枋?，從理論上證實(shí)上述幾何特征，并 尋求有效算法 ? 有解： 唯一解 /多個(gè)解 (整條邊、面、甚至整個(gè)可行集 ) 有頂點(diǎn)解 頂點(diǎn) 一條邊 無(wú) (下 )界 線性規(guī)劃問(wèn)題解的幾種情況 單純形法簡(jiǎn)介 ? 適用形式： 標(biāo)準(zhǔn)形 (基本可行解 =極點(diǎn) ) ? 理論基礎(chǔ)： 線性規(guī)劃的 基本定理 ！ ? 基本思想： 從約束集的 某個(gè)極點(diǎn) /BFS開(kāi)始，依次移動(dòng)到 相鄰極點(diǎn) /BFS，直到找出最優(yōu)解，或判斷問(wèn)題無(wú)界 . ? 初始化： 如何找到一個(gè) BFS？ ? 判斷準(zhǔn)則： 何時(shí)最優(yōu)？何時(shí)無(wú)界？ ? 迭代規(guī)則： 如何從一個(gè)極點(diǎn) /BFS迭代到相鄰極點(diǎn) /BFS？ 1. 轉(zhuǎn)軸 (基本解 →相鄰 基本解 ) 滿秩假定： A是行滿秩的 規(guī)范形 (canonical form) 基變量 基本解 非基變量 等價(jià)變形
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1