第2章 線性規(guī)劃的對偶理論與靈敏度分析2011,9(上課)

1、1、線性規(guī)劃的對偶問題、線性規(guī)劃的對偶問題2、圖解法的靈敏度分析、圖解法的靈敏度分析對偶是一種普遍現(xiàn)象對偶是一種普遍現(xiàn)象兩個黃鸝鳴翠柳兩個黃鸝鳴翠柳, , 一行白露上青天。一行白露上青天。門泊東吳萬里船。門泊東吳萬里船。窗含西嶺千秋雪窗含西嶺千秋雪, , 第一節(jié) 線性規(guī)劃的對偶問題 一、問題的提出一、問題的提出我們先來看一個例題我們先來看一個例題: 例例1 某工廠在計劃期內(nèi)安排甲、乙兩種產(chǎn)品，已某工廠在計劃期內(nèi)安排甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需設(shè)備知生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺時和所獲利潤如臺時和所獲利潤如下表所示：下表所示： 甲乙資源限量設(shè)備A11300臺時設(shè)備B 21400臺時設(shè)

2、備C01250臺時利潤（元） 50100 問：工廠應(yīng)分別生產(chǎn)甲、乙產(chǎn)品各多少，才能使工廠問：工廠應(yīng)分別生產(chǎn)甲、乙產(chǎn)品各多少，才能使工廠獲獲利最多？利最多？設(shè)：甲設(shè)：甲 x1， 乙乙 x2該線性規(guī)劃的模型為：該線性規(guī)劃的模型為： 現(xiàn)在我們從另一個角度來考慮這個問題現(xiàn)在我們從另一個角度來考慮這個問題。 假如有另外一個工廠要求租用該廠的設(shè)備假如有另外一個工廠要求租用該廠的設(shè)備A、B、C，那么，那么該廠的廠長應(yīng)該如何來確定合理的租金呢？該廠的廠長應(yīng)該如何來確定合理的租金呢？(LP1)0 x0,x250 x400 x2x300 x x100 x50 xmax Z212212121設(shè)：設(shè)：y1 - A 每

3、臺時的租金每臺時的租金_ y2 - B 每臺時的租金每臺時的租金 y3 - C 每臺時的租金每臺時的租金則則 建立該線性規(guī)劃的數(shù)學(xué)模型為：建立該線性規(guī)劃的數(shù)學(xué)模型為：Min z = 300y1+400y2+250y3 y1+2y2 50 y1+y2+y3 100 (LP2) y1,y2,y3 0LP1 與與LP2 是一對是一對對偶問題對偶問題cj50 100 0 0 0 x1 x2 x3 x4 x511 0 -1 0 0 -2 1 1cBixBi50 x10 x4bi50biaikyj=cj-zj100 x2050250 0 1 0 0 1 0 0 -50 0 -50 - 27500cj-30

4、0 -400 -250 0 0 -M cBixBi-300 y1-250 y3bi50biaikyj=cj-zj50y1 y2 y3 y4 y5 y6 1 2 0 -1 0 10 -1 1 1 -1 -1 0 - 50 0 -50 -250 -m+50 27500LP1最終單純型表最終單純型表LP2最終單純型表最終單純型表求解問題求解問題 LP1得：得：X* = （x1,x2,x3,x4,x5)T = (50,250,0,50,0)T Max z = 27500求解問題求解問題 LP2得：得：Y* = （y1,y2,y3,y4,y5, y6,)T = (50,0,50,0,0,0)TMin z

5、 = 275000,. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZ對稱形式下線性規(guī)劃原問題的一般形式為：對稱形式下線性規(guī)劃原問題的一般形式為： 用用yi（i=1，2，.，m）代表第）代表第i種資源的種資源的估價，則其對偶問題的一般形式為：估價，則其對偶問題的一般形式為：0,. .2122112211112121112211mnmmnnn2mm222mmmmyyycyyycyyycyyyybybybminZaaaaaaaaats用矩陣形式表示，對稱形式的線性規(guī)劃用矩陣形式表示，對稱形式的

