運(yùn)籌學(xué)基礎(chǔ)對偶線性規(guī)劃(1)(文件)
【正文】 ???080024320b????????????????????????????????????????????222100802/14/102/34/102/14/102/154/51*b注： B1擴(kuò)充了檢驗(yàn)行，目標(biāo)值的變化 △ b*=B1△ b 15/2+10 7/2+2 3/22 17/22 35/2 11/2 1/2 21/2 B1 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15 0 5 1 0 0 5 1 1 0 0 1 2 0 4 0 1 6 x3 x1 x4 0 2 0 10 0 1 0 0 2 最優(yōu)值 maxz*=10 即得新最優(yōu)解 x1=5， x2=0， x3=15， x4=2 ， x5=0 【 解 】 (b)若第 2個約束條件變?yōu)? 6x1+2x2≤24+l Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 因 將其加到最終單純形表的基變量 b這一數(shù)列上得下表 ????????????00lb????????????????????????????????????????????44445002/14/102/34/102/14/102/154/51*lllllb15/2+5l/4 7/2+l/4 3/2l/4 17/2l/4 15/2+5/4l??? l??6 7/2+1/4l??? l???4 3/21/4l??? l?6 得 6? l?6 即： 6? l?6時，最優(yōu)解不變； 三、增加一個變量的分析 增加一個變量在實(shí)際問題中反映為增加一種新的產(chǎn)品。6PCj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 因 ?6=10 ,故用單純形法繼續(xù)計算 70 21 3 x6 增加變量 x6，有 c6=3, P6=(3,4,2)T，試分析最優(yōu)解的變化。2139。 4M 5+24M 0 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x’2 x3 x4 x5 x6 2 3 0 0 0 3 3/8 0 0 1/24 1/6 1 1/24 11/4 1 0 1/12 1/3 0 1/12 15/8 0 1 1/8 0 0 1/8 x5 x1 x’2 0 2 3 89/8 0 0 5/24 2/3 0 M+5/24 新的最優(yōu)值為 maxz*=89/8 得到新最優(yōu)解： x1=11/4， x2=15/8， x3=0， x4=0， x5=3/8， x6=0 五、增加一個約束條件的分析 增加一個約束條件，在實(shí)際問題中相當(dāng)于增添一道工序。 【 解 】 先將原問題最優(yōu)解 x1 =7/2, x2 =3/2代入新約束條件，因有 故將約束條件寫成 3x1+2x2 +x6 = 12，并取 x6為基變量，直接反映到最終表中 3 7/2++2 3/2=27/212 maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 3x1 +2x2 ≤ 12 x1 , x2 ≥0 得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 x6 2 1 0 0 0 0 15/2 0 0 1 5/4 15/2 0 7/2 1 0 0 1/4 1/2 0 3/2 0 1 0 1/4 3/2 0 x3 x1 x2 x6 0 2 1 0 17/2 0 0 0 1/4 1/2 0 x1與 x2的向量不是單位向量，要繼續(xù)變換 12 3 2 0 0 0 1 得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 x6 2 1 0 0 0 0 15/2 0 0 1 5/4 15/2 0 11/4 1 0 0 1/4 1/2 0 3/2 0 1 0 1/4 3/2 0 x3 x1 x2 x6 0 2 1 0 17/2 0 0 0 1/4 1/2 0 用對偶單純形法迭代繼續(xù)變換 3/2 0 0 0 1/4 3/2 1 得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 x6 2 1 0 0 0 0 15 0 0 1 5/2 0 5 4 1 0 0 1/3 0 1/3 0 0 1 0 1/2 0 1 x3 x1 x2 x5 0 2 1 0 8 0 0 0 1/6 0 1/3 1 0 0 0 1/6 1 2/3 新的最優(yōu)值為 max z*=8 得新的最優(yōu)解為： x1=4， x2=0， x3=15， x4=0， x5=1， x6=0， 。否則，將新增約束直接反映到最終表中，再進(jìn)行分析。2P11/2 1/2 1/2 3/2 繼續(xù)迭代得下表 因原問題與其對偶問題均為非可行解，通過引入人工變量將原問題轉(zhuǎn)化為可行解，再用單純形法繼續(xù)計算。 【 例 】 上例中， c2=3， x2的系數(shù)向量變?yōu)?P2=(8， 4， 1)T，試分析最
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1