對(duì)偶理論與影子價(jià)格

1、對(duì)偶理論與影子價(jià)格第1頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三2對(duì)偶問題的提出第2頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三例1：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：?jiǎn)栴}：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？ 產(chǎn)品甲產(chǎn)品乙設(shè)備能力設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)15002500 現(xiàn)在從另一個(gè)角度來討論該問題： 如果工廠考慮不安排生產(chǎn)，而準(zhǔn)備把所有設(shè)備出租（或用于外協(xié)加工），工廠收取租金（或加工費(fèi)）。試問：設(shè)備 A、B、C 每工時(shí)各如何

2、收費(fèi)（租金或加工費(fèi)）才最有競(jìng)爭(zhēng)力？ 工廠為了獲得最大利潤(rùn)，在為設(shè)備定價(jià)時(shí)，應(yīng)保證生產(chǎn)某產(chǎn)品的設(shè)備工時(shí)所收取的費(fèi)用不低于生產(chǎn)該產(chǎn)品的利潤(rùn)；同時(shí)，為了提高競(jìng)爭(zhēng)力，應(yīng)該使定價(jià)盡可能低。目標(biāo)函數(shù)設(shè)x1，x2分別為生產(chǎn)甲乙兩種產(chǎn)品的件數(shù)約束條件 設(shè) y1 ，y2 ，y3 分別為每工時(shí)設(shè)備 A、B、C 的收費(fèi)。目標(biāo)函數(shù)約束條件第3頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三4 解： 可以建立如下的線性規(guī)劃模型： 目標(biāo)函數(shù) 約束條件 化為標(biāo)準(zhǔn)型，利用單純形法進(jìn)行求解。 最優(yōu)解X=(5, 25, 0, 5, 0)， 最優(yōu)值（利潤(rùn)）為70000。 第4頁，共35頁，2022年，5月20日，1點(diǎn)57分

3、，星期三5 解： 設(shè) y1 ，y2 ，y3 分別為每工時(shí)設(shè)備 A、B、C 的收費(fèi)。可以建立以下線性規(guī)劃模型： 化為標(biāo)準(zhǔn)型，利用單純形法進(jìn)行求解。 最優(yōu)解Y=(500, 0, 500, 0, 0) 最優(yōu)值（收費(fèi)）為70000。 第5頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三6原問題對(duì)偶問題第6頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三7原問題對(duì)偶問題目標(biāo)函數(shù) Max Min約束條件系數(shù)矩陣AAT資源常數(shù)b c目標(biāo)系數(shù)cb2個(gè)變量2個(gè)約束 3個(gè)約束 3個(gè)變量解 檢驗(yàn)數(shù)檢驗(yàn)數(shù)解可以看到，這兩個(gè)問題關(guān)系密切，用同樣的原始數(shù)據(jù)：第7頁，共35頁，2022年，5月20日，1點(diǎn)5

4、7分，星期三 線性規(guī)劃有一個(gè)有趣的特性，就是對(duì)于任何一個(gè)求極大的線性規(guī)劃問題都存在一個(gè)與其匹配的求極小的線性規(guī)劃問題，并且這一對(duì)線性規(guī)劃問題的解之間還存在著密切的關(guān)系。線性規(guī)劃的這個(gè)特性稱為對(duì)偶性。 對(duì)這兩個(gè)線性規(guī)劃問題，一般稱前者為原問題，后者是前者的對(duì)偶問題8第8頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三對(duì)偶問題的形式9 如果線性規(guī)劃問題的變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大值時(shí)均取“”，當(dāng)目標(biāo)函數(shù)求極小值時(shí)均取“”，則稱具有對(duì)稱形式。對(duì)稱形式下原問題和對(duì)偶問題的形式：（LP）“Max”s.t.（DP）“Min”s.t.第9頁，共35頁，2022年，5月20日，1點(diǎn)

5、57分，星期三一對(duì)對(duì)稱形式的對(duì)偶規(guī)劃之間具有下面的對(duì)應(yīng)關(guān)系： 1.若一個(gè)模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對(duì)偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，”和“min，”相對(duì)應(yīng)。 2.從約束系數(shù)矩陣看：一個(gè)模型中為，則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量 3.從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型中，b和C的位置對(duì)換 4.兩個(gè)規(guī)劃模型中的變量皆非負(fù)10第10頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三11Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2y

6、mam1am2amnbmyi 0c1c2cn第11頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)偶規(guī)劃。 對(duì)于非對(duì)稱形式的規(guī)劃，可以按照下面的對(duì)應(yīng)關(guān)系進(jìn)行處理并給出其對(duì)偶規(guī)劃： 1. 將模型統(tǒng)一為“max，”或“min，” 的形式，對(duì)于其中的等式約束按下面的方法處理； 2. 若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒有非負(fù)限制； 3. 若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限制，則在對(duì)偶問題中與此變量對(duì)應(yīng)的那個(gè)約束為等式。 也可以直接給出其對(duì)偶規(guī)劃。12第12頁，共35頁，2022年，5月20日，1點(diǎn)57分

