【正文】 y1 , y2 ? 0 min g=7y139。 7y1 +9y2 令 y1 = y139。 y1 ， 則 min g=7y1 +9y2 3y1+4y2 ?5 2y1 +y2 ? 6 y1自由 , y2 ? 0 山東理工大學(xué)管理學(xué)院 非對稱的對偶問題 原問題 對偶問題 ? ? ? ? ? ? 0 max X b AX CX f ? ? ? ? ? 無正負限制 Y C YA Yb g min 山東理工大學(xué)管理學(xué)院 混合形式的對偶問題 ???????????????????????無限制321321321321321,0,0322252.523m a xyyyyyyyyyyyytsyyyg? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 無限制 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 , 0 , 0 5 2 2 2 3 . 3 2 25 min x x x x x x x x x x x x t s x x x f 山東理工大學(xué)管理學(xué)院 例 4：寫出下列線性規(guī)劃的對偶規(guī)劃 min f= 4x1 +2x2 –3x3 x1+2x2 ? 6 2x1 +3x3 ? 9 x1 +5x2 –2x3 = 4 x2 , x3 ?0 max g= 6y1 +9y2 +4y3 y1+2y2 + y3 = 4 2y1 +5y3 ? 2 3y2 2y3 ? 3 y1 ? 0 , y2 ?0 , y3為 自由變量 解：原線性規(guī)劃的對偶規(guī)劃為： 山東理工大學(xué)管理學(xué)院 課堂練習(xí) 32145m a x xxxf ??? ???????????????????0,0458022903.21321321321xxxxxxxxxxxts 寫出下列線性規(guī)劃問題的對偶規(guī)劃 山東理工大學(xué)管理學(xué)院 原問題和對偶問題的關(guān)系 原問題（或?qū)ε紗栴}） 對偶問題（或原問題） 目標函數(shù)形式 m ax f 目標函數(shù)形式 m in g 約 束 條 件 m 個約束 約束 ? 約束 ? = 變 量 m 個變量 變量 ? 0 變量 ? 0 無正負限制 變 量 n 個變量 變量 ? 0 變量 ? 0 無正負限制 約 束 條 件 n 個約束 約束 ? 約束 ? = 約束方程右端項 目標函數(shù)中的系數(shù) 目標函數(shù)中的系數(shù) 約束方程右端項 山東理工大學(xué)管理學(xué)院 二、對偶問題的基本性質(zhì) gfYbCX ?? ，即 若 X和 Y分別是原問題和對偶問題的任一可行解，則必有 該性質(zhì)告訴我們，最大化問題的任一可行解的目標函數(shù)值都是其對偶最小化問題目標函數(shù)的下界；而最小化問題的任一可行解的目標函數(shù)值都是其對偶最大化問題目標函數(shù)的上界。 X* 和 Y* 分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問題和對偶問題的目標函數(shù)值相等，即 CX* = Y*b ，則 X* 和 Y*分別為原問題和對偶問題的最優(yōu)解。 若原問題（對偶問題）的目標函數(shù)無界，則其對偶問題 （原問題）必無可行解。 該性質(zhì)說明，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。 若原問題和對偶問題之一有最優(yōu)解，則另一個也有最優(yōu)解，且兩者的最優(yōu)目標函數(shù)值相等。 山東理工大學(xué)管理學(xué)院 XB = B1b， 則對偶問題的最優(yōu)解為 Y=CBB1. ，則他們必都有最優(yōu)解。 最優(yōu)解。 ??????????????0,45802903.21212121xxxxxxxxts21 45m a x xxf ??????????????0,4352.321321321yyyyyyyyytsm i n g y y y? ? ?90 80 451 2 3例 原問題 對偶問題 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 x5 B1b 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 0 0 初始單純形表 最優(yōu)單純形表 原問題 山東理工大學(xué)管理學(xué)院 y1 y2 y3 y4 y5 B1b y2 y3 2 1 0 1 1 5 0 1 1 2 1 3 g’ 25 0 0 35 10 215 對偶問題最優(yōu)單純形表： 綜上所述，一對對偶問題的解必然是下列三種情況之一： ，且最優(yōu)目標函數(shù)值相等。 。 ，則另一個問題無可行解。 山東理工大學(xué)管理學(xué)院 例 3 已知線性規(guī)劃問題 ??????????????0,132232.321321321xxxxxxxxxts21 3m a x xxf ??試用對偶理論證明上述問題無最優(yōu)解。 山東理工大學(xué)管理學(xué)院 三、對偶解的經(jīng)濟涵義 —— 影子價格 通過求解：原問題和對偶問題的最優(yōu)解分別為 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 , , 4 3 5 2 0 , 45 80 2 90 3 45 80 90 min 4 5 max 3 2 1 3 2 1 3 2 1 2 1 2 1 2 1 2 1 3 2 1 2 1 y y y y y y y y y x x x x x x x x y y y g x x f 215 min , ) 3 , 1 , 0 ( ) , , ( 215 max , ) 25 , 10 , 35 ( ) , , ( 3 2 1 3 2 1 ? ? ? ? ? ? g y y y y f x x x x T T 山東理工大學(xué)管理學(xué)院 對偶問題是資源定價問題，對偶問題的最優(yōu)解 y y ...、ym稱為 m種資源的 影子價格（ Shadow Price）。 影子價格 是指在最優(yōu)解的基礎(chǔ)上，當?shù)? i 個約束條件的右端項 bi 增加一個單位時，目標函數(shù)的變化量。 由對偶定理可知 ， 當達到最優(yōu)解時，原問題與對偶問題的目標函數(shù)值相等，即有 f *=CX*=Y*b=y1* b1+ y2* b2+…+ ym* bm 現(xiàn)考慮在最優(yōu)解處，右端項 bi的微小變動對目標函數(shù)值的影響，由上式，將 f *對 bi求偏導(dǎo)數(shù)： ),...,2,1(**miybf ii???? 該式表明了，若原問題的某一個約束條件的右端項 bi每增加一個單位，則由此引起的最優(yōu)目標函數(shù)值的增加量，就等于與該約束條件相對應(yīng)的對偶變量的最優(yōu)解的值。 山東理工大學(xué)管理學(xué)院 例 4 某工廠生產(chǎn)三種產(chǎn)品，三種產(chǎn)品對于原材料、勞動力、電力的單位消耗系數(shù)，資源限量和單位產(chǎn)品價格如下表所示： A B C 資源限量 原材料（ kg） 勞動力（人） 電力（度） 2 6 5 1 5 4 8 10 320 640 750 單位價格（元） 4 6 10 資源 產(chǎn)品 。 ，并解釋其經(jīng)濟意義。 山東理工大學(xué)管理學(xué)院 ??????????????????????0,0,0750105564086.1064m a x321321321321321xxxxxxxxxxxxtsxxxfxj x1 x2 x3 x4 x5 x6 B1b x2 x5 x3 0 1 0 2 0 2 0 0 6 1 1/2 0 1 1 0 40 160 55 f 1 0 0 2 0 790 山東理工大學(xué)管理學(xué)院 ① 影子價格可以告訴管理人員，增加哪一種資源對增加經(jīng)濟效益最有益。 ② 影子價格可以告訴管理人員，花多大的代價增加資源才是合算的。 ③ 影子價格在新產(chǎn)品開發(fā)決策中的應(yīng)用。 ④ 影子價格在資源購銷決策中的應(yīng)用。 山東理工大學(xué)管理學(xué)院 例 : 一個大學(xué)教授用部分時間從事于咨詢工作。通過這項工作，他的總收入將有所提高，該教授掌握了咨詢補償?shù)幕疽?guī)律： “ 一個專家的價值正比于廠商和專家之間的距離 ” 。也就是說，要求咨詢的單位愈遠，他得到的報酬愈多。遺憾的是，旅行時間也將增加。目前他有較多的咨詢機會，但可用時間有限，他希望詳細分析這種情況，他是否要雇助手？如果這樣，他應(yīng)付多少工資？ 山東理工大學(xué)管理學(xué)院 設(shè)： x1 = 每月為 A企業(yè)咨詢的小時數(shù) （ 利潤： 100元 /h） x2 = 每月為 B企業(yè)咨詢的小時數(shù) （ 利潤： 120元 /h） x3 = 每月為 C企業(yè)咨詢的小時數(shù) （ 利潤： 160元 /h） 進一步假定該教授每月有 40小時 用于咨詢工作，并且希望他的旅行時間每月在 24小時 以內(nèi)。每小時咨詢工作所要求的旅行時間對于企業(yè) A、 B、 C來說分別為 、 、 。教授估計三個企業(yè)每月要求最大的咨詢時間分別是 80、60、 20小時 。據(jù)此，我們可以很快建立該問題的線性規(guī)劃模型。 山東理工大學(xué)管理學(xué)院 1 2 3m a x 1 0 0 1 2 0 1 6 0f x x x? ? ??????????????????????0,20608040.321321321321xxxxxxxxxxxxts式中 f—從事咨詢工作每月可得的利潤總和 （ 元 /月 ） 。 對偶問題的模型為： 山東理工大學(xué)管理學(xué)院 思路： 單純形法：找基 B，滿足 右端常數(shù)非負 ， 但檢驗數(shù) 不全 ? 0。 迭代 保持右端常數(shù) ?0， 使 檢驗數(shù) ? 0。 對偶單純形法：找基 B，滿足 檢驗數(shù) ? 0， 但 右端常數(shù)不全 ?0。 迭代 保持 檢驗數(shù) ? 0， 使 右端常數(shù) ?0。 四、對偶單純形法 山東理工大學(xué)管理學(xué)院 例 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 山東理工大學(xué)管理學(xué)院 xj x1 x2 x3 x4 x5 B1b