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