1、線性規(guī)劃的對偶理論包括以下幾個基本定理。,定理1 （對稱性定理）,2.2 線性規(guī)劃的對偶理論,定理2 （弱對偶定理）,即對偶問題的對偶是原問題。,設(shè)x和y分別是原問題和對偶問題的可行解，則必有cxyb，即原問題的目標值小于對偶問題的目標值,定理3 （無界性）,若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解。,若原（對偶）問題有可行解,對偶（原）問題無可行解，則原（對偶）問題一定無界；,注:此定理可以判定解的情況,定理4 （可行解是最優(yōu)解的性質(zhì)）,定理5 （強對偶定理）,設(shè)X*是原問題的可行解，Y*是對偶問題的可行解，當CX*=Y*b時， X*與Y*是最優(yōu)解 。,若原問題有最優(yōu)解，

2、那么對偶問題也有最優(yōu)解，且目標函數(shù)值相等,綜合上述結(jié)論得原問題與對偶問題的解的關(guān)系,一般是：cxyb,原問題與對偶問題解的對應(yīng)關(guān)系,由原問題與對偶問題的解的關(guān)系可以判定線性規(guī)劃的解。,Min w = 2y1 +y2 S.t. y1 2y2 1 y1 + y2 1 y1 y2 0 y1,y2 0,應(yīng)用如上關(guān)系求解線性規(guī)劃問題,試用對偶理論證明上述規(guī)劃問題無最優(yōu)解。,由第一約束條件可知對偶問題無可行解，則原問題的解無界或無可行解， 由于原問題存在可行解，所以解無界。,解 該問題存在可行解，如X=(0，0，0)；,其對偶問題為：,對偶問題無可行解,定理6（互補松弛定理）,在線性規(guī)劃問題的最優(yōu)解中，如

3、果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。,注：證明過程參見教材59頁性質(zhì)5證明,討論:,互補松弛定理也稱松緊定理，它描述了線性規(guī)劃達到最優(yōu)時，原問題（或?qū)ε紗栴}）的變量取值和對偶問題（或原問題）約束松緊之間的對應(yīng)關(guān)系。 當線性規(guī)劃問題達到最優(yōu)時，我們不僅同時得到了原問題和對偶問題的最優(yōu)解，而且也還得到了變量和約束之間的一種對應(yīng)關(guān)系?；パa松弛定理即揭示了這一點。,1.如果原問題的某一約束為緊約束（嚴格等式:松弛變量為零），該約束對應(yīng)的對偶變量應(yīng)大于或等于零；,2.如果原問題的某一約束為松約束（嚴格不等式:松弛變量大于

4、零），則對應(yīng)的對偶變量必為零；,3.如果原問題的某一變量大于零該變量對應(yīng)的對偶約束必為緊約束(嚴格等式)；,4.如果原問題的某一變量等于零，該變量對應(yīng)的對偶約束可能是緊約束(嚴格等式)，也可能是松約束(嚴格不等式)。,線性規(guī)劃達到最優(yōu)時的關(guān)系,22,1/5 3,17/55,7/5 2,3=3,解：寫出對偶問題為： Max Z = 4y1 + 3y S.t. y1 + 2y2 2 y1 y2 3 2y1 +3y2 5 y1 + y2 2 3y1 +y2 3 y1,y2 0,又例:應(yīng)用如上關(guān)系求解線性規(guī)劃問題,已知對偶問題的最優(yōu)解為 y1 = 4/5, y2 = 3/5, 試應(yīng)用對偶理論求解原問題

5、。,x2 = 0,x3 = 0,x4 = 0,等號,又因y1,y2 0，故原問題的兩個約束必為緊約束，即,解得：x1 = x5 = 1。,maxZ=5=minS=5,得原問題的最優(yōu)解X*=(1,0,0,0,1) minS=5,Max.Z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）,附 練習(xí)答案：y1=4/5, y2=3/5, y3=1, y4=0,已知原問題的最優(yōu)解為:X*=(2,2,4,0)T，試根據(jù)互補松弛定理解出其對偶問題的最優(yōu)解。,線性規(guī)劃問題的對偶問題為： Min.

