第03章對偶問題與靈敏度分析

1、1第第3 3章章 對偶問題與靈敏度分析對偶問題與靈敏度分析3-1 3-1 線性規(guī)劃的對偶問題概念線性規(guī)劃的對偶問題概念3-2 3-2 建立對偶問題的規(guī)則建立對偶問題的規(guī)則3-3 3-3 對偶基本理論或性質(zhì)對偶基本理論或性質(zhì)3-4 3-4 線性規(guī)劃解法之三：線性規(guī)劃解法之三： 對偶單純形法對偶單純形法3-5 3-5 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析23-1 3-1 線性規(guī)劃的對偶問題概念線性規(guī)劃的對偶問題概念一、營養(yǎng)配置問題舉例一、營養(yǎng)配置問題舉例例例1 某養(yǎng)雞場所用的飼料由某養(yǎng)雞場所用的飼料由A、B、C三種配料組成，三種配料組成，下表給出了各種配料所含的營養(yǎng)成份、單位成本以下表給出了各

2、種配料所含的營養(yǎng)成份、單位成本以及及l(fā)份混合詞料必須含有的各種營養(yǎng)成份。份混合詞料必須含有的各種營養(yǎng)成份。3(1)問如何配制混合詞料使成本最?。繂柸绾闻渲苹旌显~料使成本最?。?2)若有一個飼料廠制造含有這三種營養(yǎng)成分的營若有一個飼料廠制造含有這三種營養(yǎng)成分的營養(yǎng)養(yǎng)飼飼料，在料，在1份混合飼料中三種營養(yǎng)丸的價格如何份混合飼料中三種營養(yǎng)丸的價格如何制定才使其售價最大？制定才使其售價最大？4解解:(1)設(shè)設(shè)xj表示一份混合飼料中第表示一份混合飼料中第j種配料的含量，種配料的含量， j=A，B，C。則。則 min Z=6XA十十3XB十十2XC s.t. XA十十XB十十XC 20 1/2XA十十1/

3、2XB十十1/4XC 6 2XA十十XB十十XC 10 XA，XB，XC 0求解結(jié)果為：求解結(jié)果為：5 cj632000cBXBBx1x2x3x4x5x62x316001-2400 x610-100-1013x241101-40 zj cj zj333020-11-4400表中所有檢驗數(shù)均不小于表中所有檢驗數(shù)均不小于0，已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為X=(0,4,16,0,0,10)T Zmin=216+34=446(2)若有一個飼料廠制造含有這三種營養(yǎng)成分為若有一個飼料廠制造含有這三種營養(yǎng)成分為1個單個單位的營養(yǎng)丸，在位的營養(yǎng)丸，在1份混合飼料中三種營養(yǎng)丸的價格如份混合飼料中三種營養(yǎng)

4、丸的價格如何制定才使其售價最大？何制定才使其售價最大？解：解：(2)設(shè)設(shè)qi表示一份混合飼料中第表示一份混合飼料中第I種營養(yǎng)丸的價格，種營養(yǎng)丸的價格，i=D,E,F,則則max Z=20q1十十6q2十十10q3 s.t. q1十十1/2q2十十2q3 6 q1十十1/2q2十十q3 3 q1十十1/4q2十十q3 2 q1 ， q2 ， q3 0求解結(jié)果為：求解結(jié)果為：7 cj20610000cBqBBq1q2q3q4q5q60q430011-106q2401004-420q111010-12 zj cj zj2006020-10004- 416-16表中所有檢驗數(shù)均不大于表中所有檢驗數(shù)均不

5、大于0，已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為q=(0,4,16,0,0,10)T Zmax=64+201=448LP1與與LP2的關(guān)系：的關(guān)系：min Z=6XA十十3XB十十2XC s.t. XA十十XB十十XC 20 1/2XA十十1/2XB十十1/4XC 6 2XA十十XB十十XC 10 XA，XB，XC 0 max w=20q1十十6q2十十10q3 s.t. q1十十1/2q2十十2q3 20 q1十十1/2q2十十q3 3 q1十十1/4q2十十q3 2 q1 ， q2 ， q3 09 cj632000cBXBBx1x2x3x4x5x62x316001-2400 x610-100

6、-1013x241101-40 zj cj zj333020-11-4400 cj20610000cBqBBq1q2q3q4q5q60q430011-106q2401004-420q111010-12 zj cj zj2006020-10004- 416-1610關(guān)系：關(guān)系：兩個兩個LP問題的最優(yōu)解的目標(biāo)函數(shù)值相同問題的最優(yōu)解的目標(biāo)函數(shù)值相同用單純形法求解一個用單純形法求解一個LP問題就知道另一問題就知道另一個問題的解個問題的解二、對偶問題的概念及實質(zhì)二、對偶問題的概念及實質(zhì)1.對每一個對每一個LP問題所伴隨著的另一個問題所伴隨著的另一個LP問問題，就稱為對偶問題；原來的題，就稱為對偶問題；原

