第二章對(duì)偶問題(運(yùn)籌學(xué)重慶大學(xué),熊中楷)

運(yùn)籌學(xué)對(duì)偶問題（1）復(fù)習(xí)典型引例：某工廠在計(jì)劃期內(nèi)安排甲，乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所消耗資源以及產(chǎn)生的利潤如下表：

甲產(chǎn)品乙產(chǎn)品資源量設(shè)備128臺(tái)時(shí)原材料A4016公斤原材料B0412公斤產(chǎn)生的利潤2元3元

第二章：對(duì)偶問題（1）Questions:ifsomeonewanttobuytheResourceb,whatisthereasonablepriceForbothofthem?(buyerandsupplier)第二章：對(duì)偶問題（1）另一個(gè)相關(guān)問題的提出：有人想把企業(yè)的資源租用，他應(yīng)該出價(jià)多少??原問題對(duì)偶問題生產(chǎn)者追求利潤最大租用者希望租金最小St.資源約束St.租金不小于利潤市場(chǎng)約束Max2X1+3X2Min8Y1+16Y2+12Y3

X1+2X2<=8Y1+4Y2>=24X1<=162Y1+4Y3>=34X2<=12Y1,Y2,Y3>=0X1>=0

X2>=0第二章：對(duì)偶問題（1）對(duì)偶引例：

單位產(chǎn)品產(chǎn)品消耗資源資源產(chǎn)品1產(chǎn)品2資源約束對(duì)偶決策變量資源定價(jià)設(shè)備原料A原料1y2y3單位產(chǎn)品利潤2元3元原問題決策變量各產(chǎn)品產(chǎn)量x1x2第二章：對(duì)偶問題（1）Chapter2:dualproblem(1)Aexampleofdualproblem(economicinterpretation)FactoryBmustsetapricefortheresourcesownedbyFactoryA.FactoryBwanttopaylessmoneytogettheseresources,butalsoneedensuretheprofitofFactoryA.Property1ofduality:thedualityofdualproblemisprimalproblem.Property2ofduality:weakduality.Property3ofduality:thedualisunbounded.Property4ofduality:thefeasiblesolutionistheoptimal.

對(duì)偶問題的引例（經(jīng)濟(jì)含意）乙方為購買甲方資源而給甲方資源定價(jià)，一方面乙方希望少付錢，又要保證甲方利益

對(duì)偶性質(zhì)1：對(duì)偶的對(duì)偶問題是原問題對(duì)偶性質(zhì)2：弱對(duì)偶性對(duì)偶性質(zhì)3：無界性對(duì)偶性質(zhì)4：可行解是最優(yōu)解性質(zhì)

第二章：對(duì)偶問題（1）

對(duì)偶問題租用者希望租金最小St.租金不小于利潤

模型：Miny·bSt.YA≥cy≥0對(duì)偶問題的提出：

原問題

生產(chǎn)者追求利潤最大

St.資源約束

市場(chǎng)約束

模型：Maxc·x

St.Ax≤b

x≥0

第二章：對(duì)偶問題（1）第二章：對(duì)偶問題（1）

原問題對(duì)偶問題

MaxZ=CXAX<=bX≥0Minw=YbYA≥CY≥0經(jīng)濟(jì)意義A，X，b，C,CX,AXY,Yb,YA標(biāo)準(zhǔn)化松弛變量Xs剩余變量YsMaxZ=CXAX+Xs=bX,Xs≥0Minw=YbYA--Ys=CY,Ys≥0第二章：對(duì)偶問題（1）七個(gè)性質(zhì)

1.對(duì)稱性對(duì)偶問題的對(duì)偶是原問題。2.弱對(duì)偶性若X是原問題的可行解，Y是對(duì)偶問題的可行解，則存在CX≤Yb3.無界性若原問題無界解，則其對(duì)偶問題無可行解。4.設(shè)X*是原問題的可行解，Y*是對(duì)偶問題的可行解，當(dāng)CX*=Y*b時(shí)X*，Y*是最優(yōu)解5.對(duì)偶定理若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。6.互補(bǔ)松弛性若X*.Y*分別是原問題和對(duì)偶問題的可行解，那么Y*Xs=0和YsX*=0，當(dāng)且僅當(dāng)X*.Y*為最優(yōu)解。7.設(shè)原問題是MaxZ=CXAX+Xs=bX,Xs≥0其對(duì)偶問題為Minw=YbYA--Ys=CY,Ys≥0則原問題單純形表的松弛變量的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)解性質(zhì)2的證明：求證:弱對(duì)偶性若X是原問題的可行解，Y是對(duì)偶問題的可行解，則存在CX≤Yb證明：因?yàn)镃≤YA,所以CX≤YAX因?yàn)锳X≤b，所以YAX≤Yb，即CX≤YAX≤Yb性質(zhì)1的證明：求證:對(duì)稱性對(duì)偶問題的對(duì)偶是原問題。證明：原問題：MaxCX，AX≤b，X≥0

