1、第二章LP的對偶理論與靈敏度分析,線性規(guī)劃的對偶問題,問公司應每天制造兩種家電各多少件，使獲取的利潤最大。,例1,問題 美佳公司愿意以多大的代價出讓自己所擁有的生產資源？,設y1,y2和y3分別表示出讓資源A，B和調試工序的單價，則美佳公司同意出讓的條件將是 同意出讓生產產品I的資源 同意出讓生產產品II的資源 購買者希望用最少的代價獲得這些資源，因此,這樣得到一個新的線性規(guī)劃問題,稱這一問題是原來的LP問題的對偶線性規(guī)劃問題或對偶問題，原來的LP問題也稱為原問題。,LP問題的對稱形式,變量：所有變量均具有非負約束 約束條件： 最大化問題 所有約束條件都是“”型的 最小化問題 所有約束條件都是

2、“”型的,對稱形式下的對偶關系,對稱形式的對應關系,對偶問題的對偶是原問題，即對偶關系是相互對稱的關系,非對稱形式下的對偶關系,單純形法的矩陣表示,添加松弛變量XS,將XB的系數矩陣化為單位矩陣,初始單純形表,迭代后的單純形表,在初始單純形表中單位矩陣經過迭代后變?yōu)榛仃嘊的逆 在初始單純形表給出的解中基變量Xs=b,而在迭代后的表給出的解中基變量 XB=B-1b 系數矩陣的變化: A, IB-1A, I 在初始單純形表中變量xj的系數為Pj經過迭代后變?yōu)镻j,并且Pj=B-1 Pj 若迭代后的單純形表為最終表則該表也同時給出對偶問題的最優(yōu)解,原問題最終單純形表,對偶問題最終單純形表,例1,最

3、大化問題檢驗數的相反數給出了對偶問題的解,原本在對偶關系中，原問題的變量對應著對偶問題的約束條件，原問題的約束條件對應著對偶變量。但在分別添加了松弛變量和剩余變量后，也可以建立原問題變量與對偶問題變量之間的對應關系,注 上表中我們將松弛變量與剩余變量統(tǒng)稱為松弛變量,對偶問題的基本性質,弱對偶性 原問題可行解的目標函數不超過對偶問題可行解的目標函數,弱對偶性的推論,（1）原問題任一可行解的目標函數值是其對偶問題目標函數值的下界；反之對偶問題任一可行解的目標函數值是原問題目標函數值的上界。 （2）如原問題有可行解且目標函數無界（即原問題為無界解），則對偶問題無可行解；反之對偶問題有可行解且目標函數

4、無界，則原問題無可行解。注意該推論的逆命題不成立。 （3）若原問題有可行解而對偶問題無可行解，則原問題目標函數無界；反之對偶問題有可行解而原問題無可行解，則原問題目標函數無界。,最優(yōu)性 若原問題一個可行解目標函數等于對偶問題的某個可行解的目標函數,則這兩個可行解分別是原問題和對偶問題的最優(yōu)解 強對偶性 若原問題和對偶問題都有可行解,則它們都有最優(yōu)解,且最優(yōu)解的目標函數值相等 互補松弛性 在線性規(guī)劃問題的最優(yōu)解中,如果對應某一約束條件的對偶變量值非零,則其對應的約束條件取等式;反之若一個約束條件為嚴格的不等式,則其對應的對偶變量為零,互補松弛性的另一種表述,在線性規(guī)劃問題的最優(yōu)解中,如果對應某一

5、約束條件的對偶變量值非零,則該約束條件中松弛變量等于零;反之若一個約束條件中松弛變量非零,則其對應的對偶變量為零。,例（p76.7）,原問題,對偶問題,將原問題最優(yōu)解X*=(2,2,4,0)代入原問題約束條件中得,第一個約束條件：2+6=8，為等式,第二個約束條件：4+2=6，為等式,第三個約束條件：2+4=6，為等式,第四個約束條件：2+2+49，為不等式，故y4 = 0,而由x1=20, 得,而由x2=20, 得,而由x3=40, 得,于是得到方程組,得對偶問題最優(yōu)解為,注：原問題與對偶問題最優(yōu)目標函數值都是 z*=4+8+4=16,第三節(jié) 影子價格,式中bi是線性規(guī)劃原問題約束條件的右端

6、項，它代表第i種資源的擁有量；對偶變量yi的意義代表在資源最優(yōu)利用的條件下對第i種資源的估價。這種估價不是資源的市場價格，而是根據資源在生產中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格。,設 和 分別是原問題和對偶問題的最優(yōu)解，則由對偶性質，有,資源的影子價格隨企業(yè)的生產任務、產品結構的改變而改變 影子價格是資源的邊際價格 資源的影子價格也可視為一種機會成本 在生產過程中若某種資源未得到充分利用則其影子價格為零；只有在資源得到充分利用時，其影子價格才可能非零 利用影子價格可以說明：單純形法中的檢驗數可以看成生產某種產品的產值與隱含成本的差 可以利用影子價格確定企業(yè)內部的核算價格，以便控制有

