第6章單純形法的靈敏度與對(duì)偶

1、中華管理學(xué)習(xí)網(wǎng) 1 第六章第六章 單純形法的靈敏度分析與對(duì)偶單純形法的靈敏度分析與對(duì)偶 1 1單純形表的靈敏度分析單純形表的靈敏度分析 2 2線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 3 3對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì) 4 4對(duì)偶單純形法對(duì)偶單純形法 中華管理學(xué)習(xí)網(wǎng) 2 1 1單純形表的靈敏度分析單純形表的靈敏度分析 一、目標(biāo)函數(shù)中變量Ck系數(shù)靈敏度分析 1.在最終的單純形表里，X k是非基變量 由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與Ck沒有任何關(guān)系， 所以當(dāng)Ck變成Ck+ Ck時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閄k是非 基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)

2、不變，即CB不變，可知Zk也不變，只是Ck變 成了Ck+ Ck。這時(shí) K= Ck-Zk就變成了Ck+ Ck- Zk= K+ Ck。要使原來的最優(yōu)解 仍為最優(yōu)解，只要 K+ Ck0即可，也就是Ck的增量 Ck- K。 2.在最終的單純形表中， X k是基變量 當(dāng)Ck變成Ck+ Ck時(shí)，最終單純形表中約束方程的增廣矩陣不變，但是基變量的目 標(biāo)函數(shù)的系數(shù)CB變了，則ZJ(J=1,2,.,N)一般也變了，不妨設(shè)CB=(CB1, CB2。, Ck, ， CBm),當(dāng)CB變成=(CB1, CB2。,Ck+ Ck,CBm),則： ZJ=(CB1, CB2。, Ck,，CBm)(a1j , a2j , aKj

3、 , amj) ZJ=(CB1, CB2。, Ck+ Ck,，CBm)(a1j , a2j , aKj , amj) = ZJ + Ck aKj T T 中華管理學(xué)習(xí)網(wǎng) 3 1 1單純形表的靈敏度分析單純形表的靈敏度分析 根據(jù)上式可知 檢驗(yàn)數(shù) J (J=1,2,.,M)變成了 J,有 J=CJ-ZJ= J+ CK aKj 。要使最優(yōu)解不變，只要當(dāng)J K時(shí)， J 0，就可求出 的取值范圍，也就是使得第K個(gè)約束條件的對(duì)偶價(jià)格不變的 bk的變化范圍。 ， -1-1-1 B XB .(bb)BbBb 。 k b mkk 3kk 2kk 1kk 1-2 1 k db . db db db bB, . D

4、則 mk k k d d d mkk 2kk 1kk 2 1 BB db . db db . XX Bm B B X X X 有新的最優(yōu)解為 中華管理學(xué)習(xí)網(wǎng) 12 1 1單純形表的靈敏度分析單純形表的靈敏度分析 下面我們?nèi)砸缘诙吕?在最終單純形表上對(duì)bj 進(jìn)行靈敏度分析。 最終單純形表如下所示： Bk k X00b Max|0bMin|0 BiBi ikik ikik xx dd dd 要使也就是各個(gè)分量均不小于 ，用一個(gè)數(shù)學(xué)式子來表示 的 允許變化范圍是 迭代次數(shù)基變量CB X1 X2 S1 S2 S3 b 50 100 0 0 0 2 X1501 0 1 0 -150 S200 0 -2

5、 1 150 X21000 1 0 0 1250 ZJ 50 100 50 0 5027500 CJ -ZJ0 0 -50 0 -50 中華管理學(xué)習(xí)網(wǎng) 13 1 1單純形表的靈敏度分析單純形表的靈敏度分析 我們對(duì)b1進(jìn)行靈敏度分析，因?yàn)樵诘谝粋€(gè)約束方程中含有松弛變量S1, 實(shí)際意義可以描述為：當(dāng)設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每設(shè)備臺(tái) 時(shí)數(shù)在250與325之間變化，則設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每臺(tái)設(shè)備 臺(tái)時(shí)50元。 的第一列。就是），純形表中的系數(shù)列（所以松弛變量在最終單 -1T B021 變。約束條件的對(duì)偶價(jià)格不 第一個(gè)即故有當(dāng)而 可以因?yàn)?325bb250,25b50,250|Min 5

