線性規(guī)劃及其應用線性規(guī)劃的對偶理論

1第一頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論2重慶大學經濟與工商管理學院肖智

(3.4-1)

上述問題是企業(yè)利用已有的資源,通過自己加工、生產出產品進行銷售而獲得收入。企業(yè)是利潤最大化為目標。因此，對于該問題也可考慮另一種經營問題，即出租（或出讓）資源，來獲得收入。該問題的關鍵是確定資源的價格，特別是要確定資源的價格在什么條件下，使出租（或出讓）資源所獲的最少收入與自己生產所獲最大收入相同.為此，不妨假設木工與油漆工的單位工時租金分別為：y1和y2，可得數學模型如下：第二頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論3重慶大學經濟與工商管理學院肖智

(3.4-2)

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

第三頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論4重慶大學經濟與工商管理學院肖智二、如何將原問題轉化為對偶問題1、轉化原則：

表3.4-1對偶關系對應表原問題（或對偶問題）對偶問題（或原問題）目標函數maxZ目標函數minW變量n個約束條件n個≥≥0≤0≤無限制＝約束條件m個變量m個≥0≤≥≤0＝無限制約束條件右邊常數項目標函數變量系數目標函數變量系數約束條件右邊常數項第四頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論5重慶大學經濟與工商管理學院肖智2、例3.4.2原問題：

(3.4-5)

對偶問題：

(3.4-6)第五頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論6重慶大學經濟與工商管理學院肖智三、線性規(guī)劃的對偶理論

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

3）對偶單純形7、例：對例3.4.1用上述方法2)得原問題的最優(yōu)單純形表第十二頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論13重慶大學經濟與工商管理學院肖智2、例：對例3.4.1用上述方法2)得原問題的最優(yōu)單純形表表3.4-2最優(yōu)單純形表cj503000bxBCBx1x2x3x4x304310120x40210150σj5030000x30011-220x15011/201/225σj050-251250x230011-220x15010-1/23/215σj00-5-151350第十三頁，共十五頁，編輯于2023年，星期三§3.4線性規(guī)劃對偶理論14重慶大學經濟與工商管理學院肖智原問題的最優(yōu)解為：X*=(15,20)T，最優(yōu)值為：