最優(yōu)化方法課件：2-4 對偶規(guī)劃與靈敏度分析

1、14 對偶規(guī)劃與靈敏度分析 對偶線性規(guī)劃 對偶定理 對偶單純形法 靈敏度分析2 對偶理論是線性規(guī)劃的重要內容之一。對應于每個線性規(guī)劃問題都伴生一個相應的線性規(guī)劃問題。 原問題和對偶問題緊密關聯(lián)，它們不但有相同的數(shù)據(jù)集合，相同的最優(yōu)目標函數(shù)值，而且在求得一個線性規(guī)劃的最優(yōu)解的同時，也同步得到對偶線性規(guī)劃的最優(yōu)解。 由對偶問題引伸出來的對偶解還有著重要的經(jīng)濟意義，是研究經(jīng)濟學的重要概念和工具之一。 3對偶問題的提出例1、某工廠生產(chǎn)甲,乙兩種產(chǎn)品，這兩種產(chǎn)品需要在A,B,C三種不同設備上加工。每種甲、乙產(chǎn)品在不同設備上加工所需的臺時，它們銷售后所能獲得的利潤，以及這三種設備在計劃期內能提供的有限臺時

2、數(shù)均列于表。試問如何安排生產(chǎn)計劃，即甲,乙兩種產(chǎn)品各生產(chǎn)多少噸，可使該廠所獲得利潤達到最大。對偶線性規(guī)劃設備每噸產(chǎn)品的加工臺時 可供臺時數(shù) 甲 乙 ABC 359 448 364076 利潤（元/噸） 32 30 4 假設計劃期內甲乙兩種產(chǎn)品各生產(chǎn) 噸，設備每噸產(chǎn)品的加工臺時 可供臺時數(shù) 甲 乙 ABC 359 448 364076 利潤（元/噸） 32 30 用圖解法或單純形法可求得最優(yōu)解 (元) 即在計劃期內甲產(chǎn)品生產(chǎn) 噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤達到最大，為 元。5 現(xiàn)在從另一個角度來考慮該工廠的生產(chǎn)問題:假設該廠打算不再自己生產(chǎn)甲,乙產(chǎn)品，而是把各種設備租讓給其他工廠，這時工廠的決

3、策者應該如何確定各種設備的租價。設 分別為設備A，B，C每臺時的租價，約束條件：把設備租出去所獲得的租金不應低于利用這些設備自行生產(chǎn)所獲得的利潤目標函數(shù)：所獲租金總額盡量少設備每噸產(chǎn)品的加工臺時 可供臺時數(shù) 甲 乙 ABC 359 448 364076 利潤（元/噸） 32 30 6由此可得兩個對稱的線性規(guī)劃：7矩陣形式：8可以得到另一個線性規(guī)劃：稱之為原線性規(guī)劃問題的對偶問題， 對偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問題9101112若令線性規(guī)劃標準型的對偶規(guī)劃為： 線性規(guī)劃問題標準型的對偶問題考慮一個標準形式的線性規(guī)劃問題 由于任何一個等式約束都可以用兩個不等式約束等價地表示，所以標

4、準形線性規(guī)劃問題可等價表示為：它的對偶規(guī)劃為：13對偶線性規(guī)劃的求法從任何一個線性規(guī)劃出發(fā)，都可以求出相應的對偶規(guī)劃，在實際求解過程中，通常不通過求標準型，而是利用如下反映原始問題與對偶問題對應關系的原始對偶表： 目標函數(shù)變量系數(shù)約束條件右端項 約束條件右端項目標函數(shù)變量系數(shù) 約束條件個數(shù)：n個 變量個數(shù)：n個 變量個數(shù)：m個 約束條件個數(shù)：m個 目標函數(shù)minW 目標函數(shù)maxZ 對偶問題（或原問題） 原問題（或對偶問題） 14解：對偶規(guī)劃：例2 寫出下列線性規(guī)劃的對偶問題15例3 寫出下列線性規(guī)劃的對偶問題解：上述問題的對偶規(guī)劃：16本節(jié)討論幾條重要的對偶定理，這些定理揭示了原始問題的解和