7、來的LP問題就稱問題就稱為原問題為原問題2.實質(zhì)：實質(zhì)：對偶問題實質(zhì)上也是一個對偶問題實質(zhì)上也是一個LP問題問題11 3-2 3-2 建立對偶問題的規(guī)則建立對偶問題的規(guī)則一、建立對偶問題的規(guī)則一、建立對偶問題的規(guī)則 (LP) Max z = c x (DP) Min w = bTq s.t. Ax b s.t. AT q cT x 0 q 0 “Max - ” “Min- ”121.注意原問題與對偶問題的決策變量的表示方式：注意原問題與對偶問題的決策變量的表示方式：Xj,qi分別表示原問題、對偶問題的決策變量分別表示原問題、對偶問題的決策變量2.將問題變換為統(tǒng)一形式，其中將問題變換為統(tǒng)一形式，

8、其中b可以為負(fù)數(shù)可以為負(fù)數(shù)原問題原問題“max ”對偶問題對偶問題“min ”原問題原問題“min ” 對偶問題對偶問題“max ”對偶問題建立的規(guī)則；請同學(xué)們抄寫下來對偶問題建立的規(guī)則；請同學(xué)們抄寫下來1，原問題目標(biāo)函數(shù)求最大，原問題目標(biāo)函數(shù)求最大或者最小或者最小，則所有的約束條件符號，則所有的約束條件符號統(tǒng)一成小于或者等于統(tǒng)一成小于或者等于大于或者等于大于或者等于2，原問題一個行約束對應(yīng)對偶問題的一個變量，如果行約束為，原問題一個行約束對應(yīng)對偶問題的一個變量，如果行約束為不等式，這個變量就大于等于零不等式，這個變量就大于等于零否則就沒有限制否則就沒有限制為自由變量為自由變量3，原問題每個變

9、量的列向量對應(yīng)對偶問題的一個行約束，如果，原問題每個變量的列向量對應(yīng)對偶問題的一個行約束，如果原問題的變量大于等于零，則行約束小于等于零如果原問題的原問題的變量大于等于零，則行約束小于等于零如果原問題的變量沒有限制，則行約束為等號。變量沒有限制，則行約束為等號。4原問題目標(biāo)函數(shù)與對偶問題目標(biāo)函數(shù)相反。原問題目標(biāo)函數(shù)與對偶問題目標(biāo)函數(shù)相反。136.對偶問題的約束條件方程的右端值是原問題目標(biāo)對偶問題的約束條件方程的右端值是原問題目標(biāo)函數(shù)中決策變量的系數(shù)函數(shù)中決策變量的系數(shù)Cj；7.原問題與對偶問題的關(guān)系原問題與對偶問題的關(guān)系 xjqix1X2xn原始約束原始約束Min wq1a11a12a1nb1

10、q2a21a22a2nb2qmam1am2amnbm對偶約束對偶約束max zC1C2Cn14二、原問題不符合建立規(guī)則的處理二、原問題不符合建立規(guī)則的處理1.原問題為原問題為“max ”形式形式原問題為原問題為“max ”形式形式約束條件方程約束條件方程兩端乘以兩端乘以-12.原問題為原問題為“min ”形式形式原問題為原問題為“min ”形式形式約束條件方程約束條件方程兩端乘以兩端乘以-13.原問題的每一個約束條件方程對應(yīng)對偶問題的一原問題的每一個約束條件方程對應(yīng)對偶問題的一個決策變量個決策變量qi若第若第i個約束條件為不等式個約束條件為不等式,則限定則限定qi0若約束條件方程是若約束條件方

11、程是“=”形式形式:將將“=”變?yōu)樽優(yōu)椤啊焙秃汀啊眱蓚€約束條件方程兩個約束條件方程,在按照在按照1、2條處理條處理15例例2：根據(jù)下表寫出原問題：根據(jù)下表寫出原問題(max)與對偶問題與對偶問題(min)的的表達(dá)式表達(dá)式 xjqix1X2bq1128q24016qm0412Cj2316(1) min Z=2X1十十4X2十十3X3 s.t. X1十十2X23X3 5 2X1 3X2 2X33 X1十十X2十十X3 =2 X1，X2，X3 0(2) max Z=X1十十2X2十十3X3十十4X4 s.t. X1十十X2X3 3X4 =5 6X1十十7X2十十3X35X4 812X1 9X2 9X

12、3十十9X420 X1，X2，X3 ，X40例例3：建立下列：建立下列LP 問題的對偶問題問題的對偶問題17(3)沒有非負(fù)限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ183-3 3-3 對偶基本理論或性質(zhì)對偶基本理論或性質(zhì)一、對稱性一、對稱性對偶問題的對偶是原問題對偶問題的對偶是原問題二、二、弱對偶性弱對偶性若若 x, q x, q 分別為（分別為（LP) LP) 和（和（DPDP）的可行）的可行解，那么解，那么cx bcx bT Tq q推論推論三、三、最優(yōu)性準(zhǔn)則定理最優(yōu)性準(zhǔn)則定理若若x x, ,q q分別

