最優(yōu)化方法-之單純形法

最優(yōu)化方法Optimization

第五講第三章單純形法主要內(nèi)容(分2講)單純形法兩階段法退化情形處理方法:Bland法則修正單純形法線性規(guī)劃的最優(yōu)性條件單純形法TheSimplexMethod*可行域的極點(diǎn)對(duì)應(yīng)LP問(wèn)題的基(本)可行解*LP的最優(yōu)解確定可以在基(本)可行解中找到1.單純形法的步驟初始基可行解最優(yōu)性條件最優(yōu)解換基迭代新的基可行解NYLP基本定理:2.舉例x1x212341234l2l1OAB(1,1.5)C

可行域

（OABC）最優(yōu)解：X=（11.5)T化成標(biāo)準(zhǔn)形找初始基可行解推斷是否最優(yōu)解?能否找到另一個(gè)基可行解使目標(biāo)函數(shù)值下降?換基迭代換基：找一個(gè)非基變量作為換入變量，同時(shí)確定一個(gè)基變量為換出變量。依據(jù)原則：1)新的基可行解能使目標(biāo)值削減；2)新的基照舊是可行基。確定換入變量：選取x1為換入變量確定換出變量:迭代（求新的基本可行解）主元素推斷代入目標(biāo)函數(shù)得確定進(jìn)基變量和出基變量換基迭代推斷代入目標(biāo)函數(shù)：最優(yōu)解：x1x212341234l2l1OAB(1,1.5)C

可行域

（OABC）最優(yōu)解：X=（11.5)T設(shè)(L)有一個(gè)初始基初始基本可行解為:考慮xk的取值單純性法計(jì)算步驟初始基為B,初始基本可行解為x(0)=(B-1b0)T是否yk=B-1Pk≤0是x(0)為最優(yōu)解無(wú)界是例1例2表格形式的單純形方法單純形表fxBxN右端xBf0ImB-1NB-1b10cBB-1N-cN

cBB-1b可省略檢驗(yàn)數(shù)(判別數(shù))目標(biāo)函數(shù)取值基變量取值用單純形表求解問(wèn)題：xBxN右端xBImB-1NB-1b0cBB-1N-cNcBB-1b主元消去法檢驗(yàn)數(shù)\基\函數(shù)值等的變更----矩陣運(yùn)算xBxN右端xBImB-1NB-1b0cBB-1N-cNcBB-1bx1x4x51-210001-31001-10101-2002120x1

x2x3x4x5x1

x2x3x4x5x1x4x51-210001-31001-10101-2002120x1x2x3100-1/25/2010-1/23/2001-1/21/2000-1/2-1/213/25/21/2-3/2x1x2x510-52001-310002-11001-10411-1１２x1

x2

x3

x4x5x4x51131014-101-2-1100640x3x10-111/3-1/31301/32/30601/35/32/314/326/3x4x10-331-114-10107-102248１３單純形法的進(jìn)一步探討

無(wú)界解Oz→-∞結(jié)論：若zj-cj>0,對(duì)應(yīng)的系數(shù)列向量≤0，則該LP存在無(wú)界解。x1

x2

x3

x4-3101-20111100-31264x3x2-2-31-110-3101x3x42423000

1無(wú)限多個(gè)解x1x2l2l1OABCx1

x2

x3

x4

2710720141400x3x421210017/45-2/4510-2/457/4500-20x2x17/37/3-422/711/7045/70-2/7100-20x2x4315-42745/7結(jié)論：若某個(gè)非基變量的檢驗(yàn)數(shù)為零，則該LP存在多個(gè)最優(yōu)解。

課外練習(xí)第六講單純形法之完善

兩階段法xa的每個(gè)重量稱為人工變量.兩階段法第1階段:用單純形法把人工變量變?yōu)榉腔兞浚?/p>

求出原問(wèn)題的一個(gè)基可行解。

方法：求解下列模型基變量第2階段:從得到的基本可行解動(dòng)身,用單純形法求(L)的最優(yōu)解.x1x2x3

x4x5x6x711-10010-110-100102-1-10001200100x6x7x53184300210-2-110-100120-1101-120-1100-210-1/21/201/2-1/201-1/2-1/201/21/2003/21/21-1/3-1/2000-200-1x6x2x5x1x2x52161232012求解第1階段問(wèn)題：起先第2階段：x1x2x3x4x5x1x2x510-1/21/2001-1/2-1/20003/21/21003/2-1/20123-4x1x2x31002/31/3010-1/31/30011/32/3000-1-1232-73/210-1001-20-3-210-1/211/21/200-10-4-200x2x5x610000101/201/200-5-21210-1001x2x5x1100

x1x2x3x4x5x6

-121100-44-1010-34-200010-1001x4x5x6240421-5x1x2

x3x41002/50012/5000-1/10x2x3x1100-10101/2x1x2

x3

x4

x5x6

1002/5-1/53/50012/5-1/5-2/5

0101/201/200-5-21210-1001x2x3x1x2x5x1100100

-50101/201/2第2階段112退化情形—(自學(xué))x1

x2

x3

x4

x5x6x4x5x6

-1010001010111001243201.5000x1x5x6

-10100021-210021-101201021.5-200-401*在單純形法的計(jì)算過(guò)程中，確定出基變量時(shí)存在兩個(gè)或兩個(gè)以上的最小比值，這時(shí)會(huì)出現(xiàn)退化解。*有時(shí)，退化會(huì)造成計(jì)算過(guò)程的循環(huán)，恒久達(dá)不到最優(yōu)解。x1

x2

x3

x4

x5

x6

x71００1/4-8-190101/2-12-1/2300100100003/4-201/2-64001-32-436-210043/2-150010010-300047/2-33x1x2x3x4x2x300100100-1280108-84-1/21/40013/8-15/40010010-1-10002-18x4x5x300011/448x1

x2

x3

x4

x5

x6

x7-3/21０1/801-21/21/16-1/80-3/64103/163/2-11-1/80021/22-30-1/40032-60-5/256101/3-2/30-1/416/301-2615/2-56001-101/2-1600x6x5x3x6x7x3001001001-30-5/4281/2001/301/6-4-1/6100100100207/4-44-1/20x1x7x300013/1621/3x1