對(duì)偶與靈敏度分析第一頁(yè)，共四十五頁(yè)，2022年，8月28日對(duì)偶模型的一般式以例7為例，原問(wèn)題為（P）（D）這是最常見(jiàn)的對(duì)偶模型形式，稱為對(duì)稱式對(duì)偶模型。二者間具有十分對(duì)稱的對(duì)應(yīng)關(guān)系：

原問(wèn)題（P）對(duì)偶問(wèn)題（D）目標(biāo)max型目標(biāo)min型有n個(gè)變量（非負(fù)）有n個(gè)約束（大于等于）有m個(gè)約束（小于等于）有m個(gè)變量（非負(fù)）價(jià)格系數(shù)資源向量資源向量?jī)r(jià)格系數(shù)技術(shù)系數(shù)矩陣技術(shù)系數(shù)矩陣的轉(zhuǎn)置第二頁(yè)，共四十五頁(yè)，2022年，8月28日此外，還有一種情形

原問(wèn)題（P）對(duì)偶問(wèn)題（D）第j個(gè)變量為自由變量第j個(gè)約束為等式約束第i個(gè)約束為等式約束第i個(gè)變量為自由變量例8：寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃模型：第三頁(yè)，共四十五頁(yè)，2022年，8月28日例8：寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃模型：第四頁(yè)，共四十五頁(yè)，2022年，8月28日二、對(duì)偶的性質(zhì)（P）（D）考慮1.對(duì)稱性（P）與（D）互為對(duì)偶。證：由（P）、（D）的約束可得幾何意義：CXYb第五頁(yè)，共四十五頁(yè)，2022年，8月28日4.對(duì)偶定理若（P）有最優(yōu)解，則（D）也有最優(yōu)解，

且最優(yōu)值相同。證：對(duì)（P）增加松弛變量Xs，化為設(shè)其最優(yōu)基為B，終表為其檢驗(yàn)數(shù)為第六頁(yè)，共四十五頁(yè)，2022年，8月28日得證。第七頁(yè)，共四十五頁(yè)，2022年，8月28日問(wèn)題：(1)由性質(zhì)4可知，對(duì)偶問(wèn)題最優(yōu)解的表達(dá)式Y(jié)*=？

(2)

求Y*是否有必要重新求解（D）？

——CBB-1——不必。可以從原問(wèn)題（P）的單純形終表獲得。例如，在前面的練習(xí)中已知的終表為請(qǐng)指出其對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。第八頁(yè)，共四十五頁(yè)，2022年，8月28日5.互補(bǔ)松弛定理第九頁(yè)，共四十五頁(yè)，2022年，8月28日y1…yi…ymym+1…ym+j…yn+m

x1…xj…xnxn+1…xn+i…xn+m

對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的松弛變量原始問(wèn)題的變量原始問(wèn)題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0直觀上第十頁(yè)，共四十五頁(yè)，2022年，8月28日

6.對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋

（1）對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋——資源的影子價(jià)格（ShadowPrice）CBB-1——對(duì)偶問(wèn)題的最優(yōu)解——買主的最低出價(jià)；——原問(wèn)題資源的影子價(jià)格——當(dāng)該資源增加1單

位時(shí)引起的總收入的增量——賣主的內(nèi)控價(jià)格。例10：例1（煤電油例）的單純形終表如下：（1）請(qǐng)指出資源煤電油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？第十一頁(yè)，共四十五頁(yè)，2022年，8月28日例10：例1（煤電油例）的單純形終表如下：（1）請(qǐng)指出資源煤、電、油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？解：（1）煤、電、油的影子價(jià)格分別是0、1.36、0.52；其經(jīng)濟(jì)意義是當(dāng)煤、電、油分別增加1單位時(shí)可使總收入分別增加0、1.36、0.52。（2）由單純形終表還可得到：原問(wèn)題的最優(yōu)生產(chǎn)計(jì)劃、最大收入、資源剩余，對(duì)偶問(wèn)題的最低購(gòu)買價(jià)格、最少的購(gòu)買費(fèi)用等。第十二頁(yè)，共四十五頁(yè)，2022年，8月28日y1y2ym（2）對(duì)偶約束的經(jīng)濟(jì)解釋——產(chǎn)品的機(jī)會(huì)成本(OpportunityCost)機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn)增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品可以節(jié)省的資源第十三頁(yè)，共四十五頁(yè)，2022年，8月28日機(jī)會(huì)成本利潤(rùn)差額成本（3）對(duì)偶松弛變量的經(jīng)濟(jì)解釋——產(chǎn)品的差額成本（ReducedCost）差額成本=機(jī)會(huì)成本－利潤(rùn)第十四頁(yè)，共四十五頁(yè)，2022年，8月28日在利潤(rùn)最大化的生產(chǎn)計(jì)劃中（1）影子價(jià)格大于0的資源沒(méi)有剩余；（2）有剩余的資源影子價(jià)格等于0；（3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)；（4）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)。（4）互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋第十五頁(yè)，共四十五頁(yè)，2022年，8月28日三、對(duì)偶單純形法前節(jié)講到原問(wèn)題與對(duì)偶問(wèn)題的解之間的對(duì)應(yīng)關(guān)系時(shí)指出：在單純形表中進(jìn)行迭代時(shí)，在b列中得到的是原問(wèn)題的基可行解，而在檢驗(yàn)數(shù)行得到的是對(duì)偶問(wèn)題的基解。通過(guò)逐步迭代，當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問(wèn)題的解也是基可行解時(shí),已得到最優(yōu)解。即原問(wèn)題與對(duì)偶問(wèn)題都是最優(yōu)解。根據(jù)對(duì)偶問(wèn)題的對(duì)稱性，可以這樣考慮：若保持對(duì)偶問(wèn)題的解是基可行解，即cj?CBB-1Pj≤0，而原問(wèn)題在非可行解的基礎(chǔ)上，通過(guò)逐步迭代達(dá)到基可行解，這樣也得到了最優(yōu)解。其優(yōu)點(diǎn)是原問(wèn)題的初始解不一定是基可行解，可從非基可行解開(kāi)始迭代。第十六頁(yè)，共四十五頁(yè)，2022年，8月28日設(shè)原問(wèn)題為