13、分別(LP),(DP)(LP),(DP)的可行解的可行解, ,且且cxcx= =b bT Tq q，那么那么x x, ,y y分別為分別為(LP)(LP)和和(DP)(DP)的最優(yōu)解的最優(yōu)解19四、對偶定理四、對偶定理若若(LP)(LP)和和(DP)(DP)均可行均可行 那么那么(LP)(LP)和和(DP)(DP)均有最優(yōu)解均有最優(yōu)解, ,且最優(yōu)值相等且最優(yōu)值相等五、從一個問題的最優(yōu)解單純形表中可五、從一個問題的最優(yōu)解單純形表中可以得到另一個問題的最優(yōu)解以得到另一個問題的最優(yōu)解從從(LP)(LP)的最優(yōu)解單純形表中找的最優(yōu)解單純形表中找(DP)(DP)的最優(yōu)解：的最優(yōu)解：q qi i=|Z=|

14、Zn+in+i| n| n為為(LP)(LP)的實際決策變量數(shù)的實際決策變量數(shù)從從(DP)(DP)的最優(yōu)解單純形表中找的最優(yōu)解單純形表中找 (LP)(LP)的最優(yōu)的最優(yōu)解：解：X Xj j=|Z=|Zm+im+i| m| m為為(LP)(LP)的約束條件方程個數(shù)的約束條件方程個數(shù)六、互補松弛性六、互補松弛性若若X,qX,q分別是分別是(LP)(LP)和和(DP)(DP)的可行解，那么的可行解，那么qXqXs s=0=0和和q qs sX=0X=0，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)X,qX,q為最優(yōu)解為最優(yōu)解20例例4 4：已知：已知LPLP問題問題max Z=xmax Z=x1 1+x+x2 2s.t. x

15、s.t. x1 1+x+x2 2+x+x3 322-2x-2x1 1+x+x2 2-x-x3 31 1 x x1 1,x,x2 2,x,x3 300試用對偶理論證明試用對偶理論證明上述上述LPLP問題無最優(yōu)問題無最優(yōu)解解例例5 5：已知：已知LPLP問題問題min Z=2xmin Z=2x1 1+3x+3x2 2 +5x+5x3 3+2x+2x4 4 +3x+3x5 5s.t. xs.t. x1 1+x+x2 2+2x+2x3 3 +x+x4 4 +3x+3x5 5 44 2x 2x1 1-x-x2 2+3x+3x3 3 +x+x4 4 +x+x5 5 3 3 x x1 1,x,x2 2,x,

16、x3 3 ,x,x4 4 ,x,x5 500已知其對偶問題的最優(yōu)解為已知其對偶問題的最優(yōu)解為q q1 1=4/5;q=4/5;q2 2=3/5;z=5.=3/5;z=5.試用對偶試用對偶理論找出原問題的最優(yōu)解理論找出原問題的最優(yōu)解21解：先寫出其對偶問題：解：先寫出其對偶問題： max w=4q1+3q2 q1+2q22 (1) q1 -q23 (2)2q1+3q25 (3) q1 +q22 (4)3q1 +q23 (5)將將q1,q2的值代入約束條的值代入約束條件，得件，得(2),(3),(4)為嚴(yán)格不為嚴(yán)格不等式；由互補松弛性等式；由互補松弛性qsx=0得得x2=0,x3=0,x4=0。又

17、因為又因為q1,q20，由互補松弛，由互補松弛性性qxs=0得得xs1=0 ,xs2=0,j即原問即原問題的兩個約束條件應(yīng)取等式，題的兩個約束條件應(yīng)取等式，故有故有 x x1 1 +3x+3x5 5 =4=4 2x 2x1 1 +x+x5 5 =3=3求解得求解得x x1 1=1.x=1.x2 2=1=1故原問題的最優(yōu)解為故原問題的最優(yōu)解為X=(1,0,0,0,1)X=(1,0,0,0,1)T TZ Zminmin=5=522例例6 6：已知某：已知某LPLP問題的最優(yōu)單純形表如下，試問題的最優(yōu)單純形表如下，試分別寫出其原問題和對偶問題的最優(yōu)解分別寫出其原問題和對偶問題的最優(yōu)解 cj63200

18、0cBXBBx1x2x3x4x5x62x316001-2400 x610-100-1013x241101-40 zj cj zj333020-11-4400對偶問題的用途對偶問題的用途減少計算工作量：如判斷減少計算工作量：如判斷LP問題有無最優(yōu)解問題有無最優(yōu)解對求對求“min ”時，可轉(zhuǎn)換為對偶問題易求解時，可轉(zhuǎn)換為對偶問題易求解233-4 3-4 線性規(guī)劃解法之三：線性規(guī)劃解法之三：對偶單純形法對偶單純形法一、對偶單純形法的基本思想一、對偶單純形法的基本思想從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶可行解（檢驗數(shù)非正），所以

19、也但它對應(yīng)著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)可以說是從一個對偶可行解出發(fā)然后檢驗原規(guī)劃的基本解是否可行，即是否有負(fù)的然后檢驗原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進行迭代，求另一個分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)非正）非正）如果得到的基本解的分量皆非負(fù)，則該基本解為最如果得到的基本解的分量皆非負(fù)，則該基本解為最優(yōu)解。也就是說，優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正）

