1、,管理運(yùn)籌學(xué),汪賢裕 2009.08,2,第2章 線性規(guī)劃的對偶理論及應(yīng)用 2.1 線性規(guī)劃的對偶問題 2.1.1 對偶規(guī)劃問題的提出,3,例1.1生產(chǎn)計(jì)劃問題 求下列數(shù)據(jù)下家俱廠生產(chǎn)計(jì)劃，使利潤最大。,解：設(shè)生產(chǎn)桌子x1個(gè)，生產(chǎn)椅子x2個(gè),線性規(guī)劃模型為： max z = 50 x1 30 x2 s.t. 4 x1 3 x2 120 2 x1 x2 50 x1 0, x2 0.,4,例2.1（續(xù)）設(shè)有另一個(gè)企業(yè)，缺少木工和油漆工，它向家俱廠提出租用木工和油漆工。問該企業(yè)提出什么樣的租用價(jià)格。 解：設(shè)它提出的木工和油漆工的租用工時(shí)價(jià)分別為y1和y2. Min w =120y150y2 s.t.

2、 4y12y250 3y1y230 y10, y20.,5,例1.2營養(yǎng)配餐問題 要求配餐中至少應(yīng)有熱量3000kcal,蛋白質(zhì)55g，鈣300mg。問應(yīng)怎樣配餐成本最低？,6,解：設(shè)每天購入豬肉 x1千克、雞蛋 x2千克、大米 x3千克、白菜 x4千克。（決策變量） 則配餐問題的線性規(guī)劃模型如下： Min z=14x1 6x2 3x3 2x4 （目標(biāo)函數(shù)) s.t. 1000 x1800 x2900 x3200 x4 3000 50 x1 60 x2 20 x3 10 x4 55 400 x1 200 x2300 x3500 x4 800 x i 0 i =1, 2, 3, 4. （s.t.

3、后全是約束條件）,7,例2.2（續(xù)）現(xiàn)有一個(gè)企業(yè)生產(chǎn)人造營養(yǎng)品：熱量、蛋白質(zhì)、鈣，并賣給營養(yǎng)配方管理者。它應(yīng)對生產(chǎn)的人造營養(yǎng)品定價(jià)，以獲取更多的收入。 解：設(shè)它對三種人造營養(yǎng)品定價(jià)分別為y1、y2、y3。有線性規(guī)劃模型： Max w =3000 y155 y2800 y3 s.t. 1000 y150 y2400 y3 14 800 y160 y2200 y3 6 900 y120 y2300 y3 3 200 y110 y2500 y3 2 y1 0, y2 0, y3 0.,8,2.1.2. 線性規(guī)劃對偶問題的定義,對稱形式： 互為對偶 (LP) Max z = cT x (DP) Min

4、 f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”,9,對稱形式的對偶規(guī)劃 (1)若一個(gè)模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，”和“min，”相對應(yīng)。,(2)從約束系數(shù)矩陣看：一個(gè)模型中為，則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束，n個(gè)變量，則它的對偶模型為n個(gè)約束，m個(gè)變量。 (3)從數(shù)據(jù)b、c的位置看：在兩個(gè)規(guī)劃模型中，b和c的位置對換。 (4)兩個(gè)規(guī)劃模型中的變量皆非負(fù)。,10,非對稱形式的對偶規(guī)劃 一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形

5、式的對偶規(guī)劃。 對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系直接給出其對偶規(guī)劃。 （1）將模型統(tǒng)一為“max，”或“min，” 的形式，對于其中的等式約束按下面（2）、（3）中的方法處理； （2）若原規(guī)劃的某個(gè)約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個(gè)變量取值沒有非負(fù)限制；,（3）若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限制，則在對偶問題中與此變量對應(yīng)的那個(gè)約束為等式。,11,下面對關(guān)系（2）作一說明。對于關(guān)系（3）可以給出類似的解釋。 設(shè)原規(guī)劃中第一個(gè)約束為等式： a11x1 + + a1nxn = b1,等價(jià),這樣，原規(guī)劃模型可以寫成,12,此時(shí)已轉(zhuǎn)化為對稱形式，直接寫出對偶規(guī)劃,這里，把

6、 y1 看作是 y1 = y1 - y1，于是 y1 沒有非負(fù)限制，關(guān)系（2）的說明完畢。 關(guān)系（3）則是這一過程的逆過程。,13,例2.3 寫出下面線性規(guī)劃的對偶規(guī)劃模型,解: 先將約束條件變形為“”形式,14,再根據(jù)非對稱形式的對應(yīng)關(guān)系，直接寫出對偶規(guī)劃,15,2.2 線性規(guī)劃的對偶理論 定理2.1（對稱性定理） 對偶問題的對偶是原問題。 定理2.2 （弱對偶定理） 設(shè) x，y 分別是（LP）和（DP）的可行解， 則 c x y b 定理2. 3（對偶定理） 若 x* 和 y* 分別是(LP)和(DP)的可行解，則 x* 和 y* 分別為(LP)和(DP)的最優(yōu)解的充分必要條件是： c x

