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