1第1頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論2重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智

(3.4-1)

上述問(wèn)題是企業(yè)利用已有的資源,通過(guò)自己加工、生產(chǎn)出產(chǎn)品進(jìn)行銷售而獲得收入。企業(yè)是利潤(rùn)最大化為目標(biāo)。因此，對(duì)于該問(wèn)題也可考慮另一種經(jīng)營(yíng)問(wèn)題，即出租（或出讓）資源，來(lái)獲得收入。該問(wèn)題的關(guān)鍵是確定資源的價(jià)格，特別是要確定資源的價(jià)格在什么條件下，使出租（或出讓）資源所獲的最少收入與自己生產(chǎn)所獲最大收入相同.為此，不妨假設(shè)木工與油漆工的單位工時(shí)租金分別為：y1和y2，可得數(shù)學(xué)模型如下：第2頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論3重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智

(3.4-2)

上述問(wèn)題顯然也是線性規(guī)劃問(wèn)題。通常稱模型(3.4-1)與模型(3.4-2)互為對(duì)偶問(wèn)題；若稱模型(3.4-1)為原問(wèn)題，則稱模型(3.4-2)為模型(3.4-1)的對(duì)偶問(wèn)題。2、原問(wèn)題與對(duì)偶問(wèn)題一般矩陣形式：原問(wèn)題對(duì)偶問(wèn)題（P）（D）(3.4-3)

第3頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論4重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智二、如何將原問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題1、轉(zhuǎn)化原則：

表3.4-1對(duì)偶關(guān)系對(duì)應(yīng)表原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)maxZ目標(biāo)函數(shù)minW變量n個(gè)約束條件n個(gè)≥≥0≤0≤無(wú)限制＝約束條件m個(gè)變量m個(gè)≥0≤≥≤0＝無(wú)限制約束條件右邊常數(shù)項(xiàng)目標(biāo)函數(shù)變量系數(shù)目標(biāo)函數(shù)變量系數(shù)約束條件右邊常數(shù)項(xiàng)第4頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論5重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智2、例3.4.2原問(wèn)題：

(3.4-5)

對(duì)偶問(wèn)題：

(3.4-6)第5頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論6重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智三、線性規(guī)劃的對(duì)偶理論