6、線性規(guī)劃問題的原問題為：問題的原問題為： YCYYmin wZ0A. .X0XbAX. .CXmaxtsts其對偶問題為：0 x0,x182x3x 122x4 x5x3xmax Z221212121例0y0,y0,y52y2y33yy 18y12y4ymin w3213231321其對偶問題：原問題和對偶問題的關(guān)系可用下面表格的形式來表示：原問題和對偶問題的關(guān)系可用下面表格的形式來表示：原問題（求極大）c1 c2 cn x1 x2 xn右邊對偶問題（求極?。゜1 y1b2 y2bm ym a11 a12 a1n a21 a22 . . a2n. am1 am2 . amnb1b2bm右邊 c1

7、 c2cm 例3、寫出下述線性規(guī)劃問題的對偶問題無約束333333333333300Zxxxbxaxaxabxaxaxabxaxaxaxcxcxc,max21221122222121112121112211 0, 0, 0, 0yyyyxcZmax0 x, 0 x, 0 x,xxx,xx33213333333322311322323332222121223233322221211131333121211133332211 33233322xxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxaxcxcxc對偶變量則上式可寫為：其中令 0y, 0y, 0y, 0ycyyy

8、ycyyyycyyyycyyyyybybybybmin w3221333322322311333332322321132332222222121133121221211133222211aaaaaaaaaaaaaaaa其對偶問題為： 0y,y0ycyyycyyycyyyy-y,y-yy333333133321132233222無約束由此得令2122122221211111332211,min:,aaaaaaaaaybybybw原問題（對偶問題）原問題（對偶問題）對偶問題（原問題）對偶問題（原問題）無約束），（量變jjjxxxnj00. .1xjjiijjiijjiijcyacyacyaj），個

9、（件條束約n. .1nijijijijijijbxabxabxai），個（件條束約m. .1m變量無約束iiyyy00m)1,.,(iyiijjxczmaxiiybzmin例例4 4、寫對偶規(guī)劃、寫對偶規(guī)劃minZ= 4x1 +2x2 -3x3 -x1+2x2 62x1 +3x3 9 x1 +5x2 -2x3 = = 4x2 , x3 0maxW= 6y1 +9y2 +4y3 -y1+2y2 + y3 = = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 , y3自由自由minZ= 4x1 +2x2 -3x3 x1 -2x2 - 62x1 +3x3 9 x1 +5x2

10、-2x3 = = 4x2 , x3 0或?qū)⒃瓎栴}變形為或?qū)⒃瓎栴}變形為maxW= -6y1 +9y2 +4y3 y1+2y2 + y3 = = 4-2y1 +5y3 2 3y2 -2y3 -3y1 , y2 0 , y3自由自由對偶規(guī)劃對偶規(guī)劃例例5 寫出下面線性規(guī)劃的對偶規(guī)劃寫出下面線性規(guī)劃的對偶規(guī)劃 min z = 3x1+9x2 + 4x3 x1+ 2x2 +3x3 = 180 2x1- 3x2 + x3 60 5x1 + 3x2 240 x1 0, x2 0)n,.,2 , 1j (0 x)m,.,2 , 1i (bxa)P(xczmax jn1jijijn1jjj原問題：)m,.,2

11、 , 1i (0y)n,.,2 , 1j (cya)D(ybmin wim1ijiijm1iji其對偶問題為：1、弱對偶性、弱對偶性n1jm1iiijjijybxcDPy,x）的可行解，則有：），（分別為（如果n1jm1iiijjm1im1im1iijn1jijijn1jijiin1jn1jm1iijn1jijjim1iijjjybxcyxay)xaybyxax)yaxc所以（因為證l原問題任一可行解的目標函數(shù)值是其對偶問題原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任一可行目標函數(shù)值的下界；反之，對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。解的目標函

