【正文】 數(shù) ?j 1/4 5/4 1 0 1/4 1/4 1/2 15/2 0 1 1/2 3/2 y2 y3 24 5 17/2 15/2 0 0 7/2 3/2 最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， maxw*=17/2 – 4 5 3 – 12MinZ=17/2 對(duì)偶線性規(guī)劃 43 應(yīng)用對(duì)偶單純形方法之矩陣法 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 0 0 5 24 15 W’ 1 1 1 2 5 0 2 0 1 6 0 0 0 0 1 ～ 8 0 1 0 15 W’ 1/3 1 2/3 0 5 0 1/3 0 1/6 1 0 0 4 1/3 1/6 ～ 17/2 3/2 0 0 15/2 W’ 1/2 3/2 1 0 15/2 0 1/4 0 0 1 5/4 0 7/2 1/2 1/4 最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， max w*=17/2 Min Z=17/2 對(duì)偶線性規(guī)劃 44 兩種方法的主要 區(qū)別 在于： 而對(duì)偶單純形方法在整個(gè)迭代過(guò)程中，則是始終保持 對(duì)偶問(wèn)題的可行性 即 亦即 , ，也就是全部檢驗(yàn)數(shù) ≤0，最后達(dá)到全部右邊項(xiàng)所有負(fù)分量逐步變?yōu)槿坑疫呿?xiàng)≥0,即滿足原問(wèn)題的可行性時(shí)為止。 CyA ? 0? yAC 所以 ,對(duì)偶單純形方法實(shí)質(zhì) 就是在保證對(duì)偶問(wèn)題可行的條件下向原問(wèn)題可行的方向迭代。 ABCC B 1 0? yAC 原始單純形方法在整個(gè)迭代過(guò)程中，始終是保持 原問(wèn)題的可行性 ，最后達(dá)到檢驗(yàn)數(shù) 即 即 maxZ取得最優(yōu)值時(shí)為止。 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ì)偶問(wèn)題的解可行為止 相當(dāng)于：即直到原問(wèn)題的解可行為止 對(duì)偶線性規(guī)劃 45 【 例 】 用對(duì)偶單純形方法解下述線性規(guī)劃問(wèn)題 原問(wèn)題是： 原問(wèn)題的標(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ì)偶單純形方法的解題過(guò)程一般分為四步 （ 1） 寫(xiě)出與已有的初始基 B對(duì)應(yīng)的初始單純形表 。 根據(jù)模型的標(biāo)準(zhǔn)型 ， 若右邊項(xiàng)的數(shù)字都為非負(fù) ， 且檢驗(yàn)數(shù)都為非正 ， 則已得到最優(yōu)解 ， 計(jì)算結(jié)束；否則 ， 若右邊項(xiàng)中至少有一個(gè)負(fù)分量 ， 且檢驗(yàn)數(shù)也仍然非正 ， 則進(jìn)行如下計(jì)算 。 （ 2） 確定出基變量 。 若有： 則以對(duì)應(yīng)的變量 xr為出基變量 。 ? ? riii bBbBbB )(0)()(m i n 111 ??（ 3） 確定入基變量 。 在單純形表中觀察 xr所在行的各系數(shù) arj，若所有的 arj≥0， 則無(wú)可行解 ， 停止計(jì)算；否則若存在： rkkkrjrjjjj azcaazc ??????????? ?? 0m i n? ， 則以 xk為入基變量 。 （ 4） 以 ark為主元按原始單純形方法的迭代方法進(jìn)行迭代 ，得到新的單純形表。 對(duì)偶線性規(guī)劃 48 ? 對(duì)偶單純形方法的顯著優(yōu)點(diǎn)： （ 1） 初始解可以是不可行解 ， 當(dāng)檢驗(yàn)數(shù)都非正時(shí) ， 即可以進(jìn)行基的變換 ， 這時(shí)不需要引進(jìn)人工變量 ， 因此就簡(jiǎn)化了計(jì)算 。 （ 2） 對(duì)于變量個(gè)數(shù)多于約束方程個(gè)數(shù)的線性規(guī)劃問(wèn)題 ，采用對(duì)偶單純形法計(jì)算量較少 。 因此對(duì)于 變量較少 、 約束較多 的線性規(guī)劃問(wèn)題 , 可以先將它轉(zhuǎn)化成對(duì)偶問(wèn)題 ， 然后用對(duì)偶單純形方法求解 。 對(duì)偶線性規(guī)劃 49 【 另例 】 用對(duì)偶單純形方法解下述線性規(guī)劃問(wèn)題 原問(wèn)題是： 原問(wèn)題的標(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ī)劃問(wèn)題 ????????????0,3m i n21212121xxxxxxxxz942 對(duì)偶線性規(guī)劃 52 影子價(jià)格 從對(duì)偶問(wèn)題的基本性質(zhì)可以看出，在單純形法的每步迭代中有目標(biāo)函數(shù) ?????? miiinjjj ybxcz11 此時(shí)的估價(jià)不是市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中的貢獻(xiàn)而作的估價(jià)。 此時(shí)的定價(jià)區(qū)別于市場(chǎng)價(jià)格稱為 影子價(jià)格。 對(duì)偶線性規(guī)劃 第 i種資源的估價(jià) 第 i種資源的擁有量 ?影子價(jià)格的意義 市場(chǎng)價(jià)格 主要隨市場(chǎng)供求變化；而它的 影子價(jià)格 有賴于 資源 的利用情況，是未知數(shù)。 由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。同樣一種資源，若它們?cè)诓煌髽I(yè)中發(fā)揮的作用不同，對(duì)這種資源所做的估價(jià)也不同，即影子價(jià)格也不同。 即：生產(chǎn)任務(wù)、結(jié)構(gòu)的改變會(huì)影響影子價(jià)格。 對(duì)偶線性規(guī)劃 54 影子價(jià)格是一種邊際價(jià)格。 iiybz ??? yi代表 bi每增加一個(gè)單位，目標(biāo)函數(shù) z的增量 maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 +1 （ 1） z*=42 不變， A的邊際價(jià)格為 0 +1 （ 2） x*=(10/3,13/2) z*=，B的 邊際價(jià)格為 +1 （ 3） x*=(13/3,6) z*=43， C的 邊際價(jià)格為 1 x1 =8 2x2 =12 3x1 +4 x2 =36 x1 x2 4 8 12 3 6 9 0 A B(8,3) C(4,6) D ???miii ybz1對(duì)偶線性規(guī)劃 影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺，影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺。 55 資源的影子價(jià)格實(shí)際上是一種機(jī)會(huì)成本。 市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)的決策者應(yīng)買進(jìn)資源用于擴(kuò)大再生產(chǎn)； 當(dāng)某種資源的市場(chǎng)價(jià)格高于企業(yè)影子價(jià)格時(shí)，企業(yè)的決策者應(yīng)把已有資源賣掉，以其獲得更大的利潤(rùn)。 隨著資源的買進(jìn)和賣出，它的影子價(jià)格也隨之發(fā)生變化。 生產(chǎn)過(guò)程中，如果某種資源 bi未得到充分利用時(shí)，該種資源的影子價(jià)格為 0； 某種資源的影子價(jià)格不為 0時(shí)，表明該種資源已經(jīng)耗盡。 由對(duì)偶互補(bǔ)松弛定理即可說(shuō)明 對(duì)偶線性規(guī)劃 對(duì)偶線性規(guī)劃 【 例 】 某工廠準(zhǔn)備安排甲、乙、丙三種產(chǎn)品 的生產(chǎn)，需要消耗原材料 A和 B兩種資源。為了確定利潤(rùn)最大的生產(chǎn)計(jì)劃，建立下列線性規(guī)劃： 1 2 31 2 31 2 31 2 3m a x 3 56 3 5 45 . . 3 4 5 30 0z x x xx x x As t x x x Bx x x? ? ?? ? ???? ? ??? ??（ 原 材 料 的 約 束 ）（ 原 材 料 的 約 束 ）， ， 其中 x1,x2,x3表示甲、乙、丙的產(chǎn)量，經(jīng)計(jì)算得到下列最終單純形表（ x4,x5是松弛變量）。 57 對(duì)偶線性規(guī)劃 根據(jù)以上資料，回答下列問(wèn)題： （ 1）寫(xiě)出對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值； （ 2）求出原材料 B的影子價(jià)格。若原材料 B不夠，可到市場(chǎng)上購(gòu)買，市場(chǎng)價(jià)格為 /單位。問(wèn)是否要購(gòu)進(jìn)？ 解：（ 1）根據(jù)對(duì)偶問(wèn)題的基本性質(zhì) 7，最終單純形表中原問(wèn)題加入的 松弛變量檢驗(yàn)數(shù)的相反數(shù) 對(duì)應(yīng)于 對(duì)偶問(wèn)題的最優(yōu)解 。 所以，對(duì)偶問(wèn)題的最優(yōu)解是 **120 。 1yy??最優(yōu)目標(biāo)函數(shù)值是 ** 30WZ??（ 2）原材料 B的影子價(jià)格是 1，所以以 /單位的價(jià)格購(gòu)進(jìn)原材料 B是值得的。 58 靈敏度分析 ，是指對(duì)系統(tǒng)或事物因周圍條件變化所表現(xiàn)出的敏感性程度的分析。 在前面講的線性規(guī)劃問(wèn)題中，通常都是假定問(wèn)題中的 aij， bi， cj系數(shù)是已知的常數(shù) ,但實(shí)際上這些參數(shù)都是一些估計(jì)或預(yù)測(cè)的數(shù)字。 在現(xiàn)實(shí)中，如果市場(chǎng)條件變化， cj值就會(huì)發(fā)生變化；如果工藝技術(shù)條件改變，則 aij就會(huì)變化；如果資源的可用量發(fā)生變化，則 bi也會(huì)發(fā)生變化。 靈敏度分析 問(wèn)題： 參數(shù)發(fā)生變化時(shí)，問(wèn)題的最優(yōu)解會(huì)有什么變化？ 參數(shù)多大的范圍內(nèi)變化時(shí) ,原最優(yōu)解保持不變。 對(duì)偶線性規(guī)劃 59 解決方法： 當(dāng)參數(shù)變化時(shí)，用單純形法從頭計(jì)算，看最