6、Z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）,練習(xí)：已知線性規(guī)劃問題為：,為嚴格不等式，由互補松弛定知，必有y4 = 0；,Max.Z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）, 8=8, 6=6, 6=6, 89,解之，有： y1=4/5, y2=3/5, y3=1，y4 = 0,答案：因為原問題的最優(yōu)解為:X*=(2,2,4,0)T ：,又因x

7、1, x2 , x30，故對偶問題的前三個約束必為緊約束,線性規(guī)劃問題的對偶問題為： Min.Z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）,等號,（1）寫出對偶問題； （2）已知原問題的最優(yōu)解為X*=（2，0，1，1）T，求對偶問題的最優(yōu)解。,已知線性規(guī)劃問題,定理7,結(jié)論：用單純形法求解線性規(guī)劃時，迭代的每一步在得到原問題一個基本可行解的同時，其：,線性規(guī)劃原問題及其對偶問題之間存在一對互補的基解，其中原問題的松馳變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題

8、的變量；這些互相對應(yīng)的變量如果在一個問題的解中是基變量，則在另一問題的解中是非基變量；將這兩個解代入各自的目標數(shù)中有 z=w。,注：證明過程參見教材60頁性質(zhì)6證明,檢驗數(shù)行的-(cj-zj)值是其對偶問題的一個基本解yi ；,用單純形法同時求解原問題和對偶問題,原問題是：,maxZ=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,原問題的標準型是：,maxZ=2x1 +x2+0 x3+0 x4 +0 x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi 0,maxZ=2x1 +x2+0 x3+

9、0 x4 +0 x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi 0,原問題變量,原問題松馳變量,對偶問題剩余變量 y4、y5,對偶問題變量 y1、y2 、y3,得原問題可行解:X=(0,0,15,24,5)T,對偶問題解:Y*=(0,0,0,-2,-1)T,檢驗數(shù)行的 (cj-zj)值是其對偶問題的一個基本解yi ；,得原問題可行解:X=(4,0,15,0,1)T，此時Z=8,同時得對偶問題基礎(chǔ)解:Y*=(0,1/3,0, 0,-1/3)T，W=8,檢驗數(shù)行的-(cj-zj)值是其對偶問題的一個基本解yi ；,變換單純形表,此時得原問題

10、最優(yōu)解:X*=(7/2,3/2,15/2,0,0)T，Z*=17/2,原問題變量,原問題松馳變量,對偶問題剩余變量 y4、y5,對偶問題變量 y1、y2 、y3,則對偶問題最優(yōu)解:Y*=(0,1/4,1/2,0,0)T，S*=17/2,檢驗數(shù)行的-(cj-zj)值是其對偶問題的一個基本解yi ；,又例：用單純形法同時求解原問題和對偶問題,maxZ= 100 x1 + 80 x2 2 x1+4 x2 80 3 x1+ x2 60 x1, x2 0,將線性規(guī)劃問題標準化,maxZ= 100 x1 + 80 x2 + 0 x3 + 0 x4 2 x1+4 x2 + x3 = 80 3 x1+ x2

11、+ x4 =60 x1, x2 x3 x4 0,此時得原問題的最優(yōu)解：X0=(16,12,0,0)T , maxZ=2560,初等變換,2 x1+ 4 x2 + x3 = 80 3 x1+ x2 + x4 =60 -Z+100 x1 + 80 x2 + 0 x3 + 0 x4=0,-Z x1 x2 x3 x4 b,同時得對偶問題的最優(yōu)解：y1=14,y2 =24,y3 =0,y4 =0,即Y0=(14,24,0,0)T , minS=2560,2.3 對偶單純形方法,原問題是：,原問題的標準型是：,maxw= -15y1-24y2-5y3 +0y4 +0y5 6y2+y3 - y4 = 2 5

12、y1 +2y2 +y3 - y5 =1 y1 , y2 , y3 , y4 , y5 0,利用單純形法：,maxw= -15y1-24y2-5y3 +0y4 +0y5-My6-My7 6y2+y3 - y4 +y6 = 2 5y1 +2y2 +y3 - y5 +y7 =1 y1 , y2 , y3 , y4 , y5 , y6 , y7 0,一、 用對偶單純形方法解線性規(guī)劃,對偶單純形方法是使用對偶原理求解原問題解的一種方法，而不是求解對偶問題解的單純形方法。與對偶單純形方法相對應(yīng)，原已有的單純形方法稱原始單純形方法。,用對偶單純形方法解下述線性規(guī)劃問題,原問題是：,原問題的標準型是：,max

