管理運(yùn)籌學(xué)講義第2章對偶規(guī)劃

1、石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,1,第2章 對偶規(guī)劃,Sub title,學(xué)習(xí)要點,理解線性規(guī)劃問題的對偶問題 構(gòu)建線性規(guī)劃問題的對偶模型 正確理解對偶規(guī)劃的基本性質(zhì) 掌握影子價值的涵義及其應(yīng)用 資源總存量和分配量增減決策,石家莊經(jīng)濟(jì)學(xué)院

2、 管理科學(xué)與工程學(xué)院,2,例1 某廠生產(chǎn)甲乙兩種產(chǎn)品，生產(chǎn)工藝路線為：各自的零部件分別在設(shè)備A、B加工，最后都需在設(shè)備C上裝配。經(jīng)測算得到相關(guān)數(shù)據(jù)如表所示。應(yīng)如何制定生產(chǎn)計劃，使總利潤為最大。 據(jù)市場分析，單位甲乙產(chǎn)品的銷售價格分別為73和75元，試確定獲利最大的產(chǎn)品生產(chǎn)計劃。,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型,一、對偶問題的提出,石家莊經(jīng)濟(jì)學(xué)院

3、 管理科學(xué)與工程學(xué)院,3,LP模型：,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,4,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型,一、對偶問題的提出,若例1中該廠的產(chǎn)品平銷，現(xiàn)有另一企業(yè)想租賃其設(shè)備。廠方為了在談判時心中有數(shù)，需掌握設(shè)備臺時費用的最低

4、價格，以便衡量對方出價，對出租與否做出抉擇。在這個問題上廠長面臨著兩種選擇：自行生產(chǎn)或出租設(shè)備。首先要弄清兩個問題：①合理安排生產(chǎn)能取得多大利潤? ②為保持利潤水平不降低，資源轉(zhuǎn)讓的最低價格是多少？問題 ①的最優(yōu)解：x1=4，x2=5，Z*=37。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,5,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型

5、,一、對偶問題的提出,出讓定價,假設(shè)出讓A、B、C設(shè)備單位設(shè)備臺時所得利潤分別為y1、y2、y3原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺時，如若出讓，不應(yīng)低于自行生產(chǎn)帶來的利潤，否則寧愿自己生產(chǎn)。于是有 2y1+0y2+3y3≥ 3同理，對乙產(chǎn)品而言，則有 0y1+2y2+4y3≥ 5設(shè)備臺時出讓的收益（最低期望收益值） min? =16y1+10y2+32y3顯然還有： y1，y2，y3

6、≥0,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,6,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型,一、對偶問題的提出,例1的對偶問題的數(shù)學(xué)模型,對偶問題的最優(yōu)解： y1=0，y2=1/2，y3=1，W* =37兩個問題的目標(biāo)函數(shù)值相等并非偶然前者稱為線性規(guī)劃原問題，則后者為對偶問題，反之亦然。 對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始

7、基變量的檢驗數(shù)的相反數(shù)。,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,7,對偶問題的定義： （對稱形式）,（LP ） max Z=c1 x1 + c2 x2 + ... + cn xn s.t. a11x1 + a12 x2 + ... + a1nxn ? b1 . . . . .

8、 . am1x1 + am2x2 + ...+ amn xn ? bm x1 , x2 , ... , xn ? 0（DP） min W=b1 y1+ b2 y2+ ... + bm ym s.t. a11y1+ a21 y2+ ... + am1 ym ? c1 . . . . . .

9、 a1ny1+ a2n y2+ ... + amnym ? cn y1 , y2 , ... , ym ? 0,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,8,(LP) Max z = cT

10、 x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 則（DP）稱為（LP）的對稱形式的對偶問題,設(shè)：,石家莊經(jīng)濟(jì)學(xué)院

11、 管理科學(xué)與工程學(xué)院,9,原問題與對偶問題之間的對應(yīng)規(guī)律見表,一個問題的約束條件總是對應(yīng)于另一問題的決策變量,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,10,把LP看作一個使收益最大的生產(chǎn)計劃問題，其中的技術(shù)約束看作資源約束，那么對偶問題的最優(yōu)解y1*，y2*，…ym*分別稱為m種資源的影子價格。下面將

