第6章單純形法的靈敏度分析與課件

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1上節(jié)回顧上節(jié)回顧 4.退化問題（求出基變量過程中存在兩個(gè)以上的最小比值，這樣在下一次迭代就有一個(gè)或多個(gè)基變量等于零，造成的后果是：最優(yōu)值在經(jīng)過了一次或幾次迭代而沒有改善，降低了單純型算法的效率） 5.針對(duì)退化問題，講解了一個(gè)迭代循環(huán)的例子，引出了勃蘭特法則： 按照決策變量、松弛變量、人工變量順序排序。不管是檢驗(yàn)數(shù)相等，還是比值相等，都選下標(biāo)最小的為入基變量或出基變量。 時(shí)間問題，習(xí)題沒有做。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2第六章第六章 單純形法的靈敏度分析與對(duì)偶問題單純形法的靈敏度分析與對(duì)偶問題 1 1單純形表的靈敏度分析單純形表的靈敏度分析 2 2線性規(guī)劃的對(duì)偶問

2、題線性規(guī)劃的對(duì)偶問題 3 3對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì) 4 4對(duì)偶單純形法對(duì)偶單純形法管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3單純形表單純形表管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)41 1單純形表的靈敏度分析單純形表的靈敏度分析一、目標(biāo)函數(shù)中變量系數(shù)Ck靈敏度分析（在什么范圍內(nèi)變化，最優(yōu)解不變，與第二章，第三章聯(lián)系起來） 在線性規(guī)劃的求解過程中，目標(biāo)函數(shù)系數(shù)的變動(dòng)將會(huì)影響檢驗(yàn)數(shù)的取值，但是，當(dāng)目標(biāo)函數(shù)的系數(shù)的變動(dòng)不破壞最優(yōu)判別準(zhǔn)則時(shí)，原最優(yōu)解不變，否則，原最優(yōu)解將發(fā)生變化，要設(shè)法求出新的最優(yōu)解。下面我們具體的分析 1.在最終的單純形表里，X k是非基變量 由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行的

3、初等變換與Ck沒有任何關(guān)系， 所以當(dāng)Ck變成Ck+ Ck時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閄k是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB不變，可知Zk也不變，只是Ck變成了Ck+ Ck。這時(shí) K= Ck-Zk就變成了Ck+ Ck- Zk= K+ Ck。要使原來的最優(yōu)解仍為最優(yōu)解，只要 K+ Ck0即可，也就是Ck的增量 Ck- K。 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)5 2.在最終的單純形表中， X k是基變量 當(dāng)Ck變成Ck+ Ck時(shí)，最終單純形表中約束方程的增廣矩陣不變，但是基變量的目標(biāo)函數(shù)的系數(shù)CB變了，則ZJ(J=1,2,.,N)一般也變了，不妨設(shè)CB=(CB1, CB

4、2。, Ck,， CBm),當(dāng)CB變成=(CB1, CB2。,Ck+ Ck,CBm),則： ZJ=(CB1, CB2。, Ck,，CBm)(a1j , a2j , aKj , amj) ZJ=(CB1, CB2。, Ck+ Ck,，CBm)(a1j , a2j , aKj , amj) = ZJ + Ck aKj T管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)61 1單純形表的靈敏度分析單純形表的靈敏度分析根據(jù)上式可知 檢驗(yàn)數(shù) J (J=1,2,.,M)變成了 J,只要當(dāng)J K時(shí)，有 J=CJ-ZJ= J- CK aKj 。要使最優(yōu)解不變，J 0，就可求出 的取值范圍，也就是使得第K個(gè)約束條件的對(duì)偶價(jià)格不變的

