1、1,第三章 線性規(guī)劃的對(duì)偶理論與靈敏度分析,主要內(nèi)容： 了解影子價(jià)格的含義。 理解線性規(guī)劃的對(duì)偶問(wèn)題及其性質(zhì)。 深刻理解對(duì)偶單純形法；靈敏度分析的方法和步驟。 教學(xué)重點(diǎn)與難點(diǎn)： 對(duì)偶單純形法； 靈敏度分析的方法和步驟。,2,3.1 線性規(guī)劃的對(duì)偶問(wèn)題,一、引例 例31生產(chǎn)計(jì)劃問(wèn)題（資源利用問(wèn)題） 勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子銷售價(jià)格30/個(gè)，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每個(gè)月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷售收入最

2、大？,3,數(shù)學(xué)模型 max g= 50 x1 + 30 x2 s.t. 4x1 + 3x2 120 (3.1) 2x1 + x2 50 x1,x2 0,4,如果我們換一個(gè)角度，考慮另外一種經(jīng)營(yíng)問(wèn)題。 假如有一個(gè)企業(yè)家有一批等待加工的訂單，有意利用該家具廠的木工和油漆工資源來(lái)加工他的產(chǎn)品。因此，他要同家具廠談判付給該廠每個(gè)工時(shí)的價(jià)格。可以構(gòu)造一個(gè)數(shù)學(xué)模型來(lái)研究如何既使家具廠覺(jué)得有利可圖肯把資源出租給他，又使自己付的租金最少？,5,假設(shè) y1, y2 分別表示每個(gè)木工和油漆工工時(shí)的租金，則所付租金最小的目標(biāo)函數(shù)可表示為： min s = 120 y1 + 50 y2 目標(biāo)函數(shù)中的系數(shù) 120，50

3、 分別表示可供出租的木工和油漆工工時(shí)數(shù)。,6,該企業(yè)家所付的租金不能太低，否則家具廠的管理者覺(jué)得無(wú)利可圖而不肯出租給他。因此他付的租金應(yīng)不低于家具廠利用這些資源所能得到的利益： 4 y1 + 2y2 50 3 y1 + y2 30 y1, y2 0,7,得到另外一個(gè)數(shù)學(xué)模型： min s = 120 y1 + 50 y2 s.t. 4 y1 + 2y2 50 (3.2) 3 y1+ y2 30 y1, y2 0,8,模型(3.1)和模型(3.2) 既有區(qū)別又有聯(lián)系。聯(lián)系在于它們都是關(guān)于家具廠的模型并且使用相同的數(shù)據(jù)，區(qū)別在于模型反映的實(shí)質(zhì)內(nèi)容是不同的。模型(3.1)是站在家具廠經(jīng)營(yíng)者立場(chǎng)追求銷

4、售收入最大，模型(3.2)則是站在家具廠對(duì)手的立場(chǎng)追求所付的租金最少。,9,如果模型(3.1)稱為原問(wèn)題， 則模型(3.2)稱為對(duì)偶問(wèn)題。 任何線性規(guī)劃問(wèn)題都有對(duì)偶問(wèn)題，而且都有相應(yīng)的意義。,10,例3 .2 營(yíng)養(yǎng)配餐問(wèn)題 假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見(jiàn)下表。問(wèn)如何選擇才能在滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最小？,11,各種食物的營(yíng)養(yǎng)成分表,12,解：設(shè)xj為第j種食品每天的購(gòu)入量，則配餐問(wèn)題的線性規(guī)劃模型為： min S=14x1+6x2 +3x3+2x4 s.t.

5、 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0 (3.3),13,該問(wèn)題的對(duì)偶問(wèn)題： max g = 3000 y1+55y2+800y3 s.t. 1000 y1+50y2+400y3 14 800 y1+60y2+200y3 6 900 y1+20y2+300y3 3 200 y1+10y2+500y3 2 y1，y2，y3 0 (3.4),14,該問(wèn)題的對(duì)偶問(wèn)題(3.4)經(jīng)濟(jì)意義可解釋為：市場(chǎng)上有一廠商

