運(yùn)籌學(xué)_9 對(duì)偶問題的性質(zhì)

1、HomeHomeOperational Research2代表最優(yōu)解代表可行解 )0(XX 建立對(duì)偶問題與原問題之間的橋梁。少證明，多說明其本質(zhì)與應(yīng)用的價(jià)值。Operational Research3Operational Research4Operational Research5 0Y Cs.t YAYb w 0X bs.t AXCXzmin max 0Y CYAs.t Yb w max 0X bAXs.t CX w0Y CYAs.t Yb w min max 0X bs.t AXCX w max 又變?yōu)閙ax問題：兩邊乘負(fù)號(hào)兩邊再乘負(fù)號(hào)A取轉(zhuǎn)置，(YA)= AY Operational

2、Research6 原問題對(duì)偶問題bYCX)0()0(Operational Research7原問題對(duì)偶問題bYXCbYCXOperational Research8Operational Research9原問題對(duì)偶問題bYXCbYCXOperational Research100,12 2 s.t.max32132132121xxxxxxxxxxxz0,0 1 12 . .2min2121212121yyyyyyyytsyyw（1）觀察出原問題； （2）因?yàn)閷?duì)偶問題的式1與基本條件存在矛盾，因此，無可行解。根據(jù)強(qiáng)對(duì)偶性，如果原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解。因此，原問題Operati

3、onal Research11 0,422y 3686min w dual0,62 82643max 32132121321212212121yy yyyys.t y yyyxxxx xxs.t x xxz ：注意：（1）是“檢驗(yàn)數(shù)的相反數(shù)”，而不是檢驗(yàn)數(shù)； （2）第零步原問題檢驗(yàn)數(shù)（34000），對(duì)偶問題基本解為（00034）原因：原問題的檢驗(yàn)數(shù)是價(jià)值系數(shù)，是對(duì)偶問題的約束條件即基本解的相反數(shù)對(duì)應(yīng)性：原問題第一個(gè)檢驗(yàn)數(shù)，是對(duì)偶問題第一個(gè)剩余變量的解； 三個(gè)松弛變量的檢驗(yàn)數(shù)，是對(duì)偶問題三個(gè)變量的基本解。Operational Research120,422y 3686min w dual0,62 82643max 32132121321212212121yy yyyys.t y yyyxxxx xxs.t x xxz ：Operational Research13020232 20322 . .432max4, 3 , 2, 1432143214321xxxxxxxxxtsxxxxz0,423 332 22 12 . .2020 min212121212121yyyyyyyyyytsyyw題目：