第6章單純形法的靈敏度分析與對偶

第六章單純形法的靈敏度分析與對偶§1單純形表的靈敏度分析§2線性規(guī)劃的對偶問題§3對偶規(guī)劃的基本性質§4對偶單純形法1§1單純形表的靈敏度分析一、目標函數中變量Ck系數靈敏度分析1.在最終的單純形表里，X

k是非基變量

由于約束方程系數增廣矩陣在迭代中只是其本身的行的初等變換與Ck沒有任何關系，所以當Ck變成Ck+Ck時，在最終單純形表中其系數的增廣矩陣不變，又因為Xk是非基變量，所以基變量的目標函數的系數不變，即CB不變，可知Zk也不變，只是Ck變成了Ck+Ck。這時K=Ck-Zk就變成了Ck+Ck-Zk=K+Ck。要使原來的最優(yōu)解仍為最優(yōu)解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。2.在最終的單純形表中，X

k是基變量

當Ck變成Ck+Ck時，最終單純形表中約束方程的增廣矩陣不變，但是基變量的目標函數的系數CB變了，則ZJ(J=1,2,…..,N)一般也變了，不妨設CB=(CB1,

CB2。。。,Ck,…，CBm),當CB變成=(CB1,

CB2。。。,Ck+Ck,…,CBm),則：

ZJ=(CB1,

CB2。。。,Ck,…，CBm)(a’1j,a’2j,…,a’Kj

,…,a’mj)Z’J=(CB1,

CB2。。。,Ck+Ck,…，CBm)(a’1j,a’2j,…,a’Kj

,…,a’mj)=ZJ+

Cka’Kj

2§1單純形表的靈敏度分析根據上式可知檢驗數J(J=1,2,…..,M)變成了’J,有

’

J=CJ-Z’J=J+CKa’Kj

。要使最優(yōu)解不變，只要當JK時，’J<=0

3§1單純形表的靈敏度分析例：目標函數：Maxz=50X1+100X2

約束條件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最優(yōu)單純形表如下迭代次數基變量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-504§1單純形表的靈敏度分析

我們先對非基變量S1的目標函數的系數C3進行靈敏度分析。這里δ3=-50，所以當c3的增量Δc3≤50，最優(yōu)解不變。再對基變量x1的目標函數的系數c1進行靈敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和

a13’大于0，a15’小于0，可知，有。同樣有。這樣可以知道當-50≤Δc1≤50時，也就是x1的目標函數c1’在0≤c1’≤100時最優(yōu)解不變。在最終的單純形表中，用C’1代替原來的C1=50,計算得表5§1單純形表的靈敏度分析迭代次數基變量CBX1X2S1S2S3b501000002X1C’11010-150

S2000-21150

X210001001250

ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-100

從δ3≤0，得到-c1’≤0,即c1’≥0，并且從δ5≤0，得到c1’≤100。那么如果c1’取值超出這個范圍，必然存在一個檢驗數大于0，我們可以通過迭代來得到新的最優(yōu)解。6§1單純形表的靈敏度分析二、約束方程中常數項的靈敏度分析

從上表我們可以發(fā)現各個松弛變量的值，正好等于相應變量的對偶價格。在最優(yōu)解中S2=50是基變量，即為，原料A有50千克沒用完，再增加A原料是不會增加利潤的，

A的對偶價格為0。對于任何為基變量的松弛變量所對應的約束條件的對偶價格為0。迭代次數基變量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-507§1單純形表的靈敏度分析

可以看出，上題中對于設備臺時數約束來說，當其松弛變量在目標函數中從0變到Z3=50時，也就是只要當前余下一臺時數設備從不能獲利變成獲利50元時，譬如有人愿意出50元買一個設備時，我們就不必為生產Ι、П產品而使用完所有的設備臺時了，這說明了設備臺時數的對偶價格就是Z3=50元。對于含有大于等于號的約束條件，添加剩余變量化為標準型。這時這個約束條件的對偶價格就和這個剩余變量的有關了。這將使得最優(yōu)目標值特別“惡化”而不是改進，故這時約束條件的對偶價格應取值的相反數-。

對于含有等于號的約束條件，其約束條件的對偶價格就和該約束方程的人工變量有關了。其約束條件的對偶價格就等于此約束方程的人工變量的值。

8下表給出了一個由最終單純形表對于不同約束類型的對偶價格的取值。

從對偶價格的定義,可以知道當對偶價格為正時它將改進目標函數的值，當對偶價格為負時它將使得目標函數朝著與最優(yōu)化相反的方向前進。