6、生產(chǎn)三種可代替食品中的熱量、蛋白質(zhì)和鈣的營(yíng)養(yǎng)素，該廠商希望它的產(chǎn)品既有市場(chǎng)競(jìng)爭(zhēng)力，又能帶來(lái)最大利潤(rùn)，因此需要構(gòu)造一個(gè)模型來(lái)研究定價(jià)問(wèn)題。以上模型的變量為各營(yíng)養(yǎng)素單位營(yíng)養(yǎng)量的價(jià)格，目標(biāo)函數(shù)反映廠商利潤(rùn)最大的目標(biāo)，約束條件反映市場(chǎng)的競(jìng)爭(zhēng)條件，即：用于購(gòu)買與某種食品營(yíng)養(yǎng)價(jià)值相同的營(yíng)養(yǎng)素的價(jià)格應(yīng)小于該食品的市場(chǎng)價(jià)格。,15,二、對(duì)偶規(guī)則,原問(wèn)題一般模型： 對(duì)偶問(wèn)題一般模型： maxZ=CX min =Yb AX b YA C X 0 Y 0,16,對(duì)偶規(guī)則,原問(wèn)題有m個(gè)約束條件，對(duì)偶問(wèn)題有m個(gè)變量 原問(wèn)題有n個(gè)變量，對(duì)偶問(wèn)題有n個(gè)約束條件 原問(wèn)題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的右端項(xiàng) 原問(wèn)題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問(wèn)

7、題的價(jià)值系數(shù) 原問(wèn)題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問(wèn)題系數(shù)矩陣 原問(wèn)題的約束條件與對(duì)偶問(wèn)題方向相反 原問(wèn)題與對(duì)偶問(wèn)題優(yōu)化方向相反,17,.,18,例3.3 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 minZ=3x1+2x2-6x3+x5 2x1+x2-4x3+x4+3x5 7 x1+ 2x3 -x4 4 -x1+3x2 -x4+ x5 =-2 x1，x2，x3 0; x4 0;x5無(wú)限制,19,max =7y1+4y2-2y3 2y1+ y2- y3 3 y1 +3y3 2 -4y1+ 2y2 -6 y1 -y2 -y3 0 3y1 +y3=1 y1 0，y2 0y3 無(wú)約束,20,例3.4：寫出下列線性規(guī)

8、劃問(wèn)題的對(duì)偶問(wèn)題 max S = 10 x1 + x2 + 2x3 s.t. X1 + x2 + 2x3 10 4x1 +2x2 - x3 20 x1，x2 ， x3 0,21,三、對(duì)偶問(wèn)題的基本性質(zhì),對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題 弱對(duì)偶性：極大化原問(wèn)題的任一可行解的目標(biāo)函數(shù)值，不大于其對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值 無(wú)界性：原問(wèn)題無(wú)界，對(duì)偶問(wèn)題無(wú)可行解,22,對(duì)偶定理：若一個(gè)問(wèn)題有 最優(yōu)解，則另一問(wèn)題也有最 優(yōu)解，且目標(biāo)函數(shù)值相等。 推理:對(duì)偶問(wèn)題的最優(yōu)解為 原問(wèn)題最優(yōu)表中,相應(yīng)的松 馳變量檢驗(yàn)數(shù)的相反數(shù)。,23,原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系,24,3.2 對(duì)偶單純形法 原始單純形法的

9、基本思路：在換基迭代過(guò)程中，始終保持基變量值非負(fù)，逐步使檢驗(yàn)數(shù)變成非正，最后求得最優(yōu)解或判斷無(wú)最優(yōu)解。 對(duì)偶單純形法的基本思路：在換基迭代過(guò)程中，始終保持檢驗(yàn)數(shù)非正，逐步使基變量值變成非負(fù)，最后求得最優(yōu)解或判斷無(wú)最優(yōu)解。,25,例2-9：用對(duì)偶單純形法解下列線性規(guī)劃問(wèn)題 min Z= 2x1 + 3x2 + 4x3 s.t. x1+2x2 +x3 3 2x1 - x2+3x3 4 x1，x2 ， x3 0,26,3.3 對(duì)偶解的經(jīng)濟(jì)解釋 如果把線性規(guī)劃的約束看成廣義資源約束，右邊項(xiàng)則代表某種資源的可用量。對(duì)偶解的經(jīng)濟(jì)含義是資源的單位改變量引起目標(biāo)函數(shù)值的改變量。通常稱為影子價(jià)格。影子價(jià)格表明對(duì)

