運籌學(xué)-第二章--對偶理論與靈敏度分析課件

1、運籌學(xué)第二章 對偶理論與靈敏度分析學(xué)習(xí)目標(biāo)對偶問題對偶定理對偶單純形法靈敏度分析3開篇案例某工廠在計劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺時及A、B兩種原材料的消耗，該工廠每生產(chǎn)一件產(chǎn)品甲可獲利2元，每生產(chǎn)一件產(chǎn)品乙可獲利3元。假設(shè)該工廠決定不再生產(chǎn)甲、乙產(chǎn)品，而將其出租或出售，這時該如何考慮每種資源的定價？45 設(shè) 分別為出租單位設(shè)備臺時的租金和出讓單位原材料A、B的附加額。試考慮，若用一個單位臺時和4個單位原材料A生產(chǎn)一件產(chǎn)品甲，可獲利2元，那么生產(chǎn)每件產(chǎn)品甲的設(shè)備臺時和原材料出租和出讓的收入應(yīng)不低于生產(chǎn)一件甲產(chǎn)品的利潤，即 。同理，將生產(chǎn)每件乙產(chǎn)品的設(shè)備臺時和原材

2、料出租和出讓的收入應(yīng)不低于生產(chǎn)一件乙產(chǎn)品的利潤，即 。將工廠所有設(shè)備臺時和資源都出租和出讓，其收入為 。對工廠來說， 越大越好，但對接受者來說，支付的愈少愈好，所以工廠只能在滿足大于等于所有產(chǎn)品的利潤前提下，使其總收入盡可能小，才能實現(xiàn)其愿望。為此，得到如下模型：通過該模型的求解，即可得到工廠出租和出讓3種資源的收入不低于生產(chǎn)產(chǎn)品的定價策略。 2.1 線性規(guī)劃問題的對偶及其變換 對偶理論是線性規(guī)劃中的重要內(nèi)容之一，每個線性規(guī)劃問題都伴隨一個與之相對應(yīng)的線性規(guī)劃問題，一個問題稱為原問題，則另一個則稱為其對偶問題。原問題與對偶問題有著非常密切的關(guān)系，對偶理論深刻地揭示了原問題和對偶問題的內(nèi)在聯(lián)系，

3、為進一步深入研究線性規(guī)劃理論提供了依據(jù)。62.1.1 對偶問題的提出例2-1 已知資料如表2-1所示，問怎樣安排生產(chǎn)計劃使得既能充分利用現(xiàn)有資源又使得總利潤最大？7根據(jù)線性規(guī)劃理論，可假設(shè)甲、乙兩種產(chǎn)品的產(chǎn)量分別為x1、x2件，使得總利潤最大 8 如果從另一個角度來討論這個問題，現(xiàn)假設(shè)：該廠的決策者不是考慮自己生產(chǎn)甲、乙兩種產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來加工任務(wù)，只收取加工費。試問該決策者應(yīng)如何制定合理的收費標(biāo)準(zhǔn)（接受外來加工任務(wù)利潤至少不比生產(chǎn)產(chǎn)品獲利少）？ 這個問題可以從兩個方面來思考：（1）要求每種資源收回的費用不能低于自己生產(chǎn)時的可獲利潤；（2）定價又不能太高，因為要使對方能夠

4、接受。9 假設(shè)y1,y2,y3分別為三種資源的收費定價，每種資源收回的費用不能低于自己生產(chǎn)時的可獲利潤，所以有 1011從承租方來看，是使租金 ，最少，則對承租方應(yīng)有如下模型：對以上模型進行求解，得出的結(jié)果就是租賃雙方?jīng)Q策者認(rèn)為的最優(yōu)方案。12把生產(chǎn)模型（原問題）與租賃模型（對偶問題）進行對比： 站在生產(chǎn)者的立場上建立起來的數(shù)學(xué)模型同站在承租方立場上所建立的數(shù)學(xué)模型加以對比，可以發(fā)現(xiàn)它們的參數(shù)是一一對應(yīng)的。即建立后一個模型并不需要在前一個模型的基礎(chǔ)上增加任何補充信息。亦即后一個線性規(guī)劃問題是前一個線性規(guī)劃問題從相反角度所作的闡述；如果前者稱為線性規(guī)劃的原問題，那么后者就稱為其對偶問題。 132

