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

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

2、p><p>　　學生姓名 學號 </p><p>　　指導教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要:對偶線性規(guī)劃是運籌學的一個重要分支，并應用到社會各個方面。本文首先介紹了對

3、偶線性規(guī)劃理論產(chǎn)生的背景，以及它的發(fā)展歷程和發(fā)展方向。接著敘述了解決對偶線性規(guī)劃問題的方法及其算法。我們通過分析問題建立數(shù)學模型，使用適當方法求出最優(yōu)解，并對其進行分析得到該問題的最優(yōu)值。最后運用對偶線性規(guī)劃理論來解決相關(guān)實際問題，即它被應用的過程。</p><p>　　關(guān)鍵詞:對偶線性規(guī)劃；數(shù)學模型；最優(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. 對偶線性規(guī)劃理論的概述3</p><p>　　2.1 對偶線性規(guī)劃理論的發(fā)展歷程及現(xiàn)狀3</p><p>　　2. 2 對偶問題的基本性質(zhì)3&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、</p><p>　　引進松弛變量和，把問題變換成標準形式，得</p><p>　　注意，相應上面問題的對偶變量和，分別標注在上式對應的約束條件的左邊，因此，對偶問題為</p><p><b>　　無限制</b></p><p><b>　　這也就是</b></p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、斤的利潤是元.因客觀條件所限，該廠只能得到煤噸、電萬度、勞力個勞動日.問該廠應生產(chǎn)產(chǎ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;　　求出各種資源（煤、電、勞力）的影子價格；</p><p>　　若廠方想增加一種新產(chǎn)品，已知生產(chǎn)每公斤需耗煤噸，耗電百度，用工個勞動日.</p><p>　　問產(chǎn)品的單位利潤多大才值得投產(chǎn)？</p><p>　　解 將原問題轉(zhuǎ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)品公斤.可獲利潤元.</p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

69、1-1.</p><p>　　[4] 朱德通.最優(yōu)化模型與實驗[M].上海：同濟大學出版社，2003，4：49-50.</p><p>　　[5] 胡運權(quán)，郭耀煌.運籌學教程[M].第三版.北京：清華大學出版社，2007，4：55-57.</p><p>　　[6] 胡清淮，魏一鳴.線性規(guī)劃及其應用[M].北京：科學出版社，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ī)劃方法應用詳解[M].北

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

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