管理運籌學(xué) 第6章 單純形法的靈敏度分析與對偶ppt課件

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

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

3、, aKj , amj) ZJ=(CB1, CB2。, Ck+ Ck,，CBm)(a1j , a2j , aKj , amj) = ZJ + Ck aKj TT管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析根據(jù)上式可知 檢驗數(shù) J (J=1,2,.,M)變成了 J,有 J=CJ-ZJ= J+ CK aKj 。要使最優(yōu)解不變，只需當J K時， J 0，就可求出 的取值范圍，也就是使得第K個約束條件的對偶價錢不變的bk的變化范圍。 ，-1-1-1BXB .(bb)BbBb 。kbmkk3kk2kk1kk1-21kdb.dbdbdbbB,.D則mkkkdddmkk2kk

4、1kk21BBdb.dbdb.XXBmBBXXX有新的最優(yōu)解為管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析下面我們?nèi)砸缘诙吕?在最終單純形表上對bj 進展靈敏度分析。最終單純形表如下所示：BkkX00bMax|0bMin|0BiBiikikikikxxdddd 要使也就是各個分量均不小于 ，用一個數(shù)學(xué)式子來表示的允許變化范圍是迭代次數(shù)基變量CBX1 X2 S1 S2 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

5、-50 0 -50管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析 我們對b1進展靈敏度分析，由于在第一個約束方程中含有松弛變量S1, 實踐意義可以描畫為：當設(shè)備臺時數(shù)的對偶價錢不變，都為每設(shè)備臺時數(shù)在250與325之間變化，那么設(shè)備臺時數(shù)的對偶價錢不變，都為每臺設(shè)備臺時50元。的第一列。就是），純形表中的系數(shù)列（所以松弛變量在最終單-1TB021 變。約束條件的對偶價格不第一個即故有當而可以因為325bb250,25b50,250|Min500|Max,50X,50X, 02d, 01d11111212111iiBiiiBiddxddx管管 理理 運運 籌籌 學(xué)學(xué)

6、1 1 單純形表的靈敏度分析單純形表的靈敏度分析三、約束方程系數(shù)矩陣A靈敏度分析下面分兩種情況討論 1.在初始單純形表上的變量Xk的系數(shù)列Pk改動為Pk經(jīng)過迭代后，在最終單純形表上Xk是非基變量。由于單純形表的迭代是約束方程的增廣矩陣的行變換，Pk變成Pk僅僅影響最終單純形表上第k列數(shù)據(jù)，包括Xk的系數(shù)列、Zk以及 k，這時最終單純形表上的Xk的系數(shù)列就變成了B-1Pj,而Zk就變成CBB-1Pk，新的檢驗數(shù) k=Ck-CBB-1Pk。假設(shè) k0，那么原最優(yōu)解依然為最優(yōu)解。假設(shè) k 0，那么繼續(xù)進展迭代以求出最優(yōu)。 例 以第二章例1為根底，設(shè)該廠除了消費，種產(chǎn)品外，如今試制成一個新產(chǎn)品，知消費

7、產(chǎn)品,每件需求設(shè)備2臺時，并耗費A原料0.5公斤。B原料1.5公斤，獲利150元，問該廠應(yīng)該消費該產(chǎn)品多少？解：這是一個添加新變量的問題。我們可以把它以為是一個改動變量X3在初始表上的系數(shù)列的問題，管管 理理 運運 籌籌 學(xué)學(xué)1 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)解就是新問這時新變量如下表所示這時就變成了上是非基變量，在最終表之后的第六列上，顯然把

8、它放在的一列，上添上新的一列變量，。這樣在原來的最終表變成從ZCZXSX迭代次數(shù)基變量CBX1 X2 S1 S2 S3 X3 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管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析例 假設(shè)上例題中產(chǎn)品的工藝構(gòu)造有了改良，這時消費1件產(chǎn)品需求運用1.5臺設(shè)備 ，耗費原料A為2千克，原料B為1千克，每件產(chǎn)品的利潤為160元，問

9、該廠的消費方案能否要修正。 解：首先求出X3在最終表上的系數(shù)列 61PB填入下表,35,125100.5(50,0,100),105 . 0125 . 1111010021PB66661ZCzj迭代次數(shù)基變量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1502X1501 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管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析接下來

