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