線性規(guī)劃單純形大M法及階段經(jīng)典運(yùn)籌學(xué)

1、上堂課主要內(nèi)容:1.若（LP）問(wèn)題有可行解，則可行域是一個(gè)凸多邊形2.若（LP）問(wèn)題有最優(yōu)解，則最優(yōu)解一定可以在凸多邊 形的某個(gè)頂點(diǎn)達(dá)到4.基本可行解的個(gè)數(shù)是有限的3.頂點(diǎn)與基本可行解是一一對(duì)應(yīng)的若（LP）問(wèn)題有最優(yōu)解，則最優(yōu)解一定可以在某個(gè) 基本可行解達(dá)到找最優(yōu)解可從一個(gè)基本可行解入手，通過(guò)某種方法，調(diào)整基變量，轉(zhuǎn)到另一個(gè)基本可行解，并使目標(biāo)函數(shù)值不斷增大，通過(guò)有限次的迭代就能找到最優(yōu)解1單純形法：B的典則形式：取一可行基B，E0常數(shù)項(xiàng)初始單純形表：0？2E0常數(shù)項(xiàng)0最優(yōu)值 最優(yōu)單純形表3單純形法的理論證明：r(A)=m假定1、問(wèn)題的可行解域非空2、所有的基本可行解非退化3、已找到一個(gè)初始基

2、本可行解4可得一個(gè)初始基本可行解不可行51.4.4 尋找初始基本可行解一、兩階段法基本思路：通過(guò)引進(jìn)人工變量，構(gòu)造一個(gè)輔助線性規(guī)劃問(wèn)題，該線性規(guī)劃問(wèn)題明顯有一個(gè)基本可行解，通過(guò)對(duì)該問(wèn)題求最優(yōu)解來(lái)得到原問(wèn)題的一個(gè)基本可行解6做輔助線性規(guī)劃問(wèn)題:2、（2）的目標(biāo)函數(shù)值S有 上界，3、（2）有最優(yōu)值S*(1)(2)7定理：若輔助線性規(guī)劃問(wèn)題（2）的最優(yōu)值S*0,則原 線性規(guī)劃問(wèn)題（1）無(wú)可行解，因此無(wú)最優(yōu)解(1)(2)反證：若不然，原問(wèn)題（1）有可行解矛盾8定理：若輔助線性規(guī)劃問(wèn)題（2）的最優(yōu)值S*=0, (1)(2)因?yàn)镾*=0可證X是基本可行解9解：做輔助線性規(guī)劃問(wèn)題 不是典則形式最優(yōu)值S*=0

3、得原問(wèn)題的一個(gè)基本可行解X=（1/2,0,1/4,0,0)為原問(wèn)題的最優(yōu)解最優(yōu)值Z= -31/41 -1 6 -1 0 1 0 2 1 1 2 0 -1 0 1 12 0 8 -1 -1 0 0 S+3 -5 0 21 0 0 0 0 Z 0 -2 4 -1 1 1 -1 1 1 1 2 0 -1 0 1 10 -2 4 -1 1 0 -2 S+10 5 -11 0 -5 0 5 Z+50 1/2 1 1/4 1/4 1/4 -1/4 1/4 1 2 0 1/2 -3/2 1/2 3/2 1/20 0 0 0 0 -1 -1 S+00 1/2 0 -11/4 9/4 11/4 9/4 Z+31

4、/40 1/2 0 -11/4 9/4 11/4 9/4 Z+31/4最優(yōu)解X*=（1/2,0,1/4,0,0,0,0)10解：做輔助線性規(guī)劃問(wèn)題3 4 0 -1 0 S+123 2 0 0 0 Z 2 1 1 0 0 2 3 4 0 -1 1 12-5 0 -4 -1 0 S+4 -1 0 -2 0 0 Z-4 2 1 1 0 0 2 -2 0 -4 -1 1 4輔助線性規(guī)劃問(wèn)題的最優(yōu)解S=-40所以原問(wèn)題無(wú)最優(yōu)解11111.51x4x6x3-201000110100-11-213-20100-1101-100001Z+10100-10-3S+1x4x2x30100-11-21-201000

