第3章對(duì)偶規(guī)劃

1第三章

線性規(guī)劃問(wèn)題的對(duì)偶與靈敏度分析一、對(duì)偶思想1.

對(duì)偶思想舉例---矩形的面積與周長(zhǎng)關(guān)系的兩種表述：周長(zhǎng)一定的矩形中，以正方形面積最大；面積一定的矩形中，以正方形周長(zhǎng)最??；

對(duì)偶問(wèn)題的提出對(duì)偶是指對(duì)同一問(wèn)題從不同的角度觀察，得到兩種獨(dú)立的表述的思想。例1

要求制定一個(gè)生產(chǎn)計(jì)劃方案，在設(shè)備和原材料可能供應(yīng)的范圍內(nèi)，使得產(chǎn)品的總利潤(rùn)最大：甲產(chǎn)品乙產(chǎn)品提供量設(shè)備128臺(tái)時(shí)材料A4016kg材料B0412kg利潤(rùn)23單位元1.對(duì)偶問(wèn)題的提出3.1線性規(guī)劃的對(duì)偶問(wèn)題它的對(duì)偶問(wèn)題就是一個(gè)價(jià)格系統(tǒng)，使在平衡了設(shè)備和原材料的直接成本后，所確定的價(jià)格系統(tǒng)最具有競(jìng)爭(zhēng)力。（用于生產(chǎn)第i種產(chǎn)品的資源轉(zhuǎn)讓收益不小于生產(chǎn)該種產(chǎn)品時(shí)獲得的利潤(rùn)）

若工廠自己不生產(chǎn)甲和乙產(chǎn)品，將現(xiàn)有的設(shè)備及原材料轉(zhuǎn)為外租時(shí)，那么上述的價(jià)格系統(tǒng)能保證不虧本又最富有競(jìng)爭(zhēng)力（包工及原材料的總價(jià)格最低）。

當(dāng)原問(wèn)題和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，這一對(duì)線性規(guī)劃對(duì)應(yīng)的目標(biāo)函數(shù)值是相等的：

Zmax=Wmin=14

對(duì)偶變量的經(jīng)濟(jì)意義可以解釋為對(duì)設(shè)備及原材料的單位定價(jià)。表示對(duì)偶關(guān)系二、原問(wèn)題和對(duì)偶問(wèn)題的關(guān)系1.對(duì)稱形式的對(duì)偶關(guān)系（1）定義：若原問(wèn)題是

則定義其對(duì)偶問(wèn)題為:這兩個(gè)式子之間的變換關(guān)系稱為“對(duì)稱形式的對(duì)偶關(guān)系”。

（2）對(duì)稱形式的對(duì)偶關(guān)系的矩陣描述（L）

（3）怎樣從原始問(wèn)題寫(xiě)出其對(duì)偶問(wèn)題？

對(duì)稱性問(wèn)題按照定義“上、下”交換，“轉(zhuǎn)置”互換，不等式變號(hào)，“極大”變“極小”9或者對(duì)稱形式：互為對(duì)偶

(LP)Maxz=cT

x(DP)Minf=bT

ys.t.Ax≤bs.t.AT

y≥c

x≥0y≥0“Max--≤”“Min--≥”例3寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃

11非對(duì)稱形式的對(duì)偶規(guī)劃:對(duì)非對(duì)稱形式，可以按照下面的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃(1)將模型統(tǒng)一為“max，≤”或“min，≥”的形式，對(duì)于其中的等式約束按下面(2)、(3)中的方法處理；(2)若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒(méi)有非負(fù)限制；(3)若原規(guī)劃的某個(gè)變量的值沒(méi)有非負(fù)限制，則在對(duì)偶問(wèn)題中與此變量對(duì)應(yīng)的那個(gè)約束為等式。2.非對(duì)稱形式的對(duì)偶關(guān)系：12

下面對(duì)關(guān)系(2)作一說(shuō)明。對(duì)于關(guān)系(3)可以給出類似的解釋：設(shè)原規(guī)劃中第一個(gè)約束為等式：