5、對偶問題的解之間的基本關系。定理1：（對合性）對偶問題的對偶是原問題。證明：設原問題為對偶問題為改寫對偶問題為對偶問題的對偶為對偶定理17 定理2：弱對偶定理 若是原（極小化）問題的可行解，是對偶（極大化）問題的可行解，那么 證明：因為是對偶問題的可行解，所以滿足約束條件 又因為是原問題的可行解，可得，,所以 。注：原（極小化）問題的最優(yōu)目標函數(shù)值以對偶問題任一可行解的目標函數(shù)值為下界。 對偶（極大化）問題的最優(yōu)目標函數(shù)值以原問題任一可行解的目標函數(shù)值為上界。推論1：如果原問題沒有下界（即minZ），則對偶問題不可行。 如果對偶問題沒有上界（即maxW），則原問題不可行。 若原問題與對偶問題之

6、一無界，則另一個無可行解。18證明：由弱對偶定理，對于原始問題的所有可行解，都有 因此是原問題的最優(yōu)解。同理，對于對偶問題的所有可行解 ，都有 所以 是對偶問題的最優(yōu)解。 推論2：最優(yōu)性定理若是原問題的可行解，是對偶問題的可行解，而且兩者的目標函數(shù)值相等，即，則和分別是原問題和對偶問題的最優(yōu)解。19證明：設是原問題(min)的最優(yōu)解，則對應的基必有。若定義，則 ，因此為對偶問題的可行解，而且 ，由最優(yōu)性定理，是對偶問題的最優(yōu)解。 定理3: 強對偶定理 如果原問題（min)與對偶問題(max)之一有最優(yōu)解，那么另一個也有最優(yōu)解，而且目標函數(shù)值相等。20證明：設滿足原問題(min)的最優(yōu)性條件，則

7、對應的基必有。若定義 ，則 ，因此為對偶問題的基本可行解。 定理4：設滿足原問題(min)的最優(yōu)性條件的一個基本解，則其對應的線性規(guī)劃問題(min)的檢驗數(shù)對應對偶問題的一個基本可行解。21原問題與對偶問題可能出現(xiàn)的情況（1）兩者都有最優(yōu)解，且最優(yōu)值相等；（2）一個有可行解，但無界，則另一個無可行解；（3）兩者都無可行解。22定理5：互補松弛定理如果 分別是原問題(min)和對偶問題（max)的可行解，那么 和 為最優(yōu)解的充要條件是 通常稱之為互補松弛條件。證明：充分性必要性23例5、已知線性規(guī)劃問題:其對偶問題的最優(yōu)解。試用互補松弛定理找出原問題的最優(yōu)解。解：原問題的對偶問題為：由對偶問題最

8、優(yōu)解可知，由互補松弛定理， 解方程組 所以原問題最優(yōu)解24 假設計劃期內甲乙兩種產(chǎn)品各生產(chǎn) 噸，設備每噸產(chǎn)品的加工臺時 可供臺時數(shù) 甲 乙 ABC 359 448 364076 利潤（元/噸） 32 30 用圖解法或單純形法可求得最優(yōu)解 (元) 即在計劃期內甲產(chǎn)品生產(chǎn) 噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤達到最大，為 元。例：對偶最優(yōu)解的經(jīng)濟解釋影子價格 2526由強對偶定理可知，如果原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且它們的目標函數(shù)值相等，即有：其中是線性規(guī)劃原問題約束條件的右端數(shù)據(jù)向量，它代表各種資源的擁有量。為對偶問題最優(yōu)解，它代表在資源最優(yōu)利用條件下對各種單位資源的估價，這種估計不

9、是資源的市場價格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻（如創(chuàng)造利潤，產(chǎn)值等）而作出估價，為區(qū)別起見，稱之為影子價格(shadow price)。27影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內的稀缺程度。如果第i種資源供大于求，即在達到最優(yōu)解時，該種資源沒有用完，或松弛變量，由互補松弛定理，在對偶最優(yōu)解中，第i種資源的影子價格。反之如果第i種資源的影子價格，那么由互補松弛定理，原問題的第i個約束為嚴格等式，即，這表明第i種資源已經(jīng)用完，成為稀缺資源。 資源的影子價格同時也是一種機會成本，在市場經(jīng)濟的條件下，當某種資源的市場價格低于影子價格時，企業(yè)應買進這種資源用于擴大生產(chǎn)；相反當某種資源的市場價