5、.1.2 對偶問題的一般形式線性規(guī)劃原問題的標(biāo)準(zhǔn)形式為：1415用 代表第i種資源的估價，則其對偶問題的形式為:用矩陣形式表示，對稱形式的線形規(guī)劃問題的原問題為：其對偶問題為： 16 如果將目標(biāo)函數(shù)求極大值、約束條件取小于等于號、決策變量非負(fù)的線性規(guī)劃問題稱為對稱形式的原問題。 對稱形式的原問題與其對偶問題的對應(yīng)關(guān)系可概括為：1若原問題目標(biāo)函數(shù)求極大值，那么對偶問題目標(biāo)函數(shù)求極小值；2原問題決策變量的數(shù)目等于對偶問題約束條件的數(shù)目；173原問題約束條件的數(shù)目等于對偶問題決策變量的數(shù)目；4原問題的價值系數(shù) 成為對偶問題的資源系數(shù) ；5原問題的資源系數(shù) 成為對偶問題的價值系數(shù) ；6原問題的技術(shù)系數(shù)

6、矩陣與對偶問題的技術(shù)系數(shù)矩陣互為轉(zhuǎn)置；7原問題約束條件為“” ，對偶問題約束條件為“” ；8原問題決策變量大于等于零，對偶問題決策變量大于等于零。 18 一般地（1）如果原問題是MAX問題，則其對偶問題是MIN問題，按下表可將其對偶問題寫出。1920（2）如果原問題是MIN問題，則其對偶問題是MAX問題，按下表可將其對偶問題寫出。 2122例2-2 寫出下列線性規(guī)劃問題的對偶問題 23解：其對偶問題為 2425例2-3 寫出下列線性規(guī)劃問題的對偶問題26解：其對偶問題為： 2.2 線性規(guī)劃對偶問題的基本性質(zhì) 假定原問題為：27性質(zhì)1(對稱性) 對偶問題的對偶問題是原問題 證明：設(shè)原問題為對偶問

7、題為對偶問題的對偶問題為比較模型(2-7)和式(2-9), 顯然二者是等價的, 命題得證。2829證明：根據(jù)模型(2-7), 由于 ,又由于 ,從而必有：根據(jù)模型(2-8), 由于 ，又由于 ，從而必有結(jié)合式(2-11)和式(2-12), 立即可得 ，命題得證性質(zhì)2(弱對偶性) 設(shè)原問題為模型(2-7)，對偶問題為模型(2-8), 是原問題的任意一個可行解, 是對偶問題的任意一個可行解,那么總有30性質(zhì)3(最優(yōu)性)：設(shè) 原問題模型(2-7)的可行解, 是對偶問題題模型(2-8)的可行解,當(dāng)是 時， 是原問題模型(2-7)的最優(yōu)解， 是對偶問題模型(2-8)的最優(yōu)解。證明:設(shè) 是模型(2-7)的

