第二章 對(duì)偶理論和靈敏度

1、1 第二章 對(duì)偶理論和靈敏度分析 2 第一節(jié) 單純形法的矩陣描述 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為： max . 0 zCX AX st X b 5210 3 22 1 2max 543 542 41 5421 ,jx xxx xxx xx s.t xxxxz j 1 B XB b 1 BNN ZC B bX 1 NNB CC B N 1 B CC B A 4 1 1 1 min0 i j i j i B b B P B P 第二節(jié) 改進(jìn)單純形法 w改進(jìn)單純形法的出發(fā)點(diǎn)改進(jìn)單純形法的出發(fā)點(diǎn)：由于單純形法的迭代 過(guò)程中基矩陣的逆矩陣求出后，單純形表上的 其它行和列的數(shù)字也隨著可確定，不必要計(jì)算 很多與下一步

2、迭代無(wú)關(guān)的數(shù)字，提高計(jì)算效率， 減少計(jì)算機(jī)求解所需的存儲(chǔ)單元。 5 改進(jìn)單純形法的計(jì)算步驟 6 7 例1 用改進(jìn)單純形法求解 12345 123 14 25 12345 max23000 28 416 . 412 ,0 zxxxxx xxx xx st xx x x x x x 1 B XB b 1 BNN ZC B bX 1 NNB CC B N 1 B CC B A 1 1 1 min0 i j i j i B b B P B P 8 習(xí)題2.1 9 123 123 13 123 max623 222 .44 ,0 zxxx xxx st xx x x x 123 1234 135 123

3、45 max623 222 .44 ,0 zxxx xxxx st xxx x x x x x 第三節(jié)第三節(jié) 對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的提出 10 例例1：某工廠在計(jì)劃期內(nèi)安排生產(chǎn)：某工廠在計(jì)劃期內(nèi)安排生產(chǎn) 、兩種產(chǎn)品兩種產(chǎn)品，已知生產(chǎn)單位已知生產(chǎn)單位 產(chǎn)品所需的設(shè)備臺(tái)時(shí)、產(chǎn)品所需的設(shè)備臺(tái)時(shí)、A、B兩種兩種 原材料的消耗如下表所示：原材料的消耗如下表所示： 該工廠每生產(chǎn)一件產(chǎn)品該工廠每生產(chǎn)一件產(chǎn)品可獲利可獲利2 元，每元，每生產(chǎn)一件產(chǎn)品生產(chǎn)一件產(chǎn)品可獲利可獲利3元，元， 問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利 最多？最多？ 資源限制資源限制 設(shè)設(shè) 備備128 臺(tái)時(shí)臺(tái)時(shí) 原料原料

4、 A4016 千克千克 原料原料 B0412 千克千克 單位產(chǎn)品獲利單位產(chǎn)品獲利2 元元3 元元 現(xiàn)在從另一角度來(lái) 討論這個(gè)問(wèn)題。假 設(shè)該工廠的決策者 決定不生產(chǎn)產(chǎn)品， 而將所有資源出租 或外售。這時(shí)工廠 的決策者就要考慮 給每種資源如何定 價(jià)的問(wèn)題。 原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系 非對(duì)稱形式線性規(guī)劃問(wèn)題的處理 w若原問(wèn)題的第i個(gè)約束條件是等式約束， 則對(duì)偶問(wèn)題中相應(yīng)于它的變量無(wú)非負(fù)要 求；反之，若原問(wèn)題的第i個(gè)變量無(wú)非負(fù) 要求，則對(duì)偶問(wèn)題中相應(yīng)于它的約束條 件是等式約束。 12 13 12 12 12 12 max23 215 .4320 ,0 zxx xx stxx x x 0 2034 152

5、 . 32max 1 21 21 21 x xx xx ts xxz 0, 2034 152 . 32max 21 21 21 21 xx xx xx ts xxz 0, 0 2034 152 . 32max 21 21 21 21 xx xx xx ts xxz 14 例 求下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 無(wú)約束,0,0, 2099912 85376 53 . 432max 4321 4321 4321 4321 4321 xxxx xxxx xxxx xxxx ts xxxxz 例3 試求下述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 1234 1234 134 234 1234 min235 35 224 .