7、，星期三例2：寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模13第13頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三解：先化為對(duì)稱形式（Max） “”的約束兩端同乘以“1” “=”的約束等價(jià)轉(zhuǎn)換為“”和“”的兩個(gè)約束，再變換 變量0，用變量替換，如 變量無非負(fù)限制，用變量替換，如 14第14頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三寫出對(duì)偶問題：15第15頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三變量替換，令16第16頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三把對(duì)偶問題和原問題進(jìn)行比較 17 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1

8、 + 3 x2 5 x3 2原問題 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 沒有非負(fù)限制 Min f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1對(duì)偶問題 3 y1 y2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3無非負(fù)限制第17頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 由此得到非對(duì)稱形式的線性規(guī)劃原問題和對(duì)偶問題的對(duì)應(yīng)關(guān)系（對(duì)稱形式也適用）18原問題對(duì)偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件右端項(xiàng)目標(biāo)函數(shù)中的系數(shù)C目標(biāo)函數(shù)中的系數(shù)約束條

9、件右端項(xiàng)目標(biāo)函數(shù)Max z = cj xjMin z = bi yi變量n個(gè) xj 0(0，無限制)約束條件n個(gè)aij yj(，=)cj約束條件m個(gè)aij xj(，=)bi變量m個(gè) yi0(0，無限制)第18頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三對(duì)偶問題的基本性質(zhì) 對(duì)偶問題的基本性質(zhì)對(duì)對(duì)稱形式和非對(duì)稱形式都是同樣適用的，但為了方便，在說明或證明時(shí)以對(duì)稱形式為例（非對(duì)稱形式可以化為對(duì)稱形式） 對(duì)稱形式下原(Primal)問題和對(duì)偶(Dual)問題如下： (P) Max z = CX (D) Min f = YTb s.t. AX b s.t. ATY CT X 0 Y 0 “M

10、ax - ” “Min- ”19第19頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三1對(duì)稱性。即對(duì)偶問題的對(duì)偶是原問題。20第20頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 2.（弱對(duì)偶定理）若X，Y分別為（P) 和（D）的可行解，那么CX YTb。證明：由變量的非負(fù)性限制，可以得到21第21頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三弱對(duì)偶定理的推論： 1.（P）任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；（D）任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。 2. 若（P）可行，那么（P）無有限最優(yōu)解的充分必要條件是（D）無可行解。 3. 若（

11、D）可行，那么（D）無有限最優(yōu)解的充分必要條件是（P）無可行解。 4. 若（P）、（D）可行，那么（P）、（D）都有最優(yōu)解。22第22頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 3.（最優(yōu)性準(zhǔn)則定理）若X，Y分別為(P)，(D)的可行解，且CTX=YTb，則X，Y分別為(P)和(D)的最優(yōu)解。 證明：設(shè) X 為(P)的可行解，由弱對(duì)偶定理可得 CTX YTb = CTX因此 X 為(P) 的最優(yōu)解。設(shè) Y 為(D)的可行解，由弱對(duì)偶定理可得 YTb CTX = YTb因此 Y 為(D) 的最優(yōu)解。23第23頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 4.（主對(duì)偶定理

12、）若(P)和(D)均可行，那么(P)和(D)均有最優(yōu)解，且最優(yōu)值相等。證明：若(P)和(D)均可行，則由弱對(duì)偶定理的推論知 (P)和(D)均有最優(yōu)解。 設(shè)(P)的最優(yōu)基為B，令YT= CBB-1，由=C - CBB-1A 0，對(duì)于松弛變量部分，目標(biāo)函數(shù)系數(shù)為0，系數(shù)矩陣為單位陣，檢驗(yàn)數(shù)為= - CBB-10，故Y0，且YTAC，ATY CT，因此 Y 為(D)的可行解。 目標(biāo)YTb = CBB-1b = CX（原問題最優(yōu)值），由最優(yōu)性準(zhǔn)則定理知 Y 為 (D) 的最優(yōu)解注：(P) 松弛變量的檢驗(yàn)數(shù)的絕對(duì)值是(D)的基可行解推論：(P)有最優(yōu)解的充分必要條件是(D)有最優(yōu)解24第24頁，共35頁

13、，2022年，5月20日，1點(diǎn)57分，星期三對(duì)稱形式下原問題和對(duì)偶問題的標(biāo)準(zhǔn)形式如下 5.（互補(bǔ)松弛定理）若X 和Y 分別是 (P)和(D)的最優(yōu)解（對(duì)稱形式的標(biāo)準(zhǔn)型下），則有即約束取等式或?qū)?yīng)的變量為025第25頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三證明：由弱對(duì)偶定理（CXYTb）得由主對(duì)偶定理可知最優(yōu)值相等，上述不等式取“=”，26第26頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三對(duì)偶問題基本性質(zhì)的應(yīng)用： 利用單純形法，求得對(duì)偶問題最優(yōu)解 X=(1, 0, 0, 2, 0)T，最優(yōu)值 z* = 9。 由互補(bǔ)松弛定理，得 x1 y3 = 0， x2 y4 = 0

