【正文】 37 9026 72 3103 2t tt t??? ?? ? ? ? ?? ??????? ? ? ? ???? ??，可知當(dāng)參數(shù) t 從 0 開始增大到 9/7，即[0, 9/ 7]t? 時，檢驗數(shù)都保持為非 正 ，故此時最優(yōu)解保持為 * (2, 6, 2, 0, 0) TX ? ，*( ) 36 2z t t??。 （ 7） 若約束條件②變?yōu)?1 2 310 5 10 10 0x x x? ? ?，即 1x 、 2x 的系數(shù)分別變?yōu)?110P ????????、215P ???????， b 列變?yōu)?20100b ???????，則 1 12 1 0 1 1 1 1[ , ] 4 1 1 0 5 1 4 1B P P? ??? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? 1 1 0 2 0 2 04 1 1 0 0 2 0Bb? ? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? 由于基變量 2x 的系數(shù)發(fā)生變化，故在約束條件①中引入人工變量 6x ，單純形表變?yōu)椋? jc － 5 5 13 0 0 － M i? BC BX b 1x 2x 3x 4x 5x 6x M 6x 20 1 1 [3] 1 0 1 20/3 0 5x 20 14 1 － 2 － 4 1 0 j? 5M 5+M 13+3M M 0 0 13 3x 20/3 1/3 1/3 1 1/3 0 1/3 20 0 5x 100/3 40/3 [5/3] 0 10/3 1 2/3 20 j? 2/3 2/3 0 13/3 0 M13/3 13 3x 0 3 0 1 1 1/5 1/5 5 2x 20 8 1 0 2 3/5 2/5 j? 6 0 0 3 2/5 M23/5 故，最優(yōu)解為 * ( 0 , 2 0 , 0 , 0 , 0 , 0 ) TX ? ， * 100z ? 。 （ 6） 若引入一個約束③，單純形表 將增加一行。 （ 4） 1x 在原最優(yōu)解中為非基變量，若 1x 的系數(shù)列 變 為105P ???????， 由 1 1 1 0 0 04 1 5 5BP? ? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? 可知， 檢驗數(shù) 1? 由 0 變?yōu)椋?5，故最優(yōu)解不變。 （ 2）約束條件右端常數(shù)此時為 (20,85)Tb ? ，由 1 1 0 2 0 2 0 04 1 8 5 5Bb? ? ? ? ? ? ?? ? ?? ? ? ? ? ??? ? ? ? ? ? 可知， 最優(yōu)基不變，最優(yōu)解為 * (0 , 20 , 0 , 0 , 5 ) TX ? ， * 100z ? 。 由單純形表可知，原問題中 1 1041B? ??? ?????。 例 有線性規(guī)劃如下： 1 2 31 2 31 2 31 2 3m a x 5 5 133 20 . . 12 4 10 90 , , 0z x x xx x xs t x x xx x x? ? ? ?? ? ? ??? ? ? ??? ??①② 先用單純形法求出最優(yōu)解，再分析以下各種條件下，最優(yōu)解分別有什么變化： （ 1）約束條件①的右端常數(shù)由 20 變?yōu)?30； （ 2）約束條件②的右端常數(shù)由 90 變?yōu)?85； （ 3）目標(biāo)函數(shù)中 3x 的系數(shù)由 13 變?yōu)?8； （ 4） 1x 的系數(shù)列向量由 [1, 12]T變?yōu)?[0, 5]T； （ 5） 1x 和 2x 的系數(shù)列向量由 [1, 12]T 、 [1, 4]T變?yōu)?[0, 5]T 、 [2, 1]T； （ 6）增加一個約束條件 ③ 1 2 32 3 5 50x x x? ? ?； （ 7）將約束條件②改變?yōu)?1 2 310 5 10 10 0x x x? ? ?。 解： 原問題的對偶問題為： 12122121212m in 8 122 2 221. . 526,0w y yyyys t y yyyyy?????? ??????? ???? ?? 將對偶問題的最優(yōu)解代入約束條件，可得： *1*2*3*42 * 4 2 * 1 2 02 * 4 1 04 1 5 04 2 * 1 6 0xxxx? ? ? ? ??? ? ??? ? ? ? ??? ? ? ? ?? （ 1） 又由 * * * *1 1 3 4* * * * *2 1 2 3 40 2 80 2 2 2 12y x x xy x x x x? ? ? ? ???? ? ? ? ??? ＝ ＝ （ 2） 將結(jié)論（ 1）和（ 2）結(jié)合起來， 可得： **34**3482 12xxxx? ??????＝＝ ，解得 *3*444xx? ?????? 即原問題的最優(yōu)解為 * (0, 0, 4, 4)TX ? 。 解： 原問題的對偶問題為： 1212121212m in 1 0 1 6232 2 41,0w y yyyyyyyyy?????? ???? ???? ?? 將 * (6,2,0)TX ? 代入原 問題的約束條件，可得： *1*26 2 * 2 10 02 * 6 2 * 2 16 0yy? ? ? ? ???? ? ? ??? （ 1） 又由 * * *1 1 2* * *2 1 2* * *1 1 20 2 30 2 2 40 1x y yx y yx y y? ? ? ? ??? ? ? ??? ? ? ? ?? （ 2） 將結(jié)論（ 1）和（ 2）結(jié) 合起來，可 解得 **121yy??。 解：由 * 1 5 2[ , , ]B P P P? ，可知： 1* 1 11 5 21 0 2 0 1 / 4 0[ , , ] 4 0 0 2 1 / 2 10 1 4 1 / 2 1 / 8 0B P P P???? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ??? ? ? ? 故由單純形表的行變換過程可知： *10 1 / 4 0 8 1 2 1 0 0 4 1 0 0 1 / 4 0[ , ] 2 1 / 2 1 1 6 4 0 0 1 0 4 0 0 2 1 / 2 11 / 2 1 / 8 0 1 2 0 4 0 0 1 2 0 1 1 / 2 1 / 8 0B b A?? ? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ? 原問題的最優(yōu)單純形表為： jc 2 3 0 0 0 Bc BX b 1x 2x 3x 4x 5x 2 1x 4 1 0 0 1/4 0 0 5x 4 0 0 － 2 1/2 1 3 2x 2 0 1 1/2 － 1/8 0 j? 0 0 － 3/2 － 1/8 0 例 8：已知某線性規(guī)劃的最優(yōu)單純形表為： jc 2 3 0 0 0 Bc BX b 1x 2x 3x 4x 5x 2 1x 4 1 0 0 1/4 0 0 5x 4 0 0 － 2 1/2 1 3 2x 2 0 1 1/2 － 1/8 0 j? 0 0 － 3/2 － 1/8 0 其中， 345,x x x 為松弛變量，求該線性規(guī)劃的初始單純形表。先將原問題化為標(biāo)準(zhǔn)型，可得： 1 2 31 2 3 41 3 52 3 6m a x 2 2622..200 , 1, 2 , , 6jz x x xx x x xx x xstx x xxj? ? ?? ? ? ???? ? ? ??? ? ? ??? ??? 引入人工變量，可得第一階段的問題為： 7 8 91 2 3 4 71 3 5 82 3 6 9m i n 622..200 , 1 , 2 , , 9jz x x xx x x x xx x x xstx x x xxj? ? ?? ? ? ? ??? ? ? ? ? ??? ? ? ? ??? ??? 構(gòu)造單純形表，計算如下： jc 0 0 0 0 0 0 1 1 1 i? Bc BX b 1x 2x 3x 4x 5x 6x 7x 8x 9x 1 7x 6 1 1 1 － 1 0 0 1 0 0 6 1 8x 2 － 2 0 1 0 － 1 0 0 1 0 － 1 9x 0 0 [2] － 1 0 0 － 1 0 0 1 0 j? 1 － 3 － 1 1 1 1 0 0 0 1 7x 6 1 0 3/2 － 1 0 1/2 1 0 － 1/2 4 1 8x 2 － 2 0 [1] 0 － 1 0 0 1 0 2 0 2x 0 0 1 － 1/2 0 0 － 1/2 0 0 1/2 － j? 1 0 － 5/2 1 1 － 1/2 0 0 3/2 1 7x 3 [4] 0 0 － 1 3/2 1/2 1 － 3/2 － 1/2 3/4 0 3x 2 － 2 0 1 0 － 1 0 0 1 0 － 0 2x 1 － 1 1 0 0 － 1/2 － 1/2 0 1/2 1/2 － j? － 4 0 0 1 － 3/2 － 1/2 0 5/2 3/2 0 1x 3/4 1 0 0 － 1/4 3/8 1/8 1/4 － 3/8 － 1/8 0 3x 7/2 0 0 1 － 1/2 － 1/4 1/4 1/2 1/4 － 1/4 0 2x 7/4 0 1 0 － 1/4 － 1/8 － 3/8 1/4 1/8 3/8 j? 0 0 0 0 0 0 1 1 1 故，第一階段的最優(yōu)解為 * 3 7 7( , , , 0 , 0 , 0 , 0 , 0 , 0 )442 TX ? 第二階段的單純形表如下： jc 2 － 1 2 0 0 0 i? Bc BX b 1x 2x 3x 4x 5x 6x 0 1x 3/4 1 0 0 － 1/4 3/8 1/8 0 3x 7/2 0 0 1 － 1/2 － 1/4 1/4 0 2x 7/4 0 1 0 － 1/4 － 1/8 － 3/8 j? 0 0 0 5/4 － 3/8 － 9/8 非基變量 4x 的檢驗數(shù)為正，但其系數(shù)向量為負(fù)，故原問題為無界解。將原問題化為標(biāo)準(zhǔn)型，可得： 1 2 31 2 3 41 2 3 51 2 3 6m a x 10 15 125 3 95 6 15 15..250 , 1 , 2 , , 7jz x x xx x x xx x x xstx x x xxj? ? ?? ? ? ??? ? ? ? ? ??? ? ? ? ??? ??? 在第三個等式約束中引入一個人工變量 7x ，可得： 1 2 3 71 2 3 41 2 3 51 2 3 6 7m a x 10 15 125 3 95 6 15 15..250 , 1 , 2 , , 7jz x x x Mxx x x xx x x xstx x x x xxj? ? ? ?? ? ? ??? ? ? ? ? ??? ? ? ? ? ??? ??? 用單純形表求解，可得： jc 10 15 12 0 0 0 － M i? Bc BX b 1x 2x 3x 4x 5x 6x 7x 0 4x 9 [5] 3 1 1 0 0 0 9/5 0 5x 15 － 5 6 15 0 1 0 0 － M 7x 5 2 1 1 0 0 1 1 5/2 j? 2M+10 M+15 M+12 0 0 M 0 10 1x 9/5 1 3/5 1/5 1/5 0 0 0 9 0 5x 24 0 9 [16] 1 1 0 0 3/2 － M 7x 7/5 0 1/5 3/5 2/5 0 1 1 7/3 j? 0 9M/5 3M/5+