12、數(shù)值是其原問題目標函數(shù)值的上界。l如原問題有可行解且其目標函數(shù)值無界（具有如原問題有可行解且其目標函數(shù)值無界（具有無界解），則其對偶問題無可行解；反之，對無界解），則其對偶問題無可行解；反之，對偶問題有可行解且其目標函數(shù)值無界，則其原偶問題有可行解且其目標函數(shù)值無界，則其原問題無可行解（注意，本點性質(zhì)的逆不成立）。問題無可行解（注意，本點性質(zhì)的逆不成立）。l若原問題有可行解而其對偶問題無可行解，則若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界；反之，對偶問題有可原問題目標函數(shù)值無界；反之，對偶問題有可行解而其原問題無可行解，則對偶問題的目行解而其原問題無可行解，則對偶問題的目標函

13、數(shù)值無界。標函數(shù)值無界。212minxxz0, 02221212121xxxxxx無可行解 St例：例：2122maxyyw002211212121yyyyyy解有可行解，則必有無界而對偶問題：2、最優(yōu)性、最優(yōu)性的最優(yōu)解則它們是）的可行解，且有：），（分別為（如果(D)(P),ybxcDPyxn1jm1iiijjij ,3、強對偶性、強對偶性 若原問題及其對偶問題均具有可行解，則若原問題及其對偶問題均具有可行解，則兩者均有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)兩者均有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。值相等。4 互補松弛性互補松弛性 在線性規(guī)劃的最優(yōu)解中，如果對應(yīng)某一在線性規(guī)劃的最優(yōu)解中，如果對應(yīng)

14、某一約束條件的對偶變量值為非零，則該約束約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴條件取嚴格等式；反之如果約束條件取嚴格不等式，則對應(yīng)的對偶變量一定為零。格不等式，則對應(yīng)的對偶變量一定為零。0y 0b-x a0b-x a0y 0y b-x am.1i2.220b-x a0y 2.220y b-x a2.212.21y bx c2.21y by x ax ciijn1jijijn1jijiiijn1jijijn1jijim1iiijn1jijn1jm1iiijjn1jm1iiim1iijn1jijjj 時，必有當時，必有由此當有，）式成立必須對所有，故（，因）（）式

15、右端等式得應(yīng)全為等式。由（）式中，故（又根據(jù)最優(yōu)性）（由弱對偶性知證證明同上，則如果有時，則如果有對偶問題同樣有：0 x cy acy a0 x jjim1iijjim1iijj求對偶問題的最優(yōu)解。），（的最優(yōu)解為例、已知線性規(guī)劃,Tj321321321026X*1,2,3j0,x16x2x2x10 x2x xx4x3xmax Z26w11Y1y1y42y2y32yy0 x0 x0y0y1yy42y2y32yy1610212212），最優(yōu)值，（，解得：變量等于零，即、二個約束的松弛，所以對偶問題的第一，因為解、對偶問題是*,min211212121121yyw例：例： min = 2x1+3x

16、2+5x3+2x4+3x5 其對偶解其對偶解 y1 =4/5 y2 =3/5 Z =5 用對偶理論求用對偶理論求(P)的最優(yōu)解的最優(yōu)解x1+x2+2x3+x4+3x5 42x1 -x2+3x3+x4+x5 3 xi 0 ( i =1 5 )(P)解：解：(D)為為maxZ =4y1+3y2y1+2y2 2 y1 - y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1 , y2 0將將y1 ，y2 代入，知代入，知, , 為嚴格不等式為嚴格不等式 x2 = x3 = x4 = 0 x = (1, 0, 0, 0, 1)T Z=5由由y1 ，y20知原約束為等式知原約束為等式 x