a11x1+…+a1nxn

=b1那么，它與下面兩個(gè)不等式等價(jià)13原規(guī)劃模型可以寫(xiě)成14這里，把y1看做是y1=y1'-y1"，于是y1沒(méi)有非負(fù)限制。轉(zhuǎn)化為對(duì)稱形式，直接寫(xiě)出對(duì)偶規(guī)劃（1）原問(wèn)題（2）對(duì)偶問(wèn)題特點(diǎn)：對(duì)偶變量符號(hào)不限，系數(shù)陣轉(zhuǎn)置。(特點(diǎn)：等式約束)非對(duì)稱形式的對(duì)偶關(guān)系：

原問(wèn)題（或?qū)ε紗?wèn)題）

對(duì)偶問(wèn)題（或原問(wèn)題）

目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinW約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”

對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量

決策變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量

約束條件數(shù)：n第j個(gè)約束條件類型為“≥”第j個(gè)約束條件類型為“≤”第j個(gè)約束條件類型為“=”

（2）原始問(wèn)題與對(duì)偶問(wèn)題關(guān)系表例4寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃：對(duì)偶定理是揭示原始問(wèn)題與對(duì)偶問(wèn)題解之間重要關(guān)系的

定理

對(duì)稱性定理(證明略)對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。3.1.3線性規(guī)劃的對(duì)偶理論一系列定理。22定理3-1(弱對(duì)偶定理）若X和Y分別為原規(guī)劃（P）和對(duì)偶規(guī)劃（D）的可行解，那么cTx≤bTy。推論1設(shè)X0和Y0分別為原規(guī)劃（P）和對(duì)偶規(guī)劃（D）的可行解，當(dāng)CTX0=bTY0時(shí)，X0、Y0分別是兩個(gè)問(wèn)題的最優(yōu)解。23推論2若規(guī)劃（P）有可行解，則（P）有最優(yōu)解的充分必要條件是規(guī)劃（D）有可行解。推論3若規(guī)劃（D）有可行解，則（D）有最優(yōu)解的充分必要條件是規(guī)劃（P）有可行解。推論4

若原問(wèn)題與對(duì)偶問(wèn)題都有可行解，則它們都有最優(yōu)解。推論5若原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)界解，則其對(duì)偶問(wèn)題(原問(wèn)題)無(wú)可行解。其逆不真。若原問(wèn)題有最優(yōu)，則對(duì)偶問(wèn)題也有最優(yōu)，且最優(yōu)值相等，反之亦然。定理3-2強(qiáng)對(duì)偶定理推論對(duì)偶問(wèn)題的最優(yōu)解為原問(wèn)題最優(yōu)表中，相應(yīng)的松弛變量的檢驗(yàn)數(shù)的相反數(shù)。對(duì)偶性質(zhì)原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系小結(jié)對(duì)應(yīng)關(guān)系原問(wèn)題最優(yōu)解無(wú)界解無(wú)可行解對(duì)偶問(wèn)題最優(yōu)解(Y,Y)(N,N)————無(wú)界解————(Y,Y)無(wú)可行解——(Y,Y)(Y,Y)一對(duì)對(duì)偶問(wèn)題關(guān)系1.都有最優(yōu)解，且目標(biāo)函數(shù)相等或都沒(méi)最優(yōu)2.都無(wú)可行解3.一個(gè)無(wú)界解（有可行解），另一個(gè)無(wú)可行解351．影子價(jià)格的概念考慮互為對(duì)偶的線性規(guī)劃(P)、(D)設(shè)y*=（y1*,…，ym*)T為對(duì)偶規(guī)劃(D)的最優(yōu)解，則yi*稱為規(guī)劃(P)第i個(gè)約束對(duì)應(yīng)的影子價(jià)格(ShadowPrice)。四、影子價(jià)格36影子價(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)。37(2)影子價(jià)格表明資源增加對(duì)總效益產(chǎn)生的影響。根據(jù)推論，在最優(yōu)解的情況下，有因此，可以將z*看做是bi的函數(shù)，對(duì)bi求偏導(dǎo)數(shù)可得到這說(shuō)明，如果右端常數(shù)增加一個(gè)單位，則目標(biāo)函數(shù)值的增量將是y*。38

