對(duì)偶理論與影子價(jià)格(編輯修改稿)
2025-06-20 08:35 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ??? ? ??? ? ? ? ???? ? ??? ? ? ? ??? ? ??? ??管 理 運(yùn) 籌 學(xué) 變量替換，令 16 1 2 31 2 31 2 31 2 31 2 3m i n 2 42 3 1345 6 30 , 0 ,y y yy y yy y yy y yy y y? ? ?? ? ???? ? ???? ? ? ??? ???無(wú) 非 負(fù) 限 制2 2 3 3 3,y y y y y? ? ??? ? ? ?管 理 運(yùn) 籌 學(xué) 把對(duì)偶問(wèn)題和原問(wèn)題進(jìn)行比較 17 Max z = x1 + 4 x2 + 3 x3 . 2 x1 + 3 x2 – 5 x3 ≤ 2 原問(wèn)題 3 x1 – x2 + 6 x3 ≥ 1 x1 + x2 + x3 = 4 x1 ≥ 0， x2 ≤ 0， x3 沒(méi)有非負(fù)限制 Min f = 2 y1 + y2 + 4 y3 . 2 y1 + 3 y2 + y3 ≥ 1 對(duì)偶問(wèn)題 3 y1 – y2 + y3 ≤ 4 – 5 y1 + 6 y2 + y3 = 3 y1≥ 0 ， y2 ≤ 0， y3無(wú)非負(fù)限制 管 理 運(yùn) 籌 學(xué) 由此得到非對(duì)稱形式的線性規(guī)劃原問(wèn)題和對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（對(duì)稱形式也適用） 18 原問(wèn)題 對(duì)偶問(wèn)題 A 約束系數(shù)矩陣 約束系數(shù)矩陣的轉(zhuǎn)置 b 約束條件右端項(xiàng) 目標(biāo)函數(shù)中的系數(shù) C 目標(biāo)函數(shù)中的系數(shù) 約束條件右端項(xiàng) 目標(biāo)函數(shù) Max z = Σcj xj Min z = Σbi yi 變量 n個(gè) xj ≥0(≤0 ，無(wú)限制 ) 約束條件 n個(gè) Σaij yj≥(≤ ， =)cj 約束條件 m個(gè) Σaij xj≤(≥ ， =)bi 變量 m個(gè) yi≥0(≤0 ，無(wú)限制 ) 管 理 運(yùn) 籌 學(xué) 對(duì)偶問(wèn)題的基本性質(zhì) 對(duì)偶問(wèn)題的基本性質(zhì)對(duì)對(duì)稱形式和非對(duì)稱形式都是同樣適用的，但為了方便，在說(shuō)明或證明時(shí)以對(duì)稱形式為例（非對(duì)稱形式可以化為對(duì)稱形式） 對(duì)稱形式下原 (Primal)問(wèn)題和對(duì)偶 (Dual)問(wèn)題如下： (P) Max z = CX (D) Min f = YTb . AX ≤ b . ATY ≥ CT X ≥ 0 Y ≥ 0 ―Max ≤ ‖ ―Min ≥‖ 19 管 理 運(yùn) 籌 學(xué) ? 1． 對(duì)稱性 。即對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。 20 管 理 運(yùn) 籌 學(xué) 2.（弱對(duì)偶定理）若 X， Y分別為（ P) 和（ D）的可行解，那么 CX ≤ YTb。 證明：由變量的非負(fù)性限制，可以得到 21 管 理 運(yùn) 籌 學(xué) 弱對(duì)偶定理的推論： 1.（ P）任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；（ D）任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。 2. 若（ P）可行，那么（ P）無(wú)有限最優(yōu)解的充分必要條件是（ D）無(wú)可行解。 3. 若（ D）可行，那么（ D）無(wú)有限最優(yōu)解的充分必要條件是（ P）無(wú)可行解。 4. 若（ P）、（ D）可行，那么（ P）、（ D）都有最優(yōu)解。 22 管 理 運(yùn) 籌 學(xué) 3.（最優(yōu)性準(zhǔn)則定理）若 X’， Y’分別為 (P)， (D)的可行解，且 CTX’=Y’Tb，則 X’， Y’分別為 (P)和 (D)的最優(yōu)解。 證明：設(shè) X 為 (P)的可行解，由弱對(duì)偶定理可得 CTX ≤ Y’Tb
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1