對偶理論第三章線性規(guī)劃

1、對偶理論第三章線性規(guī)劃 對偶理論 一、原問題與對偶問題一、原問題與對偶問題 例例1、某廠在計劃期內(nèi)要安排生產(chǎn)、某廠在計劃期內(nèi)要安排生產(chǎn)A、B兩種產(chǎn)品，這兩種產(chǎn)品分別兩種產(chǎn)品，這兩種產(chǎn)品分別 需要在甲、乙丙三種不同的設(shè)備上加工，有關(guān)數(shù)據(jù)如表需要在甲、乙丙三種不同的設(shè)備上加工，有關(guān)數(shù)據(jù)如表3-14所示。所示。 問應(yīng)如何安排生產(chǎn)計劃才能使利潤最大？問應(yīng)如何安排生產(chǎn)計劃才能使利潤最大？ 45利潤（元利潤（元/件）件） 4511丙丙 8012乙乙 9031甲甲 有效臺時有效臺時BA 設(shè)備設(shè)備 產(chǎn)品產(chǎn)品 對偶理論第三章線性規(guī)劃 該問題的數(shù)學(xué)模型 如果設(shè)如果設(shè)A、B兩種產(chǎn)品生產(chǎn)的件數(shù)分別為兩種產(chǎn)品生產(chǎn)的件數(shù)

2、分別為 ,則這個問題則這個問題 可以歸結(jié)為求解下列線性規(guī)劃問題：可以歸結(jié)為求解下列線性規(guī)劃問題： 0, 45 802 903 . 21 21 21 21 xx xx xx xx ts 21 45maxxxf xx 12 , 對偶理論第三章線性規(guī)劃 其對偶問題的數(shù)學(xué)模型 設(shè)設(shè) 分別表示設(shè)備甲、乙、丙每臺時的價格（或分別表示設(shè)備甲、乙、丙每臺時的價格（或 租金）租金）,則則 yyy 123 , 0, 43 52 . 321 321 321 yyy yyy yyy ts mingyyy908045 123 對偶理論第三章線性規(guī)劃 例例2、每頭牲畜每日對各種維生素的需求量及飼料商提供的營養(yǎng)每頭牲畜每日

3、對各種維生素的需求量及飼料商提供的營養(yǎng) 飼料飼料M和和N中各種維生素含量及定價如下表所示，牧場主在保中各種維生素含量及定價如下表所示，牧場主在保 證牲畜維生素需求條件下，每日為每頭牲畜購證牲畜維生素需求條件下，每日為每頭牲畜購M、N各多少可各多少可 使總費用最少？使總費用最少？ MN 日需要量日需要量 A B C D 0.1 0 0.1 0.2 0 0.1 0.2 0.1 0.4 0.6 2.0 1.7 定價定價 104 維生素維生素 營養(yǎng)飼料營養(yǎng)飼料 對偶理論第三章線性規(guī)劃 設(shè)每日每頭牲畜需營養(yǎng)飼料設(shè)每日每頭牲畜需營養(yǎng)飼料M、N分別為分別為 ，則該，則該 問題的線性規(guī)劃模型為：問題的線性規(guī)劃

4、模型為： xx 12 , 0, 7 . 11 . 02 . 0 22 . 01 . 0 6 . 00.1 0.4 1 . 0 . . 410min 21 21 21 2 1 21 xx xx xx x x ts xxf 對偶理論第三章線性規(guī)劃 已知條件同上例，某藥品商想提供畜用維生素已知條件同上例，某藥品商想提供畜用維生素A、B、C、D 四種營養(yǎng)藥品，在滿足牲畜營養(yǎng)要求且可與飼料商競爭條件四種營養(yǎng)藥品，在滿足牲畜營養(yǎng)要求且可與飼料商競爭條件 下，四種藥品如何定價可使總收入最大下，四種藥品如何定價可使總收入最大？ 0, 41 . 02 . 01 . 0 102 . 01 . 0 1 . 0 .

5、. 7 . 126 . 04 . 0max 4321 432 431 4321 yyyy yyy yyy t s yyyyg 對偶理論第三章線性規(guī)劃 0, 45 802 903 . 21 21 21 21 xx xx xx xx ts 21 45maxxxf 0, 43 52 . 321 321 321 yyy yyy yyy ts mingyyy908045 123 對偶理論第三章線性規(guī)劃 0, 7 . 11 . 02 . 0 22 . 01 . 0 6 . 00.1 0.4 1 . 0 . . 410min 21 21 21 2 1 21 xx xx xx x x ts xxf 0, 41