影子價(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ì)含義是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過(guò)了這個(gè)“一定的范圍”時(shí)，總利潤(rùn)的增加量則不是按照影子價(jià)格給出的數(shù)值線性地增加。這個(gè)問(wèn)題還將在靈敏度分析一節(jié)中討論。第2節(jié)對(duì)偶單純形法最小比值原則421.建立初始單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2；2.若b≥0,檢驗(yàn)數(shù)都為非正，則得到最優(yōu)解,停止;否則,若有bk<0,轉(zhuǎn)3二、對(duì)偶單純形法主要步驟為了保證檢驗(yàn)數(shù)的非正性取適合于解如下形式的線性規(guī)劃問(wèn)題在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便。三、對(duì)偶單純形法的適用范圍是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計(jì)算計(jì)算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒(méi)有最優(yōu)解沒(méi)有最優(yōu)解單純形法對(duì)偶單純形法<第3節(jié)靈敏度分析56ci

單個(gè)變化保持最優(yōu)解不變的允許范圍bj單個(gè)變化保持對(duì)偶價(jià)格不變的允許范圍上述研究是本段重點(diǎn)A中元素發(fā)生變化線性規(guī)劃增加一個(gè)約束線性規(guī)劃增加一個(gè)變量57考慮檢驗(yàn)數(shù)

j1.若ck是非基變量的系數(shù)：設(shè)ck變化為ck

+

ck

k’=ck

+ck－∑aikci=k+ck只要k’≤0,即

ck

≤-k，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù)

k用k’取代，繼續(xù)單純形法的表格計(jì)算。一、目標(biāo)函數(shù)系數(shù)ci的變化58例Maxz=-2x1-3x2-4x3s.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥059最優(yōu)單純形表

從表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5時(shí)，原最優(yōu)解不變。60設(shè)cs變化為cs

+cs

，那么j’=cj-∑aijci-(

cs+cs)asj

=j

-csasj

i≠s只要對(duì)所有非基變量j’≤0，即j≤csasj

，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù)j用j’取代，繼續(xù)單純形法的表格計(jì)算。

Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}2.若cs是基變量的系數(shù)61Maxz=2x1+3x2+0x3+0x4+0x5

s.t.

x1+2x2+x3=84x1+x4=164x2+x5=

12

x1,x2,x3,x4,x5≥0例62下表為最優(yōu)單純形表,考慮基變量系數(shù)c2發(fā)生變化由σj=cj-(c1×a1j+c5×a5j+(c2+Δc2)×a2j)(j=3,4)可得到-3≤Δc2≤1時(shí)，原最優(yōu)解不變。63

設(shè)分量br

變化為br+br

，根據(jù)第2章的討論，最優(yōu)解的基變量xB=B-1b，那么只要保持B-1(b+b)≥0，其中b=(0,…,br,0,…,0)T,則最優(yōu)基不變；否則，需要利用對(duì)偶單純形法繼續(xù)計(jì)算?？紤](LP)

Maxz=cT

xs.t.Ax≤b

x≥0二、右端常數(shù)的變化最優(yōu)單純形表中含有B-1=(aij）(i=1,…,m;j=n+1,…,n+m)66新的xi=(B-1b)i+brair(i=1,…,m)由此可得，最優(yōu)基不變的條件是Max{-b’i/airair>0}≤br≤Min{-b’i/airair<0}67上例最優(yōu)單純形表如下

6800.250這里B-1=-20.510.5-0.1250各列分別對(duì)應(yīng)b1、b2、b3的單一變化因此，設(shè)b1增加4，則x1、x5、x2分別變?yōu)椋?+0×4=4,4+(-2)×4=-4<0,2+0.5×4=4用對(duì)偶單純形法進(jìn)一步求解，可得：69于是，x*=(