對(duì)偶規(guī)劃與靈敏度分析

對(duì)偶規(guī)劃與靈敏度分析1第一頁，共六十頁，2022年，8月28日

對(duì)偶理論是線性規(guī)劃的重要內(nèi)容之一。對(duì)應(yīng)于每個(gè)線性規(guī)劃問題都伴生一個(gè)相應(yīng)的線性規(guī)劃問題。

原問題和對(duì)偶問題緊密關(guān)聯(lián)，它們不但有相同的數(shù)據(jù)集合，相同的最優(yōu)目標(biāo)函數(shù)值，而且在求得一個(gè)線性規(guī)劃的最優(yōu)解的同時(shí)，也同步得到對(duì)偶線性規(guī)劃的最優(yōu)解。由對(duì)偶問題引伸出來的對(duì)偶解還有著重要的經(jīng)濟(jì)意義，是研究經(jīng)濟(jì)學(xué)的重要概念和工具之一。

2第二頁，共六十頁，2022年，8月28日對(duì)偶問題的提出例1、某工廠生產(chǎn)甲,乙兩種產(chǎn)品，這兩種產(chǎn)品需要在A,B,C三種不同設(shè)備上加工。每噸甲、乙產(chǎn)品在不同設(shè)備上加工所需的臺(tái)時(shí)，它們銷售后所能獲得的利潤，以及這三種設(shè)備在計(jì)劃期內(nèi)能提供的有限臺(tái)時(shí)數(shù)均列于表。試問如何安排生產(chǎn)計(jì)劃，即甲,乙兩種產(chǎn)品各生產(chǎn)多少噸，可使該廠所獲得利潤達(dá)到最大?！?

對(duì)偶線性規(guī)劃設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤（元/噸）32303第三頁，共六十頁，2022年，8月28日

假設(shè)計(jì)劃期內(nèi)甲乙兩種產(chǎn)品各生產(chǎn)噸，設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計(jì)劃期內(nèi)甲產(chǎn)品生產(chǎn)噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤達(dá)到最大，為元。4第四頁，共六十頁，2022年，8月28日

現(xiàn)在從另一個(gè)角度來考慮該工廠的生產(chǎn)問題:假設(shè)該廠的決策者打算不再自己生產(chǎn)甲,乙產(chǎn)品，而是把各種設(shè)備的有限臺(tái)時(shí)數(shù)租讓給其他工廠使用，這時(shí)工廠的決策者應(yīng)該如何確定各種設(shè)備的租價(jià)。設(shè)分別為設(shè)備A，B，C每臺(tái)時(shí)的租價(jià)，約束條件：把設(shè)備租出去所獲得的租金不應(yīng)低于利用這些設(shè)備自行生產(chǎn)所獲得的利潤目標(biāo)函數(shù)：所獲租金總額盡量少．5第五頁，共六十頁，2022年，8月28日由此可得兩個(gè)對(duì)稱的線性規(guī)劃：6第六頁，共六十頁，2022年，8月28日矩陣形式：7第七頁，共六十頁，2022年，8月28日可以得到另一個(gè)線性規(guī)劃：稱之為原線性規(guī)劃問題的對(duì)偶問題，

對(duì)偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問題8第八頁，共六十頁，2022年，8月28日9第九頁，共六十頁，2022年，8月28日10第十頁，共六十頁，2022年，8月28日11第十一頁，共六十頁，2022年，8月28日

若令線性規(guī)劃標(biāo)準(zhǔn)型的對(duì)偶規(guī)劃為：

線性規(guī)劃問題標(biāo)準(zhǔn)型的對(duì)偶問題考慮一個(gè)標(biāo)準(zhǔn)形式的線性規(guī)劃問題由于任何一個(gè)等式約束都可以用兩個(gè)不等式約束等價(jià)地表示，所以標(biāo)準(zhǔn)形線性規(guī)劃問題可等價(jià)表示為：它的對(duì)偶規(guī)劃為：12第十二頁，共六十頁，2022年，8月28日對(duì)偶線性規(guī)劃的求法

