運(yùn)籌學(xué)胡運(yùn)權(quán)第五版課件第二章

第二章線性規(guī)劃的對偶理論DualTheory§2.1對偶問題的提出

例

常山機(jī)器廠生產(chǎn)I、II

兩種產(chǎn)品。這兩種產(chǎn)品都分別要在ABC三種不同設(shè)備上加工。按工藝規(guī)定，生產(chǎn)每件產(chǎn)品的單位利潤、消耗三種設(shè)備的工時(shí)以及各種設(shè)備工時(shí)的限額如表：如何安排生產(chǎn)才能使總的利潤最大？消耗設(shè)備工時(shí)III設(shè)備工時(shí)限量設(shè)備A設(shè)備B設(shè)備C240205121615利潤（元）23解：maxz=2x1+3

x2

2x1+2x212 4x1165

x2

15x10，

x20

s.t.LP1

假設(shè)另有四海機(jī)器廠想租借常山機(jī)器廠的全部可用資源進(jìn)行生產(chǎn)。問：常山機(jī)器廠應(yīng)該如何給這些資源定出一個(gè)合理的租金，既使四海機(jī)器廠愿意租借，又使本廠能得到自己組織生產(chǎn)這些產(chǎn)品時(shí)所能獲得的最大收益。解：設(shè)A、B、C設(shè)備每小時(shí)出租的價(jià)格分別為y1、y2、y3元，則新的線性規(guī)劃數(shù)學(xué)模型為：LP2

對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（LP1

）必然有與之相伴而生的另一個(gè)線性規(guī)劃問題（LP2

），即任何一個(gè)求max

z

的LP1都有一個(gè)求min

w的LP2

。將LP1稱為“原問題”，記為P；將LP2稱為“對偶問題”，記為D。原問題（P）：對偶問題（D）：1、基本概念原問題P對偶問題D原變量x1,x2對偶變量y1,y2,y3原目標(biāo)z對偶目標(biāo)w原約束對偶約束變量約束2、一般形式原問題Pmaxz=c1x1+c2x2+···+

cn

xn

s.t.

a11x1+a12x2+···+

a1nxn

b1

a21x1+a22x2+···+

a2nxn

b2

···am1x1+am2x2+···+

amn

xn

bm

xj

0，（j=1,2,···,n）

對偶問題Dminw=b1y1+b2y2+···+bm

ym

s.t.

a11y1+a21y2+···+am1ym

c1

a12y1+a22y2+···+am2ym

c2

···a1ny1+a2ny2+···+amn

ym

cn

yi0，(i=1,2,···,m)其中

例：寫出下列LP問題的對偶問題解：對偶問題為：§2.2原問題與對偶問題（max的基本形式）（min的基本形式）1、基本形式的聯(lián)系與區(qū)別（1）原目標(biāo)求極大，對偶目標(biāo)求極??；（2）原約束個(gè)數(shù)=對偶變量個(gè)數(shù)原變量個(gè)數(shù)=對偶約束個(gè)數(shù)

原約束決定對偶變量原變量決定對偶約束；（3）原約束≤方向，對偶約束≥方向；（4）原目標(biāo)的系數(shù)對應(yīng)對偶約束的右端常數(shù)原約束的右端常數(shù)對應(yīng)對偶目標(biāo)的系數(shù)；（5）原系數(shù)矩陣與對偶系數(shù)矩陣互為轉(zhuǎn)置；（6）原變量與對偶變量都是非負(fù)取值。例將下列問題作為原問題，寫出其對偶問題。解：先改寫為原問題的基本形式：再對偶化：最后簡化得到已知問題的對偶問題：2、基本形式的表格比較3、互為對偶關(guān)系

若LP2是LP1的對偶問題，則LP1是LP2的對偶問題。minZ’=-CXs.t.-AX≥-b X≥0