6、00|Max,50X,50X, 02d, 01d 11 1 1 1 212111 i i Bi i i Bi d d x d d x 中華管理學(xué)習(xí)網(wǎng) 14 1 1單純形表的靈敏度分析單純形表的靈敏度分析 三、約束方程系數(shù)矩陣A靈敏度分析 下面分兩種情況討論 1.在初始單純形表上的變量Xk的系數(shù)列Pk改變?yōu)镻k經(jīng)過迭代后，在最終單 純形表上Xk是非基變量。由于單純形表的迭代是約束方程的增廣矩陣的行變 換，Pk變成Pk僅僅影響最終單純形表上第k列數(shù)據(jù)，包括Xk的系數(shù)列、Zk以 及 k，這時(shí)最終單純形表上的Xk的系數(shù)列就變成了B-1Pj,而Zk就變成CBB-1Pk， 新的檢驗(yàn)數(shù) k=Ck-CBB-1

7、Pk。若 k0，則原最優(yōu)解仍然為最優(yōu)解。若 k 0， 則繼續(xù)進(jìn)行迭代以求出最優(yōu)。 例例 以第二章例1為基礎(chǔ)，設(shè)該廠除了生產(chǎn)，種產(chǎn)品外，現(xiàn)在試制成一個(gè)新產(chǎn) 品，已知生產(chǎn)產(chǎn)品,每件需要設(shè)備2臺(tái)時(shí)，并消耗A原料0.5公斤。B原料 1.5公斤，獲利150元，問該廠應(yīng)該生產(chǎn)該產(chǎn)品多少？ 解：這是一個(gè)增加新變量的問題。我們可以把它認(rèn)為是一個(gè)改變變量X3在初始 表上的系數(shù)列的問題， 中華管理學(xué)習(xí)網(wǎng) 15 1 1單純形表的靈敏度分析單純形表的靈敏度分析 接上頁(yè) ., 0, 25,150255 . 11005 . 050, 5 . 1 2 5 . 0 5 . 1 5 . 0 2 1 1 1 0 1 0 0 2

8、1 PB ）1.5，0.5，2（ ）1.5，0.5，2（）0，0，0（ 6 66666 1 - 33 3 TT 見表題的最優(yōu)解可知原最優(yōu)解就是新問這時(shí)新變量如下表所示 這時(shí) 就變成了上是非基變量，在最終表之后的第六列上，顯然把它放在 的一列，上添上新的一列變量，。這樣在原來的最終表變成從 ZCZ XS X 迭代次數(shù)基變量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500 CJ -ZJ0 0 -5

9、0 0 -50 -25 中華管理學(xué)習(xí)網(wǎng) 16 1 1單純形表的靈敏度分析單純形表的靈敏度分析 例 假設(shè)上例題中產(chǎn)品的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)生產(chǎn)1件產(chǎn)品需要 使用1.5臺(tái)設(shè)備 ，消耗原料A為2千克，原料B為1千克，每件產(chǎn)品的 利潤(rùn)為160元，問該廠的生產(chǎn)計(jì)劃是否要修改。 解：首先求出X3在最終表上的系數(shù)列 6 1P B 填入下表,35 ,125 1 0 0.5 (50,0,100), 1 0 5 . 0 1 2 5 . 1 1 1 1 0 1 0 0 2 1 PB 66 66 1 ZC z j 迭代 次數(shù) 基變量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 2 X

10、1501 0 1 0 -1 0.55050/0.5 S200 0 -2 1 1 050 X21000 1 0 0 1 1250250/1 ZJ50 100 50 0 50 12527500 CJ -ZJ0 0 -50 0 -50 35 中華管理學(xué)習(xí)網(wǎng) 17 1 1單純形表的靈敏度分析單純形表的靈敏度分析 接下來又可以有新的迭代S3進(jìn)基， 63 1 0,3,X X 由于可知此解不是最優(yōu)解 我們要進(jìn)行第 次迭代 選為入基變量， 為出基變量 迭代 次數(shù) 基變量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 3 X31602 0 2 0 -2 1100- S200 0 -

11、2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 16031000 CJ -ZJ-70 0 -120 0 20 0 中華管理學(xué)習(xí)網(wǎng) 18 1 1單純形表的靈敏度分析單純形表的靈敏度分析 接上頁(yè) 可知此規(guī)模的最優(yōu)解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此時(shí)， 最大目標(biāo)函數(shù)為32000元。也就是說，該廠的新的生產(chǎn)計(jì)劃為不生產(chǎn)、 產(chǎn)品，生產(chǎn)產(chǎn)品200件, 可獲得最大利潤(rùn)32000元。 迭代 次數(shù) 基變量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 4 X31