6、 . 02 . 01 . 0 102 . 01 . 0 1 . 0 . . 7 . 126 . 04 . 0max 4321 432 431 4321 yyyy yyy yyy t s yyyyg 對偶理論第三章線性規(guī)劃 對稱的對偶問題 原問題原問題對偶問題對偶問題 njx mibxa xcf j i n j jij n j jj , 2, 1, 0 , 2, 1, max 1 1 miy njcay ybg i j m i iji i m i i , 2 , 1, 0 , 2 , 1, min 1 1 對偶理論第三章線性規(guī)劃 對稱的對偶問題 原問題原問題對偶問題對偶問題 0 max X bA

7、X CXf 0 min Y CYA Ybg 對偶理論第三章線性規(guī)劃 非對稱的對偶問題 原問題原問題 對偶問題對偶問題 0 max X bAX CXf 無正負限制Y CYA Ybgmin 對偶理論第三章線性規(guī)劃 混合形式的對偶問題混合形式的對偶問題 無限制 321 321 321 321 321 , 0, 0 52 22 3 . 3225min xxx xxx xxx xxx ts xxxf 無限制 321 321 321 321 321 , 0, 0 3 22 252 . 523max yyy yyy yyy yyy ts yyyg 對偶理論第三章線性規(guī)劃 原問題和對偶問題的關(guān)系原問題和對偶問

8、題的關(guān)系 原原問問題題（或或?qū)ε寂紗枂栴}題） 對對偶偶問問題題（或或原原問問題題） 目目標標函函數(shù)數(shù)形形式式 max f 目目標標函函數(shù)數(shù)形形式式 min g 約約 束束 條條 件件 m 個個約約束束 約約束束 約約束束 = 變變 量量 m 個個變變量量 變變量量 0 0 變變量量 0 0 無無正正負負限限制制 變變 量量 n 個個變變量量 變變量量 0 0 變變量量 0 0 無無正正負負限限制制 約約 束束 條條 件件 n 個個約約束束 約約束束 約約束束 = 約約束束方方程程右右端端項項 目目標標函函數(shù)數(shù)中中的的系系數(shù)數(shù) 目目標標函函數(shù)數(shù)中中的的系系數(shù)數(shù) 約約束束方方程程右右端端項項 對

9、偶理論第三章線性規(guī)劃 二、對偶問題的基本性質(zhì)二、對偶問題的基本性質(zhì) XY * 和 bYCX * XY * , gfYbCX，即 1.1.弱對偶性弱對偶性 若若X X和和Y Y分別是原問題和對偶問題的任一可行解，則必有分別是原問題和對偶問題的任一可行解，則必有 該性質(zhì)告訴我們，最大化問題的任一可行解的目標函數(shù)值都是其對偶最小化該性質(zhì)告訴我們，最大化問題的任一可行解的目標函數(shù)值都是其對偶最小化 問題目標函數(shù)的下界；而最小化問題的任一可行解的目標函數(shù)值都是其對偶問題目標函數(shù)的下界；而最小化問題的任一可行解的目標函數(shù)值都是其對偶 最大化問題目標函數(shù)的上界。最大化問題目標函數(shù)的上界。 2 2. .若若

10、分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問 題和對偶問題的目標函數(shù)值相等，即題和對偶問題的目標函數(shù)值相等，即 ，則，則 分別為原問分別為原問 題和對偶問題的最優(yōu)解。題和對偶問題的最優(yōu)解。 3.3.無界性無界性 若原問題（對偶問題）的目標函數(shù)無界，則其對偶問題若原問題（對偶問題）的目標函數(shù)無界，則其對偶問題 （原問題）必?zé)o可行解。（原問題）必?zé)o可行解。 該性質(zhì)說明，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。該性質(zhì)說明，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。 4.4.對偶定理對偶定理 若原問題和對偶問題之一有最優(yōu)解，則另

11、一個也有最優(yōu)若原問題和對偶問題之一有最優(yōu)解，則另一個也有最優(yōu) 解，且兩者的最優(yōu)目標函數(shù)值相等。解，且兩者的最優(yōu)目標函數(shù)值相等。 對偶理論第三章線性規(guī)劃 11 , BCYbBX BB 則對偶問題的最優(yōu)解為6.若原問題的最優(yōu)解為若原問題的最優(yōu)解為 。 5.若原問題和對偶問題同時有可行解，則他們必都有最優(yōu)解。若原問題和對偶問題同時有可行解，則他們必都有最優(yōu)解。 7. .根據(jù)原問題最優(yōu)單純形表中的檢驗數(shù)可以讀出對偶問題的最優(yōu)解。根據(jù)原問題最優(yōu)單純形表中的檢驗數(shù)可以讀出對偶問題的最優(yōu)解。 0, 45 802 903 . 21 21 21 21 xx xx xx xx ts 21 45maxxxf 0,