minW=bTYs.t.ATY≥CTY≥0maxZ=CXs.t.AX≤b X≥0對偶的定義對偶的定義maxW’=-bTYs.t.-ATY≤-CTY≥0改寫改寫例寫出下列問題的對偶問題。解：第一步改寫為min的基本形式第二步對偶化第三步簡化為已知問題的對偶問題：比較原問題和對偶問題：基本形式非基本形式4、原問題與對偶問題的互化原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)max（基本）目標(biāo)函數(shù)min

（基本）約束條件m個(gè)m個(gè)變量≤（基本）≥0（基本）≥≤0=無約束變量n個(gè)n個(gè)約束條件≥0（基本）≥（基本）≤0≤無約束=約束條件的右端項(xiàng)目標(biāo)函數(shù)的系數(shù)目標(biāo)函數(shù)的系數(shù)約束條件的右端項(xiàng)例直接寫出下列線性規(guī)劃問題的對偶問題。練習(xí)寫出下列問題的對偶問題。解：對偶問題為：§2.3對偶問題的基本性質(zhì)在本節(jié)中設(shè)原問題和對偶問題如下：1、弱對偶性（弱對偶原理）：設(shè)和分別是問題P和D的可行解，則必有證明：2、最優(yōu)性：

若X*和Y*分別是P和D的可行解且CX*=bTY*，則X*，Y*分別是問題P和D的最優(yōu)解。證明：3、無界性

若原問題有無界解，則對偶問題無可行解。

若對偶問題有無界解，則原問題無可行解。證明：注：逆定理不成立。即“如果原問題無可行解，那么對偶問題有無界解”不成立。此時(shí)，對偶問題可能有無界解，也可能無可行解。4、強(qiáng)對偶性（對偶定理）

若原問題有最優(yōu)解，則對偶問題一定有最優(yōu)解，且

zmax=wmin.證：設(shè)X*是原問題的最優(yōu)解，則所有檢驗(yàn)數(shù)都非正。即

=C-CBB-1A0∴CBB-1AC令CBB-1=

Y*

T，有

Y*T

AC,轉(zhuǎn)置得ATY*

CT-----------------------①又因?yàn)?/p>

S′

=-CBB-1

=-Y*T0，所以Y*=-（S′）T

0------②

由①②知Y*是對偶問題的可行解，而CX*=CBb′，其滿足:CX*

=CB(B-1b)=CBB-1b=Y*T

b=bTY*

由最優(yōu)性(性質(zhì)2)，∴Y*是對偶問題的最優(yōu)解。注意：若原問題有最優(yōu)解，則在最終單純形表中，原問題的最優(yōu)解是第三列，而對偶問題的最優(yōu)解是松弛變量檢驗(yàn)數(shù)的相反數(shù)。

1001/40

00-21/21

011/2-1/80

4422X10X53X2

x1x2x3x4x5

CBXBb

23000

Cj00-3/2-1/805、互補(bǔ)松弛性證明：松條件---變量＞0，約束不等式；緊條件---變量=0，約束為等式。將該性質(zhì)應(yīng)用于其對偶問題時(shí)，則有：例考慮下面問題解:則6、P和D之間存在一對互補(bǔ)的基解

（1）原問題的變量對應(yīng)于對偶問題的剩余變量，原松弛變量對應(yīng)對偶變量；（2）互相對應(yīng)的變量在一個(gè)問題中是基變量，在另一個(gè)問題中是非基變量；（3）互補(bǔ)的基解對應(yīng)的目標(biāo)函數(shù)值相等。原問題對偶問題原變量x1,x2對偶剩余變量y4,y5原松弛變量x3,x4,x5對偶變量y1,y2,y3例對比兩個(gè)互為對偶問題間的互補(bǔ)基解。序號原問題P目標(biāo)函數(shù)值對偶問題Dx1x2x3x4x5基可行解？y1y2y3y4y5基可行解？143-200×1701/23/500√233040√15*101/500√(15)342005√143/2-1/4000×4404015√801/200-3×5600-815×121000-1×6036160√9003/5-20×706016-15×183/20010√800121615√0000-2-3×利用一對互補(bǔ)的基解，判定目標(biāo)函數(shù)的大?。耗繕?biāo)函數(shù)值原問題P可行解非可行解對偶問題D可行解最優(yōu)zmaxz＞zmax非可行解z＜zmax不確定小結(jié)