5、bk的變化范圍。 ，-1-1-1BXB .(bb)BbBb 。kbmkk3kk2kk1kk1-21kdb.dbdbdbbB,.D則mkkkdddmkk2kk1kk21BBdb.dbdb.XXBmBBXXX有新的最優(yōu)解為管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)211 1單純形表的靈敏度分析單純形表的靈敏度分析（k的取值固定的值，i的取值是1到m）下面我們?nèi)砸缘诙吕?在最終單純形表上對(duì)b1進(jìn)行靈敏度分析。最終單純形表如下所示：BkkX00bMax|0bMin|0BiBiikikikikxxdddd 要使也就是各個(gè)分量均不小于 ，用一個(gè)數(shù)學(xué)式子來表示 的允許變化范圍是迭代次數(shù)基變量CBX1 X2 S1 S2

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

7、250,25b50,252500|Min501500|Max,50X,50X, 02d, 01d11111212111iiBiiiBiddxddx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)231 1單純形表的靈敏度分析單純形表的靈敏度分析三、約束方程系數(shù)矩陣三、約束方程系數(shù)矩陣A A靈敏度分析（約束條件改變，對(duì)最優(yōu)解的影響，比如靈敏度分析（約束條件改變，對(duì)最優(yōu)解的影響，比如有新產(chǎn)品要生產(chǎn)、生產(chǎn)工藝改進(jìn)等）有新產(chǎn)品要生產(chǎn)、生產(chǎn)工藝改進(jìn)等）下面分兩種情況討論 1.在最終單純形表上在最終單純形表上Xk是非基變量：在初始單純形表上的變量是非基變量：在初始單純形表上的變量Xk的系數(shù)列的系數(shù)列Pk改變?yōu)楦淖優(yōu)镻k經(jīng)過迭

8、代后，在最終單純形表上經(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-1Pk。若 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è)

9、增加新變量的問題。我們可以把它認(rèn)為是一個(gè)改變變量X3在初始表上的系數(shù)列的問題，管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)241 1單純形表的靈敏度分析單純形表的靈敏度分析., 0,25,150255 . 11005 . 050,5 . 125 . 05 . 15 . 02111010021PB）1.5，0.5，2（）1.5，0.5，2（）0，0，0（6666661 -333TT見表題的最優(yōu)解可知原最優(yōu)解就是新問這時(shí)新變量如下表所示這時(shí)就變成了上是非基變量，在最終表之后的第六列上，顯然把它放在的一列，上添上新的一列變量，。這樣在原來的最終表變成從ZCZXSX迭代次數(shù)基變量CBX1 X2 S1 S2 S3 X3

10、 b50 100 0 0 0 150X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500CJ -ZJ0 0 -50 0 -50 -25管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)251 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ù)列 61PB填入下表,35,125100.5(50,0,100

11、),105 . 0125 . 1111010021PB66661ZCzj迭代次數(shù)基變量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1602X1501 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 12527500CJ -ZJ0 0 -50 0 -50 35管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)261 1單純形表的靈敏度分析單純形表的靈敏度分析接下來又可以有新的迭代S3進(jìn)基，6310,3,XX由于可知此解不是最優(yōu)解 我們要進(jìn)行第 次迭代 選為入基變量，為出基變量迭代次

12、數(shù)基變量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1503X31602 0 2 0 -2 1100- S200 0 -2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 16031000CJ -ZJ-70 0 -120 0 20 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)271 1單純形表的靈敏度分析單純形表的靈敏度分析接上頁 可知此規(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)品20

13、0件, 可獲得最大利潤(rùn)32000元。迭代次數(shù)基變量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1504X31602 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 16032000CJ -ZJ-70 0 -80 -20 0 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)281 1單純形表的靈敏度分析單純形表的靈敏度分析 2.最終表上最終表上XK是基變量：在初始表上的變量是基變量：在初始表上的變量XK的系數(shù)的系數(shù)PK改變?yōu)楦淖優(yōu)镻K，經(jīng)過迭代后，在最終表上，經(jīng)過迭代后，在最終表