對(duì)偶：MinYb，YA≥C，Y≥0即Max-Yb，-YA≤-C，Y≥0對(duì)偶問題的對(duì)偶：Min-CX，-AX≥-b，X≥0即:原問題第二章：對(duì)偶問題（1）性質(zhì)3的證明：求證:無界性若原問題無界解，則其對(duì)偶問題無可行解。證明：若原問題無界解，存在X，CX≥M（M任意大）由性質(zhì)2任意的Y，M≤Yb性質(zhì)5的證明：求證對(duì)偶定理若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。證明：設(shè)X*是原問題最優(yōu)解，B是最優(yōu)基，Z=CX=CBXB＋CNXN=CBB-1b最優(yōu)表中檢驗(yàn)數(shù)=C-CBB-1A=C-YA<＝0這里令：Y＝CBB-1

即YA>=C,已知Y可行，W=Yb＝CBB-1b性質(zhì)4的證明：求證設(shè)X*是原問題的可行解，Y*是對(duì)偶問題的可行解，當(dāng)CX*=Y*b時(shí)X*，Y*是最優(yōu)解證明：如果CX*=Y*b，根據(jù)性質(zhì)2，對(duì)偶所有可行解Y，都有Yb>=CX*=Y*b所以Y*是使目標(biāo)值最小的可行解，因此Y*是最優(yōu)解同理，X*是最優(yōu)解第二章：對(duì)偶問題（1）AX=bBXB+NXN=bXB=B-1b-B-1NXNZ=CX=CBXB+CNXN

=CB(B-1b-B-1NXN)

+CNXN=CBB-1b+(CN-CBB-1N)XN＋0XB性質(zhì)6的證明：求證:.互補(bǔ)松弛性若X*.Y*分別是原問題和對(duì)偶問題的可行解，那么Y*Xs=0和YsX*=0，當(dāng)且僅當(dāng)X*.Y*為最優(yōu)解。證明：MaxZ=CXAX+Xs=bX,Xs≥0對(duì)偶：Minw=YbYA--Ys=CY,Ys≥0Z=CX＝（YA--Ys）X＝Y(jié)AX--YsXw=Yb＝Y(jié)(AX+Xs)=YAX+YXs如果Y*Xs=0和YsX*=0那么CX＝Y(jié)b，性質(zhì)4,X*.Y*為最優(yōu)解如果X*,Y*為最優(yōu)解，性質(zhì)4：CX＝Y(jié)b，Y*Xs+YsX*=0那么Y*Xs=0和YsX*=0第二章：對(duì)偶問題（1）性質(zhì)7的證明：求證:設(shè)原問題是MaxZ=CXAX+Xs=bX,Xs≥0其對(duì)偶問題為Minw=YbYA--Ys=CY,Ys≥0則原問題單純形表的松弛變量的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)解證明：MaxZ=CX非基變量的檢驗(yàn)數(shù):

AX+Xs=bBXB+

NXN+XS=bX,Xs≥0對(duì)偶：Minw=YbYA--Ys=CY,Ys≥0

XB=B-1b-B-1NXN-B-1XS

代入Z=CX=CBXB+CNXN=CBB-1b-CBB-1NXN-CBB-1XS+CNXN

=CBB-1b+(CN-CBB-1N)XN-CBB-1XS注意非基變量的檢驗(yàn)數(shù)和松弛變量的檢驗(yàn)數(shù)，松弛變量XS的檢驗(yàn)數(shù)-CBB-1對(duì)應(yīng)對(duì)偶問題的一個(gè)解CBB-1

