運籌學(xué)基礎(chǔ)對偶線性規(guī)劃(1)(已修改)
2025-05-17 22:31 本頁面
【正文】 167。 對偶單純形方法 原問題是： 原問題的標(biāo)準(zhǔn)型是： minZ=15y1+24y2+5y3 6y2+y3 ≥ 2 5y1 +2y2 +y3 ≥1 y1 , y2 , y3 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2+y3 y4 = 2 5y1 +2y2 +y3 y5 =1 y1 , y2 , y3 , y4 , y5 ≥ 0 利用單純形法： maxw’= 15y124y25y3 +0y4 +0y5My6My7 6y2+y3 y4 +y6 = 2 5y1 +2y2 +y3 y5 +y7 =1 y1 , y2 , y3 , y4 , y5 , y6 , y7≥ 0 一、 用對偶單純形方法解線性規(guī)劃 對偶單純形方法 是使用對偶原理求解原問題解的一種方法，而不是求解對偶問題解的單純形方法。與對偶單純形方法相對應(yīng)，原已有的單純形方法稱 原始單純形方法 。 用對偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標(biāo)準(zhǔn)型是： minZ=15y1+24y2+5y3 6y2+y3 ≥ 2 5y1 +2y2 +y3 ≥1 y1 , y2 , y3 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2+y3 y4 = 2 5y1 +2y2 +y3 y5 =1 y1 , y2 , y3 , y4 , y5 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 對偶單純形方法 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/3 0 1 1/6 1/6 0 1/3 5 0 2/3 1/3 1 Y2 y5 24 0 8 15 0 1 4 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 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 最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， maxw*=17/2 – 4 5 3 – 12 MinZ=17/2 應(yīng)用對偶單純形方法之矩陣法 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 0 0 5 24 15 W’ 1 1 1 2 5 0 2 0 1 6 0 0 0 0 1 ～ 8 0 1 0 15 W’ 1/3 1 2/3 0 5 0 1/3 0 1/6 1 0 0 4 1/3 1/6 ～ 17/2 3/2 0 0 15/2 W’ 1/2 3/2 1 0 15/2 0 1/4 0 0 1 5/4 0 7/2 1/2 1/4 最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， max w*=17/2 Min Z=17/2 兩種方法的主要 區(qū)別 在于： 而對偶單純形方法在整個迭代過程中，則是始終保持 對偶問題的可行性 即 亦即 , ，也就是全部檢驗數(shù) ≤0，最后達(dá)到全部右邊項所有負(fù)分量逐步變?yōu)槿坑疫呿?≥0,即滿足原問題的可行性時為止。 CyA ? 0?? yAC 所以 ,對偶單純形方法實質(zhì) 就是在保證對偶問題可行的條件下向原問題可行的方向迭代。 ABCC B 1?? 0?? yAC 原始單純形方法在整個迭代過程中，始終是保持 原問題的可行性 ， 最后達(dá)到檢驗數(shù) 即 即 maxZ取得最優(yōu)值時為止。 2560 24 14 0 0 Z 16 2/5 1/10 0 1 0 12 1/5 3/10 1 0 0 相當(dāng)于：直到對偶問題的解可行為止 相當(dāng)于：即直到原問題的解可行為止 用對偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標(biāo)準(zhǔn)型是： minZ=2x1+3x2+4x3 x1+ 2x2+x3 ≥ 3 2x1 x2 +3x3 ≥4 x1 , x2 , x3 ≥ 0 maxZ’= 2x13x24x3 +0x4 +0x5 x1+ 2x2+x3 x4 = 3 2x1 x2 +3x3 x5 =4 x1 , x2 , x3 , x4 , x5 ≥ 0 maxw’= 2x13x24x3 +0x4 +0x5 x1 2x2 x3 +x4 = 3 2x1 + x2 3x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0 應(yīng)用對偶單純形方法之矩陣法 0 0 4 3 2 W’ 4 1 3 1 2 0 3 0 1 2 1 0 0 0 1 ～ 4 1 1 4 0 W’ 2 1/2 3/2 1/2 1 0 1 1/2 1/2 5/2 0 0
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1