第2章線性規(guī)劃的對偶理論

第2章

線性規(guī)劃的對偶理論2.1

線性規(guī)劃的對偶模型

DualModelofLP2.2對偶性質(zhì)

Dualproperty

2.3

對偶單純形法

DualSimplexMethod2.4靈敏度與參數(shù)分析

SensitivityandParametricAnalysis12.1線性規(guī)劃的對偶模型某工廠生產(chǎn)A，B兩種產(chǎn)品，已知制造A產(chǎn)品每件需勞動力7人，原料5公斤，電力2度。制造B產(chǎn)品每件需勞動力5人，原料8公斤，電力5度，工廠可使用的勞動力最多為3500人，原料最多為4000公斤，電力最多為2000度，A產(chǎn)品每件利潤6元，B產(chǎn)品每件利潤7元，問如何安排生產(chǎn)，才使工廠的利潤最大？2ⅠⅡ勞動力753500原材料584000電力252000單位產(chǎn)品的利潤（元）673線性規(guī)劃的對偶問題的例子設(shè)x1,x2分別是A，B產(chǎn)品的生產(chǎn)量，則：勞動力約束原料約束電力約束現(xiàn)在從另一個角度來考慮企業(yè)的決策問題。假如企業(yè)不考慮自己生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源標(biāo)價出售，

問題：決策者應(yīng)怎樣給定資源一個合理的價格？4設(shè)購買該廠的資源(勞動力，原料，電力)的單位價格分別為y1,y2,y3,則有生產(chǎn)1個單位的A產(chǎn)品的資源出售給公司應(yīng)大于其利潤生產(chǎn)1個單位的B產(chǎn)品的資源出售給公司應(yīng)大于其利潤線性規(guī)劃的對偶問題5線性規(guī)劃的對偶問題兩個問題的線性規(guī)劃如下：兩個線性規(guī)劃之間的關(guān)系？6兩個線性規(guī)劃的特點約束條件的右端是另一個規(guī)劃的目標(biāo)函數(shù)的系數(shù)約束條件的系數(shù)矩陣的轉(zhuǎn)置是另一個規(guī)劃的約束條件的系數(shù)矩陣這兩個線性規(guī)劃具有對稱性。7線性規(guī)劃的對偶問題稱(LP)和(LD)是一對相互對偶的線性規(guī)劃問題目標(biāo)函數(shù)求最小，約束條件寫成大于等于；目標(biāo)函數(shù)求最大，約束條件寫成小于等于。8線性規(guī)劃問題(2.2)就是原線性規(guī)劃問題(2.1)的對偶線性規(guī)劃問題，反之，(2.2)的對偶問題就是(2.1)．原問題與對偶問題有如下關(guān)系(假設(shè)原問題(2.1))：(1)原問題求最大，對偶問題是求最小(2)原問題的約束個數(shù)(不含非負(fù)約束)等于對偶變量的個數(shù)(3)原問題的目標(biāo)函數(shù)系數(shù)對應(yīng)于對偶問題的右端項(4)原問題的右端項對應(yīng)于對偶問題的目標(biāo)函數(shù)系數(shù)(5)原問題的約束矩陣轉(zhuǎn)置就是對偶問題系數(shù)矩陣(6)原問題不等式約束符號為“≤”,對偶問題不等式約束符號為“≥”9例2.1寫出下列線性規(guī)劃的對偶問題【解】設(shè)Y=(y1，y2)，則有10線性規(guī)劃問題的規(guī)范形式(CanonicalForm或叫對稱形式)：定義：

目標(biāo)函數(shù)求極大值時，所有約束條件為≤號，變量非負(fù)；

目標(biāo)函數(shù)求極小值時，所有約束條件為≥號，變量非負(fù)。

注：(1)線性規(guī)劃規(guī)范形式與標(biāo)準(zhǔn)型是兩種不同形式，但可以相互轉(zhuǎn)換。(2)規(guī)范形式的線性規(guī)劃問題的對偶仍然是規(guī)范形式．11問題：討論一般形式的線性規(guī)劃問題的對偶問題？方法：先將其轉(zhuǎn)化為規(guī)范形式的線性規(guī)劃問題，然后寫出其對偶問題，適當(dāng)將其進行化簡。122.2對偶性質(zhì)Dualproperty