20、，使原規(guī)劃的基持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時得到對偶規(guī)劃與本解由不可行逐步變?yōu)榭尚校?dāng)同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解24二、對偶單純形法求解線性規(guī)劃問題過程二、對偶單純形法求解線性規(guī)劃問題過程1.1.建立初始對偶單純形表建立初始對偶單純形表, ,對應(yīng)一個基本解對應(yīng)一個基本解, ,所有檢驗數(shù)均非正所有檢驗數(shù)均非正, ,轉(zhuǎn)轉(zhuǎn)2 2；2.2.若若b b0,0,則得到最優(yōu)解則得到最優(yōu)解, ,停止停止; ;否則否則, ,若有若有b bk k00則選則選minminb bk k| |b bk k

21、00的的k k行的基變量為換出變行的基變量為換出變量量, ,轉(zhuǎn)轉(zhuǎn)3 33.3.若所有若所有a akjkj0( 0( j j = 1,2, = 1,2,n n ) )，則原問，則原問題無可行解題無可行解, ,停止停止; ;否則否則, ,若有若有a akjkj0 0 則選則選minmin j j / / a akjkja akjkj00= r r/a akrkr那么選那么選x xr r為換入基變量為換入基變量, ,轉(zhuǎn)轉(zhuǎn)4 4；4.4.以以a akrkr進行轉(zhuǎn)軸運算進行轉(zhuǎn)軸運算, ,作矩陣行變換使其變作矩陣行變換使其變?yōu)闉?,1,該列其他元素變?yōu)樵摿衅渌刈優(yōu)?,0,轉(zhuǎn)轉(zhuǎn)2 225例例7 7：用對

22、偶單純形法求解下列：用對偶單純形法求解下列LPLP問題問題 min Z=6X1十十3X2十十2X3 s.t. X1十十X2十十X3 20 1/2X1十十1/2X2十十1/4X3 6 2X1十十X2十十X3 10 X1，X2，X3 026解法一解法一: :將將LPLP問題化為問題化為 max Z= 6X1 3X2 2X3 s.t. X1 X2 X3十十X4 = 20 1/2X1 1/2X2 1/4X3 十十X5 = 6 2X1 X2 X3 十十X6 = 10 X1，X2，X3 , X4 , X5 , X6 ,0 cj-6-3-2000cBXBbx1x2x3x4x5x60 x4-20-1-1-11

23、000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj cj zj0-60-30-200000027 cj-6-3-2000cBXBbx1x2x3x4x5x60 x4(-20)-1-1-1*1000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj cj zj0-60-30-2000000-2x320111-1000 x5(-1)-1/4-1/4*0-1/4100 x610-100-101 zj cj zj-2-4-2-1-202-20000-2x316001-240-3x241101-400 x610-100-101 zj cj zj

24、-3-3-30-201-14-40028表中所有檢驗數(shù)均不大于表中所有檢驗數(shù)均不大于0，且，且bi0已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為X=(0,4,16,0,0,10)T , Zmax=64+201=44Zmin= Zmax=44解法二解法二: :將將LPLP問題化為問題化為 min Z= 6X1十十3X2十十2X3 s.t. X1 X2 X3十十X4 = 20 1/2X1 1/2X2 1/4X3 十十X5 = 6 2X1 X2 X3 十十X6 = 10 X1，X2，X3 , X4 , X5 , X6 ,029 cj632000cBXBbx1x2x3x4x5x60 x4(-20)-1-1-

25、1*1000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj zj cj0-60-30-2000000例例8:用對偶單純形法求解下列用對偶單純形法求解下列LP問題問題min Z=3X1十十2X2十十X3 s.t. X1十十X2十十X3 6 X1 X3 4 X2X3 3 X1，X2，X3 030解解:化為化為 min Z=3X1十十2X2十十X3 s.t. X1十十X2十十X3十十X4 =6 X1 十十X3 十十X5 =-4 X2 十十X3 十十X6 =-3 X1，X2，X3 , X4 , X5 , X6 0 cj321000cBXBbx1x2x3x4x5x60 x

26、461111000 x5(-4)-1*010100 x6-30-11001 zj zj cj0-30-20-100000031 cj321000cBXBbx1x2x3x4x5x60 x461111000 x5(-4)-1*010100 x6-30-11001 zj zj cj0-30-20-10000000 x420121103x1410-10-100 x6(-3)0-1*1001 zj zj cj300-2-3-400-3-3000 x4(-1)0011113x1410-10-100 x6301-100-1 zj zj cj3020-5-600-3-3-2-232表中所有檢驗數(shù)均不大于表中所

