【正文】 1 將下列線性規(guī)劃模型化為標準形式并列出初始單純形表。 （ 1） 1 2 31 2 31 2 31 2 31 2 3m in 2 43 2 2 194 3 4 14.. 5 2 4 260 , 0 ,z x x xx x xx x xst x x xx x x? ? ?? ? ? ???? ? ? ??? ? ? ? ??? ??? 無 約 束 解： （ 1）令 1 1 3 3 339。 , 39。 , 39。x x x x x z z? ? ? ? ? ?，則得到標準型為（其中 M 為一個任意大的正數(shù)） 1 2 3 3 4 5 6 71 2 3 3 41 2 3 3 5 61 2 3 3 71 2 3 3 4 5 6 7m a x 39。 2 39。 2 4 39。 4 39。39。 0 03 39。 2 2 39。 2 39。39。 1 94 39。 3 4 39。 4 39。39。 1 4..5 39。 2 4 39。 4 39。39。 2 639。, , 39。, 39。39。, , , , 0z x x x x x x M x M xx x x x xx x x x x xstx x x x xx x x x x x x x? ? ? ? ? ? ? ? ?? ? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ??? ?? 初始單純形表如表 21 所示： 表 21 cj 2 2 4 4 0 0 M M ? CB XB b 139。x x2 339。x 339。39。x x4 x5 x6 x7 0 x4 19 3 2 2 2 1 0 0 0 19/3 M x6 14 [ 4 ] 3 4 4 0 1 1 0 14/4 M x7 26 5 2 4 4 0 0 0 1 26/5 z 2+9M 2+5M 4+8M 48M 0 M 0 0 用單純形法求解下列線性規(guī)劃問題。 （ 1） 1 2 31 2 31 2 31 2 31 2 3m ax 23 602 10..2 20, , 0z x x xx x xx x xstx x xx x x? ? ?? ? ??? ? ? ??? ? ? ??? ?? （ 2） 1 2 3 41 2 3 41 2 3 41 2 3 4m in 5 2 3 22 3 4 7. . 2 2 2 3, , , 0z x x x xx x x xs t x x x xx x x x? ? ? ?? ? ? ???? ? ? ??? ?? 解： （ 1）最優(yōu)解為 **(15, 5, 0) , 25Txz??。 （ 2） 最優(yōu)解為 (0 ,1 .5 , 0 , 0 ) , 3T? ? ?。 分別用大 M 法和兩階段法求解下列線性規(guī)劃問題。 （ 1） 1 2 31 2 31 2 31 2 3m a x 2 3 57. . 2 5 1 0, , 0z x x xx x xs t x x xx x x? ? ?? ? ???? ? ??? ?? （ 2） 12121 2 31 2 41 2 3 4m in 4334 3 6..24, , , 0z x xxxx x xstx x xx x x x?????? ? ? ??? ? ? ??? ?? 解： （ 1）最優(yōu)解為 **(6 .4 2 9 , 0 .5 7 1 , 0 ) , 1 4 .5 7 1Txz??。 （ 2）最優(yōu)解為 (0 .4 ,1 .8 ,1, 0 ) , 3 .4T。 2 已知線性規(guī)劃問題 1 2 3 4 51 2 3 4 51 2 3 4 5m in 2 3 5 2 32 3 4. . 2 3 30 , 1 , 2 , , 5jZ x x x x xx x x x xs t x x x x xxj? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ??? 其對偶問題最優(yōu)解為 * * *124 / 5 , 3 / 5 。 5y y Z? ? ?。試用對偶理論找出原問題最優(yōu)解。 解： 先寫出它的對偶問題 12121212121212max 4 32232 3 5..233,0w y yyyyyyystyyyyyy?????? ???? ???????? ?????? 將 **124 / 5, 3 / 5yy??代入約束條件可知，第 4 個約束為嚴格不等式，因此，由互補松弛性得 * * *2 3 4 0x x x? ? ? 。又因為 **12,0yy? ，所以原問題的兩個約束條件應(yīng)取等式，因此有 **15**153423xxxx? ???? ???? ? *1*511xx??????? 故原問題最優(yōu)解為 **(1, 0 , 0 , 0 ,1) , 5TXz??。 現(xiàn)有線性規(guī)劃問題 1 2 31 2 31 2 31 2 3m a x 5 5 1 33 2 0. . 1 2 4 1 0 9 0, , 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 變 為 70； （ 3）目標函數(shù)中 3x 的系數(shù)由 13 變?yōu)?8； （ 4） 1x 的系數(shù)列向量由 ( 1,12)T? 變?yōu)?(0,5)T ； （ 5）將原約束條件 ② 改變?yōu)?1 2 310 5 10 100x x x? ? ?； （ 6）增加一個約束條件 1 2 32 3 5 50x x x? ? ?。 解： 在上述 LP 問題的第 ① 、 ② 個約束條件中分別加入松弛變量 x4,x5得 1 2 3 4 51 2 3 41 2 3 51 2 3 4 5m a x 5 5 1 3 0 03 2 0. . 1 2 4 1 0 9 0, , , , 0z x x x x xx x x xs t x x x xx x x x x? ? ? ? ? ?? ? ? ? ???? ? ? ??? ?? ① ② 3 列出此問題的初始單純形表并進行迭代運算，過程如表 211 所示。 由表 211 中的計算結(jié)果可知， LP 問題的最優(yōu)解 X*=(0,20,0,0,10)T， z*=5*20=100。 （ 1）約束條件 ① 的右端項系數(shù)由 20 變?yōu)?30，則有 1 1 0 3 0 3 04 1 9 0 3 0Bb? ? ? ? ? ? ???? ? ? ? ? ???? ? ? ? ? ? 列出單純形表，并利用對偶單純形法求解，過程如表 212 所示。 表 211 cj 5 5 13 0 0 θi CB XB b x1 x2 x3 x4 x5 0 x4 20 1 1 [ 3 ] 1 0 20/3 0 x5 90 12 4 10 0 1 9 cjzj 5 5 13 0 0 13 x3 20/3 1/3 [ 1/3 ] 1 1/3 0 20 0 x5 70/3 46/3 2/3 0 10/3 1 35 cjzj 2/3 2/3 0 13/3 0 5 x2 20 1 1 3 1 0 0 x5 10 16 0 2 4 1 cjzj 0 0 2 5 0 表 212 cj 5 5 13 0 0 CB XB b x1 x2 x3 x4 x5 5 x2 30 1 1 3 1 0 0 X5 30 16 0 [ 2 ] 4 1 cjzj 0 0 2 5 0 5 x2 15 23 1 0 [ 5 ] 3/2 13 x3 15 8 0 1 2 1/2 cjzj 16 0 0 1 1 0 x4 3 23/5 1/5 0 1 3/10 13 x3 9 6/5 2/5 1 0 1/10 cjzj 103/5 1/5 0 0 13/10 由表 212 中計算結(jié)果可知 ， LP 問題的最優(yōu)解變?yōu)?**(0 , 0 , 9 , 3 , 0 ) , 1 3 9 1 1 7TXz? ? ? ?。 （ 2）約束條件 ② 的右端常數(shù)由 90 變?yōu)?70，則有 1 1 0 2 0 2 04 1 7 0 1 0Bb? ? ?? ? ? ???? ?? ? ? ???? ?? ? ? ? 列出單純形表，并利用對偶單純形法求解，結(jié)果如表 213 所示。 4 表 213 cj 5 5 13 0 0 CB XB b x1 x2 x3 x4 x5 5 x2 20 1 1 3 1 0 0 X5 10 16 0 [ 2 ] 4 1 cjzj 0 0 2 5 0 5 x2 5 23 1 0 5 3/2 13 x3 5 8 0 1 2 1/2 cjzj 16 0 0 1 1 由表 213 結(jié)果知， LP 問題的最優(yōu)解變?yōu)?**(0 , 5 , 5 , 0 , 0 ) , 5 5 1 3 5 9 0TXz? ? ? ? ? ?。 （ 3）目標函數(shù)中 x3 的系數(shù)由 13 變?yōu)?8，由于 x3 是非基變量，其檢驗數(shù)變?yōu)? 3 8 5 3 0 ( 2 ) 7 0? ? ? ? ? ? ? ? ? ? 所以 LP 問題的最優(yōu)解不變。 （ 4） x1 的系數(shù)列向量由 (1,12)T變?yōu)?(0,5) T，則 x1 在最終單純形表中的系數(shù)列向量變?yōu)? 139。1 1 0 0 04 1 5 5BP? ? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ? 從 而 x1 在最終單純形表中的檢驗數(shù)變?yōu)? 39。 1 39。1 1 1 05 ( 5 , 0 ) 5 05Bc C B P? ? ??? ? ? ? ? ? ? ????? 所以 LP 問題的最優(yōu)解保持不變。 （ 5）將原約束條件 ② 改變?yōu)?10x1+5x2+10x3≤100，則 x1在最終單純形表中系數(shù)列向量變?yōu)?39。111( 1,14)TP B P?? ? ?，檢驗數(shù) 39。11 1 1 5 ( 5 , 0 ) ( 1 , 1 4 ) 0TBc C B P? ?? ? ? ? ? ? ? x2 在最終單純形表中系數(shù)列向量變?yōu)?39。122(1,1)TP B P???，檢驗數(shù)39。12 2 2 5 ( 5 , 0 ) (1 , 1 ) 0TBc C B P? ?? ? ? ? ?。 又因 1 1 0 2 0 2 04 1 1 0 0 2 0Bb? ? ? ? ? ? ???? ? ? ? ? ??? ? ? ? ? ?的各分量均大于 0，故 LP 問題的最優(yōu)解不變。 （ 6）增加一個約束條件 2x1+3x2+5x3≤50，則在此約束條件中加入松弛變量 x6，并將此約束加入到最終單純形表中，繼續(xù)迭代，過程如表 214 所示。 由表 214 中計算結(jié)果可知， LP 問題的最優(yōu)解變?yōu)?* (0 , 2 5 / 2 , 5 / 2 , 0 ,1 5 , 0 ) TX ? ，* 5 2 5 / 2 1 3 5 / 2 9 5z ? ? ? ? ?。 表 214 cj 5 5 13 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 5 5 x2 20 1 1 3 1 0 0 0 x5 10 16 0 2 4 1 0 0 x6 50 2 3 5 0 0 1 5 x2 20 1 1 3 1 0 0 0 x5 10 16 0 2 4 1 0 0 x6 10 5 0 [ 4 ] 3 0 1 cj zj 0 0 2 5 0 0 5 x2 25/2 11/4 1 0 5/4 0 3/4 0 x5 15 27/2 0 0 5/2 1 1/2 13 x3 5/2 5/4 0 1 3/4 0 1/4 cj zj 5/2 0 0 7/2 0 1/2 分別用分支定界法和割平面法求解下列整數(shù)規(guī)劃模型。 （ 1） 12min 4 3z x x?? ? （ 2） 12max z x x?? 1212124 1 0. . 2 3 8, 0 ,xxs t x xxx?????????? 且 為 整 數(shù) 12121226. . 4 5 2 0, 0 ,xxs t x x