7、*= y* b。,16,2.3 對偶解的經(jīng)濟(jì)解釋,對偶解和影子價(jià)格 若x*,y* 分別為（LP）和（DP）的最優(yōu)解， 那么， cT x* = bT y* 。 根據(jù) z* = cT x* = bT y* = b1y1*+ b2y2*+bmym* 可知 z* / bi = yi* yi* 表示 bi 變化1個(gè)單位對目標(biāo) z產(chǎn)生的影響，稱 yi* 為 bi的影子價(jià)格。 影子價(jià)格是對系統(tǒng)內(nèi)部資源的一種客觀評價(jià)。 它是一種虛擬的價(jià)格，而不是真實(shí)的價(jià)格。,17,影子價(jià)格的幾個(gè)特點(diǎn): （1）影子價(jià)格是對現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種最優(yōu)估價(jià)。 （2）影子價(jià)格的取值與系統(tǒng)的價(jià)值取向有關(guān)，并受系統(tǒng)狀態(tài)變化的影響。

8、 系統(tǒng)內(nèi)部資源數(shù)量和價(jià)格的任何變化都會(huì)引起影子價(jià)格的變化。,18,（3）影子價(jià)格的大小客觀地反映資源在系統(tǒng)內(nèi)的稀缺程度。 如果某資源在系統(tǒng)內(nèi)部供大于求，它的影子價(jià)格為零；如果資源是稀缺資源，其影子價(jià)格必然大于零。 （4）影子價(jià)格是一種邊際價(jià)值，它與經(jīng)濟(jì)學(xué)中邊際成本的概念相同。 企業(yè)管理者可以根據(jù)資源在本企業(yè)內(nèi)的影子價(jià)格的大小決定企業(yè)的經(jīng)營策略。 例如：出租設(shè)備，購買設(shè)備，購買或出賣資源。,19,例1.1生產(chǎn)計(jì)劃問題（續(xù)）,增加一個(gè)約束條件： 現(xiàn)木工廠生產(chǎn)的是有一定工藝的產(chǎn)品，每個(gè)桌 子用工藝工2小時(shí)，每個(gè)椅子用工藝工3小時(shí)。 問工廠應(yīng)如何安排生產(chǎn)。,20,線性規(guī)劃模型為： max z = 50

9、 x1 30 x2 s.t. 4 x1 3 x2 120 2 x1 x2 50 2 x1 3 x2 70 x1 0, x2 0.,解：設(shè)生產(chǎn)桌子x1個(gè)，生產(chǎn)椅子x2個(gè),求解得：,21,例2.1（續(xù)）設(shè)有另一個(gè)企業(yè)，缺少木工、油漆工和工藝工，它向家俱廠提出租用木工、油漆工和工藝工。問該企業(yè)提出什么樣的租用價(jià)格。 解：設(shè)它提出的木工和油漆工工藝工的租用工時(shí)價(jià)分別為y1，y2和y3. Min w =120y1 50y2 70y3 s.t. 4y1 2y2 2y350 3y1 y23 y330 y10, y20, y30. 求解得：,22,例：某外貿(mào)公司準(zhǔn)備購進(jìn)A1 ,A2 兩種產(chǎn)品。購進(jìn)產(chǎn)品A1每件

10、需要10元，占用5m3的空間，待每件A1賣出后，可獲純利潤3元；購進(jìn)產(chǎn)品A2每件需要15元，占用空間3m3的空間，待每件A2賣出后，可獲純收潤4元。公司現(xiàn)有資金1400元，有430m3的倉庫空間存放產(chǎn)品，根據(jù)這些條件，可以建立求最大利潤的線性規(guī)劃模型： 求解得： 對偶解為：,23,現(xiàn)公司另有一筆資金585元，準(zhǔn)備用于投資。 這筆資金可以用于購買A1 ,A2 兩種產(chǎn)品，也可以用來增加倉庫的容量。假設(shè)增加倉庫的容量，每m3需0.8元。 問該公司應(yīng)如何使用這筆資金。 考查該問題的影子價(jià)格： 每增加0.8元，可增倉庫容量1m3，可增利潤1/9元； 增加1元，可增倉庫容量(1/0.8)m3，可增利潤1/(90.8)元=0.14元； 每增加1元