27、有檢驗數(shù)均不大于0,但但x4變量行的變量行的aij全為全為非負(fù)非負(fù),故該問題無可行解故該問題無可行解三、三、對偶單純形法的適用范圍對偶單純形法的適用范圍1.1.應(yīng)用前提：有一個基，其對應(yīng)的基滿足應(yīng)用前提：有一個基，其對應(yīng)的基滿足: :單純形表的檢驗數(shù)行全部非正（對偶可行）單純形表的檢驗數(shù)行全部非正（對偶可行）變量取值可有負(fù)數(shù)（非可行解）變量取值可有負(fù)數(shù)（非可行解）注：通過矩陣行變換運算，使所有相應(yīng)變量注：通過矩陣行變換運算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純性表取值均為非負(fù)數(shù)即得到最優(yōu)單純性表2.2.對偶單純形法適合于解如下形式的線性規(guī)對偶單純形法適合于解如下形式的線性規(guī)劃問題劃問題3

28、3njxmibxacxcZjnjijijnjjjj,2,1,0,2,10min11例例9 9：求解下列：求解下列LPLP問題問題max Z=X1十十X2s.t. 2X1十十X24 X1十十7X27 X1，X2034四、對偶單純形法與單純形法的比較四、對偶單純形法與單純形法的比較1.思路比較思路比較單純形法是單純形法是從一個基本可行解轉(zhuǎn)到另一個更從一個基本可行解轉(zhuǎn)到另一個更優(yōu)的基本可行解，優(yōu)的基本可行解，即跌代中始終保持原問題的即跌代中始終保持原問題的可行性：可行性：b0，檢驗數(shù)中大于檢驗數(shù)中大于0的逐步變?yōu)槿康闹鸩阶優(yōu)槿?為止為止對偶單純形法是對偶單純形法是保持滿足最優(yōu)檢驗判斷，即保持滿足

29、最優(yōu)檢驗判斷，即全部檢驗數(shù)全部檢驗數(shù)0，從一個基本解逐步跌代變?yōu)橐粡囊粋€基本解逐步跌代變?yōu)橐粋€基本可行解，即個基本可行解，即b0為止為止2.計算步驟的關(guān)系計算步驟的關(guān)系35是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以中心元素進行迭代以中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min36五、對偶單純法的應(yīng)用：增加約束條件五、對偶單純法的應(yīng)用：增加約束條件(一一)對偶單純形法的用途對偶單純形

30、法的用途1.對約束條件方程為對約束條件方程為“”型型,不必加人工變量用大不必加人工變量用大M法或兩階段法求解而采用對偶單純形法求解更容易法或兩階段法求解而采用對偶單純形法求解更容易2.增加一個約束條件方程后不必重新求解，只需在增加一個約束條件方程后不必重新求解，只需在最優(yōu)解表上增加用對偶單純形法求解即可最優(yōu)解表上增加用對偶單純形法求解即可(二二)LP問題新增約束條件的求解步驟問題新增約束條件的求解步驟1.檢驗原來的最優(yōu)解是否滿足新增加的約束條件：檢驗原來的最優(yōu)解是否滿足新增加的約束條件：若滿足，則原最優(yōu)解就是新問題的最優(yōu)解若滿足，則原最優(yōu)解就是新問題的最優(yōu)解若不滿足，則進行下一步若不滿足，則進

31、行下一步372.將新增約束條件加入松弛變量或多余變量后加到原將新增約束條件加入松弛變量或多余變量后加到原來最優(yōu)單純形表中，令來最優(yōu)單純形表中，令原基變量和新增的松弛變量或原基變量和新增的松弛變量或多余變量組成新基，并將基變量對應(yīng)的系數(shù)矩陣變?yōu)槎嘤嘧兞拷M成新基，并將基變量對應(yīng)的系數(shù)矩陣變?yōu)閱挝痪仃噯挝痪仃嚒啊毙图s束條件方程加松弛變量變?yōu)樾图s束條件方程加松弛變量變?yōu)椤啊毙图s束型約束條件方程條件方程“”型約束條件方程減多余變量變?yōu)樾图s束條件方程減多余變量變?yōu)椤啊毙图s束型約束條件方程，然后等式方程兩端乘以條件方程，然后等式方程兩端乘以(-1)“=”型約束條件方程轉(zhuǎn)化為型約束條件方程轉(zhuǎn)化為“”和和“”，

32、然后將不滿，然后將不滿足的條件加進去足的條件加進去3.利用對偶單純形法求最優(yōu)解利用對偶單純形法求最優(yōu)解38例例10：已知：已知LP問題問題 Max z =40 xMax z =40 x1 1+45x+45x2 2 +24x +24x3 3 s.t. 2x s.t. 2x1 1+3x+3x2 2+x+x3 3 100 100 3x 3x1 1+3x+3x2 2+2x+2x3 3 120 120 x x1 1 ,x,x2 2 ，x x3 300用單純形法求解得最優(yōu)單純形表如下：用單純形法求解得最優(yōu)單純形表如下： cj40452400cBXBBx1x2x3x4x545x22001-1/31-2/34

33、0 x120101-11 zj cj zj40045025-15-510-1039試求在增加一個約束條件試求在增加一個約束條件X115時新的最優(yōu)解時新的最優(yōu)解解解:(1)原最優(yōu)解為原最優(yōu)解為X1=20,X2=20,而新增約束而新增約束X115,所所以原最優(yōu)解不滿足新增約束條件以原最優(yōu)解不滿足新增約束條件(2) X115處理得處理得X1 X6=15， X60，從而得到新的，從而得到新的單純形表并進行初等交換單純形表并進行初等交換 cj404524000cBXBBx1x2x3x4x5x645x22001-1/31-2/3040 x120101-1100 x61510000140 cj4045240

