對(duì)偶線性規(guī)劃理論及其在經(jīng)濟(jì)中的應(yīng)用[畢業(yè)論文]

1、<p>　　本科畢業(yè)論文（設(shè)計(jì)）</p><p><b>　?。?0 屆）</b></p><p>　　對(duì)偶線性規(guī)劃理論及其在經(jīng)濟(jì)中的應(yīng)用</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級(jí) 信息與計(jì)算科學(xué) </

2、p><p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要:對(duì)偶線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，并應(yīng)用到社會(huì)各個(gè)方面。本文首先介紹了對(duì)

3、偶線性規(guī)劃理論產(chǎn)生的背景，以及它的發(fā)展歷程和發(fā)展方向。接著敘述了解決對(duì)偶線性規(guī)劃問題的方法及其算法。我們通過分析問題建立數(shù)學(xué)模型，使用適當(dāng)方法求出最優(yōu)解，并對(duì)其進(jìn)行分析得到該問題的最優(yōu)值。最后運(yùn)用對(duì)偶線性規(guī)劃理論來(lái)解決相關(guān)實(shí)際問題，即它被應(yīng)用的過程。</p><p>　　關(guān)鍵詞:對(duì)偶線性規(guī)劃；數(shù)學(xué)模型；最優(yōu)解.</p><p>　　The Theory of Dual Linear Pro

4、gramming and its Application in economics</p><p>　　Abstract:Dual linear programming is an important branch of operations research, and it’s applied to all aspects of the society. In this paper the background

5、 of the dual linear programming theory, the development history and direction of dual linear programming theory are introduced. Then the methods and algorithms of solving the dual linear programming problems are describe

6、d. We can build a mathematical model by analyzing the problem,obtain an optinum solution in the proper way and analyze the s</p><p>　　Keywords:dual linear programming; mathematical models; optimal value.<

7、/p><p><b>　　目 錄</b></p><p><b>　　1. 緒論1</b></p><p>　　2. 對(duì)偶線性規(guī)劃理論的概述3</p><p>　　2.1 對(duì)偶線性規(guī)劃理論的發(fā)展歷程及現(xiàn)狀3</p><p>　　2. 2 對(duì)偶問題的基本性質(zhì)3&l

8、t;/p><p>　　3 線性規(guī)劃的對(duì)偶原理及其應(yīng)用6</p><p>　　3.1 對(duì)偶理論6</p><p>　　3.2 對(duì)偶性的其他問題8</p><p>　　3.3 對(duì)偶規(guī)劃問題的三種解法介紹9</p><p>　　3.4 最優(yōu)對(duì)偶變量（影子價(jià)格）的經(jīng)濟(jì)解釋11</p><p&

9、gt;　　3.5 影子價(jià)格在企業(yè)經(jīng)營(yíng)管理中的應(yīng)用18</p><p><b>　　4. 結(jié)論21</b></p><p>　　致 謝錯(cuò)誤!未定義書簽。</p><p><b>　　參考文獻(xiàn)22</b></p><p><b>　　1. 緒論</b></p&g

10、t;<p>　　任一線性規(guī)劃問題都存在另一與之伴隨的線性規(guī)劃問題，他們從不同角度對(duì)一個(gè)實(shí)際問題提出并進(jìn)行描述，組成一對(duì)互為對(duì)偶的線性規(guī)劃問題。</p><p>　　什么是“對(duì)偶問題”呢？對(duì)偶問題實(shí)際上是換一個(gè)角度來(lái)分析原問題。在線性規(guī)劃分析方法中，假設(shè)原問題的目標(biāo)是盡可能地利用可利用的資源來(lái)獲得最大化利潤(rùn)的話，那么從問題的另一個(gè)側(cè)面來(lái)思考問題，目標(biāo)變成盡可能地利用原問題所給出的利潤(rùn)指標(biāo)來(lái)調(diào)整范圍條件

11、來(lái)減少資源的消耗，于是以原問題目標(biāo)函數(shù)中的決策變量系數(shù)作為新問題的資源，其所形成的線性規(guī)劃模型就成為對(duì)偶問題的線性規(guī)劃模型。</p><p>　　當(dāng)原問題與對(duì)偶問題的最優(yōu)化目標(biāo)函數(shù)值相同時(shí)，可以揭示公平交易最為根本的東西：無(wú)論是從買方看，還是從賣方看，都實(shí)現(xiàn)了自己的交易目標(biāo)最優(yōu)化。在一樁交易中，賣方總是希望獲利最大化，而買方則是希望采購(gòu)成本最小化，他們的成交底線在哪里呢？從對(duì)偶規(guī)劃的角度看，如果交易雙方都是理性交

12、易的話，他們的成交底線應(yīng)該是相同的，即賣方的利益最大化目標(biāo)值等于買方的成本最小化目標(biāo)值。[1]</p><p>　　所以，對(duì)偶線性規(guī)劃理論在經(jīng)濟(jì)中的應(yīng)用是很有實(shí)用價(jià)值，也是很值得研究的。</p><p>　　我國(guó)加入之后，融入經(jīng)濟(jì)全球化的速度不斷加快，競(jìng)爭(zhēng)日趨激烈，為了適應(yīng)新的生存環(huán)境，企業(yè)的經(jīng)營(yíng)理念就必須不斷深化。產(chǎn)品（業(yè)務(wù)）經(jīng)營(yíng)、資產(chǎn)經(jīng)營(yíng)、資本經(jīng)營(yíng)三管齊下，確保企業(yè)的競(jìng)爭(zhēng)力處在最好水平