8、最優(yōu)解, 那么有由于 ，那么根據(jù)弱對偶性質(zhì)，又有從而 ，也就是 是原問題模型(2-7)的最優(yōu)解。同理可證明 是對偶問題模型(2-8)的最優(yōu)解。31 性質(zhì)4(無界性) 設(shè)原問題為無界解，則對偶問題無解證明：用反證法證明。設(shè)原問題為模型(2-7)，對偶問題為模型(2-8)。假定對偶問題有解，那么存在一個可行解為 ，這時對偶問題的目標(biāo)函數(shù)值為 。由于原問題為無界解，那么一定存在一個可行解 滿足 ，因此 。而根據(jù)弱對偶性，又有 ，發(fā)生矛盾。從而對偶問題沒有可行解。32證明：設(shè)B為原問題模型(2-7)的最優(yōu)基，那么當(dāng)基為B時的檢驗數(shù)為 ，其中 為由基變量的價值系數(shù)組成的價值向量。既然B為原問題模型(2-

9、7)的最優(yōu)基，那么有 。令： ，那么有 ，從而 是對偶問題模型(2-8)的可行解。 這樣一來， 是對偶問題的可行解， 是原問題的最優(yōu)基可行解。由于 ，而 ，從而有 。根據(jù)性質(zhì)（3），命題得證性質(zhì)5(強對偶性、對偶性定理) 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值相等33證明：設(shè)原問題和對偶問題的標(biāo)準(zhǔn)型是原問題對偶問題將原問題目標(biāo)函數(shù)中的系數(shù)向量C用 代替后，得到：將對偶問題的目標(biāo)函數(shù)中系數(shù)列向量，用 代替得到：若 則 ，由最優(yōu)性可知 分別是原問題和對偶問題的最優(yōu)解性質(zhì)6(對偶松弛定理、松弛性) 若 分別是原問題和對偶問題的可行解，那么 和 ，當(dāng)且僅當(dāng) 為最優(yōu)解34又若 分別是

10、原問題和對偶問題的可行解，再根據(jù)最優(yōu)性，則有由式(2-16)和(2-17)，必有2.3 對偶單純形法2.3.1對偶單純形法的基本思路前面介紹的單純形法可以解決一切線性規(guī)劃問題，但它對于某些特殊問題，雖然也可解決，但計算量較大。對偶單純形法是根據(jù)對偶原理和單純形法的原理而設(shè)計出來求解線性規(guī)劃問題的一種方法（而不能簡單的將它理解為是求解對偶問題的方法）。 35例如線性規(guī)劃問題3637在約束方程中出現(xiàn)了一個負(fù)單位矩陣，若將剩余變量 取作初始基變量，則初始基 ，初始解 不滿足可行性，因此不能將 取作初始基，為了求得初始基本可行解，需在約束方程左邊增加一組人工變量，通過大M法或兩階段法進行計算，這就顯得

11、很不方便，且 也沒能利用上?？疾煲话愕臉?biāo)準(zhǔn)形式的線性規(guī)劃問題及其對偶問題：38設(shè)B為原問題(P)的一個基，不妨設(shè)則 為原問題的（P）的一個基本解；且當(dāng)時，則 為一個基可行解，B為可行基；進一步若檢驗數(shù)滿足則 為原問題（P）的一個最優(yōu)解，這時B稱為最優(yōu)基。 以上概念都是對原問題（P）而言的，因此，我們更將條件(2-19)稱為可行性條件；條件(2-20)稱為最優(yōu)性條件。3940原始單純形法的基本思路是：從滿足可行性條件(2-19)的一個基可行解出發(fā)，經(jīng)過換基運算迭代到另一個基可行解，即總是保持解的可行性不變（滿足條件(2-19)），變化的只是檢驗數(shù)向量 ，它從不滿足 ，逐步迭代到 成立，一旦達到

12、，也就得到了原問題的最優(yōu)解。41再從對偶的觀點來解釋這個問題，令 代入式2-20，得：即y是對偶問題（D）的一個可行解。條件(2-21)稱為對偶可行性條件，即最優(yōu)性條件(2-20)與對偶可行性條件(2-21)是等價的，因此，如果一個原始可行基B是原問題（P）的最優(yōu)基，則 就是對偶問題（D）的一個可行解，此時對應(yīng)的目標(biāo)函數(shù)值 等于原問題（P）的目標(biāo)函數(shù)值，可知 也是對偶問題（D）的最優(yōu)解。 若原問題（P）的一個基本解 對應(yīng)的檢驗數(shù)向量滿足條件(2-20)，即則稱X為（P）的一個正則解。 于是可知，原問題（P）的正則解x與對偶問題（D）的可行解y是一一對應(yīng)的，它們由同一個基B所決定，我們稱這一基為

