修正對偶ppt課件(編輯修改稿)
2025-06-02 03:05 本頁面
【文章內(nèi)容簡介】 bm x1 ， x2 ， … ， xn ≥ 0 對偶規(guī)劃的形式 (1)對稱形式的對偶關(guān)系 (規(guī)范型的線性規(guī)劃 ) 上一頁 下一頁 返回 Min f = b1y1 + b2 y2 + … + bn ym . a11 y1 + a21 y2 + … + am1 ym ≥ c1 a12 y1 + a22 y2 + … + am2 ym ≥c2 …… …… a1n y1 + a2n y2 + … + amn ym ≥ y1 ， y2 ， … ， ym ≥ 0 一對對稱形式的對偶規(guī)劃之間具有下面的對應關(guān)系 。 原問題記為 LP,對偶問題記為 DP 上一頁 下一頁 返回 LP問題為目標最大化， DP問題為最小化 。 LP問題的約束為 “ ≤” ,DP問題的約束為 “ ≥” 。 LP的價值系數(shù) ci ,在 DP問題中恰好為約束右端項 。 LP的約束右端項 bi ,在 DP問題中恰好為價值系數(shù) 。 LP中的每個約束條件對應著 DP問題中的一個變量 ,而 LP中的每個決策變量對應著 DP問題中的一個約束 。 Max z = c1 x1 + c2 x2 + … + xn . a11 x1 + a12 x 2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1+ am2 x2 + … + amn xn ≤ bm x1 ， x2 ， … ， xn ≥ 0 Min f = b1y1 + b2 y2 + … + bn ym . a11 y1 + a21 y2 + … + am1 ym ≥ c1 a12 y1 + a22 y2 + … + am2 ym ≥c2 …… …… a1n y1 + a2n y2 + … + amn ym ≥ y1 ， y2 ， … ， ym ≥ 0 1) 2) 3) 4) 5) 上一頁 下一頁 返回 (LP) Max z = CTX . AX ≤ b X ≥ 0 Max z = c1 x1 + c2 x2 + … + xn . a11 x1 + a12 x 2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1+ am2 x2 + … + amn xn ≤ bm x1 ， x2 ， … ， xn ≥ 0 Max f = b1y1 + b2 y2 + … + bm ym . a11 y1 + a21 y2 + … + am1 ym ≥ c1 a12 y1 + a22 y2 + … + am2 ym ≥c2 …… …… a1n y1 + a2n y2 + … + amn ym ≥ cm y1 ， y2 ， … ， ym ≥ 0 LP與 DP的矩陣的形式 (DP) Min f = bT y . AT y ≥ C y ≥ 0 上一頁 下一頁 返回 (2)非對稱形式的對偶關(guān)系 Max z = 2x1 + 4 x2 . x1 + x 2 = 1 3x1 + 2 x2 ≤ 3 x1 , x 2 ≥0 Max z = 2x1 + 4 x2 . x1 + x 2 ≤ 1 x1 x2 ≤ 1 3x1 + 2 x2 ≤ 3 Min y1 y2 +3y3 . y1 y2 3y3 ≥ 2 y1 y2 +2y3 ≥ 4 y1 , y2 ,y3, ≥ 0 令 y1 y2 = y4 Min y4 +3y3 . y4 3y3 ≥ 2 y4 +2y3 ≥ 4 y3 ≥ 0 上一頁 下一頁 返回 若 LP問題的某個約束條件為等式約束 ， 則在對偶 DP問題中與此約束對應著一個變量且那個變量取值無非負限制； Min y1 +3y2 . y1 3y2 ≥ 2 y1 +2y2≥ 4 y2 ≥ 0 Max z = 2x1 + 4 x2 . x1 + x 2 = 1 3x1 + 2 x2 ≤ 3 x1 , x 2 ≥0 上一頁 下一頁 返回 Max z = 2x1 + 3 x2 . x1 + x 2 ≤ 1 3x1 + 2 x2 ≤ 3 x1 ≥0 令 x/2 – x//2 = x2 Max z = 2x1 + 3 x/2 – 3x//2 . x1 + x/2 –x//2 ≤ 1 3x1 + 2 x/2 –2x//2 ≤ 3 x1, x/2 ,x//2 ≥0 Min y1 +3y2 . y1 3y2 ≥ 2 y1 +2y2≥ 3 y1 2y2≥ 3 y1 y2≥ 0 Min y1 +3y2 . y1 3y2 ≥ 2 y1 +2y2= 3 y1 y2≥ 0 若 LP問題的某個變量的值沒有非負限制 ， 則在對偶 DP問題中與此變量對應的那個約束為等式 。 上一頁 下一頁 返回 （ 1） 將模型統(tǒng)一為 “ max， ≤ ” 或 “ min， ≥ ” 的形式對于其中的等式約束按下面 (2)、 (3)中的方法處理； 對于非對稱形式的規(guī)劃，可以按照下面的對應關(guān)系直接給出其對偶規(guī)劃 : （ 2） 若 LP問題的某個約束條件為等式約束 ， 則在對偶
教學課件相關(guān)推薦
鄂ICP備17016276號-1