運籌學(xué)第四版清華大學(xué)出版社運籌學(xué)教材組單純形法剖析

攻籌學(xué)(OperationsResearchChapter2線性規(guī)劃與單純形法O本章主要內(nèi)容：§2.1線性規(guī)劃問題及其數(shù)學(xué)模型§2.2線性規(guī)劃問題的幾何意義o§2.3單純形法§2.4單純形法的計算步驟§2.5單純形法的進(jìn)一步討論§2.6應(yīng)用舉例Page3§2.3單純形法§2.3單純形法Page4?2.3.1舉例?2.3.2初始基可行解的確定?2.3.3最優(yōu)性檢驗與解的判斷?2?3?4基變換?2.3.5迭代（旋轉(zhuǎn)運算）§2.3單純形法Page5單純形法求解線性規(guī)劃的思路：一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時有不定的解。但可以從線性方程組中找出一個個的單純形，每一個單純形可以求得一組解，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標(biāo)函數(shù)實現(xiàn)最大值，或最小值為止。這樣，問題就得到了最優(yōu)解，先舉一例來說明。_§2,3單純形法p心234舉例例2.6試以例2.1來討論如何用單純形法求解。maxz=2xt

+3x2

+Ox、+0x4+0x5x1

+2x2

-84x；

++x4=164x2+x5=12x'Oj=1,2,,5(2-11)(2-12)§2.3單純形法Page7解：約束條件(2-12)式的系數(shù)矩陣為rl2100、A=(P{,P2,P3,P4JP5)=

40010l^o4001〉(1)從(2_12)式^3^5的系數(shù)構(gòu)成的列向量11\:0，/>1，^5=0線性無關(guān)，構(gòu)成一個基對應(yīng)于B的變:x^x5為基變量。15-§2.3單純形法Page8x3

=8-Xj-2xx5=12-4x2x}+2x，+x3

-84Xj+x4=16x4=16-4x)4x2+x5=12將(2-13)式代入目標(biāo)函數(shù)(2-11)z=2xx

+3x2+0x3+0x4+0x.得z—

2xj+3x2(2-14)令非基變量X/=X2=0，得到一個基可行解Xw=(0,0,8，16，12)t，zo=0,(2-13)■B,.,_.§2.3單純形法Page9?這個基可行解的經(jīng)濟(jì)含義：工廠沒有安排生產(chǎn)產(chǎn)品I和n，資源都沒有被利用，所以利潤為?從(2-14)可以看到：非基變量的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品I或II，就可以使工廠的利潤指標(biāo)增加。所以只要在目標(biāo)函數(shù)(2-14)的表達(dá)式中還存在有正系數(shù)的睡變量，這表示目標(biāo)函數(shù)值還有增加的可能，就壽^要將非基變量與基變量進(jìn)行對換。三I?—V§2.3單純形法Page10(2)—般選擇目標(biāo)函數(shù)中正系數(shù)最大的那個非基變量為換入變量，將它換到基變量中，同時還要確定基變量中哪一個換出來成為非基變量o分析(2-14)式，當(dāng)將定為換入變量后，必須從中確定一個換出變量，并保證其余的變量仍然非負(fù)，>0。當(dāng)巧=0時，由(2-13)式得到x3

=8-2x2

>0=>Jx4=16

>0(2-15)x.=12-4x,>0之=8—xt

—2x2<x4=16-4xtx5

—12—4x2§2.3單純形法p;_只有x2:min（8/2，_，12/4）:3時才能使（2-15）式成立。因當(dāng)x2=3時，x5=0,x5為換出變量，即用jc2替換r5。以上數(shù)學(xué)描述說明，每生產(chǎn)一件產(chǎn)品II,需要用掉的各種資源數(shù)為（2，0，4）。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品n的產(chǎn)量。這里就是由原材料s的數(shù)量確定了產(chǎn)品n的I三了§2.3單純形法Page12貝！為新的基變量，久，；^為非基變量。由(2-13)將基變量用非基變量表示出來。x3

=8—x,-2x2x3

+2x2=8-Xjx4

=16-4xx

(2-13)=>x4=16-4xtX-