12、會看到，它與原問題最優(yōu)解有密切關(guān)系，并在經(jīng)濟(jì)管理中有重要的作用。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,11,綜上所述，其變換形式歸納如下：,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,12,例 寫出下面線性規(guī)劃的對偶規(guī)劃模

13、型,,解：按照對稱形式的對偶關(guān)系，其對偶模型為,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,13,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,14,二、如何將一般問題轉(zhuǎn)化為對偶問題,一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的

14、對偶規(guī)劃，下面舉例說明如何寫出其對偶問題。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,15,寫出下列LP的對偶問題： (1)

15、 (2),,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,16,解: 首先把問題改寫為對稱形式，再求它的對偶問題。 式（1）兩邊乘以（－1），成為－2x1+x2≤－1 把式（2）拆成兩個不等式： x1+3x2≤5 －x1－3x2≤－5 然后令x1'=－x1，x1'≥0；令x2= x

16、2'－x2''，x2'≥0，x2''≥0；把原問題變換為等價模型：,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,17,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,18,它的對偶模型是

17、（假定對偶變量為y1'，y2'，y3'）,(a) (b) (c),,石家莊經(jīng)濟(jì)學(xué)院

18、 管理科學(xué)與工程學(xué)院,19,將（a）兩邊乘（－1），把（b）與（c）合并成一個等式，約束條件變?yōu)椋?,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,20,再令y1=－y1‘，y1≤0；令y2=y2’－y3‘，y2無符號約束，最后對偶問題成為：,,石家莊經(jīng)濟(jì)學(xué)院

19、 管理科學(xué)與工程學(xué)院,21,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,22,DP模型與原問題LP模型之間，對應(yīng)規(guī)律表中（2）、（4）、（5）、（6）各項對應(yīng)規(guī)律仍然成立，而（1）、（3）兩項有所變動。仔細(xì)分析上述推導(dǎo)過程可以發(fā)現(xiàn)，如原問題的變

20、量xj無符號約束，則對偶技術(shù)約束為等式；如xj≤0，則對偶技術(shù)約束的不等號要反向（由≥變?yōu)椤埽?；如原問題某個技術(shù)約束為等式，則對偶變量無符號約束；如原問題的某個技術(shù)約束不等式反向（由≤改為≥），則對偶變量≤0?？偨Y(jié)這些規(guī)律，現(xiàn)將一般情形下對偶問題之間的對應(yīng)規(guī)律，匯集在下表中。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,23,,,,,

21、,,xj≥0,,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,24,為了便于記憶對偶約束之間的對應(yīng)規(guī)律，約定下列術(shù)語。在求max值的LP中，把問題設(shè)想為合理利用某些資源以實現(xiàn)收益最大的模型，它的技術(shù)約束一般表示資源限制，通常為≤型的，稱為正向約束；反之，如某個技術(shù)約束為≥型，則稱為反向的；若約束為=型的，則稱為雙向的。對于求min值的

22、LP，把問題設(shè)想為利用某些原料配制一種產(chǎn)品，使得成本最低的模型。這時技術(shù)約束一般表示質(zhì)量要求，往往是≥型的，因此稱為正向的；如某個技術(shù)約束為≤型的，則稱為反向的；如約束為=型的，則稱為雙向的。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,25,就變量的符號約束來說，總是把非負(fù)約束稱為正向的，非正約束稱為反向的，符號無約束稱為雙向的。

23、采用這些術(shù)語，對偶約束之間的對應(yīng)規(guī)律可用一句話來概括：一個問題中的正向（或反號，或雙向）技術(shù)約束，對應(yīng)于另一個問題的正向（或反向，或雙向）變量符號約束，即兩個對偶約束，總屬于同樣的類型。利用這個規(guī)律，可以很容易地寫出任意線性規(guī)劃的對偶規(guī)劃。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,26,寫出線性規(guī)劃的對偶規(guī)劃,,石家莊經(jīng)濟(jì)學(xué)院