6、6 0;,0; zxxxx xxxx xxx st xxx xx xx 無(wú)約束 2.3 17 0, 564 373 2532 . 422min 321 321 321 321 321 xxx xxx xxx xxx ts xxxz 原問(wèn)題與對(duì)偶問(wèn)題對(duì)應(yīng)關(guān)系的一般形式 0 . max X bAX ts CXz 0, . min 21 2211 22222112 11221111 2211 m nmmnnn mm mm mm yyy cyayaya cyayaya cyayaya ts ybybybw 0 . min Y CYA ts Ybw 0, . max 21 2211 22222121 1

7、1212111 2211 n mnmnmm nn nn nn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcz 4.2 對(duì)偶問(wèn)題的基本性質(zhì) 1.對(duì)稱性對(duì)稱性對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題 2.弱對(duì)偶性弱對(duì)偶性若若是原問(wèn)題的可行是原問(wèn)題的可行 解，解，是對(duì)偶問(wèn)題的可行解，則存是對(duì)偶問(wèn)題的可行解，則存 在在 X Y bYXC 3.無(wú)界性無(wú)界性若原問(wèn)題（對(duì)偶問(wèn)題）為若原問(wèn)題（對(duì)偶問(wèn)題）為 無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題） 無(wú)可行解。無(wú)可行解。 此問(wèn)題的性質(zhì)不存在逆。此問(wèn)題的性質(zhì)不存在逆。 0, 1 1 . min 21 21 21

8、 21 xx xx xx ts xxw 0, 1 1 . max 21 21 21 21 yy yy yy ts yyz 4.可行解是最優(yōu)解時(shí)的性質(zhì)可行解是最優(yōu)解時(shí)的性質(zhì) 設(shè)設(shè)是原問(wèn)題的可行解，是原問(wèn)題的可行解，是對(duì)偶問(wèn)是對(duì)偶問(wèn) 題的可行解，當(dāng)題的可行解，當(dāng)時(shí)，時(shí)，是最是最 優(yōu)解。優(yōu)解。 X Y bYXC YX , 5.對(duì)偶定理對(duì)偶定理若原問(wèn)題有最優(yōu)解，若原問(wèn)題有最優(yōu)解， 那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo) 函數(shù)值相等。函數(shù)值相等。 例4 已知線性規(guī)劃問(wèn)題 12 123 123 123 max 2 21 ,0 zxx xxx xxx x xx 試用對(duì)偶理論證明上述線性

9、規(guī)劃問(wèn)題無(wú) 最優(yōu)解。 6.互補(bǔ)松弛定理互補(bǔ)松弛定理若若分別是原問(wèn)題分別是原問(wèn)題 和對(duì)偶問(wèn)題的可行解，那么和對(duì)偶問(wèn)題的可行解，那么和和 ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)為最優(yōu)解。為最優(yōu)解。 YX , 0 S XY 0Y X S YX , max ,0 S S zCX AXXb X X min ,0 S S wYb YA YC Y Y 原問(wèn)題與對(duì)偶問(wèn)題對(duì)應(yīng)關(guān)系的一般形式 0 . max X bAX ts CXz 0, . min 21 2211 22222112 11221111 2211 m nmmnnn mm mm mm yyy cyayaya cyayaya cyayaya ts ybybybw 0 .

10、 min Y CYA ts Ybw 0, . max 21 2211 22222121 11212111 2211 n mnmnmm nn nn nn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcz 例5 已知線性規(guī)劃問(wèn)題 12345 12345 12345 min23523 234 233 0,1,2,5 j wxxxxx xxxxx xxxxx xj 已知其對(duì)偶問(wèn)題的最優(yōu)解為 * 12 4/5,3/5,5yyz 試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。 7.原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng) 其對(duì)偶問(wèn)題的一個(gè)基解，對(duì)應(yīng)關(guān)系其對(duì)偶問(wèn)題的一個(gè)基解，對(duì)