=12-4x24x2=12-x^3=2-Xl+^5g=>一x4=16—4X((2-17)J'i1x，=3——x2

4s55^=i§2.3單純形法Page13再將(2-17)式代入目標(biāo)函數(shù)(2-14)式得到(2-18)令非基變fixy=X5=0,得到另一個基可行解z=9十145X(1)=(0,3,2，16,0)T，q-9從目標(biāo)函數(shù)的表達(dá)式(2-18)可看到，非基變量的系數(shù)是正的，說明目標(biāo)函數(shù)值還可以增大，~即X⑴還不是最優(yōu)解。于是，再用上述方桜確定換入、換出變量，繼續(xù)迭代。-Page14(3)令々為換入變量，當(dāng)jrs=O時，由(2-17)式得到x,=2-X,0<x4

=16-4x)>0x，=3^0只有巧=側(cè)7/(2,12/4,

-)=3時才能使上式成立。因當(dāng)X/=2時，x3=0,為換出變量，即用久替^^。則AAA為新的基變量，XhX^非基變量。由(2-17)將基變量用非基變量表示出來。Page15x2=3x，=32-x.+-x5x4=16-4Xj1—x:1x.=2-

x,+—x;132x4=8+4x)-2x514再將(2-19)式代入目標(biāo)函數(shù)(2-18)式得到z=13-2x3+ix5

(2-20)4令非基變ix5=x5=o,得到另一個基可行解義(2)=(2,3,0,8,0)「，z2

=13.(2-19)Page16因當(dāng)x5=4時，x^=0,久為換出變量，即用x5替換與。rm—則工介人為新的基變量，A而為非基變量。由(2-19)將基變量用非基變量表示出來。x2=3一產(chǎn)0只有x5=min(-，8/2,3/1/4)=4時才能使上式成立。(4)令x5為換介變量，爭r3=0時，由(2-19)式得到x.=2+—x->01

2<x4

=8-2x5

>0Page1721)再將(2-21)式代、目標(biāo)-數(shù)(2-20)式得到=14'2X3_gx4(2-22)令非基變fix?=x,=0,得到另一個基可行解=(4,2,0,0,0)',Z3=14.'=2-x3+^x54-去X4x4

