運(yùn)籌學(xué)02對(duì)偶理論1線性規(guī)劃的對(duì)偶模型,對(duì)偶性質(zhì)(編輯修改稿)
2025-06-17 15:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ) 約束條件系數(shù)矩陣 A(AT) 目標(biāo)函數(shù) min 資源限量 (目標(biāo)函數(shù)系數(shù) ) 約束條件系數(shù)矩陣 AT(A) 變 量 n個(gè)變量 第 j個(gè)變量 ≥0 第 j 個(gè)變量 ≤0 第 j個(gè)變量無(wú)約束 約 束 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è)變量無(wú)約束 線性規(guī)劃的對(duì)偶模型 Dual model of LP 問(wèn)題 ：討論一般形式的線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題？ 方法： 先將其轉(zhuǎn)化為規(guī)范形式的線性規(guī)劃問(wèn)題，然后寫(xiě)出其對(duì)偶問(wèn)題，適當(dāng)將其進(jìn)行化簡(jiǎn)。 對(duì)偶性質(zhì) (了解 ) Dual property Chapter3 對(duì)偶理論 Dual Theory ??????0m a xXbAXCXZ對(duì)偶問(wèn)題是 (記為 DP)： ??????0m i nYCYAYbw這里 A是 m n矩陣 , X是 n 1列向量 , Y是 1 m行向量 。 【 性質(zhì) 1】 對(duì)稱性 : 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。 設(shè)原問(wèn)題是 (記為 LP)： 對(duì)偶性質(zhì) Dual property 對(duì)偶性質(zhì) 【 性質(zhì) 2】 弱對(duì)偶性 : 設(shè) X*、 Y*分別為 LP(max)與 DP(min)的可行解，則 bYCX ** ?Chapter3 對(duì)偶理論 Dual Theory 對(duì)偶性質(zhì) Dual property 由這個(gè)性質(zhì)可得到下面幾個(gè) 結(jié)論 ： (1) (LP) 的任一可行解的目標(biāo)值是 (DP) 的最優(yōu)值下 界； (DP)的任一可行解的目標(biāo)是 (LP)的最優(yōu)值的上界； (2) 在互為對(duì)偶的兩個(gè)問(wèn)題中 ， 若一個(gè)問(wèn)題可行且具有無(wú)界解 ， 則另一個(gè)問(wèn)題無(wú)可行解； (3) 若原問(wèn)題可行且另一個(gè)問(wèn)題不可行，則原問(wèn)題具 有無(wú)界解。 注意 : 上述結(jié)論 (2)及 (3)的條件不能少 。 一個(gè)問(wèn)題無(wú)可行解時(shí) ， 另一個(gè)問(wèn)題可能有可行解 (此時(shí)具有無(wú)界解 )也可能無(wú)可行解 。 **( ( m a x ) ) ( ( m i n ) )L P D PC X Y b?Chapter3 對(duì)偶理論 Dual Theory 例如： ???????????????0,22212m i n21212121xxxxxxxxz無(wú)可行解 ， 而對(duì)偶問(wèn)題 ??????????????0,221122m a x21212121yyyyyyyyw有可行解 ， 由結(jié)論 (3)知必有無(wú)界解 。 對(duì)偶性質(zhì) Dual property Chapter3 對(duì)偶理論 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 . 對(duì)偶性質(zhì) Dual property 【 性質(zhì) 4】 對(duì)偶性： 若互為對(duì)偶的兩個(gè)問(wèn)題其中一個(gè)有最優(yōu)解 ， 則另一個(gè)也有最優(yōu)解 ， 且最優(yōu)值相同 。 另一結(jié)論 ：若 (LP)與 (DP)都有可行解 ， 則兩者都有最優(yōu)解 ， 若一個(gè)問(wèn)題無(wú)最優(yōu)解 ， 則另一問(wèn)題也無(wú)最優(yōu)解 。 【 性質(zhì) 5】 互補(bǔ)松弛定理 : 設(shè) X*、 Y*分別為 (LP) 與 (DP) 的可行解 ， XS和 YS分別 是它們的松弛變量的可行解 ， 則X*和 Y*是最優(yōu)解當(dāng)且僅當(dāng) YSX*=0 和 Y*XS=0 Chapter3 對(duì)偶理論 Dual Theory 性質(zhì) 5告訴我們已知一個(gè)問(wèn)題的最優(yōu)解時(shí)求另一個(gè)問(wèn)題的最優(yōu)解的方法 ， 即已知 Y*求 X*或已知 X*求 Y*。 Y * XS = 0 和 YS X * = 0 兩式稱為 互補(bǔ)松弛條件 。 將互補(bǔ)松弛條件寫(xiě)成下式 *1*100ijmiSinSjjyxyx??????由于變量都非負(fù) ， 要使求和式等于零 ， 則必定每一分量為零 ， 因而有下列關(guān)系： 對(duì)偶性質(zhì) Dual property Chapter3 對(duì)偶理論 Dual Theory (1)當(dāng) yi*0時(shí) ， ,
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1