運(yùn)籌學(xué)-管理課件西南交通經(jīng)濟(jì)學(xué)院

s西南交通大學(xué)經(jīng)濟(jì)§1單純形法的矩陣maxz

maxzCX0XAXX

引入松弛變X xn1 ,xn

AXIXSbX0,X maxzCBXBCNXN0XBXBNXNIXSXB,XN,XSXBB1bB1NXNB1XZCBB1b(CNCBB1N)XNCBB1X初始非基變初始基變右側(cè)常 0 Ib 00基變非基右側(cè)常 IB-1 B-B-10CN-CBB- -CBB--CBB-

與初等

B1=B- 1 1

B2-

B2-1

Bi-1§2一、對偶問題的面積一定，周長

正方一對對應(yīng)問題表示了一個(gè)問題的兩個(gè)側(cè)面，是對一個(gè)研究對象從兩個(gè)角度提出極值問題，兩類極值問題具有相同的目標(biāo)函數(shù)值。例1某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ,Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時(shí)及A，B兩種原材料的消產(chǎn)品產(chǎn)品資源設(shè)128臺原材料4016原材料0412單件利23解根據(jù)上一章的知識，設(shè)x1，x2maxz=2x1+3x2 x1,例2對例1，假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品Ⅰ，解同理，設(shè) 和出讓單位原材料A，B的附加額思路：出售生產(chǎn)一件產(chǎn)品I的資源的收入應(yīng)不低于生產(chǎn)y1+4y2≥min

maxz=2x1+3x2 y,y,y