12、602 0 2 0 -2 1200- S300 0 -2 1 1 05050/1 X2100-2 1 4 -3 0 00250/3 ZJ120 100 80 20 0 16032000 CJ -ZJ-70 0 -80 -20 0 0 中華管理學(xué)習(xí)網(wǎng) 19 1 1單純形表的靈敏度分析單純形表的靈敏度分析 2.在初始表上的變量XK的系數(shù)PK改變?yōu)镻K，經(jīng) 過迭代后，在最終表上XK是基變量，在這種情況下 原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問題十分 復(fù)雜，一般不去修改原表而是直接計(jì)算。 中華管理學(xué)習(xí)網(wǎng) 20 1 1單純形表的靈敏度分析單純形表的靈敏度分析 四、增加一個(gè)約束條件的靈敏度分析 在原線性

13、規(guī)劃中增加一個(gè)約束條件時(shí),先將原問 題的最優(yōu)解的變量值代入新增的約束條件，如滿足 則說明新增的條件沒有起到限制作用，故原最優(yōu)解 不變，否則將新增的約束添入原最終單純形表上進(jìn) 一步求解。 下面仍以第三章例1為例來加以說明。 例：假如該工廠除了在設(shè)備臺(tái)時(shí)，原材料A、B 上對(duì)該廠的生產(chǎn)有限制外，還有電力供應(yīng)上的限制。 最高供應(yīng)電量為5000度，而生產(chǎn)一個(gè)產(chǎn)品需要用 電10度，而生產(chǎn)一個(gè)產(chǎn)品需要用電30度。試分析 此時(shí)該廠獲得最大利潤(rùn)的生產(chǎn)計(jì)劃？ 中華管理學(xué)習(xí)網(wǎng) 21 1 1單純形表的靈敏度分析單純形表的靈敏度分析 1 x 2 x解：先將原問題的最優(yōu)解=50=50，=250代入用電量的約束條件 得：1

14、050+30250=500+75005000,所以原題的最優(yōu)解不是本題的最優(yōu)解。 在用電量的約束條件中加入松馳變量S4后得： 124 10 x +30 x +s =5000 把這個(gè)約束條件加入到原最終單純形表上，其中S4為基變量，得表如下： B C 1 x 2 x 1 s 2 s 3 s 4 s 1 x 2 s 2 x 4 s j z 迭代迭代 次數(shù)次數(shù) 基變量基變量b b比值比值 50501001000 00 00 00 0 50501 10 01 10 0-1-10 05050 0 00 00 0-2-21 11 10 05050 1001000 01 10 00 01 10 025025

15、0 0 0101030300 00 00 01 150005000 505010010050500 050500 027502750 0 0 0 00 0-50-500 0-50-500 0 jjj cz 12 10305000 xx 中華管理學(xué)習(xí)網(wǎng) 22 1 1單純形表的靈敏度分析單純形表的靈敏度分析 在上表中的X1，X2不是單位向量，故進(jìn)行行的線性變換，得 迭代迭代 次數(shù)次數(shù) 基變量基變量C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3s s4 4b b比值比值 50501001000 00 00 00 0 x x1 150501 10 01 10 0-1-10 0

16、5050 s s2 20 00 00 0-2-21 11 10 05050 x x2 21001000 01 10 00 01 10 0250250 s s4 40 00 00 0-10-100 0-20-201 1-3000-3000 z zj j505010010050500 050500 02750027500 0 00 0-50-500 0-50-500 0 把上表中的S4行的約束可以寫為： 134 10203000sss 上式兩邊乘以（-1），再加上人工變量a1得： 1341 10203000sssa 用上式替換上表中的S4行，得下表： jjj cz 中華管理學(xué)習(xí)網(wǎng) 23 1 1單純

17、形表的靈敏度分析單純形表的靈敏度分析 迭代迭代 次數(shù)次數(shù) 基變基變 量量 x x1 1x x2 2s s1 1s s2 2s s3 3s s4 4a a1 1b b比值比值 50501001000 00 00 00 0-M-M x x1 150501 10 01 10 0-1-10 00 05050 s s2 20 00 00 0-2-21 1(1)(1)0 00 05050 x x2 21001000 01 10 00 01 10 00 0250250 s s4 4-M-M0 00 0-10-100 0-20-201 11 130003000 z zj j505010010050-10M50