13、w= -15y1-24y2-5y3 +0y4 +0y5 6y2+y3 - y4 = 2 5y1 +2y2 +y3 - y5 =1 y1 , y2 , y3 , y4 , y5 0,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,對偶單純形方法,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5

14、0,最優(yōu)解:Y*=(0,1/4,1/2,0,0)T，maxw*=-17/2,MinZ=17/2,應(yīng)用對偶單純形方法之矩陣法,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,最優(yōu)解:Y*=(0,1/4,1/2,0,0)T， max w*=-17/2 Min Z=17/2,兩種方法的主要區(qū)別在于：,而對偶單純形方法在整個迭代過程中，則是始終保持對偶問題的可行性即 亦即, ，也就是全部檢驗數(shù)0，最后達到全部右邊項所有負分量逐步變?yōu)槿坑疫呿?,即

15、滿足原問題的可行性時為止。,所以,對偶單純形方法實質(zhì)就是在保證對偶問題可行的條件下向原問題可行的方向迭代。,原始單純形方法在整個迭代過程中，始終是保持原問題的可行性，最后達到檢驗數(shù) 即 即maxZ取得最優(yōu)值時為止。,相當于：直到對偶問題的解可行為止,相當于：即直到原問題的解可行為止,用對偶單純形方法解下述線性規(guī)劃問題,原問題是：,原問題的標準型是：,maxZ= -2x1-3x2-4x3 +0 x4 +0 x5 x1+ 2x2+x3 - x4 = 3 2x1 - x2 +3x3 - x5 =4 x1 , x2 , x3 , x4 , x5 0,maxw= -2x1-3x2-4x3 +0 x4 +

16、0 x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,應(yīng)用對偶單純形方法之矩陣法,最優(yōu)解:Y*=(11/5,2/5,0,0,0)T，Maxw =-28/5,maxw= -2x1-3x2-4x3 +0 x4 +0 x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,MinZ* = 28/5,小結(jié)：對偶單純形方法的解題過程一般分為四步,（1）寫出與已有的初始基B對應(yīng)的初始單純形表。根據(jù)模型的

17、標準型，若右邊項的數(shù)字都為非負，且檢驗數(shù)都為非正，則已得到最優(yōu)解，計算結(jié)束；否則，若右邊項中至少有一個負分量，且檢驗數(shù)也仍然非正，則進行如下計算。,（2）確定出基變量。若有： 則以對應(yīng)的變量 xr為出基變量。,（3）確定入基變量。在單純形表中觀察xr所在行的各系數(shù)arj，若所有的arj0，則無可行解，停止計算；否則若存在：,， 則以xk為入基變量。,（4） 以ark為主元按原始單純形方法的迭代方法進行迭代，得到新的單純形表。,對偶單純形方法的顯著優(yōu)點：,（1）初始解可以是不可行解，當檢驗數(shù)都非正時，即可以進行基的變換，這時不需要引進人工變量 ，因此就簡化了計算。,（2）對于變量個數(shù)多于約束方程個數(shù)的線性規(guī)劃問題，采用對偶單純形法計算量較少。因此對于變量較少、約束較多的線性規(guī)劃問題, 可以先將它轉(zhuǎn)化成對偶問題，然后用對偶單純形方法求解。,2.4 影子價格,從對偶問題的基本性質(zhì)可以看出，在單純形法的每步迭代中有目標函數(shù),其中bi原來代表第i種資源的擁有量；現(xiàn)在代表第i種資源的估價。此時的估價不是市場價格，而是根據(jù)資源在生產(chǎn)中的貢獻而作的估價。此時的定價區(qū)別于市場價格稱為影子價格。,說明,1、市場價格主要隨市場供求變化；而它的影子價格有賴于資源的利用情況。生產(chǎn)任務(wù)、結(jié)構(gòu)的改變會影響影子價格。,2、影子價格是一種邊際價