利用對偶問題的基本性質(zhì)確定最優(yōu)解的方法：性質(zhì)2（最優(yōu)性）一對使目標(biāo)函數(shù)相等的可行解為最優(yōu)解。性質(zhì)4（強(qiáng)對偶性）最終表中原問題的最優(yōu)解在第三列，對偶問題的最優(yōu)解是松弛變量的檢驗(yàn)數(shù)的相反數(shù)。性質(zhì)5（互補(bǔ)松弛性）性質(zhì)6（互補(bǔ)的基解）一對可行的互補(bǔ)基解為最優(yōu)解。例判斷下列說法是否正確：（1）若線性規(guī)劃的原問題有可行解，則對偶問題一定有可行解。（2）若線性規(guī)劃的對偶問題無可行解，則原問題一定無可行解。（3）在互為對偶的一對原問題和對偶問題中，不管原問題是求極大還是求極小，原問題可行解的目標(biāo)函數(shù)值一定不超過對偶問題可行解的目標(biāo)函數(shù)值。（4）任何線性規(guī)劃問題都有唯一的對偶問題（×）（×）（×）（√）1、定義對于一對互補(bǔ)的基解，總滿足§2.4影子價(jià)格其中，bi是線性規(guī)劃原問題約束條件的右端項(xiàng)，表示第i種資源的擁有量；對偶變量yi表示對一個(gè)單位的第i種資源在生產(chǎn)中做出貢獻(xiàn)的估價(jià)，稱為第i種資源的影子價(jià)格（shadowprice）.注意：影子價(jià)格不是資源的市場價(jià)格。2、性質(zhì)（1）資源的市場價(jià)格隨市場供求變化，通常是穩(wěn)定的；影子價(jià)格隨資源的利用情況變化，通常是不穩(wěn)定的。（2）影子價(jià)格是一種邊際價(jià)格。例已知PQ(4,2)x1x24x1=164x2=12x1+2x2=944083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=14x1+2x2=84x1=174x2=13當(dāng)b1變化1個(gè)單位時(shí)，z增加1.5，對應(yīng)y1=1.5；當(dāng)b2變化1個(gè)單位時(shí)，z增加0.125，對應(yīng)y2=0.125；當(dāng)b3變化1個(gè)單位時(shí)，z無變化，對應(yīng)y3=0.P和D的最優(yōu)解分別為：（3）影子價(jià)格是一種機(jī)會(huì)成本。

假設(shè)第i種資源的單位市場價(jià)格為mi

，影子價(jià)格為yi

。當(dāng)yi>mi

時(shí)，企業(yè)愿意購進(jìn)這種資源，單位純利為yi－mi，即有利可圖；當(dāng)yi<mi

時(shí)，企業(yè)愿意有償轉(zhuǎn)讓這種資源，可獲單位純利為mi－yi，否則企業(yè)無利可圖，甚至虧損；當(dāng)yi=mi

時(shí)，處于平衡狀態(tài)。（4）互補(bǔ)松弛性在最優(yōu)配置下，若資源bi未充分利用，則影子價(jià)格yi為0；若影子價(jià)格yi大于0，則該資源bi已經(jīng)利用完。（5）檢驗(yàn)數(shù)的經(jīng)濟(jì)意義

其中，cj代表第j種產(chǎn)品的產(chǎn)值；是生產(chǎn)一個(gè)單位該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和，稱為產(chǎn)品的隱含成本。當(dāng)該項(xiàng)產(chǎn)品的產(chǎn)值大于隱含成本時(shí)，表示生產(chǎn)該產(chǎn)品有利，可在計(jì)劃中安排；否則不在計(jì)劃中安排。