=8+4x1-2x5A=4+2x3--x4(2-;1^2=3

--^5i11x，=2--x,+-xd[22384§2.3單純形法Page18就必須支付附加費用。"目標(biāo)!!_綻盤?器鵲11^冤!’產(chǎn)品I生產(chǎn)4件，產(chǎn)品n生產(chǎn)2件時，工廠可以通過上例，可將每步迭代得到的結(jié)果與圖解法做一對比?！?.3單純形法Page19?例1滿足所有約束條件的可行域是髙維空間中的凸多面體(凸集)。該凸多面體上的頂點，就是基可行解。初始可行解x(")x(1)x(2)x(3),相于右圖中O->Q4

->Q3Q2,尤⑻=(0,0,8，16，12f-^0(0,0)X⑴=(0,3,2，16,0)14仏(0,3)—込(2,3)X{3)=(4,2,0,0t0)'^02(4,2)§2.3單純形法Page202.3.2初始基可行解的確定?為了確定初始基可行解，要首先找出初始可行基，其方法如下。-(1＞直接觀察-(2)加松弛變量-(3)加非負(fù)的人工變量§2.3單純形法Page21(1)直接觀察對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題，可直接由系數(shù)矩陣通過直接觀察，找出一個初始可行基<1B屯，P”…4)=§2.3單純形法Page22（2＞加松弛變量：所有約束條件為的不等式，在每個約束條件的左端加上一個松弛變量化為標(biāo)準(zhǔn)型。經(jīng)過整理，重新對~及?（卜1、2,…,…j?）進(jìn)行編號，則可得下列方程組，么為松弛變量）：=bth+a2mHxm+l+……+a2?x〃=b21G一■????漏?*?,,(2-23)x?+art

-++(zrtlxtJ=bQL--inmjn+im+\mnrnXj>o,j=l，2，."，n§2.3單純形法于是，（2-23）中含有一個znX/n階單位矩陣，初始可行基打即可取該單位矩陣。a…si…???l…k將（2-22）式每個等式移項得=4氣叫i^+i……A-=T_—,X2

—辦2°2,m+lXw+l…a2f,X.,￡~?*???VVV???■V**■.‘(2~24）廣Y=h=GX

—囑*mmiif+1-…amXn-Tf§2.3單純形法Page24(3)加非負(fù)的人工變量對所有約束條件為形式的不等式及等式約束情況，若不存在單位矩陣時，可采用人造基方法。-即對不等式約束，減去一個非負(fù)的剩余變量，再加上一個非負(fù)的人工變量；對于等式約束，再加上一個非負(fù)的人工變量這樣，總能在新的約束條件系數(shù)構(gòu)成的矩陣中得到一個單位矩陣。15-_§2.3單純形法w233最優(yōu)性檢驗與解的判別經(jīng)過迭代后(2-24)式變成Xi=b;—

Zayxp(f=1,2,…w)(2-25)代入目標(biāo)函數(shù)(2-20)式，整理后得hin?zjxj=

Hcixi+ZcjxjJ=lt=lmitwi=lj=m+1j=ffl+1§2.3單純形法Page26mm?oi=lt=lj=m+lj=m+lmfimn=^^cibi

—+J}CjXj1=1mj=m+lj=m+ljifm

、=Ec+LcrZcXxj

(2-26)(=1J=/M+l\f=lJmm

專J7令%=公々;，、=公人，j=m十l，"，'zi=li=lL§2.3單純形法Page27于是Z=z?+2(c;~zj)

xj(2—27)令aj-cj-Zj(j=m+l9^^n)9z=z0

+Z(2-28)稱為x;的檢驗數(shù)。j='"十|初始解x((,)=(4，/^"X，o，”.，o)，則此時有d)若幺0(J=訊+1，…，n)，z<z0;⑵若cr;>o(y=歷+1，…，ft)，z>Z0,故是判斷xw是否為最優(yōu)解的關(guān)鍵?！?.3單純形法Page28若X⑻=（《，心…人，0，...，0蘆對應(yīng)于基B的一個基可行解1.最優(yōu)解的判定理若對于一切戶m+7，...，n，有（7yd），則X＜（"為最優(yōu)解。2.無窮多最優(yōu)解判別定理I若對于一切/=W+A...，《，有＜7^0，且存在某個非基變量的檢驗數(shù)＜7,^=0,則線性規(guī)劃問題有無：窮多最優(yōu)解，xw為其中一個最優(yōu)解。"§2.3單純形法Page293.無界解判別定理若存在某個（rm+k

>0,并且對m

有a‘i，n^O,那么該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）。?其它情形-以上討論都是針對標(biāo)準(zhǔn)型的，即求目標(biāo)函數(shù)極大化時的情況。當(dāng)要求目標(biāo)函數(shù)極小化時，一種情況是t將其化為標(biāo)準(zhǔn)型。-如果不化為標(biāo)準(zhǔn)型，只需在上述1，2點中把agO改$為^0,第3點中將％+k>0改寫為<^<0目_。-§2.3單純形法Page30234基變換?若初始基可行解不是最優(yōu)解及不能判別無界時，需要找一個新的基可行解。?具體做法是-從原可行解基中換一個列向量（當(dāng)然要保證線性獨立），得到一個新的可行基，稱為基變換。為了換基，先要確定換入變量，再確定換出變量，讓它們相應(yīng)的系數(shù)列向量進(jìn)行對換，就得到一個新的基可行解。Qa_4§2.3單純形法Page31ijn+t,rn-k-tx:為換出變量。按最小比值確定0值，稱為最小比值規(guī)則一6xf0)1.換入變量的確定選取max^(rz

>0^=o;對應(yīng)的變量xA為換入變量。也可任意選擇或者按照最小下標(biāo)碼選擇。A,m+r>0=0=min2.換出變量的確定rx；o)§2.3單純形法Page32233迭代（旋轉(zhuǎn)運算）上述討論的基可行解的轉(zhuǎn)換方法是用向量方程描述的，在實際計算時不太方便，因此下面介紹系數(shù)矩陣法?？紤]以下形式的約束方程組§2.3單純形法Page33設(shè)^^,,...4為基變量，對應(yīng)的系數(shù)矩陣是單位陣/,它是可行基。令非基變量W?+2,..人為零，即可得到一個基可行解。若它不是最優(yōu)解，則要另找一個使目標(biāo)函數(shù)值增大的基可行解。這時從非基變量中確定心為換入變量。顯然這時0為(9=min—>0|=—f1

Jaik在迭代過程中0可表示為其中經(jīng)過迭代后對應(yīng)于么，么的元素值二§2.3單純形法Page34按權(quán)規(guī)則確定T/為換出變量，的系數(shù)列向量分別為第Z個分量§2.3單純形法為了使^與X,進(jìn)行對換，須把巧變?yōu)閱挝幌蛄?，這可以通過(2-33)式系數(shù)矩陣的增廣矩陣進(jìn)行初等變換來實現(xiàn)?！瑼…X入mX??xk…Lb，1??……ah,t?1??a“料i…a汝…alnb,(2_-34)???二1?_?amk??,amu§2.3單純形法Page36變換的步驟是:(1)將增廣矩陣(2-34)式中的第/行除以&，得到(2)將(2-34)式中a列的各元素，除叫變換為1以外，其他都應(yīng)變換為零。其他行的變換是將(2_35)式乘以aik(i4X)后，從(2-34)式的第桁減去，得到新的第/行。§2.3單純形法Page37由此可得到變換后系數(shù)矩陣