x1,約束條件一個(gè)為≤，一個(gè)為定義1.設(shè)有線性規(guī)劃問題maxz=CX式中X=(x1…xn)T，C=(c1…cn)，b=(b1… min 題，式（Ⅰ）稱為原問題。兩者合在一起稱為一對對稱的對原問題與對偶問 zc1x

c2x2 cna11xa21x

a12x2na22xn

b

a1nxa2nxam1x

am2x

a

xnxj j1,2 ,bmn wy1b1y2b2 ym

am1y a11y

a21y

c1am2y a1ny

a2ny

c

amny yi i1,2 cm原問題與對偶問…≤………≥…max等AX=

maxz=CXAX≤AX≤-

UV

minwUAVACU0,V0

令YU

YAY為自由構(gòu)造對偶規(guī)劃的束是不等式，則限制yi0；如果第i個(gè)約束是等式，則。果xj0，則對偶約束為不等式；如果x 問題目標(biāo)函數(shù)為max，則對偶問題為min。例3寫出下述線性規(guī)劃問題的對偶zz2x13x5x3xx1x23x3x52x2x3x4x2x3x6x10,x2,x3x4無符號限 令x' (x' z2x'3 5 x'2x

3 2 x2x3x4x , , 無約 (1、、123 w5y14y26yy12y2y1y33y12yy1y2yy1,y2

y3y3無約二、對偶定max min

YA≥定理1(弱對偶定理)若X和Y分別是（LP)和(LD)的任一可行解，則CX推論1若X為原問題LP的任一可行解，則CX為其對偶問題LD的一個(gè)下界若Y為LD的任一可行解，則Yb為LP的一個(gè)上界推論2若LP有可行解，LD無可行解，則LP無上界；同理，若LD，LP無可行解，則LD無下界推論3若LP有可行解，但其目標(biāo)函數(shù)值無上界，則LD無可行解；同理LD有可行解，但其目標(biāo)函數(shù)值無下界，則LP無可行解推論4若X*與Y*分別是LP與LD的可行解，且CX*=Y*b，則X*與Y*分別是推論5LP與LD同時(shí)有最優(yōu)解的充要條件是：LP與LD同時(shí)有可行解例 ；在都有最優(yōu)解的條件下，若X和U分別為（1）和（2）CXminz1CXAXb

maxz2CUAUb（1）minz1AX

z'1

maxz2CUAUb

z'2

問題1（1）和（2）都有可行解，假設(shè)（1）問題2（1）和（2）都有可行解，假設(shè) （2） 問題3（1）和（2）

X和分別為

CX和（4）也都有可行解，設(shè)Y為（3）和（4）由定理1CXYb和YbCU，因此CXCU例5min x1－x2+2x3≥3x1,x2,x3≥0證：其對偶問題max－y2y1,原問題有可行解，如X=(4,0,0)T3y2≤2第二個(gè)約束兩邊同乘以（-1），得y21，。定理2（最優(yōu)性定理）若原規(guī)劃和對偶規(guī)劃都有可行解，maxCX=min定理3（對偶定理）若（LP）和（LD）中有一個(gè)有最優(yōu)原問有有限最優(yōu)

關(guān) 對偶問有有限最優(yōu)4（互補(bǔ)松弛定理）X*與Y*分別是（LP）與的可行解，則X*和Y*為最優(yōu)解的充要條sYs

等價(jià)于y*x 等價(jià)于y*x

原原問對偶問某個(gè)變對應(yīng)變x*j約束為y*x*j約束為嚴(yán)格不y*約束為嚴(yán)格不x*對應(yīng)變某個(gè)變y*i約束為x*y*i例6對例1，已知其最優(yōu)解為(4,2)T解：首先將（LP）及（LD）化max +xs2 + x1,xs1,xs2,xs3min － － y1,y2,y3≥0ys1,ys2≥0再將(4,2)T代入（LP）的約束，xs1=0,xs2=0,由定理4（互補(bǔ)松弛定理） y

xjx

ys1=代入（LD）的約束，y1+4y2 從而 定理 LP的檢驗(yàn)數(shù)對應(yīng)對偶問題的一個(gè)0BNIIB-10CN-CBB--CBB-對應(yīng)的對偶---maxz7x13x12x24x16x27x2x10,x2

minw90y1200y2210y33y14y22y16y27y3y1,y2,y3minw90y1200y2210y33y14y2y4y62y16y27y3y5y7yi i1 75000b710-0501-0000-100--00 b0 b 10--- -01-3/10- 00 M-14M-- 三、對偶問題的 z*w*CB1by*b by i i變量yi*的經(jīng)濟(jì)意義是在其它條件不變的情況下，單在完全市場經(jīng)濟(jì)條件下 價(jià)格對市場有調(diào)節(jié)作 當(dāng)資源的市場價(jià)高 價(jià)格時(shí)，企業(yè)應(yīng)把已有資源賣例7對例1，原問題最優(yōu)點(diǎn)B(4,2),最優(yōu)值543

②

③ ① y設(shè)備臺時(shí)數(shù)由8增到9，則可行域界線從①移到了①，，最優(yōu)點(diǎn)變?yōu)閥*目標(biāo)值由14增加到31/2，增加了3/2，等于對偶問題1y原材料A若增加1千克，可行域邊界由②移到②‘，最優(yōu)點(diǎn)變?yōu)镕，最優(yōu)y增加1/8，等于對偶問題的2原材料B若增加1千克，可行域由③移到了③‘所以對偶問

等于3§３對偶單一、對偶單純形LP的最優(yōu)解必須滿足三基本可行最優(yōu)

B1bCCBB1A0YA