第二章：對(duì)偶問題（1）第二章：對(duì)偶問題（1）對(duì)偶問題的經(jīng)濟(jì)解釋（影子價(jià)格）1.對(duì)偶解的經(jīng)濟(jì)含義?(p61)單位資源的變化引起最優(yōu)值的變化：Z=CBB-1bY=dZ\db＝CBB-12.影子價(jià)格的特點(diǎn)（1）影子價(jià)格是對(duì)系統(tǒng)資源的最優(yōu)估價(jià)，不是真實(shí)價(jià)格（2）對(duì)偶解---影子價(jià)格大小客觀反映了資源在系統(tǒng)內(nèi)部的稀缺程度影子價(jià)格越高，該資源在系統(tǒng)中越稀缺影子價(jià)格為0，該資源在系統(tǒng)中供大于求（3）系統(tǒng)內(nèi)部資源數(shù)量和市場(chǎng)價(jià)格的任何變化都會(huì)引起影子價(jià)格的變化3.影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用若資源的影子價(jià)格高（低）于其市場(chǎng)價(jià)格，則該資源在系統(tǒng)中有（無）獲利能力應(yīng)買入（賣出）該資源第二章：對(duì)偶問題（1）基變量基變量XB非基變量XN松弛變量XS基解B-1b

檢驗(yàn)數(shù)

CN-CBB-1N

對(duì)偶單純形法

Z=CBB-1b+(CN-CBB-1N)XN-CBB-1XS1.對(duì)偶單純形法理論基礎(chǔ)原問題基解-CBB-1松弛變量的檢驗(yàn)數(shù)＝－對(duì)偶解=-Y對(duì)偶單純形法2.對(duì)偶單純形法計(jì)算步驟第一步：先定行，負(fù)中取小第二步：再定列，相除后正中取小

XBXNB-1b存在負(fù)數(shù)非正第二章：對(duì)偶問題（1）XBXNB-1b先定行：負(fù)中取小再定列：正中取小例：試用對(duì)偶單純形法求解線性規(guī)劃問題MinZ=x1+x22x1+x2≥4x1+7x2≥7x1,x2≥0解:變換問題形式為:（沒有人工變量,出現(xiàn)單位矩陣）Max(-z)=-x1-x2-2x1-x2+x3=-4右邊有負(fù)數(shù)-x1-7x2+x4=-7右邊有負(fù)數(shù)x1,x2≥0第二章：對(duì)偶問題（1）

x1x2x3x4

x5-2-110-4x4-1-701-7

-1-100

X1X2X3X4

X3-13/701-1/7-3X21/710-1/71

-6/700-1/71

第二章：對(duì)偶問題（1）對(duì)偶單純形法:先定行，負(fù)中取小再定列，相除后正中取小下一步：轉(zhuǎn)軸元所在列變?yōu)閱挝幌蛄?/p>

X1X2X3

X110-7/131/1321/13X2011/13-2/1310/13

00-6/13-1/13

31/13

最優(yōu)解為x*＝(21/13,10/13,0,0)T(X3X4是松弛變量)Z*=31/13對(duì)偶解Y*＝(6/13,1/13)T只有兩種資源（兩個(gè)約束）W*=31/13第二章：對(duì)偶問題（1）松弛變量檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶解－YX4對(duì)偶單純形法:先定行，負(fù)中取小無法進(jìn)行，表示最優(yōu)解達(dá)到對(duì)偶單純形法3.優(yōu)缺點(diǎn)優(yōu)點(diǎn)（1）初始解可以是非可行解，不需要加入人工變量（2）適合于XB少，XN很多的情況對(duì)偶轉(zhuǎn)換

（3）靈敏度分析，有時(shí)可簡(jiǎn)化分析缺點(diǎn)初始可行基難找XN少XB多XN多XB少第二章：對(duì)偶問題（1）影子價(jià)格的意義（1）影子價(jià)格不是運(yùn)籌學(xué)中的概念，而是經(jīng)濟(jì)學(xué)中的概念。它表示對(duì)某種資源一個(gè)單位的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是該種資源在生產(chǎn)中具體使用時(shí)所體現(xiàn)出來的價(jià)值。它隨使用情況的不同而不同。（2）前面的對(duì)偶問題的性質(zhì)中講到：原問題的剩余變量對(duì)應(yīng)對(duì)偶問題的決策變量。對(duì)偶問題的決策變量就是對(duì)原問題中各種資源一個(gè)單位的估價(jià)。原問題剩余變量在單純形表中的檢驗(yàn)數(shù)的相反數(shù)，就是對(duì)偶問題基本解中決策變量的值。原問題最優(yōu)單純形表中對(duì)應(yīng)的對(duì)偶變量的這些值。就是各種資源影子價(jià)格的數(shù)值。（3）經(jīng)濟(jì)學(xué)中常把數(shù)學(xué)中的導(dǎo)函數(shù)稱為邊際函數(shù)，影子價(jià)格就是導(dǎo)數(shù)值，因此是一種邊際價(jià)格。后面2.6節(jié)靈敏度分析中將要講到，某種資源的擁有量bI在原來數(shù)值左右某個(gè)范圍內(nèi)波動(dòng)時(shí)，原最優(yōu)基將不發(fā)生變化，因此對(duì)偶問題的最優(yōu)解也不變化，恒為Y*=CBB-1，這時(shí)的最大利潤，就有，所以第i種資源的影子價(jià)格實(shí)際就是最大利潤對(duì)該種數(shù)量的變化率。（4）資源的擁有者可以比較資源的影子價(jià)格與市場(chǎng)價(jià)格的大小關(guān)系，以決定買進(jìn)或賣出該種資源。（5）由對(duì)偶問題的互補(bǔ)松弛性可知：在生產(chǎn)過程中如果某種資源的年有量bi未得到充分利用時(shí)，該種資源的影子價(jià)格就是零，而當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)凈盡。