17、1+3x5 =42x1+x5 =3l 綜合以上對偶定理，互為對偶的兩個線性綜合以上對偶定理，互為對偶的兩個線性規(guī)劃問題的解之間的關(guān)系，只可能有三種情況：規(guī)劃問題的解之間的關(guān)系，只可能有三種情況：（1)兩個問題都存在最優(yōu)解，且目標函數(shù)最優(yōu)值兩個問題都存在最優(yōu)解，且目標函數(shù)最優(yōu)值相等；相等；（2）兩個問題都不存在可行解；）兩個問題都不存在可行解；（3）一個問題無界，而另一個問題不存在可行）一個問題無界，而另一個問題不存在可行解。解。*m1iiin1jjj*wybxcz*Z*=yb=(y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymZ=bi yi對對求求bi的偏導(dǎo)：的偏導(dǎo)：

18、z* bi=yi*yi* 影子價格（影子價格（shadow price）。）。 yi*的意義代表在資源最優(yōu)利用條件的意義代表在資源最優(yōu)利用條件下對單位第下對單位第i種資源的估價種資源的估價;bi 的單位改變的單位改變量所引起的目標函數(shù)值的改變量。量所引起的目標函數(shù)值的改變量。yi ：反映：反映bi 的邊際效益的邊際效益( (邊際成本邊際成本) )例例1中中y1 =50, 當機器臺時數(shù)增加當機器臺時數(shù)增加1個單位時，個單位時，工廠可增加利潤工廠可增加利潤50個單位。個單位。求解問題求解問題 LP1得：得：X* = （x1,x2,x3,x4,x5)T = (50,250,0,50,0)T Max

19、z = 27500求解問題求解問題 LP2得：得：Y* = （y1,y2,y3,y4,y5, y6,)T = (50,0,50,0,0,0)TMin z = 27500l根據(jù)對偶問題的互補松馳性質(zhì)中有根據(jù)對偶問題的互補松馳性質(zhì)中有 生產(chǎn)過程中如果某種資源生產(chǎn)過程中如果某種資源bi未得到充分利用未得到充分利用時，該種資源的影子價格為零；又當資源時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種在生產(chǎn)中的影子價格不為零時，表明該種在生產(chǎn)中已消耗完畢。已消耗完畢。，時，有當時，in1jjijiiin1jjijbxa0y0ybxa;例例.某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，消耗的資源某企業(yè)生產(chǎn)甲、

20、乙兩種產(chǎn)品，消耗的資源等情況見下表所示，問應(yīng)如何組織生產(chǎn)，使利等情況見下表所示，問應(yīng)如何組織生產(chǎn)，使利潤最大？潤最大？甲 乙每天可用量資源單位成本AB2 31 225單位15小時5元/單位10元/小時產(chǎn)品售價（元）23 40第一種模型第一種模型:),(*,*,max21212111116Y40z152555X015250203210 x54023ZTj434343對偶變量：，），（最優(yōu)解：xxxxxxxxxxxx),(*,*,max21212111Y40z55X015225323ZTj對偶變量：，），（最優(yōu)解：xxxxxxx第二種模型第二種模型:l一般說對線性規(guī)劃的求解是確定資源的一般說對線性

21、規(guī)劃的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當估價，這種估價則是確定對資源的恰當估價，這種估價直接涉及資源的最有效利用。直接涉及資源的最有效利用。第二節(jié) 圖解法的靈敏度分析 靈敏度分析（靈敏度分析（Sensitivity Analysis) 是指對系統(tǒng)或是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度。即，在建立數(shù)事物因周圍條件變化顯示出來的敏感程度。即，在建立數(shù)學(xué)模型和求得最優(yōu)解之后學(xué)模型和求得最優(yōu)解之后,研究線性規(guī)劃的系數(shù)研究線性規(guī)劃的系數(shù)ci,aij,bj等變等變化時化時,對最優(yōu)解產(chǎn)生什么影響對最優(yōu)解產(chǎn)生什么影響?一一 目標

