線性規(guī)劃LinearProgramming〔LP〕

單純形方法1線性規(guī)劃LinearProgramming〔LP〕單純形方法是于1947年首先創(chuàng)造的。近50年來(lái)，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問(wèn)題的求解。本節(jié)討論單純形法的根本概念、原理及算法。2線性規(guī)劃LinearProgramming〔LP〕給定線性規(guī)劃問(wèn)題〔標(biāo)準(zhǔn)形式〕maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0〔j=1，2…n〕3線性規(guī)劃LinearProgramming〔LP〕一、線性規(guī)劃問(wèn)題的解的概念可行解最優(yōu)解基基解〔根本解〕基可行解可行基4線性規(guī)劃LinearProgramming〔LP〕MaxZ=3X1+5X2X1+X3=4s.t.2X2+X4=123X1+2X2+X5=18Xi≥0

5線性規(guī)劃LinearProgramming〔LP〕X1X2X3X4X5Z004121800640630094-60454001261260-2120184600-64243060272620036√√√√√*6線性規(guī)劃LinearProgramming〔LP〕123456787線性規(guī)劃LinearProgramming〔LP〕二、凸集及其頂點(diǎn)凸集頂點(diǎn)〔極點(diǎn)〕凸集凹集8線性規(guī)劃LinearProgramming〔LP〕三、線性規(guī)劃根本定理根本定理1線性規(guī)劃所有可行解組成的集合S={X|AX=b，X≥0}是凸集。根本定理2X是線性規(guī)劃問(wèn)題的根本可行解的充要條件為是X是凸集S={X|AX=b，X≥0}的極點(diǎn)。根本定理3給定線性規(guī)劃問(wèn)題，A是秩為m的mn矩陣，〔i〕假設(shè)線性規(guī)劃問(wèn)題存在可行解，那么必存在基可行解〔ii〕假設(shè)線性規(guī)劃問(wèn)題存在有界最優(yōu)解，那么必存在有界最優(yōu)基可行解。9線性規(guī)劃LinearProgramming〔LP〕單純形法迭代原理及其思路單純形法的初步討論

MaxZ=50X1+30X2s.t.4X1+3X2≤

1202X1+X2≤50X1，X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2

+X4

=50X1，X2，X3，X4

≥0化為標(biāo)準(zhǔn)型10線性規(guī)劃LinearProgramming〔LP〕此線性規(guī)劃問(wèn)題轉(zhuǎn)化為了一個(gè)含有四個(gè)變量的標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題，X3，X4為松弛變量。為求解上面的LP問(wèn)題，我們要考慮滿(mǎn)足約束條件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下---11線性規(guī)劃LinearProgramming〔LP〕確定初始基可行解：通過(guò)觀察可以發(fā)現(xiàn)，松弛變量X3和X4對(duì)應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此?。篨3，X4為基變量；X1，X2為非基變量。那么可變?yōu)镸ax

Z=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2

X1，X2，X3，X4≥012線性規(guī)劃LinearProgramming〔LP〕典式關(guān)于基的典式——1、等式約束條件中顯含基可行解2、目標(biāo)函數(shù)中不含基變量MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2

+X4

=50X1，X2，X3，X4≥0Max

Z=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2X1，X2，X3，X4≥013線性規(guī)劃LinearProgramming〔LP〕在典式中令：X1=X2=0，我們得到一個(gè)根本可行解X1=〔X1，X2，X3，X4〕T=〔0，0，120，50〕T，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z1=50X1+30X2=0Max