14、上XK是基變量，是基變量，（比如（比如X1，X2，制作產(chǎn)品，制作產(chǎn)品1，產(chǎn)品，產(chǎn)品2的工藝有改善，在這種的工藝有改善，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問題十情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問題十分復(fù)雜）一般不去修改最終單純形表，而是重新用單純形分復(fù)雜）一般不去修改最終單純形表，而是重新用單純形法計(jì)算。法計(jì)算。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)291 1單純形表的靈敏度分析單純形表的靈敏度分析四、增加一個(gè)約束條件的靈敏度分析（增加一個(gè)約束條件對(duì)最優(yōu)解的影響） 在原線性規(guī)劃中增加一個(gè)約束條件時(shí),（1）先將原問題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說明新增的條件沒有起

15、到限制作用，故原最優(yōu)解不變，停止計(jì)算。（2）否則將新增的約束添入原最終單純形表上，進(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ì)劃？ 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)301 1單純形表的靈敏度分析單純形表的靈敏度分析 1x2x解：先將原問題的最優(yōu)解=50=50，=250代入用電量的約束條件得：1050+30250=500+75005000,所以原題的最優(yōu)解不是本題的最優(yōu)解。在用電量的約束條

16、件中加入松馳變量S4后得：12410 x +30 x +s =5000把這個(gè)約束條件加入到原最終單純形表上，其中S4為基變量，得表如下：BC1x2x1s2s3s4s1x2s2x4sjz迭代迭代次數(shù)次數(shù)基變量基變量b b比值比值50501001000 00 00 00 050501 10 01 10 0-1-10 050500 00 00 0-2-21 11 10 050501001000 01 10 00 01 10 02502500 0101030300 00 00 01 150005000505010010050500 050500 0275027500 00 00 0-50-500 0-

17、50-500 0jjjcz1210305000 xx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)311 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 05050s s2 20 00 00 0-2-21 11 10 05050 x x2 21001000 01 10 00 01 10 0250250s s4 40 00 00 0-10

18、-100 0-20-201 1-3000-3000z zj j505010010050500 050500 027500275000 00 0-50-500 0-50-500 0把上表中的S4行的約束可以寫為ss 上式兩邊乘以（-1），再加上人工變量a1得：134110203000sssa用上式替換上表中的S4行，得下表：jjjcz管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)321 1單純形表的靈敏度分析單純形表的靈敏度分析迭代迭代次數(shù)次數(shù)基變基變量量x x1 1x x2 2s s1 1s s2 2s s3 3s s4 4a a1 1b b比值比值50501001000 00 00

19、00 0-M-Mx x1 150501 10 01 10 0-1-10 00 05050s s2 20 00 00 0-2-21 1(1)(1)0 00 05050 x x2 21001000 01 10 00 01 10 00 0250250s s4 4-M-M0 00 0-10-100 0-20-201 11 130003000z zj j505010010050-10M50-10M0 050-20M50-20M0 0-M-M0 00 010M-5010M-500 020M-5020M-500 00 0 x x1 150501 10 0-1-11 10 00 00 0100100s s3

20、30 00 00 0-2-21 11 10 00 05050 x x2 21001000 01 12 2-1-10 00 00 0200200s s4 4-M-M0 00 05050-20-200 0-1-11 120002000z zj j5050100100150-50M150-50M20M-5020M-500 0M M-M-M0 050M-15050M-15050-20M50-20M0 0-M-M0 0 x x1 150501 10 00 03/53/50 0-1/50-1/501/501/50140140s s3 30 00 00 00 01/51/51 1-2/50-2/502/50

21、2/50130130 x x2 21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120s s4 40 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040z zj j50501001000 010100 03 3-3-30 00 0-10-100 0-3-3-M+3-M+3jjjczjjjczjjjcz管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)331 1單純形表的靈敏度分析單純形表的靈敏度分析 由上表可知，最優(yōu)解為：1212311401200 xxsssa 即該工廠在添加了用電限量以后的最優(yōu)生產(chǎn)計(jì)劃為產(chǎn)品生產(chǎn)140件，產(chǎn)品生產(chǎn)