13、正則基。42 因此，我們可以設(shè)想另一條求解思路，即在迭代過程中，始終保持對偶問題解的可行性，而原問題的解由不可行逐漸向可行性轉(zhuǎn)化，一旦原問題的解也滿足了可行性條件，也就達到了最優(yōu)解。也即在保持正則解的正則性不變條件下，在迭代過程中，使原問題解的不可行性逐步消失，一旦迭代到可行解時，即達到了最優(yōu)解。這正是對偶單純形法的思路，這個方法并不需要把原問題化為對偶問題，利用原問題與對偶問題的數(shù)據(jù)相同（只是所處位置不同）這一特點，直接在反映原問題的單純形表上進行運算。432.3.2對偶單純形法的計算步驟求解如下標(biāo)準(zhǔn)形式線性規(guī)劃問題:對偶單純形法的計算步驟：4445（1）找一個正則基B和初始正則解 ，將原問

14、題化為關(guān)于基B（不妨設(shè) ）的典式，列初始對偶單純形表，見表2-5。表2-5對偶單純形表462.若 ，則停止計算，當(dāng)前的正則解 ，即為原問題的最優(yōu)解；否則轉(zhuǎn)下一步。3.確定換出（出基）變量：令 ，（顯然 ），則取相應(yīng)的變量， 為換出（出基）變量。4.若 ，（j = 1,2, n），則停止計算，原問題無可行解。否則轉(zhuǎn)下一步。5.確定進（換入）基變量：若則取相應(yīng)的變量 為進（換入）基變量。6.以 為主元進行換基運算，得到新的正則解，轉(zhuǎn)（2）。例2-4 用對偶單純形法求解 47解：將問題化為其中 松弛變量，取初始正則基則問題已化為關(guān)于基B的典式，初始正則解為：及目標(biāo)函數(shù)值48建立對偶單純形表并進行迭代

15、見表2-5，由表2-6（）可知，因為49表2-6 對偶單純形法求解例2-4的單純形表過程50故應(yīng)取 為換出基變量，又因為 故應(yīng)取 為換入基變量，以 為主元作換基運算，得由表2-6（），又該表可知，因為故應(yīng)取 為換出基變量，又因為故應(yīng)取 為換入基變量，以 為主元作換基運算，得表2-6()，至此，基變量的取值已全部非負(fù)，檢驗已全部非正，故已求得最優(yōu)解 及相應(yīng)的目標(biāo)函數(shù)最優(yōu)值， ，原問題的目標(biāo)函數(shù)最優(yōu)值 由表2-6()還可以看出，其對偶問題的最優(yōu)解為 及目標(biāo)函數(shù)最優(yōu)值例2-5 用對偶單純形法求解 51解：將問題化為:其中 為松弛變量，取初始正則基 則問題已代為關(guān)于基B的典式，初始正則解為： 及目標(biāo)函

16、數(shù)值用對偶單純形法求解、迭代過程如表2-6。 5253表2-6續(xù)表54 由表2-6（）可知，基變量的取值已全部非負(fù)，檢驗數(shù)已全部非正，故已求得最優(yōu)解: x*=(6,2,0,0,2,0)T及原問題目標(biāo)函數(shù)最優(yōu)值Z*=20。55 從以上求解過程可以看到，對偶單純形法與原始單純形法的計算步驟類似，但又有所不同，對偶單純形法有以下優(yōu)點：（1）初始解可以是非可行解，當(dāng)檢驗數(shù)都為負(fù)數(shù)時，就可以進行基的變換，這時不需要加入人工變量，因此，可以簡化計算；（2）變量多于約束條件的線性規(guī)劃問題，用對偶單純形法計算可以減少計算工作量，因此，對變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成對偶問題，然后用對偶

17、單純形法求解。562.4 對偶問題的經(jīng)濟解釋影子價格2.4.1 影子價格的概念考慮一對對稱的對偶問題從對偶問題的基本性質(zhì)可知，當(dāng)（P）問題求得最優(yōu)解 其（D）問題也得到最優(yōu)解 ，且有57 對偶變量yi*的意義代表在資源最優(yōu)利用條件下對單位第i種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而得到的估價，稱之為影子價格。 資源的影子價格有賴于資源的利用情況，不同企業(yè)，即使是相同的資源，其影子價格也不一定相同，就是同一個企業(yè)，由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。5859在(2-22)式中對z求 的偏導(dǎo)數(shù)，得 ，這說明 的值相當(dāng)于在資源得到最優(yōu)