24、 管理科學(xué)與工程學(xué)院,27,解: 原問題求min，對偶問題目標(biāo)函數(shù)應(yīng)求max，原問題三個技術(shù)約束分別為反向，正向，雙向的，對偶變量約束分別為y1≤0，y2≥0，y3無約束；x1，x2，x3，x4的符號約束分別為正向，正向，反向，雙向的，對偶技術(shù)約束分別為≤型，≤型，≥型與=型，從而可得對偶線性規(guī)劃為：,,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型

25、,三、對偶規(guī)劃的性質(zhì),為了便于理解，下列性質(zhì)僅對對稱形式的對偶問題進(jìn)行討論，但這些性質(zhì)對于一般情況也是正確的。,min Z’= - CXs.t. - AX ≥-bX ≥0,定理 1：對稱性定理：對偶問題的對偶是原問題。,,,max W’ = -Y´bs.t. -A´Y≤-C´ Y≥0,第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型,三、對偶規(guī)劃的性質(zhì),石家莊經(jīng)濟(jì)學(xué)院

26、 管理科學(xué)與工程學(xué)院,30,弱對偶原理（弱對偶性）：設(shè) 和 分別是問題（P）和（D）的可行解，則必有,定理 2,證：由 P 和 D 的約束條件 AX?b, ATY?C, X?0, y?0 可直接推得 CX ? AT YX = YAX? Yb ,證畢。,石家莊經(jīng)濟(jì)學(xué)院

27、 管理科學(xué)與工程學(xué)院,31,推論1：原問題任一可行解的目標(biāo)函數(shù)值是對偶問題函數(shù)值的下界；對偶問題的任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。,推論2：如原問題有可行解且目標(biāo)函數(shù)值無界，則對偶問題無可行解；對偶問題有可行解且目標(biāo)函數(shù)值無界，則原問題無可行解。,推論3：若原問題有可行解而其對偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；對偶問題有可行解而其原問題無可行解，則對偶問題目標(biāo)函數(shù)值無界。,石家莊經(jīng)濟(jì)學(xué)院

28、 管理科學(xué)與工程學(xué)院,32,定理3（最優(yōu)性判定定理） 設(shè) ， 分別為問題L與D的可行解，且 ，則兩者均為最優(yōu)解。證: 設(shè)X*是L的最優(yōu)解，則 。由定理2，可得 ，但 ，故必有

29、 ，從而 是L的最優(yōu)解。同理可證 是D的最優(yōu)解。,,,,,,,,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,33,定理4（強(qiáng)對偶定理） 如果原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；設(shè)前者的最優(yōu)基為B，則對偶最優(yōu)解為Y*=CBB－1，且兩者最優(yōu)值相等。,綜上所述，一對對偶問題的關(guān)系，只能有下面三種情況之一出

30、現(xiàn)：①都有最優(yōu)解，分別設(shè)為X* 和Y*，則必有CX* =Y*b；②一個問題無界，則另一個問題無可行解；③兩個都無可行解。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,34,定理5：互補(bǔ)松弛定理在LP的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值非零，則該約束條件取嚴(yán)格等式。反之，如果約束條件取嚴(yán)格不等式，則對應(yīng)的對偶變量一定為零

31、。即：若 則 則 若 則 則 恒有,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,35,互補(bǔ)松弛性的經(jīng)濟(jì)意義,若資源的影子價格大于零(yi?0)，必為緊缺資源，約束為緊約束（ ）；若資源有剩余，約束為松約束(

32、 )，其對偶解必為零(yi=0) 。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,36,例 已知線性規(guī)劃 min z = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 s.t. x1 + x2 + 2x3 + x4 + 3x5 ? 4 2x1 - x2

33、+ 3x3 + x4 + x5 ? 3 x1 , x2 , x3 , x4 , x5 ? 0其對偶問題的最優(yōu)解為：y1* = 0.8, y2* = 0.6。試用對偶理論求出它的原問題的最優(yōu)解,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,37,對偶問題： Max w= 4y1

34、 + 3y2 s.t. y1 + 2y2 ? 2 y1 - y2 ? 3 2y1+ 3y2 ? 5 y1+ y2 ? 2 3y1+ y2 ? 3 y1 ? 0, y2 ? 0,代入y1*=0.8, y2*=0.6,松約束? x2 = 0,緊約束? x1 ? 0,松約束? x3 = 0,松約束? x4 = 0,緊約束? x5 ? 0,石家莊經(jīng)濟(jì)學(xué)院

