運(yùn)籌學(xué)課件-對(duì)偶定理、影子價(jià)格

設(shè)原問題是（記為L(zhǎng)P）：

對(duì)偶問題是（記為DP）：這里A是m×n矩陣X是n×1列向量，Y是1×m行向量。假設(shè)Xs與Ys分別是（LP）與（DP）的松馳變量?！拘再|(zhì)1】

對(duì)稱性對(duì)偶問題的對(duì)偶是原問題。

【證】設(shè)原問題是2.1.3對(duì)偶定理它與下列線性規(guī)劃問題是等價(jià)的：再寫出它的對(duì)偶問題。它與下列線性規(guī)劃問題是等價(jià)的即是原問題。

由表2－1知，它的對(duì)偶問題是【性質(zhì)2】

弱對(duì)偶性

設(shè)X°、Y°分別為（LP）與（DP）的可行解，則

【證】因?yàn)閄°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,將不等式AX°≤b

兩邊左乘Y°得Y°AX°≤Y°b再將不等式Y(jié)°A≥C

兩邊右乘X°，故

CX°≤Y°AX≤Y°b這一性質(zhì)說明了兩個(gè)線性規(guī)劃互為對(duì)偶時(shí)，求最大值的線性規(guī)劃的任意目標(biāo)值都不會(huì)大于求最小值的線性規(guī)劃的任一目標(biāo)值，不能理解為原問題的目標(biāo)值不超過對(duì)偶問題的目標(biāo)值。得CX°≤Y°AX°由這個(gè)性質(zhì)可得到下面幾個(gè)結(jié)論：

（1）（LP）的任一可行解的目標(biāo)值是（DP）的最優(yōu)值下界；（DP）的任一可行解的目標(biāo)是（LP）的最優(yōu)值的上界；（2）在互為對(duì)偶的兩個(gè)問題中，若一個(gè)問題可行且具有無界解，則另一個(gè)問題無可行解；(3）若原問題可行且另一個(gè)問題不可行，則原問題具有無界解。

注意上述結(jié)論（2）及（3）的條件不能少。一個(gè)問題有可行解時(shí)，另一個(gè)問題可能有可行解（此時(shí)具有無界解）也可能無可行解。例如：無可行解，而對(duì)偶問題有可行解，由結(jié)論（3）知必有無界解?！拘再|(zhì)3】最優(yōu)準(zhǔn)則定理設(shè)X°與Y°分別是（LP）與（DP）的可行解，則當(dāng)X°、Y°是（LP）與（DP）的最優(yōu)解當(dāng)且僅當(dāng)CX°=Y°b.【證】若X°、Y°為最優(yōu)解，B為（LP）的最優(yōu)基，則有Y°=CBB－1，并且當(dāng)CX°=Y°b時(shí)，由性質(zhì)1，對(duì)任意可行解有即Y°b是（DP）中任一可行解的目標(biāo)值的下界，CX°是（LP）中任一可行解的目標(biāo)值的上界，從而X°、Y°是最優(yōu)解?！拘再|(zhì)4】

還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解?！咀C】設(shè)（LP）有最優(yōu)解X°，那么對(duì)于最優(yōu)基B必有C－

CBB-1A≤0與－CBB-1≤0，即有Y°A≥C與Y°≥0，這里Y°=CBB-1

，從而Y°是可行解，對(duì)目標(biāo)函數(shù)有由性質(zhì)3知Y°是最優(yōu)解。由性質(zhì)4還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解。證明：由兩者均有可行解，則根據(jù)弱對(duì)偶定理可知兩者均有界，因此均有最優(yōu)解。以下對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃問題及其對(duì)偶問題證明在最優(yōu)解時(shí)，原問題與對(duì)偶問題相等。的最優(yōu)值相等。定理5(主對(duì)偶定理)

若(LP)和(DP)均可行，那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。設(shè)B是其最優(yōu)基，是與之對(duì)應(yīng)的最優(yōu)的基本可行解。令，則對(duì)應(yīng)于基B的檢驗(yàn)數(shù)滿足：

因此成為對(duì)偶問題的一個(gè)可行解，且此時(shí)對(duì)應(yīng)的目標(biāo)函數(shù)值為：

注意到原問題的最優(yōu)目標(biāo)值為：恰好與對(duì)偶問題的目標(biāo)函數(shù)值相等?！拘再|(zhì)6】

（LP）的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于（DP）的一組基本解.

其中第j個(gè)決策變量xj的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于（DP）中第j個(gè)松弛變量的解，第i個(gè)松弛變量的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于第i個(gè)對(duì)偶變量yi的解。反之，（DP）的檢驗(yàn)數(shù)（注意：不乘負(fù)號(hào)）對(duì)應(yīng)于（LP）的一組基本解。證明略?！纠?.1】線性規(guī)劃（1）用單純形法求最優(yōu)解；（2）寫出每步迭代對(duì)應(yīng)對(duì)偶問題的基本解；（3）從最優(yōu)表中寫出對(duì)偶問題的最優(yōu)解；（4）用公式Y(jié)=CBB-1求對(duì)偶問題的最優(yōu)解?！窘狻浚?）加入松弛變量x4、x5后，單純形迭代如表2－2所示。表2－2XBx1x2x3x4x5b(1)x4x52*1-102410012→4λj6↑-2100

(2)x1x510-1/21/2*131/2-1/20113→λj01↑-5-30

(3)x1x21001460-11246λj00-11-2-2

最優(yōu)解X=（4，6，0），最優(yōu)值Z=6×4－2×6=12；

（2）設(shè)對(duì)偶變量為y1、y2,松弛變量為y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性質(zhì)6得到對(duì)偶問題的基本解（y1、y2、y3、y4、y5）

=（－λ4，－λ5，－λ1，－λ2，－λ3），即

表2－2（1）中λ=（6，－2，1，0，0），

則Y（1）=（0，0，-6，2，－1）表2－2（2）中λ=（0，1，－5，－3，0），

則Y（2）=（3，0，0，－1，5）表2－2（3）中λ=（0，0，－11，－2，－2），

則Y（3）=（2，2，0，0，11）（1）因?yàn)楸?－2（3）為最優(yōu)解，故