10、格高于影子價格時，企業(yè)應賣出這種資源。隨著資源的買進賣出，企業(yè)資源的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。28設備每噸產(chǎn)品的加工臺時 可供臺時數(shù) 甲 乙 ABC 359 448 364076 利潤（元/噸） 32 30 例：對偶最優(yōu)解其中為設備A的影子價格，在資源最優(yōu)利用的條件下，設備A每增加一個單位臺時，可以使總利潤增加元。若設備可供臺時數(shù)，則29對偶單純形法單純形法是以保持原問題可行為條件，即不論進行怎樣的基變換，常數(shù)列必須保持非負。利用對偶問題的對稱性，我們從另一個角度來考慮求解原問題最優(yōu)解的方法，這種方法以保持對偶問題可行為條件，即不論進行何

11、種基變換，必須保持所有的檢驗數(shù)非負，同時取消原問題必須可行的要求，即取消常數(shù)列的非負限制，通過基變換使原問題在非可行解的基礎上逐步轉換成基本可行解，一旦原問題的基本解可行，則該基本可行解也就是最優(yōu)解，這就是對偶單純形法的基本思想。單純形法： 可行性最優(yōu)性對偶單純形法：最優(yōu)性可行性30例6 求解下列線性規(guī)劃 min z=5x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 min z=5x1+2x2+6x32x1 +4x2+8x3 - x4 =244x1 + x2 +4x3 -x5 =8x1、x2，x3，x4，x50 min z=5x1+2x2

12、+6x32x1 4x2 8x3 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x5031Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-80032對偶單純形法基變換的次序和一般單純形法不同：一般單純形法首先由最大減少原則確定換入變量，然而用最小比值原則確定換出變量 。對偶單純形法則是先將具有負分量的基變量 取出，作為換出變量，然后確定某個非基變量作為換入變量。其變換目的是在保持對偶問題可行性的前提下，使原問題的基本解向可行解靠攏。33對偶單純形法的計算步驟如下：（4）以 為主元進

13、行旋轉變換，得新的單純形表，返回（2）。 （2）確定換出變量 根據(jù) ，確定基變量 作為換出變量。檢驗所在行各元素若所有,則無可行解，停止計算。否則轉入().（3）確定換入變量按最大比值原則，若確定非基變量 為換入變量。（1）根據(jù)原始線性規(guī)劃，列出初始單純形表，檢查b列數(shù)字，若b列數(shù)字全部非負，則已經(jīng)求得最優(yōu)解，停止計算。若b列中至少有一個負分量，則轉入（2）.34例6 用對偶單純形法求解下列線性規(guī)劃 min z=5x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 將問題改寫成如下形式 min z=5x1+2x2+6x32x1 4x2 8x3

14、 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50顯然，p4、p5可以構成現(xiàn)成的單位基，此時，非基變量在目標函數(shù)中的系數(shù)全為負數(shù)，因此p4、p5構成的就是初始正則基。35 7/4 0 1 1/8 -1/21x36 -3 1 0 -1/2 14x22-2/7 0 -2 -1/4 1-2x501 /2 1 2 -1/4 06x22-4 -1 -4 0 1-8x50-2 -4 -8 1 0-24x40 1/2 0 0 1/4 0 4/(-7/2) 2/-2 (1/2)/(-1/4) 4 0 2 1/2 0 5/-2 2 /-4 6/-8 5 2 6 0 0 x1 x2

15、 x3 x4 x5bXBCB 5 2 6 0 0C36最后一個單純形表中，已得到一個可行的正則解，因而得到問題的最優(yōu)解為 X*=（0，4，1）T最優(yōu)值為z*=14（1）對于形如min z=CX，AXb，X0，且C0的線性規(guī)劃問題。因為將其改寫為max (z) =CX，AX+XS=b，X0，則立即可以得到初始正則解； （2）在靈敏度分析中，有時需要用對偶單純形法，可使問題的處理簡化。對偶單純形法在以下情況下較為方便。37例7 用對偶單純形法求解解：先化為標準型 對偶單純形允許約束方程右端為負，因此可將方程2，3兩端同乘-1，可得含單位矩陣的標準型：38據(jù)此列出初始單純形表，并施行對偶單純形法迭代

