運籌學(xué)基礎(chǔ)對偶線性規(guī)劃(2)(參考版)
2025-05-03 12:05本頁面
【正文】 注：證明過程參見教材 60頁性質(zhì) 6證明 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 用單純形法同時求解 原問題 和 對偶問題 原問題是： maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 原問題的標(biāo)準(zhǔn)型是： maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 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 maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 24/6=4 5/1=5 原問題變量 原問題松馳變量 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 得原問題可行解 :X=(0,0,15,24,5)T 對偶問題解 :Y*=(0,0,0,2,1)T 檢驗數(shù)行的 － (cjzj)值是其對偶問題的一個 基本解 yi ； 檢驗數(shù) ?j 15 0 5 1 0 0 4 1 1/3 0 1/6 0 1 0 2/3 0 1/6 1 x3 x1 x5 0 2 0 8 0 1/3 0 1/3 0 3 12 得原問題可行解 :X=(4,0,15,0,1)T，此時 Z=8 同時得對偶問題基礎(chǔ)解 :Y*=(0,1/3,0, 0,1/3)T， W=8 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 原問題變量 原問題松馳變量 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 變換單純形表 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 此時得原問題最優(yōu)解 :X*=(7/2,3/2,15/2,0,0)T， Z*=17/2 原問題變量 原問題松馳變量 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 則對偶問題最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， S*=17/2 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 又例： 用單純形法同時求解 原問題 和 對偶問題 maxZ= 100 x1 + 80 x2 2 x1+4 x2≤ 80 3 x1+ x2≤ 60 x1, x2 ≥0 將線性規(guī)劃問題標(biāo)準(zhǔn)化 maxZ= 100 x1 + 80 x2 + 0 x3 + 0 x4 2 x1+4 x2 + x3 = 80 3 x1+ x2 + x4 =60 x1, x2 x3 x4 ≥0 0 0 0 80 100 Z 60 1 0 1 3 0 80 0 1 4 2 0 此時得原問題的最優(yōu)解： X0=(16,12,0,0)T , maxZ=2560 初等變換 2022 100/3 0 140/3 0 Z 20 1/3 0 1/3 1 0 40 2/3 1 10/3 0 0 2 x1+ 4 x2 + x3 = 80 3 x1+ x2 + x4 =60 Z+100 x1 + 80 x2 + 0 x3 + 0 x4=0 ～ ～ 2560 24 14 0 0 Z 16 2/5 1/10 0 1 0 12 1/5 3/10 1 0 0 Z x1 x2 x3 x4 b 同時得對偶問題的最優(yōu)解： y1=14,y2 =24,y3 =0,y4 =0,即 Y0=(14,24,0,0)T , minS=2560 。 線性規(guī)劃問題的對偶問題為： =8y1+6y2+6y3+9y4 . y1+2y2 +y4 ≥ 2 3y1+y2 + y3 +y4 ≥ 4 y3 +y4 ≥ 1 y1 +y3 ≥ 1 yj≥0（ j=1,2,3,4） 練習(xí)：已知線性規(guī)劃問題為： ④ 為嚴(yán)格不等式，由互補松弛定知，必有 y4 = 0； =2x1+4x2+x3+x4 . x1+3x2 +x4≤8 2x1+x2 ≤6 x2 + x3 +x4≤6 x1 + x2 +x3 ≤9 xj≥0（ j=1,2,3,4） ① 8=8 ② 6=6 ③ 6=6 ④ 89 解之，有： y1=4/5, y2=3/5, y3=1， y4 = 0 答案：因為原問題的最優(yōu)解為 :X*=(2,2,4,0)T ： 又因 x1, x2 , x3＞ 0，故對偶問題的前三個約束必為緊約束 線性規(guī)劃問題的對偶問題為： =8y1+6y2+6y3+9y4 . y1+2y2 +y4 ≥ 2
電大資料相關(guān)推薦
鄂ICP備17016276號-1