Y（3）=（2，2，0，0，11）為對(duì)偶問題最優(yōu)解；（1）表2－2（3）中的最優(yōu)基

B-1為表2－2（3）中x4，x5兩列的系數(shù)，即CB=（6，－2），因而本節(jié)您學(xué)了六個(gè)對(duì)偶性質(zhì)；這些性質(zhì)是研究原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系；表2－3也許對(duì)您了解這些性質(zhì)有幫助。表2－3一個(gè)問題max另一個(gè)問題min有最優(yōu)解有最優(yōu)解性質(zhì)4無最優(yōu)解無最優(yōu)解無最優(yōu)解性質(zhì)4無界解（有可行解）無可行解性質(zhì)2無可行解無界解（有可行解）應(yīng)用已知最優(yōu)解通過解方程求最優(yōu)解性質(zhì)5已知檢驗(yàn)數(shù)檢驗(yàn)數(shù)乘以－1求得基本解性質(zhì)6影子價(jià)格

——

是一個(gè)向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。

若x*,y*

分別為（LP）和（DP）的最優(yōu)解，

那么，cT

x*=bT

y*

。

根據(jù)f=bTy*=b1y1*+b2y2*+

+bmym*

可知

f/

bi

=

yi*

yi*

表示

bi

變化1個(gè)單位對(duì)目標(biāo)f

產(chǎn)生的影響，稱yi*

為bi的影子價(jià)格。

注意：若B

是最優(yōu)基，

y*=(BT)-1

cB

為影子價(jià)格向量。2.1.4影子價(jià)格

影子價(jià)格的經(jīng)濟(jì)含義

(1)影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià)企業(yè)可以根據(jù)現(xiàn)有資源的影子價(jià)格，對(duì)資源的使用有兩種考慮：第一，是否將設(shè)備用于外加工或出租，若租費(fèi)高于某設(shè)備的影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租。第二，是否將投資用于購(gòu)買設(shè)備，以擴(kuò)大生產(chǎn)能力，若市價(jià)低于某設(shè)備的影子價(jià)格，可考慮買進(jìn)該設(shè)備，否則不宜買進(jìn)。

（2）影子價(jià)格表明資源增加對(duì)總效益產(chǎn)生的影響。根據(jù)推論“設(shè)x0和y0分別為原規(guī)劃（P）和對(duì)偶規(guī)劃（D）的可行解，當(dāng)cx0=bTy0時(shí)，x0、y0分別是兩個(gè)問題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關(guān)系

因此，可以將z*看作是bi,i=1,2，…,m的函數(shù)，對(duì)bi求偏導(dǎo)數(shù)可得到

這說明，如果右端常數(shù)增加一個(gè)單位，則目標(biāo)函數(shù)值的增量將是

影子價(jià)格反映了不同的局部或個(gè)體的增量可以獲得不同的整體經(jīng)濟(jì)效益。如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價(jià)格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。

需要指出，影子價(jià)格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤(rùn)等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格的經(jīng)濟(jì)含義（2），是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過了這個(gè)“一定的范圍”時(shí)，總利潤(rùn)的增加量則不是按照影子價(jià)格給出的數(shù)值線性地增