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