（2）使管理者了解花多大代價(jià)買進(jìn)資源或賣出資源是合適的3、影子價(jià)格的意義（1）使管理者掌握增加何種資源對企業(yè)更有利（3）為新產(chǎn)品定價(jià)提供依據(jù)（4）使有限資源發(fā)揮更大的經(jīng)濟(jì)效益§2.6靈敏度分析1．概念廣義：對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。狹義：在線性規(guī)劃問題中，分析一個(gè)或多個(gè)參數(shù)發(fā)生變化時(shí)，最優(yōu)解將如何改變；或者分析參數(shù)在一個(gè)怎樣的范圍內(nèi)變化時(shí)，最優(yōu)解不變。其中可以改變的參數(shù)有：cj——目標(biāo)函數(shù)系數(shù)的變化，即市場條件的改變；

bi——約束右端項(xiàng)的變化，即資源擁有量的改變；Pj——約束左端系數(shù)的變化，即工藝技術(shù)條件的改變。其他的變化例如：增加一種新產(chǎn)品、增加一道新工序等。2．步驟

（1）cj的變化：直接反映到最終表中，重新計(jì)算檢驗(yàn)數(shù)。（2）bi的變化：（b+△b）′=B-1

（b+△b）=B-1b+B-1△b=b′+（△b)′(△b)′=B-1△b（3）Pj的變化：

（Pj+△Pj

）′=B-1

（Pj+△Pj

）=B-1

Pj+B-1△Pj=Pj′+(△Pj)′

(△Pj)′=B-1△Pj（4）增加新產(chǎn)品：即增加一個(gè)決策變量，仿照Pj變化。（5）增加新工序：即增加一個(gè)約束條件，直接反映到最終表中。第一步利用最終單純形表將變化后的結(jié)果按下述基本原則修改最終表。第二步在最終表中分別檢查原問題和對偶問題是否為可行解。若第三列沒有負(fù)數(shù)，則原問題的基解是可行解；若檢驗(yàn)數(shù)沒有正數(shù)，則對偶問題的基解是可行解。第三步按下表所列情況進(jìn)行：原問題對偶問題結(jié)論或繼續(xù)可行解可行解仍為最優(yōu)解可行解非可行解用單純形法繼續(xù)非可行解可行解用對偶單純形法繼續(xù)(略)非可行解非可行解引入人工變量，用單純形法繼續(xù)（略）6-1分析cj的變化范圍

例已知線性規(guī)劃問題如下，試分析λ1和λ2分別在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。解：當(dāng)λ1=λ2=0時(shí)，上述線性規(guī)劃問題的最終表為：Cj23000CBXBbX1X2X3X4X52X10X43X234310?0-1/500-214/501001/5

00-10-1/5當(dāng)λ2=0時(shí)，將λ1反映到最終表得到Cj

2+λ13000CBXBbX1X2X3X4X52+λ1

X10X43X234310?0-1/500-214/501001/5

00-1-?λ10-1/5+1/5λ1

為使表中解為最優(yōu)解，條件是即當(dāng)時(shí)，滿足要求。當(dāng)λ1=0時(shí)，將λ2反映到最終表得到Cj

23+λ2000CBXBbX1X2X3X4X52

X10X43+λ2

X234310?0-1/500-214/501001/5

00-10-1/5-1/5λ2

為使表中解為最優(yōu)解，條件是即當(dāng)時(shí)，滿足要求。綜上所述，為使最優(yōu)解不變必須滿足：6-2分析bi的變化范圍

例已知線性規(guī)劃問題如下，試分析λ1，λ2和λ3分別在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變。Cj23000CBXBbX1X2X3X4X52X10X43X234310?0-1/500-214/501001/5

00-10-1/5解：當(dāng)λ1=λ2=λ3=0時(shí)，上述線性規(guī)劃問題的最終表為：（1）分析λ1的影響由公式使問題的最優(yōu)基不變的條件是：解得：（2）分析λ2的影響由公式使問題的最優(yōu)基不變的條件是：解得：（3）分析λ3的影響由公式使問題的最優(yōu)基不變的條件是：解得：終上所述，使問題的最優(yōu)基不變的條件是：6-3增加一個(gè)變量的分析例已知線性規(guī)劃問題如下，若增加一個(gè)變量x6，而且試分析問題最優(yōu)解的變化。Cj23000CBXBbX1X2X3X4X52X10X43X2