11、應(yīng)關(guān)系 見(jiàn)下表。見(jiàn)下表。 27 max ,0 S S zCX AXXb X X min ,0 S S wYb YA YC Y Y 補(bǔ)充例題 123 123 123 123 max61413 1 224 2 2460 ,0 zxxx xxx xxx x x x 該線性規(guī)劃問(wèn)題的 最終單純形表如下， 求對(duì)偶問(wèn)題的最優(yōu) 解。 第五節(jié)第五節(jié) 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 的經(jīng)濟(jì)解釋的經(jīng)濟(jì)解釋 對(duì)偶問(wèn)題的解的經(jīng)濟(jì)意義：在其它條件不對(duì)偶問(wèn)題的解的經(jīng)濟(jì)意義：在其它條件不 變的情況下，單位資源變化所引起的目標(biāo)函變的情況下，單位資源變化所引起的目標(biāo)函 數(shù)的最優(yōu)值的變化。數(shù)的最優(yōu)值的變化。 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋對(duì)偶問(wèn)題的經(jīng)濟(jì)解

12、釋 某工廠在計(jì)劃期內(nèi)要 安排、兩種產(chǎn)品 的生產(chǎn)，已知生產(chǎn)單 位產(chǎn)品所需的設(shè)備臺(tái) 時(shí)及A、B兩種原材 料的消耗以及資源的 限制，如下表： 問(wèn)題：如何安排生產(chǎn) 才能使工廠獲利最多？ 30 資源限制資源限制 設(shè)設(shè) 備備128 臺(tái)時(shí)臺(tái)時(shí) 原料原料 A4016 千克千克 原料原料 B0412 千克千克 單位產(chǎn)品獲利單位產(chǎn)品獲利2 元元3 元元 0, 124 164 82 . 32max 21 2 1 21 21 xx x x xx ts xxz 0, 342 24 . 12168min 321 31 21 321 yyy yy yy ts yyyw 31 3 4 8 4 0 x2 x1 B(4.25,1

13、.875)Z=14.125 A(4,2)Z=14 C(4,2.5)Z=15.5 C AB 0 124 164 82 32max 21 2 1 21 21 ,xx x x xx s.t xxz 的值代表對(duì)第的值代表對(duì)第種資源的估價(jià)。種資源的估價(jià)。 這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存 在的一種特殊價(jià)格，稱它為在的一種特殊價(jià)格，稱它為“影子價(jià)影子價(jià) 格格”(ShadowpriceorDualprice)。 i yi 影子價(jià)格的性質(zhì) u影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺 u影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺 u如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資 源的影

14、子價(jià)格一定等于0 34 影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。在完全影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。在完全 市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng) 價(jià)格低于企業(yè)影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)價(jià)格低于企業(yè)影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn) 該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的 市場(chǎng)價(jià)格高于企業(yè)影子價(jià)格時(shí)，則企業(yè)市場(chǎng)價(jià)格高于企業(yè)影子價(jià)格時(shí)，則企業(yè) 的決策者應(yīng)把已有資源賣掉。的決策者應(yīng)把已有資源賣掉。 第六節(jié) 對(duì)偶單純形法 對(duì)偶單純形法的基本思想：保持對(duì)偶問(wèn)題 的解是可行解，原問(wèn)題在非可行解的基礎(chǔ)上， 通過(guò)逐步迭代達(dá)到基可行解，最終得到最優(yōu)解 。 在單純形表中進(jìn)行迭代時(shí)，在

15、b 列中得到 的是原問(wèn)題的可行解，而在檢驗(yàn)數(shù)行得到的是 對(duì)偶問(wèn)題的基解。通過(guò)逐步迭代，當(dāng)在檢驗(yàn)數(shù) 行得到對(duì)偶問(wèn)題的解也是基可行解時(shí)，對(duì)偶問(wèn) 題得到最優(yōu)解。 例題 12 12 12 12 max 22 .1 ,0 zxx xx stxx x x 123 124 12 22 .1 ,0 xxx stxxx x x 例6 用對(duì)偶單純形法求解 123 123 123 123 min234 23 234 ,0 wxxx xxx xxx x xx 對(duì)偶單純形法的計(jì)算步驟 目標(biāo)函數(shù)求極大值目標(biāo)函數(shù)求極大值 w初始單純形表：檢驗(yàn)數(shù)非初始單純形表：檢驗(yàn)數(shù)非 正，常數(shù)項(xiàng)若非負(fù)，已是正，常數(shù)項(xiàng)若非負(fù)，已是 最優(yōu)解，

