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

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

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

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

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

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

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

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

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

第二章：對偶問題（1）

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

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

原問題

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

St.資源約束

市場約束

模型：Maxc·x

St.Ax≤b

x≥0

第二章：對偶問題（1）第二章：對偶問題（1）

原問題對偶問題

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

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

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

即YA>=C,已知Y可行，W=Yb＝CBB-1b性質(zhì)4的證明：求證設(shè)X*是原問題的可行解，Y*是對偶問題的可行解，當(dāng)CX*=Y*b時X*，Y*是最優(yōu)解證明：如果CX*=Y*b，根據(jù)性質(zhì)2，對偶所有可行解Y，都有Yb>=CX*=Y*b所以Y*是使目標(biāo)值最小的可行解，因此Y*是最優(yōu)解同理，X*是最優(yōu)解第二章：對偶問題（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的證明：求證:.互補松弛性若X*.Y*分別是原問題和對偶問題的可行解，那么Y*Xs=0和YsX*=0，當(dāng)且僅當(dāng)X*.Y*為最優(yōu)解。證明：MaxZ=CXAX+Xs=bX,Xs≥0對偶：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第二章：對偶問題（1）性質(zhì)7的證明：求證:設(shè)原問題是MaxZ=CXAX+Xs=bX,Xs≥0其對偶問題為Minw=YbYA--Ys=CY,Ys≥0則原問題單純形表的松弛變量的檢驗數(shù)對應(yīng)對偶問題的一個解證明：MaxZ=CX非基變量的檢驗數(shù):

AX+Xs=bBXB+

NXN+XS=bX,Xs≥0對偶：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注意非基變量的檢驗數(shù)和松弛變量的檢驗數(shù)，松弛變量XS的檢驗數(shù)-CBB-1對應(yīng)對偶問題的一個解CBB-1

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

檢驗數(shù)

CN-CBB-1N

對偶單純形法

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

XBXNB-1b存在負(fù)數(shù)非正第二章：對偶問題（1）XBXNB-1b先定行：負(fù)中取小再定列：正中取小例：試用對偶單純形法求解線性規(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第二章：對偶問題（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

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

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

第二章：對偶問題（1）第二章：對偶問題（1）毛羽同學(xué)談影子價格

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

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

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

工廠

ABCDE

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

第二章：對偶問題（1）毛羽同學(xué)談影子價格有100萬的外匯用于投資，進口設(shè)備，擴大生產(chǎn)能力。已知甲工廠設(shè)備每臺價格為2萬美元，乙工廠設(shè)備每臺價格為1美元，問題是企業(yè)到底該如何投資，才能使以后增加的外匯收入最大？其實，如果用影子價格來思考，這問題也就沒那么復(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)初始單純形表為

第二章：對偶問題（1）毛羽同學(xué)談影子價格

x1x2x3x4x5x6x7

x64915107103600x71115403012400Z-12-20-45-40-1800

第二章：對偶問題（1）毛羽同學(xué)談影子價格

x1x2x3x4x5x6x7

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

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

約束≥≤ =

變量≥≤自由

變量≥≤自由

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

可這樣來理解：1．

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

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

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

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

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

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

原問題對偶問題

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

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

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

檢驗數(shù)

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

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

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

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

第二章：對偶問題（2）對偶性質(zhì)的應(yīng)用二例：例2：用對偶理論求解原問題的最優(yōu)解(p60)MinZ=2X1+3X2+5X3+2X4+3X5X1+X2+2X3+X4+3X5>=42X1-X2+3X3+X4+X5>=3X1X2X3X4X5>=0已知對偶最優(yōu)解為：Y1＝4/5，Y2＝3/5，Z=5思路：利用互補松弛性可以得到許多已知方程組-------------------------互補松弛性：若X*.Y*分別是原問題和對偶問題的可行解，那么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

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

=（Y1，Y2）第二章：對偶問題（2）思路：利用互補松弛性可以得到許多已知方程組-------------------------互補松弛性：若X*.Y*分別是原問題和對偶問題的可行解，那么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第二章：對偶問題（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由互補松弛YsX*=0：Y3X1+Y4X2+Y5X3+Y6X4+Y7X5=0得X2＝X3＝

X4＝0代入原來問題得：X1+3X5=42X1+X5=3求解得：X1=1，X5=1用對偶理論求解原問題的最優(yōu)解：X=（1，0，0，0，1）Z=5第二章：對偶問題（2）原問題Max對偶問題Min決策變量變量數(shù)目n(產(chǎn)品種類數(shù))約束條件約束數(shù)目n（每種產(chǎn)品利潤約束）>=0>=0<=0<=0無約束＝約束條件約束數(shù)目m（資源約束）決策變量變量數(shù)目m（每種資源價格）<=0>=0>=0<=0＝無約束系數(shù)對應(yīng)CX系數(shù)對應(yīng)YbAX?bYA?CX正負(fù)？Y正負(fù)？寫出線性規(guī)劃的對偶問題（P57）運籌學(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)濟影響幾何影響單純形表的影響靈敏度分析

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

實際中A.b.C可能為估計值、預(yù)測值

利潤C變化資源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)表還要用對偶單純形法，繼續(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è)備臺時影子價格1.5元,原問題松弛變量的檢驗數(shù)如果這時從別處調(diào)4臺時，問最優(yōu)計劃如何改變？b=(4,0,0)T最優(yōu)基B=初始表中的（P1，P5，P2）B-1

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

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

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

b=00.25O-20.510.5-0.1250400從別處調(diào)4臺時,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ù)，因此：對偶單純形方法：先定行負(fù)取小松弛變量X3=2,設(shè)備還有2臺時沒有利用：實際只需求增加2臺時與原最優(yōu)表相同第二章：靈敏度分析（1）B-1

b

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

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

=B-1

b+B-1

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