【正文】 值Cj檢驗(yàn)數(shù)比值x5x4x3x2x100012 1 5 / 25 /41001 5 /2 1 /21 /40017 /23 /2 1 /40103 /2x2x1x312+ l0 1 /2 1 /4000 1 7 /22+l 1 0 0 0 0 2+l 1 17/2 l 0 0 1/4 1/2 17/27/2l 0 0 0 1/41/4l 1/2+1/2l 即： 1≤ l≤?時(shí)，最優(yōu)解不變； 對(duì)偶線性規(guī)劃 二、分析 bi變化的影響 bi的變化 在實(shí)際問(wèn)題中表明可用資源的數(shù)量發(fā)生變化，其變化 △ b反映到最終單純形表上 只引起基變量列數(shù)字變化 △ b*。 常數(shù)項(xiàng) bi的改變量 系數(shù) aij的改變量 目標(biāo)函數(shù)系數(shù) cj的改變量 對(duì)偶線性規(guī)劃 此公式是單純形法利用公式求解的推導(dǎo)結(jié)果 ! 61 解的情況判定表 原問(wèn)題 對(duì)偶問(wèn)題 結(jié)論或繼續(xù)計(jì)算的步驟可行解 可行解 仍為問(wèn)題最優(yōu)解可行解 非可行解 用單純法繼續(xù)迭代求最優(yōu)解非可行解 可行解 用對(duì)偶單純法繼續(xù)迭代求最優(yōu)解非可行解 非可行解 引進(jìn)人工變量，編制新的單純形表重新計(jì)算對(duì)偶線性規(guī)劃 62 一、分析 cj變化的影響 目標(biāo)函數(shù)中的系數(shù) cj的變化僅僅影響到檢驗(yàn)數(shù) (cjzi)的變化。 在前面講的線性規(guī)劃問(wèn)題中，通常都是假定問(wèn)題中的 aij， bi， cj系數(shù)是已知的常數(shù) ,但實(shí)際上這些參數(shù)都是一些估計(jì)或預(yù)測(cè)的數(shù)字。 由對(duì)偶互補(bǔ)松弛定理即可說(shuō)明 對(duì)偶線性規(guī)劃 對(duì)偶線性規(guī)劃 【 例 】 某工廠準(zhǔn)備安排甲、乙、丙三種產(chǎn)品 的生產(chǎn)，需要消耗原材料 A和 B兩種資源。同樣一種資源，若它們?cè)诓煌髽I(yè)中發(fā)揮的作用不同，對(duì)這種資源所做的估價(jià)也不同，即影子價(jià)格也不同。 （ 4） 以 ark為主元按原始單純形方法的迭代方法進(jìn)行迭代 ，得到新的單純形表。 CyA ? 0? yAC 所以 ,對(duì)偶單純形方法實(shí)質(zhì) 就是在保證對(duì)偶問(wèn)題可行的條件下向原問(wèn)題可行的方向迭代。 對(duì)偶線性規(guī)劃 28 【 又例 】 應(yīng)用如上關(guān)系求解線性規(guī)劃問(wèn)題 例 5 已知線性規(guī)劃問(wèn)題 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ì)偶問(wèn)題為： Max Z = 4y1 + 3y . y1 + 2y2 ≤2 ① y1 – y2 ≤3 ② 2y1 +3y2 ≤5 ③ y1 + y2 ≤2 ④ 3y1 +y2 ≤3 ⑤ y1,y2 ≥ 0 已知對(duì)偶問(wèn)題的最優(yōu)解為 y1 = 4/5, y2 = 3/5, 試應(yīng)用對(duì)偶理論求解原問(wèn)題。 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等 一般是：cx≤yb 對(duì)偶線性規(guī)劃 23 綜上所述：原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系 由原問(wèn)題與對(duì)偶問(wèn)題的解的關(guān)系可以判定線性規(guī)劃的解。原問(wèn)題和對(duì)偶問(wèn)題總是相依存在的。 對(duì)偶線性規(guī)劃問(wèn)題的提出 對(duì)偶線性規(guī)劃 3 一、對(duì)偶線性規(guī)劃問(wèn)題 某工廠計(jì)劃安排生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品 ， 已知每種單位產(chǎn)品的利潤(rùn) 、 生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A、 B兩種原材料的消耗 、現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額如下表所示： 【 例 1】 Ⅰ Ⅱ 設(shè) 備 1 2 8臺(tái)時(shí) 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產(chǎn)品利潤(rùn)（萬(wàn)元） 2 3 ? 原問(wèn)題的策略 : ? 問(wèn)應(yīng)如何安排生產(chǎn)才能使工廠獲利最大？ ? 現(xiàn)在的策略 : ? 假設(shè)不生產(chǎn) Ⅰ 、 Ⅱ 產(chǎn)品 ,而是計(jì)劃將現(xiàn)有資源出租或出售 ,從而獲得利潤(rùn) ,這時(shí)需要考慮如何定價(jià)才合理 ? 對(duì)偶線性規(guī)劃 4 21 32 xxf ??m a x????????????0x,x12x4 16 x48x2x.212121 設(shè) x x2分別表示計(jì)劃生產(chǎn) 產(chǎn)品 Ⅰ 、 Ⅱ 的單位數(shù)量，由題意 原問(wèn)題的模型 為： 工廠獲得最大利潤(rùn) 符合資源限制 Ⅰ Ⅱ 設(shè) 備 1 2 8臺(tái)時(shí) 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產(chǎn)品利潤(rùn)（萬(wàn)元） 2 3 ? 原問(wèn)題的模型 對(duì)偶線性規(guī)劃 5 改變策略后，需要考慮如何給資源定價(jià)的問(wèn)題！ 設(shè) y y2 、 y3分別表示出租單位設(shè)備 臺(tái)時(shí)的租金和出售單位原材料 A、 B的利潤(rùn) . y1+4y2≥2 ， 2y1+4y3≥3 則： ? 工廠出租設(shè)備 、 原材料的租金要大于生產(chǎn)的利潤(rùn)才合算 。 對(duì)偶線性規(guī)劃 8 所謂 對(duì)偶規(guī)劃 ，就是與線性規(guī)劃原問(wèn)題相對(duì)應(yīng)并使用同一組數(shù)據(jù)按照特定方法形成的另一種反映不同性質(zhì)問(wèn)題的線性規(guī)劃模型。 原問(wèn)題線性規(guī)劃模型 對(duì)偶線性規(guī)劃模型 對(duì)偶線性規(guī)劃 11 原問(wèn)題為 maxZ的線性規(guī)劃問(wèn)題對(duì)偶關(guān)系表 原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題 （或原問(wèn)題） 目標(biāo)函數(shù)最大化 (maxZ) n 個(gè)變量 m 個(gè)約束 約束條件限定向量（右邊項(xiàng)） 目標(biāo)函數(shù)價(jià)值向量（系數(shù)） ≥ 0 變量 ≤ 0 ≥ 無(wú)限制 約束 ≤ ＝ 目標(biāo)函數(shù)最小化（ minS ） n 個(gè)約束 m 個(gè)變量 目標(biāo)函數(shù)價(jià)值向量（系數(shù)） 約束條件限定向量（右邊項(xiàng)） ≥ 約束 ≤ ≤ 0 ＝ 變量 ≥ 0 無(wú)限制 同號(hào) 反號(hào) 對(duì)偶線性規(guī)劃 12 原問(wèn)題 對(duì)偶問(wèn)題 目標(biāo)函數(shù) max 目標(biāo)函數(shù) min ???????無(wú)約束個(gè)量變00n件條束約個(gè)??????????n????????個(gè)件條束約 m量變無(wú)約束個(gè)?????????00m?原問(wèn)題 (maxZ)與對(duì)偶之關(guān)系 原問(wèn)題 (maxZ)口訣 : 約束決定變量是反號(hào) 原問(wèn)題 (maxZ)口訣 : 變量決定約束是同號(hào) 對(duì)偶線性規(guī)劃 13 【 解 】 由原模型 三個(gè)約束條件確定 對(duì)偶模型有 三個(gè)變量 y1,y2,y3 （還可依對(duì)偶問(wèn)題寫出原問(wèn)題） 【 例 1】 寫出下列問(wèn)題的對(duì)偶問(wèn)題： 變量決定約束是同號(hào) ,約束決定變量是反號(hào) max Z=2x1+x2 5x2 ≤ 15 6x1 +2x2≥ 24 x1+ x2 ＝ 5 x1 ≥ 0 , x2 ≤0 min w=15y1+24y2+5y3 6y2+y3 ≥ 2 . 原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最大化 ( m ax Z )n 個(gè)變量m 個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）≥ 0變量 ≤ 0 ≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最小化（ m i nS ）n 個(gè)約束m 個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量（右邊項(xiàng)）≥約束 ≤≤ 0＝變量 ≥ 0 無(wú)限制原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最大化個(gè)變量個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）≥變量 ≤≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最小化（ ）個(gè)約束個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量（右邊項(xiàng)）≥約束 ≤≤＝變量 ≥無(wú)限制y1 ≥ 0, y2 ≤ 0, y3 無(wú)約束 5y1 +2y2 +y3 ≤ 1 對(duì)偶線性規(guī)劃 14 原問(wèn)題為 minS的線性規(guī)劃問(wèn)題對(duì)偶關(guān)系表 原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題 （或原問(wèn)題） 目標(biāo)函數(shù)最小化 (minS) n 個(gè)變量 m 個(gè)約束 約束條件限定向量（右邊項(xiàng)） 目標(biāo)函數(shù)價(jià)值向量 ≥ 0 變量 ≤ 0 ≥ 無(wú)限制 約束 ≤ ＝ 目標(biāo)函數(shù)最大化（ maxZ ） n 個(gè)約束 m 個(gè)變量 目標(biāo)函數(shù)價(jià)值向量（系數(shù)） 約束條件限定向量 ≤ 約束 ≥ ≥ 0 ＝ 變量 ≤ 0 無(wú)限制 同號(hào) 反號(hào) 對(duì)偶線性規(guī)劃 15 原問(wèn)題 對(duì)偶問(wèn)題 目標(biāo)函數(shù) min 目標(biāo)函數(shù) max ???????無(wú)約束個(gè)量變00n件條束約個(gè)????????n????????個(gè)件條束約 m量變無(wú)約束個(gè)???????00m?原問(wèn)題 (minS) 與對(duì)偶之關(guān)系： 原問(wèn)題 (minS)口訣 : 約束決定變量是同號(hào) 原問(wèn)題 (minS)口訣 : 變量決定約束是反號(hào) 對(duì)偶線性規(guī)劃 16 【 解 】 由原模型三個(gè)約束條件確定對(duì)偶模型有三個(gè)變量 y1,y2,y3 3 2 1 3 4 max y y y Z ? ? . 1 2 3 2 1 ? y y 2y 3 3 2 1 ? ? y 4y 4 2 3 2 1 ? ? ? y y y （還可依對(duì)偶問(wèn)題寫出原問(wèn)題） 【 例 2】 寫出下列問(wèn)題的對(duì)偶問(wèn)題： 3 2 1 4 3 Min x x x S ? ? . 1 3 2 1 ? ? ? x x 2x 4 2 3 3 2 1 ? ? ? x x x 3 2 3 1 ? ? x x x1??,x2??,x3無(wú)約束 變量決定約束是反號(hào) ,約束決定變量是同號(hào) 0 1 ? y ， 0 2 ? y 3 無(wú)約束 y ， 原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最小化 ( m i nS )n 個(gè)變量m 個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量≥ 0變量 ≤ 0 ≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最大化（ m ax Z ）n 個(gè)約束m 個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量≤約束 ≥≥ 0＝變量 ≤ 0無(wú)限制原問(wèn)題原問(wèn)題 （或?qū)ε紗?wèn)題） 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （或原問(wèn)題）目標(biāo)函數(shù)最小化個(gè)變量個(gè)約束約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量≥變量 ≤≥無(wú)限制約束 ≤＝目標(biāo)函數(shù)最大化（ ）個(gè)約束個(gè)變量目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量≤約束 ≥≥＝變量 ≤無(wú)限制對(duì)偶線性規(guī)劃 17 練習(xí) ： 試求下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 3 2 1 3 4 2 max x x x Z ? ? . 10 3 2 1 ? ? x x x 5 3 4 3 2