《運(yùn)籌學(xué)》清華版-2-01對(duì)偶問題

1、編輯ppt第一節(jié)第一節(jié) 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題n一、對(duì)偶問題的提出一、對(duì)偶問題的提出n二、原問題與對(duì)偶問題的數(shù)學(xué)模型二、原問題與對(duì)偶問題的數(shù)學(xué)模型n三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種實(shí)例：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種 產(chǎn)品，產(chǎn)品， 有關(guān)數(shù)據(jù)如下表：有關(guān)數(shù)據(jù)如下表： 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤（元）利潤（元）0612521115時(shí)時(shí)24時(shí)時(shí) 5時(shí)時(shí)產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品D一、對(duì)偶問題的提出一、對(duì)偶問題的提出如何安排生產(chǎn)，如何安排生產(chǎn)，使獲利最多使獲利最多？廠廠家家設(shè)設(shè) 產(chǎn)量產(chǎn)量 產(chǎn)量產(chǎn)量1x2x 0, 5 2

2、426 155 2max 212121221xxxxxxxs.t.xxz 設(shè)：設(shè)備設(shè)：設(shè)備A A 元時(shí)元時(shí) 設(shè)備設(shè)備B B 元時(shí)元時(shí) 調(diào)試工序調(diào)試工序 元時(shí)元時(shí)1y2y3y收收購購 付出的代價(jià)最小，付出的代價(jià)最小， 且對(duì)方能接受。且對(duì)方能接受。 廠家覺得比廠家覺得比自己生產(chǎn)有利。自己生產(chǎn)有利。 設(shè)備設(shè)備A y1 設(shè)備設(shè)備B y2調(diào)試工序調(diào)試工序y3利潤（元）利潤（元）0612521115時(shí)時(shí)24時(shí)時(shí) 5時(shí)時(shí)Dn廠家能接受的條件：廠家能接受的條件：n收購方的意愿：收購方的意愿：32152415minyyyw單位產(chǎn)品單位產(chǎn)品出租出租收入不低于收入不低于2 2元元單位產(chǎn)品單位產(chǎn)品出租出租收入不低于收

3、入不低于1 1元元出讓代價(jià)應(yīng)不低于出讓代價(jià)應(yīng)不低于用同等數(shù)量的資源用同等數(shù)量的資源自己生產(chǎn)的利潤。自己生產(chǎn)的利潤。1252632132yyyyy廠廠家家0, 5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw對(duì)對(duì)偶偶問問題題原原問問題題收收購購廠廠家家一對(duì)對(duì)偶問題一對(duì)對(duì)偶問題11265021xx5241512321yyymaxmin對(duì)對(duì)偶偶問問題題原問題原問題0 min bAX 0X . .CXz max YC s.t. YAYb wts),(21ccC 21xxX)(ijaA ),

4、y,y(yY321321bbbb3 3個(gè)約束個(gè)約束2 2個(gè)變量個(gè)變量2 2個(gè)約束個(gè)約束 3 3個(gè)變量個(gè)變量原問題原問題對(duì)偶問題對(duì)偶問題一般規(guī)律nccc.21mnmmnnaaaaaaaaa.212222111211nxxx.21myyy.21.maxmin對(duì)對(duì)偶偶問問題題原問題原問題mbbb.21二、對(duì)稱形式的對(duì)偶問題二、對(duì)稱形式的對(duì)偶問題nixbxaxaxabxaxaxabxaxaxaxcxcxczimnmnmmnnnnnn,.,2 , 1, 0.max221122222121112121112211原問題原問題mjycyayayacyayayacyayayaybybybwjnmmnnnmmm

5、mmm,.2 , 1, 0.min221122222112112211112211對(duì)偶問題對(duì)偶問題mmnmmnnmTmmcccaaaaaaaaayyytsbbbyyyw,.,.,.,. .,.,.,min21212222111211212121可寫成可寫成YY 0 min bAX 0X . .CXz max YC s.t. YAYb wts原問題原問題對(duì)偶問題對(duì)偶問題行向量myyyY,.,21 特點(diǎn)：特點(diǎn)： 1 2限定向量限定向量b 價(jià)值向量價(jià)值向量C （資源向量）資源向量） 3一個(gè)約束一個(gè)約束 一個(gè)變量。一個(gè)變量。 4 的的LP約束約束“ ” 的的 LP是是“ ”的約束。的約束。 5變量都是

6、非負(fù)限制。變量都是非負(fù)限制。 min max z maxzmin 其它形式其它形式的對(duì)偶的對(duì)偶? ?n對(duì)偶問題的對(duì)偶是原問題對(duì)偶問題的對(duì)偶是原問題 三、非對(duì)稱形式的對(duì)偶三、非對(duì)稱形式的對(duì)偶 1 若原問題的約束條件中有等式若原問題的約束條件中有等式 例：求例：求LP問題的對(duì)偶問題問題的對(duì)偶問題0, 5 2426 155 2max212121221xxxxxxxs.t.xxz第二個(gè)約束第二個(gè)約束是等式是等式原問題原問題解：解：0,5242624261552max21212121221xxxxxxxxxxxz3221 yyyy對(duì)偶問題對(duì)偶問題0, ,1 2252 665 242415min32213

7、2213223221yyyyyyyyyyyyyyyw222 yyy令對(duì)偶問題對(duì)偶問題無約束23132132321,0,1252652415minyyyyyyyyyyyw11265021xx5241512321yyy=maxmin對(duì)對(duì)偶偶問問題題原問題原問題無約束無約束結(jié)論：結(jié)論：等式等式約束約束 對(duì)偶對(duì)偶變量無約束變量無約束？原問題（？原問題（max）的約束條件是的約束條件是例：例：1221122max2515 6224 ,0zxxxxxxx1221122max2515 -6224 ,0zxxxxxxx1221212min152462 521 ,0wyyyyyyy1221212min152462 521 0,0wyyyyyyy(y2= - y2)四、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系四、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系約束條件的限定向量目標(biāo)函數(shù)的價(jià)值向量自由變量變量變量個(gè)變量約束約束約束個(gè)約束目標(biāo)函數(shù) 00 maxmn z原問題（或?qū)ε紗栴}）原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）對(duì)偶問題（或原問題）目標(biāo)函數(shù)的價(jià)值向量約束條件的限定向量約束約束約束個(gè)約束自由變量變量變量個(gè)變量目標(biāo)函數(shù) 00minmn w zmax zminn例例:無約束,x x,xxxxxxxxxxs.txxxx z