chapter3對偶理論dualtheory(編輯修改稿)
2024-11-23 04:05 本頁面
【文章內(nèi)容簡介】 ,03354751086m in321321321iyyyyyyyyyywi 線性規(guī)劃的對偶模型 Dual model of LP Chapter3 對偶理論 Dual Theory 線性規(guī)劃問題的 規(guī)范形式 (Canonical Form 或叫 對稱形式 ) ： 定義： 目標(biāo)函數(shù)求 極大值 時(shí)，所有約束條件 為 ≤號 ， 變量非負(fù) ； 目標(biāo)函數(shù)求 極小值 時(shí)，所有約束條件 為 ≥號，變量非負(fù) 。 線性規(guī)劃的對偶模型 Dual model of LP ??????0)(m a xXbAXCXZ??????0)(m i nXbAXCXZ注： (1)線性規(guī)劃規(guī)范形式與標(biāo)準(zhǔn)型是兩種不同形式，但可以 相互轉(zhuǎn)換。 (2)規(guī)范形式的線性規(guī)劃問題的對偶仍然是規(guī)范形式． Chapter3 對偶理論 Dual Theory 原問題 (或?qū)ε紗栴} ) 對偶問題 (或原問題 ) 目標(biāo)函數(shù) max 目標(biāo)函數(shù)系數(shù) (資源限量 ) 約束條件系數(shù)矩陣 A(AT) 目標(biāo)函數(shù) min 資源限量 (目標(biāo)函數(shù)系數(shù) ) 約束條件系數(shù)矩陣 AT(A) 變 量 n個(gè)變量 第 j個(gè)變量 ≥0 第 j 個(gè)變量 ≤0 第 j個(gè)變量無約束 約 束 n個(gè)約束 第 j個(gè)約束為 ≥ 第 j個(gè)約束為 ≤ 第 j個(gè)約束為 = 約 束 m個(gè)約束 第 i個(gè)約束 ≤ 第 i個(gè)約束 ≥ 第 i個(gè)約束為 = 變 量 m個(gè)變量 第 i個(gè)變量 ≥0 第 i個(gè)變量 ≤0 第 i個(gè)變量無約束 線性規(guī)劃的對偶模型 Dual model of LP 問題 ：討論一般形式的線性規(guī)劃問題的對偶問題？ 方法： 先將其轉(zhuǎn)化為規(guī)范形式的線性規(guī)劃問題，然后寫出其對偶問題，適當(dāng)將其進(jìn)行化簡。 (具體過程見書本 P40) 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory ??????0m a xXbAXCXZ對偶問題是 (記為 DP)： ??????0m inYCYAYbw這里 A是 m n矩陣 , X是 n 1列向量 , Y是 1 m行向量 。 【 性質(zhì) 1】 對稱性 : 對偶問題的對偶是原問題。 設(shè)原問題是 (記為 LP)： 對偶性質(zhì) Dual property 對偶性質(zhì) 【 性質(zhì) 2】 弱對偶性 : 設(shè) X*、 Y*分別為 LP(max)與 DP(min)的可行解，則 bYCX ** ?Chapter3 對偶理論 Dual Theory 對偶性質(zhì) Dual property 由這個(gè)性質(zhì)可得到下面幾個(gè) 結(jié)論 ： (1) (LP) 的任一可行解的目標(biāo)值是 (DP) 的最優(yōu)值下 界； (DP)的任一可行解的目標(biāo)是 (LP)的最優(yōu)值的上界； (2) 在互為對偶的兩個(gè)問題中 ， 若一個(gè)問題可行且具有無界解 ， 則另一個(gè)問題無可行解； (3) 若原問題可行且另一個(gè)問題不可行，則原問題具 有無界解。 注意 : 上述結(jié)論 (2)及 (3)的條件不能少 。 一個(gè)問題無可行解時(shí) ， 另一個(gè)問題可能有可行解 (此時(shí)具有無界解 )也可能無可行解 。 **( ( m a x ) ) ( ( m i n ) )L P D PC X Y b?Chapter3 對偶理論 Dual Theory 例如： ???????????????0,22212m in21212121xxxxxxxxz無可行解 ， 而對偶問題 ??????????????0,221122m a x21212121yyyyyyyyw有可行解 ， 由結(jié)論 (3)知必有無界解 。 對偶性質(zhì) Dual property Chapter3 對偶理論 Dual Theory 【 性質(zhì) 3】 最優(yōu)準(zhǔn)則定理 : 設(shè) X*與 Y*分別是 (LP)與 (DP)的可行解 ， 則 X*、 Y*是 (LP)與 (DP)的最優(yōu)解當(dāng)且僅當(dāng) C X*= Y*b . 對偶性質(zhì) Dual property 【 性質(zhì) 4】 對偶性： 若互為對偶的兩個(gè)問題其中一個(gè)有最優(yōu)解 ， 則另一個(gè)也有最優(yōu)解 ， 且最優(yōu)值相同 。 另一結(jié)論 ：若 (LP)與 (DP)都有可行解 ， 則兩者都有最優(yōu)解 ， 若一個(gè)問題無最優(yōu)解 ， 則另一問題也無最優(yōu)解 。 【 性質(zhì) 5】 互補(bǔ)松弛定理 : 設(shè) X*、 Y*分別為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1