18、-10M0 050-20M50-20M0 0-M-M 0 00 010M-5010M-500 020M-5020M-500 00 0 x x1 150501 10 0-1-11 10 00 00 0100100 s s3 30 00 00 0-2-21 11 10 00 05050 x x2 21001000 01 12 2-1-10 00 00 0200200 s s4 4-M-M0 00 05050-20-200 0-1-11 120002000 z zj j5050100100150-50M150-50M20M-5020M-500 0M M-M-M 0 050M-15050M-15050

19、-20M50-20M0 0-M-M0 0 x x1 150501 10 00 03/53/50 0-1/50-1/501/501/50140140 s s3 30 00 00 00 01/51/51 1-2/50-2/502/502/50130130 x x2 21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120 s s4 40 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040 z zj j50501001000 010100 03 3-3-3 0 00 0-10-100 0-3-3-M+3-M+3 jjj

20、 cz jjj cz jjj cz 中華管理學(xué)習(xí)網(wǎng) 24 1 1單純形表的靈敏度分析單純形表的靈敏度分析 由上表可知，最優(yōu)解為： 121231 1401200 xxsssa 即該工廠在添加了用電限量以后的最優(yōu)生產(chǎn)計(jì)劃為 產(chǎn)品生產(chǎn)140件，產(chǎn)品生產(chǎn)120件。 中華管理學(xué)習(xí)網(wǎng) 25 每一個(gè)線性規(guī)劃問題，都存在每一個(gè)與它密切相關(guān)的線性規(guī)劃的問題，我們稱其為原問題， 另一個(gè)為對(duì)偶問題。 例題例題1 1 某工廠在計(jì)劃期內(nèi)安排、兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如表所示 該工廠每生產(chǎn)一單位產(chǎn)品 可獲利50元，每生產(chǎn)一單位產(chǎn)品可獲利100元，問工廠應(yīng)分別 生產(chǎn)多少 產(chǎn)品和產(chǎn)品，才能使工廠獲利最多？

21、 解：設(shè) 為產(chǎn)品 的計(jì)劃產(chǎn)量， 為產(chǎn)品的計(jì)劃產(chǎn)量，則有 目標(biāo)函數(shù)： Max z z=50 +100 約束條件： ， 資源限量 設(shè)備 A 1 1 300 臺(tái)時(shí) 設(shè)備 B 2 1 400 臺(tái)時(shí) 設(shè)備 C 0 1 250 臺(tái)時(shí) 1 x 2 x 300 21 xx 4002 21 xx 2 x 250 2 x 1 x 0 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 26 現(xiàn)在我們從另一個(gè)角度來考慮這個(gè)問題。假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、 C，那么該廠的廠長(zhǎng)應(yīng)該如何來確定合理的租金呢？ 設(shè) 分別為設(shè)備A、B、C的每臺(tái)時(shí)的租金。為了敘述方便，這里把租金定義為扣 除成本后的利

22、潤(rùn)。作為出租者來說，把生產(chǎn)單位 產(chǎn)品所需各設(shè)備的臺(tái)時(shí)各總租金不應(yīng)低于 原利潤(rùn)50元，即 ，否則就不出租還是用于生產(chǎn) 產(chǎn)品以獲利50元；同樣把 生產(chǎn)一單位 產(chǎn)品所需各設(shè)備的臺(tái)時(shí)的總租金也不應(yīng)當(dāng)?shù)陀谠麧?rùn)100元， 即 ，否則這些設(shè)備臺(tái)時(shí)就不出租，還是用于生產(chǎn) 產(chǎn)品以獲利100元。但對(duì)于租用者來說，他要 求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設(shè)備臺(tái)時(shí)的總 租金越低越好，即min ，這樣我們得到了該問題的數(shù)學(xué)模型： 目標(biāo)函數(shù)： 約束條件： 這樣從兩個(gè)不同的角度來考慮同一個(gè)工廠的最大利潤(rùn)（最小租金）的問題，所建立起來 的兩個(gè)線性模型就是一對(duì)對(duì)偶問題，其中一個(gè)叫做原問題原問

23、題，而另外一個(gè)叫對(duì)偶問題對(duì)偶問題。 3, 21, yyy 321 250400300minyyyf 502 21 yy 100 321 yyy 321 250400300yyy 0, 100 502 321 321 21 yyy yyy yy 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 27 如果我們把求目標(biāo)函數(shù)最大值的線性規(guī)劃問題看成原問題，則求目標(biāo)函數(shù)最小值的線性 規(guī)劃問題看成對(duì)偶問題。下面來研究這兩個(gè)問題在數(shù)學(xué)模型上的關(guān)系。 1 求目標(biāo)函數(shù)最大值的線性規(guī)劃問題中有n 個(gè)變量 m個(gè)約束條件，它的約束條件都是小于 等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問題，有

