2-最優(yōu)化方法-線性規(guī)劃-單純形法-文庫吧
2025-07-11 03:52 本頁面
【正文】 設(shè)計(jì)算法 極點(diǎn) 凸集理論 幾何理論 (與表述形式 無關(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)的開線段上的點(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ī)劃解的 幾何特征 ? 無界 ：沒有有限最優(yōu)解 ? 不可行 ：沒有可行解 無解 可行集： 多邊形 (二維 ) → 多邊集 (高維空間 ) 給出 有效的代數(shù)刻畫 和 嚴(yán)謹(jǐn)?shù)膸缀蚊枋?，從理論上證實(shí)上述幾何特征，并 尋求有效算法 ? 有解： 唯一解 /多個(gè)解 (整條邊、面、甚至整個(gè)可行集 ) 有頂點(diǎn)解 頂點(diǎn) 一條邊 無 (下 )界 線性規(guī)劃問題解的幾種情況 單純形法簡(jiǎn)介 ? 適用形式： 標(biāo)準(zhǔn)形 (基本可行解 =極點(diǎn) ) ? 理論基礎(chǔ)： 線性規(guī)劃的 基本定理 ！ ? 基本思想： 從約束集的 某個(gè)極點(diǎn) /BFS開始，依次移動(dòng)到 相鄰極點(diǎn) /BFS，直到找出最優(yōu)解，或判斷問題無界 . ? 初始化： 如何找到一個(gè) BFS？ ? 判斷準(zhǔn)則： 何時(shí)最優(yōu)？何時(shí)無界？ ? 迭代規(guī)則： 如何從一個(gè)極點(diǎn) /BFS迭代到相鄰極點(diǎn) /BFS？ 1. 轉(zhuǎn)軸 (基本解 →相鄰 基本解 ) 滿秩假定： A是行滿秩的 規(guī)范形 (canonical form) 基變量 基本解 非基變量 等價(jià)變形 不妨設(shè) 線性無關(guān) 一般地 ： 次序可以打亂！ 只要有 m個(gè)單位列 規(guī)范形的轉(zhuǎn)換問題 ⊙ 什么時(shí)候可以替換？ ⊙ 替換后 新 規(guī)范形 是什么？ ◎ 替換問題
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1