22、120件。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)34上節(jié)回顧上節(jié)回顧單純形法的靈敏度分析1.目標(biāo)函數(shù)系數(shù)Cj的靈敏度2.常數(shù)項(xiàng)bj的靈敏度分析3.系數(shù)矩陣A的靈敏度分析 在初始表上的變量XK的系數(shù)PK改變?yōu)镻K，經(jīng)過迭代后，在最終表上XK是基變量，（比如X1，X2，制作產(chǎn)品1，產(chǎn)品2的工藝有改善，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問題十分復(fù)雜）一般不去修改最終單純形表，而是重新用單純形法計(jì)算。4.增加一個(gè)約束條件的靈敏度分析 （1）先將原問題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說明新增的條件沒有起到限制作用，故原最優(yōu)解不變，停止計(jì)算。 （2）否則將新增的約束添入原最終單純形表上，

23、進(jìn)一步求解。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)35對(duì)偶單純形法： 對(duì)偶單純形法也是解決線性規(guī)劃問題的一種方法。對(duì)偶單純形法是在保持原有問題的所有檢驗(yàn)數(shù)都小于0的情況下，通過迭代使得所有的約束都大于等于0，最后求得最優(yōu)解。 優(yōu)點(diǎn)：簡(jiǎn)化計(jì)算是對(duì)偶單純形法的優(yōu)點(diǎn) 例子： 缺點(diǎn)：但是它在使用上有很大的局限，這主要是 大多數(shù)線性規(guī)劃問題很難找到初始解使得其所有檢驗(yàn)數(shù)都小于0。 適用目標(biāo)函數(shù)的特點(diǎn)： A.max f= -M1*X1-M2*X2.的形式 B.用在靈敏度分析中（增加約束條件的）。 上節(jié)回顧上節(jié)回顧5021 xx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)36 1.對(duì)偶問題的定義 2.原問題與對(duì)偶問題的關(guān)系 3.如何

24、根據(jù)原問題的結(jié)果去找對(duì)偶問題的答案 4.如何將原問題轉(zhuǎn)化成對(duì)偶問題 5.對(duì)偶規(guī)劃的基本性質(zhì)2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)37任何一個(gè)求極大化的線性規(guī)劃問題都有一個(gè)求極小化的線性規(guī)劃問題與之對(duì)應(yīng)，反之亦然，如果任何一個(gè)求極大化的線性規(guī)劃問題都有一個(gè)求極小化的線性規(guī)劃問題與之對(duì)應(yīng)，反之亦然，如果我們把其中一個(gè)叫原問題，則另一個(gè)就叫做它的對(duì)偶問題，并稱這一對(duì)互相聯(lián)系的兩個(gè)問題為一我們把其中一個(gè)叫原問題，則另一個(gè)就叫做它的對(duì)偶問題，并稱這一對(duì)互相聯(lián)系的兩個(gè)問題為一對(duì)對(duì)偶問題。對(duì)對(duì)偶問題。例題例題1 1 某工廠在計(jì)劃期內(nèi)安排、兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B

25、、C臺(tái)時(shí)如表所示 該工廠每生產(chǎn)一單位產(chǎn)品 可獲利50元，每生產(chǎn)一單位產(chǎn)品可獲利100元，問工廠應(yīng)分別生產(chǎn)多少 產(chǎn)品和產(chǎn)品，才能使工廠獲利最多？解：設(shè) 為產(chǎn)品 的計(jì)劃產(chǎn)量， 為產(chǎn)品的計(jì)劃產(chǎn)量，則有目標(biāo)函數(shù)： Max z z=50X1 +100 x2約束條件： ， 資源限量 設(shè)備 A 1 1 300 臺(tái)時(shí) 設(shè)備 B 2 1 400 臺(tái)時(shí) 設(shè)備 C 0 1 250 臺(tái)時(shí) 1x2x30021 xx400221 xx2x2502x1x02 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)38 現(xiàn)在我們從另一個(gè)角度來考慮這個(gè)問題。假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、C，那么該廠