下面我們研究當右端項bj發(fā)生變化時，在什么范圍內其對偶價格不變。由于bj的變化并不影響系數矩陣的迭代，故其最終單純形表中的系數矩陣沒有變化。由此可見當bj變化時，要使原來的基不變得到的基本可行解仍然是可行解，也就是所求的基變量的值一定要大于0。所謂使其對偶價格不變的bj的變化范圍，也就是使其最優(yōu)解的所有基變量不變，且所得的最優(yōu)解仍然是可行的bj的變化范圍。約束條件影子價格的取值

≤等于這個約束條件對應的松弛變量的值,即為的相反數

≥等于這個約束條件對應的剩余變量的值,即為的相反數

=等于這個約束條件對應的人工變量的值,即為的相反數

§1單純形表的靈敏度分析9§1單純形表的靈敏度分析

當bj中的第k項bK

變成

時，也就是原來的初始單純形表中的b向量變成了b’向量10§1單純形表的靈敏度分析這樣在最終單純形表中基變量XB的解就變成了如要使XB成為可行解，只要使上述等式的右邊>0，就可求出的取值范圍，也就是使得第K個約束條件的對偶價格不變的bk的變化范圍。，11§1單純形表的靈敏度分析下面我們仍以第二章例1在最終單純形表上對bj

進行靈敏度分析。最終單純形表如下所示：迭代次數基變量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-5012§1單純形表的靈敏度分析我們對b1進行靈敏度分析，因為在第一個約束方程中含有松弛變量S1,

實際意義可以描述為：當設備臺時數的對偶價格不變，都為每設備臺時數在250與325之間變化，則設備臺時數的對偶價格不變，都為每臺設備臺時50元。13§1單純形表的靈敏度分析三、約束方程系數矩陣A靈敏度分析下面分兩種情況討論

1.在初始單純形表上的變量Xk的系數列Pk改變?yōu)镻’k經過迭代后，在最終單純形表上Xk是非基變量。由于單純形表的迭代是約束方程的增廣矩陣的行變換，Pk變成Pk’僅僅影響最終單純形表上第k列數據，包括Xk的系數列、Zk以及k，這時最終單純形表上的Xk的系數列就變成了B-1Pj’,而Zk就變成CBB-1Pk’，新的檢驗數k=Ck-CBB-1Pk’。若k≤0，則原最優(yōu)解仍然為最優(yōu)解。若k〉0，則繼續(xù)進行迭代以求出最優(yōu)。例以第二章例1為基礎，設該廠除了生產Ι，Ⅱ種產品外，現在試制成一個新產品Ⅲ，已知生產產品Ⅲ,每件需要設備2臺時，并消耗A原料0.5公斤。B原料1.5公斤，獲利150元，問該廠應該生產該產品多少？解：這是一個增加新變量的問題。我們可以把它認為是一個改變變量X3在初始表上的系數列的問題，14§1單純形表的靈敏度分析接上頁迭代次數基變量CBX1X2S1S2S3X3b50100000150X1501010-10.550

S2000-211-250

X2100010011.5250

ZJ501005005017527500CJ-ZJ00-500-50-2515§1單純形表的靈敏度分析例假設上例題中產品Ш的工藝結構有了改進，這時生產1件Ш產品需要使用1.5臺設備，消耗原料A為2千克，原料B為1千克，每件Ш產品的利潤為160元，問該廠的生產計劃是否要修改。解：首先求出X3在最終表上的系數列

迭代次數基變量CBX1X2S1S2S3X3b501000001502X1501010-10.55050/0.5

S2000-211050

X2100010011250250/1

ZJ501005005012527500CJ-ZJ00-500-503516§1單純形表的靈敏度分析接下來又可以有新的迭代S3進基，迭代次數基變量CBX1X2S1S2S3X3b501000001503X31602020-21100---

S2000-21105050/1

X2100-201-2030150250/3

ZJ1201001200-2016031000CJ-ZJ-700-120020017§1單純形表的靈敏度分析接上頁可知此規(guī)模的最優(yōu)解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此時，最大目標函數為32000元。也就是說，該廠的新的生產計劃為不生產Ι、П產品，生產Ш產品200件,可獲得最大利潤32000元。迭代次數基變量CBX1X2S1S2S3X3b501000001504X31602020-21200---

S3000-21105050/1

X2100-214-3000250/3

ZJ1201008020016032000CJ-ZJ-700-80-200018§1單純形表的靈敏度分析

2.在初始表上的變量XK的系數PK改變?yōu)镻’K，經過迭代后，在最終表上XK是基變量，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問題十分復雜，一般不去修改原表而是直接計算。19§1單純形表的靈敏度分析四、增加一個約束條件的靈敏度分析