35、 管理科學(xué)與工程學(xué)院,38,原問題的約束為緊約束, 故有: x1 + 3x5 = 4 2x1 + x5 = 3解得：x1* = 1， x5* = 1原問題的最優(yōu)解為：X = (1 , 0 , 0 , 0 , 1) , z* = 5,石家莊經(jīng)濟(jì)學(xué)院

36、 管理科學(xué)與工程學(xué)院,39,例 已知線性規(guī)劃的最優(yōu)解為X*=（0，0，4，4）T。試?yán)没パa(bǔ)松弛定理求對偶問題最優(yōu)解。,,（2.12a）,（2.12b）,（2.12c）,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,40,解 對偶問題為,,（2.13a）,（2.13b）,（2

37、.13c）,（2.13d）,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,41,由于x3*=x4*=4>0，是松約束，故（2.13c）與（2.13d）是緊約束，即對Y*成立等式：,把X*代入原問題三個約束中，可知（2.12c)松的，故y3*=0，然后解方程組：,,石家莊經(jīng)濟(jì)學(xué)院

38、 管理科學(xué)與工程學(xué)院,42,故對偶最優(yōu)解為：Y*=（6/5，1/5，0），z*=w*=28。,,,得到,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,43,例 求解下面線性規(guī)劃問題，并根據(jù)最優(yōu)單純形表中的檢驗數(shù)，給出其對偶問題的最優(yōu)解。,解 引入松弛變量、將模型化為標(biāo)準(zhǔn)型，

39、經(jīng)求解后得到其最優(yōu)單純形表,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,44,對偶規(guī)劃的最優(yōu)解為 :,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,45,第二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,一、影子價值的內(nèi)涵,,yi是資源bi每增加一個單位對

40、目標(biāo)函數(shù)Z的貢獻(xiàn)；對偶變量 yi在經(jīng)濟(jì)上表示原問題第i種資源的邊際價值。對偶變量的值 yi*表示第i種資源的邊際價值，稱為影子價值。若原問題價值系數(shù)Cj表示單位產(chǎn)值，則yi 稱為影子價格。若原問題價值系數(shù)Cj表示單位利潤，則yi 稱為影子利潤。影子價格=資源成本+影子利潤,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,46,第

41、二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,一、影子價值的內(nèi)涵,影子價格不是資源的實際價格，它反映了資源配置結(jié)構(gòu)。是當(dāng)其它數(shù)據(jù)不變時，某資源增加一個單位導(dǎo)致目標(biāo)函數(shù)的增量。對資源i總存量的評估：購進(jìn) or 出讓對資源i當(dāng)前分配量的評估：增加 or 減少,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,47,第二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,一、影子價值的

42、內(nèi)涵,第一，影子利潤說明增加哪種資源對經(jīng)濟(jì)效益最有利第二，影子價格告知以怎樣的代價去取得緊缺資源（將影 子價格與市場價格相比較），購進(jìn)or賣出。第三，影子價格是機(jī)會成本，提示資源出租/轉(zhuǎn)讓的基價第四，利用影子價格分析新品的資源效果：定價決策第五，利用影子價格分析現(xiàn)有產(chǎn)品價格變動時對資源緊缺情況的影響第六，可以幫助分析工藝改變后對資源節(jié)約的收益第七，可以預(yù)知哪些資源是稀缺資源而哪些資源不稀缺,石家莊經(jīng)濟(jì)學(xué)院

43、 管理科學(xué)與工程學(xué)院,48,例：某廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品的資源消耗如下表所示。 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使每周的利潤為最大。如果企業(yè)可以不生產(chǎn)，那資源出讓如何定價？,第二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,二、資源獲利決策,石家莊經(jīng)濟(jì)學(xué)院

