第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析教材課件

運(yùn)籌學(xué)趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院2023/12/61第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析線性規(guī)劃的對(duì)偶問(wèn)題影子價(jià)格對(duì)偶單純形法靈敏度分析2023/12/62例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況如下表所示。問(wèn)該公司應(yīng)制造Ⅰ、Ⅱ兩種家電備多少件．使獲取的利潤(rùn)為最大。設(shè)：x1——A產(chǎn)品的生產(chǎn)量

x2——B產(chǎn)品的生產(chǎn)量利潤(rùn)max

z=2x1+x2

約束條件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題2023/12/635x2

+x3=156x1+2x2+x4=24x1+x2

+

x5=5x1，x2，x3

，x4

，x5

≥0約束條件st.利潤(rùn)maxz=2x1+x2

+0x3+0x4+0x5

標(biāo)準(zhǔn)化最終單純形表C21000θCBXBbx1x2x3x4x50

0

0x3x4x515245051006201011001σ

21000最優(yōu)解X*=(7/2,3/2,15/2,0,0)Z*=17/2C21000θCBXBbx1x2x3x4x50

2

1x3x1x215/27/23/20015/4-15/210

01/4-1/2010-1/43/2σ

000-1/4-1/22023/12/645x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥0約束條件把解X=(7/2,3/2)代入原問(wèn)題(因?yàn)閤3、x4、x5為附加變量)分析5×3÷2＝15/2245A有空閑B設(shè)備已經(jīng)飽和調(diào)試工序也已經(jīng)滿(mǎn)負(fù)荷

一個(gè)問(wèn)題？

市場(chǎng)上設(shè)備A、設(shè)備B和調(diào)試工序每小時(shí)值多少錢(qián)？在什么價(jià)位時(shí)，才能使美佳公司愿意出讓自己的資源？＜＝＝2023/12/656y2+y3分析設(shè)：y1—設(shè)備A值的價(jià)值y2—設(shè)備B值的價(jià)值

y3—調(diào)試工序值的價(jià)值≥25y1+2y2+y31≥z=15y1+24y2

+5y3總價(jià)值miny1,y2,y3≥0st.2023/12/666y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.z'=-15y1-24y2-5y3maxst.6y2+y3–y4=25y1+2y2+y3–y51=y1,y2,y3,y4,y5≥0C-15-24-500-M-MθCBYBby1y2y3y4y5y6y7-M-My6y721061-10105210-101σM-158M-242M-5-M-M00問(wèn)題求解2023/12/67C-15-24-500θCBYBby1y2y3y4y5-24-5y2y31/41/2-5/410-1/41/415/2011/2-3/2

σ-15/200-7/2-3/2Y=(0,?,?,0,0)z'=-17/2z=17/22023/12/68Y=(0,?,?,0,0)問(wèn)題分析問(wèn)題的解6y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.問(wèn)題：？原問(wèn)題：利潤(rùn)max

z=2x1+x2

約束條件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.問(wèn)題的解X*=(7/2,3/2,15/2,0,0)Z*=17/2Z*=17/25*3/2=15/215＜6*7/2+2*3/2=2424=7/2+3/2=55=結(jié)論兩個(gè)問(wèn)題的最優(yōu)解的值一致最大值問(wèn)題可行解的目標(biāo)值必定不大于最小值問(wèn)題可行解的目標(biāo)值一個(gè)問(wèn)題的剩余變量（松弛變量）不為0（即有資源剩余），則對(duì)應(yīng)問(wèn)題的解為0一個(gè)決策變量不為0，則對(duì)應(yīng)的問(wèn)題的約束條件的剩余變量(松弛變量)為0(即資源徹底用完)估價(jià)——影子價(jià)格（即增加單位資源所得到的貢獻(xiàn)）Z=ω=CX=Yb

Z/

b=(Yb)

'=Y2023/12/69C21000CBXBbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/210

01/4-1/2010-1/43/2σ000-1/4-1/2-σ0001/41/2利潤(rùn)max

z=2x1+x2

約束條件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.6y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.C-15-24-500CBYBby1y2y3y4y5-24-5y2y31/41/2-5/410-1/41/415/2011/2-3/2