26、的廠長(zhǎng)應(yīng)該如何來確定合理的租金呢？ 設(shè) 分別為設(shè)備A、B、C的每臺(tái)時(shí)的租金。租金定價(jià)的原則是： 出租者：生產(chǎn)一個(gè)單位的 產(chǎn)品需消耗1個(gè)單位的設(shè)備A、2個(gè)單位的設(shè)備B、0個(gè)單位的設(shè)備C，獲利50個(gè)單位；那么，將這些資源（設(shè)備臺(tái)時(shí)）全部轉(zhuǎn)讓時(shí)所獲得的利潤(rùn) 應(yīng)不少于50個(gè)單位，否則就不出租還是用于生產(chǎn) 產(chǎn)品以獲利50元；同樣把生產(chǎn)一個(gè)單位 產(chǎn)品所需各設(shè)備的臺(tái)時(shí)的總租金也不應(yīng)當(dāng)?shù)陀谠麧?rùn)100元， 即，否則這些設(shè)備臺(tái)時(shí)就不出租，還是用于生產(chǎn) 產(chǎn)品以獲利100元。3,21,yyy50221 yy100321yyy2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)39對(duì)于租用者，他要

27、求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設(shè)備臺(tái)時(shí)的總租金越低越好，即min ，這樣我們得到了該問題的數(shù)學(xué)模型： 目標(biāo)函數(shù)： 約束條件： 這樣從兩個(gè)不同的角度來考慮同一個(gè)工廠的最大利潤(rùn)（最小租金）的問題，所建立起來的兩個(gè)線性模型就是一對(duì)對(duì)偶問題，其中一個(gè)叫做原問題原問題，而另外一個(gè)叫對(duì)偶問對(duì)偶問題題。321250400300yyy321250400300minyyyf0,10050232132121yyyyyyyy管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)40 如果我們把求目標(biāo)函數(shù)最大值的線性規(guī)劃問題看成原問題，則求目標(biāo)函數(shù)最小值的線性規(guī)劃問題看成對(duì)偶問題。下面來研究這兩個(gè)問題在數(shù)

28、學(xué)模型上的關(guān)系。 1 求目標(biāo)函數(shù)最大值的線性規(guī)劃問題中有n 個(gè)變量 m個(gè)約束條件，它的約束條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問題，有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ù)。 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)

29、414 對(duì)偶問題的約束條件的系數(shù)矩陣A是原問題約束矩陣的轉(zhuǎn)置。 設(shè) A=則 mnmmnaaaaaa.2111211mnnnmTaaaaaaA2112111管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)42如果我們用矩陣形式來表示，則有原問題： 其中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,maxxbAxcxz).,.,(21ncccTmbbb),.,(21TATbTCTmyyy),.,(210.minycyAybfTTT2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題Tnxxx,21

30、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)43 加上剩余變量 和人工變量 ，把此問題化成標(biāo)準(zhǔn)型如下：把上述數(shù)據(jù)填入單純形表計(jì)算。21,ss1a1321500400300)max(Mayyyf0,10050212132123211121assyyysyyyasyy2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)44迭代變量基變量 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-25000M-2502M-1500-M-25002-4001/210-1/

31、201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+50bc1y2y3y2s1s1a1a3yjzjjzc 2y3y2/1752/125jzjjzc 1y3yjzjjzc 2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)45 由上表，最優(yōu)解：由上表，最優(yōu)解： =50， -f 的最大值為的最大值為-27500，即目標(biāo)函數(shù)，即目標(biāo)函數(shù)f的最大值為的最大值

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

33、偶關(guān)系的線性規(guī)劃的問題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問題的對(duì)偶價(jià)格而求得其對(duì)偶問題的最優(yōu)其中一個(gè)最優(yōu)解，就可以從這個(gè)問題的對(duì)偶價(jià)格而求得其對(duì)偶問題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問題的最優(yōu)值，因?yàn)檫@兩個(gè)最解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問題的最優(yōu)值，因?yàn)檫@兩個(gè)最優(yōu)值相等。優(yōu)值相等。 1y0, 0, 0,50, 012132assyy2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)46 下面來闡述如何寫出一個(gè)線性規(guī)劃問題的對(duì)偶問題。為了便于闡述，我們不妨以下面的線性規(guī)劃為例，寫出它的對(duì)偶問題。 S.T. 321643maxxxxz0,200

