對偶理論與影子價(jià)格-文庫吧
2025-04-25 08:35 本頁面
【正文】 解 可以看到，這兩個(gè)問題關(guān)系密切，用同樣的原始數(shù)據(jù)： 管 理 運(yùn) 籌 學(xué) 線性規(guī)劃有一個(gè)有趣的特性，就是對于任何一個(gè)求極大的線性規(guī)劃問題都存在一個(gè)與其匹配的求極小的線性規(guī)劃問題，并且這一對線性規(guī)劃問題的解之間還存在著密切的關(guān)系。線性規(guī)劃的這個(gè)特性稱為對偶性。 對這兩個(gè)線性規(guī)劃問題，一般稱前者為原問題，后者是前者的對偶問題 8 管 理 運(yùn) 籌 學(xué) 對偶問題的形式 9 如果線性規(guī)劃問題的變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大值時(shí)均取“ ≤ ”，當(dāng)目標(biāo)函數(shù)求極小值時(shí)均取“ ≥ ”，則稱具有對稱形式。 對稱形式下原問題和對偶問題的形式： （ LP） m ax z C X?0AX bX??“Max —— ≤” . m i n Tz Y b?（ DP） 0TTA Y CY??“Min —— ≥” . 管 理 運(yùn) 籌 學(xué) 一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系： “極大”，約束為“小于等于”的不等式，則它的對偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“ max， ≤”和“ min， ≥”相對應(yīng)。 ：一個(gè)模型中為Ａ，則另一個(gè)模型中為 AT。一個(gè)模型是 m個(gè)約束， n個(gè)變量，則它的對偶模型為 n個(gè)約束， m個(gè)變量 b、 C的位置看：在兩個(gè)規(guī)劃模型中， b和 C的位置對換 10 管 理 運(yùn) 籌 學(xué) 11 Max z Min f x1 x2 ? xn xi ≥0 y1 a11 a12 ? a1n ≤ b1 y2 a21 a22 ? a2n ≤ b2 ? ? ? ? ? ≤ ? ym am1 am2 ? amn ≤ bm yi ≥0 c1 c2 ? ≥ ≥ ≥ ≥ 管 理 運(yùn) 籌 學(xué) 一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。 對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系進(jìn)行處理并給出其對偶規(guī)劃： 1. 將模型統(tǒng)一為“ max， ≤”或“ min， ≥” 的形式，對于其中的等式約束按下面的方法處理； 2. 若原規(guī)劃的某個(gè)約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個(gè)變量取值沒有非負(fù)限制； 3. 若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限制，則在對偶問題中與此變量對應(yīng)的那個(gè)約束為等式。 也可以直接給出其對偶規(guī)劃。 12 管 理 運(yùn) 籌 學(xué) 例 2：寫出下面線性規(guī)劃的對偶規(guī)劃模 13 1 2 31 2 31 2 31 2 31 2 3m a x 4 32 3 5 23 6 140 , 0 ,z x x xx x xx x xx x xx x x? ? ?? ? ???? ? ???? ? ??? ??? 沒 有 非 負(fù) 限 制..st管 理 運(yùn) 籌 學(xué) 解：先化為對稱形式（ Max—≤） “ ≥”的約束兩端同乘以“ –1‖ ―=‖的約束等價(jià)轉(zhuǎn)換為“ ≤”和“ ≥”的兩個(gè)約束，再變換 變量 ≤0，用變量替換，如 變量無非負(fù)限制，用變量替換，如 14 22=xx?3 3 3x x x? ????1 2 3 31 2 3 31 2 3 31 2 3 31 2 3 31 2 3 3m a x 4 3 32 3 5 5 23 6 6 144, , , 0z x x x xx x x xx x x xx x x xx x x xx x x x? ? ??? ? ? ?? ? ??? ? ? ???? ? ??? ? ? ? ? ???? ? ??? ? ? ???? ? ??? ? ? ? ? ??? ? ??? ??管 理 運(yùn) 籌 學(xué) 寫出對偶問題： 15 1 2 3 31 2 3 31 2 33 331 2 33 331 22 33 331 2 33 3m i n 2 4 42 3 1345 6 35 6 3, , , 0f y y y yy y y yy y y yy y y yy y y yy y y y? ? ??? ? ? ?? ? ??? ? ? ???? ? ??? ? ? ? ? ?
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1