σ-15/200-7/2-3/2-σ15/2007/23/2Y=(0,?,?,0,0)X*=(7/2,3/2,15/2,0,0)問(wèn)題變量問(wèn)題剩余松弛變量解的關(guān)系2023/12/610一、對(duì)偶問(wèn)題對(duì)稱(chēng)形式X

≥0st.AX≤bmaxz=CX其中：C=（c1，c2,…,cn)b=（b1，b2,…,bm)TX=（x1，x2,…,xn)TY=（y1，y2,…,ym)TA=a11a12…a1na11a12…a1n

┇┇…┇am1am2

…anmY

≥0st.ATY≥CTminw=YTb利潤(rùn)max

z=2x1+x2

約束條件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.6y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.2023/12/611非對(duì)稱(chēng)形式x1≥0,x2≤

0,x3無(wú)約束st.a11x1+a12x2+a13x3

≤b1a21x1+a22x2+a23x3=b2a31x1+a32x2+a33x3≥b3maxz=c1x1+c2x2+c3x3

x1,x2',x3'，x3"

≥0st.a11x1-a12x2'+a13x3'-a13x3"

≤b1a21x1-a22x2'+a23x3'-a23x3"

≤b2-a21x1+a22x2'_a23x3'+a23x3"

≤-b2-a31x1+a32x2'-a33x3'+a33x3"

≤-b3maxz=c1x1-c2x2'+c3x3'-c3x3"

y1,y2',y2"

，y3'≥0st.a11y1+

a21y2'–a21y2"-a31y3'≥c1-a12y1-

a22y2'+a22y2"-a32y3'≥-c2a13y1+

a23y2'–a23y2"-a33y3'≥c3-a13y1-

a23y2'+a23y2"+a33y3'≥-c3minw=b1y1+b2y2'-b2y2"-b3y3'minw=b1y1+b2y2+b3y3a11y1+

a21y2+a31y3≥c1a12y1+

a22y2+a32y3≤

c2a13y1+

a23y2+a33y3

=c3st.y1≥0,y2無(wú)約束，y3≤02023/12/612二、對(duì)偶規(guī)則

原問(wèn)題有m個(gè)約束條件，對(duì)偶問(wèn)題有m個(gè)變量原問(wèn)題有n個(gè)變量，對(duì)偶問(wèn)題有n個(gè)約束條件原問(wèn)題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的右端項(xiàng)原問(wèn)題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問(wèn)題的價(jià)值系數(shù)原問(wèn)題的系數(shù)矩陣轉(zhuǎn)置后為對(duì)偶問(wèn)題系數(shù)矩陣變量、約束與系數(shù)2023/12/613變量與約束對(duì)應(yīng)關(guān)系原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）maxz=CX

AX(≤＝≥)bX(≤＝≥)0或無(wú)約束minw=Yb

ATY(≤＝≥)C

Y(≤＝≥)0或無(wú)約束有n個(gè)決策變量xj(j＝0、2……n)xj

≥0變量

xj

≤

0

xj

無(wú)約束有n個(gè)約束條件對(duì)應(yīng)的約束為≥約束對(duì)應(yīng)的約束為≤

對(duì)應(yīng)的約束為＝有m個(gè)約束條件對(duì)應(yīng)的約束為≤

約束對(duì)應(yīng)的約束為≥

對(duì)應(yīng)的約束為＝有m個(gè)決策變量yj(j＝0、2……m)yj

≥0變量

yj

≤

0

yj

無(wú)約束2023/12/614三、對(duì)偶問(wèn)題的基本性質(zhì)（對(duì)稱(chēng)形）對(duì)稱(chēng)性：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題弱對(duì)偶性：極大化原問(wèn)題的任一可行解的目標(biāo)函數(shù)值，不大于其對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值對(duì)偶定理：若一個(gè)問(wèn)題有最優(yōu)解，則另一問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問(wèn)題最優(yōu)基為B，則其對(duì)偶問(wèn)題最優(yōu)解Y*=CBB-1無(wú)界性：原問(wèn)題無(wú)界，對(duì)偶問(wèn)題無(wú)可行解需要說(shuō)明的是：這些性質(zhì)同樣適用于非對(duì)稱(chēng)形問(wèn)題2023/12/615X

≥0st.AX≤bmaxz=CXX,Xs≥0st.AX+IXs=bmaxz=CX+0XsCC0CBXBbXXs0Xsb

