2-最優(yōu)化方法-線性規(guī)劃-單純形法(完整版)
【正文】 環(huán) (cycling) ◎ 退化問題 ⊙ 單純形法 可能出現 循環(huán)！ ⊙ 實際中經常碰到退化問題，但 很少出現 循環(huán) ⊙ 避免出現循環(huán)的措施： 攝動法、 Bland法則、字典序法 基本可行解是退化 的當且僅當單純形表最后一列有一個或者多個零！ 一次轉軸是退化 的當且僅當目標函數沒有發(fā)生變化！ 最小系數規(guī)則 ： ◎ 進基變量：最小系數規(guī)則 ◎ 出基變量：最小指標規(guī)則 循環(huán)的例子 Beale 循環(huán) 定義：從某張單純形表開始返回到該單純形表的一串轉軸 轉軸規(guī)則：選取進基變量和離基變量的明確規(guī)則 循環(huán)！ 注： 循環(huán)轉軸序列中所有 BFS都是退化的！是同一個 BFS！ 第七張單純形表 避免循環(huán)的方法 ⊙ 如果有多個費用系數是負的，選取下標最小的相對費用系數對應的變量為進基變量 ◎ 攝動法 (Charnes， 1952年 ) ◎ Bland法則 (Bland, 1977)－最小指標法則 ◎ 字典序法 (Dantzig, Orden和 Wolfe， 1954年 ) ⊙ 如果最小正比值在多個指標處取得，取下標最小者對應的變量為進基變量 美好愿望：構造某種 永遠不會產生循環(huán) 的轉軸規(guī)則！ 前四張 單純形表相同！ 利用 Bland法則 作為轉軸規(guī)則求解 Beale的例子！ 最后一張單純形表 /最優(yōu)單純形表 單純形法的收斂性 ◎ 非退化 線性規(guī)劃：任一基本可行解非退化 對 非退化 線性規(guī)劃，從任一基本可行解出發(fā)，利用單純形法可在 有限步內 得到最優(yōu)解或判斷問題無界 . ◎ 收斂性定理： 5. 兩階段法 如何啟動單純形法－ 人工變量 ◎ 目標 判斷 Ax=b, x≥0 是否有界； 有解時找一個基本可行解； ⊙ 給有需要的行 乘以 1，使得 b≥0 ◎ 方法 (x, y)=(0, b)是基本可行解！ 故可以 (0,b)為初始 BFS，利用單純形法求解輔助問題 假設最后得最優(yōu)解 (x, y)、最優(yōu)值 z* 和最優(yōu)基 B ⊙ 構造輔助問題 人工變量 得到原問題的基本可行解 ◎ z* 0， 無 可行解！ ◎ z*= 0， 有 可行解！ ⊙ 基變量中 無 人工變量 →x 是 BFS， B 是對應的基 ⊙ 基變量中 有 人工變量 →驅趕人工變量出基 假設第 i 個基變量是人工變量，且當前單純形表 第 i 行的前 n個數據是 第 i 個約束冗余； 刪除單純形表的第 i 行數據 以 任一非零元 為轉軸元轉軸 得輔助問題的一個新最優(yōu) BFS，且基變量中少 1個人工變量！ 例 1. 給出下面系統(tǒng)的一個基本可行解，或者說明其無解 引入 人工 變量 目標 ： 輔助問題的初始表格 ！ BFS 第一張 單純形表 第二張 單純形表 注意基變量整列包括末行 z在內除了基變量其他元素都是 0 輔助問題的 最優(yōu)值是 0. 原問題的 BFS： 兩階段法－ 可求任一 線性規(guī)劃問題 ◎ 第 I階段：啟動單純形法 →構造、求解輔助問題 →
公司管理相關推薦
鄂ICP備17016276號-1