12、43 52 . 321 321 321 yyy yyy yyy ts min gyyy908045 123 例例1、 原問題原問題對偶問題對偶問題 對偶理論第三章線性規(guī)劃 xj x1 x2 x3 x4 x5 B-1b x3 x1 x2 0 0 1 2 -5 1 0 0 1 -1 0 1 0 -1 2 25 35 10 -f 0 0 0 -1 -3-215 xj x1 x2 x3 x4 x5 b x3 x4 x5 1 2 1 0 0 2 1 0 1 0 1 1 0 0 1 90 80 45 -f 5 4 0 0 00 初始單純形表初始單純形表 最優(yōu)單純形表最優(yōu)單純形表 原問題原問題 對偶理論第三

13、章線性規(guī)劃 y1 y2 y3 y4 y5B-1b y2 y3 -2 1 0 -1 1 5 0 1 1 -2 1 3 -g -25 0 0 -35 -10215 對偶問題最優(yōu)單純形表：對偶問題最優(yōu)單純形表： 綜上所述，一對對偶問題的解必然是下列三種情況之一：綜上所述，一對對偶問題的解必然是下列三種情況之一： 1.原問題和對偶問題都有最優(yōu)解，且最優(yōu)目標函數(shù)值相等。原問題和對偶問題都有最優(yōu)解，且最優(yōu)目標函數(shù)值相等。 3.原問題和對偶問題都無可行解。原問題和對偶問題都無可行解。 2.一個問題具有無界解，則另一個問題無可行解。一個問題具有無界解，則另一個問題無可行解。 對偶理論第三章線性規(guī)劃 例例3 已

14、知線性規(guī)劃問題已知線性規(guī)劃問題 0, 132 232 . 321 321 321 xxx xxx xxx ts 21 3maxxxf 試用對偶理論證明上述問題無最優(yōu)解。試用對偶理論證明上述問題無最優(yōu)解。 對偶理論第三章線性規(guī)劃 三、對偶解的經(jīng)濟涵義三、對偶解的經(jīng)濟涵義影子價格影子價格 0, 43 52 0, 45 802 903 458090min45max 321 321 321 21 21 21 21 32121 yyy yyy yyy xx xx xx xx yyygxxf 通過求解：原問題和對偶問題的最優(yōu)解分別為通過求解：原問題和對偶問題的最優(yōu)解分別為 215min, ) 3, 1 ,

15、0(),( 215max,)25,10,35(),( 321 321 gyyyy fxxxx TT 對偶理論第三章線性規(guī)劃 1.影子價格的定義影子價格的定義 對偶問題是資源定價問題，對偶問題的最優(yōu)解對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、.、 ym稱為稱為m種資源的影子價格（種資源的影子價格（Shadow Price）。）。 影子價格是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)谟白觾r格是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)?i 個約束條件的右個約束條件的右 端項端項 bi 增加一個單位時，目標函數(shù)的變化量。增加一個單位時，目標函數(shù)的變化量。 由對偶定理可知由對偶定理可知，當(dāng)達到最優(yōu)解時，原問題與對偶問題的目當(dāng)達

