第三章線性規(guī)劃的對(duì)偶理論與靈敏度分析

第三章線性規(guī)劃的對(duì)偶理論與靈敏度分析1第一頁，共三十九頁，編輯于2023年，星期四3.1線性規(guī)劃的對(duì)偶問題一、引例例3．1生產(chǎn)計(jì)劃問題（資源利用問題）

勝利家具廠生產(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í)。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？第二頁，共三十九頁，編輯于2023年，星期四數(shù)學(xué)模型

maxg=50x1+30x2s.t.4x1+3x2120(3.1)2x1+x250x1,x20第三頁，共三十九頁，編輯于2023年，星期四

如果我們換一個(gè)角度，考慮另外一種經(jīng)營問題。假如有一個(gè)企業(yè)家有一批等待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。因此，他要同家具廠談判付給該廠每個(gè)工時(shí)的價(jià)格。可以構(gòu)造一個(gè)數(shù)學(xué)模型來研究如何既使家具廠覺得有利可圖肯把資源出租給他，又使自己付的租金最少？第四頁，共三十九頁，編輯于2023年，星期四

假設(shè)y1,y2分別表示每個(gè)木工和油漆工工時(shí)的租金，則所付租金最小的目標(biāo)函數(shù)可表示為：

mins=120y1+50y2目標(biāo)函數(shù)中的系數(shù)120，50分別表示可供出租的木工和油漆工工時(shí)數(shù)。第五頁，共三十九頁，編輯于2023年，星期四

該企業(yè)家所付的租金不能太低，否則家具廠的管理者覺得無利可圖而不肯出租給他。因此他付的租金應(yīng)不低于家具廠利用這些資源所能得到的利益：

4y1+2y2503y1+y230y1,y20第六頁，共三十九頁，編輯于2023年，星期四

得到另外一個(gè)數(shù)學(xué)模型：mins=120y1+50y2s.t.4y1+2y250(3.2)3y1+y230y1,y20第七頁，共三十九頁，編輯于2023年，星期四模型(3.1)和模型(3.2)既有區(qū)別又有聯(lián)系。聯(lián)系在于它們都是關(guān)于家具廠的模型并且使用相同的數(shù)據(jù)，區(qū)別在于模型反映的實(shí)質(zhì)內(nèi)容是不同的。模型(3.1)是站在家具廠經(jīng)營者立場(chǎng)追求銷售收入最大，模型(3.2)則是站在家具廠對(duì)手的立場(chǎng)追求所付的租金最少。第八頁，共三十九頁，編輯于2023年，星期四如果模型(3.1)稱為原問題，則模型(3.2)稱為對(duì)偶問題。任何線性規(guī)劃問題都有對(duì)偶問題，而且都有相應(yīng)的意義。第九頁，共三十九頁，編輯于2023年，星期四例3.2營養(yǎng)配餐問題

假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場(chǎng)價(jià)格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最?。康谑?，共三十九頁，編輯于2023年，星期四各種食物的營養(yǎng)成分表第十一頁，共三十九頁，編輯于2023年，星期四解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，

x3，x40(3.3)第十二頁，共三十九頁，編輯于2023年，星期四該問題的對(duì)偶問題：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30(3.4)第十三頁，共三十九頁，編輯于2023年，星期四該問題的對(duì)偶問題(3.4)經(jīng)濟(jì)意義可解釋為：市場(chǎng)上有一廠商生產(chǎn)三種可代替食品中的熱量、蛋白質(zhì)和鈣的營養(yǎng)素，該廠商希望它的產(chǎn)品既有市場(chǎng)競(jìng)爭(zhēng)力，又能帶來最大利潤，因此需要構(gòu)造一個(gè)模型來研究定價(jià)問題。以上模型的變量為各營養(yǎng)素單位營養(yǎng)量的價(jià)格，目標(biāo)函數(shù)反映廠商利潤最大的目標(biāo)，約束條件反映市場(chǎng)的競(jìng)爭(zhēng)條件，即：用于購買與某種食品營養(yǎng)價(jià)值相同的營養(yǎng)素的價(jià)格應(yīng)小于該食品的市場(chǎng)價(jià)格。第十四頁，共三十九頁，編輯于2023年，星期四二、對(duì)偶規(guī)則原問題一般模型：對(duì)偶問題一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0第十五頁，共三十九頁，編輯于2023年，星期四對(duì)偶規(guī)則原問題有m個(gè)約束條件，對(duì)偶問題有m個(gè)變量原問題有n個(gè)變量，對(duì)偶問題有n個(gè)約束條件原問題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問題的右端項(xiàng)原問題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問題的價(jià)值系數(shù)原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問題系數(shù)矩陣原問題的約束條件與對(duì)偶問題方向相反原問題與對(duì)偶問題優(yōu)化方向相反第十六頁，共三十九頁，編輯于2023年，星期四原問題對(duì)偶問題目標(biāo)函數(shù)maxmin目標(biāo)函數(shù)約束條件m個(gè)≤

≥=變量n個(gè)

≥≤無約束價(jià)值系數(shù)約束條件的右端項(xiàng)變量符號(hào)n個(gè)

≥≤

無約束約束條件m個(gè)

≥≤=約束條件的右端項(xiàng)價(jià)值系數(shù).第十七頁，共三十九頁，編輯于2023年，星期四例3.3寫出下列線性規(guī)劃問題的對(duì)偶問題minZ=3x1+2x2-6x3+x52x1+x2-4x3+x4+3x5≥7x1+2x3-x4

≤4-x1+3x2-x4+x5=-2x1，x2，x3≥0;x4

≤0;x5無限制第十八頁，共三十九頁，編輯于2023年，星期四maxω=7y1+4y2-2y32y1+y2-y3

