第三章(肖健華)

1、1 第三章 線性規(guī)劃的對偶理論 2 內(nèi)涵一致但從相反角度提出的一對問 題互為對偶問題。 原問題P與對偶問題D的對應(yīng)關(guān)系：相 伴而生。 3 本章主要內(nèi)容 n給定LP原問題P后，如何寫出對偶 問題D； n原問題與對偶問題的關(guān)系； n給出解LP問題的對偶單純形算法； n靈敏度分析 4 3.1 對偶問題的提出 例1：某家具廠木器車間生產(chǎn)木門與木 窗兩種產(chǎn)品，加工木門收入為56元/扇，加 工木窗收入為30元/扇，生產(chǎn)一扇木門需要 木工4小時，油漆工2小時；生產(chǎn)一扇木窗 需要木工3小時，油漆工1小時，該車間每 日可用木工總工時為120小時，油漆工總 工時為50小時，問該車間如何安排生產(chǎn)才 能使每日收入最大

2、？ 5 例2：某工廠在某一計劃期內(nèi)準(zhǔn)備生產(chǎn) 甲、乙兩種產(chǎn)品，生產(chǎn)需要消耗A、B、C 三種資源，各種資源擁有量分別為8、16、 12。生產(chǎn)甲需A、B、C分別為1，4，0，生 產(chǎn)乙需A、B、C分別為2，0，4?，F(xiàn)已知甲、 乙的利潤分別為2，3.問：如何安排生產(chǎn)， 以使計劃期內(nèi)的生產(chǎn)獲利最大？ 6 原問題與對偶問題的對應(yīng) 原問題 對偶問題 ), 2 , 1(0 max 2211 22222121 11212111 2211 njx bxaxaxa bxaxaxa bxaxaxa xcxcxcz j mnmnmm nn nn nn ), 2 , 1(0 min 2211 22222112 112211

3、11 2211 mjy cyayaya cyayaya cyayaya ybybybw j nmmnnn mm mm mm 7 注意： 8 3.2 對偶關(guān)系及對偶性質(zhì) 一、原問題與其對偶問題的對應(yīng)關(guān)系 對稱形式的原問題：目標(biāo)函數(shù)求極大 值、約束條件取小于等于號、決策變量非 負(fù)的線性規(guī)劃問題。 9 對稱形式的原問題與對偶問題具有對應(yīng)關(guān)系： 原問題目標(biāo)函數(shù)求極大值，對偶問題 目標(biāo)函數(shù)求極小值； 原問題約束條件的數(shù)目等于對偶問題 決策變量的數(shù)目； 原問題決策變量的數(shù)目等于對偶問題 約束條件的數(shù)目； 原問題的價值系數(shù)成為對偶問題的資 源系數(shù)； 10 對稱形式的原問題與對偶問題具有對應(yīng)關(guān)系： 原問題的資

4、源系數(shù)成為對偶問題的價 值系數(shù)； 原問題的技術(shù)系數(shù)矩陣與對偶問題的 技術(shù)系數(shù)矩陣互為轉(zhuǎn)置； 原問題的約束條件為小于等于號，對 偶問題的決策變量大于等于0； 原問題的決策變量大于等于0，對偶問 題的約束條件為大于等于號。 11 例1：設(shè)LP的數(shù)學(xué)模型如下，求其對稱 形式下的對偶問題的數(shù)學(xué)模型。 21 22maxxxz 0, 12 12 142 21 21 21 21 xx xx xx xx 12 例2：寫出如下線性規(guī)劃問題的對偶問題 321 32maxxxxz 0, 632 532 4 321 321 321 321 xxx xxx xxx xxx 13 本例表明：原問題約束條件不等號的方向 決

5、定對偶決策變量取值的正負(fù)。 原問題的約束條件取等號，那么與它對 應(yīng)的對偶變量取無約束； 原問題(max)的約束條件取小于等于號， 那么與它對應(yīng)的對偶變量取值非負(fù)； 原問題(max)的約束條件取大于等于號， 那么與它對應(yīng)的對偶變量取值非正。 14 例3 寫出以下線性規(guī)劃問題的對偶問題 321 32maxxxxz 無約束 321 321 321 321 , 0, 0 632 532 4 xxx xxx xxx xxx 15 本例表明：原問題的決策變量的取值決定其 對偶約束條件不等號的方向。 原問題決策變量取值無約束，其對應(yīng)的對偶 約束條件取等號； 原問題(max)決策變量取值非負(fù)，那么與之 對應(yīng)的

6、對偶約束條件取大于等于號； 原問題(max)決策變量取值非正，那么與之 對應(yīng)的對偶約束條件取小于等于號。 16 對偶關(guān)系表 17 例4：根據(jù)對偶關(guān)系表寫出下述線性規(guī)劃 的對偶規(guī)劃 321 3225minxxxz 無限制 321 321 321 321 , 0, 0 12 12 1 xxx xxx xxx xxx 18 二、對偶性質(zhì) （1）對偶性：對偶問題的對偶是原問題； （2）弱對偶性：若X和Y分別是原問題（max）的任 一可行解和對偶問題的任一可行解，則一定存 在CX YB； （3）無界性：若原問題有無界解，則其對偶問題無 可行解； （4）最優(yōu)性：若X是原問題（max）的可行解， Y 是對偶

7、問題的可行解，當(dāng)CX YB時，X是原 問題的最優(yōu)解，Y是對偶問題的最優(yōu)解； （5）強(qiáng)對偶性：弱原問題有最優(yōu)解，那么對偶問題 也一定有最優(yōu)解，且兩者的目標(biāo)函數(shù)值相等。 19 二、對偶性質(zhì) （6）互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解中，若對應(yīng)某 一約束條件的對偶變量值為非零，則該約束條件 取嚴(yán)格的等式；反之，若約束條件取嚴(yán)格的不等 式，則其對應(yīng)的對偶變量為零。 （7）用單純形法求解線性規(guī)劃問題時，迭代的每一步 在得到原問題的一個基本可行解的同時，其檢驗(yàn) 數(shù)行j的值是其對偶問題的一個基本解；在單純 形表中，原問題的松弛變量對應(yīng)對偶問題的變量， 對偶問題的剩余變量對應(yīng)原問題的變量；這些互 相對應(yīng)的變量如果在

8、一個問題的解中是基變量， 則在另一個問題的解中是非基變量。 20 對性質(zhì)7的說明 例：原問題 21 2maxxxz 0, 5 2426 155 21 21 21 2 xx xx xx x 21 對偶問題 321 52415minyyyw 0, 125 26 321 321 32 yyy yyy yy 22 3.3 對偶單純形法 n對偶單純形法是利用的對偶原理 來求解原問題的一種方法，而不 是用來求解對偶問題； n之前第2章的單純形法稱為原始單 純形法。 23 注意： n對偶單純形方法并不需要把原問題轉(zhuǎn)化為對偶問 題，只需利用原問題與對偶問題的數(shù)據(jù)相同（只 是所處位置不同）這一特點(diǎn)，直接在反映原

9、問題 的單純形表上進(jìn)行計算； n對偶單純形法并不要求原問題的初始解是基可行 解，因此，可以從非可行的基解開始迭代，從而 省去了引入人工變量的麻煩； n對偶單純形法要求對偶問題的解始終是基可行解， 即要求原問題的所有變量的檢驗(yàn)數(shù)非負(fù)，這是對 偶單純形法應(yīng)用的前提，十分苛刻，所以直接應(yīng) 用對偶單純形法求解線性規(guī)劃問題并不多見，主 要用于靈敏度分析。 24 二、對偶單純形法的計算步驟 25 26 例1：用對偶單純形法求解LP問題 421 34minxxxw 0, 242 32 4321 4321 4321 xxxx xxxx xxxx 27 例2：用對偶單純形法求解LP問題 321 52415max

10、xxxz 0, 125 26 321 321 32 xxx xxx xx 28 二、對偶單純形法中無可行解的識別 n在對偶單純形法中，總是存在著對偶問 題的可行解，因此對于能用對偶單純形 法求解的線性規(guī)劃問題來說，其解不存 在無界解的可能； n對偶單純形法無可行解的識別是通過入 基變量選擇失敗來加以反映的，即當(dāng)主 行的所有元素均為非負(fù)時，線性規(guī)劃問 題無可行解。 29 例3：用對偶單純形法求解下述線性規(guī)劃問題 321 2minxxxw 0, 122 102 321 321 321 xxx xxx xxx 30 思考題： n問：是否存在某一單純形表，既 可用單純形法求解，又可用對偶 單純形法法求

11、解？ 31 答：不行 如果可用單純形法法求解，必然存在b 0； 如果可用對偶單純形法求解，必然存在 0； 若b 0和 0同時成立，則得到最優(yōu)解。 32 思考題 問：對于一個LP問題，有可能用單純形法 求解，也有可能用對偶單純形法求解，問 可否在一個LP中先用單純形法求解，后用 對偶單純形法求解？或反之？ 33 答：不會 因?yàn)樵谇蠼膺^程中，始終有b 0或 0。 34 3.4 靈敏度分析 n靈敏度分析是指對系統(tǒng)因環(huán)境變化顯示出來的敏感程 度分析。 n就LP問題而言，決策者還需要掌握兩方面的信息： LP問題中的各項系數(shù)（價值系數(shù)、技術(shù)系 數(shù)、資源項）一個或幾個發(fā)生變化時，已 求得的最優(yōu)解會有什么變化