13設(shè)原問題是(記為LP)：對偶問題是(記為LD)：2.2.1對偶性質(zhì)這里A是m×n矩陣,X是n×1列向量。【性質(zhì)1】弱對偶性:

設(shè)X*、Y*分別為LP(max)與

LD(min)的可行解，則14由這個性質(zhì)可得到下面幾個結(jié)論：

(LP)的任一可行解的目標(biāo)值是(LD)的最優(yōu)值下界；(LD)的任一可行解的目標(biāo)值是(LP)的最優(yōu)值的上界；

(2)在互為對偶的兩個問題中，若一個問題可行且具有無界解，則另一個問題無可行解；

(3)若原問題可行且另一個問題不可行，則原問題具有無界解。

注意:

上述結(jié)論(2)及(3)的條件不能少。一個問題無可行解時，另一個問題可能有可行解(此時具有無界解)也可能無可行解。15例如：無可行解，而對偶問題有可行解，由結(jié)論(3)知必有無界解。16【性質(zhì)3】無界性:如果原問題(對偶問題)具有無界解,則對偶問題(原問題)無可行解?！拘再|(zhì)2】最優(yōu)性:

設(shè)X*與Y*分別是(LP)與(LD)的可行解，則X*、Y*是(LP)與(LD)的最優(yōu)解當(dāng)且僅當(dāng)CX*=Y*b.17【性質(zhì)4】強對偶性：若互為對偶的兩個問題其中一個有最優(yōu)解，則另一個也有最優(yōu)解，且最優(yōu)值相同。另一結(jié)論：若(LP)與(LD)都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解?！拘再|(zhì)5】互補松弛性:在線性規(guī)劃的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。即18根據(jù)對偶性質(zhì)；可將原問題與對偶問題解的對應(yīng)關(guān)系列表如下：一個問題max另一個問題min有最優(yōu)解有最優(yōu)解性質(zhì)4無無最優(yōu)解無最優(yōu)解性質(zhì)4最優(yōu)無界解(有可行解)無可行解性質(zhì)2解無可行解無界解(有可行解)19影子價格在單純形法的每步迭代中，目標(biāo)函數(shù)都取式中：bi是線形規(guī)劃原問題約束條件的右端項，它代表第i種資源的擁有量。對偶變量yi的意義代表對一個單位第i種資源的估價。影子價格指的是根據(jù)資源在生產(chǎn)中做出的貢獻的估價，而不是資源的市場價格。20影子價格是一種邊界價格說明yi的值相當(dāng)于在給定的生產(chǎn)條件下，bi每增加一個單位時目標(biāo)函數(shù)z的增量。21從圖中可看到，設(shè)備增加一臺時，代表該約束條件的直線由①移至①′，相應(yīng)的最優(yōu)解由(4，2)變?yōu)?4，2.5)，目標(biāo)函數(shù)z=2×4+3×2.5=15.5，即比原來的增大1.5。又若原材料A增加1kg時，代表該約束方程的直線由②移至②′，相應(yīng)的最優(yōu)解從(4，2)變?yōu)?4.25，1.875)，目標(biāo)函數(shù)z=２×4.25+3×1.875=14.125。比原來的增加0.125。原材料B增加1kg時，該約束方程的直線由③移至③′，這時的最優(yōu)解不變。22——代表第j種產(chǎn)品的產(chǎn)值影子價格的經(jīng)濟意義——是生產(chǎn)一個單位產(chǎn)品所消耗的各項資源的影子價格的總和，即產(chǎn)品的隱含成本。23影子價格(Shadowprice)取決于企業(yè)對資源使用的狀況，受生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)差異、管理效率等因素影響。邊際利潤的概念：增加單位資源對利潤的貢獻。對資源使用決策的參考依據(jù)：買進、賣出制定內(nèi)部結(jié)算價格的參考242.3對偶單純形法由于單純表中同時反映原問題與對偶問題的最優(yōu)解，故可以從求對偶問題最優(yōu)解角度求解LP模型。例：minz=2x1+3x2maxz'=-2x1-3x2+0x3+0x4 s.tx1+x23標(biāo)準(zhǔn)化s.tx1+x2-x3=3 x1+2x24 x1+2x2-x4=4 x10,x20 xj0,(j=1,2,3,4)maxz'=-2x1-3x2+0x3+0x4

