運(yùn)籌學(xué)第一章14大m法和兩階段法-資料下載頁
2025-05-10 15:18本頁面
【正文】 （ 說明出現(xiàn)了退化的基本可行解 ， 即非 0分量的個數(shù)小于約束方程的個數(shù) 。 按照 “ 攝動原理 ”所得的規(guī)則 ， 從相同比值對應(yīng)的基變量中選下標(biāo)最大的基變量作為換出變量可以避免出現(xiàn)“ 死循環(huán) ” 現(xiàn)象 ） 選擇進(jìn)基變量時 ， 同時有若干個正檢驗(yàn)數(shù) ， 怎麼選 ？ （ 最大正檢驗(yàn)數(shù)或從左至右第 1個出現(xiàn)的正檢驗(yàn)數(shù)所對應(yīng)的非基變量進(jìn)基 ） （ 2） 兩階段法 第一階段：建立輔助線性規(guī)劃并求解 ，以判斷原線性規(guī)劃是否存在基本可行解 。 輔助線性規(guī)劃的結(jié)構(gòu)：目標(biāo)函數(shù) W為所有人工變量之和，目標(biāo)要求是使目標(biāo)函數(shù)極小化，約束條件與原線性規(guī)劃相同。 求解結(jié)果 ① W最優(yōu)值 =0—— 即所有人工變量取值全為 0（ 為什麼 ？ ） ， 均為非基變量 ， 最優(yōu)解是原線性規(guī)劃的一個基本可行解 ， 轉(zhuǎn)入第二階段； ② W最優(yōu)值 =0—— 但人工變量中有等于 0的基變量 ， 構(gòu)成退化的基本可行解 ， 可以轉(zhuǎn)化為情況 ① ；如何轉(zhuǎn)化 ？ 選一個不是人工變量的非基變量進(jìn)基 ， 把在基中的人工變量替換出來 ③ W最優(yōu)值 0—— 至少有一個人工變量取值0,說明基變量中至少有 1個人工變量 ,表明原問題沒有可行解 ,討論結(jié)束 。 （ 1） ? ? ? ? ? ? ? … . . 2 1 t s x x x MinZ m n n n … … … ? ? ? ? ? ? ? ? . 2 1 t s x x x MaxZ m n n n （ 2） … … … … 試比較 ② （ 1）式目標(biāo)要求改為極大化（或（ 2）式目標(biāo)要求改為極小化）行不行？ 第二階段： 將第一階段的最優(yōu)解作為初始可行解 ，目標(biāo)函數(shù)換成原問題的目標(biāo)函數(shù) ， 進(jìn)行單純形迭代 ， 求出最優(yōu)解 。 建立輔助線性規(guī)劃問題得： ????????????????0,1023421085..m i n43214321432165xxxxxxxxxxxxtsxxW化成標(biāo)準(zhǔn)型，整理得： ???????????????????0,,1023421085..39。m a x654321643215432165xxxxxxxxxxxxxxxxtsxxw
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1