16、步驟如下： 5/4 7/4 000-1/4 1/4 0102x2 2 -1/4 -3/4 0014x1 3 5/4 3/4 1004x3 0 2/3 0007/3 -1/3 0011/3 10/3 x2 21/3 100-4/3-16/3 x4 0101018 x3 000023100-3-1 -10 x5 00101-1 -2 x4 00013218 x3 0 x5 x4 x3 x2 x1 b XB CB 0002 3 C可得最優(yōu)解 39例8 用對偶單純形法求解下列線性規(guī)劃 min z=x1+2x2x1 +x2 42x1 +3 x218x1、x20解 將問題改寫成如下形式 min z=x1+

17、2x2x1 +x2 + x3 =42x13x2 + x4 =18x1、x2，x3，x40顯然，p3、p4可以構成現(xiàn)成的單位基，此時，非基變量在目標函數(shù)中的系數(shù)全為負數(shù)，因此p3、p4構成的就是初始z正則基。1 0 3 1 -6x11 0 1 -2 -1 10 x221 3/2 0 -1/2 9x110 -1/2 1 1/2 -5x30-2 -3 0 1-15x401 1 1 04x300 0 1 10 1/2 0 1/2 1/-2 2/-3 1 2 0 0 x1 x2 x3 x4 bXBCB 1 2 0 0C41靈敏度分析 線性規(guī)劃問題所對應的數(shù)據(jù)集合，b，常常是通過預測或估計所得到的統(tǒng)計數(shù)據(jù)

18、，在實際使用中，不免會有一定的誤差。而且隨著市場環(huán)境，工藝條件和資源數(shù)量的改變，這些數(shù)據(jù)完全可能發(fā)生變化。 因此有必要來分析一下當這些數(shù)據(jù)發(fā)生波動時，對目前的最優(yōu)解，最優(yōu)值或者最優(yōu)基會產(chǎn)生什么影響，這就是所謂的靈敏度分析。 42靈敏度分析主要討論如下二類問題：數(shù)據(jù)集合在什么范圍內波動將不影響最優(yōu)解或最優(yōu)基？若最優(yōu)解發(fā)生變化，應如何找到新的最優(yōu)解。CC1 C2 Cn CB XB b x1 x2 xn CB1 XB1 B-1b B-1A=B-1(P1，P2，Pn) CB2 XB2 : : CBm XBm C-CBTB-1A 列出標準型線性規(guī)劃問題最優(yōu)單純形表：43價值向量C的改變當價值向量由 時，

19、檢驗行應修改為：目標函數(shù)值應為 。 只要非基變量檢驗數(shù)那么原最優(yōu)解仍然為最優(yōu)。至于目標函數(shù)值是否改變，取決于分別就價值系數(shù)對應非基變量或基變量加以討論：44若是非基變量的價值系數(shù)，為其改變量，在最優(yōu)表中檢驗數(shù) 發(fā)生變化。若超出范圍，那么 ，當前解已不是最優(yōu)解。此時以修改后的最優(yōu)單純形表出發(fā)，進行單純形迭代，直至求出新的最優(yōu)解。 由 只要 即就可以保持現(xiàn)行最優(yōu)解仍為最優(yōu)。 45若是某基變量的價值系數(shù)，為改變量，在最優(yōu)表中所有的非基變量檢驗數(shù)均發(fā)生了變化.由上式可得到一個不等式組，求解該不等式組就可得到價值系數(shù) 的可變動范圍。由，只要檢驗數(shù)： 或則最優(yōu)解仍然保持為最優(yōu).46例7、某工廠用甲乙兩種原

20、料生產(chǎn)A，B，C，D四種產(chǎn)品，每種產(chǎn)品的利潤，現(xiàn)有原料數(shù)及每種產(chǎn)品消耗原料定額如表所示：原料（公斤）產(chǎn)品（萬件）供應量A B C D甲乙3 2 10 40 0 2 1/2183利潤（萬元/萬件）9 8 50 19問應該怎樣組織生產(chǎn)，才能使總利潤最大，若產(chǎn)品或的利潤產(chǎn)生波動，波動范圍多大時，原最優(yōu)解保持不變？解：設生產(chǎn)，四種產(chǎn)品各萬件，則此問題的線性規(guī)劃模型為：47標準化，引入松弛變量x5,x6， 利用單純形表求解： 4 2/3 0 0 13/3 10/3 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/321x4x3-19-50 0 -2 0 -2 3 102