24、m個(gè)變量n個(gè)約束條件， 其約束條件都為大于等于不等式。 2 原問題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問題中的約束條件的右邊常數(shù)項(xiàng)，并且原問題的 目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)就等于對(duì)偶問題中的第i個(gè)約束條件的右邊常數(shù)項(xiàng)。 3 原問題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問題的目標(biāo)函數(shù)中的變量的系數(shù)。并且原問題的 第i個(gè)約束條件的右邊常數(shù)項(xiàng)就等于零對(duì)偶問題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)。 4 對(duì)偶問題的約束條件的系數(shù)矩陣A是原問題約束矩陣的轉(zhuǎn)置。 設(shè) A= 則 mnmm n aaa aaa . . . 21 11211 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 mnnn m T aaa aaa A 21 12

25、111 中華管理學(xué)習(xí)網(wǎng) 28 如果我們用矩陣形式來表示，則有原問題： 其中A是 矩陣m*n，該問題有m個(gè)約束條件n個(gè)變量，x= ,b= , c= 對(duì)偶問題： 其中 是A的轉(zhuǎn)置， 是b的轉(zhuǎn)置, 是c的轉(zhuǎn)置, y= 現(xiàn)在我們用單純形法求對(duì)偶問題的解。 0 , ,max x bAx cxz ).,.,( 21n ccc T m bbb),.,( 21 T A T b T C T m yyy),.,( 21 0 . .min y cyA ybf TT T 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 T n xxx, 21 中華管理學(xué)習(xí)網(wǎng) 29 加上剩余變量 和人工變量 ，把此問題化成標(biāo)準(zhǔn)型如下： 把

26、上述數(shù)據(jù)填入單純形表計(jì)算。 21,s s 1 a 1321 500400300)max(Mayyyf 0, 100 502 121321 2321 1121 assyyy syyy asyy 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 30 迭代 變量 基變量 b -300-400-25000-M 1 -M1 0 -1 0 15050/2 -250 1 1 1 0 -1 0 100100/1 -M-250-2M- 250 -250M250-M-50M-25000 M-250 2M- 150 0-M-2500 2 -4001/210-1/201/225 -2501/2011/2

27、-1-1/275 -325-400-25075250-75-28750 2500-75-250-M+75 3 -300120-10150 -2500-111-1-150 -300-350-25050250-50-27500 0-500-50-250-M+50 b c 1 y 2 y 3 y 2 s 1 s 1 a 1 a 3 y j z jj zc 2 y 3 y 2/1 75 2/1 25 j z jj zc 1 y 3 y j z jj zc 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 31 由上表，最優(yōu)解： =50， -f 的最大值為-27500，即目標(biāo)函數(shù)f的最大值為

28、f=27500元。 從上面可知租金：A設(shè)備為50元，B設(shè)備為0元，C設(shè)備為50元。這樣把工 廠的所有設(shè)備出租可共得租金27500元。對(duì)出租者來說這租金是出租者愿意出 租設(shè)備的最小費(fèi)用，因?yàn)檫@是目 標(biāo)函數(shù)的最小值。 通過比較，我們發(fā)現(xiàn)：對(duì)偶問題的最優(yōu)解即最佳租金恰好等于原問題各種 設(shè)備的對(duì)偶價(jià)格，這在道理上也能講得通。 對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃 的問題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問題的對(duì)偶價(jià)格而 求得其對(duì)偶問題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問題的最 優(yōu)值，因?yàn)檫@兩個(gè)最優(yōu)值相等。 1 y0, 0, 0,50, 0 12132 assyy 2 2 線性規(guī)劃的對(duì)偶問題

29、線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 32 下面來闡述如何寫出一個(gè)線性規(guī)劃問題的對(duì)偶問題。為了 便于闡述，我們不妨以下面的線性規(guī)劃為例，寫出它的對(duì)偶 問題。 S.T. 321 643maxxxxz 0, ,20035 ,10046 ,440632 321 321 321 321 xxx xxx xxx xxx 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 33 這是一個(gè)求最大值的線性規(guī)劃問題，為了寫出它的對(duì)偶問題，我們不 妨把它的約束條件都變換成取小于號(hào)的不等式。顯然第一個(gè)約束條件已符 合要求，不要做任何變動(dòng)，而第二個(gè)約束條件，我們只要兩邊都乘以（- 1），使不等號(hào)方向改變即可，