≤3y1+3y3≤2-4y1+2y2

≤-6y1-y2-y3

≥

03y1+y3=1y1

≥0，y2≤0y3

無約束第十九頁，共三十九頁，編輯于2023年，星期四例3.4：寫出下列線性規(guī)劃問題的對(duì)偶問題maxS=10x1+x2+2x3s.t.X1+x2+2x3

104x1+2x2-x320

x1，x2，

x30第二十頁，共三十九頁，編輯于2023年，星期四三、對(duì)偶問題的基本性質(zhì)對(duì)稱性：對(duì)偶問題的對(duì)偶問題是原問題弱對(duì)偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對(duì)偶問題任意可行解的目標(biāo)函數(shù)值無界性：原問題無界，對(duì)偶問題無可行解第二十一頁，共三十九頁，編輯于2023年，星期四對(duì)偶定理：若一個(gè)問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。推理:對(duì)偶問題的最優(yōu)解為原問題最優(yōu)表中,相應(yīng)的松馳變量檢驗(yàn)數(shù)的相反數(shù)。第二十二頁，共三十九頁，編輯于2023年，星期四原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系第二十三頁，共三十九頁，編輯于2023年，星期四3.2對(duì)偶單純形法原始單純形法的基本思路：在換基迭代過程中，始終保持基變量值非負(fù)，逐步使檢驗(yàn)數(shù)變成非正，最后求得最優(yōu)解或判斷無最優(yōu)解。對(duì)偶單純形法的基本思路：在換基迭代過程中，始終保持檢驗(yàn)數(shù)非正，逐步使基變量值變成非負(fù)，最后求得最優(yōu)解或判斷無最優(yōu)解。第二十四頁，共三十九頁，編輯于2023年，星期四例2-9：用對(duì)偶單純形法解下列線性規(guī)劃問題

minZ=2x1+3x2+4x3s.t.x1+2x2+x3

32x1-x2+3x3

4x1，x2，

x30第二十五頁，共三十九頁，編輯于2023年，星期四3.3對(duì)偶解的經(jīng)濟(jì)解釋如果把線性規(guī)劃的約束看成廣義資源約束，右邊項(xiàng)則代表某種資源的可用量。對(duì)偶解的經(jīng)濟(jì)含義是資源的單位改變量引起目標(biāo)函數(shù)值的改變量。通常稱為影子價(jià)格。影子價(jià)格表明對(duì)偶解是對(duì)系統(tǒng)內(nèi)部資源的客觀估計(jì)，又表明它是一種虛擬的價(jià)格而不是真實(shí)價(jià)格。第二十六頁，共三十九頁，編輯于2023年，星期四影子價(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à)格體系。第二十七頁，共三十九頁，編輯于2023年，星期四影子價(jià)格的大小客觀反映了資源在系統(tǒng)內(nèi)的稀缺程度。如果某資源在系統(tǒng)內(nèi)供大于求，盡管它有市場(chǎng)價(jià)格，但它的影子價(jià)格等于零。增加這種資源的供應(yīng)不會(huì)引起系統(tǒng)目標(biāo)的任何變化。如果某資源是稀缺資源，其影子價(jià)格必然大于零。影子價(jià)格越高，這種資源在系統(tǒng)中越稀缺。第二十八頁，共三十九頁，編輯于2023年，星期四影子價(jià)格是一種邊際價(jià)值，它與經(jīng)濟(jì)學(xué)中邊際成本的概念相同。 因而在經(jīng)濟(jì)管理中有十分重要的價(jià)值。企業(yè)管理者可以根據(jù)資源在企業(yè)內(nèi)部影子價(jià)格的大小決定企業(yè)的經(jīng)營策略。第二十九頁，共三十九頁，編輯于2023年，星期四一般來講，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的影子價(jià)格高于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應(yīng)買入該資源。如果某資源的影子價(jià)格低于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)無獲利能力，應(yīng)賣出該資源。如果某資源的影子價(jià)格等于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)處于平衡狀態(tài)，既不用買入，也不必賣出該資源。第三十頁，共三十九頁，編輯于2023年，星期四3.4靈敏度分析在以前討論線性規(guī)劃問題時(shí)，假定aij,bi,cj都是常數(shù)，但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值．a(chǎn)ij,bi,cj變化時(shí)，最優(yōu)解將如何變化的分析，就叫靈敏度分析。第三十一頁，共三十九頁，編輯于2023年，星期四

靈敏度分析討論兩個(gè)問題：

1、研究系數(shù)在什么范圍內(nèi)變化最優(yōu)解仍為最優(yōu)解。2、若原最優(yōu)解不再是最優(yōu)解，如何用最簡(jiǎn)便的方法找到新的最優(yōu)解。第三十二頁，共三十九頁，編輯于2023年，星期四假定線性規(guī)劃問題maxZ=CXs.t.AX=bX≥0的最優(yōu)表為：cjcB基bx1x2……xnB-1AσjC-CBB-1A第三十三頁，共三十九頁，編輯于2023年，星期四不難看出，表中各塊與參數(shù)（aij,bi,cj）的關(guān)系為：B-1A與bi,cj無關(guān)，與aij有關(guān)；XB=B-1b與cj無關(guān)，與bi,aij有關(guān);σj=C-CBB-1A與bi無關(guān)，與cj,aij有關(guān)；Z=CBB-1b與bi,cj,aij均有關(guān)；第三十四頁，共三十九頁，編輯于2023年，星期四由此可知，當(dāng)某些參數(shù)變化時(shí)，并不一定要重新計(jì)算整個(gè)單純形表，而可以從原最優(yōu)單純形表出發(fā)，