22、函數(shù)中的系數(shù)目標函數(shù)中的系數(shù)cj,的靈敏度分析的靈敏度分析 l 我們以下面的例題來看一下我們以下面的例題來看一下cj的變化的變化是如何來影響最優(yōu)解的是如何來影響最優(yōu)解的:l l 例例1、 某工廠在計劃期內(nèi)安排甲、乙某工廠在計劃期內(nèi)安排甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需設(shè)備兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需設(shè)備和和A 、B原材料消耗和所獲利潤如下表所原材料消耗和所獲利潤如下表所示示 甲乙資源限量設(shè)備11300臺時原料A 21400千克原料B01250千克利潤（元） 50100 問：工廠應(yīng)分別生產(chǎn)甲、乙產(chǎn)品各多少，才能使工廠問：工廠應(yīng)分別生產(chǎn)甲、乙產(chǎn)品各多少，才能使工廠獲利最多？獲利最多？設(shè)：甲設(shè)：

23、甲 x1， 乙乙 x2該線性規(guī)劃的模型為：該線性規(guī)劃的模型為： max z = 50 x1+100 x2 x1+x2 300 2x1+x2 400 (LP1) x2 250 x1 0, x2 0求解問題求解問題 LP1得：得：X* = （x1,x2,x3,x4,x5)T = (50,250,0,50,0)T Max z = 27500用圖解的方法定出利潤變化的范圍用圖解的方法定出利潤變化的范圍z直線直線E 的方程為的方程為:E: x1+x2 = 300 x2 = -x1+ 300F: x2= 0 x1+250G: x2 = -2x1+ 400目標函數(shù)目標函數(shù): z = c1x1+ c2x2 也

24、可表示為也可表示為: x2 = x1+c2-c1c2z100200300100200300 x1x2直線直線G（原料（原料A的約束）的約束）直線直線E （設(shè)備約束）（設(shè)備約束）50 x1+100 x2=27500直線直線F點仍然是最優(yōu)解。之間變化時，元到的利潤在不變時，單位產(chǎn)品即當解得：不變，則有假設(shè)當B1000100c100c00100c1100c0cc1211221點仍然是最優(yōu)解。元時，利潤只要大于等于的不變時，而單位產(chǎn)品即當解得：不變，則有假設(shè)的變化范圍：計算B5050cc500c50150cc12212l假定前例中的假定前例中的A設(shè)備臺時數(shù)增加了設(shè)備臺時數(shù)增加了10個個臺時臺時,共有共

25、有310個臺時，此時約束條件就個臺時，此時約束條件就變?yōu)樽優(yōu)?310 xx21100200300100200300 x1x2*50 x1+100 x2=27500BC*B/ (60,250)為最優(yōu)解為最優(yōu)解MAX Z=28000元元其影子價格為其影子價格為: 500/10=50 如果原材料如果原材料A增加增加10千克千克,將會對最優(yōu)解和最優(yōu)值產(chǎn)將會對最優(yōu)解和最優(yōu)值產(chǎn)生影響什么生影響什么?100200300100200300 x1x250 x1+100 x2=27500最優(yōu)解仍最優(yōu)解仍然為然為B點點 當約束條件的右邊常數(shù)增加一個單位時當約束條件的右邊常數(shù)增加一個單位時: 1 如果影子價格大于零如

26、果影子價格大于零,則其最優(yōu)目標函數(shù)值得則其最優(yōu)目標函數(shù)值得到改進到改進,即求最大值時即求最大值時,變得更大變得更大;求最小值時求最小值時,變得更小變得更小. 2如果如果影子影子價格小于零價格小于零,則其最優(yōu)目標函數(shù)值變壞則其最優(yōu)目標函數(shù)值變壞,即求最大值時即求最大值時,變得小了變得小了;求最小值時求最小值時,變得大了變得大了. 3如果如果影子影子價格等于零價格等于零,則其最優(yōu)目標函數(shù)值不便則其最優(yōu)目標函數(shù)值不便. 例例8：某部門現(xiàn)有資金：某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的萬元，今后五年內(nèi)考慮給以下的l項目投資，已知項目項目投資，已知項目A：從第一年到第五年每年年初都可投資，：從第

