【正文】 0 4 0 0 1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 30 換入變量 ， 換出變量 ， ２為主元進(jìn)行旋轉(zhuǎn)變換 3x 4x基本可行解 ， Z= 15， X=(0 ,0 ,4 , 0 , 3 ) T1/2 1 1 1/2 0 4 x3 3 1 4 0 2 0 15 Z 5/2 3 0 1/2 1 3 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 1 2 2 1 0 8 x4 1 3 0 4 0 0 1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 8/2 7/1 31 最優(yōu)解 最優(yōu)值 6 1 7X , 0 , , 0 , 055T? ??? ???? 換入變量 ， 換出變量 ， ５ /２為主元進(jìn)行旋轉(zhuǎn)變換 1x 5xN N Bσ = C C N 0? 81Z5? ?4/1/2 1/2 1 1 1/2 0 4 x3 3 1 4 0 2 0 15 Z 3/5/2 5/2 3 0 1/2 1 3 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 0 2/5 1 3/5 1/5 17/5 x3 3 0 26/5 0 9/5 2/5 81/5 Z 1 6/5 0 1/5 2/5 6/5 x1 5 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 32 例 用單純形方法求解線(xiàn)性規(guī)劃問(wèn)題 解：本題的目標(biāo)函數(shù)是求極小化的線(xiàn)性函數(shù)， 可以令 則 這兩個(gè)線(xiàn)性規(guī)劃問(wèn)題具有相同的可行域和最優(yōu)解， 只是目標(biāo)函數(shù)相差一個(gè)符號(hào)而已。 當(dāng)Ｂ =Ｉ時(shí) ， Ｂ 1=Ｉ ， 易知： 1N N Bσ =C C B N1BZ = C B b?N N Bσ =C C N BZ=C b28 可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡(jiǎn)單的表格 ， 即單純形表來(lái)完成： C CB CN θ CB XB b X1 X2 ? 每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值 通過(guò)目標(biāo)函數(shù)值可以觀(guān)察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加 ， 直至求得最優(yōu)目標(biāo)函數(shù)為止 。X = X = ( , 0 , , 0 , 0 )55T* 81Z=52B3B N 4N152 3 1 1 7xC = ( 3 ,5 )x 10 5 5 5 5X = ,X = x ,B = ,N = , ,b =C = ( 2 , 1 ,1 )x 0 1 6 1 2 6x5 5 5 5? ? ? ???? ? ? ??? ????? ? ? ??? ????? ? ? ????? ??? ? ? ???? ? ? ?27 ?表格單純形法 通過(guò)例１我們發(fā)現(xiàn) ， 在單純形法的求解過(guò)程中 ， 有下列重要指標(biāo)： ? 每一個(gè)基本可行解的檢驗(yàn)向量 根據(jù)檢驗(yàn)向量可以確定所求得的基本可行解是否為最優(yōu)解 。X = ( ,0 , , 0 , 0 )55T* 6 1 739。 檢驗(yàn)向量 因?yàn)樗袡z驗(yàn)數(shù)均小于零， 所以 是最優(yōu)解， 1N N B2 4 52 3 15 5 5σ =C C B N= (2, 1,1) (3,5)6 1 25 5 536 4 7 26 9 2=( 2, 1,1) ( , , ) =( , , )5 5 5 5 5 5 σ σ σ???????????????6 1 739。X1x5x11111 1 0 41 1 0 4 2222665 1 21103 0 1 35 5 5 5223 172 101 5 5 5 5 66 1 2105 5 5 5???????????????????? ???? ???????????????????????13BB N 25N411x1x C = ( 3 ,1 )1 0 422X = ,X = x ,B = ,N = , ,b =x C = ( 5 ,2 , 1 )0 1 5 1 33x22???????? ? ? ? ??????? ? ? ? ???? ? ? ? ? ??? ????????第二行乘以２ /５ 第一行減以第二行的１ /２倍 25 —————————————————————————— 可得改進(jìn)的基本可行解 。 ② 選取換出變量 且 ， 選取 為換出變量 . 4 3 3m in ,1 / 2 5 / 2 5 / 2?? ?????X=(0 ,0 ,4 , 0 , 3 ) T11114 2B b = , B P 0352??????????????? ? ? ?????1 10? ?? 1x5x13BB N 25N411x1x C = ( 3 ,1 )1 0 422X = ,X = x ,B = ,N = , ,b =x C = ( 5 ,2 , 1 )0 1 5 1 33x22???????? ? ? ? ??????? ? ? ? ???? ? ? ? ? ??? ????????3 1 11 1 15x 4 1 /2= B b B P x = xx 3 5 /2?? ? ? ? ??? ? ? ? ?? ? ? ???24 （ 4） 求改進(jìn)了的基本可行解 對(duì)約束方程組的增廣矩陣施以初等行變換 ， 使換入變量 所對(duì)應(yīng) 的系數(shù)列向量 變換成換出變量 所對(duì)應(yīng)的單位向量 , 112P=52????????????50P1???????39。 檢驗(yàn)向量 因?yàn)? ， 所以 仍不是最優(yōu)解。 ， 基變量 ， 非基變量 。 32P=1?????? 41P0???????50P=1?????? 11 1 1 0 41 2 2 1 0 8 223 4 1 0 1 73 4 1 0 1 7111 1 0 422 5 13 0 1 322??????????????????????????????????????? 39。 X=(0 ,0 ,0 , 8 , 7 ) T 1N N B1 2 31 2 2σ =C C B N =( 5,2,3) (1,1)3 4 1=( 5,2,3) ( 2,2, 1) =( 3, 0, 4) σ σ σ?????????14BB N 25N3xx C = ( 1, 1)1 0 1 2 2 8X = ,X = x ,B = ,N = , ,b =x C = ( 5, 2, 3)0 1 3 4 1 7x???? ? ? ? ? ? ????? ? ? ? ? ? ???? ? ? ? ? ??? ????X=(0 ,0 ,0 , 8 , 7 ) T19 （ 3） 基本可行解 的改進(jìn) ① 選取換入變量 因?yàn)?max{3， 4}=4，取 x3為換入變量。 4510B = ( P P ) =01??????45x ,x 1 2 3x ,x , x14BB N 25N3xx C = ( 1, 1)1 0 1 2 2 8X = ,X = x ,B = ,N = , ,b =x C = ( 5, 2, 3)0 1 3 4 1 7x???? ? ? ? ? ? ????? ? ? ? ? ? ???? ? ? ? ? ??? ????1NB8X = 0 X = B b =7? ???? ????X=(0 ,0 ,0 , 8 , 7 ) T1B8Z = C B b = ( 1 ,1 ) 17? ?? ??????18 (2) 檢驗(yàn) 是否最優(yōu)。X17 1 2 3 4 51 2 3 41 2 3 51 2 3 4 5m a xZ =5x 2x 3x x xx 2x 2x x 83x 4x x x 7 x ,x ,x ,x ,x 0? ? ? ?? ? ? ???? ? ? ??? ??1 2 2 1 0A=3 4 1 0 1??????8b7???????C =(5 ,2 , 3 , 1 , 1 )?例 1 解： (１ )確定初始的基本可行解。 由于行初等變換后的方程組 與原約束方程組 或 同解 B 1 1NX( I , B N ) = B bX??????AX=b39。這些基變量的系數(shù)列向量是單位矩陣 I中的單位向量。變換的結(jié)果是將系數(shù)矩陣Ａ中的可行基Ｂ變換成單位矩陣 I，把非基變量系數(shù)列向量構(gòu)成的矩陣Ｎ變換成 ，把資源向量 b變換成 。 可得基本可行解 。 1BbX= 0???????1 m + kB P 0?m +k 0? ?證：令 ，則得新的可行解 將上式代入 因?yàn)? , 故當(dāng) λ→+∞ 時(shí)，