從任何一個(gè)線性規(guī)劃出發(fā)，都可以求出相應(yīng)的對(duì)偶規(guī)劃，在實(shí)際求解過程中，通常不通過求標(biāo)準(zhǔn)型，而是利用如下反映原始問題與對(duì)偶問題對(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ì)偶問題（或原問題）原問題（或?qū)ε紗栴}）13第十三頁，共六十頁，2022年，8月28日解：對(duì)偶規(guī)劃：例2寫出下列線性規(guī)劃的對(duì)偶問題14第十四頁，共六十頁，2022年，8月28日例3寫出下列線性規(guī)劃的對(duì)偶問題解：上述問題的對(duì)偶規(guī)劃：15第十五頁，共六十頁，2022年，8月28日

本節(jié)討論幾條重要的對(duì)偶定理，這些定理揭示了原始問題的解和對(duì)偶問題的解之間的基本關(guān)系。定理1：（對(duì)合性）對(duì)偶問題的對(duì)偶是原問題。證明：設(shè)原問題為對(duì)偶問題為改寫對(duì)偶問題為對(duì)偶問題的對(duì)偶為§2

對(duì)偶定理16第十六頁，共六十頁，2022年，8月28日

定理2：弱對(duì)偶定理

若是原（極小化）問題的可行解，是對(duì)偶（極大化）問題的可行解，那么

證明：因?yàn)槭菍?duì)偶問題的可行解，所以滿足約束條件又因?yàn)槭窃瓎栴}的可行解，可得，,所以。注：原（極小化）問題的最優(yōu)目標(biāo)函數(shù)值以對(duì)偶問題任一可行解的目標(biāo)函數(shù)值為下界。對(duì)偶（極大化）問題的最優(yōu)目標(biāo)函數(shù)值以原問題任一可行解的目標(biāo)函數(shù)值為上界。

推論1：如果原問題沒有下界（即minZ→－∞），則對(duì)偶問題不可行。如果對(duì)偶問題沒有上界（即maxW→＋∞），則原問題不可行。

若原問題與對(duì)偶問題之一無界，則另一個(gè)無可行解。17第十七頁，共六十頁，2022年，8月28日證明：由弱對(duì)偶定理，對(duì)于原始問題的所有可行解，都有因此是原問題的最優(yōu)解。同理，對(duì)于對(duì)偶問題的所有可行解，都有所以是對(duì)偶問題的最優(yōu)解。推論2：最優(yōu)性定理

若是原問題的可行解，是對(duì)偶問題的可行解，而且兩者的目標(biāo)函數(shù)值相等，即，則和分別是原問題和對(duì)偶問題的最優(yōu)解。18第十八頁，共六十頁，2022年，8月28日證明：設(shè)是原問題(min)的最優(yōu)解，則對(duì)應(yīng)的基Ｂ必有。若定義，則，

因此為對(duì)偶問題的可行解，而且，由最優(yōu)性定理，是對(duì)偶問題的最優(yōu)解。

定理3:

強(qiáng)對(duì)偶定理如果原問題（min)與對(duì)偶問題(max)之一有最優(yōu)解，那么另一個(gè)也有最優(yōu)解，而且目標(biāo)函數(shù)值相等。19第十九頁，共六十頁，2022年，8月28日證明：設(shè)滿足原問題(min)的最優(yōu)性條件，則對(duì)應(yīng)的基Ｂ必有。若定義，則，

因此為對(duì)偶問題的基本可行解。

定理4：設(shè)滿足原問題(min)的最優(yōu)性條件的一個(gè)基本解，則其對(duì)應(yīng)的線性規(guī)劃問題(min)的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)基本可行解。20第二十頁，共六十頁，2022年，8月28日原問題與對(duì)偶問題可能出現(xiàn)的情況（1）兩者都有最優(yōu)解，且最優(yōu)值相等；（2）一個(gè)有可行解，但無界，則另一個(gè)無可行解；（3）兩者都無可行解。21第二十一頁，共六十頁，2022年，8月28日定理5：互補(bǔ)松弛定理

如果分別是原問題(min)和對(duì)偶問題（max)的可行解，那么和為最優(yōu)解的充要條件是