maxz=CX

AX=b

X≥0又設(shè)B是一個(gè)基。不失一般性，令B=(P1，P2，…，Pm)，它對(duì)應(yīng)的變量為XB=(x1，x2，…,xm)。當(dāng)非基變量都為零時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，設(shè)(B-1b)i＜0，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，即對(duì)偶問(wèn)題保持可行解，它的各分量是

(1)對(duì)應(yīng)基變量x1，x2，…,xm的檢驗(yàn)數(shù)是σi=ci

?

CBB-1Pj=0，i=1,2,…,m(2)對(duì)應(yīng)非基變量xm+1，…，xn的檢驗(yàn)數(shù)是σj=cj?CBB-1Pj≤0，j=m+1,…,n第十七頁(yè)，共四十五頁(yè)，2022年，8月28日每次迭代是將基變量中的負(fù)分量xl取出，去替換非基變量中的xk，經(jīng)基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問(wèn)題來(lái)看，經(jīng)過(guò)每次迭代，原問(wèn)題由非可行解往可行解靠近。當(dāng)原問(wèn)題得到可行解時(shí)，便得到了最優(yōu)解。第十八頁(yè)，共四十五頁(yè)，2022年，8月28日對(duì)偶單純形法的計(jì)算步驟如下：

(1)根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。停止計(jì)算。若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算。

(2)確定換出變量。按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l對(duì)應(yīng)的基變量xi為換出變量

(3)確定換入變量。在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有αlj≥0，則無(wú)可行解，停止計(jì)算。若存在αlj＜0(j=1,2,…，n),計(jì)算第十九頁(yè)，共四十五頁(yè)，2022年，8月28日對(duì)偶單純形法的計(jì)算步驟如下：按θ規(guī)則所對(duì)應(yīng)的列的非基變量xk為換入變量，這樣才能保持得到的對(duì)偶問(wèn)題解仍為可行解。

(4)以αlk為主元素，按原單純形法在表中進(jìn)行迭代運(yùn)算，得到新的計(jì)算表。重復(fù)步驟(1)～(4)。第二十頁(yè)，共四十五頁(yè)，2022年，8月28日例:用對(duì)偶單純形法求解minw=2x1+3x2+4x3x1+2x2+x3≥32x1?x2+3x3≥4x1，x2，x3≥0

解：先將此問(wèn)題化成下列形式，以便得到對(duì)偶問(wèn)題的初始可行基maxz=?2x1?

3x2?

4x3?x1?

2x2?

x3+x4=?3?2x1+x2?

3x3+x5=?4xj≥0，j=1,2,…,5第二十一頁(yè)，共四十五頁(yè)，2022年，8月28日例6的初始單純形表，見(jiàn)表。從表看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解。因b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。

第二十二頁(yè)，共四十五頁(yè)，2022年，8月28日換出變量的確定：換入變量的確定：按上述對(duì)偶單純形法計(jì)算步驟(3)，即在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有αlj≥0，則無(wú)可行解，停止計(jì)算。按上述對(duì)偶單純形法計(jì)算步驟(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l對(duì)應(yīng)的基變量xi為換出變量。計(jì)算min(?3,?4)=?4故x5為換出變量。故x1為換入變量。換入、換出變量的所在列、行的交叉處“?2”為主元素。按單純形法計(jì)算步驟進(jìn)行迭代，得表2-7。第二十三頁(yè)，共四十五頁(yè)，2022年，8月28日第二十四頁(yè)，共四十五頁(yè)，2022年，8月28日表2-8中，b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，故問(wèn)題的最優(yōu)解為X*=(11/5，2/5，0，0，0)T若對(duì)應(yīng)兩個(gè)約束條件的對(duì)偶變量分別為y1和y2，則對(duì)偶問(wèn)題的最優(yōu)解為Y*=(y1*,y2*)=(8/5,1/5)第二十五頁(yè)，共四十五頁(yè)，2022年，8月28日對(duì)偶單純形法有以下優(yōu)點(diǎn)：(1)初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算。(2)當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問(wèn)題用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。(3)在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時(shí)需要用對(duì)偶單純形法，這樣可使問(wèn)題的處理簡(jiǎn)化。對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可行基，因而這種方法在求解線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)應(yīng)用。第二十六頁(yè)，共四十五頁(yè)，2022年，8月28日三、靈敏度分析

