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

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

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

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

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

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

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

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

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

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

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

11、種基變換，必須保持所有的檢驗(yàn)數(shù)非負(fù)，同時(shí)取消原問(wèn)題必須可行的要求，即取消常數(shù)列的非負(fù)限制，通過(guò)基變換使原問(wèn)題在非可行解的基礎(chǔ)上逐步轉(zhuǎn)換成基本可行解，一旦原問(wèn)題的基本解可行，則該基本可行解也就是最優(yōu)解，這就是對(duì)偶單純形法的基本思想。單純形法： 可行性最優(yōu)性對(duì)偶單純形法：最優(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對(duì)偶單純形法基變換的次序和一般單純形法不同：一般單純形法首先由最大減少原則確定換入變量，然而用最小比值原則確定換出變量 。對(duì)偶單純形法則是先將具有負(fù)分量的基變量 取出，作為換出變量，然后確定某個(gè)非基變量作為換入變量。其變換目的是在保持對(duì)偶問(wèn)題可行性的前提下，使原問(wèn)題的基本解向可行解靠攏。33對(duì)偶單純形法的計(jì)算步驟如下：（4）以 為主元進(jìn)

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

14、 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50顯然，p4、p5可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p4、p5構(gòu)成的就是初始正則基。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最后一個(gè)單純形表中，已得到一個(gè)可行的正則解，因而得到問(wèn)題的最優(yōu)解為 X*=（0，4，1）T最優(yōu)值為z*=14（1）對(duì)于形如min z=CX，AXb，X0，且C0的線性規(guī)劃問(wèn)題。因?yàn)閷⑵涓膶?xiě)為max (z) =CX，AX+XS=b，X0，則立即可以得到初始正則解； （2）在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法，可使問(wèn)題的處理簡(jiǎn)化。對(duì)偶單純形法在以下情況下較為方便。37例7 用對(duì)偶單純形法求解解：先化為標(biāo)準(zhǔn)型 對(duì)偶單純形允許約束方程右端為負(fù)，因此可將方程2，3兩端同乘-1，可得含單位矩陣的標(biāo)準(zhǔn)型：38據(jù)此列出初始單純形表，并施行對(duì)偶單純形法迭代

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 用對(duì)偶單純形法求解下列線性規(guī)劃 min z=x1+2x2x1 +x2 42x1 +3 x218x1、x20解 將問(wèn)題改寫(xiě)成如下形式 min z=x1+

17、2x2x1 +x2 + x3 =42x13x2 + x4 =18x1、x2，x3，x40顯然，p3、p4可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p3、p4構(gòu)成的就是初始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ī)劃問(wèn)題所對(duì)應(yīng)的數(shù)據(jù)集合，b，常常是通過(guò)預(yù)測(cè)或估計(jì)所得到的統(tǒng)計(jì)數(shù)據(jù)

18、，在實(shí)際使用中，不免會(huì)有一定的誤差。而且隨著市場(chǎng)環(huán)境，工藝條件和資源數(shù)量的改變，這些數(shù)據(jù)完全可能發(fā)生變化。 因此有必要來(lái)分析一下當(dāng)這些數(shù)據(jù)發(fā)生波動(dòng)時(shí)，對(duì)目前的最優(yōu)解，最優(yōu)值或者最優(yōu)基會(huì)產(chǎn)生什么影響，這就是所謂的靈敏度分析。 42靈敏度分析主要討論如下二類問(wèn)題：數(shù)據(jù)集合在什么范圍內(nèi)波動(dòng)將不影響最優(yōu)解或最優(yōu)基？若最優(yōu)解發(fā)生變化，應(yīng)如何找到新的最優(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 列出標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題最優(yōu)單純形表：43價(jià)值向量C的改變當(dāng)價(jià)值向量由 時(shí)，

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

20、料生產(chǎn)A，B，C，D四種產(chǎn)品，每種產(chǎn)品的利潤(rùn)，現(xiàn)有原料數(shù)及每種產(chǎn)品消耗原料定額如表所示：原料（公斤）產(chǎn)品（萬(wàn)件）供應(yīng)量A B C D甲乙3 2 10 40 0 2 1/2183利潤(rùn)（萬(wàn)元/萬(wàn)件）9 8 50 19問(wèn)應(yīng)該怎樣組織生產(chǎn)，才能使總利潤(rùn)最大，若產(chǎn)品或的利潤(rùn)產(chǎn)生波動(dòng)，波動(dòng)范圍多大時(shí)，原最優(yōu)解保持不變？解：設(shè)生產(chǎn)，四種產(chǎn)品各萬(wàn)件，則此問(wèn)題的線性規(guī)劃模型為：47標(biāo)準(zhǔn)化，引入松弛變量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萬(wàn)件，產(chǎn)品2萬(wàn)件，不生產(chǎn),兩種產(chǎn)品。可得最大利潤(rùn)為88萬(wàn)元。 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)利潤(rùn)值（萬(wàn)元）也不變。(1)若 有改變量。因?yàn)闉榉腔兞浚赏频眉?或時(shí)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àn)闉榛兞浚赏频眉串?dāng)或時(shí)原最優(yōu)解不變，最優(yōu)利潤(rùn)值 萬(wàn)元50右端

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

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