34、00cBXBBx1x2x3x4x5x645x22001-1/31-2/3040 x120101-1100 x6-500-1*1-11 zj cj zj40045025-15-510-100045x265/30102/3-1/3-1/340 x11510000124x35001-11-1 zj cj zj4004502406-69-91-1表中所有檢驗數(shù)均不大于表中所有檢驗數(shù)均不大于0，且，且bi0已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為X=(15,65/3,5,0,0,0)T , Zmax=1695413-5 3-5 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析一、線性規(guī)劃與參數(shù)規(guī)劃一、線性規(guī)劃與參

35、數(shù)規(guī)劃1.1.線性規(guī)劃：目標(biāo)函數(shù)系數(shù)線性規(guī)劃：目標(biāo)函數(shù)系數(shù)C Cj j、約束條件方程、約束條件方程系數(shù)系數(shù)a aijij、約束條件方程右端值、約束條件方程右端值b bi i均固定均固定2.2.參數(shù)規(guī)劃：參數(shù)規(guī)劃：C Cj j、a aijij、b bi i不固定不固定使得最優(yōu)解或最優(yōu)基不變的使得最優(yōu)解或最優(yōu)基不變的C Cj j、a aijij、b bi i的變的變化范圍的分析化范圍的分析LPLP問題的靈敏度分析問題的靈敏度分析使得最優(yōu)解或最優(yōu)基變化的使得最優(yōu)解或最優(yōu)基變化的C Cj j、a aijij、b bi i的變的變化范圍的分析化范圍的分析參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃42二、靈敏度分析的概念與

36、界定范圍二、靈敏度分析的概念與界定范圍1.概念：概念：某一參數(shù)發(fā)生變化時，目標(biāo)函數(shù)發(fā)生怎樣變某一參數(shù)發(fā)生變化時，目標(biāo)函數(shù)發(fā)生怎樣變化的分析化的分析2.界定范圍：界定范圍：“Max ”三、三、LP問題靈敏度分析的內(nèi)容問題靈敏度分析的內(nèi)容1.對對C Cj j值的靈敏度分析值的靈敏度分析2.對對b bi i值的靈敏度分析值的靈敏度分析對對3. a3. aijij值的靈敏度分析值的靈敏度分析* *4.4.增加或刪去一個變量的分析增加或刪去一個變量的分析5.5.增加或去掉一個約束條件的分析增加或去掉一個約束條件的分析43四、理解最優(yōu)單純性表中各元素的含義四、理解最優(yōu)單純性表中各元素的含義考慮問題考慮問題

37、 Max Max z z = = c c1 1 x x1 1 + + c c2 2 x x2 2 + + + + c cn n x xn n s.t. s.t. a a1111x x1 1 + + a a1212x x2 2 + + + + a a1n1nx xn n b b1 1 a a2121x x1 1 + + a a2222x x2 2 + + + + a a2n2nx xn n b b2 2 . . . . . . a am1m1x x1 1 + + a am2m2x x2 2 + + + + a amnmnx xn n b bm m x x1 1 ，x x2 2 ， ，x xn n

38、 0 0 引入引入 m m 個松弛變量后，通過計算得到個松弛變量后，通過計算得到最優(yōu)單純形表。最優(yōu)單純形表。 應(yīng)能夠找到最優(yōu)基應(yīng)能夠找到最優(yōu)基 B B 的的逆矩陣逆矩陣 B B-1-1 和檢驗數(shù)等和檢驗數(shù)等44五、價值系數(shù)五、價值系數(shù)cj的靈敏度分析的靈敏度分析1.1.對對cj的靈敏度分析的前提的靈敏度分析的前提 維持最優(yōu)解維持最優(yōu)解 不變：基變量及其取值不變不變：基變量及其取值不變cj的變化仍使單純形表中的非基本量的檢驗數(shù)的變化仍使單純形表中的非基本量的檢驗數(shù) j = cj zj都保持不大于都保持不大于0 cj的變化僅影響的變化僅影響zj和檢驗數(shù)和檢驗數(shù) j = cj zj2.2.對對cj的

39、靈敏度分析的靈敏度分析(1) (1) xj是非基變量時是非基變量時若若x xj j是非基變量時，是非基變量時， cj的變化僅影響的變化僅影響x xj j對應(yīng)的檢驗對應(yīng)的檢驗數(shù)數(shù)cj zjcj減少的范圍：減少的范圍： xj已經(jīng)不在最優(yōu)解內(nèi)，已經(jīng)不在最優(yōu)解內(nèi)， cj減少時減少時xj更不會在最優(yōu)解范圍內(nèi)，所以更不會在最優(yōu)解范圍內(nèi)，所以cj的變動下限為的變動下限為 45cj增加的范圍：設(shè)在原最優(yōu)單純形表中，增加的范圍：設(shè)在原最優(yōu)單純形表中， cj變?yōu)樽優(yōu)閏j + cj ，則檢驗數(shù)為，則檢驗數(shù)為 j = cj + cj zjv若若cj + cj zj0成立，則目標(biāo)不變；成立，則目標(biāo)不變；v若若cj +