44、 管理科學(xué)與工程學(xué)院,49,決策變量：要確定甲、乙兩種產(chǎn)品的產(chǎn)量，我們設(shè)每周生產(chǎn)的甲產(chǎn)品的產(chǎn)量x1，每周生產(chǎn)的乙產(chǎn)品的產(chǎn)量 x2。由上表計算單位甲產(chǎn)品的成本為383元，單位乙產(chǎn)品的成本為340元，則它們的盈利能力分別為7和12。生產(chǎn)計劃的線性規(guī)劃模型：,第二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,二、資源獲利決策,石家莊經(jīng)濟(jì)學(xué)院

45、 管理科學(xué)與工程學(xué)院,50,二、資源獲利決策,如果決策者考慮自己不生產(chǎn)甲乙兩種產(chǎn)品，而把原擬用于生產(chǎn)這兩種產(chǎn)品的原材料、設(shè)備工時、電量資源全部出售給外單位，或者做代加工，則應(yīng)如何確定這三種資源的價格。,設(shè)原材料的單位出讓獲利為y1，設(shè)備工時的單位出讓獲利為y2，電量的單位出讓獲利為y3 。出讓決策的線性規(guī)劃模型：,第二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,石家莊經(jīng)濟(jì)學(xué)院

46、 管理科學(xué)與工程學(xué)院,51,三、影子價格、影子利潤與企業(yè)的價值取向,第二節(jié) 對偶規(guī)劃的經(jīng)濟(jì)解釋,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,52,52,LP模型：,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)

47、與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,53,53,例1（利潤最大化模型）,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院

48、 管理科學(xué)與工程學(xué)院,54,54,例1（利潤最大化模型）,三種資源的影子利潤分別為：y1=0 y2=0.5 y3=1,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,55,55,例1（

49、利潤最大化模型）,影子價格=資源成本+影子利潤,三種資源的影子價格分別為：y1=20+0=20 y2=15+0.5=15.5y3=10+1=11,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院

50、,56,56,LP模型：,例1（產(chǎn)值最大化模型）,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,57,57,例1（產(chǎn)值最大化模型）,石家莊經(jīng)濟(jì)學(xué)院

51、 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,58,58,例1（產(chǎn)值最大化模型）,三種資源的影子價格分別為：y1=8.375 y2=0 y3=18.75,石家莊經(jīng)濟(jì)學(xué)院

52、管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,59,59,LP1模型（利潤最大化）,LP2模型（產(chǎn)值最大化）,三種資源的影子價格分別為：y1=20 y2=15.5 y3=11,三種資源的影子價格分別為：y1=8.375 y2=0 y3=18.75,石家莊經(jīng)濟(jì)學(xué)院

53、 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,60,60,LP1模型（利潤最大化）,LP2模型（產(chǎn)值最大化）,最優(yōu)解：x1=4 x2=5產(chǎn)值：73*4+75*5=667利潤：4*3+5*5=37資源消耗：A:8 B:10 C:32,最優(yōu)解：x1=

54、8 x2=2產(chǎn)值：73*8+75*2=734利潤：8*3+2*5=34資源消耗：A:16 B:4 C:32,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,61,,例,第三節(jié) 對偶單純型法,石家

55、莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,62,,,按照第一章的方法，可用人工變量法求解，而現(xiàn)在可用對偶單純形法求解。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,63,（1）建立初始單純形表，使得所有檢驗數(shù)σj≤0；（2）檢查表

56、中b列元素，如果所有bi≥0，則已得到最優(yōu)解，結(jié)束。否則轉(zhuǎn)入下一步；（3）確定換出變量：設(shè) ，則第l方程原基變量為換出變量，第l行為主元行；（4）確定換入變量：設(shè) ，則xk為換入變量，第k列為主元列；（5）以alk為主元作換基迭代運(yùn)算，方法與單純形法完全相同，得到新的單純形表，返回

57、步驟（2）。,,,對偶單純形法計算步驟：,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,64,,關(guān)于原問題無可行解的情況說明：,如果b存在至少一個負(fù)分量, 且 ?i? 0 , ?i = (?i1, ?i2, ... ?in)，由線性規(guī)劃的典則方程：,再由條件bi < 0和 ?i ?0，(xB)i 不可能變?yōu)檎虼嗽瓎栴}無可行解

