[管理學(xué)]線性規(guī)劃的圖解法與單純形解法(參考版)
2025-01-22 07:42本頁面
【正文】 復(fù)習(xí)舉例 考慮如下的線性規(guī)劃問題： 12121212mi n1240 , 0z x xxxxxxx???? ? ???? ? ?????? 試問：當(dāng)?在什么范圍內(nèi)取值時(shí)，分別有下面的結(jié)論成立？ （ 1 ） 該問題具有無窮多最優(yōu)解； （ 2 ） 該問題是無界的； （ 3 ） 以T( 2 , 3 )為唯一最優(yōu)解。 線性規(guī)劃單純形法的改進(jìn)舉例 第二步迭代，計(jì)算 ?? 111. PB??????????041， 2140?????????????， 21 0 04 1 00 0 1E???????????? 2B的逆陣 112 2 11 0 0 1 0 1 2 1 0 1 24 1 0 0 1 0 4 1 20 0 1 0 0 1 4 0 0 1 4B E B????? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? 非基變量檢驗(yàn)數(shù) ? ? ? ? ? ?2 2 21221 0 1 2 1 00 , 0 2 , 0 , 3 4 1 2 0 0 2 , 1 40 0 1 4 0 1N N BBNCC???? ? ? ?? ? ? ?? ? ? ? ? ? ?? ? ? ?? ? ? ?? ? ? ? 對(duì)應(yīng)的換入變量5x，計(jì)算 111() 83m in ( ) 0 m in , , 42 1 4()ikik iBbBPBP?????? ????? ? ? ? ? ??? ???????? 對(duì)應(yīng)的換出變量4x ，由此得到新的基 ? ?3 1 5 2,B P P P?， ? ?3 1 5 2,B x x xX ? 線性規(guī)劃單純形法的改進(jìn)舉例 第三步迭代，計(jì)算 12512214BP?????????????， 3141218?????????????， 31 1 4 00 1 2 00 1 8 1E????????? ???，113 3 21 1 4 0 1 0 1 2 0 1 4 040 1 2 0 1 2 2 1 2 10 1 8 1 0 0 1 4 1 2 1 8 0B E B???? ? ? ? ? ?? ? ? ? ? ??? ? ? ?? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ? 非基變量檢驗(yàn)數(shù) 所以，可得最優(yōu)解 1*15320 1 4 0 8 42 1 2 1 16 41 2 1 8 0 12 2xX x B bx??? ? ? ? ? ? ??? ? ? ? ? ? ?? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ??? ? ? ? ? ? ?3 3 31330 1 / 4 0 1 00 0 2 0 3 2 1 / 2 1 0 1 3 / 2 1 / 81 / 2 1 / 8 0 0 0N N BC C B N??? ? ? ?? ? ? ?? ? ? ? ? ? ? ?? ? ? ?? ? ? ??? ? ? ?復(fù)習(xí)舉例 有兩個(gè)變量的線性規(guī)劃問題 ?????????????0,1m a x2121211xxxxaxxxz （ 1 ） 證明本題當(dāng)且僅當(dāng)1?a 時(shí)為可行。 線性規(guī)劃單純形法的改進(jìn)舉例 例 用改進(jìn)的單純法形求解 1 2 3 4 51 2 31425m a x 2 3 0 0 0284 164 120 ( 1 , 5 )iz x x x x xx x xxxxxxi? ? ? ? ?? ? ?????????????≥ 解 1 2 3 4 51 2 1 0 04 0 0 1 00 4 0 0 1x x x x xA???????????， ???????????12168b 線性規(guī)劃單純形法的改進(jìn)舉例 0 3 , 4 51 0 0, 0 1 00 0 1B P P P?????????? ??????， ? ?0 T345,B x x xX ? ? ?0 0 , 0 , 0BC ?， 0T1 , 2N xxX ??? ??， ? ?0 2 , 3NC ? 計(jì)算非基變量檢驗(yàn)數(shù)? ?0 0 0 1 0 2 , 3N N B BNCC? ?? ? ?，21 32?? ? ? ?，由此確定2x為換入變量，則 ???????????4022P，111() 8 1 2m in ( ) 0 m in , , 324()ikik iBbBPBP???????? ??? ? ? ? ??? ???????? 對(duì)應(yīng)換出變量為 x5，于是得到新的基1 3 , 4 2,B P P P??? ??，? ?1 T345,B x x xX ?，? ?1 0 , 0 , 3BC ?， ? ? ? ?11 1 5, , 2 , 0NN P P C??。 很顯然， ? ?11 2 1 2, , , , , , , ,k m mE e e B P e e e e??? ??? 令 121kkkmkaaBPa????????????????，211 0 00 1 00 0 1lkkmkaaEa???????????????? 線性規(guī)劃單純形法的改進(jìn) 考慮 ( E 1 I ) → ( I E ) ： 121 0 0 1 0 0 00 1 0 0 1 0 00 0 0 0 0 1 00 0 0 10 0 1kklklkaaaa??????????????????? ? 進(jìn)行初等變換： 121 0 01 0 0 00 1 00 1 0 00 0 1 0 0 0 1 00 0 0 1 0 0 1k lkk lklkmk lkaaaaaaa??????????????????????? 線性規(guī)劃單純形法的改進(jìn) 令 121k lkk lklkmk lkaaaaaaa???????????? ????????????? 從而有 ? ?1 2 1 1, , , , , , ,l l mE e e e e e????。 （ 2 ）矩陣求逆 用單純形法求解過程的關(guān)鍵性計(jì)算是對(duì)基陣的求逆，換一個(gè)基后，還要對(duì)新矩陣求逆，新舊矩陣僅僅一列之差，它的求逆有沒有更方便的方法？ 如何根據(jù)1B和換入變量kx的系數(shù)向量kP來計(jì)算出11B?，而不直接求11B?？ 線性規(guī)劃單純形法的改進(jìn) 考慮如下的矩陣運(yùn)算關(guān)系： ? ?1112111 2 1 1, , , , , , , ,kl m kl m kB P Ie e e e B P BEe e B P e e B????????一 次 迭 代二 次 迭 代 假定111B E B???, ? ?1kke E B P??。 線性規(guī)劃單純形法的改進(jìn) 根據(jù)基于矩陣描述單純形法求解線性規(guī)劃問題的一般計(jì)算步驟為，實(shí)際上可對(duì)單純形法作兩個(gè)方面的改進(jìn)： （ 1 ）11()BBC B A C B A?? ?或11( ) ( )B j B jC B P C B P?? ? 前者是單純形表格用的方法。 如：勃蘭特法； 字典序法； 攝動(dòng)法。 單純形法計(jì)算可能的循環(huán)現(xiàn)象 ?在求解線性規(guī)劃單純形方法的計(jì)算過程循環(huán)極少出現(xiàn)，但還是可能的。實(shí)際上，該問題的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1