通常稱為互補(bǔ)松弛條件。證明：充分性必要性22第二十二頁，共六十頁，2022年，8月28日例5、已知線性規(guī)劃問題:其對(duì)偶問題的最優(yōu)解。試用互補(bǔ)松弛定理找出原問題的最優(yōu)解。解：原問題的對(duì)偶問題為：由對(duì)偶問題最優(yōu)解可知，由互補(bǔ)松弛定理，解方程組所以原問題最優(yōu)解23第二十三頁，共六十頁，2022年，8月28日

假設(shè)計(jì)劃期內(nèi)甲乙兩種產(chǎn)品各生產(chǎn)噸，設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計(jì)劃期內(nèi)甲產(chǎn)品生產(chǎn)噸，乙產(chǎn)品生產(chǎn)8噸，可以使總利潤達(dá)到最大，為元。例１：對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋—影子價(jià)格

24第二十四頁，共六十頁，2022年，8月28日25第二十五頁，共六十頁，2022年，8月28日

由強(qiáng)對(duì)偶定理可知，如果原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，而且它們的目標(biāo)函數(shù)值相等，即有：其中是線性規(guī)劃原問題約束條件的右端數(shù)據(jù)向量，它代表各種資源的擁有量。為對(duì)偶問題最優(yōu)解，它代表在資源最優(yōu)利用條件下對(duì)各種單位資源的估價(jià)，這種估計(jì)不是資源的市場價(jià)格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻(xiàn)（如創(chuàng)造利潤，產(chǎn)值等）而作出估價(jià)，為區(qū)別起見，稱之為影子價(jià)格(shadowprice)。26第二十六頁，共六十頁，2022年，8月28日

影子價(jià)格的大小客觀地反映了各種不同資源在系統(tǒng)內(nèi)的稀缺程度。如果第i種資源供大于求，即在達(dá)到最優(yōu)解時(shí)，該種資源沒有用完，或松弛變量，由互補(bǔ)松弛定理，在對(duì)偶最優(yōu)解中，第i種資源的影子價(jià)格。反之如果第i種資源的影子價(jià)格，那么由互補(bǔ)松弛定理，原問題的第i個(gè)約束為嚴(yán)格等式，即，這表明第i種資源已經(jīng)用完，成為稀缺資源。

資源的影子價(jià)格同時(shí)也是一種機(jī)會(huì)成本，在市場經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)這種資源用于擴(kuò)大生產(chǎn)；相反當(dāng)某種資源的市場價(jià)格高于影子價(jià)格時(shí)，企業(yè)應(yīng)賣出這種資源。隨著資源的買進(jìn)賣出，企業(yè)資源的影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。

27第二十七頁，共六十頁，2022年，8月28日設(shè)備每噸產(chǎn)品的加工臺(tái)時(shí)可供臺(tái)時(shí)數(shù)甲乙ABC359448364076利潤（元/噸）3230例１：對(duì)偶最優(yōu)解其中為設(shè)備A的影子價(jià)格，在資源最優(yōu)利用的條件下，設(shè)備A每增加一個(gè)單位臺(tái)時(shí)，可以使總利潤增加元。若設(shè)備Ａ可供臺(tái)時(shí)數(shù)＝３７，則28第二十八頁，共六十頁，2022年，8月28日§3對(duì)偶單純形法

單純形法是以保持原問題可行為條件，即不論進(jìn)行怎樣的基變換，常數(shù)列必須保持非負(fù)。利用對(duì)偶問題的對(duì)稱性，我們從另一個(gè)角度來考慮求解原問題最優(yōu)解的方法，這種方法以保持對(duì)偶問題可行為條件，即不論進(jìn)行何種基變換，必須保持所有的檢驗(yàn)數(shù)非負(fù)，同時(shí)取消原問題必須可行的要求，即取消常數(shù)列的非負(fù)限制，通過基變換使原問題在非可行解的基礎(chǔ)上逐步轉(zhuǎn)換成基本可行解，一旦原問題的基本解可行，則該基本可行解也就是最優(yōu)解，這就是對(duì)偶單純形法的基本思想。單純形法：可行性→最優(yōu)性對(duì)偶單純形法：最優(yōu)性→可行性

29第二十九頁，共六十頁，2022年，8月28日例6求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解