13、，這種由全球性的優(yōu)秀企業(yè)所創(chuàng)造的經(jīng)營(yíng)理念也將成為我國(guó)所有成功企業(yè)的經(jīng)營(yíng)理念。其中，資產(chǎn)經(jīng)營(yíng)將成為各類企業(yè)保持競(jìng)爭(zhēng)力的一種普遍行為。</p><p>　　資產(chǎn)經(jīng)營(yíng)的主要內(nèi)容是企業(yè)的業(yè)務(wù)重組和資產(chǎn)重組。而在資產(chǎn)經(jīng)營(yíng)策略中，交易價(jià)格底線的確定往往是意見困難的事情。價(jià)格底線訂高了，擔(dān)心交易不成，損失機(jī)會(huì)；價(jià)格底線訂低了，又擔(dān)心交易吃虧了，損失利益。究竟采取什么策略才能保證既不會(huì)喪失機(jī)會(huì)又不至于吃虧呢？一種策略是，決策層事

14、先不了解價(jià)格底線也不給出價(jià)格底線，讓業(yè)務(wù)人員處在無(wú)底線約束的狀況下與交易對(duì)象進(jìn)行談判，在談判的過程中不斷地了解對(duì)方的意圖和信息，并且將信息反饋到?jīng)Q策層，由決策層根據(jù)對(duì)方的意圖來(lái)確定價(jià)格底線，并據(jù)此確定最后的交易價(jià)格。</p><p>　　另一種策略是，決策層事先安排資產(chǎn)評(píng)估分析人員對(duì)擬進(jìn)行交易的標(biāo)的物進(jìn)行評(píng)估，并提出轉(zhuǎn)讓或購(gòu)入資產(chǎn)的價(jià)格底線的專業(yè)性建議，再讓業(yè)務(wù)人員帶著決策底線去現(xiàn)場(chǎng)談判，在談判中進(jìn)一步了解信息，

15、并且將信息反饋到?jīng)Q策層，由決策層根據(jù)不沖信息對(duì)價(jià)格底線建議進(jìn)行修正，然后最終確定交易價(jià)格。</p><p>　　粗看起來(lái)，兩種策略差不多，并且似乎前者更靈活一些，更有可能抓住機(jī)會(huì)，獲得更多的利益。其實(shí)，真正能做到既抓住交易機(jī)會(huì)，又不會(huì)損失合理利益，既能保證原則性，又可以現(xiàn)實(shí)靈活性的策略是第二種。</p><p>　　因此，第一種策略是一個(gè)基于對(duì)手理性的決策過程，而第二種策略則是一個(gè)基于自我

16、理性的決策過程。與一個(gè)理性的交易對(duì)手打交道，第一種策略的最優(yōu)交易結(jié)果是不賠不賺，而第二種策略的最差結(jié)果是不賠不賺。</p><p>　　不賠不賺交易可以稱為對(duì)等交易。從邏輯上看，采用第一種策略與一個(gè)理性的交易對(duì)手進(jìn)行交易，不能導(dǎo)致交易的對(duì)等結(jié)果必然出現(xiàn)，在與一個(gè)非理性的交易對(duì)手進(jìn)行交易時(shí)，也不能保證交易本身是對(duì)等的或者是對(duì)己方有利的，因此它不是一個(gè)好的策略。而采用第二種策略，在與一個(gè)理性的交易對(duì)手進(jìn)行交易時(shí)，可以

17、保證交易本身不會(huì)劣于對(duì)等的結(jié)果，在與一個(gè)非理性的交易對(duì)手金鄉(xiāng)交易時(shí)，還有可能獲得優(yōu)于對(duì)等的交易結(jié)果，因此它是一個(gè)好的策略。</p><p>　　有人或許要問，既然對(duì)等交易不賠也不賺，為什么還要?jiǎng)诿駛?cái)?shù)剡M(jìn)行呢？請(qǐng)注意，這里所謂的“對(duì)等”概念，是就交易本身而言的。雙方都不吃虧的交易就叫“對(duì)等”交易。但這里邊并沒有包括對(duì)等交易目的這個(gè)關(guān)鍵內(nèi)容。如果通過交易，雙方都能打到優(yōu)化各自資產(chǎn)或者是業(yè)務(wù)結(jié)構(gòu)的目的，形成新的資產(chǎn)增

18、值機(jī)會(huì)，那么，通過對(duì)等交易所獲得的最終結(jié)果將是“雙贏”，盡管可能存在交易的一方通過交易獲得的資產(chǎn)增殖潛力比另一方更大些的情形，但是，只要雙方同時(shí)都擴(kuò)大了自身資產(chǎn)的增殖潛力，那就可以稱為“雙贏”。這就是對(duì)一些理性的經(jīng)營(yíng)者在交易中只關(guān)心自己是否得到了應(yīng)該得到的錢，而不過問交易對(duì)手可能賺多少錢這種日益流行的經(jīng)濟(jì)學(xué)現(xiàn)象的合理解釋。</p><p>　　而影子價(jià)格正是確定交易底線的基本依據(jù)！</p><

19、p>　　2. 對(duì)偶線性規(guī)劃理論的概述</p><p>　　2.1 對(duì)偶線性規(guī)劃理論的發(fā)展歷程及現(xiàn)狀[2] [3]</p><p>　　線性規(guī)劃理論產(chǎn)生于20世紀(jì)30年代。1939年，蘇聯(lián)數(shù)學(xué)家康托羅維奇在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書中，最早提出和研究了線性規(guī)劃問題。 1947年，美國(guó)數(shù)學(xué)家丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問題的通用方法─單純形法，為這門學(xué)科奠定