Z=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2X1，X2，X3，X4≥014線性規(guī)劃LinearProgramming〔LP〕最優(yōu)性檢驗(yàn)：根本可行解X1是最優(yōu)解嗎？顯然不是。應(yīng)尋找更好的解。從問(wèn)題的數(shù)學(xué)角度分析，在典式的目標(biāo)函數(shù)中，非基變量X1，X2前的系數(shù)都為正，說(shuō)明目標(biāo)函數(shù)值有增加的可能。只要將目標(biāo)函數(shù)中系數(shù)為正的某非基變量與某一基變量地位對(duì)換。15線性規(guī)劃LinearProgramming〔LP〕換基迭代：進(jìn)行換基就是要從非基變量中選一個(gè)變量入基，再?gòu)幕兞恐羞x一個(gè)變量出基。并且換基后仍需滿(mǎn)足：1、新的解仍是根本可行解；2、目標(biāo)函數(shù)值將得到改善。16線性規(guī)劃LinearProgramming〔LP〕選擇入基變量：由于在目標(biāo)函數(shù)Z1=50X1+30X2中X1，X2的系數(shù)都為正，哪一個(gè)入基都可使目標(biāo)函數(shù)值得到改善。對(duì)于求目標(biāo)函數(shù)極大化的問(wèn)題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的X1入基。選擇出基變量：X1入基后，其值從零增加并由于約束條件的原因會(huì)引起其他變量的變化。由典式以及變量必須取正值的條件，我們可以得到以下不等式關(guān)系：X3=120-4X1-3X2≥0X4=50-2X1-X2≥017線性規(guī)劃LinearProgramming〔LP〕因?yàn)榈骕2仍為非基變量〔仍會(huì)令其取值為零〕，那么上式可簡(jiǎn)化為：120-4X1≥050-2X1≥0由此可以看出，雖然我們希望X1入基后取正值，且取值越大目標(biāo)值增加越大，但是，X1又得受到約束。顯然，只有取X1=min〔120/4，50/2〕=25時(shí)，才能使上述不等式成立并且恰使基變量X4變?yōu)榱?，這正好滿(mǎn)足非基變量必須取值零的條件，所以可令X4出基，方程變?yōu)椋?X1+X3=120-3X22X1=50-X2-X4化簡(jiǎn)后得新的典式方程：X3=20-X2+2X4X1=25-0.5X2-0.5X418線性規(guī)劃LinearProgramming〔LP〕代入目標(biāo)函數(shù)可得：Z2=1250+5X2-25X4令非基變量X2=X4=0，即可得一個(gè)新的根本可行解X2=〔25，0，20，0〕T，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z2=1250，并完成了第一次迭代。由于目標(biāo)函數(shù)Z2=1250+5X2-25X4中X2的系數(shù)仍為正，該解X2仍不是最優(yōu)解。重復(fù)上述迭代過(guò)程得到：X2入基，X3出基，那么新的典式方程變?yōu)椋篨1=15+0.5X3-1.5X4X2=20-X3+2X4Z3=1350-5X3-15X419線性規(guī)劃LinearProgramming〔LP〕第三個(gè)根本可行解X3=〔15，20，0，0〕T，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z3=1350。此時(shí)松弛變量都是非基變量〔取值為零〕，這說(shuō)明資源已用盡；并且目標(biāo)函數(shù)值Z3=1350-5X3-15X4中非基變量X3，X4的系數(shù)全為負(fù)值，說(shuō)明目標(biāo)函數(shù)已無(wú)法進(jìn)一步改善，因此該解已是最優(yōu)解。20線性規(guī)劃LinearProgramming〔LP〕單純形法小結(jié)：?jiǎn)渭冃畏ㄊ沁@樣一種迭代算法——如以下圖…X1Z1保持單調(diào)增保持可行性保持可行性保持可行性保持可行性保持單調(diào)增保持單調(diào)增保持單調(diào)增X2X3...XkZ2Z3...Zk當(dāng)Zk中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的根本可行解Xk即是線性規(guī)劃問(wèn)題的最優(yōu)解，迭代結(jié)束。21線性規(guī)劃LinearProgramming〔LP〕單純形表對(duì)于給定的線性規(guī)劃問(wèn)題：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2s.t.………am1x1+am2x2+…+amnxn≤bmxj≥0〔j=1，2…n〕對(duì)此問(wèn)題添加m個(gè)松弛變量后，可得下面線性規(guī)劃問(wèn)題并且是典式的形式。22線性規(guī)劃LinearProgramming〔LP〕線性規(guī)劃的典式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2s.t.…am1x1+am2x2+…+amnxn+xn+m=bmxj≥0〔j=1，2…n，n+1，n+2，…n+m〕23線性規(guī)劃LinearProgramming〔LP〕將上面典式中各變量及系數(shù)填寫(xiě)在一張表格中就形成下面的單純形表cj