s.t-x1-x2+x3=-3 -x1-2x2+x4=-4 xj0,(j=1,2,3,4)25Cj→x1x2x3x4XBbCB-1 -1 1 0-1 -2 01-2 -3 0 0-3-4x3x400cj-zj-2-300-1/2 0 1 -1/21/2 1 0-1/2x3x2-12cj-zj-1/2 00-3/20-31 0 -2 10 1 1-1x1x221cj-zj0 0 -1 -1-2-3列單純表計算：26對偶單純形法步驟：1.列初始單純形表，使得所有檢驗數(shù)j0；2.出基變量：取min{bi<0

}=bl

→x(l) 3.入基變量：min{——|alk<0}=→xk 4.主元素：[alk]5.迭代：同單純形法，新單純表中pk化為單位向量cj-zjalj說明：10使用對偶單純形法時，初始表中檢驗數(shù)必須全部為j0，即使得其對偶問題為可行解，20為便于說明，這里采取從原問題角度敘述迭代步驟。27本例如果用單純形法計算，確定初始基可行解時需引入兩個人工變量，計算量要多于對偶單純形法。一般情況下，如果問題能夠用對偶單純形法計算，計算量會少于單純形法。但是，對偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線性規(guī)劃問題都能用對偶單純形法計算的。當(dāng)線性規(guī)劃問題具備下面條件時，可以用對偶單純形法求解：

①問題標(biāo)準(zhǔn)化后，價值系數(shù)全非正；

②所有約束全是不等式。282.4靈敏度分析1．靈敏度分析的概念：當(dāng)某一個參數(shù)發(fā)生變化后，引起最優(yōu)解如何改變的分析。可以改變的參數(shù)有： bi——約束右端項的變化，通常稱資源的改變；

cj——目標(biāo)函數(shù)系數(shù)的變化，通常稱市場條件的變化；

pj

——約束條件系數(shù)的變化，通常稱工藝系數(shù)的變化；其他的變化有：增加一種新產(chǎn)品、增加一道新的工序等。29302．分析原理：借助最終單純形表將變化后的結(jié)果按下述基本原則反映到最終表里去。（1）bi變化：（b+△b）′=B-1（b+△b） =B-1b+B-1

△b=b′+B-1

△b（2）pj變化：（pj+△pj

）′=B-1（pj+△pj

） =B-1pj+B-1

△pj

=pj

′+B-1

△pj

（3）cj變化：直接反映到最終表中，計算檢驗數(shù)。（4）增加一個約束方程：直接反映到最終表中。（5）增加新產(chǎn)品：仿照pj變化。313．計算示例：maxz=2x1+3x2s.t2x1+2x2

12

x1+2x28

4x1

164x212x10,x20例：已知某線性規(guī)劃模型及最終的單純表如下：問：（1）若b2增加8個單位，最優(yōu)解如何變化？（2）若c2還可增加2個單位，最優(yōu)解如何改變？（3）若引進一個新變量（產(chǎn)品）y，其目標(biāo)函數(shù)系數(shù)為cy=5，系數(shù)列向量為py=[3263]，問最優(yōu)解是否會改變？

cj—230000

CBXBbx1x2x3x4x5x60x302x140x643x22001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-1.5-0.125032解：（1）（b+△b）′=B-1b+B-1

△b=b′+B-1

△b =0442T

+-80-164T=-84-126TB-1△b=1-1-0.250000.2500-20.5100.5-0.12500800=-80-164利用對偶單純形法繼續(xù)求最優(yōu)解。（2）當(dāng)cj變化時，′=C′－CB′B-1

A，列出單純形表，重新求出檢驗數(shù)，如表中所示：（3）增加y時，y=cy-CB

B-1

py=5-(01.50.1250)[3263]T =1.25>0選擇y作入基變量，py′=B-1

py==-0.51.520.25T繼續(xù)迭代：33

cj—230000

CBXBbx1x2x3x4x5x60x3-82x140x6-123x26001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-1.5-0.12500x3-22x140x463x230010-0.5-0.510000.2500001-0.25-0.5010000.25cj－zj0000-0.5-0.750x542x130x673x2300-2011100.500-0.2500-0.510-0.25010000.25cj－zj00-100-0.25返回右端項變化分析單純形表：34

cj—250000

CBXBbx1x2x3x4x5x60x302x140x645x22001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-2.50.12500x322x120x585x23001-200.510010-0.5000-412010000.25cj－zj000-20-0.25返回Cj變化分析單純形表：35

cj—230000

5

CBXBbx1x2x3x4x5x6