在原線性規(guī)劃中增加一個約束條件時,先將原問題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說明新增的條件沒有起到限制作用，故原最優(yōu)解不變，否則將新增的約束添入原最終單純形表上進一步求解。下面仍以第三章例1為例來加以說明。例：假如該工廠除了在設備臺時，原材料A、B上對該廠的生產有限制外，還有電力供應上的限制。最高供應電量為5000度，而生產一個Ⅰ產品需要用電10度，而生產一個Ⅱ產品需要用電30度。試分析此時該廠獲得最大利潤的生產計劃？20§1單純形表的靈敏度分析

解：先將原問題的最優(yōu)解=50，=250代入用電量的約束條件得：10×50+30×250=500+7500>5000,所以原題的最優(yōu)解不是本題的最優(yōu)解。在用電量的約束條件中加入松馳變量S4后得：把這個約束條件加入到原最終單純形表上，其中S4為基變量，得表如下：迭代次數基變量b比值501000000501010-1050000-2110501000100102500103000015000501005005002750000-500-50021§1單純形表的靈敏度分析

在上表中的X1，X2不是單位向量，故進行行的線性變換，得迭代次數基變量CBx1x2s1s2s3s4b比值501000000x1501010-1050s2000-211050x2100010010250s4000-100-201-3000zj501005005002750000-500-500把上表中的S4行的約束可以寫為：上式兩邊乘以（-1），再加上人工變量a1得：用上式替換上表中的S4行，得下表：22§1單純形表的靈敏度分析迭代次數基變量x1x2s1s2s3s4a1b比值501000000-Mx1501010-10050s2000-21(1)0050x21000100100250s4-M00-100-20113000zj5010050-10M050-20M0-M0010M-50020M-5000

x15010-11000100

s3000-2110050

x2100012-1000200

s4-M0050-200-112000

zj50100150-50M20M-500M-M

050M-15050-20M0-M0

x1501003/50-1/501/50140

s300001/51-2/502/50130

x2100010-1/502/50-2/50120

s40001-2/50-1/501/5040

zj5010001003-3

00-100-3-M+3

23§1單純形表的靈敏度分析

由上表可知，最優(yōu)解為：

即該工廠在添加了用電限量以后的最優(yōu)生產計劃為Ⅰ產品生產140件，Ⅱ產品生產120件。24每一個線性規(guī)劃問題，都存在每一個與它密切相關的線性規(guī)劃的問題，我們稱其為原問題，另一個為對偶問題。例題1

某工廠在計劃期內安排Ⅰ、Ⅱ兩種產品，生產單位產品所需設備A、B、C臺時如表所示

該工廠每生產一單位產品可獲利50元，每生產一單位產品Ⅱ可獲利100元，問工廠應分別生產多少產品和Ⅱ產品，才能使工廠獲利最多？解：設為產品的計劃產量，為產品Ⅱ的計劃產量，則有目標函數：Maxz=50+100約束條件：

，§2線性規(guī)劃的對偶問題25現在我們從另一個角度來考慮這個問題。假如有另外一個工廠要求租用該廠的設備A、B、C，那么該廠的廠長應該如何來確定合理的租金呢？設分別為設備A、B、C的每臺時的租金。為了敘述方便，這里把租金定義為扣除成本后的利潤。作為出租者來說，把生產單位產品所需各設備的臺時各總租金不應低于原利潤50元，即，否則就不出租還是用于生產產品以獲利50元；同樣把生產一單位產品所需各設備的臺時的總租金也不應當低于原利潤100元，即，否則這些設備臺時就不出租，還是用于生產產品以獲利100元。但對于租用者來說，他要求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設備臺時的總租金越低越好，即min，這樣我們得到了該問題的數學模型：

目標函數：約束條件：這樣從兩個不同的角度來考慮同一個工廠的最大利潤（最小租金）的問題，所建立起來的兩個線性模型就是一對對偶問題，其中一個叫做原問題，而另外一個叫對偶問題?！?線性規(guī)劃的對偶問題26如果我們把求目標函數最大值的線性規(guī)劃問題看成原問題，則求目標函數最小值的線性規(guī)劃問題看成對偶問題。下面來研究這兩個問題在數學模型上的關系。

1求目標函數最大值的線性規(guī)劃問題中有n個變量m個約束條件，它的約束條件都是小于等于不等式。而其對偶則是求目標函數為最小值的線性規(guī)劃問題，有m個變量n個約束條件，其約束條件都為大于等于不等式。

