運籌學基礎對偶線性規(guī)劃(1)-資料下載頁
2025-05-05 22:31本頁面
【正文】 =3， x2的系數(shù)向量變?yōu)?P2=(8， 4， 1)T，試分析最優(yōu)解的變化。 【 解 】 同上例 maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 maxZ=2x +3 8x2 6x1 + 4x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 ? ? 231482/14/103*2 ??????????????? Pyc jj????????????????????????????????????? ?21212111482/34/102/14/102/154/5139。2139。2 PBP ? ?231482/14/1032 ??????????????Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 3 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 ???????????????????????????????????21212111482/34/102/14/102/154/5139。2P11/2 1/2 1/2 3/2 繼續(xù)迭代得下表 因原問題與其對偶問題均為非可行解，通過引入人工變量將原問題轉化為可行解，再用單純形法繼續(xù)計算。 將第一行 x3+4x4 24x5= 9 化為標準型 x34x4 +24x5=9 再加上人工變量 x3 4x4 +24x5 +x6 =9 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x‘2 x3 x4 x5 2 3 0 0 0 9 0 0 1 4 24 2 1 0 0 1/2 2 3 0 1 0 1/2 3 x3 x1 x‘2 0 2 3 13 0 0 0 1/2 5 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x’2 x3 x4 x5 x6 2 3 0 0 0 M 9 0 0 1 4 24 1 2 1 0 0 1/2 2 0 3/2 0 1 0 1/2 3 0 x6 x1 x’2 0 2 3 因 ?5 0 ,故用單純形法迭代計算 － x3－ 4x4 +24x5 +x6 =9 13 0 0 0 1/2 5 M 13+9M 0 0 M 189。 4M 5+24M 0 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗數(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 五、增加一個約束條件的分析 增加一個約束條件，在實際問題中相當于增添一道工序。分析的方法是先將原來的問題的最優(yōu)解變量取值代入這個新增的約束條件中，如滿足，說明新增約束未起到限制作用，原最優(yōu)解不變。否則，將新增約束直接反映到最終表中，再進行分析。 【 例 】 上例中， 新增添一個約束條件 3x1+2x2 ≤12， 試分析最優(yōu)解的變化。 【 解 】 先將原問題最優(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 檢驗數(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 檢驗數(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 檢驗數(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，
范文總結相關推薦
鄂ICP備17016276號-1