CAN-File-10-10-08-13-線(xiàn)性規(guī)劃對(duì)偶.ppt
,第03章線(xiàn)性規(guī)劃:對(duì)偶LinearProgramming:duality,對(duì)偶理論對(duì)偶問(wèn)題對(duì)偶定理與單純形法的關(guān)系互補(bǔ)松弛KKT條件基于對(duì)偶的方法對(duì)偶單純形法(概念、步驟、收斂性),對(duì)偶理論,食譜問(wèn)題:確定食品數(shù)量,滿(mǎn)足營(yíng)養(yǎng)需求,花費(fèi)最???,對(duì)偶問(wèn)題:舉例,n種食品,m種營(yíng)養(yǎng)成份;第j種食品的單價(jià),每單位第j種食品所含第i種營(yíng)養(yǎng)的數(shù)量,為了健康,每天必須食用第i種營(yíng)養(yǎng)的數(shù)量,模型:,對(duì)偶問(wèn)題:經(jīng)濟(jì)解釋,保健品公司:藥劑師、營(yíng)養(yǎng)丸、定價(jià)問(wèn)題,對(duì)偶問(wèn)題,對(duì)偶問(wèn)題:對(duì)稱(chēng)形式的對(duì)偶對(duì),注:對(duì)偶是相互的,即對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題,原始問(wèn)題(primal):,給定數(shù)據(jù),原問(wèn)題的變量,對(duì)偶問(wèn)題:非對(duì)稱(chēng)形式的對(duì)偶對(duì),注:為了確定任一線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶,可以利用對(duì)稱(chēng)形式或非對(duì)稱(chēng)形式的對(duì)偶對(duì)!,原始問(wèn)題(primal):,給定數(shù)據(jù),原問(wèn)題的變量,對(duì)偶問(wèn)題:一般問(wèn)題的對(duì)偶,給定數(shù)據(jù)c,A,b;記A的第j行為aj,A的第i列為ai,原問(wèn)題(primal):,對(duì)偶問(wèn)題(dual):,對(duì)偶問(wèn)題:例子,對(duì)偶定理:弱對(duì)偶定理,弱對(duì)偶定理.設(shè)和分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解,則,推論2.如果原始問(wèn)題與對(duì)偶問(wèn)題之一無(wú)界,則另一個(gè)問(wèn)題沒(méi)有可行解.,對(duì)偶定理:強(qiáng)對(duì)偶定理,對(duì)于一般形式的線(xiàn)性規(guī)劃利用凸集分離定理證明!,強(qiáng)對(duì)偶定理.如果原始問(wèn)題和對(duì)偶問(wèn)題之一有解,則另一個(gè)問(wèn)題也有解,且最優(yōu)值相等.,與單純形法的關(guān)系:定理,如何由原始問(wèn)題的解得到對(duì)偶問(wèn)題的解?,與單純形法的關(guān)系:例子,考慮問(wèn)題,引入松弛變量標(biāo)準(zhǔn)形利用單純形法求解,對(duì)偶問(wèn)題,與單純形法的關(guān)系:例子(續(xù)),原問(wèn)題最優(yōu)解,對(duì)偶問(wèn)題最優(yōu)解,與單純形法的關(guān)系:?jiǎn)渭冃纬俗?與基B對(duì)應(yīng)的單純形乘子(simplexmultiplier),經(jīng)濟(jì)解釋記A的列向量為aj,對(duì)應(yīng)費(fèi)用為cj,j=1,n,解釋為單位向量ei的合成價(jià)格!,解釋為aj的相對(duì)費(fèi)用系數(shù),最優(yōu)性:對(duì)所有的i有,與單純形法的關(guān)系:?jiǎn)渭冃纬俗?續(xù)),靈敏度(sensitivity,工程上),假設(shè)該問(wèn)題的最優(yōu)基是B.則,假設(shè)非退化!,問(wèn)題:當(dāng)向量b變化時(shí),最優(yōu)值如何變化?,與單純形法的關(guān)系:?jiǎn)渭冃纬俗?續(xù)),影子價(jià)格(shadowprice,經(jīng)濟(jì)上),稱(chēng)為分量所對(duì)應(yīng)資源的邊際價(jià)格(marginalprice)或者影子價(jià)格(shadowprice),互補(bǔ)松弛ComplementarySlackness,互補(bǔ)松弛定理,定理.設(shè)和分別是對(duì)稱(chēng)形式原始問(wèn)題和對(duì)偶問(wèn)題的可行解.則它們是各自最優(yōu)解的充要條件是:對(duì)所有的i和j有,對(duì)偶單純形法DualSimplexMethod,對(duì)偶單純形法:概述,適用問(wèn)題:標(biāo)準(zhǔn)形問(wèn)題有一個(gè)不可行的基本解,但對(duì)應(yīng)單純形乘子是對(duì)偶問(wèn)題的可行解,單純形表中的表現(xiàn):,第一張單純形表:相對(duì)費(fèi)用系數(shù)非負(fù),但有基變量取負(fù)值!,轉(zhuǎn)軸過(guò)程中:保持相對(duì)費(fèi)用系數(shù)非負(fù),直到基變量全部取非負(fù)值!,則稱(chēng)x是標(biāo)準(zhǔn)形問(wèn)題的對(duì)偶可行基本解.,定義.假設(shè)是Ax=b的基本解.如果,基本解可行對(duì)偶可行最優(yōu)解,對(duì)偶單純形法:對(duì)偶可行基本解,是對(duì)偶問(wèn)題的可行解,即,目的:找新的使前m個(gè)等式中的某個(gè)與后n-m個(gè)不等式中的某個(gè)角色互換,同時(shí)使對(duì)偶問(wèn)題的目標(biāo)函數(shù)值增大!,對(duì)偶單純形法:推導(dǎo)I,對(duì)偶單純形法:推導(dǎo)II,令,其中ui是B-1的第i行,則,出基變量:取負(fù)值的基變量(*),進(jìn)基變量:取到最小正比值的非基變量(*),步0給定對(duì)偶可行基本解對(duì)應(yīng)的單純形表.,步1若對(duì)每個(gè)i都有,停;當(dāng)前DFBS是最優(yōu)的.,步2選取i滿(mǎn)足yi0<0,這時(shí),第i個(gè)基變量出基.,步4以yiq為轉(zhuǎn)軸元進(jìn)行轉(zhuǎn)軸,更新單純形表,返步1.,對(duì)偶單純形法:計(jì)算步驟,步3若,停,問(wèn)題無(wú)可行解;否則,選q滿(mǎn)足,引入盈余變量;并給等式兩邊同乘-1;得初始表格,對(duì)偶單純形法:例子,對(duì)偶單純形法:例子(續(xù)),最優(yōu)解:,結(jié)論:由對(duì)偶可行基本解確定的單純形乘子集合與對(duì)偶問(wèn)題可行集的極點(diǎn)是完全相同的。,對(duì)偶單純形法:進(jìn)一步的理解,原問(wèn)題,對(duì)偶單純形法:收斂性,定理.如果標(biāo)準(zhǔn)形線(xiàn)性規(guī)劃問(wèn)題的任一對(duì)偶可行基本解所對(duì)應(yīng)的非基變量的相對(duì)費(fèi)用系數(shù)大于零,則對(duì)偶單純形法在有限步內(nèi)終止.,如果線(xiàn)性規(guī)劃問(wèn)題可以用對(duì)偶單純形法求解,則必有界!其計(jì)算結(jié)果只能是不可行或者有解!,如果線(xiàn)性規(guī)劃問(wèn)題可以用單純形法求解,則其無(wú)界或有解!兩階段法可以求解任一線(xiàn)性規(guī)劃問(wèn)題;第I階段的結(jié)果分有可行解或者無(wú)可行解兩種;對(duì)有可行解的,在第II階段可得問(wèn)題無(wú)界或有解!,典型情況(有顯然的對(duì)偶可行基本解),一般情況,已有一個(gè)標(biāo)準(zhǔn)形問(wèn)題的最優(yōu)解和最優(yōu)基,添加一個(gè)“不等式約束”后的新問(wèn)題,對(duì)偶單純形法:?jiǎn)?dòng),“不等式約束”,后的新問(wèn)題,線(xiàn)性規(guī)劃的應(yīng)用:博弈論(GameTheory),石頭布剪刀(Rock-Paper-Scissors),二人博弈,支付矩陣:行palyer給列player的支付(payoff),注:某個(gè)player利用任一確定性(純)策略,均可被另一個(gè)player擊敗.,二人零和博弈(Two-PersonZero-sumGames),給定mn矩陣A,注:A的行代表rowboy的確定性策略,而A的列代表colgirl的確定性策略.,行player(rowboy)選擇策略列player(colgirl)選擇策略rowboy支付給colgirlaij美元,確定性策略可能會(huì)很差!,隨機(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,其求解問(wèn)題,因此colgirl應(yīng)該選取x,其極大化這種可能性,求解Max-Min問(wèn)題(轉(zhuǎn)化成線(xiàn)性規(guī)劃問(wèn)題),內(nèi)層優(yōu)化很容易:,引入標(biāo)量變量v表示內(nèi)層極小化的值:,因此colgirl的問(wèn)題是,Rowboy的問(wèn)題,類(lèi)似地,rowboy選擇y,該問(wèn)題等價(jià)于:,注:colgirl的問(wèn)題是rowboy的問(wèn)題的對(duì)偶,MinMax定理,設(shè)x*表示colgirl的max-min問(wèn)題的解;設(shè)y*是rowboy的min-max問(wèn)題的解.則,證明.由強(qiáng)對(duì)偶定理,我們有,且,