18、利用的生產(chǎn)條件下， 每增加一個單位時目標(biāo)函數(shù)z的增量，所以，影子價格是一種邊際價格。例2.6 某企業(yè)產(chǎn)品的單位產(chǎn)值，對三種資源的單位消耗及資源的現(xiàn)有數(shù)量如表2-7，經(jīng)理對其生產(chǎn)的甲、乙兩種產(chǎn)品，用線性規(guī)劃來確定最優(yōu)的產(chǎn)量方案。60用單純形法解這個線性規(guī)劃問題，得初始及最優(yōu)單純形表（表2-8）。 61 求解結(jié)果說明最優(yōu)生產(chǎn)方案為甲產(chǎn)品生產(chǎn)35件，乙產(chǎn)品生產(chǎn)10件，總產(chǎn)值達到最大為215。 同時在最優(yōu)單純形表中，得到對偶解，即影子價格：資源A的影子價格y1=0；資源B的影子價格y2=1；資源C的影子價格y3=3。 資源A的影子價格為零，說明增加這種資源不會增加總的產(chǎn)值，如在表2-8的初始表中的90

19、改為91，則最優(yōu)單純形表為表2-9，這說明資源A的增加不改變產(chǎn)品生產(chǎn)方案，也不增加總的產(chǎn)值。 6263如果資源C增加一個單位從45改為46，最優(yōu)單純形表為表2-10。64 這說明增加一個單位的資源C以后，最優(yōu)生產(chǎn)方案為甲產(chǎn)品生產(chǎn)34件，乙產(chǎn)品生產(chǎn)12件，總產(chǎn)值由原來215件增加到218，增加了3個單位，即為該資源的影子價格格或邊際價格。6566由對偶問題的互補松弛定理中有 時， ；當(dāng) 時，有 ，這表明生產(chǎn)過程中，如果某種資源， 未得到充分利用時，該種資源的影子價格為零；又當(dāng)資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。 2.4.2 影子價格在企業(yè)經(jīng)營管理中的應(yīng)用 影子價格在企業(yè)經(jīng)營管

20、理中的用處很多，可從以下方面來理解。1影子價格說明增加哪一種資源對增加經(jīng)濟效益最有利。如例2.6中的三種資源的影子價格為（0,1,3），說明首先應(yīng)考慮增加資源C，因為相比之下它能給收益帶來的增加最大。2. 影子價格又是一種機會成本，企業(yè)經(jīng)營決策者可以把本企業(yè)資源的影子價格與當(dāng)時的市場價格進行比較，當(dāng)年i種資源的影子價格高于市場價格時，則企業(yè)可以買進該種資源；而當(dāng)某種資源的67影子價格低于市場價格時（特別是當(dāng)影子價格為零時），則企業(yè)可以賣出該種資源，以獲得較大的利潤。682.5 線性規(guī)劃的靈敏度分析 在前面討論線性規(guī)劃問題時，總是假定aij,bi,cj都是常數(shù)，但在實際問題中，這些數(shù)據(jù)往往是估計

21、值或預(yù)測值，因此會有一定的誤差。而且隨著情況的變化，這些數(shù)據(jù)也會經(jīng)常發(fā)生改變。例如，市場行情的變化會引起價值系數(shù)cj的變化；工藝條件的改變會引起消耗系數(shù)aij的變化；資源數(shù)量bi也會視經(jīng)濟效益而進行調(diào)整；增加新產(chǎn)品會引起決策變量的增加；增加新的資源限制會引起約束條件的增加等等。因此很自然會提出這樣的問題，當(dāng)這些參數(shù)中的一個或幾個發(fā)生變化時，問題的最優(yōu)解會有什69么變化，或者這些參數(shù)在一個多大范圍內(nèi)變化時，問題的最優(yōu)基不變。這就是靈敏度分析所需研究解決的問題。 靈敏度分析就是分析、研究線性規(guī)劃模型參數(shù)aij,bi,cj 的取值變化時，最優(yōu)解或最優(yōu)基的影響，它在應(yīng)用線性規(guī)劃解決實際問題的過程中是非