16、若常數(shù)項(xiàng)有負(fù)分最優(yōu)解，若常數(shù)項(xiàng)有負(fù)分 量，轉(zhuǎn)入下一步。量，轉(zhuǎn)入下一步。 w換出變量：值為負(fù)的變量換出變量：值為負(fù)的變量 w換入變量：檢查出基變量換入變量：檢查出基變量 所在行的系數(shù)，若都為非所在行的系數(shù)，若都為非 負(fù)，則無(wú)可行解。若存在負(fù)，則無(wú)可行解。若存在 系數(shù)小于零，計(jì)算檢驗(yàn)數(shù)系數(shù)小于零，計(jì)算檢驗(yàn)數(shù) 與系數(shù)的比值，取最小值與系數(shù)的比值，取最小值 對(duì)應(yīng)的系數(shù)為主元素。對(duì)應(yīng)的系數(shù)為主元素。 w迭代，重復(fù)上述步驟。迭代，重復(fù)上述步驟。 目標(biāo)函數(shù)求極小值目標(biāo)函數(shù)求極小值 w初始單純形表：檢驗(yàn)數(shù)初始單純形表：檢驗(yàn)數(shù)非非 負(fù)負(fù)，常數(shù)項(xiàng)若非負(fù)，已是，常數(shù)項(xiàng)若非負(fù)，已是 最優(yōu)解，若常數(shù)項(xiàng)有負(fù)分最優(yōu)解，若常

17、數(shù)項(xiàng)有負(fù)分 量，轉(zhuǎn)入下一步。量，轉(zhuǎn)入下一步。 w換出變量：值為負(fù)的變量換出變量：值為負(fù)的變量 w換入變量：檢查出基變量換入變量：檢查出基變量 所在行的系數(shù)，若都為非所在行的系數(shù)，若都為非 負(fù)，則無(wú)可行解。若存在負(fù)，則無(wú)可行解。若存在 系數(shù)小于零，計(jì)算檢驗(yàn)數(shù)系數(shù)小于零，計(jì)算檢驗(yàn)數(shù) 與系數(shù)的比值，取與系數(shù)的比值，取絕對(duì)值絕對(duì)值 的最小值對(duì)應(yīng)的系數(shù)為主的最小值對(duì)應(yīng)的系數(shù)為主 元素。元素。 w迭代，重復(fù)上述步驟。迭代，重復(fù)上述步驟。 對(duì)偶單純形法的優(yōu)點(diǎn)與局限 優(yōu)點(diǎn)優(yōu)點(diǎn) w初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就 可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因 此可以簡(jiǎn)化計(jì)算。 w在靈敏度分析及求解整

18、數(shù)規(guī)劃的割平面法中，有時(shí) 需要對(duì)偶單純形法，這樣可使問(wèn)題的處理簡(jiǎn)化。 局限：局限： 對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可 行基，因而這種方法在求解線性規(guī)劃問(wèn)題時(shí)很少單 獨(dú)應(yīng)用。 第七節(jié) 靈敏度分析 w當(dāng)線性規(guī)劃的系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)， 已求得的線性規(guī)劃問(wèn)題最優(yōu)解會(huì)有什么變化； w或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃 問(wèn)題的最優(yōu)解或最優(yōu)基保持不變。 42 43 原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟 可行解可行解 可行解可行解表中的解仍為最優(yōu)解表中的解仍為最優(yōu)解 可行解可行解 非可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解用單純形法繼續(xù)迭代求最優(yōu)解 非可行