16、到最優(yōu)解時，原問題與對偶問題的目 標函數(shù)值相等，即有標函數(shù)值相等，即有f *=CX*=Y*b=y1* b1+ y2* b2+ ym* bm 現(xiàn)考慮在最優(yōu)解處，右端項現(xiàn)考慮在最優(yōu)解處，右端項bi的微小變動對目標函數(shù)值的微小變動對目標函數(shù)值 的影響，由上式，將的影響，由上式，將f *對對bi求偏導(dǎo)數(shù)：求偏導(dǎo)數(shù)： ),.,2 , 1( * * miy b f i i 該式表明了，若原問題的某一個約束條件的右端項該式表明了，若原問題的某一個約束條件的右端項bi每增加每增加 一個單位，則由此引起的最優(yōu)目標函數(shù)值的增加量，就等于一個單位，則由此引起的最優(yōu)目標函數(shù)值的增加量，就等于 與該約束條件相對應(yīng)的對偶

17、變量的最優(yōu)解的值。與該約束條件相對應(yīng)的對偶變量的最優(yōu)解的值。 對偶理論第三章線性規(guī)劃 2.影子價格的求法影子價格的求法 例例4 某工廠生產(chǎn)三種產(chǎn)品，三種產(chǎn)品對于原材料、勞動力、某工廠生產(chǎn)三種產(chǎn)品，三種產(chǎn)品對于原材料、勞動力、 電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價格如下表電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價格如下表 所示：所示： ABC 資源限量資源限量 原材料（原材料（kg） 勞動力（人）勞動力（人） 電力（度）電力（度） 2 6 5 2.5 1 5 4 8 10 320 640 750 單位價格（元）單位價格（元） 4610 資源資源 產(chǎn)品產(chǎn)品 1.求最佳生產(chǎn)方案使總產(chǎn)值最大。求最佳

18、生產(chǎn)方案使總產(chǎn)值最大。 2.求各資源的影子價格，并解釋其經(jīng)濟意義。求各資源的影子價格，并解釋其經(jīng)濟意義。 對偶理論第三章線性規(guī)劃 0,0,0 7501055 64086 32045.22 . 1064max 321 321 321 321 321 xxx xxx xxx xxx ts xxxf xj x1 x2 x3 x4 x5 x6 B-1b x2 x5 x3 0 1 0 2 0 -0.8 2 0 0 6 1 -3.2 1/2 0 1 -1 0 0.5 40 160 55 -f -1 0 0 -2 0 -0.2-790 對偶理論第三章線性規(guī)劃 3.影子價格的作用影子價格的作用 影子價格可以告

19、訴管理人員，增加哪一種資源對增加經(jīng)濟效益最有益。影子價格可以告訴管理人員，增加哪一種資源對增加經(jīng)濟效益最有益。 影子價格可以告訴管理人員，花多大的代價增加資源才是合算的。影子價格可以告訴管理人員，花多大的代價增加資源才是合算的。 影子價格在新產(chǎn)品開發(fā)決策中的應(yīng)用。影子價格在新產(chǎn)品開發(fā)決策中的應(yīng)用。 影子價格在資源購銷決策中的應(yīng)用。影子價格在資源購銷決策中的應(yīng)用。 利用影子價格分析工藝改變后對資源節(jié)約的收益。利用影子價格分析工藝改變后對資源節(jié)約的收益。 如在上例中，當(dāng)工藝改進后，使原材料節(jié)約如在上例中，當(dāng)工藝改進后，使原材料節(jié)約10%，則帶來的經(jīng)濟效益，則帶來的經(jīng)濟效益 為：為：2 320 10

20、%=64（元）（元） 對偶理論第三章線性規(guī)劃 在利潤最大化的生產(chǎn)計劃中在利潤最大化的生產(chǎn)計劃中 （1）邊際利潤大于）邊際利潤大于0的資源沒有剩余的資源沒有剩余 （2）有剩余的資源邊際利潤等于）有剩余的資源邊際利潤等于0 種資源的邊際利潤第 種資源的增量第 最大利潤的增量 i ib f y i i * * 關(guān)于影子價格的幾點說明：關(guān)于影子價格的幾點說明： 對偶理論第三章線性規(guī)劃 影子價格越大，說明這種資源越是相對緊缺影子價格越大，說明這種資源越是相對緊缺 影子價格越小，說明這種資源相對不緊缺影子價格越小，說明這種資源相對不緊缺 如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影如果最優(yōu)生產(chǎn)計劃下某種

21、資源有剩余，這種資源的影 子價格一定等于子價格一定等于0 影子價格為影子價格為0，資源并不一定有剩余，資源并不一定有剩余 影子價格是資源最優(yōu)配置下資源的理想價格，資源的影子價格是資源最優(yōu)配置下資源的理想價格，資源的 影子價格與資源的緊缺度有關(guān)影子價格與資源的緊缺度有關(guān) 對偶理論第三章線性規(guī)劃 思路：思路：( (max型型) ) 單純形法：找基單純形法：找基B B，滿足，滿足B-1b 0，但檢驗數(shù)但檢驗數(shù) C - CBB-1 A不全不全 0。 迭代迭代保持保持B-1b 0，使使C -CBB-1 A 0。 對偶單純形法：找基對偶單純形法：找基B B，滿足，滿足C - CBB-1 A 0，但但 B-

22、1b不全不全 0。 迭代迭代 保持保持C -CBB-1 A 0，使使B-1b 0。 四、對偶單純形法四、對偶單純形法 對偶理論第三章線性規(guī)劃 例例1 1： max f =2x1 +x2 x1+ x2 + x3 = = 5 2x2 + x3 5 4x2 +6x3 9 x1 , x2 , x3 0 max f =2x1 +x2 x1+ x2 + x3 = = 5 2x2 + x3 +x4 = 5 -4x2 6x3 +x5 =-9 x1 x5 0 對偶理論第三章線性規(guī)劃 xj x1 x2 x3 x4 x5 B-1b x1 x4 x5 1 1 1 0 0 0 2 1 1 0 0 -4 -6 0 1 5 5 -9 -f 0 -1 -2 0 0-10 2 1 0 0 0 0 2 0 0 x1 x4 x2 1 0 -1/2 0 1/4 0 0 -2 1 -1/2 0 1 3/2 0 -1/4 11/4 1/2 9/4 -f 0 0 -1/2 0 -1/4-31/4 2 0 1 對偶理論第三章線性規(guī)劃 例例2. 0, 12 423 32 3min 21 21 21 21 21 xx xx xx xx xxf 0, 12 423 32 3max 54321 521 421 321 21 xxxxx xxx xxx xxx xxf 0, 12 423 3