10、又可以有新的迭代S3進基，6310,3,XX由于可知此解不是最優(yōu)解 我們要進行第 次迭代 選為入基變量，為出基變量迭代次數(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管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析接上頁 可知此規(guī)模的最優(yōu)解X1=0, X2=0, S1=0, S2=0,

11、S3=50, X3=200,此時，最大目的函數(shù)為32000元。也就是說，該廠的新的消費方案為不消費、產(chǎn)品，消費產(chǎn)品200件, 可獲得最大利潤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管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析 2.在初始表上的變量XK的系數(shù)PK改動為P

12、K，經(jīng)過迭代后，在最終表上XK是基變量，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都能夠被破壞，問題非常復(fù)雜，普通不去修正原表而是直接計算。管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析四、添加一個約束條件的靈敏度分析 在原線性規(guī)劃中添加一個約束條件時在原線性規(guī)劃中添加一個約束條件時, ,先將原問題的最先將原問題的最優(yōu)解的變量值代入新增的約束條件，如滿足那么闡明新增的優(yōu)解的變量值代入新增的約束條件，如滿足那么闡明新增的條件沒有起到限制造用，故原最優(yōu)解不變，否那么將新增的條件沒有起到限制造用，故原最優(yōu)解不變，否那么將新增的約束添入原最終單純形表上進一步求解。約束添入原最終

13、單純形表上進一步求解。 下面仍以第三章例下面仍以第三章例1 1為例來加以闡明。為例來加以闡明。 例：假設(shè)該工廠除了在設(shè)備臺時，原資料例：假設(shè)該工廠除了在設(shè)備臺時，原資料A A、B B上對該廠上對該廠的消費有限制外，還有電力供應(yīng)上的限制。最高供應(yīng)電量為的消費有限制外，還有電力供應(yīng)上的限制。最高供應(yīng)電量為50005000度，而消費一個度，而消費一個產(chǎn)品需求用電產(chǎn)品需求用電1010度，而消費一個度，而消費一個產(chǎn)產(chǎn)品需求用電品需求用電3030度。試分析此時該廠獲得最大利潤的消費方案？度。試分析此時該廠獲得最大利潤的消費方案？管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析

14、1x2x解：先將原問題的最優(yōu)解=50=50，=250代入用電量的約束條件得：1050+30250=500+75005000,所以原題的最優(yōu)解不是此題的最優(yōu)解。在用電量的約束條件中參與松馳變量S4后得：12410 x +30 x +s =5000把這個約束條件參與到原最終單純形表上，其中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 02

15、502500 0101030300 00 00 01 150005000505010010050500 050500 0275027500 00 00 0-50-500 0-50-500 0jjjcz1210305000 xx管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析 在上表中的X1，X2不是單位向量，故進展行的線性變換，得迭代迭代次數(shù)次數(shù)基變量基變量CBCBx1x1x2x2s1s1s2s2s3s3s4s4b b比比值值50501001000 00 00 00 0 x1x150501 10 01 10 0-1-10 05050s2s20 00 00 0-2-2

16、1 11 10 05050 x2x21001000 01 10 00 01 10 0250250s4s40 00 00 0-10-100 0-20-201 1-3000-3000zjzj505010010050500 050500 027500275000 00 0-50-500 0-50-500 0把上表中的S4行的約束可以寫為ss 上式兩邊乘以-1，再加上人工變量a1得：134110203000sssa用上式交換上表中的S4行，得下表：jjjcz管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析迭代迭代次數(shù)次數(shù)基變基變量量x1x1x2x2

17、s1s1s2s2s3s3s4s4a1a1b b比值比值50501001000 00 00 00 0-M-Mx1x150501 10 01 10 0-1-10 00 05050s2s20 00 00 0-2-21 1(1)(1)0 00 05050 x2x21001000 01 10 00 01 10 00 0250250s4s4-M-M0 00 0-10-100 0-20-201 11 130003000zjzj505010010050-10M50-10M0 050-20M50-20M0 0-M-M0 00 010M-5010M-500 020M-5020M-500 00 0 x1x15050

18、1 10 0-1-11 100 00 0100100s3s30 00 00 0-2-21 11 10 00 05050 x2x21001000 01 12 2-1-10 00 00 0200200s4s4-M-M0 00 05050-20-200 0-1-11 120002000zjzj5050100100150-50M150-50M20M-5020M-500 0M M-M-M0 050M-15050M-15050-20M50-20M0 0-M-M0 0 x1x150501 10 00 03/53/50 0-1/50-1/501/501/50140140s3s30 00 00 00 01/51

19、/51 1-2/50-2/502/502/50130130 x2x21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120s4s40 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040zjzj50501001000 010100 03 3-3-30 00 0-10-100 0-3-3-M+3-M+3jjjczjjjczjjjcz管管 理理 運運 籌籌 學(xué)學(xué)1 1 單純形表的靈敏度分析單純形表的靈敏度分析 由上表可知，最優(yōu)解為：1212311401200 xxsssa 即該工廠在添加了用電限量以后的最優(yōu)消費方案為產(chǎn)

20、品消費140件，產(chǎn)品消費120件。管管 理理 運運 籌籌 學(xué)學(xué) 每一個線性規(guī)劃問題，都存在每一個與它親密相關(guān)的線性規(guī)劃的問題，我們稱其為原問題，另一個為對偶問題。例題1 某工廠在方案期內(nèi)安排、兩種產(chǎn)品，消費單位產(chǎn)品所需設(shè)備A、B、C臺時如表所示 該工廠每消費一單位產(chǎn)品 可獲利50元，每消費一單位產(chǎn)品可獲利100元，問工廠應(yīng)分別消費多少 產(chǎn)品和產(chǎn)品，才干使工廠獲利最多？解：設(shè) 為產(chǎn)品 的方案產(chǎn)量， 為產(chǎn)品的方案產(chǎn)量，那么有目的函數(shù)： Max z=50 +100約束條件： ， 資源限量 設(shè)備 A 1 1 300 臺時 設(shè)備 B 2 1 400 臺時 設(shè)備 C 0 1 250 臺時 1x2x3002

21、1 xx400221 xx2x2502x1x02 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 如今我們從另一個角度來思索這個問題。假設(shè)有另外一個工廠要求租用該廠的設(shè)備A、B、C，那么該廠的廠長應(yīng)該如何來確定合理的租金呢？ 設(shè) 分別為設(shè)備A、B、C的每臺時的租金。為了表達方便，這里把租金定義為扣除本錢后的利潤。作為出租者來說，把消費單位 產(chǎn)品所需各設(shè)備的臺時各總租金不應(yīng)低于原利潤50元，即 ，否那么就不出租還是用于消費 產(chǎn)品以獲利50元；同樣把 消費一單位 產(chǎn)品所需各設(shè)備的臺時的總租金也不該當?shù)陀谠麧?00元， 即，否那么這些設(shè)備臺時就不出租，還是用于消費 產(chǎn)品以獲利