21、6 1 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/213/2x1x3-9-50 -9 -8 0 -13/2 0 251- 3 2 0 3/2 1 -5 0 0 1 1/4 0 1/233/2x5x30-50 -9 -8 -50 -19 0 09/53/2 3 2 10 4 1 0 0 0 2 1/2 0 1183x5x600 x1 x2 x3 x4 x5 x6bXBCB -9 -8 -50 -19 0 0C即最優(yōu)生產(chǎn)方案是生產(chǎn)產(chǎn)品1萬件，產(chǎn)品2萬件，不生產(chǎn),兩種產(chǎn)品?？傻米畲罄麧櫈?8萬元。 48C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x

22、5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最優(yōu)表：原最優(yōu)解不變，最優(yōu)利潤值（萬元）也不變。(1)若 有改變量。因為為非基變量，由推得即 或時49C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最優(yōu)表：()若 有改變量。因為為基變量，由推得即當或時原最優(yōu)解不變，最優(yōu)利潤值 萬元50右端

23、項向量b的改變當右端項向量時，改變的是表中右端常數(shù)列。此時基變量，目標函數(shù)值。而檢驗行的檢驗向量保持不變。若，可用對偶單純形法再次進行迭代，直到求得新最優(yōu)解。為了使B可行，只要或51例8、在例7中，若想增加甲種原料，問增加多少時原最優(yōu)基不變？ 解：設甲種原料的改變量為 ,則由 即 最優(yōu)目標函數(shù)值 (萬元)由此可以推得， 即當 時，原最優(yōu)基不變。此時最優(yōu)解 或52約束矩陣A的改變 假設原線性規(guī)劃問題有一個最優(yōu)解其中為最優(yōu)基，約束矩陣A的改變可能導致不同的最優(yōu)解和最優(yōu)基.以下只涉及兩種較簡單的情形：增加一個變量，增加一個約束條件。53 增加一個變量增加一個新變量，對應的價值系數(shù)為，對應的系數(shù)列向量

24、為，可得新的線性規(guī)劃問題：設，則 為新問題的一個可行解。因此可在此基礎上開始單純形法，求新的最優(yōu)解。如果 ，則， 是新問題的最優(yōu)解。否則以為換入變量進行基變換，繼續(xù)使用單純形算法為新的線性規(guī)劃尋求一個最優(yōu)解。54增加一個約束如果加入一個新的約束條件，不妨假設此約束條件為不等式形式，即在附加不等式約束左端加上一個松弛變量 ,新的線性規(guī)劃變成 55由此可以在原來最優(yōu)基的基礎上定義一個新的基, 是非奇異矩陣，得到新問題的一個基本解 在原最優(yōu)解基礎上對新問題作初等行變換，使基變量對應的系數(shù)列向量為單位矩陣，該基本解不一定是可行解，但是由于是原線性規(guī)劃問題的最優(yōu)基，所以能保證該線性規(guī)劃的對偶規(guī)劃是可行的。56結論：如果由新基定義的基本解是非負的。那么該基本解就是有附加約束條件的新線性規(guī)劃問題的最優(yōu)解。不滿足非負條件。那么至少有一個基變量小于零，此時可用對偶單純形法求出新問題的最優(yōu)解。57解：（1）設生產(chǎn)產(chǎn)品x7萬件，1萬件E產(chǎn)品的利潤為c7萬元，則數(shù)學模型變?yōu)椋豪?、在例7中，若考慮生產(chǎn)另一種產(chǎn)品，已知每生產(chǎn)1萬件產(chǎn)品要消耗甲原料3公斤，乙原料1公斤，那么，產(chǎn)品的每萬件利潤為多少時才有利于該種產(chǎn)品投產(chǎn)？若假設該工廠又增加了用電量不超過9千瓦的限制，已知生產(chǎn)，四種產(chǎn)品各1萬件分別耗電4，3，5，2千瓦，問此約束是否改變了原最優(yōu)決策方案？58已知 是原問題的最優(yōu)解，若令，則是現(xiàn)問題的一