12、？ 上述系數(shù)在什么范圍內(nèi)發(fā)生變化時，線性 規(guī)劃問題的最優(yōu)解（或最優(yōu)基）不變。 35 將變化直接反映到最終單純形表中，并按下表處理： 原問題對偶問題 結(jié)論或繼續(xù)計算步驟 可行解可行解最優(yōu)解 可行解非可行解 用單純形法求解 非可行解 可行解用對偶單純形法求解 非可行解 非可行解 引入人工變量再求解 不含單位矩陣先作初等行變換獲取單位矩陣，再操作 36 一、資源系數(shù)變化的分析 37 例2 某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記 本和練習(xí)本三種產(chǎn)品。該廠現(xiàn)有工人100人，每天白坯 紙供應(yīng)限量30000kg。如果單獨(dú)生產(chǎn)各種產(chǎn)品時，每個 工人每天可生產(chǎn)原稿紙30捆或日記本30打或練習(xí)本30 箱。已

13、知原材料消耗為：每捆原稿紙用白坯紙10/3kg， 每打日記本用白坯紙40/3kg，每箱練習(xí)本用白坯紙 80/3kg，又知每生產(chǎn)一捆原稿紙可盈利2元，每生產(chǎn)一 打日記本可盈利3元，每生產(chǎn)一箱練習(xí)本可盈利1元。試 決定：在現(xiàn)有生產(chǎn)條件下，工廠盈利的最大方案； 如果白坯紙的供應(yīng)量不變，當(dāng)工人人數(shù)不足時，可招收 臨時工，臨時工每人每天40元，問該廠要不要招收臨時 工，最多招收多少人？ 38 二、價值系數(shù)變化的分析 39 情況1：價值系數(shù)發(fā)生變化的變量在 最終單純形表中為非基變量 40 情況2：價值系數(shù)發(fā)生變化的變量在 最終單純形表中為基變量 41 三、技術(shù)系數(shù)變化的分析 n情況1：技術(shù)系數(shù)發(fā)生變化的變

14、量在最終單純形表 中為非基變量。 n例1 線性規(guī)劃問題如下，問a23在什么范圍內(nèi)變化 時，最優(yōu)解保持不變。 54321 0032minxxxxxw 0, 974 3 521 5321 4321 xxx xxxx xxxx 42 情況2：技術(shù)系數(shù)發(fā)生變化的變量在 最終單純形表中為基變量 例2 同上題，問當(dāng)a11由1變?yōu)?時，原最優(yōu)解是否 發(fā)生改變，如果改變，求出新的最優(yōu)解。 54321 0032minxxxxxw 0, 974 3 521 5321 4321 xxx xxxx xxxx 43 44 45 四、增加一個新的變量的分析 n從形式上講，增加一個新的變量相當(dāng)于在單純 形表中增加一列，只要新增加的變量在最終單 純形表中的檢驗(yàn)數(shù)非負(fù)（min），原問題的最 優(yōu)解就不會改變。如果檢驗(yàn)數(shù)為負(fù)數(shù)，則需要 重新迭代，以獲取新的最優(yōu)解； n在實(shí)際問題中，增加一個新的變量相當(dāng)