c1c2…cncn+1…cn+mCB基解

x1x2…xnxn+1…xn+10000xn+1xn+2…xn+m

b1

b2…

bma11a12…a1n1a21a22…a2n………………am1am2…amn112…mj=cj–zj

c1c2…cn0…0j=cj–zj

1

2…

nn+1…n+m24線性規(guī)劃LinearProgramming〔LP〕上面的單純形表還可以表示成矩陣的形式基解X

XSXSbAIj

C

0基解XB

XN

XSXSbBNIj

CB

CN

025線性規(guī)劃LinearProgramming〔LP〕由單純形表進(jìn)行迭代步驟：選擇Xj入基：當(dāng)j行中cj=max{ci∣ci0}選擇Xi出基：當(dāng)i=min{(bi/aij)∣aij0}換基迭代：當(dāng)確定了入基變量Xj、出基變量Xi后，以aij作為主元對(duì)單純形表進(jìn)行初等行變換〔取主運(yùn)算〕，即將aij所在列除采用初等行變換將aii變換為1外的其余元素都變換為0。注意這種變換只能采用初等行變換!26線性規(guī)劃LinearProgramming〔LP〕最優(yōu)解檢驗(yàn)：1、當(dāng)?shù)M(jìn)行至某一步時(shí)，j行中所有檢驗(yàn)數(shù)均小于等于零，那么迭代結(jié)束。表中當(dāng)前所指根本可行解即為最優(yōu)解。2、當(dāng)?shù)M(jìn)行至某一步時(shí)，j行中所有檢驗(yàn)數(shù)均小于等于零，且此時(shí)至少有一個(gè)非基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)rk等于零，那么原線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解。3、當(dāng)?shù)M(jìn)行至某一步時(shí)，j行中至少有一個(gè)檢驗(yàn)數(shù)rk大于零，且該檢驗(yàn)數(shù)對(duì)應(yīng)的列中a1k，a2k，…amk，均小于等于零，那么原線性規(guī)劃問(wèn)題最優(yōu)解無(wú)界〔maxZ→+∞〕。27線性規(guī)劃LinearProgramming〔LP〕其中b≥0，I是mm單位矩陣。對(duì)上面〔I式〕經(jīng)過(guò)迭代，并設(shè)最終的最優(yōu)基矩陣為B,不妨設(shè)B為A的首m列，那么將〔I式〕改寫(xiě)后有單純形方法的矩陣描述：設(shè)線性規(guī)劃問(wèn)題maxZ=CXmaxZ=CX+0XSs.t.AX≤bs.t.AX+IXS=b〔I式〕X≥0X，XS≥028線性規(guī)劃LinearProgramming〔LP〕maxZ=CBXB+CNXN+0XS

s.t.BXB+NXN+IXS=bXB，XN，XS≥0

maxZ=CBB-1+〔CN-CBB-1〕XN-CBB-1XSs.t.XB+B-1NXN+B-1XS=B-1bXB，XN，XS≥0

B式中最優(yōu)目標(biāo)函數(shù)值Z*=CBB

-1，檢驗(yàn)數(shù)CN-CBB

-1≤

0

，-

CBB

-1≤0單純形方法迭代〔I式〕〔B式〕29線性規(guī)劃LinearProgramming〔LP〕單純形方法的矩陣描述：基解XB

XN

XSXSbBNIj

CB

CN

0基解XB

XN

XSXBB-1bIB-1NB-1j

0

CN-CBB

–1N-

CBB

