whut運籌學(xué)-7 矩陣表示 對偶問題 理論 影子價格.ppt

1、對偶理論和靈敏度分析，單純形法的矩陣描述線性規(guī)劃的對偶問題對偶問題的經(jīng)濟解釋-影子價格對偶單純形法靈敏度分析，例子，單純形法的矩陣描述，CB=2 0 3，CN=0 0，單純形法的矩陣描述，B，CB，XB，CN，xn，N，B，單純形法的矩陣描述，B-1 N，B-1 b，單純形法的矩陣描述，考慮單純形法的矩陣描述，單純形法的矩陣描述，繼續(xù)討論前面的例子，CB=203，CBB-1=1.51解3360將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)類型，單純形法的矩陣描述，并用單純形法求解如下。線性規(guī)劃問題的對偶問題，1。提出雙重問題)，1例1一個工廠用兩臺機器生產(chǎn)三種產(chǎn)品，相關(guān)數(shù)據(jù)見下表：如何組織生產(chǎn)以使總利潤最大化？X1、X2

2、、X3-分別生產(chǎn)的產(chǎn)品A、B和C的數(shù)量。例2如果另一家工廠想租用這兩臺機器來生產(chǎn)產(chǎn)品，工廠應(yīng)該如何確定合理的租金？線性規(guī)劃問題的對偶問題，y1，y2 -機器一和機器二的租金，例1和例2是同一問題的兩個方面，兩個線性規(guī)劃模型是一對對偶問題，2。原問題與對偶問題的關(guān)系，對稱關(guān)系，例3找到了對偶問題的以下問題，對稱形式對偶關(guān)系，對偶問題的線性規(guī)劃問題。非對稱關(guān)系，練習(xí)：線性規(guī)劃問題的對偶問題，原問題與對偶問題的對偶關(guān)系對照表，線性規(guī)劃問題的對偶問題，例4，線性規(guī)劃問題的對偶問題，例5，線性規(guī)劃問題的對偶問題，考慮到對稱關(guān)系的基本性質(zhì)，對偶問題是原問題。如果原(對偶)問題有無界解，那么對偶(原)問題就

3、沒有可行解。對偶問題的基本性質(zhì)是不可行、不可行、無界和不可行。如果原問題有一個最優(yōu)解，對應(yīng)的最優(yōu)基是B，那么對偶問題也有一個最優(yōu)解，最優(yōu)解是(CBB-1)T；和目標(biāo)函數(shù)值相等，都是CBB-1b。對偶問題的基本性質(zhì)，假設(shè)原問題是它的對偶問題，原問題的簡單表的檢查數(shù)行對應(yīng)于它的對偶問題的基本解：例如，已知通過用單純形法求解下面的線性規(guī)劃問題獲得的最終表如下，試圖確定對偶問題的最優(yōu)解，對偶問題的基本性質(zhì)，并且解3360被稱為CB=(。對偶問題的基本性質(zhì)使得原問題的可行解是對偶問題的可行解，那么它們分別是原問題和對偶問題的最優(yōu)解，當(dāng)且僅當(dāng)：例6:線性規(guī)劃問題已知，且其最優(yōu)解為x*1=2，x*2=0，x

4、*3=8。試著利用對偶問題的性質(zhì)找到它對偶數(shù)問題的最優(yōu)解。這個線性規(guī)劃問題的對偶問題是：將x*1=2，x*2=0，x*3=8代入原線性規(guī)劃問題的約束，我們可以看到第一個約束是嚴格不等式，然后y*1=0。是從互補松弛中得到的，而對偶問題的基本性質(zhì)也是由于x * 1 x *得到的。因此，對偶問題的第一個約束條件和第三個約束條件應(yīng)該相等，即8y*1 4 y*2 2y*3=60，y*1 1.5y*2 0.5y*3=20。解是y*2=10，y*3=10。因此，對偶問題的最優(yōu)解是y * 1=線性規(guī)劃對偶問題的經(jīng)濟解釋影子價格，假設(shè)它分別是原問題和對偶問題的最優(yōu)解，是基于對偶問題的基本性質(zhì)。因此，變量的經(jīng)濟

5、意義是在其他條件不變的情況下，第一資源單位變化引起的目標(biāo)函數(shù)值的增加。，1影子價格的解釋，變量的值代表ith資源的估值。這種估價不是來源一的市場價格，而是具體工廠根據(jù)資源在生產(chǎn)中的貢獻所作的估價，這就是所謂的“影子價格”。影子價格是雙解的一個非常生動的名稱，它不僅表明雙解是對系統(tǒng)內(nèi)部資源的客觀評價，而且表明它是一個虛構(gòu)的價格，而不是真實的價格。線性規(guī)劃對偶問題的經(jīng)濟解釋影子價格，例如，一個工廠用三臺機器生產(chǎn)兩種產(chǎn)品，相關(guān)數(shù)據(jù)見下表：如何組織生產(chǎn)以使總利潤最大化？a (m) b (m)可用資源(小時)機器I 1 2 8機器II 4 0 16機器III 0 4 12利潤2 3、x1、x2-a和b分別生產(chǎn)的產(chǎn)品數(shù)量，線性規(guī)劃對偶問題的經(jīng)濟解釋-影子價格問題：如果另一個工廠想租賃這三臺機器來生產(chǎn)產(chǎn)品，y1、y2、y2 -機器I、機器II和機器III的租金， 線性規(guī)劃對偶問題的經(jīng)濟學(xué)解釋影子價格，2影子價格的作用，影子價格的大小反映了系統(tǒng)中資源的稀缺性，根據(jù)互補松弛，當(dāng)一個資源的影子價格為0時，該資源沒有被充分利用，仍然有剩余； 當(dāng)一種資源的影子價格不為0時，該資源已經(jīng)在生產(chǎn)中被消耗，目前是稀缺的。這時，如果經(jīng)理增加資源的供給，總收入就會增加。線性規(guī)劃雙重問題的經(jīng)濟學(xué)解釋-影子價格，它可以調(diào)節(jié)市場。在完全市場經(jīng)濟條件下，當(dāng)一種資源的