27、一年到第五年每年年初都可投資，l當年末能收回本利當年末能收回本利110%。l 項目項目B：從第一年到第四年每年年初都可以投資，次年末：從第一年到第四年每年年初都可以投資，次年末l回收本利回收本利125%，但規(guī)定每年最大投資額不能超過，但規(guī)定每年最大投資額不能超過30萬元。萬元。l 項目項目C：第三年初需要投資，到第五年末能回收本利：第三年初需要投資，到第五年末能回收本利140%，l但規(guī)定最大投資額不能超過但規(guī)定最大投資額不能超過80萬元。萬元。l 項目項目D：第二年初需要投資，到第五年末能回收本利：第二年初需要投資，到第五年末能回收本利155%，l但規(guī)定最大投資額不能超過但規(guī)定最大投資額不能超

28、過100萬元。萬元。l 據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下所示：據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下所示：項目項目風(fēng)險指數(shù)（每萬元每次）風(fēng)險指數(shù)（每萬元每次）A1B3C4D5.5問：問：1）應(yīng)如何確定這些項目的每年投資額，使得第五年）應(yīng)如何確定這些項目的每年投資額，使得第五年 末擁有資金的本利金額為最大？末擁有資金的本利金額為最大？ 2）應(yīng)如何確定這些項目的每年投資額，使得第五年）應(yīng)如何確定這些項目的每年投資額，使得第五年 末擁有資金的本利在末擁有資金的本利在330萬的基礎(chǔ)上使得其投資總?cè)f的基礎(chǔ)上使得其投資總 的風(fēng)險系數(shù)為最??？的風(fēng)險系數(shù)為最小？解：解：（1）確定變量）確定變量1）我們設(shè)）我們設(shè)

29、xij=第第i年初投資于年初投資于j 項目的金額項目的金額(單位萬元）根據(jù)單位萬元）根據(jù)給定條件，將變量列于下表：給定條件，將變量列于下表： 年份年份項目項目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D 801.11.251.4301001.55(10)(11)(2)約束條件約束條件 第一年：第一年： x1A+ x1B=200 第二年：第二年： x2A + x2B +x2D = 1.1 x1A 第三年：第三年： x3A + x3B + x3C =1.1x2A+1.25 x1B 第四年：第四年： x4A + x4B =1.1 x3A+1.25 x2B 第五

30、年：第五年： x5A = 1.1x4A + 1.25 x3B 此外：對項目此外：對項目B，C，D的投資額的限制有：的投資額的限制有： xiB 30 (i=1,2,3,4) x3C 80 x2D 100(3）目標函數(shù)）目標函數(shù)Max z=1.1 x5A +1.25 x4B +1.40 x3C +1.55 x2D 數(shù)學(xué)模型為：數(shù)學(xué)模型為：目標函數(shù)目標函數(shù) MAX 1.1X5+1.25X9+1.40X10+1.55X11S.T. 約束約束 1) : X1+X6=200 約束約束 2) : -1.1X1+X2+X7+X11=0 約束約束 3) : -1.1X2+X3-1.25X6+X8+X10=0 約

31、束約束 4) : -1.1X3+X4-1.25X7+X9=0 約束約束 5) : -1.1X4+X5-1.25X8=0 約束約束 6) : X630 約束約束 7) : X730 約束約束 8) : X830 約束約束 9) : X930 約束約束 10) : X1080 約束約束 11) : X11100 xij 0 *最優(yōu)解如下最優(yōu)解如下* 目標函數(shù)最優(yōu)值為目標函數(shù)最優(yōu)值為 : 341.35 變量變量 最優(yōu)解最優(yōu)解 相差值相差值 - - - x 1 170 0 x 2 63 0 x 3 0 .044 x 4 0 0 x 5 33.5 0 x 6 30 0 x 7 24 0 x 8 26.8