30、得 這樣第二個(gè)約束條件也就符合要求。對(duì)于第三個(gè)約束條件，我們可以 用小于等于和大于等于兩個(gè)約束條件來替代它。即有 顯然，這兩個(gè)約束條件與原來第三個(gè)約束條件是等價(jià)的，我們?cè)侔哑?中的 兩邊都乘以（-1），得 10046 321 xxx 20035 20035 321 321 xxx xxx 20035 321 xxx 20035 321 xxx 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 34 通過上面的一些變換，我們得到了一個(gè)和原線性規(guī)劃等價(jià)的線性規(guī)劃 問題： s.t. 321 643maxxxxz 0, 20035 20035 ,10046 ,440632 321 321

31、321 321 321 xxx xxx xxx xxx xxx 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 35 這個(gè)求最大值的線性規(guī)劃問題的約束條件都取小于等于號(hào)，我們馬 上可以寫出其對(duì)偶問題： s.t. 3 3 21 200200100440minyyyyf , 0, , 66 , 43343 , 35562 3 3 21 3 3 21 3 3 21 3 3 21 yyyy yyyy yyyy yyyy 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 36 這里 和 一樣都是不同的決策變量，為了表示這兩個(gè) 決策變量都來源于原問題的第三個(gè)約束條件，記為 。 因

32、為在該對(duì)偶問題中 和 的系數(shù)只相差一個(gè)符號(hào)，我們可以把 上面的對(duì)偶問題化為： s.t. 3 3 , yy 21, y y 3 y3 y )(200100440min3 3 21 yyyyf , 0, , 6)(6 , 4)(343 , 3)(562 3 3 21 3 3 21 3 3 21 3 3 21 yyyy yyyy yyyy yyyy 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 3 3 , yy 中華管理學(xué)習(xí)網(wǎng) 37 進(jìn)一步，我們可以令 ，這時(shí)當(dāng) 時(shí)， ，當(dāng) 時(shí)， 。這也就是說，盡管 但 的取值可以為正，可以為0， 可以為負(fù)，即 沒有非負(fù)限制。 這樣我們把原規(guī)劃的對(duì)偶問題化為 s.t

33、. 沒有限制。 對(duì)照原線性規(guī)劃問題，我們可以知道： 當(dāng)原線性規(guī)劃問題的第i個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問題的 i個(gè)決策變量沒有非 負(fù)限制。 如果當(dāng)原線性規(guī)劃問題中的第 i個(gè)決策變量 沒有非負(fù)限制時(shí)，我們也可以用 進(jìn)行替換，這里 ， ，用類似的方法知道其對(duì)偶問題中第 i個(gè) 約束條件取等號(hào)。 3 3 3 yyy3 3 yy 0y 3 3 yy 0 3 y, 0, 3 3 yy 3 y 3 y 321 200100440minyyyf , 0, , 66 , 4343 , 3562 21 321 321 321 yy yyy yyy yyy 3 y i x ii i xxx 0 ix0 ix 2 2

34、 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 38 另外，用大于等于0的兩個(gè)決策變量之差來代替無非負(fù)限制的決策變 量也是求解含有無非負(fù)限制的決策變量的線性規(guī)劃問題的一種方法。 原線性規(guī)劃問題為： s.t. 無非負(fù)限制。 321 493minxxxf , 0, ,24035 ,6032 ,18032 21 21 321 321 xx xx xxx xxx 3 x 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 中華管理學(xué)習(xí)網(wǎng) 39 3 3對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì) 對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì) 1對(duì)稱性對(duì)稱性。即對(duì)偶問題的對(duì)偶是原問題。 2弱對(duì)偶性弱對(duì)偶性。即對(duì)于原問題

35、（）和對(duì)偶問題（）的可 行解 都有C bT 。 由弱對(duì)偶性，可得出以下推論： （1）原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的 下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù) 值的上界。 （2）如原問題有可行解且目標(biāo)函數(shù)值無界（或具有無界解），則 其對(duì)偶問題無可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界， 則其原問題無可行解（注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問題無 可行解時(shí)，其原問題或具有無界解或無可行解，反之亦然）。 （3）若原問題有可行解而其對(duì)偶問題無可行解，則原問題目標(biāo)函 數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問 題的目標(biāo)函數(shù)值無界。 YX , X Y 中華管理學(xué)習(xí)網(wǎng) 40 3 3對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì) 3最優(yōu)性最優(yōu)性。如果 是原問題()的可行解，