19、解非可行解 可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解 非可行解非可行解 非可行解非可行解引進(jìn)人工變量，編制新的單純形表，求最優(yōu)解引進(jìn)人工變量，編制新的單純形表，求最優(yōu)解 7.1 資源數(shù)量變化的分析 44 第一章例1中，求使最優(yōu)基保持不變的第二個(gè) 約束條件b2的變化范圍 b2。 。 資資 源源 限限 制制 設(shè)設(shè) 備備 128臺(tái)臺(tái) 時(shí)時(shí) 原原 料料A 4016千千 克克 原原 料料B0412千千 克克 單單 位位 產(chǎn)產(chǎn) 品品 獲獲 利利 2元元 3元元 0, 124 164 82 . 32max 21 2 1 21 21 xx x x xx ts xxz 45 例7

20、 46 從例1的最優(yōu)單純形表，每設(shè)備臺(tái)時(shí)的影子價(jià) 格為1.5元。若該廠又從其它處抽調(diào)4臺(tái)時(shí)用 于生產(chǎn)產(chǎn)品和 。求這時(shí)該廠生產(chǎn)產(chǎn)品 和的最優(yōu)方案。 資資 源源 限限 制制 設(shè)設(shè) 備備 128臺(tái)臺(tái) 時(shí)時(shí) 原原 料料A 4016千千 克克 原原 料料B0412千千 克克 單單 位位 產(chǎn)產(chǎn) 品品 獲獲 利利 2元元 3元元 0, 124 164 82 . 32max 21 2 1 21 21 xx x x xx ts xxz 47 -4 4 4 48 -4 4 4 7.2 目標(biāo)函數(shù)中價(jià)值系數(shù)的變化分析 w非基變量的價(jià)值系數(shù)變化分析 w基變量的價(jià)值系數(shù)變化分析 49 例8 以例1的最優(yōu)表為例。設(shè)基變量

21、的系數(shù)變化 ，在原最優(yōu)解不變的條件下，確定 的變 化范圍。 50 2 x 2 c 2 c 3+ 2 c 3+ 2 c 7.3 技術(shù)系數(shù)的變化 例例9分析在原計(jì)劃中是否應(yīng)該安排一種新產(chǎn)品。以例1 為例，設(shè)該廠除了生產(chǎn)產(chǎn)品1和2 外，現(xiàn)有一種新產(chǎn)品 3，每件需消耗原材料A,B各為6kg, 3kg，使用設(shè)備2臺(tái) 時(shí)，每件可獲利5元。問(wèn)該廠是否應(yīng)該生產(chǎn)該產(chǎn)品和 生產(chǎn)多少？ 51 52 例 10 分析原計(jì)劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化 。仍以例1為例，若原計(jì)劃生產(chǎn)產(chǎn)品1的工藝結(jié) 構(gòu)有了改進(jìn)，這時(shí)有關(guān)它的技術(shù)系數(shù)向量變?yōu)?，每件利潤(rùn)為4元，分析對(duì)原最優(yōu) 計(jì)劃有什么影響？ 53 T P)2 , 5 , 2(

22、1 54 例 11 假設(shè)例10的新產(chǎn)品1的技術(shù)系數(shù)向量為 ，而每件獲利仍為4元。試問(wèn)該廠應(yīng)如何安排最 優(yōu)生產(chǎn)方案？ 55 T P)2 , 5 , 4( 1 56 57 58 補(bǔ)充：增加約束條件分析 u一般將原最優(yōu)解代入新增約束，若滿足，則最 優(yōu)解保持不變。 u否則，將新約束條件加入到原單純形表中，調(diào) 整求解。 59 例題 60 0, 4 2 92 . 4max 321 321 321 321 321 xxx xxx xxx xxx ts xxxz 最優(yōu)單純形表如下： 增加新約束： 1763 321 xxx 61 62 資源數(shù)量的變化分析 63 1 1 1 1 1 (bb) (bb)0 B(bb) (bb) B B B B B XB CC B A XB XB XB 會(huì)發(fā)生變化 不變 若，則最優(yōu)基保持不變， 依然是 。最優(yōu)解變成了。 若中有負(fù)的分量，則最優(yōu)基 發(fā)生變化，需要繼續(xù)用對(duì)偶單純形法迭代， 求出新的最優(yōu)解。 價(jià)值系數(shù)的變化分析 64 1 1 1 1 1 b 0 b B B B B B XB CCB A CCB A XB CCB A 不變 會(huì)發(fā)生變化 若，