40、cj zj 0成立，則目標(biāo)不變，但有多重解成立，則目標(biāo)不變，但有多重解v若若cj + cj zj0成立，則目標(biāo)發(fā)生變化成立，則目標(biāo)發(fā)生變化cj + cj zj0 cj ( cj zj ),所以所以cj的變的變動上限為動上限為 ( cj zj ) 當(dāng)當(dāng)xj為非基變量時，為非基變量時， cj的變化范圍為的變化范圍為 cj ( cj zj )46例例11：已知下列：已知下列LP 問題：問題： MaxMax z =x z =x1 1+5x+5x2 2 +3x+3x3 3 +4x+4x4 4 s.t. 2x s.t. 2x1 1+3x+3x2 2+x+x3 3+2x+2x4 4 800 800 5x 5

41、x1 1+4x+4x2 2+3x+3x3 3+4x+4x4 4 1200 1200 3x 3x1 1+4x+4x2 2+5x+5x3 3+3x+3x4 41000 1000 x x1 1 ,x,x2 2 ，x x3 3 ，x x4 400 其最優(yōu)單純形表如下，試分析其最優(yōu)單純形表如下，試分析c c1 1和和c c3 3的靈的靈敏度范圍敏度范圍47 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.754000

42、0.25-0.251-1解：由單純形表可知解：由單純形表可知(1) c1 ( c1 z1 )， c1 3.25 c1 4.25(2) c3 ( c3 z3 )， c3 2.75 c3 5.7548(2) (2) xj是基變量時是基變量時若若x xj j是基變量時，是基變量時， cj的變化影響的變化影響所有非基變量對應(yīng)所有非基變量對應(yīng)的的zj和檢驗數(shù)和檢驗數(shù)cj zjcj變化范圍：變化范圍：v設(shè)設(shè)xj為第為第r個約束條件方程對應(yīng)的基變量，當(dāng)個約束條件方程對應(yīng)的基變量，當(dāng)cj變?yōu)樽優(yōu)閏j + cj ，則，則cB變?yōu)樽優(yōu)閏B + cB其中其中 cB=(0,0,0, cj,0,0,0)v非基變量非基變

43、量xk檢驗數(shù)應(yīng)滿足：檢驗數(shù)應(yīng)滿足：ck (cB + cB)B-1Pk0ck cB B-1Pk cBB-1Pk0(ck zk ) cBB-1Pk0(ck zk )(0,0,0, cj,0,0,0) B-1Pk049(ck zk )(0,0,0, cj,0,0,0) B-1Pk0(ck zk )(0,0,0, cj,0,0,0) Pk0(ck zk ) cjark0 cjark ck zk 當(dāng)當(dāng)ark 0時，則時，則 cj（ck zk ）/ ark 當(dāng)當(dāng)ark 0時，則時，則 cj（ck zk ）/ ark 當(dāng)當(dāng)ark =0時，則時，則 cj的變化不影響的變化不影響zk結(jié)論：當(dāng)結(jié)論：當(dāng)xj為基變量

44、時為基變量時, cj的變化范圍為的變化范圍為(xj為第為第r個方程個方程)Max（ck zk ）/ ark | ark 0 cj minck zk ）/ ark | ark 050例例12：已知：已知LP 問題的問題的最優(yōu)單純形表如下，試分最優(yōu)單純形表如下，試分析析c c2 2和和c c4 4的靈敏度范圍的靈敏度范圍 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.7540000.25-0.251-151六

45、、資源數(shù)量六、資源數(shù)量bi的靈敏度分析的靈敏度分析1.1.對對bi的靈敏度分析的前提的靈敏度分析的前提 維持最優(yōu)解基變量不變，但是其取值可變維持最優(yōu)解基變量不變，但是其取值可變bi的變化僅影響基變量的取值的變化僅影響基變量的取值2.2.對對bi的靈敏度分析的靈敏度分析原最優(yōu)解為原最優(yōu)解為X XB B=B=B-1-1b,b,設(shè)設(shè)b bk k的變化量為的變化量為b bk k，則其他系，則其他系數(shù)不變時新解中基變量的取值為數(shù)不變時新解中基變量的取值為XXB B=B=B-1-1（b+ b+ b b）00，其中，其中b=b=（0 0，0 0，b bk k ，0 0，0 0）T TXXB B=B=B-1-

46、1（b+ b+ b b）= X= XB B=B=B-1-1b+ Bb+ B-1-1 b b =(b =(b1 1+ + b bk kaa1,n+k1,n+k, b, b2 2+ + b bk kaa2,n+k 2,n+k ,， bbm m+ + b bk kaam,n+k m,n+k ) )T T由此可得由此可得, , bbi i+ + b bk kaai,n+ki,n+k 0,I=1,2,m 0,I=1,2,m b bk kaai,n+ki,n+k bbi i,I=1,2,m,I=1,2,m52(1)當(dāng)當(dāng)aai,n+ki,n+k 0 0時，則時，則b bk k bbi i/ a/ ai,n+