(對偶問題可行LP最優(yōu) LD可性單純保持LP解可LP對偶單純形

另一

逐步減少的檢驗(yàn)數(shù)個(gè)使LD解的不行性逐步消逐步消除

j0LD解可LP的基

保持LD解可

另一

解的不可行

LD解可行(最優(yōu)單純形法：(1) (1)(2)基可基可行最優(yōu)對偶單純形法：(1) (1)(2)對偶對偶可行可行二、對偶單純形1假定已給一對偶可行基（即它對應(yīng)的對偶問題的解可行）單位陣，相應(yīng)的基解為XB=B-1b。若它的各個(gè)分量均非負(fù)，則這個(gè)解就是優(yōu)解，停止迭行解，停止迭代；否則轉(zhuǎn)（3） min{bi|bi<0bl則對應(yīng)的xl為換出變量；計(jì)算θ的值，min

a a

（4）以alk為主元，進(jìn)行系數(shù)變換，得一新的正則解，轉(zhuǎn)（2）例1min2x1+4x2+5x3+x43x1－x2+7x3－2x45x1+2x2+x3+6x4x1,x2,x3,x4引入剩余變量x5x6x7maxz’=－3x1－2x2－x3－ －3x1+x2－7x3+2 + =－－5x1－2x2x1,…,x7

+x7=－3－2－1 00 0－2－4－5 0000 1 100[－5]－2－1 01 －2－1 000根據(jù)min{0－2－10}－10,以x7為換出變量,min3,2,1,4 6 以為x1為換入變量，以a31=－5為主元進(jìn)行系數(shù)變 0 00－16/5 1040 －32/5014 0020－4/5－2/500-因?yàn)閎i≥0,所以X為最優(yōu)解,相應(yīng)目標(biāo)函數(shù)值6。§3靈敏對于標(biāo)準(zhǔn)形式的maxzCXAXbX一旦其系數(shù)矩陣A，約束條件右側(cè)向量和價(jià)值系數(shù)向量C給定之后，這個(gè)線性規(guī)劃問題也就確定了．但是，這些系數(shù)是可能發(fā)生變化的。對解的影響主要1、最優(yōu)解保持不變，即基變量和它們的取值沒有2、基變量保持不變，但它們的值改3、基解完因此，我們最終要回答下面兩12、如果系數(shù)的變化超出了上述范圍，如何用最簡方法求出新的最一．價(jià)值系數(shù)變B是原問題的最優(yōu) xrc'c XB

C

價(jià)值系數(shù)變化不影響基Ｂ的可行性，只影響基Ｂ的最優(yōu)1、xr為非基變cr的變化只影響其本身的檢驗(yàn)數(shù)r,只要r=<0,最優(yōu)解不變.既對該c’,只需滿足 C'CB1A0,否則可 xr作為引入變量,進(jìn)行單純形迭代求解雖然cr的變化不影響基B的可行性，但由r

CBB1 ,r生影響。只有r

CrC

B1

B才不變。否則，取最大檢驗(yàn)數(shù)作單純形B例1maxz=x1+2x2－x1+x2－2x3x1,x2,120012000111080101412001 00 2 040 100 0

CB1

1/2

1

3/ 2 00 2 040 101 02 00 21 10800 110 0二、右側(cè)常數(shù)不影響XB CCBB1ArCrCBB1Ar和X=B-1b知b的變化對檢驗(yàn)數(shù)沒 =B-1b’0，最優(yōu)基就仍B例2對例1中的線性規(guī)劃問題，當(dāng)?shù)谝粋€(gè)約束方程的右maxz=x1+2x2－x1+x2－2x3x1,x2, 1

1/

5XB

b1/

14 解。得到表4 0 2 050[－3/2]0 1 0 0 2 1 0三、約束條件系數(shù)矩陣A非基變量的系數(shù)列向量Aj變XB

CCBB1A也變?yōu)锳’=(a )，而CCB1A，顯然 'cCB1A' 例3對例1x3的系注意332

01/1/

01211四、增加或刪去1、增加一在原問題的最優(yōu)單純形表中增加一列，對應(yīng)變量xn+1及B-個(gè)可行基，xn+1為非基變n10滿足最優(yōu)性條件，原B是新問題

B1

0新問 ，否則繼續(xù)迭代 2、刪去一若為非基變量，刪去不影響最優(yōu)基可行解和最優(yōu)目標(biāo)函若為基變量，可將其退出基（M為價(jià)值系數(shù)將其迭代出基），一旦出基即例4對例1中的線性規(guī)劃問題，增加一變量，價(jià)值系數(shù)為解：注意 1/ 1/62 0

01 11

1/

01

1/2A6 A61/

3/ 1 將x6引入，作單純形迭代，得表51 2 2 40 00 11 2 2 2/ 042 101 01 2 11 2/ 0420 140— 0五、增加或刪去1、增加一個(gè)約束 z7 5 3x12x24x16x2xj j1,,5

CD

z7x15x3x12x27x24x16x7x2xj j1,,5

增加一個(gè)約束后，可行域R'分三種R'R'

R'R首先將原問題最優(yōu)解代 束，如滿 束n+1m+2、刪除一個(gè)約束

x3解：顯然原最優(yōu)解不滿足束，采用上述加行加列的方法12 00 21 00400 100001 01300 01 00 2 0040 1000[－1/2] 01 00 00 2 0130 131 02 00例 z5x15x213xx1x23x312x14x210x3x1,x2,x3b2變?yōu)?(5)的系數(shù)變

c12,A1(0,5)Tb變?yōu)?(6)增加一個(gè)變量x，系數(shù)

c610,A6