AIσCCBCN0CBXBbXBXNXs0Xsb

BNIσCCBCN0CBXBbXBXNXsCBXBB-1b

B-1BB-1NB-1IσCB-CBB-1B

CN-CBB-1N0-CBB-1ICCBCN0CBXBbXBXNXsCBXBB-1b

B-1BB-1NB-1Iσ

0

CN-CBB-1N-CBB-12023/12/616C21000θCBXBbx1x2x3x4x515245051006201011001σ

C21000θCBXBbx1x2x3x4x515/27/23/20015/4-15/210

01/4-1/2010-1/43/2σ

B與B-1B-1=15/4-15/201/4-1/20-1/43/2B=1050620112023/12/617第二節(jié)影子價(jià)格bi是線性規(guī)劃原問(wèn)題約束條件的右端項(xiàng)，它代表第i種資源的擁有量；對(duì)偶變量yi*的意義代表在資源最優(yōu)利用條件下對(duì)單位第i種資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)，為區(qū)別起見(jiàn)，稱(chēng)為影子價(jià)格(shadowprice)。2023/12/6181、資源的市場(chǎng)價(jià)格是其價(jià)值的客觀體現(xiàn)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴(lài)于資源的利用情況。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。2、影子價(jià)格是一種邊際價(jià)格，若對(duì)式中目標(biāo)函數(shù)z求bi的偏導(dǎo)數(shù)可得。這說(shuō)明yi*的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，bi每增加一個(gè)單位時(shí)目標(biāo)函數(shù)z的增量。2023/12/6193、資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。在完全市場(chǎng)經(jīng)濟(jì)條件下，當(dāng)?shù)?種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，可以買(mǎi)進(jìn)這種資源；相反，當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，就會(huì)賣(mài)出這種資源。隨著資源的買(mǎi)進(jìn)賣(mài)出，其影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平，才處于平衡狀態(tài)。

4、在上一節(jié)對(duì)偶問(wèn)題的互補(bǔ)松弛性質(zhì)中有時(shí)，yi=0；當(dāng)yi>0時(shí)，有，這表明生產(chǎn)過(guò)程中如果某種資源bi未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。

5、當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該產(chǎn)品有利，可在計(jì)劃中安排，否則用這些資源來(lái)生產(chǎn)別的產(chǎn)品更為有利，就不在生產(chǎn)計(jì)劃中安排。這就是單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。2023/12/6206、一般說(shuō)對(duì)線性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問(wèn)題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的好壞。又如在社會(huì)上可對(duì)一些最緊缺的資源，借助影子價(jià)格規(guī)定使用這種資源一單位時(shí)必須上繳的利潤(rùn)額，以控制一些經(jīng)濟(jì)效益低的企業(yè)自覺(jué)地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大的經(jīng)濟(jì)效益。2023/12/621第三節(jié)對(duì)偶單純形法CCBCN0CBXBbXBXBXsCBXBB-1b

B-1BB-1NB-1Iσ0

CN-CBB-1N-CBB-1對(duì)于單純形法疊代過(guò)程本質(zhì)：確保1）z變大；2）B-1b≥0由對(duì)偶理論知道，當(dāng)原問(wèn)題為最優(yōu)解時(shí)，-σ≥0且為對(duì)偶問(wèn)題的最優(yōu)解，因此人們提出對(duì)偶單純形法。疊代過(guò)程本質(zhì)：1）σ≤

0；2）逐步使B-1b≥0與2023/12/6226y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.z'=-15y1-24y2-5y3st.max6y2+y3–y4=25y1+2y2+y3–y51=y1,y2,y3,y4,y5=0問(wèn)題求解z'=-15y1-24y2-5y3+0y4

+0y5

st.max-6y2-y3+y4=-2-5y1-2y2-y3+y5-1=y1,y2,y3,y4,y5≥02023/12/6231.確定出基變量。在常數(shù)列中找一個(gè)最小的負(fù)常量，把這個(gè)常量所在行作為出基變量σ0[-6]-110

-5-2-101-2-1y1

y2

y3y4y5bYBCB-15-24-500Cy4

y50

0-15-24-5

