運(yùn)籌學(xué)第一章14大m法和兩階段法-wenkub
2023-05-21 15:18:23 本頁(yè)面
【正文】 約束方程的右邊常數(shù)）值正好就是基變量的取值。 ???? ???用非基變量表示目標(biāo)函數(shù)的表達(dá)式： ????njjj xZZ10 ????????miijinjjjj acczc139。239。239。 （ 2） 出基變量的確定 —— 按最小比值原則確定出基變量 ， 為的是保持解的可行性 ； 出基變量所在的行稱為 主元行 。 引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變 量，使約束條件化為等式， 并且約束方程組的 系數(shù)陣中有一個(gè)單位陣。 利用矩陣的 初等行變換 把 主元列變成單位向量，主元素變?yōu)?1， 進(jìn)基變量對(duì)應(yīng)的檢驗(yàn)數(shù)變成 0，從而得到一張新的單純形表，返回第二步。 處理人工變量的方法： （ 1） 大 M法 —— 在約束條件中人為地加入非負(fù)的人工變量 ， 以便使它們對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣 。 輔助線性規(guī)劃的結(jié)構(gòu)：目標(biāo)函數(shù) W為所有人工變量之和，目標(biāo)要求是使目標(biāo)函數(shù)極小化，約束條件與原線性規(guī)劃相同。m a x654321643215432165xxxxxxxxxxxxxxxxtsxxw。 （ 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)解 。 對(duì)于主元列的 0元素或負(fù)元素是否也要計(jì)算比值 ？ （ 此時(shí)解的可行性自然滿足 ， 不必計(jì)算；如果主元列元素全部為 0元素或負(fù)元素 ， 則最小比值失效 ， 線性規(guī)劃無 “ 有限最優(yōu)解 ” ） 出現(xiàn)若干個(gè)相同的最小比值怎麼辦 ？ （ 說明出現(xiàn)了退化的基本可行解 ， 即非 0分量的個(gè)數(shù)小于約束方程的個(gè)數(shù) 。 （ 2） 類型二：目標(biāo)要求是 “ Max”， 約束條件是 “ =”類型 —— 左邊引入非負(fù)的人工變量 ， 并將引入的人工變量作為初始基變量 ， 則初始可行基是一個(gè)單位陣 ，然后用大 M法或兩階段法求解 。 確定是停止迭代還是轉(zhuǎn)入基變換？ 選擇（最大）
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1