20、了基礎(chǔ)。1947年，美國(guó)數(shù)學(xué)家諾伊曼提出對(duì)偶理論,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。 1951年，美國(guó)經(jīng)濟(jì)學(xué)家?guī)炱章拱丫€性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域；1960年，康托羅維奇再次發(fā)表《最佳資源利用的經(jīng)濟(jì)計(jì)算》，創(chuàng)立了享譽(yù)全球的線性規(guī)劃要點(diǎn)，對(duì)資源最優(yōu)分配理論做出了貢獻(xiàn)。為此，庫(kù)普曼斯與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。1984年，美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家卡馬卡提出求解線性規(guī)劃問題的投影尺度法，這是一個(gè)

21、有實(shí)用意義的新的多項(xiàng)式時(shí)間算法。這個(gè)算法引起了人們對(duì)內(nèi)點(diǎn)算法的關(guān)注，此后相繼出現(xiàn)看多種更為簡(jiǎn)單實(shí)用的內(nèi)點(diǎn)算法。隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，線性規(guī)劃的應(yīng)用越來(lái)越廣泛。它已成為人們合理利用有限資源制定最佳決策的有利工具。</p><p>　　由于對(duì)偶規(guī)劃問題的全面性，考慮的多面性，現(xiàn)在的很多經(jīng)濟(jì)問題都通過對(duì)偶規(guī)劃問題來(lái)解決。從而衍生出的影子價(jià)格也是現(xiàn)今各大企業(yè)在資產(chǎn)經(jīng)營(yíng)策略中一個(gè)非常重要的交易工具。它的應(yīng)用已經(jīng)遍及各

22、大企業(yè)的經(jīng)營(yíng)策略中。</p><p>　　2. 2 對(duì)偶問題的基本性質(zhì)[4] [5]</p><p>　　給定一個(gè)線性規(guī)劃問題</p><p>　　使用向量與矩陣表示形式為</p><p><b>　　1. 對(duì)稱性</b></p><p>　　對(duì)偶問題的對(duì)偶是原問題。</p>&

23、lt;p><b>　　2. 弱對(duì)偶性</b></p><p>　　設(shè)和分別是問題和的可行解，則</p><p><b>　　3. 無(wú)界性</b></p><p>　　問題和同時(shí)有最優(yōu)解的充分必要條件是它們同時(shí)有可行解。而且，若其中有一個(gè)問題無(wú)界，則另一個(gè)問題無(wú)解。</p><p><

24、b>　　4. 強(qiáng)對(duì)偶性</b></p><p>　　設(shè)和分別為和的可行解，則它們分別為和的最優(yōu)解當(dāng)且僅當(dāng)</p><p><b>　　5. 互補(bǔ)松弛性</b></p><p>　　設(shè)和分別為原問題和對(duì)偶問題的可行解，則它們分別為和的最優(yōu)解當(dāng)且僅當(dāng)</p><p>　　使用矩陣形式，可得和的互補(bǔ)松弛性

25、條件：</p><p><b>　　6. 唯一性</b></p><p>　　問題有非退化的最優(yōu)基可行解，那么，其對(duì)偶規(guī)劃有唯一的最優(yōu)解。</p><p>　　7. 對(duì)偶變量的經(jīng)濟(jì)解釋</p><p>　　假定所討論的是下面的線性規(guī)劃問題</p><p>　　其中 ——某工廠所擁有的種資源

26、的總量；</p><p>　　——生產(chǎn)每件第種產(chǎn)品需消耗第種資源的量。</p><p>　　該問題的實(shí)際背景是在資源有限的條件下安排生產(chǎn)，以使效益最大。</p><p>　　3 線性規(guī)劃的對(duì)偶原理及其應(yīng)用</p><p>　　3.1 對(duì)偶理論[6]</p><p>　　以如下一對(duì)問題來(lái)表示線性規(guī)劃問題的對(duì)偶：<

27、;/p><p>　　這里表示原問題，表示其對(duì)偶問題.</p><p>　　注意到兩個(gè)問題間的變換特點(diǎn)，這里為對(duì)偶問題的變量向量，每一個(gè)原問題的約束條件，對(duì)應(yīng)一個(gè)對(duì)偶變量（個(gè)）；每一個(gè)原問題變量對(duì)應(yīng)一個(gè)對(duì)偶問題約束條件（個(gè)）.原問題為求最大值，則對(duì)偶問題為求最小值.原問題與對(duì)偶問題中，其目標(biāo)函數(shù)系數(shù)與右端常數(shù)互換；約束條件系數(shù)矩陣互為轉(zhuǎn)置；約束條件符號(hào)則按一定規(guī)則轉(zhuǎn)換為此首先說(shuō)明原問題及對(duì)偶問題

28、稱為對(duì)偶的對(duì)稱形式，它們是互相逆轉(zhuǎn)的，現(xiàn)證明如下.</p><p>　　由于上式的對(duì)偶問題本身仍舊是一線性規(guī)劃問題，應(yīng)用轉(zhuǎn)置矩陣概念，可把它寫成如下形式：</p><p>　　以表示這個(gè)問題的對(duì)偶變量，則它的對(duì)偶問題為</p><p>　　而這個(gè)問題即為該問題的左邊問題，即原始的原問題.因此得出如下的推論：</p><p>　　推論 3.1