34、35,10046,440632321321321321xxxxxxxxxxxx2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)47 這是一個(gè)求最大值的線性規(guī)劃問題，為了寫出它的對(duì)偶問題，我們不妨把它的約束條件都變換成取小于號(hào)的不等式。顯然第一個(gè)約束條件已符合要求，不要做任何變動(dòng)，而第二個(gè)約束條件，我們只要兩邊都乘以（-1），使不等號(hào)方向改變即可，得 這樣第二個(gè)約束條件也就符合要求。對(duì)于第三個(gè)約束條件，我們可以用小于等于和大于等于兩個(gè)約束條件來替代它。即有 顯然，這兩個(gè)約束條件與原來第三個(gè)約束條件是等價(jià)的，我們?cè)侔哑渲械膬蛇叾汲艘裕?1），得 10046321xxx200

35、3520035321321xxxxxx20035321xxx20035321xxx2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)48 通過上面的一些變換，我們得到了一個(gè)和原線性規(guī)劃等價(jià)的線性規(guī)劃問題： s.t. 321643maxxxxz0,2003520035,10046,440632321321321321321xxxxxxxxxxxxxxx2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)49 這個(gè)求最大值的線性規(guī)劃問題的約束條件都取小于等于號(hào)，我們馬上可以寫出其對(duì)偶問題： s.t.3 321200200100440minyyyyf, 0,

36、 66, 43343, 355623 3213 3213 3213 321yyyyyyyyyyyyyyyy2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)50 這里 和 一樣都是不同的決策變量，為了表示這兩個(gè)決策變量都來源于原問題的第三個(gè)約束條件，記為 。 因?yàn)樵谠搶?duì)偶問題中 和 的系數(shù)只相差一個(gè)符號(hào)，我們可以把上面的對(duì)偶問題化為： s.t.3 3, yy21, yy3y3 y)(200100440min3 321yyyyf, 0, 6)(6, 4)(343, 3)(5623 3213 3213 3213 321yyyyyyyyyyyyyyyy2 2 線性規(guī)劃的對(duì)偶問題

37、線性規(guī)劃的對(duì)偶問題3 3, yy管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)51 進(jìn)一步，我們可以令 ，這時(shí)當(dāng) 時(shí)， ，當(dāng) 時(shí)， 。這也就是說，盡管 但 的取值可以為正，可以為0，可以為負(fù)，即 沒有非負(fù)限制。 這樣我們把原規(guī)劃的對(duì)偶問題化為 s.t. 沒有限制。 對(duì)照原線性規(guī)劃問題，我們可以知道： 當(dāng)原線性規(guī)劃問題的第當(dāng)原線性規(guī)劃問題的第i個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問題的個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問題的 i個(gè)決策變量沒有非個(gè)決策變量沒有非負(fù)限制。負(fù)限制。 如果當(dāng)原線性規(guī)劃問題中的第如果當(dāng)原線性規(guī)劃問題中的第 i個(gè)決策變量個(gè)決策變量 沒有非負(fù)限制時(shí)，我們也可以用沒有非負(fù)限制時(shí)，我們也可以用 進(jìn)行替換，這里進(jìn)

38、行替換，這里 ， ，用類似的方法知道其對(duì)偶問題中第，用類似的方法知道其對(duì)偶問題中第 i個(gè)個(gè)約束條件取等號(hào)。約束條件取等號(hào)。3 33yyy3 3yy 0y3 3yy 03y, 0,3 3yy3y3y321200100440minyyyf, 0, 66, 4343, 356221321321321yyyyyyyyyyy3yixiiixxx 0ix0 ix2 2 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)52 原線性規(guī)劃問題為： s.t. 無非負(fù)限制。321493minxxxf, 0,24035,6032,180322121321321xxxxxxxxxx3x2 2 線性規(guī)劃的