32、 0 x 9 30 0 x 10 80 0 x 11 100 0 約束約束 松弛松弛/剩余變量剩余變量 對偶價格對偶價格 - - - 1 0 1.664 2 0 1.513 3 0 1.375 4 0 1.21 5 0 1.1 6 0 .055 7 6 0 8 3 0 9 0 .04 10 0 .025 11 0 .037目標函數(shù)系數(shù)范圍目標函數(shù)系數(shù)范圍: 變量變量 下限下限 當前值當前值 上限上限 - - - - X 1 無下限無下限 0 .055 X 2 0 0 .037 X 3 無下限無下限 0 .044 X 4 無下限無下限 0 0 X 5 0 1.1 1.12 X 6 -.055 0

33、 無上限無上限 X 7 -.05 0 0 X 8 0 0 .025 X 9 1.21 1.25 無上限無上限 X 10 1.375 1.4 無上限無上限 X 11 1.513 1.55 無上限無上限 常數(shù)項范圍常數(shù)項范圍: 約束約束 下限下限 當前值當前值 上限上限 - - - - 1 177.851 200 202.645 2 -24.364 0 2.909 3 -26.8 0 3.2 4 -7.5 0 3.636 5 -33.5 0 無上限無上限 6 0 30 87.273 7 24 30 無上限無上限 8 26.8 30 無上限無上限 9 26.364 30 37.5 10 76.8 8

34、0 106.8 11 97.091 100 124.3642) 所設(shè)變量與所設(shè)變量與1）相同，有：）相同，有：Min z =x1A+x2A +x3A+x4A+x5A+3(x1B+x2B+x3B+x4B)+ 4 x3C +5.5 x2Ds.t, x1A+ x1B=200 x2A + x2B +x2D - 1.1 x1A= 0 x3A + x3B + x3C -1.1x2A-1.25 x1B = 0 x4A + x4B -1.1 x3A-1.25 x2B = 0 x5A -1.1x4A -1.25 x3B = 0 xiB 30 (i=1,2,3,4) x3C 80 x2D 100 1.1 x5A

35、+1.25 x4B +1.40 x3C +1.55 x2D 33 0 xij 0 目標函數(shù)目標函數(shù) MIN X1+X2+X3+X4+X5+3X6+3X7+3X8+3X9+4X10+5.5X1.T. 約束約束 1) : X1+X6=200 約束約束 2) : -1.1X1+X2+X7+X11=0 約束約束 3) : -1.1X2+X3-1.25X6+X8+X10=0 約束約束 4) : -1.1X3+X4-1.25X7+X9=0 約束約束 5) : -1.1X4+X5-1.25X8=0 約束約束 6) : X630 約束約束 7) : X730 約束約束 8) : X830 約束約束 9) :

36、X930 約束約束 10) : X1080 約束約束 11) : X11330*最優(yōu)解如下最優(yōu)解如下* 目標函數(shù)最優(yōu)值為目標函數(shù)最優(yōu)值為 : 1300 變量變量 最優(yōu)解最優(yōu)解 相差值相差值 - - - x 1 200 0 x 2 192.317 0 x 3 131.549 0 x 4 144.704 0 x 5 159.174 0 x 6 0 .5 x 7 0 .5 x 8 0 .5 x 9 0 .5 x 10 80 0 x 11 27.683 0 約束約束 松弛松弛/剩余變量剩余變量 對偶價格對偶價格- - - 1 0 10 2 0 10 3 0 10 4 0 10 5 0 10 6 30 0 7 30 0 8 30 0 9 30 0 10 0 0 11 72 0 12 0 -10目標函數(shù)系數(shù)范圍目標函數(shù)系數(shù)范圍: 變量變量 下限下限 當前值當前值 上限上限 - - - - X 1 無下限無下限 1 1.5 X 2 .024 1 1 X 3 1 1 1.781 X 4 1 1 1.71 X 5 1 1 1.645 X 6 2.5 3 無上限無上限 X 7 2.5 3 無上限無上限 X 8 2.5 3 無上限無上限 X 9 2.5 3