minz=5x1+2x2+6x32x1+4x2+8x3-x4=244x1+x2+4x3-x5=8x1、x2，x3，x4，x5≥0

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥030第三十頁，共六十頁，2022年，8月28日Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-80031第三十一頁，共六十頁，2022年，8月28日

對(duì)偶單純形法基變換的次序和一般單純形法不同：一般單純形法首先由最大減少原則確定換入變量，然而用最小比值原則確定換出變量。

對(duì)偶單純形法則是先將具有負(fù)分量的基變量取出，作為換出變量，然后確定某個(gè)非基變量作為換入變量。其變換目的是在保持對(duì)偶問題可行性的前提下，使原問題的基本解向可行解靠攏。32第三十二頁，共六十頁，2022年，8月28日對(duì)偶單純形法的計(jì)算步驟如下：（4）以為主元進(jìn)行旋轉(zhuǎn)變換，得新的單純形表，返回（2）。

（2）確定換出變量根據(jù)，確定基變量作為換出變量。檢驗(yàn)所在行各元素若所有,則無可行解，停止計(jì)算。否則轉(zhuǎn)入(３).（3）確定換入變量按最大比值原則，若確定非基變量為換入變量。（1）根據(jù)原始線性規(guī)劃，列出初始單純形表，檢查b列數(shù)字，若b列數(shù)字全部非負(fù)，則已經(jīng)求得最優(yōu)解，停止計(jì)算。若b列中至少有一個(gè)負(fù)分量，則轉(zhuǎn)入（2）.33第三十三頁，共六十頁，2022年，8月28日例6用對(duì)偶單純形法求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解將問題改寫成如下形式

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥0顯然，p4、p5可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p4、p5構(gòu)成的就是初始正則基。34第三十四頁，共六十頁，2022年，8月28日Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-800-2x21/212-1/4060x5-7/20[-2]-1/41-24021/20-120θ4/(-7/2)02/-2(1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/211/2001/40-3235第三十五頁，共六十頁，2022年，8月28日最后一個(gè)單純形表中，已得到一個(gè)可行的正則解，因而得到問題的最優(yōu)解為X*=（0，4，1）T最優(yōu)值為z*=14（1）對(duì)于形如minz=CX，AX≥b，X≥0，且C≥0的線性規(guī)劃問題。因?yàn)閷⑵涓膶憺閙ax(－z)=－CX，－AX+XS=－b，X≥0，則立即可以得到初始正則解；

（2）在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法，可使問題的處理簡化。對(duì)偶單純形法在以下情況下較為方便。36第三十六頁，共六十頁，2022年，8月28日例7用對(duì)偶單純形法求解解：先化為標(biāo)準(zhǔn)型

對(duì)偶單純形允許約束方程右端為負(fù)，因此可將方程2，3兩端同乘-1，可得含單位矩陣的標(biāo)準(zhǔn)型：37第三十七頁，共六十頁，2022年，8月28日據(jù)此列出初始單純形表，并施行對(duì)偶單純形法迭代步驟如下：5/47/4000-1/41/40102x2

2-1/4-3/40014x1

35/43/41004x3

02/30007/3-1/30011/310/3x2

21/3100-4/3-16/3x4

0101018x3

000023100-3-1-10x5

00101-1-2x4

00013218x3

0x5

x4

x3

x2

x1

bXB

CB

00023C可得最優(yōu)解38第三十八頁，共六十頁，2022年，8月28日例8用對(duì)偶單純形法求解下列線性規(guī)劃

minz=x1+2x2x1+x2

≤42x1+3x2≥18x1、x2≥0解將問題改寫成如下形式

minz=x1+2x2x1+x2+x3=4－2x1－3x2+x4=－18x1、x2，x3，x4≥0顯然，p3、p4可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p3、p4構(gòu)成的就是初始z正則基。39第三十九頁，共六十頁，2022年，8月28日§4靈敏度分析線性規(guī)劃問題所對(duì)應(yīng)的數(shù)據(jù)集合Ａ，b，Ｃ常常是通過預(yù)測或估計(jì)所得到的統(tǒng)計(jì)數(shù)據(jù)，在實(shí)際使用中，不免會(huì)有一定的誤差。而且隨著市場環(huán)境，工藝條件和資源數(shù)量的改變，這些數(shù)據(jù)完全可能發(fā)生變化。

