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