運籌學(xué)04對偶理論

1、第第1頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 對偶問題的提出對偶問題的提出 第一節(jié)第第2頁頁1 對偶問題的實際意義對偶問題的實際意義背景背景1 最優(yōu)化問題的兩個側(cè)面：最優(yōu)化問題的兩個側(cè)面： 周長給定，周長給定， 求面積最大求面積最大 面積給定，面積給定， 求周長最小求周長最小 容積給定，容積給定， 求表面積最小求表面積最小 表面積給定，表面積給定， 求容積最大求容積最大 資源給定，資源給定， 求掙錢最多求掙錢最多 收益給定，收益給定， 求用資源最少求用資源最少對偶問題對偶問題第第3頁頁背景背景2 出租機器還是搞生產(chǎn)？賣產(chǎn)品還是賣資源？出租機器還是搞生產(chǎn)？賣產(chǎn)品還是賣資源？第第4頁頁第第5頁頁

2、背景背景3 從數(shù)學(xué)公式中推導(dǎo)：從數(shù)學(xué)公式中推導(dǎo)：復(fù)習(xí)單純形表的矩陣形式：復(fù)習(xí)單純形表的矩陣形式：第第6頁頁第第7頁頁第第8頁頁第第9頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 原問題與對偶問題 第二節(jié)第第10頁頁2 原問題與對偶問題原問題與對偶問題 A b c x A c b y第第11頁頁第第12頁頁一般形式的對偶規(guī)劃一般形式的對偶規(guī)劃第第13頁頁解：解：先化為規(guī)范形式，再對偶轉(zhuǎn)換先化為規(guī)范形式，再對偶轉(zhuǎn)換第第14頁頁 0,01553232.23min3132121321321xxxxxxxxxxtsxxxz 0,01325332.52max2131321321321yyyyyyyyyytsy

3、yy 解：直接對偶轉(zhuǎn)換解：直接對偶轉(zhuǎn)換例例2：第第15頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 對偶問題的基本性質(zhì) 第三節(jié)第第16頁頁3 對偶的基本性質(zhì)對偶的基本性質(zhì)第第17頁頁3 對偶的基本性質(zhì)對偶的基本性質(zhì)第第18頁頁3 對偶的基本性質(zhì)對偶的基本性質(zhì)第第19頁頁3 對偶的基本性質(zhì)對偶的基本性質(zhì)第第20頁頁第第21頁頁第第22頁頁第第23頁頁 例例2 基互補性基互補性第第24頁頁原問題變量原問題變量原問題松弛變量原問題松弛變量對偶問題變量對偶問題變量對偶問題剩余變量對偶問題剩余變量基互補性基互補性第第25頁頁對偶問題變量對偶問題變量對偶問題剩余變量對偶問題剩余變量原問題變量原問題變量原問題松

4、弛變量原問題松弛變量基互補性基互補性第第26頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 影 子 價 格 第四節(jié)第第27頁頁背景：賣產(chǎn)品還是賣設(shè)備（資源）背景：賣產(chǎn)品還是賣設(shè)備（資源）影子價格影子價格第第28頁頁第第29頁頁影子價格的內(nèi)涵影子價格的內(nèi)涵第第30頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 對偶單純形法 第五節(jié)第第31頁頁5 對偶單純形法對偶單純形法第第32頁頁第第33頁頁第第34頁頁解：解：化為極大目標(biāo)，并標(biāo)準(zhǔn)化：化為極大目標(biāo)，并標(biāo)準(zhǔn)化：第第35頁頁第第36頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 靈敏度分析 第六節(jié)第第37頁頁6 靈敏度分析靈敏度分析|概況概況|改變價值向量改變價值向

5、量|改變右端向量改變右端向量|信息的變化：信息的變化： 價值向量變化價值向量變化市場變化市場變化 右端向量變化右端向量變化資源變化資源變化 系數(shù)矩陣變化系數(shù)矩陣變化技術(shù)進(jìn)步技術(shù)進(jìn)步 信息的變化對模型有什么影響？信息的變化對模型有什么影響？第第38頁頁靈敏度分析靈敏度分析|基本任務(wù)基本任務(wù):確定參數(shù)的影響范圍確定參數(shù)的影響范圍,即保持某即保持某LP問題的最問題的最優(yōu)基不變的條件下該參數(shù)單獨變化的最大范圍優(yōu)基不變的條件下該參數(shù)單獨變化的最大范圍|一個參數(shù)的影響范圍越小一個參數(shù)的影響范圍越小,最優(yōu)基對這一參數(shù)的變化最優(yōu)基對這一參數(shù)的變化就越敏感就越敏感,最優(yōu)基對該參數(shù)而言就越不穩(wěn)定最優(yōu)基對該參數(shù)而言

6、就越不穩(wěn)定|另一個任務(wù)另一個任務(wù):當(dāng)最優(yōu)解隨參數(shù)變化時如何簡便地求得當(dāng)最優(yōu)解隨參數(shù)變化時如何簡便地求得新最優(yōu)解新最優(yōu)解第第39頁頁1、價值向量的改變、價值向量的改變第第40頁頁原問題最優(yōu)解：原問題最優(yōu)解：第第41頁頁可以看出價值可以看出價值1變化的影響：變化的影響：第第42頁頁可以看出價值可以看出價值2變化的影響：變化的影響：第第43頁頁2、右端向量、右端向量 b 的改變的改變第第44頁頁原問題最優(yōu)解：原問題最優(yōu)解：初始基初始基第第45頁頁第第46頁頁3、增加一個變量、增加一個變量第第47頁頁原問題最優(yōu)解：原問題最優(yōu)解：第第48頁頁繼續(xù)迭代繼續(xù)迭代6x影響表中第影響表中第6列：列：第第49頁頁第第50頁頁4、增加一個約束條件、增加一個約束條件第第51頁頁解：解：第第52頁頁第第53頁頁使用對偶單純形法：使用對偶單純形法：第第54頁頁第第55頁頁線性規(guī)劃及單純型法線性規(guī)劃及單純型法 參數(shù)線性規(guī)劃 第七節(jié)第第56頁頁解：解：第第57頁頁