第二章：對(duì)偶問題（1）第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格

毛羽同學(xué)談?dòng)白觾r(jià)格重慶大學(xué)工商管理學(xué)院99金融毛羽運(yùn)籌學(xué)是門非常有用的學(xué)科，在學(xué)習(xí)中，給我印象最深的是關(guān)于影子價(jià)格這一節(jié)內(nèi)容。它在實(shí)際生活的很多地方都找得到原形，因而很有用。在《西方經(jīng)濟(jì)學(xué)》中，曾學(xué)到過機(jī)會(huì)成本與邊際效用，其實(shí)都是影子價(jià)格的擴(kuò)展和延伸。影子價(jià)格刻畫了經(jīng)濟(jì)活動(dòng)中資源變化時(shí)總效益的變化趨勢(shì)，它主要反映資源的使用價(jià)值，反映資源內(nèi)利用對(duì)經(jīng)濟(jì)總效應(yīng)的貢獻(xiàn)程度，并以這種貢獻(xiàn)的大小來度量各資源的價(jià)值。因此，影子價(jià)格無論是在宏觀經(jīng)濟(jì)中還是在微觀經(jīng)濟(jì)中均應(yīng)用很廣泛。影子價(jià)格定量地反映了資源的稀缺程度和供求矛盾，在所研究的經(jīng)濟(jì)結(jié)構(gòu)中，其長線資源的影子價(jià)格為零，稀缺資源的影子價(jià)格大于零，影子價(jià)格越高，表示該資源的稀缺程度越大。這個(gè)定量的信息對(duì)一個(gè)企業(yè)決策者在生產(chǎn)管理中作出正確決策是很重要的。因此，影子價(jià)格不矢為企業(yè)經(jīng)營管理的好方法。`比如：若有個(gè)工廠計(jì)劃用M1,M2,.M3三種原材料生產(chǎn)A、B、C、D四種產(chǎn)品（C、D為新開發(fā)產(chǎn)品）

原料每件產(chǎn)品所需原料（公斤）現(xiàn)有原料數(shù)（公斤）ABCDM1132590M2211380M3113145利潤（元/件）5488

第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格工廠是否決定生產(chǎn)新開發(fā)產(chǎn)品C、D？這就需要用影子價(jià)格來判斷。因?yàn)檫@三種資源的影子價(jià)格分別為每公斤0元、1元、3元。C型產(chǎn)品對(duì)這三種資源的消耗系數(shù)分別為2、1、3。所以C型產(chǎn)品的總影子價(jià)格為：0×2+1×1+3×3=10（元/件）這個(gè)總影子價(jià)格表示從A型、B型產(chǎn)品的生產(chǎn)中抽出資源來生產(chǎn)一件C型產(chǎn)品使總利潤失去10元（機(jī)會(huì)成本）。C型產(chǎn)品每件只能帶來利潤8元，所得小于所失，工廠從經(jīng)濟(jì)利益出發(fā)，為了不使總利潤減少，決定不投產(chǎn)C型產(chǎn)品。如果C型產(chǎn)品對(duì)資源的消耗不變，只有當(dāng)C型產(chǎn)品的單位利潤大于10元時(shí)工廠才可以考慮投產(chǎn)。（此時(shí)調(diào)整生產(chǎn)，需用最優(yōu)化后分析）D型產(chǎn)品的資源消耗系數(shù)分別為5、3、1，這樣，生產(chǎn)一件D型產(chǎn)品的機(jī)會(huì)損失為第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格【例1】判斷下列說法是否正確，為什么？（a）如果線性規(guī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解；（b）如果線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解；（c）在互為對(duì)偶的一對(duì)原問題與對(duì)偶問題中，不管原問題是否極大或極小，原問題可行解的目標(biāo)函數(shù)值都一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值。解（a）不對(duì)。因?yàn)樵瓎栴}有無界解時(shí)（它當(dāng)然有可行解），其對(duì)偶問題無可行解。而若原問題有最優(yōu)解（當(dāng)然也是可行解），則其對(duì)偶問題也有最優(yōu)解（也是可行解）。（b）為（a）的逆否命題，故亦不真。（c）不對(duì)。因?yàn)槟膫€(gè)問題是原問題，哪個(gè)問題是對(duì)偶問題是相對(duì)而言的。僅在、分別為第二章：對(duì)偶問題（1）0×5+1×3+3×1=6（元/件）每件D產(chǎn)品帶來的利潤是8元，所得大于所失，工廠可以決定生產(chǎn)D產(chǎn)品。顯然，影子價(jià)格為新產(chǎn)品是否投產(chǎn)提供了可靠的數(shù)據(jù)分析。影子價(jià)格不僅能為企業(yè)經(jīng)營管理導(dǎo)向，影子價(jià)格作為一種手段，還在投資決策起到不可估量的作用。投資經(jīng)濟(jì)效益評(píng)價(jià)是進(jìn)行投資決策的重要環(huán)節(jié)，而影子價(jià)格是進(jìn)行投資經(jīng)濟(jì)效益評(píng)價(jià)的好方法。比如：有一中外合資企業(yè)，其下有甲、乙兩個(gè)工廠，可生產(chǎn)A、B、C、D、E五種產(chǎn)品，這兩個(gè)工廠的設(shè)備日加工能力、生產(chǎn)各種產(chǎn)品所需要的兩個(gè)工廠設(shè)備的單位加工臺(tái)時(shí)以及每種產(chǎn)品的外匯收入如下表：第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格單位臺(tái)時(shí)產(chǎn)品

工廠

ABCDE

設(shè)備能力（臺(tái)時(shí)/日）甲49151073600乙11151032400單位利潤（美元）1220454018

第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格有100萬的外匯用于投資，進(jìn)口設(shè)備，擴(kuò)大生產(chǎn)能力。已知甲工廠設(shè)備每臺(tái)價(jià)格為2萬美元，乙工廠設(shè)備每臺(tái)價(jià)格為1美元，問題是企業(yè)到底該如何投資，才能使以后增加的外匯收入最大？其實(shí)，如果用影子價(jià)格來思考，這問題也就沒那么復(fù)雜了。此線性規(guī)劃模型為，maxZ=12x1+20x2+45X3+40x4+18x54x1+9x2+15x3+10x4+7x5≤3600x1+x2+15x3+40x4+3x5≤2400xi≥0(i=1,2,3,4,5)初始單純形表為

第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格

x1x2x3x4x5x6x7

x64915107103600x71115403012400Z-12-20-45-40-1800

第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格

x1x2x3x4x5x6x7

x113/7305/34/15-1/15800x40-1/303/1011/30-1/1502/7540Z020/33010/344/154/1511200經(jīng)過幾次換基迭代后，最優(yōu)表為

第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格所以，甲工廠設(shè)備的影子價(jià)格p1=44/15(美元/臺(tái))，乙工廠設(shè)備的影子價(jià)格p2=4/15（美元/臺(tái)）利用外匯100美元可購買甲工廠設(shè)備50臺(tái)或乙工廠設(shè)備100臺(tái)。假設(shè)企業(yè)美臺(tái)設(shè)備每日工作15小時(shí)，則可增加甲工廠設(shè)備能力750臺(tái)時(shí)或乙工廠設(shè)備能力1500臺(tái)時(shí)。利用影子價(jià)格可對(duì)這兩種購買設(shè)備的方案的經(jīng)濟(jì)效益進(jìn)行比較：購買甲工廠每日增加的收入為750×44/15=2200（美元）購買乙工廠每日增加的收入為1500×4/15=400（美元）從上面計(jì)算可以看出，購買甲工廠設(shè)備對(duì)這個(gè)企業(yè)帶來的效益更大。這筆100萬美元的投資用于購買甲工廠設(shè)備約經(jīng)過455天就可以收回，用于購買乙工廠的設(shè)備需過2500天才能收回。第二章：對(duì)偶問題（1）毛羽同學(xué)談?dòng)白觾r(jià)格第二章：對(duì)偶問題（1）易震同學(xué)總結(jié)對(duì)偶極小化問題（min）極大化問題（max）

約束≥≤ =

變量≥≤自由

變量≥≤自由

約束≤≥=易震同學(xué)對(duì)原問題與對(duì)偶問題關(guān)系的一點(diǎn)總結(jié)

可這樣來理解：1．

目標(biāo)函數(shù)系數(shù)對(duì)應(yīng)右端常數(shù)；2．

系數(shù)矩陣互為轉(zhuǎn)置；3．

約束條件與變量對(duì)應(yīng)；4．

若給定LP是極小化問題，則利用上表從左到右對(duì)應(yīng)寫出對(duì)偶；若給定LP是極大化問題，則利用上表從右到左對(duì)應(yīng)寫出對(duì)偶。也可按照下面的方法來做：由小變大，變量與約束異向，約束與變量同向。由大變小，變量與約束同向，約束與變量異向。自由變量與等于號(hào)相對(duì)應(yīng)。這里“變量與約束”中的“變量”指原問題的變量，“約束”指對(duì)偶問題的約束；同理“約束與變量”中的“約束”指原問題的約束，“變量”指對(duì)偶問題的變量。

第二章：對(duì)偶問題（1）易震同學(xué)總結(jié)對(duì)偶易震同學(xué)對(duì)原問題與對(duì)偶問題關(guān)系的一點(diǎn)總結(jié)

第二章：對(duì)偶問題（1）為了你的開卷題目或者為鍛煉自己的思維，你是否也發(fā)表點(diǎn)什么？運(yùn)籌學(xué)對(duì)偶問題（2）第二章：對(duì)偶問題（2）Chapter2:dualproblem(2)Property5:dualtheoremProperty6:complementaryslacknessProperty7:coefficientofcheck-upandbasicfeasiblesolutionofdualityTowexamplesofPropertyaboutduality:Example1:proofthatsomeLPhavenofeasiblesolutionbymeansofdualtheorem.Example2:findthefeasiblesolutionoforiginalLPthroughdualtheorem.第二章：對(duì)偶問題（2）對(duì)偶性質(zhì)5：對(duì)偶定理對(duì)偶性質(zhì)6：互補(bǔ)松弛性對(duì)偶性質(zhì)7：原問題檢驗(yàn)數(shù)與對(duì)偶基解對(duì)偶單純形法：對(duì)偶性質(zhì)的應(yīng)用二例：例1：用對(duì)偶理論證明線性規(guī)劃無解例2:用對(duì)偶理論求原問題的解第二章：對(duì)偶問題（2）

原問題對(duì)偶問題

MaxZ=CXAX<=bX≥0Minw=YbYA≥CY≥0經(jīng)濟(jì)意義A，X，b，C,CX,AXY,Yb,YA標(biāo)準(zhǔn)化松弛變量剩余變量MaxZ=CXAX+Xs=bX,Xs≥0Minw=YbYA--Ys=CY,Ys≥0第二章：對(duì)偶問題（2）

1.對(duì)稱性對(duì)偶問題的對(duì)偶是原問題。2.弱對(duì)偶性若X是原問題的可行解，Y是對(duì)偶問題的可行解，則存在CX≤Yb3.無界性若原問題無界解，則其對(duì)偶問題無可行解。4.設(shè)X*是原問題的可行解，Y*是對(duì)偶問題的可行解，當(dāng)CX*=Y*b時(shí)X*，Y*是最優(yōu)解5.對(duì)偶定理若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。6.互補(bǔ)松弛性若X*.Y*分別是原問題和對(duì)偶問題的可行解，那么Y*Xs=0和YsX*=0，當(dāng)且僅當(dāng)X*.Y*為最優(yōu)解。7.設(shè)原問題是MaxZ=CXAX+Xs=bX,Xs≥0其對(duì)偶問題為Minw=YbYA--Ys=CY,Ys≥0則原問題單存形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)解。

第二章：對(duì)偶問題（2）對(duì)偶問題的經(jīng)濟(jì)解釋（影子價(jià)格）1.對(duì)偶解的經(jīng)濟(jì)含義單位資源的變化引起最優(yōu)值的變化:2.影子價(jià)格的特點(diǎn)（1）影子價(jià)格是對(duì)系統(tǒng)資源的最優(yōu)估價(jià)，不是真實(shí)價(jià)格（2）對(duì)偶解---影子價(jià)格大小客觀反映了資源在系統(tǒng)內(nèi)部的稀缺程度影子價(jià)格越高，該資源在系統(tǒng)中越稀缺影子價(jià)格為0，該資源在系統(tǒng)中供大于求（3）系統(tǒng)內(nèi)部資源數(shù)量和市場(chǎng)價(jià)格的任何變化都會(huì)引起影子價(jià)格的變化3.影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用若資源的影子價(jià)格高（低）于其市場(chǎng)價(jià)格，則該資源在系統(tǒng)中有（無）獲利能力應(yīng)買入（賣出）該資源第二章：對(duì)偶問題（2）基變量基變量XB非基變量XC松弛變量XS基解B-1b

檢驗(yàn)數(shù)

原問題非基變量的檢驗(yàn)數(shù)是CN-CBB-1N

原問題松弛變量的檢驗(yàn)數(shù)是－Y=-CBB-1

單純形表第二章：對(duì)偶問題（2）對(duì)偶性質(zhì)的應(yīng)用二例：例1：用對(duì)偶理論證明線性規(guī)劃無解(p60)MaxZ=X1+X2-X1+X2+X3<=2-2X1+X2-X3<=1X1,X2,X3>=0對(duì)偶:

-Y1–2Y2>=1第1約束矛盾，無解MaxZ=CXAX<=bX≥0Minw=YbYA≥CY≥0A=-111-21-1(Y1,Y2)-111>=1，1，0-21–1思路：利用約束條件的矛盾證明線性規(guī)劃無解

第二章：對(duì)偶問題（2）對(duì)偶性質(zhì)的應(yīng)用二例：例2：用對(duì)偶理論求解原問題的最優(yōu)解(p60)MinZ=2X1+3X2+5X3+2X4+3X5X1+X2+2X3+X4+3X5>=42X1-X2+3X3+X4+X5>=3X1X2X3X4X5>=0已知對(duì)偶最優(yōu)解為：Y1＝4/5，Y2＝3/5，Z=5思路：利用互補(bǔ)松弛性可以得到許多已知方程組-------------------------互補(bǔ)松弛性：若X*.Y*分別是原問題和對(duì)偶問題的可行解，那么Y*Xs=0和YsX*=0，當(dāng)且僅當(dāng)X*.Y*為最優(yōu)解。提問題：X=?XS=?,Y=?YS=?分析：X1+X2+2X3+X4+3X5–X6=42X1-X2+3X3+X4+X5–X7=3Xs=（X6，X7）T

X=（X1，X2，X3，X4，X5

）T

寫出對(duì)偶：A，b,cMaxZ=4Y1+3Y2，Y

=（Y1，Y2）第二章：對(duì)偶問題（2）思路：利用互補(bǔ)松弛性可以得到許多已知方程組-------------------------互補(bǔ)松弛性：若X*.Y*分別是原問題和對(duì)偶問題的可行解，那么Y*Xs=0和YsX*=0，當(dāng)且僅當(dāng)X*.Y*為最優(yōu)解。Ys=（Y3，Y4，Y5，Y6，Y7）Y1+2Y2<=2。。。。。。約束1Y1-Y2<=3。。。。。。約束22Y1+3Y2<=5。。。。。。約束3Y1+Y2<=2。。。。。。約束43Y1+Y2<=3。。。。。。約束5Y1,Y2>=0Y1+2Y2+

Y3=2。。。。約束1Y1-Y2+

Y4=3。。。。約束22Y1+3Y2+

Y5=5。。。。約束3Y1+Y2+

Y6=2。。。。約束43Y1+Y2+

Y7=3。。。。約束5Y1,Y2>=0第二章：對(duì)偶問題（2）Y*Xs=0：Y1X6+Y2X7=0，由于Y1>0,Y2>0，因此X6=0，X7=0將Y1＝4/5，Y2＝3/5代入，約束2，3，4為嚴(yán)格不等式Y(jié)4>0,Y5>0，Y6>0由互補(bǔ)松弛YsX*=0：Y3X1+Y4X2+Y5X3+Y6X4+Y7X5=0得X2＝X3＝

X4＝0代入原來問題得：X1+3X5=42X1+X5=3求解得：X1=1，X5=1用對(duì)偶理論求解原問題的最優(yōu)解：X=（1，0，0，0，1）Z=5第二章：對(duì)偶問題（2）原問題Max對(duì)偶問題Min決策變量變量數(shù)目n(產(chǎn)品種類數(shù))約束條件約束數(shù)目n（每種產(chǎn)品利潤約束）>=0>=0<=0<=0無約束＝約束條件約束數(shù)目m（資源約束）決策變量變量數(shù)目m（每種資源價(jià)格）<=0>=0>=0<=0＝無約束系數(shù)對(duì)應(yīng)CX系數(shù)對(duì)應(yīng)YbAX?bYA?CX正負(fù)？Y正負(fù)？寫出線性規(guī)劃的對(duì)偶問題（P57）運(yùn)籌學(xué)靈敏度分析9.11事件發(fā)生，今年外資企業(yè)招聘數(shù)量明顯減少，深圳華為由去年7000多人變?yōu)榻衲瓴坏?000人，這叫靈敏度分析。一件事情影響另一些事情第二章：靈敏度分析第二章：靈敏度分析Chapter2:sensitivityanalysisContentofsensitivityanalysis:1.

sensitivityanalysiswhencoefficientBofresourcesquantityischanged.2.

sensitivityanalysiswhenprofitparameterCinobjectivefunctionischanged.sensitivityanalysiswhentechniqueparameteraijischanged.

靈敏度分析的內(nèi)容：1．資源數(shù)量b變化的靈敏度分析2．目標(biāo)函數(shù)中利潤系數(shù)C變化的靈敏度分析3．技術(shù)系數(shù)aij變化的靈敏度分析經(jīng)濟(jì)影響幾何影響單純形表的影響靈敏度分析

LP模型中A（單位產(chǎn)品消耗資源）.b（資源）.C（市場(chǎng)價(jià)格）為常數(shù)

實(shí)際中A.b.C可能為估計(jì)值、預(yù)測(cè)值

利潤C(jī)變化資源b變化A變化＝目標(biāo)函數(shù)等值＝可行域改變＝可行域改變線的斜率變化＝影響最優(yōu)解＝影響最優(yōu)解＝影響最優(yōu)解第二章：靈敏度分析第二章：靈敏度分析靈敏度分析

LP模型中b（資源）靈敏度分析資源b變化＝》可行域改變＝》影響單純形表中變化最優(yōu)解：X=B-1

(b+b)如果X=B-1

(b+b)>=0，可行，可解出b的范圍如果X=B-1

(b+b)<=0，不可行，原來的單純形最優(yōu)表還要用對(duì)偶單純形法，繼續(xù)求解。第二章：靈敏度分析例7（p65）第1章例1中原來題目：第二章：靈敏度分析例7（p65）第1章例1中p31最優(yōu)表X1X2X3X4X5X11000.25O4X500-20.514X2010.5-0.1250200-1.5-0.1250-14設(shè)備臺(tái)時(shí)影子價(jià)格1.5元,原問題松弛變量的檢驗(yàn)數(shù)如果這時(shí)從別處調(diào)4臺(tái)時(shí)，問最優(yōu)計(jì)劃如何改變？b=(4,0,0)T最優(yōu)基B=初始表中的（P1，P5，P2）B-1

b第二章：靈敏度分析（1）最優(yōu)表中包含了

B-1因?yàn)槌醯茸儞Q求矩陣的逆：（B，I）（I，B-1）最優(yōu)表中包含了B-1,B-1位置對(duì)應(yīng):初始單純形表中的單位矩陣的位置例7（p65）第1章例1中p31最優(yōu)表X1X2X3X4X5X11000.25O4X500-20.514X2010.5-0.1250200-1.5-0.1250-14B-1

b第二章：靈敏度分析先計(jì)算B-1

b=00.25O-20.510.5-0.1250400從別處調(diào)4臺(tái)時(shí),b0-82

=B-1

b=00.25O-20.510.5-0.125081612442

=第二章：靈敏度分析（1）C23000CBX1X2X3X4X52X11000.25O4+00X500-2轉(zhuǎn)元0.514-83X2010.5-0.12502+200-1.5-0.12502X11000。25040X3001－0.25-0.523X201000。253000-0.5-0.75B-1b+B-1

b負(fù)數(shù)，因此：對(duì)偶單純形方法：先定行負(fù)取小松弛變量X3=2,設(shè)備還有2臺(tái)時(shí)沒有利用：實(shí)際只需求增加2臺(tái)時(shí)與原最優(yōu)表相同第二章：靈敏度分析（1）B-1

b

=00.25O-20.510.5-0.1250b100如果從別處調(diào)b1臺(tái)時(shí),X=B-1

(b+b)>=0，可行，可解出b的范圍0-2b10.5b1

=B-1

b+B-1

b=+≥00-2b10.5b1442資源b變化