因此有必要來分析一下當(dāng)這些數(shù)據(jù)發(fā)生波動(dòng)時(shí)，對(duì)目前的最優(yōu)解，最優(yōu)值或者最優(yōu)基會(huì)產(chǎn)生什么影響，這就是所謂的靈敏度分析。

40第四十頁，共六十頁，2022年，8月28日靈敏度分析主要討論如下二類問題：數(shù)據(jù)集合在什么范圍內(nèi)波動(dòng)將不影響最優(yōu)解或最優(yōu)基？

若最優(yōu)解發(fā)生變化，應(yīng)如何找到新的最優(yōu)解。CC1

C2

…Cn

CB

XB

bx1

x2

…xn

CB1

XB1

B-1bB-1A=B-1(P1，P2，…，Pn)CB2

XB2

::CBm

XBm

C-CBTB-1A列出標(biāo)準(zhǔn)型線性規(guī)劃問題最優(yōu)單純形表：41第四十一頁，共六十頁，2022年，8月28日價(jià)值向量C的改變

當(dāng)價(jià)值向量由時(shí)，檢驗(yàn)行應(yīng)修改為：目標(biāo)函數(shù)值應(yīng)為。只要非基變量檢驗(yàn)數(shù)那么原最優(yōu)解仍然為最優(yōu)。至于目標(biāo)函數(shù)值是否改變，取決于分別就價(jià)值系數(shù)對(duì)應(yīng)非基變量或基變量加以討論：42第四十二頁，共六十頁，2022年，8月28日若是非基變量的價(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)。

43第四十三頁，共六十頁，2022年，8月28日

若是某基變量的價(jià)值系數(shù)，為改變量，在最優(yōu)表中所有的非基變量檢驗(yàn)數(shù)均發(fā)生了變化.

由上式可得到一個(gè)不等式組，求解該不等式組就可得到價(jià)值系數(shù)的可變動(dòng)范圍。由，只要檢驗(yàn)數(shù)：

或則最優(yōu)解仍然保持為最優(yōu).

44第四十四頁，共六十頁，2022年，8月28日例7、某工廠用甲乙兩種原料生產(chǎn)A，B，C，D四種產(chǎn)品，每種產(chǎn)品的利潤，現(xiàn)有原料數(shù)及每種產(chǎn)品消耗原料定額如表所示：

原料（公斤）產(chǎn)品（萬件）供應(yīng)量ABCD甲乙321040021/2183利潤（萬元/萬件）985019問應(yīng)該怎樣組織生產(chǎn)，才能使總利潤最大，若產(chǎn)品Ａ或Ｃ的利潤產(chǎn)生波動(dòng)，波動(dòng)范圍多大時(shí)，原最優(yōu)解保持不變？解：設(shè)生產(chǎn)Ａ，Ｂ，Ｃ，Ｄ四種產(chǎn)品各萬件，則此問題的線性規(guī)劃模型為：45第四十五頁，共六十頁，2022年，8月28日標(biāo)準(zhǔn)化，引入松弛變量x5,x6，，

利用單純形表求解：42/30013/310/324/3012/3-10/3-1/2-1/310-1/64/321x4x3-19-500-20-23102612/301/21/3-5/30011/401/213/2x1x3-9-50-9-80-13/20251-3203/21-50011/401/233/2x5x30-50-9-8-50-19009/53/232104100021/201183x5x600x1x2x3x4x5x6bXBCBθ-9-8-50-1900C即最優(yōu)生產(chǎn)方案是生產(chǎn)Ｃ產(chǎn)品1萬件，Ｄ產(chǎn)品2萬件，不生產(chǎn)Ａ,Ｂ兩種產(chǎn)品?？傻米畲罄麧櫈?8萬元。46第四十六頁，共六十頁，2022年，8月28日C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最優(yōu)表：原最優(yōu)解不變，最優(yōu)利潤值（萬元）也不變。(1)若有改變量。因?yàn)闉榉腔兞?，由推得即或時(shí)47第四十七頁，共六十頁，2022年，8月28日C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最優(yōu)表：(２)若有改變量。因?yàn)闉榛兞?，由推得即?dāng)或時(shí)原最優(yōu)解不變，最優(yōu)利潤值萬元48第四十八頁，共六十頁，2022年，8月28日右端項(xiàng)向量b的改變