22、常有用的。 當(dāng)然，當(dāng)線性規(guī)劃問題中的一個或幾個參數(shù)變化時，可以用單純形法重新計算，確定最優(yōu)解有無變化，但這樣做既麻煩又沒有必要。由單純形法的70迭代過程知，只需在最終單純形表中，看這些數(shù)據(jù)變化后，是否仍滿足可行性、最優(yōu)性的條件，如果不滿足的話，再從該表開始進行迭代計算，使之可行并求得最優(yōu)解。同樣，討論在保持現(xiàn)有最優(yōu)基不變，找出這些數(shù)據(jù)變化的范圍，即所謂數(shù)據(jù)的穩(wěn)定區(qū)間，也可通過最終單純形表中對可行性條件 和最優(yōu)性條件 的討論得到。712.5.1 目標(biāo)函數(shù)中價值系數(shù)cj的變化分析 目標(biāo)函數(shù)中價值系數(shù)cj的變化會引起 的變化，從而影響最優(yōu)性條件能否成立，可以分別就cj是對應(yīng)的非基變量和基變量兩種情況

23、來討論。72731.若 是非基變量 的系數(shù)，則 改變?yōu)?，時，則變化后的檢驗數(shù)為： 要保持原最優(yōu)基不變，必須滿足由此可以確定 的變化范圍了。當(dāng)超出這個范圍時，原最優(yōu)基將不再是最優(yōu)解了。為了求新的最優(yōu)解，可在原最優(yōu)單純形表的基礎(chǔ)上，繼續(xù)往下迭代，以求得新的最優(yōu)解。2.若 是基變量 的系數(shù)，則 改變?yōu)?將影響到所有非基變量的檢驗數(shù)，這時其中 是矩陣 的第r行，于是變化后的檢驗數(shù)為：74要求原最優(yōu)基不變，則必須滿足于是得到：當(dāng) 時，有 ；當(dāng) 時，有 ，因此 允許變化范圍是例2-7 已知線性規(guī)劃的標(biāo)準(zhǔn)形式為 其最優(yōu)單純形表如下 75問：(1)當(dāng)C1由1變?yōu)?時，求新問題的最優(yōu)解 (2)討論C2在什么范

24、圍內(nèi)變化時，原有的最優(yōu)解仍是最優(yōu)解 7677解：由表可知，C1是非基變量的價值系數(shù)，因此C1的改變只影響1：見最優(yōu)性準(zhǔn)則已不滿足，繼續(xù)迭代7879要使原最優(yōu)解仍為最優(yōu)解，只要在新的條件下滿足0成立，因為x2是基變量，所以所有的檢驗數(shù)值都將發(fā)生變化即 ，則 c2+c21 c2-1所以當(dāng) 的系數(shù)c2-1時，原最優(yōu)解仍能保持為最優(yōu)解。的系數(shù)c2-1時，原最優(yōu)解仍能保持為最優(yōu)解。2.5.2 約束條件中資源數(shù)量bi的變化分析80由于 ， ，所以資源數(shù)量 變化為 ，并假設(shè)原問題的其它系數(shù)不變，則使最終單純形表中原問題的解相應(yīng)地變化為：其中這時81其中 為 中的第r列，若要求最優(yōu)基B不變，則必須 ，即由此可

25、導(dǎo)出：當(dāng) 時，有 當(dāng) 時，有因此 的允許變化范圍是：當(dāng)b改變?yōu)?以后，若解的可行性不變，則目標(biāo)函數(shù)變?yōu)槔?-8 已知線性規(guī)劃問題及其最優(yōu)單純形表 8283若右端列向量解：因為1小于0，因此繼續(xù)迭代 84根據(jù)對偶單純形法，計算得到85所以新問題的最優(yōu)解為X*=(0,0,3/2,0,7/2,3/2) ，Z*=6。862.5.3 增加一個變量xj的分析87增加一個變量在實際問題中反映為增加一種新的產(chǎn)品。若增加一個新的變量 ，它對應(yīng)的價值系數(shù)為 ，在約束系數(shù)矩陣中的對應(yīng)列向量 ，則把 看成非基變量，在原來的最優(yōu)單純形表中增加一列 及檢驗數(shù)就得到了新問題的單純形表，若 ，則原問題最優(yōu)解不變；若 ，則按單