如果不特別說(shuō)明，原問(wèn)題（P）和對(duì)偶問(wèn)題（D）由式(3.4-3)定義。定理3.4.1：(對(duì)稱性定理)對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。定理3.4.2：(弱對(duì)偶定理)設(shè)X，Y分別是（P）和（D）的可行解，則CX≤Yb。定理3.4.3：(對(duì)偶定理)（P）和（D）存在以下對(duì)應(yīng)關(guān)系:（1）（P）有最優(yōu)解的充要條件是（D）有最優(yōu)解；（2）若（P）無(wú)界，則（D）不可行；（3）若（D）無(wú)界，則（P）不可行；第6頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論7重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智（4）若X*，Y*分別是（P）和（D）的可行解，則它們分別為（P）和（D）的最優(yōu)解的充要條件是：CX*=Y*b定理3.4.4：(互補(bǔ)松弛定理)如果X，Y分別是（P）和（D）的可行解，它們分別為（P）和（D）的最優(yōu)解的充要條件是：(C-YA)X=0和Y(b-AX)=0四、對(duì)偶解的經(jīng)濟(jì)含義1、對(duì)偶解與影子價(jià)格對(duì)偶解（Y=CBB-1）的經(jīng)濟(jì)含義是資源的單位改變量引起的目標(biāo)函數(shù)值的改變量。人們通常用價(jià)值量來(lái)衡量目標(biāo)函數(shù)值的大小，因此對(duì)偶解也具有價(jià)值的內(nèi)涵，通常又被稱為影子價(jià)格。第7頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論8重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智影子價(jià)格是對(duì)偶解的一個(gè)十分形象的名稱，它既表明對(duì)偶解是對(duì)系統(tǒng)內(nèi)部資源的一種客觀估價(jià)，又表明它是一種虛擬的價(jià)格(或價(jià)值的映象)而不是真實(shí)的價(jià)格。2、影子價(jià)格的特點(diǎn)：1）影子價(jià)格是對(duì)系統(tǒng)資源的一種最優(yōu)估價(jià)，只有系統(tǒng)達(dá)到最優(yōu)狀態(tài)時(shí)才可能賦予該資源這種價(jià)值。因此，也有人稱之為最優(yōu)價(jià)格。2）影子價(jià)格的取值與系統(tǒng)的價(jià)值取向有關(guān)，并受系統(tǒng)狀態(tài)變化的影響。系統(tǒng)內(nèi)部資源數(shù)量和價(jià)格的任何變化都會(huì)引起影子價(jià)格的變化，從這種意義上講，它是一種動(dòng)態(tài)的價(jià)格體系。3）對(duì)偶解——影子價(jià)格的大小客觀地反映資源在系統(tǒng)內(nèi)第8頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論9重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智的稀缺程度。如果某資源在系統(tǒng)內(nèi)供大于求，盡管它有實(shí)實(shí)在在的市場(chǎng)價(jià)格，但它的影子價(jià)格為零。這一事實(shí)表明,增加該資源的供應(yīng)不會(huì)引起系統(tǒng)目標(biāo)的任何變化。如果某資源是稀缺資源，其影子價(jià)格必然大于零。影子價(jià)格越高,資源在系統(tǒng)中越稀缺。4）影子價(jià)格是一種邊際價(jià)值，它與經(jīng)濟(jì)學(xué)中邊際成本的概念相同。因而在經(jīng)濟(jì)管理中有十分重要應(yīng)用價(jià)值。企業(yè)管理者可以根據(jù)資源在本企業(yè)內(nèi)影子價(jià)格的大小決定企業(yè)的經(jīng)營(yíng)策略。然而，對(duì)偶解準(zhǔn)確的經(jīng)濟(jì)意義有時(shí)要根據(jù)模型構(gòu)造的方法來(lái)確定。模型構(gòu)造方法的不同有時(shí)會(huì)導(dǎo)致對(duì)對(duì)偶解的不同解釋。3、影子價(jià)格在企業(yè)經(jīng)營(yíng)策略中的應(yīng)用第9頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論10重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智1）如果某資源的影子價(jià)格高于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應(yīng)買入該資源。2）如果某資源的影子價(jià)格低于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)一無(wú)獲利能力，應(yīng)賣出該資源。3）如果某資源的影子價(jià)格等于市場(chǎng)價(jià)格，表明該資源在系統(tǒng)內(nèi)處于平衡狀態(tài)，既不用買入，也不必賣出。4、檢驗(yàn)數(shù)與邊際貢獻(xiàn)因?yàn)?，所以，檢驗(yàn)數(shù)也可解釋為產(chǎn)品對(duì)目標(biāo)函數(shù)的邊際貢獻(xiàn)，即：增加該產(chǎn)品的單位生產(chǎn)量給目標(biāo)函數(shù)帶來(lái)的貢獻(xiàn)。檢驗(yàn)數(shù)與每一個(gè)變量相對(duì)應(yīng)，當(dāng)線性規(guī)劃問(wèn)題達(dá)到最優(yōu)時(shí)，檢驗(yàn)數(shù)總是小于或等于零(對(duì)極大化問(wèn)題)。這意味第10頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論11重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智著在最優(yōu)狀態(tài)下，每個(gè)變量對(duì)目標(biāo)函數(shù)的邊際貢獻(xiàn)都小于或等于零。檢驗(yàn)數(shù)所代表的邊際貢獻(xiàn)有和影子價(jià)格一樣的特點(diǎn)，它是在系統(tǒng)達(dá)到最優(yōu)時(shí)對(duì)變量的一種估價(jià)。它的取值也受系統(tǒng)狀態(tài)的影響，并會(huì)隨系統(tǒng)的變化而變化。5、影子價(jià)格與資源的關(guān)系如果某資源在系統(tǒng)內(nèi)的影子價(jià)格大于零(yj＞o)，該資源必是緊缺資源，對(duì)應(yīng)的約束為緊約束(bi-aix＝o)；否則,若該資源在系統(tǒng)內(nèi)仍有剩余，系統(tǒng)一定還未達(dá)到最優(yōu)狀態(tài),因?yàn)槔^續(xù)利用該資源可使目標(biāo)進(jìn)一步得到改善。另一方面,如果某資源在系統(tǒng)內(nèi)有剩余，資源約束為松約束(bi-aix＞0)時(shí)，其對(duì)偶解必為零(yj＝0)，否則，若對(duì)偶解大于零，第11頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論12重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智增加該資源的使用還可使目標(biāo)得到改善。同樣道理，在最優(yōu)狀態(tài)下，當(dāng)變量的檢驗(yàn)數(shù)小于零時(shí)(cj-ypj＜0)，說(shuō)明生產(chǎn)該產(chǎn)品的邊際貢獻(xiàn)是負(fù)的，在最優(yōu)計(jì)劃中不該生產(chǎn)它，因此，該變量必為零(xj＝0)。另一方面，當(dāng)變量大于零時(shí)(xj＞0)，該變量檢驗(yàn)數(shù)(邊際貢獻(xiàn))必為零(cj一ypj＝0)，否則，無(wú)論邊際貢獻(xiàn)取正值或負(fù)值,相應(yīng)地增加或降低該產(chǎn)品的產(chǎn)量都可使目標(biāo)得到改善。五、對(duì)偶問(wèn)題的求解方法1、對(duì)偶解的求法1）直接求對(duì)偶問(wèn)題的解；2）求原問(wèn)題的最優(yōu)解時(shí)，求得對(duì)偶解Y=CBB-1

3）對(duì)偶單純形7、例：對(duì)例3.4.1用上述方法2)得原問(wèn)題的最優(yōu)單純形表第12頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論13重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智2、例：對(duì)例3.4.1用上述方法2)得原問(wèn)題的最優(yōu)單純形表表3.4-2最優(yōu)單純形表cj503000bxBCBx1x2x3x4x304310120x40210150σj5030000x30011-220x15011/201/225σj050-251250x230011-220x15010-1/23/215σj00-5-151350第13頁(yè)，課件共15頁(yè)，創(chuàng)作于2023年2月§3.4線性規(guī)劃對(duì)偶理論14重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智原問(wèn)題的最優(yōu)解為：X*=(15,20)T，最優(yōu)值為：