當(dāng)右端項(xiàng)向量時(shí)，改變的是表中右端常數(shù)列。此時(shí)基變量，目標(biāo)函數(shù)值。而檢驗(yàn)行的檢驗(yàn)向量保持不變。

若，可用對(duì)偶單純形法再次進(jìn)行迭代，直到求得新最優(yōu)解。

為了使B可行，只要或49第四十九頁，共六十頁，2022年，8月28日例8、在例7中，若想增加甲種原料，問增加多少時(shí)原最優(yōu)基不變？

解：設(shè)甲種原料的改變量為,則由即

最優(yōu)目標(biāo)函數(shù)值(萬元)由此可以推得，即當(dāng)時(shí)，原最優(yōu)基不變。此時(shí)最優(yōu)解或50第五十頁，共六十頁，2022年，8月28日約束矩陣A的改變

假設(shè)原線性規(guī)劃問題有一個(gè)最優(yōu)解其中Ｂ為最優(yōu)基，

約束矩陣A的改變可能導(dǎo)致不同的最優(yōu)解和最優(yōu)基.以下只涉及兩種較簡單的情形：

增加一個(gè)變量，

增加一個(gè)約束條件。51第五十一頁，共六十頁，2022年，8月28日

增加一個(gè)變量增加一個(gè)新變量，對(duì)應(yīng)的價(jià)值系數(shù)為，對(duì)應(yīng)的系數(shù)列向量為，可得新的線性規(guī)劃問題：設(shè)，則

為新問題的一個(gè)可行解。因此可在此基礎(chǔ)上開始單純形法，求新的最優(yōu)解。如果，則，是新問題的最優(yōu)解。否則以為換入變量進(jìn)行基變換，繼續(xù)使用單純形算法為新的線性規(guī)劃尋求一個(gè)最優(yōu)解。52第五十二頁，共六十頁，2022年，8月28日增加一個(gè)約束

如果加入一個(gè)新的約束條件，不妨假設(shè)此約束條件為不等式形式，即

在附加不等式約束左端加上一個(gè)松弛變量

,

新的線性規(guī)劃變成

53第五十三頁，共六十頁，2022年，8月28日由此可以在原來最優(yōu)基Ｂ的基礎(chǔ)上定義一個(gè)新的基,

是非奇異矩陣，得到新問題的一個(gè)基本解在原最優(yōu)解基礎(chǔ)上對(duì)新問題作初等行變換，使基變量對(duì)應(yīng)的系數(shù)列向量為單位矩陣，該基本解不一定是可行解，但是由于Ｂ是原線性規(guī)劃問題的最優(yōu)基，所以能保證該線性規(guī)劃的對(duì)偶規(guī)劃是可行的。54第五十四頁，共六十頁，2022年，8月28日結(jié)論：如果由新基定義的基本解

是非負(fù)的。那么該基本解就是有附加約束條件的新線性規(guī)劃問題的最優(yōu)解。不滿足非負(fù)條件。那么至少有一個(gè)基變量小于零，此時(shí)可用對(duì)偶單純形法求出新問題的最優(yōu)解。55第五十五頁，共六十頁，2022年，8月28日解：（1）設(shè)生產(chǎn)Ｅ產(chǎn)品x7萬件，1萬件E產(chǎn)品的利潤為c7萬元，則數(shù)學(xué)模型變?yōu)椋豪?、在例7中，若考慮生產(chǎn)另一種產(chǎn)品Ｅ，已知每生產(chǎn)1萬件Ｅ產(chǎn)品要消耗甲原料3公斤，乙原料1公斤，那么，Ｅ產(chǎn)品的每萬件利潤為多少時(shí)才有利于該種產(chǎn)品投產(chǎn)？若假設(shè)該工廠又增加了用電量不超過9千瓦的限制，已知生產(chǎn)Ａ，Ｂ，Ｃ，Ｄ四種產(chǎn)品各1萬件分別耗電4，3，5，2千瓦，問此約束是否改變了原最優(yōu)決策方案？56第五十六頁，共六十頁，2022年，8月28日

已知是