whut運(yùn)籌學(xué)-7 矩陣表示 對(duì)偶問題 理論 影子價(jià)格.ppt

1、對(duì)偶理論和靈敏度分析，單純形法的矩陣描述線性規(guī)劃的對(duì)偶問題對(duì)偶問題的經(jīng)濟(jì)解釋-影子價(jià)格對(duì)偶單純形法靈敏度分析，例子，單純形法的矩陣描述，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ī)劃問題的對(duì)偶問題，1。提出雙重問題)，1例1一個(gè)工廠用兩臺(tái)機(jī)器生產(chǎn)三種產(chǎn)品，相關(guān)數(shù)據(jù)見下表：如何組織生產(chǎn)以使總利潤(rùn)最大化？X1、X2

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

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

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

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