5、113001-22-5121000-11-1Z+200000-1-1Sx3x2x112兩階段法：做輔助線性規(guī)劃問(wèn)題:(1)(2)定理1：若輔助線性規(guī)劃問(wèn)題（2）的最優(yōu)值S*0,且M充分大（2）有最優(yōu)值或無(wú)界151、若輔助線性規(guī)劃問(wèn)題（2）有最優(yōu)值2、若輔助線性規(guī)劃問(wèn)題（2）無(wú)界16不是單純形表M-5 -M 6M-21 -M 0 0 -M Z/+2M2M-5 0 8M-21 -M -M 0 0 Z/+3M初始單純形表M充分大 0 -2 4 -1 1 1 -1 1 0 5-2M 4M-11 -M M-5 0 5-2M Z/+5+M21 不是典則形式17 0 -2 4 -1 1 1 -1 1 0 5

6、-2M 4M-11 -M M-5 0 5-2M Z/+5+M 0 -2 4 -1 1 1 -1 1 0 -5 9 -5 0 5-M -M Z/+10 1 -1 6 -1 0 1 0 2 0 -1/2 1 -1/4 1/4 1/4 -1/4 1/4 0 -1/2 0 -11/4 -9/4 11/4-M 9/4-M Z/+31/4 1 2 0 1/2 -2/3 -1/2 3/2 1/2 線性規(guī)劃（2）的最優(yōu)解（1/2，0，1/4，0，0，0，0） 所以得原線性規(guī) 劃（1）的最優(yōu)解（1/2，0，1/4，0，0）最優(yōu)值Z= -31/418大M法：做輔助線性規(guī)劃問(wèn)題：(1)(2)M0,且M充分大1、若問(wèn)

7、題（2）有最優(yōu)值2、若問(wèn)題（2）無(wú)界19練習(xí)：20單純形法假定：1、問(wèn)題的可行解域非空2、所有的基本可行解非退化3、已找到一個(gè)初始基本可行解退化解：基本可行解中某一基變量取零值后果：在迭代過(guò)程中可能出現(xiàn)死循環(huán)211.5 退化、循環(huán)和 防止循環(huán)的方法22解及目標(biāo)函數(shù)值未變退化解002324=表1出現(xiàn)循環(huán)死循環(huán)25退化解及目標(biāo)函數(shù)值未變，未出現(xiàn)循環(huán)1126出現(xiàn)退化的原因：在確定出基變量時(shí)，有兩個(gè)或兩個(gè)以上的值相同方法二：攝動(dòng)法避免循環(huán)的方法：方法一；勃蘭特法（Bland,1977）27方法一：勃蘭特法方法與單純刑法相似，但入基變量和出基變量的確定方法不同具體做法如下：當(dāng)按規(guī)則計(jì)算比值時(shí)，若存在幾個(gè)

8、i同時(shí)達(dá)到最小，取這些i對(duì)應(yīng)的基變量中下標(biāo)最小的基變量為出基變量（1）入基變量的確定：可以證明，用此方法不會(huì)產(chǎn)生循環(huán)目標(biāo)函數(shù)上升較慢選取i0中下標(biāo)最小的檢驗(yàn)數(shù)k所對(duì)應(yīng)的非基變量xk為入基變量（2）出基變量的確定：28表2X1X2X3X4X5X6X7bZ05341-204-2000ZX11-11-5182000X6042-8-1100X70115-18-2011表3X1X2X3X4X5X6X7bZ0014.5-98-6.75-13.250ZX1100.5-4-0.752.7500X2010.5-2-0.250.2500X700-0.540.75-2.751129表4X1X2X3X4X5X6X7b

9、Z-29001815-930ZX3201-8-1.55.500X2-11020.5-2.500X710000011表3X1X2X3X4X5X6X7bZ0014.5-98-6.75-13.250ZX1100.5-4-0.752.7500X2010.5-2-0.250.2500X700-0.540.75-2.7511表5X1X2X3X4X5X6X7bZ-20-90010.5-70.50ZX3-24100.5-4.500X4-0.50.5010.25-1.2500X71000001130表5X1X2X3X4X5X6X7bZ-20-90010.5-70.50ZX3-24100.5-4.500X2-0.50.5010.25-1.2500X710000011表6X1X2X3X4X5X6X7bZ22-93-2100240ZX5-4-4-281-100X20.5-1.5-0.510100X710000011表7X1X2X3X4X5X6X7bZ0-271-440-200ZX50-5.5-2.591000X11-3-120200X7031-20-21131表7X1X2X3X4X5X6X7bZ0-271-440-200ZX50-5.5-2.591000X11-3-120200X7031-20-211表7X1X2X3X4X