7、限資源的使用和考核下屬企業(yè)經營的好壞。,例1,Max z=2x1+x2 s.t. 5x215 6x1+2x2 24 x1+x2 5 x1,x20,x2=3,6x1+2x2 =24,x1+x2 =5,最優(yōu)解,可行域,最優(yōu)目標函數值的變化：8.5變到8.75，增加1/4,資源的變化：設備B的可用時間從增加一小時,參考文獻： 李慧：資源影子價格分析與經營管理決策，系統(tǒng)工程理論與實踐，2003年4月號，22-26,第四節(jié) 對偶單純形法,按對偶問題與原問題之間的關系，對最大化問題，在用單純形法求解原問題時，最終表不但給出了原問題的最優(yōu)解，而且其檢驗數的相反數就是對偶問題的最優(yōu)解。,（對偶問題可行解）,保

8、持對偶問題有基可行解,而原問題只是基本解,通過迭代,使后者的負分量個數減少，一旦成為基可行解,則原問題與對偶問題同時實現(xiàn)最優(yōu)解.,對偶單純形法計算步驟,適應于求解這樣的LP問題：標準化后不含初始基變量，但將某些約束條件兩端乘以“-1”后，即可找出初始基變量。 要求：初始單純形表中的檢驗數滿足最優(yōu)性條件,對滿足上述條件的LP問題，對偶單純形法的步驟是：,旋轉運算。然后回到第2步。,作出初始單純形表（注意要求）,檢查b列的數據是否非負，若是，表中已經給出最優(yōu)解；否則轉下一步,確定換出變量：取b列最小的數對應的變量為換出變量,確定換入變量：用檢驗數去除以換出變量行的那些對應的負系數，在除得的商中選取

9、其中最小者對應的變量為換入變量,例 用對偶單純形法求解如下的LP問題,化成標準形式,將各約束條件兩端同乘“-1”得,用對偶單純形法求解得,最優(yōu)解：x1=0, x2=1/4, x3=1/2, x4=0, x5=0,最優(yōu)目標函數值：w*=-8.5（z*=8.5）,注：通常很少直接使用對偶單純形法求解線性規(guī)劃問題。,靈敏度分析,將討論LP問題中的參數 中有一個或幾個發(fā)生改變時問題的最優(yōu)解會有什么變化，或者這些參數在一個多大的范圍內變化時，問題的最優(yōu)解不變,研究的思路,將個別參數的變化直接在計算得到的最終單純形表中反映出來，這樣就不需要從頭計算，而直接檢查在參數改變后最終表有什么改變，若仍滿足最終表的

10、條件，則表中仍給出最優(yōu)解，否則從這個表開始進行迭代求改變以后的最優(yōu)解。,靈敏度分析的步驟,將參數的改變計算反映到最終表上來。具體計算公式可以使用 檢查原問題是否仍為可行解 檢查對偶問題是否仍為可行解 對檢查情況按下表進行處理,價值系數變化的靈敏度分析,例：在第一章美佳公司的例1中 （1）若產品I的利潤降至1.5元/件，而產品II的利潤增至2元/件，美佳公司的最優(yōu)生產計劃有何改變； （2）若產品I的利潤不變，則產品II的利潤在什么范圍變化時，該公司的最優(yōu)生產計劃不發(fā)生變化,原最終單純形表,（1）改變后,新的最優(yōu)解為：,最優(yōu)目標函數值為：,（2）改變后,為使表中的解仍為最優(yōu)解必須,因此產品II的利

11、潤變化范圍為,資源常數變化的靈敏度分析,例：在第一章美佳公司的例1中 （1）若設備A與調試工序的每天能力不變，而設備B每天的能力增加到32小時，分析公司最優(yōu)計劃的變化； （2）若設備A和B每天可用能力不變，則調試工序能力在什么范圍變化時，問題的最優(yōu)基不變,（1）b由(15，24，5)T 變?yōu)?15，32，5)T 后，相應地最終表中b列的數據變?yōu)?代入原最終表,（2）設現(xiàn)在每天調試工序的時間為x，則最終表中b列的數變?yōu)?故要使最優(yōu)基不變必須,利用Excle求解LP問題，以P45.7(2)為例,變量，已經賦了初值,目標函數值,約束條件右端值,其他專業(yè)軟件：Lindo與Lingo，WinQSB,例如Lingo，啟動Lingo后，按圖中的方式輸入模型，然后點擊求解的圖標 。就可得到所需的最優(yōu)解。,24對偶問題為,由圖解法可得對偶問題最優(yōu)解為,將該最優(yōu)解代入對偶問題約束條件可知，第四個約束條件為嚴格不等式，因此在原問題最優(yōu)解中,而由于,因此將原問題最優(yōu)解代入原問題約束條件，它們成為等式。再由于原問題最優(yōu)目標函數值等于對偶問題最優(yōu)目標函數值。于是原問題最優(yōu)解滿足方程組,解方程組得原問