22、100元。但對于租用者來說，他要求在滿足上述要求的前提下，也就是在出租者情愿出租的前提下盡量要求全部設(shè)備臺時的總租金越低越好，即min ，這樣我們得到了該問題的數(shù)學(xué)模型： 目的函數(shù)： 約束條件： 這樣從兩個不同的角度來思索同一個工廠的最大利潤最小租金的問題，所建立起來的兩個線性模型就是一對對偶問題，其中一個叫做原問題，而另外一個叫對偶問題。3, 21,yyy321250400300minyyyf50221 yy100321yyy321250400300yyy0,10050232132121yyyyyyyy2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 假設(shè)我們把求目的

23、函數(shù)最大值的線性規(guī)劃問題看成原問題，那么求目的函數(shù)最小值的線性規(guī)劃問題看成對偶問題。下面來研討這兩個問題在數(shù)學(xué)模型上的關(guān)系。 1 求目的函數(shù)最大值的線性規(guī)劃問題中有n 個變量 m個約束條件，它的約束條件都是小于等于不等式。而其對偶那么是求目的函數(shù)為最小值的線性規(guī)劃問題，有m個變量n個約束條件，其約束條件都為大于等于不等式。 2 原問題的目的函數(shù)中的變量系數(shù)為對偶問題中的約束條件的右邊常數(shù)項，并且原問題的目的函數(shù)中的第i個變量的系數(shù)就等于對偶問題中的第i個約束條件的右邊常數(shù)項。 3 原問題的約束條件的右邊常數(shù)項為對偶問題的目的函數(shù)中的變量的系數(shù)。并且原問題的第i個約束條件的右邊常數(shù)項就等于零對偶