47、ki,n+k (2)(2)當(dāng)當(dāng)aai,n+ki,n+k 0 0時，則時，則b bk k bbi i/ a/ ai,n+ki,n+k 3.3.當(dāng)當(dāng)XXB B=B=B-1-1（b+ b+ b b）00時，最優(yōu)解基變時，最優(yōu)解基變量不變，但最優(yōu)解的取值發(fā)生變化，取值為量不變，但最優(yōu)解的取值發(fā)生變化，取值為XXB B=B=B-1-1（b+ b+ b b）=B=B-1-1b+ Bb+ B-1-1 b b = X = XB B+ +b bk kPPn+kn+k4.4.當(dāng)當(dāng)XXB B=B=B-1-1（b+ b+ b b）00時，原最優(yōu)解不時，原最優(yōu)解不可行，用可行，用對偶單純形法對偶單純形法求新的最優(yōu)解求新

48、的最優(yōu)解53例例13：已知：已知LP 問題的問題的最優(yōu)單純形表如下，試分最優(yōu)單純形表如下，試分析析b b2 2和和b b3 3的靈敏度范圍的靈敏度范圍 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.7540000.25-0.251-154七、七、增加或刪去一個變量的分析增加或刪去一個變量的分析1.1.增加一個變量增加一個變量 設(shè)增加的變量為設(shè)增加的變量為x xn+1n+1, ,其價值系數(shù)為其價值系數(shù)為c

49、cn+1n+1 , ,系數(shù)列向系數(shù)列向量量P Pn+1n+1, ,則檢驗數(shù)為則檢驗數(shù)為n+1n+1=c=cn+1n+1-c-cB BB B-1-1P Pn+1n+1(1)(1)若若n+1n+1 0, 0,則原最優(yōu)解不變則原最優(yōu)解不變(2)(2)若若n+1n+1 0,0,則將則將x xn+1n+1引入基變量引入基變量, ,進行跌代進行跌代2.2.刪去一個變量刪去一個變量(1)(1)若若x xr r為非基變量，去掉為非基變量，去掉x xr r不影響最優(yōu)解不影響最優(yōu)解55(2)(2)若若x xr r為基變量，對最優(yōu)解產(chǎn)生影響，其處理方法為：為基變量，對最優(yōu)解產(chǎn)生影響，其處理方法為：取取x xr r為

50、換出變量，用對偶單純形法求解為換出變量，用對偶單純形法求解取取x xr r的價值系數(shù)的價值系數(shù)c cr r為為M M，用大，用大M M法計算法計算八、八、增加或去掉一個約束條件的分析增加或去掉一個約束條件的分析1.刪去一個約束條件刪去一個約束條件(1)對最優(yōu)解沒有影響：松弛變量、多余變量的對最優(yōu)解沒有影響：松弛變量、多余變量的取值都是大于取值都是大于0的約束條件稱為松約束的約束條件稱為松約束(2)對最優(yōu)解有影響：松弛變量、多余變量的取對最優(yōu)解有影響：松弛變量、多余變量的取值都是等于值都是等于0的約束條件稱為緊約束的約束條件稱為緊約束562.增加一個約束條件增加一個約束條件(1)若原最優(yōu)解滿足約

51、束條件，最優(yōu)解不變?nèi)粼顑?yōu)解滿足約束條件，最優(yōu)解不變(2)若原最優(yōu)解不滿足約束條件，用對偶單純形法求解若原最優(yōu)解不滿足約束條件，用對偶單純形法求解例例14：已知下列：已知下列LP 問題問題 MaxMax z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1, ,x x2 2 , ,x x3 3, ,x x4 4, ,x x5 5 0 0其其最優(yōu)單純形表如

52、下最優(yōu)單純形表如下57 cj23000cBXBBx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80 zj cj zj20303/2-3/21/8-1/800試分析：試分析：(1)分析分析C2的靈敏度范圍的靈敏度范圍(2) 當(dāng)?shù)谝粋€約束條件的當(dāng)?shù)谝粋€約束條件的b b1 1 增加增加4 4時，對原最優(yōu)解有影響嗎？時，對原最優(yōu)解有影響嗎？若有，求出新的最優(yōu)解若有，求出新的最優(yōu)解(3)(3)增加增加x x6 6時時, , p p6 6=( 2, 6, 3 )=( 2, 6, 3 )T T, , c c6 6=5=5，對原最優(yōu)解的影響對原最優(yōu)解的影響 (4)(4)增加增加3 3x x1 1+ 2+ 2x x2 21515時對原最優(yōu)解的影響時對原最優(yōu)解的影響58解解: :(1)(1) -3 -3c c2 211(2)x = ( 4, 3, 2, 0, 0 )(2)x = ( 4, 3, 2, 0, 0 )T T Z Z* * = 17 =