29、 對(duì)偶問題的對(duì)偶是原問題.</p><p>　　任何形式的線性規(guī)劃問題都能找到其對(duì)偶問題。對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問題：</p><p>　　先把它改寫成與其等價(jià)的形式：</p><p>　　以此為原問題，系數(shù)矩陣.引用對(duì)偶向量，且分塊為,相應(yīng)的對(duì)偶問題為</p><p>　　令,它是無(wú)限制的數(shù)，且簡(jiǎn)化了上面的表示.因此得出了如下一對(duì)問題：<

30、;/p><p><b>　　無(wú)限制</b></p><p>　　實(shí)際上，很多線性規(guī)劃問題包含有不同類型的約束條件，“大于或等于”，“等于”和“小于或等于”.變量也可以是：“”，“ ”和“無(wú)限制”.對(duì)這種混合形式的問題，我們提出一種轉(zhuǎn)換規(guī)則，由原問題的形式立刻可以寫出相應(yīng)的對(duì)偶問題，為清楚起見，先推導(dǎo)如下：</p><p>　　考慮如下線性規(guī)劃問題：

31、</p><p>　　引進(jìn)松弛變量和，把問題變換成標(biāo)準(zhǔn)形式，得</p><p>　　注意，相應(yīng)上面問題的對(duì)偶變量和，分別標(biāo)注在上式對(duì)應(yīng)的約束條件的左邊，因此，對(duì)偶問題為</p><p><b>　　無(wú)限制</b></p><p><b>　　這也就是</b></p><p>

32、<b>　　，無(wú)限制，</b></p><p>　　3.2 對(duì)偶性的其他問題[7]</p><p>　　對(duì)偶定理有多種解釋，是由許多學(xué)者提出并以不同形式發(fā)表的，其中包括</p><p>　　線性方程組的對(duì)偶定理另一種形式是：線性方程組有解當(dāng)且僅當(dāng)對(duì)任意滿足的行向量有成立.這是提出的.</p><p>　　下面的系統(tǒng)有且

33、只有一個(gè)是可行的：</p><p>　　我們將給出線性不等式系統(tǒng)的對(duì)偶定理.首先我們給出由原問題導(dǎo)出對(duì)偶問題的方法.主要思想是利用原問題的線性約束找到它的最優(yōu)值的一個(gè)下界，即我們線性地合并給定的約束來(lái)得到這個(gè)下界.對(duì)偶問題轉(zhuǎn)化為：最大化此下界.</p><p>　　3.3 對(duì)偶規(guī)劃問題的三種解法介紹[8]</p><p>　　例2.1 利用對(duì)偶轉(zhuǎn)換規(guī)則，將下列線

34、性規(guī)劃模型轉(zhuǎn)換為其對(duì)偶規(guī)劃模型。</p><p>　　某原問題的數(shù)學(xué)模型如下：</p><p>　　求解上式的對(duì)偶規(guī)劃問題有三種方法。</p><p>　　第一種是先把上式轉(zhuǎn)換為對(duì)偶模型，并讓對(duì)應(yīng)，讓對(duì)應(yīng)，使用普通的單純形法線性規(guī)劃程序求解出對(duì)偶規(guī)劃的結(jié)果。使用這種方法求解對(duì)偶規(guī)劃問題，需要手工完成一次由原問題向?qū)ε紗栴}轉(zhuǎn)換的過程，當(dāng)問題規(guī)模較小時(shí)，使用這種方法不會(huì)

35、出現(xiàn)多大的問題，但是當(dāng)問題規(guī)模較大時(shí)，問題就來(lái)了，一是轉(zhuǎn)換過程非常繁瑣，工作量大；二是特別容易出錯(cuò)，效率很低。</p><p>　　第二種方法是利用計(jì)算機(jī)程序，直接讀取原問題解算過程中自動(dòng)生成的數(shù)據(jù)文件，自動(dòng)地轉(zhuǎn)換原問題為對(duì)偶問題，并直接求解，給出對(duì)偶規(guī)劃的結(jié)果來(lái)。</p><p>　　第三種解法則是利用原問題的求解數(shù)據(jù)直接獲得對(duì)偶問題的最優(yōu)解。</p><p>　

36、　將下述對(duì)偶問題模型轉(zhuǎn)換為對(duì)偶模型舉例。</p><p><b>　　目標(biāo)函數(shù) </b></p><p><b>　　約束條件</b></p><p><b>　　無(wú)約束</b></p><p>　　根據(jù)前述的化標(biāo)準(zhǔn)型規(guī)則，將上述模型改寫為標(biāo)準(zhǔn)型</p><

37、;p><b>　　目標(biāo)函數(shù) </b></p><p><b>　　約束條件</b></p><p><b>　　無(wú)約束</b></p><p>　　根據(jù)上述對(duì)偶轉(zhuǎn)換規(guī)則，其對(duì)偶線性規(guī)劃問題模型為</p><p><b>　　無(wú)約束</b><

38、/p><p>　　根據(jù)前述的化標(biāo)準(zhǔn)型規(guī)則，將上式改寫為標(biāo)準(zhǔn)型</p><p><b>　　無(wú)約束</b></p><p>　　對(duì)于原問題,直接讀取數(shù)據(jù)后求解對(duì)偶最優(yōu)解程序并不適用，如果要求解之，可以使用第一種方法，使用對(duì)上式求解。</p><p>　　如前所述，對(duì)于部分問題而言，還存在第三種求解對(duì)偶規(guī)劃問題的簡(jiǎn)便方法，那就是