10、偶解是對(duì)系統(tǒng)內(nèi)部資源的客觀估計(jì)，又表明它是一種虛擬的價(jià)格而不是真實(shí)價(jià)格。,27,影子價(jià)格的特征： 影子價(jià)格是對(duì)系統(tǒng)資源的最優(yōu)估計(jì)，只有系統(tǒng)達(dá)到最優(yōu)狀態(tài)時(shí)才可能賦與資源這種價(jià)值。因此，也稱為最優(yōu)價(jià)格。 影子價(jià)格的取值與系統(tǒng)的價(jià)值取向有關(guān)，并受系統(tǒng)狀態(tài)變化的影響。系統(tǒng)內(nèi)部資源數(shù)量和價(jià)格的變化，它是一種動(dòng)態(tài)的價(jià)格體系。,28,影子價(jià)格的大小客觀反映了資源在系統(tǒng)內(nèi)的稀缺程度。如果某資源在系統(tǒng)內(nèi)供大于求，盡管它有市場(chǎng)價(jià)格，但它的影子價(jià)格等于零。增加這種資源的供應(yīng)不會(huì)引起系統(tǒng)目標(biāo)的任何變化。如果某資源是稀缺資源，其影子價(jià)格必然大于零。影子價(jià)格越高，這種資源在系統(tǒng)中越稀缺。,29,影子價(jià)格是一種邊際價(jià)值，它

11、與經(jīng)濟(jì)學(xué)中邊際成本的概念相同。因而在經(jīng)濟(jì)管理中有十分重要的價(jià)值。企業(yè)管理者可以根據(jù)資源在企業(yè)內(nèi)部影子價(jià)格的 大小決定企業(yè)的經(jīng)營(yíng)策略。,30,一般來(lái)講，我們按以下原則考慮企業(yè)的經(jīng)營(yíng)策略： 如果某資源的影子價(jià)格高于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應(yīng)買入該資源。 如果某資源的影子價(jià)格低于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)無(wú)獲利能力，應(yīng)賣出該資源。 如果某資源的影子價(jià)格等于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)處于平衡狀態(tài)，既不用買入，也不必賣出該資源。,31,3.4 靈敏度分析 在以前討論線性規(guī)劃問(wèn)題時(shí)，假定aij,bi,cj都是常數(shù)，但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值 aij,bi,cj變化時(shí)，最優(yōu)解將

12、如何變化的分析，就叫靈敏度分析。,32,靈敏度分析討論兩個(gè)問(wèn)題：1、研究系數(shù)在什么范圍內(nèi)變化最優(yōu)解仍為最優(yōu)解。 2、若原最優(yōu)解不再是最優(yōu)解，如何用最簡(jiǎn)便的方法找到新的最優(yōu)解。,33,假定線性規(guī)劃問(wèn)題 maxZ=CX s.t. AX=b X0 的最優(yōu)表為：,34,不難看出，表中各塊與參數(shù)（ aij,bi,cj）的關(guān)系為： B-1A與 bi,cj無(wú)關(guān)，與aij有關(guān)； XB= B-1b與 cj無(wú)關(guān)，與bi,aij有關(guān); j= C-CB B-1A 與bi無(wú)關(guān)，與cj,aij有關(guān)； Z=CB B-1b 與bi,cj,aij均有關(guān)；,35,由此可知，當(dāng)某些參數(shù)變化時(shí)，并不一定要重新計(jì)算整個(gè)單純形表，而可以從原最優(yōu)單純形表出發(fā)，作適當(dāng)修改后再求新的最優(yōu)解,36,靈敏度分析的步驟為：,37,一、cj變化的情況 當(dāng)只有cj發(fā)生變化時(shí)，顯然原最優(yōu)解的可行性不變，只需檢查其最優(yōu)性，若仍有全部j0,則原最優(yōu)解仍是最優(yōu)解；否則在原來(lái)的最優(yōu)單純形表的基礎(chǔ)上換基迭代，以求出新的最優(yōu)解。,38,例：美佳公