線性規(guī)劃的圖解法與單純形解法-在線瀏覽
2024-09-11 17:27本頁面
【正文】 23 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 24 【 例 】 用單純形法求解 421 22m i n xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj25 【 解 】 這是一個極小化的線性規(guī)劃問題 ,可以將其化為極大化問題求解 ,也可以直接求解 ,這時判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時得到最優(yōu)解 。目標(biāo)函數(shù)中含有基變量 x4,由第二個約束得到 x4=6+x1－ x2，并代入目標(biāo)函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝26 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,… ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問題 ,注意判斷標(biāo)準(zhǔn) ,選進基變量時 ,應(yīng)選 λj0的變量 xj進基。 由模型可以看出 ， 當(dāng)固定 x1使 x2→+∞且滿足約束條件 ， 還可以用圖解法看出具有無界解 。 使 x3進基 x5出基繼續(xù)迭代 ,得到表 (4)的另一 基本最優(yōu)解 X(1),X(2)是線性規(guī)劃的兩個最優(yōu)解 ， 它的凸組合 20,),0,0,310,38,314)2( ?? ZX T（)10()1( )2()1( ????? ??? XXX 仍是最優(yōu)解 ， 從而原線性規(guī)劃 有多重最優(yōu)解 。 ? 定理 2 有無窮多最優(yōu)解的判別定理 若 ? ? T( 0 )12 , , , , 0 , , 0mX b b b? ? ??為對應(yīng)于基 B 的一個基可行解，對于一切 j = m +1, … , n , 有檢驗數(shù) ? j ≤ 0, 且存在某個非基變量對應(yīng)的檢驗數(shù) ? m + k =0, 則該線性規(guī)劃問題有無窮多個最優(yōu)解。 34 唯一最優(yōu)解的判斷： 最優(yōu)表中所有非基變量的檢驗數(shù) 非零 ,則線規(guī)劃具有唯一最優(yōu)解 。 無界解的判斷 : 某個 λk0且 aik≤０（ i=1， 2,…,m ）則線性規(guī)劃具有無界解 35 單純形法計算的矩陣描述 對標(biāo)準(zhǔn)形式的線性規(guī)劃問題 m a x0z C XAX bX????=≥ 假定存在基 B ，基變量為BX，非基變量為NX，則有 111111()()BNB B N N B N N NB N B NX B b B N Xz C X C X C B b B N X C XC B b C C B N X????????? ? ? ? ?? ? ? 36 單純形法計算的矩陣描述 與前面檢驗數(shù)計算公式對照，可得非基變量檢驗數(shù)計算公式 1N N BC C B N???? 另外，基變（向）量 XB的檢驗數(shù)可寫作 1 0B B BC C B B??? ? ? 所以可得標(biāo)準(zhǔn)形式的線性規(guī)劃模型檢驗數(shù)計算的一般計算公式 1BC C B A???? 37 單純形法計算的矩陣描述 再考慮下列線性規(guī)劃問題 m a x0z C XAX bX????≤≥ 上式加上松弛變量后為 m a x 00 , 0SSSz C X XA X I X bXX???????≥ ≥ 38 單純形法計算的矩陣描述 ? ?m a x z | 0SXCX??? ???? ? ??????????????0,|XXbXXIASS 式中，X S松馳變量，),( 21TxxxX mnnnS ???? ? ， I 為 nm ? 單位矩陣。故當(dāng)基變量為X B 時，新的單純形表就變?yōu)? 基變量 非基變量 BX NX SX XC BB I NB 1? B 1? bB 1? zc jj ? 0 NBCC BN 1?? BC B 1?? 40 單純形法計算的矩陣描述 從上面兩表可看出，當(dāng)?shù)?，基變量為X B，其在初始單純形表中的系數(shù)矩陣為 B ，則有： （ 1 ） 對應(yīng)初始單純形表中的單位陣 I ，迭代后的單純形表中為B 1?； （ 2 ） 初始基變量bX S ? ，迭代后的表中bBX B 1??； （ 3 ） 初始單純形表中，約束系數(shù)矩陣為? ? ? ?INBIA , ?，迭代后的表中約束系數(shù)矩陣為? ? ? ? ? ?BNBIIBNBBBIBAB 1111111 , ??????? ?? （ 4 ） 若初始矩 陣中變量x j的系數(shù)向量為P 39。 j1?? （ 5 ） 當(dāng) B 為最優(yōu)基時，在上表中應(yīng)有 ?????????0011BCABCCBBN 因 X B的檢驗數(shù)可寫作01 ?? ? BBCC BB 所以 有 ?????????0011BCABCCBB BC B 1?稱為單純形乘子，若令BC BY 1?? ，則有0, ?? YCYA成立。求出初始解： ??????????????01bBXXNB （ 2 ） 計算非基變量NX的檢驗數(shù)N? ， NBCC BNN 1???? ，若0?N?已得到最優(yōu)解，停止計算，若還存在Njj ?? ,0? ，轉(zhuǎn)入下一步。 （ 4 ） 根據(jù) ?規(guī)則，求出：? ?11111( ) ( )m in 0( ) ( )ilkiilB b B bBPB P B Pkk??????????? ? ??????? 它對應(yīng)的基變量lX 為換出變量，于是可給出一組新的基變
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1