58、。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,65,例 用對偶單純形法解線性規(guī)劃,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,66,以y4，y5為初始基變量，相應(yīng)的基本解Y=（0，0，0， -2，-1）是非可行解，

59、但檢驗數(shù)符合最優(yōu)檢驗條件（全部≤0），故可列表用對偶單純形法計算。,,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,67,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,68,在第三表中，原問題與對偶問題均為可行解，故它是最優(yōu)表，Y*=（

60、0，1/4，1/2，0，0），w*=17/2。兩點說明： （1）步驟（4）中的確定換入變量法則，目的是為了保證下一張表中對偶問題仍然有基可行解（即所有σj≤0）。在上面的初始表中，可以產(chǎn)生兩個比值， -24/（-6）=4與-5/（-1）=5，如果不用前者對應(yīng)的-6作為主元迭代，而用后者對應(yīng)的-1作為主元迭代，則下一張表的檢驗行將會出現(xiàn)正值(請同學(xué)們自行驗證)，從而破壞了對偶問題解的可行性。 （2

61、）若存在某個xl<0，而所有alj≥0，j=1，…，n，顯然第l方程是矛盾方程，問題無可行解。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,69,對偶單純形方法的基本思想:,單純形方法始終保持原問題的解可行，檢驗數(shù)不一定小于等于零（即對偶解不可行）。一旦檢驗數(shù)小于等于零（即對偶解變?yōu)榭尚薪猓瑒t問題達(dá)到最優(yōu)。,對偶單純形方法的基

62、本思想：首先保證對偶問題可行，即保證σ= C - CBB-1A ? 0；一旦原問題可行，即：XB = B-1b ? 0，則找到最優(yōu)解。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,70,原始與對偶單純形法的對比,石家莊經(jīng)濟(jì)學(xué)院

63、 管理科學(xué)與工程學(xué)院,71,例 用對偶單純形方法求解：,解: （1）引入松弛變量 x3 , x4 , x5 化為標(biāo)準(zhǔn)形，并在約束等式兩側(cè)同乘-1，得到,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,72,取x3 , x4 , x5為基變量，檢驗數(shù)皆非正，因此可構(gòu)初始對偶單純形表,石家莊經(jīng)濟(jì)學(xué)院

64、 管理科學(xué)與工程學(xué)院,73,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,74,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,75,例 用對偶單純形法求解

65、下面線性規(guī)劃,解: 構(gòu)造對偶單純形表進(jìn)行迭代，,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,76,從最后的表可以看到，B-1b列元素中有-2<0，并且，-2所在行各元素皆非負(fù)，因此，原規(guī)劃沒有可行解。,石家莊經(jīng)濟(jì)學(xué)院

66、管理科學(xué)與工程學(xué)院,77,對偶單純形法適合于解如下形式的線性規(guī)劃問題:,在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進(jìn)行求解，非常方便 。,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,78,第四節(jié) 線性規(guī)劃靈敏度分析,一、單純形法的矩陣描述,石家莊經(jīng)濟(jì)學(xué)院

67、 管理科學(xué)與工程學(xué)院,79,其中XS=（xs1，xs2，xsm）T是松弛變量組成的列向量。從表可以清楚地看到，以B為基的單純形表中的增廣矩陣，是以B－1左乘初始表的增廣矩陣的結(jié)果；因此，在B為基的表中，與初始表單位矩陣相同位置上即為B的逆矩陣B-1。這是一個很有用的普遍規(guī)律。這一點還可以利用初等變換知識加以說明：初始表經(jīng)過若干次

68、行的初等變換轉(zhuǎn)化為以B為基的單純形表，在這個過程中，它把矩陣B變成為單位矩陣I，從而把單位矩陣I變成B-1。,第四節(jié) 線性規(guī)劃靈敏度分析,石家莊經(jīng)濟(jì)學(xué)院 管理科學(xué)與工程學(xué)院,80,第四節(jié) 線性規(guī)劃靈敏度分析,二、靈敏度分析的必要性,1. 優(yōu)化方案建立在特定的資源環(huán)境和技術(shù)條件之上，而資源環(huán)境和技術(shù)條件是不斷變化的；2. 基