39、，通過原問題最優(yōu)解及其迭代表格中所給出的信息，直接獲得對(duì)偶問題的最優(yōu)解。</p><p>　　如果遇到無(wú)法通過原問題解及其迭代表格中所給出的信息直接獲得對(duì)偶問題最優(yōu)解的問題，仍然必須使用人工或者自動(dòng)的方式對(duì)原問題的模型進(jìn)行轉(zhuǎn)換，獲得對(duì)偶模型后再使用普通單純形法求解。當(dāng)然也可以由程序自動(dòng)地讀取原問題的數(shù)據(jù)直接給出對(duì)偶規(guī)劃的結(jié)果。</p><p>　　3.4 最優(yōu)對(duì)偶變量（影子價(jià)格）的經(jīng)濟(jì)解

40、釋[9] [10]</p><p>　　我們之所以對(duì)線性規(guī)劃的對(duì)偶問題感興趣，是由于對(duì)偶問題的最優(yōu)解相對(duì)于原始線性規(guī)劃問題有特殊的經(jīng)濟(jì)含意，它可以從另一個(gè)角度加深我們對(duì)原線規(guī)劃模型最優(yōu)解的理解。</p><p>　　對(duì)于線性規(guī)劃的原始問題和對(duì)偶問題：</p><p>　　原始問題 對(duì)偶問題</p>

41、;<p>　　求 求 </p><p>　　滿足 滿足</p><p>　　設(shè)B為原始問題的最優(yōu)基，且A為的矩陣，A的后列組成子陣D，C的后列組成子陣，則此時(shí)相對(duì)成本向量</p><p>　　的每個(gè)分量都是非負(fù)的。所以有</p&g

42、t;<p><b>　　而最優(yōu)解為。</b></p><p>　　下面就來(lái)驗(yàn)證：原始問題的最優(yōu)基為時(shí)，其單純形乘子向量即為相應(yīng)對(duì)偶問題的最優(yōu)解。</p><p>　　由于 </p><p>　　所以有 (因?yàn)?</p><p><b

43、>　　這樣，得證。</b></p><p>　　因此，是對(duì)偶可行的。又因?yàn)椋?lt;/p><p>　　這說(shuō)明，作為對(duì)偶變量，其對(duì)偶問題目標(biāo)函數(shù)值等于原始問題最優(yōu)解時(shí)的目標(biāo)函數(shù)。根據(jù)對(duì)偶定理（如果線性規(guī)劃的原始問題和對(duì)偶問題中，一個(gè)存在有限最優(yōu)解，那么另一個(gè)也有最優(yōu)解，而且相應(yīng)的目標(biāo)函數(shù)值相等；如果任何一個(gè)問題目標(biāo)函數(shù)值無(wú)上界，那么另一個(gè)問題就無(wú)可行解。）可知，應(yīng)為對(duì)偶問題的最

44、優(yōu)解。</p><p>　　在最優(yōu)解非退化情況下，對(duì)于向量的很小變化將不會(huì)引起最優(yōu)基的改變。因此，對(duì)于而言，最優(yōu)解應(yīng)為：</p><p><b>　　即有</b></p><p>　　此時(shí)目標(biāo)函數(shù)就變成：</p><p><b>　　即有</b></p><p>　　如果向量

45、中只有某一分量由變化到，而其他分量都保持不變，則目標(biāo)函數(shù)的增量為：</p><p><b>　　即有：</b></p><p>　　上述是以不改變?cè)瓉?lái)最優(yōu)基為前提的微小變動(dòng)，記為偏導(dǎo)數(shù)形式則有：</p><p>　　這說(shuō)明給出了當(dāng)發(fā)生微小變動(dòng)時(shí)所引起目標(biāo)函數(shù)值的變化率，也就是說(shuō)反映了的邊際效益。這里所謂的邊際效益是指當(dāng)該約束右端數(shù)值由再增加一個(gè)

46、數(shù)量單位時(shí)所引起目標(biāo)函數(shù)值的增加，它反映了最后增加的那個(gè)數(shù)量單位對(duì)系統(tǒng)帶來(lái)的效益。所以也稱為的影子價(jià)格。利用影子價(jià)格這個(gè)重要的經(jīng)濟(jì)意義，可對(duì)線性規(guī)劃模型及其最優(yōu)解做進(jìn)一步的分析。</p><p>　　在利用影子價(jià)格的經(jīng)濟(jì)含義進(jìn)行分析時(shí)，往往涉及到線性規(guī)劃的另一個(gè)重要定理，即補(bǔ)松弛定理。該定理敘述了線性規(guī)劃原始問題和對(duì)偶問題都是最優(yōu)解的充分必要條件為：</p><p><b>　　

47、若，則必有；</b></p><p><b>　　若，則必有。</b></p><p>　　這說(shuō)明，當(dāng)線性規(guī)劃原問題在得到最優(yōu)解時(shí)，如果某個(gè)約束是“松”的，也就是說(shuō)該約束的松弛變量在最優(yōu)解中取大于的值，那么與該約束相應(yīng)的最有對(duì)偶變量一定等于；反之，如果某個(gè)最優(yōu)對(duì)偶變量取非的數(shù)值，那么，在原問題得到最優(yōu)解時(shí)，其相應(yīng)約束條件就一定是“緊”的，也就是說(shuō)該約束的松

