對偶問題與靈敏度分析-展示頁
2025-05-27 07:19本頁面
【正文】 ???????????????0,43232432m i n321321321321xxxxxxxxxxxxZ練習(xí)： ????????????????????????)( 04 323 2432m a x5153214321321jxxxxxxxxxxxxZcj 2 3 4 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 3 1 2 1 1 0 0 x5 4 2 1 3 0 1 Z 2 3 4 0 0 i?cj 2 3 4 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 1 0 5/2 1/2 1 1/2 2 x1 2 1 1/2 3/2 0 1/2 Z 0 4 1 0 1 i?cj 2 3 4 0 0 cB xB b x1 x2 x3 x4 x5 3 x2 2/5 0 1 1/5 2/5 1/5 2 x1 11/5 1 0 7/5 1/5 2/5 Z 28/5 0 0 3/5 8/5 1/5 i?Y=（ 8/5 . 1/5） X=（ 2/5 . 11/5 . 0） Z =28/5 靈敏度分析 為什么要進(jìn)行靈敏度分析？ 前面對線性規(guī)劃的討論，價值系數(shù) c， 資源系數(shù) b和技術(shù)系數(shù)矩陣 A都是已知 常數(shù) 。 什么是對偶單純形法？ 也就是說，求解原問題（ LP）時，可以從（ LP）的一個基本解（并不一定是基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值（ Z=Y b= CB B1b =CX）減少，當(dāng)?shù)?XB=B1b≥0時，即找到了（ LP）的最優(yōu)解，這就是對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。 (證明 ) 該定理說明：如果原問題是 最大化 問題，則它的任意可行解對應(yīng)的 目標(biāo)函數(shù)值 都會 小于等于 其對偶問題 (極小化 )的任一可行解對應(yīng)的 目標(biāo)函數(shù)值 Max z=2x1+2x24x3 . X1+3x2+3x3≤30 4x1+2x2+4x3≤80 X1,x2,x3≥0 min w=30y1+80y2 . y1+4y2≥2 3y1+2y2≥2 3y1+4y2≥4 y1,y2≥0 例如 任意取一些可行解試試看？ 定理 2（無界性） 若一個問題無界，則另一個問題不可行 max z=x1+x2 . 2x1+x2 ≤ 40 x1x2 ≤ 20 x1,x2≥ 0 可行域 Min w=40y1+20y2 . 2y1+y2 ≥ 1 y1y2 ≥ 1 y1,y2 ≥0 對偶問題顯然無可行解！ 例如 定理 3 （最優(yōu)性定理） 若 X(0), Y(0) 分別為（ LP）和（ DP）的可行解，且 CX (0) = Y (0) b ，那么 X(0), Y(0)分別為（ LP）和（ DP）的最優(yōu)解 證明 定理 4 （對偶定理） 若其中一個問題有最優(yōu)解，則另一個問題也有最優(yōu)解，且兩者最優(yōu)值相等 證明 定理 5（互補(bǔ)松弛定理） 原問題及其對偶問題的可行解 X(0)和 Y(0)是 最優(yōu)解 的 充要條件 是： Y(0)XS=0， YSX(0)=0 XS,YS分別為原問題松弛向量和對偶問題剩余向量 該定理說明：一對對偶問題達(dá)到最優(yōu)，當(dāng)且僅當(dāng)松約束對應(yīng)的對偶變量必定是緊的 利用互補(bǔ)松馳定理，可以在知道一個問題的最優(yōu)解時， 求解其對偶問題的最優(yōu)解 例： Min z=2x1+3x2+5x3+2x4+3x5 . X1+x2+2x3+x4+3x5≥4 2x12
法律信息相關(guān)推薦
鄂ICP備17016276號-1