【正文】 的生產(chǎn)，需要消耗原材料 A和 B兩種資源。 隨著資源的買進(jìn)和賣出，它的影子價(jià)格也隨之發(fā)生變化。 55 資源的影子價(jià)格實(shí)際上是一種機(jī)會(huì)成本。 對(duì)偶線性規(guī)劃 54 影子價(jià)格是一種邊際價(jià)格。同樣一種資源，若它們?cè)诓煌髽I(yè)中發(fā)揮的作用不同，對(duì)這種資源所做的估價(jià)也不同，即影子價(jià)格也不同。 對(duì)偶線性規(guī)劃 第 i種資源的估價(jià) 第 i種資源的擁有量 ?影子價(jià)格的意義 市場(chǎng)價(jià)格 主要隨市場(chǎng)供求變化；而它的 影子價(jià)格 有賴于 資源 的利用情況，是未知數(shù)。 對(duì)偶線性規(guī)劃 49 【 另例 】 用對(duì)偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標(biāo)準(zhǔn)型是： maxZ’= 9x1+7x24x3 +0x4 +0x5 5x1 + x2 +7x3 +x4 = 5 3x1 +4x2 +8x3 =4 2x1 +6x2 +8x3 x5=6 x1 , x2 , x3 , x4 , x5 ≥ 0 ???????????????????0,68624843575 479 m i n 321321321321321xxxxxxxxxxxxxxxzmaxZ’= 9x1+7x24x3 +0x4 +0x5 5x1 + x2 +7x3 +x4 = 5 3x1 +4x2 +8x3 =4 2x1 6x2 8x3 +x5= 6 x1 , x2 , x3 , x4 , x5 ≥ 0 對(duì)偶線性規(guī)劃 50 此時(shí)最優(yōu)，最優(yōu)解 :Y*=(0,1,0,4,0)T， MaxZ’ =7 MinZ =7 對(duì)偶線性規(guī)劃 6 1 8 6 2 4 0 8 4 3 5 0 7 1 5 0 0 1 0 0 4 7 9 0 ～ 0 1 4 0 5/2 1 0 2 1 3/4 4 0 5 0 17/4 0 0 1 7 0 18 0 57/4 0 【 練習(xí) 】 用對(duì)偶單純形方法解下述線性規(guī)劃問題 ????????????0,3m i n21212121xxxxxxxxz942 對(duì)偶線性規(guī)劃 52 影子價(jià)格 從對(duì)偶問題的基本性質(zhì)可以看出，在單純形法的每步迭代中有目標(biāo)函數(shù) ?????? miiinjjj ybxcz11 此時(shí)的估價(jià)不是市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中的貢獻(xiàn)而作的估價(jià)。 （ 2） 對(duì)于變量個(gè)數(shù)多于約束方程個(gè)數(shù)的線性規(guī)劃問題 ，采用對(duì)偶單純形法計(jì)算量較少 。 （ 4） 以 ark為主元按原始單純形方法的迭代方法進(jìn)行迭代 ，得到新的單純形表。 ? ? riii bBbBbB )(0)()(m i n 111 ??（ 3） 確定入基變量 。 （ 2） 確定出基變量 。 2560 24 14 0 0 Z 16 2/5 1/10 0 1 0 12 1/5 3/10 1 0 0 相當(dāng)于：直到對(duì)偶問題的解可行為止 相當(dāng)于：即直到原問題的解可行為止 對(duì)偶線性規(guī)劃 45 【 例 】 用對(duì)偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標(biāo)準(zhǔn)型是： minZ=2x1+3x2+4x3 x1+ 2x2+x3 ≥ 3 2x1 x2 +3x3 ≥4 x1 , x2 , x3 ≥ 0 maxZ’= 2x13x24x3 +0x4 +0x5 x1+ 2x2+x3 x4 = 3 2x1 x2 +3x3 x5 =4 x1 , x2 , x3 , x4 , x5 ≥ 0 maxw’= 2x13x24x3 +0x4 +0x5 x1 2x2 x3 +x4 = 3 2x1 + x2 3x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0 對(duì)偶線性規(guī)劃 46 應(yīng)用對(duì)偶單純形方法之矩陣法 0 0 4 3 2 W’ 4 1 3 1 2 0 3 0 1 2 1 0 0 0 1 ～ 4 1 1 4 0 W’ 2 1/2 3/2 1/2 1 0 1 1/2 1/2 5/2 0 0 0 0 1 ～ 28/5 1/5 3/5 0 0 W’ 11/5 2/5 7/5 0 1 0 2/5 1/5 1/5 1 0 0 8/5 1/5 2/5 最優(yōu)解 :Y*=(11/5,2/5,0,0,0)T， Maxw’ =28/5 maxw’= 2x13x24x3 +0x4 +0x5 x1 2x2 x3 +x4 = 3 2x1 + x2 3x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0 MinZ* = 28/5 對(duì)偶線性規(guī)劃 47 小結(jié)：對(duì)偶單純形方法的解題過程一般分為四步 （ 1） 寫出與已有的初始基 B對(duì)應(yīng)的初始單純形表 。 CyA ? 0? yAC 所以 ,對(duì)偶單純形方法實(shí)質(zhì) 就是在保證對(duì)偶問題可行的條件下向原問題可行的方向迭代。與對(duì)偶單純形方法相對(duì)應(yīng)，原已有的單純形方法稱 原始單純形方法 。 對(duì)偶線性規(guī)劃 32 問題：可否用單純型法求解原問題的同時(shí)求對(duì)偶問題的解 結(jié)論：用單純形法求解線性規(guī)劃時(shí) ， 迭代的每一步在得到原問題一個(gè) 基本可行解 的同時(shí) ， 其： 線性規(guī)劃原問題及其對(duì)偶問題之間存在一對(duì)互補(bǔ)的基解 ，其中 原問題的松馳變量 對(duì)應(yīng) 對(duì)偶問題的原變量 ， 對(duì)偶問題的剩余變量 對(duì)應(yīng) 原問題的原變量 ；這些互相對(duì)應(yīng)的變量如果在一個(gè)問題的解中是 基變量 ， 則在另一問題的解中 是非基變量 ；將這兩個(gè)解代入各自的目標(biāo)數(shù)中有 z=w。 maxZ=5=minS=5 得原問題的最優(yōu)解 X*=(1,0,0,0,1) minS=5 對(duì)偶線性規(guī)劃 29 【 練習(xí) 】 已知線性規(guī)劃問題為： =2x1+4x2+x3+x4 . x1+3x2 +x4≤8 2x1+x2 ≤6 x2 + x3 +x4≤6 x1 + x2 +x3 ≤9 xj≥0（ j=1,2,3,4） 附 練習(xí)答案： y1=4/5, y2=3/5, y3=1, y4=0 已知原問題的最優(yōu)解為 :X*=(2,2,4,0)T，試根據(jù)互補(bǔ)松弛定理解出其對(duì)偶問題的最優(yōu)解。 對(duì)偶線性規(guī)劃 28 【 又例 】 應(yīng)用如上關(guān)系求解線性規(guī)劃問題 例 5 已知線性規(guī)劃問題 Min S=2x1 + 3x2 + 5x3 + 2x4 + 3x5 . x1 + x2 + 2x3 + x4 + 3x5 ≥ 4 2x1 – x2 + 3x3 + x4 + x5 ≥ 3 xi ≥ 0 (i=1,2 ,3,4,5) 2＝ 2 1/5 ＜ 3 17/5＜ 5 7/5 ＜ 2 3=3 解：寫出對(duì)偶問題為： Max Z = 4y1 + 3y . y1 + 2y2 ≤2 ① y1 – y2 ≤3 ② 2y1 +3y2 ≤5 ③ y1 + y2 ≤2 ④ 3y1 +y2 ≤3 ⑤ y1,y2 ≥ 0 已知對(duì)偶問題的最優(yōu)解為 y1 = 4/5, y2 = 3/5, 試應(yīng)用對(duì)偶理論求解原問題?；パa(bǔ)松弛定理即揭示了這一點(diǎn)。 注：證明過程參見教材 59頁性質(zhì) 5證明 對(duì)偶線性規(guī)劃 26 【 討論 】 互補(bǔ)松弛定理也稱 松緊定理 ，它描述了線性規(guī)劃達(dá)到最優(yōu)時(shí)，原問題（或?qū)ε紗栴}）的變量取值和對(duì)偶問題（或原問題）約束松緊之間的對(duì)應(yīng)關(guān)系。 由第一約束條件可知對(duì)偶問題無可行解，則原問題的解無界或無可行解， 由于原問題存在可行解，所以解無界。 若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等 一般是：cx≤yb 對(duì)偶線性規(guī)劃 23 綜上所述：原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系 由原問題與對(duì)偶問題的解的關(guān)系可以判定線性規(guī)劃的解。 設(shè) x和 y分別是 原問題 和對(duì)偶問題的可行解，則必有 cx≤ yb，即原問題的目標(biāo)值小于對(duì)偶問題的目標(biāo)值 321 12168m in yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x????????????0,12416482..212121xxxxxxts 互為對(duì)偶 32121 1216832 yyyxx ????即：對(duì)偶線性規(guī)劃 22 定理 3 （無界性） 若 原問題 (對(duì)偶問題 )為 無界解 ，則其對(duì)偶問題 (原問題 )無可行解 。 定理 1 （對(duì)稱性定理） 167。 321 12168m in yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x??????????0,12416482..212121xxxxxxts 下列的表給出了原問題模型和模型的對(duì)應(yīng)關(guān)系，這些也可以看作是一個(gè)線性規(guī)劃原問題轉(zhuǎn)化為對(duì)偶問題的一般規(guī)律。原問題和對(duì)偶問題總是相依存在的。就象一個(gè)人對(duì)著鏡子會(huì)左右顛倒一樣，原問題與對(duì)偶問題之間存在著嚴(yán)格的對(duì)應(yīng)關(guān)系。 對(duì)偶線性規(guī)劃 9 二、對(duì)偶規(guī)劃的一般數(shù)學(xué)模型 原模型與對(duì)偶模型有很多的內(nèi)在聯(lián)系和相似之處。 Ⅰ Ⅱ 設(shè) 備 1 2 8臺(tái)時(shí) 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產(chǎn)品利潤（萬元） 2 3 ? 新問題的模型 對(duì)偶線性規(guī)劃 6 工廠 改變策略以后 的數(shù)學(xué)模型為： 321 y12y16y8g m i n ??????????????3,2,1,034y2y24yy.. 3121iytsi工廠獲得相應(yīng) 利潤 用戶所付租金最少 對(duì)偶線性規(guī)劃 7 321 12168m in yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x????????????0,12416482..212121xxxxxxts 聯(lián)系在于，它們都是關(guān)于工廠生產(chǎn)經(jīng)營的模型 ,并且使用相同的數(shù)據(jù)； ? 原模型和對(duì)偶模型既有聯(lián)系又有區(qū)別 區(qū)別在于 ,它們所反映的實(shí)質(zhì)內(nèi)容是完全不同的：前者是站在工廠 經(jīng)營者 的立場(chǎng)上追求工廠的 銷售收入最大 ，而后者則是站在談判對(duì)手 的立場(chǎng)上尋求應(yīng)付工廠 租金最少 的策略。 對(duì)偶線性規(guī)劃問題的提出 對(duì)偶線性規(guī)劃 3 一、對(duì)偶線性規(guī)劃問題 某工廠計(jì)劃安排生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品 ， 已知每種單位產(chǎn)品的利潤 、 生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A、 B兩種原材料的消耗 、現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額