2原問題的目標函數中的變量系數為對偶問題中的約束條件的右邊常數項，并且原問題的目標函數中的第i個變量的系數就等于對偶問題中的第i個約束條件的右邊常數項。

3原問題的約束條件的右邊常數項為對偶問題的目標函數中的變量的系數。并且原問題的第i個約束條件的右邊常數項就等于零對偶問題的目標函數中的第i個變量的系數。

4對偶問題的約束條件的系數矩陣A是原問題約束矩陣的轉置。

設

A=則

§2線性規(guī)劃的對偶問題27如果我們用矩陣形式來表示，則有原問題：

其中A是矩陣m*n，該問題有m個約束條件n個變量，x=,b=,c=

對偶問題：

其中是A的轉置，是b的轉置,是c的轉置,y=現在我們用單純形法求對偶問題的解?！?線性規(guī)劃的對偶問題28

加上剩余變量和人工變量，把此問題化成標準型如下：把上述數據填入單純形表計算?！?線性規(guī)劃的對偶問題29迭代變量基變量b-300-400-25000-M

1-M1②

0-1015050/2-2501110-10100100/1-M-250-2M-250-250M250-M-50M-25000M-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+50§2線性規(guī)劃的對偶問題30

由上表，最優(yōu)解：=50，

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

§2線性規(guī)劃的對偶問題31

下面來闡述如何寫出一個線性規(guī)劃問題的對偶問題。為了便于闡述，我們不妨以下面的線性規(guī)劃為例，寫出它的對偶問題。

S.T.

§2線性規(guī)劃的對偶問題32

這是一個求最大值的線性規(guī)劃問題，為了寫出它的對偶問題，我們不妨把它的約束條件都變換成取小于號的不等式。顯然第一個約束條件已符合要求，不要做任何變動，而第二個約束條件，我們只要兩邊都乘以（-1），使不等號方向改變即可，得

這樣第二個約束條件也就符合要求。對于第三個約束條件，我們可以用小于等于和大于等于兩個約束條件來替代它。即有

顯然，這兩個約束條件與原來第三個約束條件是等價的，我們再把其中的兩邊都乘以（-1），得

§2線性規(guī)劃的對偶問題33

通過上面的一些變換，我們得到了一個和原線性規(guī)劃等價的線性規(guī)劃問題：

s.t.

§2線性規(guī)劃的對偶問題34

這個求最大值的線性規(guī)劃問題的約束條件都取小于等于號，我們馬上可以寫出其對偶問題：

s.t.§2線性規(guī)劃的對偶問題35

這里和一樣都是不同的決策變量，為了表示這兩個決策變量都來源于原問題的第三個約束條件，記為。因為在該對偶問題中和的系數只相差一個符號，我們可以把上面的對偶問題化為：

s.t.§2線性規(guī)劃的對偶問題36進一步，我們可以令，這時當時，

，當時，。這也就是說，盡管但的取值可以為正，可以為0，可以為負，即沒有非負限制。這樣我們把原規(guī)劃的對偶問題化為

s.t.

沒有限制。對照原線性規(guī)劃問題，我們可以知道：當原線性規(guī)劃問題的第i個約束條件取等號時，則其對偶問題的i個決策變量沒有非負限制。如果當原線性規(guī)劃問題中的第i個決策變量沒有非負限制時，我們也可以用進行替換，這里，，用類似的方法知道其對偶問題中第i個約束條件取等號?！?線性規(guī)劃的對偶問題37

另外，用大于等于0的兩個決策變量之差來代替無非負限制的決策變量也是求解含有無非負限制的決策變量的線性規(guī)劃問題的一種方法。原線性規(guī)劃問題為：

s.t.

無非負限制。§2線性規(guī)劃的對偶問題38§3對偶規(guī)劃的基本性質對偶規(guī)劃的基本性質1．對稱性。即對偶問題的對偶是原問題。2．弱對偶性。即對于原問題（Ⅰ）和對偶問題（Ⅱ）的可行解都有C≤bT

。

由弱對偶性，可得出以下推論：（1）原問題任一可行解的目標函數值是其對偶問題目標函數值的下界；反之對偶問題任一可行解的目標函數值是其原問題目標函數值的上界。（2）如原問題有可行解且目標函數值無界（或具有無界解），則其對偶問題無可行解；反之對偶問題有可行解且目標函數值無界，則其原問題無可行解（注意：本點性質的逆不成立，當對偶問題無可行解時，其原問題或具有無界解或無可行解，反之亦然）。（3）若原問題有可行解而其對偶問題無可行解，則原問題目標函數值無界；反之對偶問題有可行解而其原問題無可