-1對(duì)應(yīng)I式的單純形表——

I

表對(duì)應(yīng)B

式的單純形表——B

表迭代30線性規(guī)劃LinearProgramming〔LP〕單純形表計(jì)算步驟舉例給定線性規(guī)劃問(wèn)題maxz=50X1+30X2s.t.4X1+3X2≤

1202X1+X2

≤50X1，X2

≥0maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4

≥031線性規(guī)劃LinearProgramming〔LP〕基XB解B-1bX1X2X3X4X31204310X4502101檢驗(yàn)數(shù)j

5030002120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-1532線性規(guī)劃LinearProgramming〔LP〕人工變量法：當(dāng)一般線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)化之后，我們或可得到一個(gè)顯然的根本可行解〔如松弛變量作為基變量的一個(gè)初始根本可行解〕，這樣我們就可以馬上進(jìn)入單純形表的運(yùn)算步驟。然而，并非所有問(wèn)題標(biāo)準(zhǔn)化之后我們都可得到一個(gè)顯然的初始根本可行解，這時(shí)就需要我們首先確定出一個(gè)根本可行解作為初始根本可行解。通常采用的是人工變量法來(lái)確定這樣的初始根本可行解。這種情況下一般有兩種方法：1、大M法〔罰因子法〕2、兩階段法33線性規(guī)劃LinearProgramming〔LP〕maxz=-3X1+X3

x1+x2+x3

≤4-2x1+x2–x3

≥13x2+x3=9x1，x2，x3

≥0LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥034線性規(guī)劃LinearProgramming〔LP〕大M法求解線性規(guī)劃問(wèn)題的具體方法與前面的一般單純形法相同，就是將M當(dāng)作一個(gè)充分大的數(shù)來(lái)處理。35線性規(guī)劃LinearProgramming〔LP〕1、大M法LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j36線性規(guī)劃LinearProgramming〔LP〕基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j-3-2M4M10-M0037線性規(guī)劃LinearProgramming〔LP〕基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù)j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗(yàn)數(shù)j-3+6M01+4M03M-4M038線性規(guī)劃LinearProgramming〔LP〕基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110--X7660403-311檢驗(yàn)數(shù)j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù)j00301.5-1.5-M0.5-M39線性規(guī)劃LinearProgramming〔LP〕基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2---X23011/30001/39X11102/301/2-1/21/63/2檢驗(yàn)數(shù)j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4檢驗(yàn)數(shù)j-9/2000-3/43/4-M-1/4-M40線性規(guī)劃LinearProgramming〔LP〕采用大M法求解線性規(guī)劃問(wèn)題時(shí)可能出現(xiàn)的幾種情況：1、當(dāng)采用單純形法求解LPM得到最優(yōu)解時(shí)，基變量不含任何人工變量，那么所得到的最優(yōu)解就是原問(wèn)題的最優(yōu)解；2、當(dāng)采用單純形法求解LPM得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且非零，那么原問(wèn)題無(wú)可行解；3、當(dāng)采用單純形法求解LPM得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且人工變量都為零，那么通過(guò)變換得到原問(wèn)題最優(yōu)解；41線性規(guī)劃LinearProgramming〔LP〕2、兩階段法I階段問(wèn)題maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j42線性規(guī)劃LinearProgramming〔LP〕第I階段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j-2400-10043線性規(guī)劃LinearProgramming〔LP〕第I階段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù)j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗(yàn)數(shù)j60403-4044線性規(guī)劃LinearProgramming〔LP〕第I階段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110---X7660403-311檢驗(yàn)數(shù)j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù)j00000-1-145線性規(guī)劃LinearProgramming〔LP〕第II階段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù)j00000-1-100303/246線性規(guī)劃LinearProgramming〔LP〕第II階段基XB解B-1bX1X2X3X4X5X400001-1/2---X23011/3009X11102/301/23/2檢驗(yàn)數(shù)j00303/2基XB解B-1bX1X2X3X4