運籌學基礎對偶線性規(guī)劃(1)(參考版)
2025-05-08 22:31本頁面
【正文】 【 解 】 先將原問題最優(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， 。否則，將新增約束直接反映到最終表中，再進行分析。 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 五、增加一個約束條件的分析 增加一個約束條件，在實際問題中相當于增添一道工序。2P11/2 1/2 1/2 3/2 繼續(xù)迭代得下表 因原問題與其對偶問題均為非可行解，通過引入人工變量將原問題轉化為可行解，再用單純形法繼續(xù)計算。2139。 【 例 】 上例中， c2=3， x2的系數(shù)向量變?yōu)?P2=(8， 4， 1)T，試分析最優(yōu)解的變化。6PCj 比 值 CB XB b 檢驗數(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)解的變化。 其中 cj 是新變量目標函數(shù)系數(shù) , Pi是新變量約束函數(shù)系數(shù)， y*是對偶問題的解 最終單純形表 【 例 】 上例中 Cj 比 值 CB XB b 檢驗數(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 若增加一個變量 x6，有 c6=3, P6=(3,4,2)T，試分析最優(yōu)解的變化。 注 :此公式是單純形法利用公式求解的推導結果 ! 問題： B與 B1分別是什么 ？ 以此題為例 Cj 比 值 CB XB b 檢驗數(shù) ?j y1 y2 y3 y4 y5 15 24 5 0 0 2 0 6 1 1 0 1 5 2 1 0 1 y4 Y5 0 0 0 15 24 5 0 0 檢驗數(shù) ?j 1/4 5/4 1 0 1/4 1/4 1/2 15/2 0 1 1/2 3/2 Y2 y3 24 5 17/2 15/2 0 0 7/2 3/2 初始單純形表 最終單純形表 B B1 原理是： (B|I)經(jīng)過初等變換可化為 (I|B1)，其中 I是單位陣 I I 又例 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15 0 5 1 0 0 24 6 2 0 1 0 5 1 1 0 0 1 x3 x4 x5 0 0 0 0 2 1 0 0 0 初始單純形表 Cj 比 值 CB XB b 檢驗數(shù) ?j= cjzj 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* B1 ???????????110260501BI* I 【 例 】 上例中 最終單純形表 Cj 比 值 CB XB b 檢驗數(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
范文總結相關推薦
鄂ICP備17016276號-1