14、，x3 y5 = 0，x4 y1 = 0， x5 y2 =0，因此有 y1 = 0，y3 = 0，代入第1個(gè)約束得到y(tǒng)2 = 9，代入其余約束得 y4 = 4， y5 = 64。 對(duì)于變量數(shù)量少、約束多的問題，可以利用基本性質(zhì)簡(jiǎn)化求解27例4： Min f = 5 y1 + y2 s.t. 3 y1 + y2 9 y1 + y2 5 y1 + 8 y2 8 y1，y2 0 Max z = 9 x1 + 5 x2 + 8 x3 s.t. 3 x1 + x2 + x3 5 x1 + x2 + 8 x3 1 x1， x2， x3 0 第27頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三影子

15、價(jià)格 影子價(jià)格 (Shadow Price) 的概念： 若X*，Y* 分別為（P）和（D）的最優(yōu)解，則 z = CX* = Y*Tb = f 根據(jù) z = b1y1*+b2y2*+bmym* 可知 z / bi = yi* 其中bi表示第 i 種資源的擁有量， yi*表示 bi 變化1個(gè)單位對(duì)目標(biāo) z 產(chǎn)生的影響，也是在資源最優(yōu)利用條件下對(duì)該資源的估價(jià)，稱為該資源的影子價(jià)格 例如，在例1中 yi* 是對(duì)設(shè)備租金的估價(jià)注意：若 B 是最優(yōu)基， y*T = CBB-128第28頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三影子價(jià)格的經(jīng)濟(jì)含義及應(yīng)用： 資源的市場(chǎng)價(jià)格是已知的，且相對(duì)比較穩(wěn)定

16、，而影子價(jià)格有賴于資源的利用情況，是未知數(shù)，隨著企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況的變化而發(fā)生變化。 影子價(jià)格是一種邊際價(jià)格，說明在資源得到最優(yōu)利用的條件下，增加單位資源量可以增加的收益。 影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià)，實(shí)際上是一種機(jī)會(huì)成本。企業(yè)可以根據(jù)現(xiàn)有資源的影子價(jià)格，考慮經(jīng)營(yíng)策略：如果影子價(jià)格高于市場(chǎng)價(jià)格，可考慮買進(jìn)設(shè)備，以擴(kuò)大生產(chǎn)能力，否則不宜買進(jìn)；若某設(shè)備的租費(fèi)高于影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租29第29頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 由互補(bǔ)松弛定理，可知如果某種資源未得到充分利用時(shí)（松弛變量不為0），則其影子價(jià)格為0（對(duì)應(yīng)變量為0）；當(dāng)

17、資源的影子價(jià)格不為0，表明該資源在生產(chǎn)中已耗費(fèi)完畢。 從影子價(jià)格的含義上來考察檢驗(yàn)數(shù)j = cj - aij yi， 其中 cj 表示產(chǎn)品的價(jià)值，aij yi是生產(chǎn)該產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品的價(jià)值大于隱含成本時(shí)，表明生產(chǎn)該產(chǎn)品有利；否則就不安排生產(chǎn)。這就是檢驗(yàn)數(shù)的經(jīng)濟(jì)含義。 影子價(jià)格反映了不同的局部或個(gè)體的增量可以獲得不同的整體經(jīng)濟(jì)效益。如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價(jià)格高的設(shè)備入手，以較少的局部努力，獲得較大的整體效益。30第30頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三 一般來說，對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配

18、方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)。這種估價(jià)涉及到資源的最有效利用，如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的好壞。 需要指出的是，影子價(jià)格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤(rùn)等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格說明增加單位資源量可以增加的收益，是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過了一定的范圍，總利潤(rùn)的增加量就不是按照影子價(jià)格給出的數(shù)值線性地增加。這將在靈敏度分析中討論31第31頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三影子價(jià)格的應(yīng)用舉例： 例5：某外貿(mào)公司準(zhǔn)備購進(jìn)兩種產(chǎn)

19、品A1，A2。購進(jìn)產(chǎn)品A1每件需要10元，占用5平方米的空間，賣出1件可獲純利潤(rùn)3元；購進(jìn)產(chǎn)品A2每件需要15元，占用3平方米的空間，賣出1件可獲純利潤(rùn)4元。公司現(xiàn)有資金1400元，有430平方米的倉庫空間存放產(chǎn)品。根據(jù)這些條件可以建立求最大利潤(rùn)的線性規(guī)劃模型： Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15 x2 1400 5 x1 + 3 x2 430 x1, x2 032第32頁，共35頁，2022年，5月20日，1點(diǎn)57分，星期三求解后得到最優(yōu)單純形表如下所示 ： 因此，最優(yōu)方案是分別購進(jìn)兩種產(chǎn)品50件和60件，公司的最大利潤(rùn)為390元。 同時(shí)，從表中也可以看到，資金的影子價(jià)格為11/45，即增加1元用于購買產(chǎn)品，可以多獲利潤(rùn)11/45元；倉庫的影子價(jià)格為1/9，即增加1平方米的倉庫空間，可以多獲利潤(rùn)1/9元。33CBXBbx1x2x3x44x260011/9-2/93x15010-1/151/3-z-39000-11/45-1/9第33頁，共35頁，2022年，5月20日，1點(diǎn)57分，星