002.確定入基變量。在系數(shù)列中找負(fù)數(shù)，把這個(gè)常量所在行作為入基變量。2023/12/624σ011/6–1/60-50-2/3–1/311/3-1/3y1y2y3y4y5bYBCB-15-24-500Cσ-5/410-1/41/415/2011/2-3/21/41/2-150-1-40y2y5-24

0-24

-5y2y3-15/200-7/2–3/22023/12/625第四節(jié)靈敏度分析靈敏度分析是指系統(tǒng)或事物對(duì)周?chē)h(huán)境變化顯示出來(lái)的敏感程度。在LP問(wèn)題中，aij、cj、bi都有可能發(fā)生變化，分析這些變化對(duì)最優(yōu)解或目標(biāo)值的影響程度就是靈敏度分析。2023/12/626cj通常表示一些估計(jì)或預(yù)測(cè)的數(shù)據(jù)，隨市場(chǎng)而變化；aij通常隨工藝技術(shù)條件的改變而改變；bi則反映了企業(yè)資源狀況。CBB-1bC

-CBB-1AB-1bB-1A原始數(shù)據(jù)A，b，CA=(P1P2…

Pn)①Z0=CBB-1bXB=B-1b②

A=C

-CBB-1A

N=CN-CBB-1N

j=Cj-CBB-1Pj

2023/12/627?b*=B-1?b

最優(yōu)解的增量?b*與初始b的增量?b

成B-1倍變化?Pj*

=B-1?Pj最優(yōu)解時(shí)的系數(shù)增量?Pj*

與初始的系數(shù)增量?Pj也成B-1倍變化最優(yōu)性條件可表達(dá)為：2023/12/628通常需要分析的項(xiàng)目：(1)參數(shù)a，b，C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前方案無(wú)影響？(2)參數(shù)b，b，c中的一個(gè)(幾個(gè))變動(dòng)，對(duì)當(dāng)前方案影響程度？(3)如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？2023/12/629靈敏度分析的步驟：1、將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表上來(lái)。

具體計(jì)算方法是，按下列公式計(jì)算出由參數(shù)aij，bi，cj的變化而引起的最終單純形表上有關(guān)數(shù)字的變化。

2、檢查原問(wèn)題是否仍為可行解。

3、檢查對(duì)偶問(wèn)題是否仍為可行解。

4、按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問(wèn)題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算2023/12/630一、分析cj的變化線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù)cj的變化僅僅影響到檢驗(yàn)數(shù)(cj-zj)的變化。所以將cj的變化直接反映到最終單純形表中，只可能出現(xiàn)上頁(yè)表中前兩種情況。2023/12/631

例1-1：在美佳公司例子中，(1)若家電I的利潤(rùn)降至1.5元/件，而家電II的利潤(rùn)增至2元/件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化；(2)若家電I的利潤(rùn)不變，則家電II的利潤(rùn)在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？2023/12/632

解(1)：將家電I、II的利潤(rùn)變化直接反映到最終單純形表中得到表如下：cj1.52000CB基bx1x2x3x4x50x315/2001[5/4]-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/4

因變量x4的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代計(jì)算，得表如下：cj1.52000CB基bx1x2x3x4x50x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳公司隨家電I、II的利潤(rùn)變化應(yīng)調(diào)整為生產(chǎn)2件I，生產(chǎn)3件II。2023/12/633

(2)：設(shè)家電II的利潤(rùn)為(1+m)元，反映到最終單純形表中，得表如下：cj21+m000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21+mx23/2010-1/43/2cj-zj000-1/4+1/4m-1/2-3/2m為使上表中的解仍為最優(yōu)解，應(yīng)有：解得：即家電II的利潤(rùn)c2的變化范圍應(yīng)滿(mǎn)足：2023/12/634二、分析bi的變化右端項(xiàng)bi的變化在實(shí)際問(wèn)題中反映為可用資源數(shù)量的變化。bi變化反映到最終單純形表上將引起b列數(shù)字的變化，在表中可能出現(xiàn)第一或第三的兩種情況。出現(xiàn)第一種情況時(shí)，問(wèn)題的最優(yōu)基不變，變化后的b列值為最優(yōu)解。出現(xiàn)第三種情況時(shí)，用對(duì)偶單純形法迭代繼續(xù)找出最優(yōu)解。2023/12/635例1-2：在上述美佳公司例子中，(1)若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32h，分析公司最優(yōu)計(jì)劃的變化；(2)若設(shè)備A和設(shè)備B每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)基不變。2023/12/636