48、弛變量一定為。上述定理告訴我們，如果在得到最優(yōu)解時(shí)，某種資源并未完全利用，尚有一定的剩余，其剩余量就是該約束中松弛變量的取值，那么與該約束相對(duì)應(yīng)的影子價(jià)格就一定為，也就是說(shuō)，該種資源的邊際效益是。因?yàn)椋诘玫阶顑?yōu)解時(shí)，這種資源并不稀缺，所以此時(shí)再增加這種資源不會(huì)帶來(lái)任何效益，因此它的影子價(jià)格是。反之，如果某種資源的影子價(jià)格大于，這說(shuō)明再增加該種資源的可獲取量，還會(huì)帶來(lái)一定的經(jīng)濟(jì)效益，也就是說(shuō)這種資源是比較緊缺的，那么在原始問題的最優(yōu)解中

49、，這種資源必定已被全部利用，亦即相應(yīng)這種資源限制量約束條件內(nèi)的松弛變量一定為，換句話說(shuō)，這個(gè)約束條件兩端必然保持相等。</p><p>　　某企業(yè)用種資源來(lái)生產(chǎn)種產(chǎn)品.已知每一種產(chǎn)品對(duì)各資源的單位消耗量和各種資源的現(xiàn)有量（或可供量）.要求計(jì)劃各產(chǎn)品的生產(chǎn)量，使企業(yè)獲利最大.問題的數(shù)學(xué)模型如</p><p><b>　　所示，即為</b></p><

50、p>　　其中，和分別為第種產(chǎn)品的生產(chǎn)量和單位利潤(rùn)，為第種資源的現(xiàn)有量.</p><p>　　設(shè)上述問題的最優(yōu)解為，對(duì)應(yīng)最優(yōu)基為，則便是對(duì)偶問題</p><p>　　的解，記為于是總利潤(rùn)的最大值</p><p><b>　　.</b></p><p>　　由上式可知，當(dāng)資源的現(xiàn)有量從改變?yōu)闀r(shí)（其他資源不變），最大總利

51、潤(rùn)（在最優(yōu)基不變的條件下）將從改變?yōu)?即知是資源增加一單位時(shí)最大總利潤(rùn)的增加量.可見為第種資源的影子價(jià)格.顯然，影子價(jià)格不同于市場(chǎng)價(jià)格，它是針對(duì)具體的經(jīng)濟(jì)結(jié)構(gòu)在最優(yōu)計(jì)劃前提下經(jīng)計(jì)算得出的一種潛在價(jià)格.</p><p>　　由對(duì)偶規(guī)劃的互補(bǔ)松弛性質(zhì)可知，當(dāng)時(shí)，必有.此式表明，在最優(yōu)計(jì)劃下，資源的現(xiàn)有量將全部用完.這意味著是短缺資源（或稱短線資源）.這是增加將使總利潤(rùn)提高.反之，如果，即在最優(yōu)計(jì)劃下的現(xiàn)有量有剩余，這

52、時(shí)必有.這表明過剩資源（或稱長(zhǎng)線資源）的影子價(jià)格為零.這時(shí)增加將不會(huì)提高總利潤(rùn)，反而增加庫(kù)存積壓.所以影子價(jià)格在一定范圍內(nèi)也反映了資源的稀缺成都.在經(jīng)濟(jì)管理決策分析中，影子價(jià)格是一個(gè)重要的數(shù)量依據(jù).</p><p>　　例2.2 某工廠生產(chǎn)兩種產(chǎn)品，已知生產(chǎn)產(chǎn)品每公斤需耗煤噸，耗電百度，用工個(gè)工作日（一個(gè)勞動(dòng)日指一個(gè)工人勞動(dòng)一天）；生產(chǎn)產(chǎn)品每公斤需耗煤噸，耗電百度，用工個(gè)勞動(dòng)日. 產(chǎn)品每公斤的利潤(rùn)是元，產(chǎn)品每公

53、斤的利潤(rùn)是元.因客觀條件所限，該廠只能得到煤噸、電萬(wàn)度、勞力個(gè)勞動(dòng)日.問該廠應(yīng)生產(chǎn)產(chǎn)品各多少，才能使獲得的總利潤(rùn)最大？有關(guān)數(shù)據(jù)如下表所示.</p><p>　　用分別表示產(chǎn)品的生產(chǎn)量（單位：公斤）.問題的線性規(guī)劃模型為</p><p><b>　　今要求：</b></p><p>　　求出問題的最優(yōu)生產(chǎn)方案；</p><p&

54、gt;　　求出各種資源（煤、電、勞力）的影子價(jià)格；</p><p>　　若廠方想增加一種新產(chǎn)品，已知生產(chǎn)每公斤需耗煤噸，耗電百度，用工個(gè)勞動(dòng)日.</p><p>　　問產(chǎn)品的單位利潤(rùn)多大才值得投產(chǎn)？</p><p>　　解 將原問題轉(zhuǎn)化為求解下列標(biāo)準(zhǔn)形式的線性規(guī)劃問題：</p><p>　　這里為松弛變量.然后用單純形法求解.迭代過程如下列

55、表所示.</p><p><b>　　表</b></p><p><b>　　表</b></p><p><b>　　表</b></p><p>　　從最優(yōu)單純形表（表）得知，原問題的最優(yōu)生產(chǎn)方案為：生產(chǎn)產(chǎn)品A公斤，產(chǎn)品公斤.可獲利潤(rùn)元.</p><p>

