【複習筆記】最優化方法 – 2. 線性規劃
第二章 線性規劃
本文是本人研究生課程《最優化方法》的複習筆記，主要是總結課件和相關部落格的主要內容用作複習。
2.1 線性規劃的標準型
線性規劃問題的解：
2.2 線性規劃的基本概念
1. （LP）是一個凸規劃
2. 基矩陣
3. 由「基矩陣」發展而來的其他概念
4. 基解
可行解是指滿足條件，基本解是指基矩陣對應的解，兩者同時滿足為基本可行解
2.3 線性規劃解的幾何特徵與規範式
定理 1：基可行解對應的A的列向量線性無關
定理 2：可行解是基可行解 <=>x是可行域的極點
定理 3：LP有可行解則必有基可行解
定理 4：LP如果有最優解，則必有某個基可行解是最優解
判別數的定義：
2.4 單純形法的最優性判斷
1. 定理1：判斷\(x^0\)是LP的一個最優解
2. 定理2：判斷LP無最優解
3. 基可行解的轉換（入基，出基）
4. 在3中轉換後得到的新的目標函數值是下降的
2.5 【必考】單純形法求解線性規劃
做題
2.6 初始基可行解求法：大M法
1. 構造輔助問題\(LP’\)
2. \(LP’\)與\(LP\)的關係（最優解，無可行解，無最優解）
2.7 初始基可行解求法：二階段法
1. 第一階段：求\(LP”\)，然後判斷原\(LP\)問題是否存在可行解
2. 第二階段：根據第一階段得到的基可行解，用單純型法求\(LP\)
2.8 【重點】線性規劃的對偶理論
1. 對偶規劃概念與變形方法
2. 對偶規劃的性質
對合性
自由變數與等式約束的對等關係
3. 對偶理論
4. 最優性條件