39、對(duì)偶問題線性規(guī)劃的對(duì)偶問題管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)53上節(jié)回顧 1.對(duì)偶問題的定義 任何一個(gè)求極大化的線性規(guī)劃問題都有一個(gè)求極小化的線任何一個(gè)求極大化的線性規(guī)劃問題都有一個(gè)求極小化的線性規(guī)劃問題與之對(duì)應(yīng)，反之亦然，如果我們把其中一個(gè)叫性規(guī)劃問題與之對(duì)應(yīng)，反之亦然，如果我們把其中一個(gè)叫原問題，則另一個(gè)就叫做它的對(duì)偶問題，并稱這一對(duì)互相原問題，則另一個(gè)就叫做它的對(duì)偶問題，并稱這一對(duì)互相聯(lián)系的兩個(gè)問題為一對(duì)對(duì)偶問題。聯(lián)系的兩個(gè)問題為一對(duì)對(duì)偶問題。 2.原問題與對(duì)偶問題的關(guān)系a 求目標(biāo)函數(shù)最大值的線性規(guī)劃問題中有求目標(biāo)函數(shù)最大值的線性規(guī)劃問題中有n 個(gè)變量個(gè)變量 m個(gè)約束條個(gè)約束條件，它的約束條件

40、都是小于等于不等式。而其對(duì)偶則是求件，它的約束條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問題，有目標(biāo)函數(shù)為最小值的線性規(guī)劃問題，有m個(gè)變量個(gè)變量n個(gè)約束條個(gè)約束條件，其約束條件都為大于等于不等式。件，其約束條件都為大于等于不等式。b 原問題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問題中的約束條件原問題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問題中的約束條件的右邊常數(shù)項(xiàng)。的右邊常數(shù)項(xiàng)。c 原問題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問題的目標(biāo)函數(shù)中原問題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問題的目標(biāo)函數(shù)中的變量的系數(shù)。的變量的系數(shù)。d 對(duì)偶問題的約束條件的系數(shù)矩陣對(duì)偶問題的約束條件的系數(shù)矩陣A是原問題約束矩陣的轉(zhuǎn)置

41、。是原問題約束矩陣的轉(zhuǎn)置。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)54 3.如何根據(jù)原問題的結(jié)果去找對(duì)偶問題的答案 對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃的問題，我們只對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃的問題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問題的要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問題的對(duì)偶價(jià)格而求得其對(duì)偶問題的最優(yōu)解，知道其中對(duì)偶價(jià)格而求得其對(duì)偶問題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問題的最優(yōu)值一個(gè)最優(yōu)值也就找到了其對(duì)偶問題的最優(yōu)值 4.如何將原問題轉(zhuǎn)化成對(duì)偶問題 當(dāng)原線性規(guī)劃問題的第當(dāng)原線性規(guī)劃問題的第i個(gè)約束條件取等號(hào)時(shí)，則個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問題的其對(duì)偶問題的 i個(gè)決策變量沒有非負(fù)限

42、制。個(gè)決策變量沒有非負(fù)限制。 如果當(dāng)原線性規(guī)劃問題中的第如果當(dāng)原線性規(guī)劃問題中的第 i個(gè)決策變量沒有非個(gè)決策變量沒有非負(fù)限制時(shí)，其對(duì)偶問題中第負(fù)限制時(shí)，其對(duì)偶問題中第 i個(gè)約束條件取等號(hào)。個(gè)約束條件取等號(hào)。 5.對(duì)偶規(guī)劃的基本性質(zhì)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)553 3對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì) 1對(duì)稱性對(duì)稱性。即對(duì)偶問題的對(duì)偶是原問題。 2弱對(duì)偶性弱對(duì)偶性。即對(duì)于原問題（）和對(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ì)偶問題