56、;　　在最優(yōu)單純形表中，松弛變量的對(duì)應(yīng)檢驗(yàn)數(shù)的相反數(shù)便是各對(duì)應(yīng)資源的影子價(jià)格.據(jù)此得知，煤的影子價(jià)格為元/噸，電的影子價(jià)格為元/百度，勞力的影子價(jià)格為元/勞動(dòng)日.由此可見，對(duì)該廠的最優(yōu)生產(chǎn)計(jì)劃而言，煤是長(zhǎng)線資源，電力和勞動(dòng)力是短線資源.</p><p>　　在各資源限額不變的前提下，要投產(chǎn)新產(chǎn)品，就得從產(chǎn)品的生產(chǎn)中抽出資源.每生產(chǎn)公斤產(chǎn)品，需抽出煤噸、電百度、勞力個(gè)勞動(dòng)日.因一種資源的影子價(jià)格就是該資源增加（或減

57、少）一個(gè)單位時(shí)最大總利潤(rùn)將增加（減少）的數(shù)量，所以，每生產(chǎn)產(chǎn)品公斤，將使產(chǎn)品的生產(chǎn)失去利潤(rùn)</p><p><b>　?。ㄔ?</b></p><p>　　由此可見，新產(chǎn)品的單位利潤(rùn)必須在元/公斤以上，才值得投產(chǎn).</p><p>　　3.5 影子價(jià)格在企業(yè)經(jīng)營(yíng)管理中的應(yīng)用[11][12]</p><p>　　一個(gè)線

58、性規(guī)劃對(duì)偶問題的最優(yōu)解簡(jiǎn)稱為“對(duì)偶最優(yōu)解”，也稱為“影子價(jià)格”，在經(jīng)濟(jì)上可以解釋為約束條件所付出的代價(jià)。</p><p>　　在計(jì)算線性規(guī)劃問題的檢驗(yàn)數(shù)時(shí)， 表示生產(chǎn)該項(xiàng)產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品的產(chǎn)值大于產(chǎn)品的隱含成本時(shí)，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可以安排；當(dāng)產(chǎn)品的產(chǎn)值小于產(chǎn)品的隱含成本時(shí)，表明生產(chǎn)該項(xiàng)產(chǎn)品無(wú)利可圖，用這些資源來(lái)生產(chǎn)別的產(chǎn)品可能更為有利，在生產(chǎn)計(jì)劃中就不予安排了?？?/p>

59、見，影子價(jià)格為生產(chǎn)計(jì)劃的安排提供了理論依據(jù)。從另外一個(gè)角度看，資源的市場(chǎng)價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)，產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。某種資源的影子價(jià)格高于市場(chǎng)價(jià)格，企業(yè)的管理者可以考慮對(duì)這種資源進(jìn)行投入的增加，進(jìn)而擴(kuò)大生產(chǎn)規(guī)模，獲得利潤(rùn)。隨著不斷增加資源的投入量，資源的影子價(jià)格就會(huì)逐漸變小，當(dāng)資源的影子價(jià)格等于市場(chǎng)價(jià)格時(shí)，就不應(yīng)再增加該種資源的投入；某種

60、資源的影子價(jià)格低于市場(chǎng)價(jià)格，企業(yè)的管理者應(yīng)考慮把這種資源的一部分用來(lái)生產(chǎn)別的產(chǎn)品，隨著減少該種資源的投入，資源的影子價(jià)格又會(huì)逐漸增加，當(dāng)資源的影子價(jià)格等于市場(chǎng)價(jià)格時(shí)，不再減少該種資源。可見，資源的影子價(jià)格又是一種機(jī)會(huì)成本。對(duì)資源在市場(chǎng)價(jià)格方面的估算，買賣雙方可以用影子價(jià)</p><p>　　下面以一個(gè)生產(chǎn)計(jì)劃問題為例來(lái)討論對(duì)偶最優(yōu)解的經(jīng)濟(jì)效益。</p><p>　　某企業(yè)目前生產(chǎn)3種產(chǎn)品,

61、所消耗的資源主要是工時(shí)和原材料，生產(chǎn)1個(gè)單位產(chǎn)品所需的資源以及每天可利用的資源量如下表所示，問如何制定生產(chǎn)計(jì)劃，使3種產(chǎn)品總利潤(rùn)最大？</p><p>　　生產(chǎn)計(jì)劃問題已知數(shù)據(jù)表</p><p>　　生源：生產(chǎn)單位產(chǎn)品所需資源。</p><p>　　上例的線性規(guī)劃模型如下：</p><p>　　目標(biāo)要求是使3種產(chǎn)品的總利潤(rùn)極大化</p&

62、gt;<p><b>　　工時(shí)比例約束</b></p><p><b>　　原材料約束</b></p><p>　　使用軟件，用單純形法求解得到最終表如下表所示。</p><p><b>　　最終表</b></p><p>　　一方面，從基變量列和解答列可以看出原

63、問題的最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值：</p><p>　　另一方面，從檢驗(yàn)數(shù)行可以得到對(duì)偶最優(yōu)解和對(duì)偶問題的目標(biāo)函數(shù)最優(yōu)值，只要將所有非基變量的檢驗(yàn)數(shù)變號(hào)，得到</p><p>　　現(xiàn)在來(lái)分析的各分量與的對(duì)應(yīng)關(guān)系。</p><p>　　原問題有兩個(gè)約束條件對(duì)應(yīng)著對(duì)偶問題的兩個(gè)變量。最終表中的分別表示兩個(gè)約束條件中剩余的資源量，它們所對(duì)應(yīng)的檢驗(yàn)數(shù)的相反數(shù)就正好是對(duì)應(yīng)的兩個(gè)對(duì)

