CAN-File-10-10-08-13-線性規(guī)劃對偶.ppt
《CAN-File-10-10-08-13-線性規(guī)劃對偶.ppt》由會員分享,可在線閱讀,更多相關(guān)《CAN-File-10-10-08-13-線性規(guī)劃對偶.ppt(39頁珍藏版)》請在裝配圖網(wǎng)上搜索。
,第03章線性規(guī)劃:對偶LinearProgramming:duality,對偶理論-對偶問題-對偶定理-與單純形法的關(guān)系互補(bǔ)松弛-KKT條件基于對偶的方法-對偶單純形法(概念、步驟、收斂性),對偶理論,◎食譜問題:確定食品數(shù)量,滿足營養(yǎng)需求,花費最小?,對偶問題:舉例,n種食品,m種營養(yǎng)成份;-第j種食品的單價,-每單位第j種食品所含第i種營養(yǎng)的數(shù)量,-為了健康,每天必須食用第i種營養(yǎng)的數(shù)量,◎模型:,對偶問題:經(jīng)濟(jì)解釋,◎保健品公司:藥劑師、營養(yǎng)丸、定價問題,◎?qū)ε紗栴},對偶問題:對稱形式的對偶對,注:對偶是相互的,即對偶問題的對偶是原問題,◎原始問題(primal):,給定數(shù)據(jù),-原問題的變量,對偶問題:非對稱形式的對偶對,注:為了確定任一線性規(guī)劃問題的對偶,可以利用對稱形式或非對稱形式的對偶對!,◎原始問題(primal):,給定數(shù)據(jù),-原問題的變量,對偶問題:一般問題的對偶,給定數(shù)據(jù)c,A,b;記A的第j行為aj,A的第i列為ai,◎原問題(primal):,◎?qū)ε紗栴}(dual):,對偶問題:例子,對偶定理:弱對偶定理,弱對偶定理.設(shè)和分別是原始問題和對偶問題的可行解,則,推論2.如果原始問題與對偶問題之一無界,則另一個問題沒有可行解.,,對偶定理:強(qiáng)對偶定理,對于一般形式的線性規(guī)劃--利用凸集分離定理證明!,強(qiáng)對偶定理.如果原始問題和對偶問題之一有解,則另一個問題也有解,且最優(yōu)值相等.,與單純形法的關(guān)系:定理,如何由原始問題的解得到對偶問題的解?,與單純形法的關(guān)系:例子,考慮問題,引入松弛變量→標(biāo)準(zhǔn)形→利用單純形法求解,對偶問題,與單純形法的關(guān)系:例子(續(xù)),原問題最優(yōu)解,對偶問題最優(yōu)解,與單純形法的關(guān)系:單純形乘子,◎與基B對應(yīng)的單純形乘子(simplexmultiplier),◎經(jīng)濟(jì)解釋記A的列向量為aj,對應(yīng)費用為cj,j=1,…,n,--------解釋為單位向量ei的合成價格!,--解釋為aj的相對費用系數(shù),◎最優(yōu)性:對所有的i有,與單純形法的關(guān)系:單純形乘子(續(xù)),靈敏度(sensitivity,工程上),假設(shè)該問題的最優(yōu)基是B.則,假設(shè)非退化!,問題:當(dāng)向量b變化時,最優(yōu)值如何變化?,與單純形法的關(guān)系:單純形乘子(續(xù)),影子價格(shadowprice,經(jīng)濟(jì)上),稱為分量所對應(yīng)資源的邊際價格(marginalprice)或者影子價格(shadowprice),互補(bǔ)松弛ComplementarySlackness,互補(bǔ)松弛定理,定理.設(shè)和分別是對稱形式原始問題和對偶問題的可行解.則它們是各自最優(yōu)解的充要條件是:對所有的i和j有,對偶單純形法DualSimplexMethod,對偶單純形法:概述,◎適用問題:標(biāo)準(zhǔn)形問題有一個不可行的基本解,但對應(yīng)單純形乘子是對偶問題的可行解,◎單純形表中的表現(xiàn):,⊙第一張單純形表:相對費用系數(shù)非負(fù),但有基變量取負(fù)值!,⊙轉(zhuǎn)軸過程中:保持相對費用系數(shù)非負(fù),直到基變量全部取非負(fù)值!,則稱x是標(biāo)準(zhǔn)形問題的對偶可行基本解.,定義.假設(shè)是Ax=b的基本解.如果,基本解+可行+對偶可行=最優(yōu)解,對偶單純形法:對偶可行基本解,是對偶問題的可行解,即,目的:找新的使前m個等式中的某個與后n-m個不等式中的某個角色互換,同時使對偶問題的目標(biāo)函數(shù)值增大!,對偶單純形法:推導(dǎo)I,對偶單純形法:推導(dǎo)II,令,其中ui是B-1的第i行,則,出基變量:取負(fù)值的基變量(*****),進(jìn)基變量:取到最小正比值的非基變量(*****),步0給定對偶可行基本解對應(yīng)的單純形表.,步1若對每個i都有,停;當(dāng)前DFBS是最優(yōu)的.,步2選取i滿足yi0<0,這時,第i個基變量出基.,步4以yiq為轉(zhuǎn)軸元進(jìn)行轉(zhuǎn)軸,更新單純形表,返步1.,對偶單純形法:計算步驟,步3若,停,問題無可行解;否則,選q滿足,引入盈余變量;并給等式兩邊同乘-1;得初始表格,對偶單純形法:例子,對偶單純形法:例子(續(xù)),最優(yōu)解:,結(jié)論:由對偶可行基本解確定的單純形乘子集合與對偶問題可行集的極點是完全相同的。,對偶單純形法:進(jìn)一步的理解,原問題,,,,,對偶單純形法:收斂性,定理.如果標(biāo)準(zhǔn)形線性規(guī)劃問題的任一對偶可行基本解所對應(yīng)的非基變量的相對費用系數(shù)大于零,則對偶單純形法在有限步內(nèi)終止.,◎如果線性規(guī)劃問題可以用對偶單純形法求解,則必有界!其計算結(jié)果只能是不可行或者有解!,◎如果線性規(guī)劃問題可以用單純形法求解,則其無界或有解!◎兩階段法可以求解任一線性規(guī)劃問題;第I階段的結(jié)果分有可行解或者無可行解兩種;對有可行解的,在第II階段可得問題無界或有解!,◎典型情況(有顯然的對偶可行基本解),◎一般情況,⊙已有一個標(biāo)準(zhǔn)形問題的最優(yōu)解和最優(yōu)基,◇添加一個“不等式約束”后的新問題,對偶單純形法:啟動,⊙“不等式約束”+,后的新問題,線性規(guī)劃的應(yīng)用:博弈論(GameTheory),石頭-布-剪刀(Rock-Paper-Scissors),二人博弈,支付矩陣:行palyer給列player的支付(payoff),注:某個player利用任一確定性(純)策略,均可被另一個player擊敗.,二人零和博弈(Two-PersonZero-sumGames),給定mn矩陣A,注:A的行代表rowboy的確定性策略,而A的列代表colgirl的確定性策略.,行player(rowboy)選擇策略列player(colgirl)選擇策略rowboy支付給colgirlaij美元,確定性策略可能會很差!,隨機(jī)化策略(RandomizedStrategies),假設(shè)rowboy選擇策略i的概率是yi假設(shè)colgirl選擇策略j的概率是xj,如果使用隨機(jī)(混合)策略y,colgirl使用隨機(jī)策略x,則rowboy向colgirl的期望支付是,Colgirl的分析,假設(shè)colgirl準(zhǔn)備采取策略x,則rowboy最好的防衛(wèi)是利用y,其求解問題,因此colgirl應(yīng)該選取x,其極大化這種可能性,求解Max-Min問題(轉(zhuǎn)化成線性規(guī)劃問題),內(nèi)層優(yōu)化很容易:,引入標(biāo)量變量v表示內(nèi)層極小化的值:,因此colgirl的問題是,Rowboy的問題,類似地,rowboy選擇y,該問題等價于:,注:colgirl的問題是rowboy的問題的對偶,MinMax定理,設(shè)x*表示colgirl的max-min問題的解;設(shè)y*是rowboy的min-max問題的解.則,證明.由強(qiáng)對偶定理,我們有,且,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- CAN File 10 08 13 線性規(guī)劃 對偶
鏈接地址:http://m.jqnhouse.com/p-11494469.html