解(1)：因有，則：將其反映到最終單純形表中得表如下。由于該表中原問(wèn)題為非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算，其結(jié)果如下量表所示：2023/12/637cj21000CB基bx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2cj-zj000-1/4-1/2對(duì)偶單純形法處理后結(jié)果：cj21000CB基bx1x2x3x4x50x315051002x15110010x420-401-6cj-zj0-100-2由此美佳公司的最優(yōu)計(jì)劃改變?yōu)橹簧a(chǎn)5件家電I。2023/12/638

(2)：設(shè)調(diào)式工序每天可用能力為(5+m)h，因有將其反映到最終單純形表中，其b列數(shù)字為：當(dāng)b>=0時(shí)問(wèn)題的最優(yōu)基不變，解得-1<=m<=1。由此調(diào)試工序的能力應(yīng)在4h-6h之間。2023/12/639三、增加一個(gè)變量xj的分析增加一個(gè)變量在實(shí)際問(wèn)題中反映為增加一種新的產(chǎn)品。其分析步驟為：

1、計(jì)算

2、計(jì)算

3、若，原最優(yōu)解不變，只需將計(jì)算得到的和直接寫(xiě)入最終單純形表中；若，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。

例1-3：在美佳公司例子中，設(shè)該公司又計(jì)劃推出新型號(hào)的家電III，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為3h、4h、2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該種產(chǎn)品是否值得投產(chǎn)；若投產(chǎn)，該公司的最優(yōu)生產(chǎn)計(jì)劃有何變化。2023/12/640

解設(shè)該公司生產(chǎn)x6件家電III，有c6=3，P6=(3,4,2)T將其反映到最終單純形表中得表如下:2023/12/641因，故用單純形法繼續(xù)迭代計(jì)算結(jié)果為：cj210003CB基bx1x2x3x4x5x60x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/2[2]cj-zj000-1/4-1/21cj210003CB基bx1x2x3x4x5x60x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40由上表可知，美佳公司新的最優(yōu)生產(chǎn)計(jì)劃應(yīng)該為每天生產(chǎn)7/2件家電I，51/4件家電III。2023/12/642四、分析參數(shù)aij的變化

aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。若變量xj在最終單純形表中為基變量，則aij的變化分析步驟可參照本節(jié)之三；若變量xj在最終單純形表中為基變量，則aij的變化將使相應(yīng)的B和B-1發(fā)生變化，因此有可能出現(xiàn)原問(wèn)題和對(duì)偶問(wèn)題均為非可行解的情況。出現(xiàn)這種情況時(shí)，需引進(jìn)人工變量先將原問(wèn)題的解轉(zhuǎn)化為可行解，再用單純形法求解。

例1-4：在美佳公司的例子中，若家電II每件需設(shè)備A、B和調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品的利潤(rùn)變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃。2023/12/643

解先將生產(chǎn)工時(shí)變化后的新家電II看作是一種新產(chǎn)品，生產(chǎn)量x2’，仿上一節(jié)的步驟直接計(jì)算和并反映到最終單純形表中。其中：將其反映到最終單純形表中得表如下。2023/12/644因x2已變換為x2’，故用單純形算法將x2’替換出基變量中的x2，并在下一個(gè)表中不再保留x2，得表如下：cj213000CB基bx1x2x2’x3x4x50x315/20011/215/4-15/22x17/2101/201/4-1/21x23/201[1/2]0-1/43/2cj-zj003/20-1/4-1/2cj23000CB基bx1x2’x3x4x50x3-90014-242x121001/2-23x2’3010-1/23cj-zj0001/2-52023/12/645上表中，原問(wèn)題與對(duì)偶問(wèn)題均非可行解，故先設(shè)法使原問(wèn)題變?yōu)榭尚薪?。上表中?行的約束可以寫(xiě)為：x3+4x4-24x5=-9兩邊同乘以(-1)，再加上人工變量x6得-x3-4x4+24x5+x6=9將上式替換上表第一行，得：cj23000-MCB基bx1x2’x3x4x5x6-Mx6900-1-4[24]12