64、偶變量即，而所對(duì)應(yīng)檢驗(yàn)數(shù)的相反數(shù)分別對(duì)應(yīng)著對(duì)偶問題中個(gè)約束條件的剩余變量，即。</p><p>　　進(jìn)一步可知，表示如果總工時(shí)比例增加個(gè)單位（即總工時(shí)翻一番），則產(chǎn)品總利潤(rùn)將增加千元，則表明若原材料增加，產(chǎn)品總利潤(rùn)將增加千元。</p><p>　　而則說(shuō)明如果生產(chǎn)一個(gè)單位的產(chǎn)品，將使產(chǎn)品總利潤(rùn)下降千元。</p><p>　　由上面的分析可以判斷出，目前最敏感的資源在

65、于勞動(dòng)工時(shí)，它的變化對(duì)產(chǎn)品總利潤(rùn)的影響最大，因此勞動(dòng)力是最關(guān)鍵的生產(chǎn)環(huán)節(jié)，若能采取有力措施增加勞動(dòng)工時(shí)，則產(chǎn)品總利潤(rùn)將得到較大的提高。</p><p>　　在計(jì)算機(jī)求解結(jié)果中見約束條件的影子價(jià)格和變量的機(jī)會(huì)成本統(tǒng)稱為機(jī)會(huì)成本，如下表所示。</p><p>　　“生產(chǎn)計(jì)劃問題”求解綜合結(jié)果表</p><p>　　綜上所述，影子價(jià)格通過獲取一個(gè)單位的追加產(chǎn)品因素，去測(cè)量

66、放寬一個(gè)約束條件的價(jià)值，比較追加資源的價(jià)值和資源的實(shí)際成本，就能比較有把握地作出各種可行的決策。</p><p><b>　　4. 結(jié)論</b></p><p>　　本文總的介紹了對(duì)偶線性規(guī)劃的定義以及一些特殊屬性，還有對(duì)偶規(guī)劃的一種延生——影子價(jià)格。主要是為了說(shuō)明以下線性規(guī)劃在實(shí)際應(yīng)用中兩點(diǎn)：一方面考慮在一定資源限制條件下，如何安排生產(chǎn)使工作成果最大；另一方面要求

67、，如何計(jì)劃生產(chǎn)，使完成既定任務(wù)的前提下，消耗最少。并且在各大企業(yè)中的應(yīng)用已經(jīng)變得越來(lái)越廣泛，已經(jīng)成為一種不可或缺的手段，是為了買賣雙方獲得雙贏利益的最大保障。[13] [14]</p><p>　　影子價(jià)格在對(duì)偶規(guī)劃行業(yè)有著很大的發(fā)展前景，它也日漸成為企業(yè)挖潛革新的途徑，且對(duì)市場(chǎng)資源的最優(yōu)配置起著推進(jìn)作用。它可以預(yù)測(cè)產(chǎn)品的價(jià)格，并作為同類企業(yè)經(jīng)濟(jì)效益評(píng)估指標(biāo)之一。[15]</p><p>

68、<b>　　參考文獻(xiàn)</b></p><p>　　[1] 高紅衛(wèi).實(shí)用線性規(guī)劃工具[M].北京：科學(xué)出版社，2007，1：119-119.</p><p>　　[2] 運(yùn)籌學(xué)編寫組.運(yùn)籌學(xué)[M].第三版.北京:清華大學(xué)出版社，2005，6:1-2.</p><p>　　[3] 張干宗.線性規(guī)劃[M].第二版.武漢:武漢大學(xué)出版社，2008，6:

69、1-1.</p><p>　　[4] 朱德通.最優(yōu)化模型與實(shí)驗(yàn)[M].上海：同濟(jì)大學(xué)出版社，2003，4：49-50.</p><p>　　[5] 胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].第三版.北京：清華大學(xué)出版社，2007，4：55-57.</p><p>　　[6] 胡清淮，魏一鳴.線性規(guī)劃及其應(yīng)用[M].北京：科學(xué)出版社，2004，3：94-96.</p&g

70、t;<p>　　[7] Leonid Nison Vaserstein,Christopher Cattelier Byrne.Introduction to Linear Programming to Linear Programming[M].Beijing:China Machine Press，2006，1：125-126.</p><p>　　[8] 高紅衛(wèi).線性規(guī)劃方法應(yīng)用詳解[M].北

71、京：科學(xué)出版社，2004，7：101-102.</p><p>　　[9] 江道琪，何建坤，陳松華.實(shí)用線性規(guī)劃方法及其支持系統(tǒng)[M].北京：清華大學(xué)出版社，2006，4：45-47.</p><p>　　[10] 張干宗.線性規(guī)劃[M].第二版.武漢：武漢大學(xué)出版社，2008，6：92-92.</p><p>　　[11] 姚軍，苑延華.淺談線性規(guī)劃對(duì)偶問題的經(jīng)濟(jì)

72、解釋——影子價(jià)格[J].商業(yè)文化，2009，12：270-270.</p><p>　　[12] 徐渝，賈濤.運(yùn)籌學(xué)（上冊(cè)）[M].北京：清華大學(xué)出版社，2005，2：58-60.</p><p>　　[13] 邱菀華，馮允成，魏法杰，周泓.運(yùn)籌學(xué)教程[M].北京：機(jī)械工業(yè)出版社，2004，5:42-42.</p><p>　　[14] Frederick S.Hi