24、問題的目的函數(shù)中的第i個變量的系數(shù)。 4 對偶問題的約束條件的系數(shù)矩陣A是原問題約束矩陣的轉(zhuǎn)置。 設(shè) A=那么 mnmmnaaaaaa.21112112 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題mnnnmTaaaaaaA2112111管管 理理 運運 籌籌 學(xué)學(xué)假設(shè)我們用矩陣方式來表示，那么有原問題： 其中A是 矩陣m*n，該問題有m個約束條件n個變量，x= ,b= , c= 對偶問題： 其中 是A的轉(zhuǎn)置， 是b的轉(zhuǎn)置, 是c的轉(zhuǎn)置, y= 如今我們用單純形法求對偶問題的解。0,maxxbAxcxz).,.,(21ncccTmbbb),.,(21TATbTCTmyyy),.,(210.miny

25、cyAybfTTT2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題Tnxxx,21管管 理理 運運 籌籌 學(xué)學(xué) 加上剩余變量 和人工變量 ，把此問題化成規(guī)范型如下：把上述數(shù)據(jù)填入單純形表計算。21,ss1a1321500400300)max(Mayyyf0,10050212132123211121assyyysyyyasyy2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué)迭代變量基變量 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-2500

26、0M-2502M-1500-M-25002-4001/210-1/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ī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 由上表，最優(yōu)解： =50， -f 的最大值為-27500，即目的

27、函數(shù)f的最大值為f=27500元。 從上面可知租金：A設(shè)備為50元，B設(shè)備為0元，C設(shè)備為50元。這樣把工廠的一切設(shè)備出租可共得租金27500元。對出租者來說這租金是出租者情愿出租設(shè)備的最小費用，由于這是目 標函數(shù)的最小值。 經(jīng)過比較，我們發(fā)現(xiàn)：對偶問題的最優(yōu)解即最正確租金恰好等于原問題各種設(shè)備的對偶價錢，這在道理上也能講得通。 對于兩個有對偶關(guān)系的線性規(guī)劃的問題，我們只需求得了其中一個最優(yōu)解，就可以從這個問題的對偶價錢而求得其對偶問題的最優(yōu)解，知道其中一個最優(yōu)值也就找到了其對偶問題的最優(yōu)值，由于這兩個最優(yōu)值相等。 1y0, 0, 0,50, 012132assyy2 2 線性規(guī)劃的對偶問題線

28、性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 下面來論述如何寫出一個線性規(guī)劃問題的對偶問題。為了便于論述，我們無妨以下面的線性規(guī)劃為例，寫出它的對偶問題。 S.T. 321643maxxxxz0,20035,10046,440632321321321321xxxxxxxxxxxx2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 這是一個求最大值的線性規(guī)劃問題，為了寫出它的對偶問題，我們無妨把它的約束條件都變換成取小于號的不等式。顯然第一個約束條件已符合要求，不要做任何變動，而第二個約束條件，我們只需兩邊都乘以-1，使不等號方向改動即可，得 這樣第二個約束條件也就符合要求

29、。對于第三個約束條件，我們可以用小于等于和大于等于兩個約束條件來替代它。即有 顯然，這兩個約束條件與原來第三個約束條件是等價的，我們再把其中的兩邊都乘以-1，得 10046321xxx2003520035321321xxxxxx20035321xxx20035321xxx2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 經(jīng)過上面的一些變換，我們得到了一個和原線性規(guī)劃等價的線性規(guī)劃問題： s.t. 321643maxxxxz0,2003520035,10046,440632321321321321321xxxxxxxxxxxxxxx2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶

30、問題管管 理理 運運 籌籌 學(xué)學(xué) 這個求最大值的線性規(guī)劃問題的約束條件都取小于等于號，我們馬上可以寫出其對偶問題： s.t.3 321200200100440minyyyyf, 0, 66, 43343, 355623 3213 3213 3213 321yyyyyyyyyyyyyyyy2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 這里 和 一樣都是不同的決策變量，為了表示這兩個決策變量都來源于原問題的第三個約束條件，記為 。 由于在該對偶問題中 和 的系數(shù)只相差一個符號，我們可以把上面的對偶問題化為： s.t.3 3, yy21, yy3y3 y)(2001004

31、40min3 321yyyyf, 0, 6)(6, 4)(343, 3)(5623 3213 3213 3213 321yyyyyyyyyyyyyyyy2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題3 3, yy管管 理理 運運 籌籌 學(xué)學(xué) 進一步，我們可以令 ，這時當 時， ，當 時， 。這也就是說，雖然 但 的取值可以為正，可以為0，可以為負，即 沒有非負限制。 這樣我們把原規(guī)劃的對偶問題化為 s.t. 沒有限制。 對照原線性規(guī)劃問題，我們可以知道： 當原線性規(guī)劃問題的第i個約束條件取等號時，那么其對偶問題的 i個決策變量沒有非負限制。 假設(shè)當原線性規(guī)劃問題中的第 i個決策變量 沒有非負限制

32、時，我們也可以用 進展交換，這里 ， ，用類似的方法知道其對偶問題中第 i個約束條件取等號。3 33yyy3 3yy 0y3 3yy 03y, 0,3 3yy3y3y321200100440minyyyf, 0, 66, 4343, 356221321321321yyyyyyyyyyy3yixiiixxx 0ix0 ix2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué) 另外，用大于等于0的兩個決策變量之差來替代無非負限制的決策變量也是求解含有無非負限制的決策變量的線性規(guī)劃問題的一種方法。 原線性規(guī)劃問題為： s.t. 無非負限制。321493minxxxf, 0,240

33、35,6032,180322121321321xxxxxxxxxx3x2 2 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題管管 理理 運運 籌籌 學(xué)學(xué)3 3 對偶規(guī)劃的根本性質(zhì)對偶規(guī)劃的根本性質(zhì)對偶規(guī)劃的根本性質(zhì)對偶規(guī)劃的根本性質(zhì)1對稱性。即對偶問題的對偶是原問題。對稱性。即對偶問題的對偶是原問題。2弱對偶性。即對于原問題弱對偶性。即對于原問題和對偶問題和對偶問題的可行的可行解解 都有都有C bT 。 由弱對偶性，可得出以下推論：由弱對偶性，可得出以下推論：1原問題任一可行解的目的函數(shù)值是其對偶問標題的函數(shù)原問題任一可行解的目的函數(shù)值是其對偶問標題的函數(shù)值的下界；反之對偶問題任一可行解的目的函數(shù)值是其

34、原值的下界；反之對偶問題任一可行解的目的函數(shù)值是其原問標題的函數(shù)值的上界。問標題的函數(shù)值的上界。2如原問題有可行解且目的函數(shù)值無界或具有無界解，如原問題有可行解且目的函數(shù)值無界或具有無界解，那么其對偶問題無可行解；反之對偶問題有可行解且目的那么其對偶問題無可行解；反之對偶問題有可行解且目的函數(shù)值無界，那么其原問題無可行解留意：本點性質(zhì)的函數(shù)值無界，那么其原問題無可行解留意：本點性質(zhì)的逆不成立，當對偶問題無可行解時，其原問題或具有無界逆不成立，當對偶問題無可行解時，其原問題或具有無界解或無可行解，反之亦然。解或無可行解，反之亦然。3假設(shè)原問題有可行解而其對偶問題無可行解，那么原問假設(shè)原問題有可行解而其對偶問題無可行解，那么原問標題的函數(shù)值無界；反之對偶問題有可行解而其原問題無標題的函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，那么對偶問題的目的函數(shù)值無界?？尚薪猓敲磳ε紗栴}的目的函數(shù)值無界。YX,XY管管 理理 運運 籌籌 學(xué)學(xué)3