26、純形法繼續(xù)迭代計算找出最優(yōu)。例2-9 已知線性規(guī)劃問題及其最優(yōu)單純形表 88現(xiàn)增加一個新變量x7，且c7=3，p7 =(3,1,-3) T，求新問題的最優(yōu)解 8990解：由表知：所以所以繼續(xù)迭代所以，得到最優(yōu)解 X*=(0,0,13/3,0,56/9,0,1/9) T，Z*=53/3 。912.5.4 約束條件中技術(shù)系數(shù)aij的變化92根據(jù)變動的系數(shù) 處于矩陣A中的哪一列又可分為兩種情況來考慮。1非基變量 的系數(shù)列向量 的變化分析 對于最優(yōu)基B而言，非基變量 的系數(shù)列向量 改變?yōu)?，則變化后的檢驗數(shù)為：其中 為原問題的對偶可行解，要使原最優(yōu)基B保持不變，則必須 ，即2基變量 的系數(shù)列向量 的變

27、化分析。對于最優(yōu)基B而言，當(dāng)基變量 的系數(shù)列向量 發(fā)生變化時，將使相應(yīng)的B、 都發(fā)生變化，因此，它不僅影響現(xiàn)行最優(yōu)解的可行性，也影響到它的最優(yōu)性。例2-10 已知線性規(guī)劃問題及其最優(yōu)單純形表 最優(yōu)單純形表如下：9394若p3由原來的 變?yōu)?，最優(yōu)解將如何變化？95解：計算所以繼續(xù)迭代所以得到最優(yōu)解X*=(3/7,0,60/7,0,0)T，Z*=66/7。962.5.5增加新的約束條件97增加一個約束工具在實際問題中相當(dāng)增添一道工序，設(shè)在原線性規(guī)劃問題中，增加一個新的約束條件。則首先把已求得的原問題的最優(yōu)解代入新增加的約束條件，如果條件滿足，則原問題的最優(yōu)解仍為新問題的最優(yōu)解，結(jié)束，如果條件不滿

28、足，則將新增加的約束條件直接添加到最終單純形表中重新求解。例2-11 已知線性規(guī)劃問題及其最優(yōu)單純形表 98現(xiàn)增加新約束 ，求新問題的最優(yōu)解。99解：將原問題的最優(yōu)解代入新增約束不滿足新增加的約束條件，因此引入松弛變量x7后，新增約束變?yōu)榧舆M最優(yōu)表得：規(guī)格化，繼續(xù)運用對偶單純形法求解 100所以得到最優(yōu)解為： X*=(5/3,0,11/3,0,4,2,0)T，Z*=13。101本章小結(jié) 對偶理論與靈敏度分析是研究線性規(guī)劃中原問題與對偶問題之間關(guān)系的理論。在線性規(guī)劃早期發(fā)展中最重要的發(fā)現(xiàn)是對偶問題，即每一個線性規(guī)劃問題有一個與它對應(yīng)的對偶線性規(guī)劃問題（稱為對偶問題）。對偶問題與原問題之間存在著多方面的對應(yīng)關(guān)系。對偶問題能提供原問題最優(yōu)解的許多重要信息，有助于對原問題的求解和分析。 102思考題1.對偶問題和對偶變量的經(jīng)濟意義是什么？2簡述對偶單純形法的計算步驟。它與單純形法的異同之處是什么？3什么是資源的影子價格？它和相應(yīng)的市場價格之間有什么區(qū)別？4如何根據(jù)原問題和對偶問題之間的對應(yīng)關(guān)系，找出兩個問題變量之間、解及檢驗數(shù)之間的關(guān)系？1035.寫出下列線性規(guī)劃的對偶問題104 (1) max z=2x1+2x24x3x1 + 3x2+ 3x3 304x1 + 2x2