對偶問題的分析ppt課件(編輯修改稿)
2025-05-25 23:35 本頁面
【文章內容簡介】 DP)均可行，那么均可行，那么 (LP)和和 (DP)均有最優(yōu)解均有最優(yōu)解 ,且且最優(yōu)值相等。最優(yōu)值相等。216。 如果原問題有最優(yōu)解，則其對偶問題也一樣具有最優(yōu)如果原問題有最優(yōu)解，則其對偶問題也一樣具有最優(yōu)解，且有解，且有 maxz=minw。二、對偶問題的基本性質 14167。 Ⅲ 弱對偶定理216。 若 x,y分別為（ LP)和（ DP）的可行解，那么 cTx≤bTy。167。 推論216。 ① 若 LP（或 DP）可行，那么 LP（或 DP）無有限最優(yōu)解 (有無界解 )的充分必要條件是 DP（或 LP）無可行解。216。 ？？當 LP（或 DP）無可行解時，則 DP（或 LP）具有無界解。216。 ② 極大化問題的任意一個可行解所對應的目標函數值是其對偶問題最優(yōu)目標函數值的一個下界。 216。 ③ 極小化問題的任意一個可行解所對應的目標函數值極小化問題的任意一個可行解所對應的目標函數值是其對偶問題最優(yōu)目標函數值的一個上界。是其對偶問題最優(yōu)目標函數值的一個上界。15167。 ⅣⅣ 最優(yōu)性準則定理216。 若若 x,y分別分別 (LP)， (DP)的可行解的可行解 ,且且 cTx=bTy，那么，那么 x,y分別為分別為 (LP)和和 (DP)的最優(yōu)解。的最優(yōu)解。16三、影子價格167。 市場價格市場價格167。 影子價格影子價格 ，確切的定義是： 一個線性規(guī)劃對偶問一個線性規(guī)劃對偶問題的最優(yōu)解題的最優(yōu)解 （簡稱為 “對偶最優(yōu)解 ”）。167。 對偶變量 yi：代表對一個單位第 i種資源的估價。這種估價不是資源的市場價格，而是根據資源在生產中做出的貢獻而作的估價。167。 bi是線性規(guī)劃原問題約束條件右端項，它代表第 i種資源的擁有量。17252。 影子價格是一個向量，它的分量表示最優(yōu)目標值隨相應資源數量變化的變化率。252。若 x*,y* 分別為（ LP） 和（ DP） 的最優(yōu)解， 那么， cT x* = bT y* 。 根據 w= bTy*=b1y1*+b2y2*+? +bmym* 可知 ?w/ ?bi = yi* 252。 yi* 表示 bi 變化 1個單位對目標 W 產生的影響，稱 yi* 為 bi的影子價格。 18 企業(yè)可以根據現有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設備用于外加工或出租，若租費高于某設備的影子價格，可考慮出租該設備，否則不宜出租。第二，是否將投資用于購買設備，以擴大生產能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。19 需要指出，影子價格不是固定不變的，當約束條件、產品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格是指資源在一定范圍內增加時的情況，當某種資源的增加超過了這個 “ 一定的范圍 ” 時，總利潤的增加量則不是按照影子價格給出的數值線性地增加。這個問題還將在靈敏度分析一節(jié)中討論。20利用最優(yōu)單純形表求對偶問題最優(yōu)解 標準形式： Max z = 50 x1 + 100 x2 . x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0四、對偶問題的解21cBB1IB=(p1, p4,p2 ) B1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價格 y1 = 50 y2 = 0 y3 = 50 , yi= cBB1 。 22167。、理論及經濟意義167。純形法167。23 對偶單純形法的基本思想 對偶單純形法的基本思想是：從一個 對偶可行解 （檢驗數非正）出發(fā)；然后檢驗原問題的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可行解（檢驗數非正）。24 如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持 對偶解的可行性 （即檢驗數非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，當同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解 。25167。 ,對應一個基本解 ,所有檢驗數均非正 ,轉 2； b’≥0, 則得到最優(yōu)解 ,停止 。否則 ,若有 bk0則選 b最小 的基變量為出基變量 ,轉 3 akj’≥0( j = 1,2,…, n )， 則原問題無可行解 ,停止 。 否則 ,若有 akj’0 則選 ?=min{?j’ / akj’┃ akj’0 }=?r’/ akr’ 那么 xr為入基變量 ,轉 4； 4. 作矩陣行變換使
教學課件相關推薦
鄂ICP備17016276號-1