討論模型的系數(shù)或變量發(fā)生小的變化時(shí)對(duì)解的影響（如它們?cè)诤畏秶鷥?nèi)變化時(shí)可使原最優(yōu)解或最優(yōu)基不變？）我們主要討論C、b和變量結(jié)構(gòu)變化時(shí)對(duì)解的影響。對(duì)解怎樣影響？——影響解的-最優(yōu)性

-可行性第二十七頁(yè)，共四十五頁(yè)，2022年，8月28日1.b變化時(shí)的分析第二十八頁(yè)，共四十五頁(yè)，2022年，8月28日例11：在例1（煤電油例）中，其單純形終表如下：（1）電的影子價(jià)格是多少？使最優(yōu)基仍適用的電的變化范圍為何？解：（1）電的影子價(jià)格是1.36。第二十九頁(yè)，共四十五頁(yè)，2022年，8月28日例11：在例1（煤電油例）中，其單純形終表如下：（2）若有人愿以每度1元的價(jià)格向該廠供應(yīng)25度電，是否值得接受？解：（2）值得。因25在B的適用范圍內(nèi)（即影子價(jià)格適用），且

1.00-1.36<0。第三十頁(yè)，共四十五頁(yè)，2022年，8月28日2.C變化時(shí)的分析第三十一頁(yè)，共四十五頁(yè)，2022年，8月28日例11：在例1（煤電油例）中，其單純形終表如下：（3）甲產(chǎn)品的價(jià)格在何范圍內(nèi)變化時(shí)，現(xiàn)最優(yōu)解不變？解：甲產(chǎn)品的價(jià)格c1是基變量的價(jià)格系數(shù)。第三十二頁(yè)，共四十五頁(yè)，2022年，8月28日3.增加新變量時(shí)的分析

主要討論增加新變量xn+1是否有利。經(jīng)濟(jì)意義是第n+1種新產(chǎn)品是否應(yīng)當(dāng)投產(chǎn)，數(shù)學(xué)意義是xn+1是否應(yīng)進(jìn)基。經(jīng)濟(jì)意義：市場(chǎng)價(jià)影子價(jià)第三十三頁(yè)，共四十五頁(yè)，2022年，8月28日例11：在例1（煤電油例）中，其單純形終表如下：（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價(jià)為6.5，問(wèn)該產(chǎn)品是否可投產(chǎn)？故丙產(chǎn)品可以投產(chǎn)。第三十四頁(yè)，共四十五頁(yè)，2022年，8月28日首先將線性規(guī)劃與經(jīng)濟(jì)問(wèn)題聯(lián)系起來(lái)的是

（庫(kù)普曼）和

（康脫羅維奇）二人因此而共同分享了1975年的第7屆諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。第三十五頁(yè)，共四十五頁(yè)，2022年，8月28日求解線性規(guī)劃的計(jì)算機(jī)軟件舉例——LINDO、EXCELLINDO可以從下面的網(wǎng)址下載：

LINDO由美國(guó)芝加哥大學(xué)開(kāi)發(fā)，可求解線性規(guī)劃和線性整數(shù)規(guī)劃等。其可按自然格式輸入模型，使用方便。輸入例：MAX2X+3Y

ST

2)4X+9Y<93)7X+6Y<13

END

可用HELP命令得到幫助。第三十六頁(yè)，共四十五頁(yè)，2022年，8月28日計(jì)算結(jié)果說(shuō)明：REDUCEDCOST

為使該變量進(jìn)基，其價(jià)格系數(shù)至少應(yīng)增加的數(shù)值；SLACKORSUPLUS

松弛或剩余變量；DUALPRICES

影子價(jià)格;ALLOWABLEINCREASE

靈敏度分析中可使最優(yōu)基不變的系數(shù)可增量之上界；ALLOWABLEDECREASE

靈敏度分析中可使最優(yōu)基不變的系數(shù)可減量之上界；第三十七頁(yè)，共四十五頁(yè)，2022年，8月28日例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?

A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天：第三十八頁(yè)，共四十五頁(yè)，2022年，8月28日1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時(shí)間480小時(shí)至多加工100公斤A1

50桶牛奶每天第三十九頁(yè)，共四十五頁(yè)，2022年，8月28日模型求解

軟件實(shí)現(xiàn)

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元。第四十頁(yè)，共四十五頁(yè)，2022年，8月28日結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）第四十一頁(yè)，共四十五頁(yè)，2022年，8月28日結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格

35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！第四十二頁(yè)，共四十五頁(yè)，2022年，8月28日RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINI