線性規(guī)劃理論與模型應(yīng)用PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1線性規(guī)劃理論與模型應(yīng)用線性規(guī)劃理論與模型應(yīng)用整數(shù)規(guī)劃問(wèn)題就是決策變量取整數(shù)值的線性或非線性整數(shù)規(guī)劃問(wèn)題就是決策變量取整數(shù)值的線性或非線性規(guī)劃，由于非線性整數(shù)規(guī)劃目前還沒(méi)有一般解法，因此本章規(guī)劃，由于非線性整數(shù)規(guī)劃目前還沒(méi)有一般解法，因此本章僅討論整數(shù)線性規(guī)劃。在第一章例僅討論整數(shù)線性規(guī)劃。在第一章例4中的截料問(wèn)題即是一個(gè)中的截料問(wèn)題即是一個(gè)整數(shù)線性規(guī)劃問(wèn)題。整數(shù)線性規(guī)劃問(wèn)題又可分為：整數(shù)線性規(guī)劃問(wèn)題。整數(shù)線性規(guī)劃問(wèn)題又可分為：v純整數(shù)純整數(shù)( (全整數(shù)全整數(shù)) )所有決策變量均要求取整數(shù)；所有決策變量均要求取整數(shù)；v混合整數(shù)混合整數(shù)部分決策變量要求取整數(shù)；部分決策變量要求取整數(shù)；v純純

2、0- -1規(guī)劃規(guī)劃所有決策變量均要求取所有決策變量均要求取0或或1；v混合混合0- -1規(guī)劃規(guī)劃部分決策變量要求取部分決策變量要求取0或或1。整數(shù)規(guī)劃問(wèn)題的整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題松弛問(wèn)題是指在整數(shù)規(guī)劃中去掉整數(shù)性約束是指在整數(shù)規(guī)劃中去掉整數(shù)性約束后的線性規(guī)劃問(wèn)題，求解整數(shù)規(guī)劃常常借助于松弛問(wèn)題。后的線性規(guī)劃問(wèn)題，求解整數(shù)規(guī)劃常常借助于松弛問(wèn)題。在本章中我們用在本章中我們用Z表示整數(shù)集合；表示整數(shù)集合；4.1 整數(shù)規(guī)劃模型及窮舉法整數(shù)規(guī)劃模型及窮舉法第1頁(yè)/共36頁(yè)一一. . 整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型 例例4.1 某廠生產(chǎn)甲、乙兩種大型設(shè)備，生產(chǎn)中所需物某廠生產(chǎn)甲、乙兩種大型設(shè)備，生產(chǎn)中所需物質(zhì)

3、質(zhì)A、B限制如下表所示，其他限制如下表所示，其他所需物質(zhì)和零件充足，問(wèn)所需物質(zhì)和零件充足，問(wèn)各生產(chǎn)甲、乙設(shè)備多少臺(tái)，利潤(rùn)最大？各生產(chǎn)甲、乙設(shè)備多少臺(tái)，利潤(rùn)最大？ 解：設(shè)解：設(shè)x1，x2分別為生產(chǎn)甲、乙設(shè)備的臺(tái)數(shù)，分別為生產(chǎn)甲、乙設(shè)備的臺(tái)數(shù)，z z為總利為總利潤(rùn)，則潤(rùn)，則Zxxxxxxxxtsxxz21212121210054956. .65max，654595611每臺(tái)利潤(rùn)資源數(shù)量乙甲BA第2頁(yè)/共36頁(yè)項(xiàng)目不投資項(xiàng)目投資jjxj01),.,2 , 1(10. .max11njxbxatsxczjnjjjnjjj或第3頁(yè)/共36頁(yè)例例4.4( (選址問(wèn)題選址問(wèn)題) ) 某種商品有某種商品有n個(gè)

4、銷售地，各銷售地每月個(gè)銷售地，各銷售地每月的需求量分別為的需求量分別為bj噸噸( (j=1,2,n) )?，F(xiàn)擬在?，F(xiàn)擬在m個(gè)地點(diǎn)選擇建個(gè)地點(diǎn)選擇建廠，用來(lái)生產(chǎn)這種產(chǎn)品以滿足供應(yīng)，且規(guī)定一個(gè)地址最多廠，用來(lái)生產(chǎn)這種產(chǎn)品以滿足供應(yīng)，且規(guī)定一個(gè)地址最多只能建一個(gè)工廠，若選擇第只能建一個(gè)工廠，若選擇第i個(gè)地址建廠將來(lái)生產(chǎn)能力為個(gè)地址建廠將來(lái)生產(chǎn)能力為ai噸，每月的生產(chǎn)成本為噸，每月的生產(chǎn)成本為di元元( (i=1,2,m) )。已知從第。已知從第i個(gè)工個(gè)工廠至第廠至第j個(gè)銷售地的運(yùn)價(jià)為個(gè)銷售地的運(yùn)價(jià)為cij元元/ /噸。應(yīng)如何選擇廠址和安噸。應(yīng)如何選擇廠址和安排調(diào)運(yùn)，可使總的費(fèi)用最小排調(diào)運(yùn)，可使總的費(fèi)

5、用最小? ?解：設(shè)每月從第解：設(shè)每月從第i廠至第廠至第j個(gè)銷地的運(yùn)量為個(gè)銷地的運(yùn)量為xij噸，噸，z為每月的為每月的總費(fèi)用，總費(fèi)用， 設(shè)設(shè)址不建廠第址建廠第iiyi01第4頁(yè)/共36頁(yè)則該問(wèn)題的數(shù)學(xué)模型為：則該問(wèn)題的數(shù)學(xué)模型為：10, 0),.,2 , 1(. .min11111或iijmiiijnjiiijminiiinjijijyxnjbxyaxtsydxcz例例4.1是一個(gè)全整數(shù)規(guī)劃問(wèn)題，例是一個(gè)全整數(shù)規(guī)劃問(wèn)題，例4.2是一個(gè)是一個(gè)01規(guī)劃規(guī)劃問(wèn)題，例問(wèn)題，例4.4是一個(gè)混合整數(shù)規(guī)劃問(wèn)題。是一個(gè)混合整數(shù)規(guī)劃問(wèn)題。第5頁(yè)/共36頁(yè)二二. .窮舉法窮舉法 類似于線性規(guī)劃的圖解法，對(duì)于二維線性

6、整數(shù)規(guī)劃問(wèn)類似于線性規(guī)劃的圖解法，對(duì)于二維線性整數(shù)規(guī)劃問(wèn)題，也可以用圖解法題，也可以用圖解法窮舉法。用窮舉法求解例窮舉法。用窮舉法求解例4.1Zxxxxxxxxtsxxz21212121210054956. .65max，解：解：1)1)先作出該模型的松弛問(wèn)題的可行域，并標(biāo)出可行域內(nèi)所有整數(shù)格點(diǎn)先作出該模型的松弛問(wèn)題的可行域，并標(biāo)出可行域內(nèi)所有整數(shù)格點(diǎn); ;第6頁(yè)/共36頁(yè) 2) 找出松弛問(wèn)題的解找出松弛問(wèn)題的解x=(9/4，15/4)，過(guò)最優(yōu)點(diǎn)做目標(biāo)，過(guò)最優(yōu)點(diǎn)做目標(biāo)函數(shù)的等值線，令該等值線向可行域內(nèi)保持平行移動(dòng)，首函數(shù)的等值線，令該等值線向可行域內(nèi)保持平行移動(dòng)，首先遇到的格點(diǎn)就是最優(yōu)整數(shù)解先

7、遇到的格點(diǎn)就是最優(yōu)整數(shù)解! !此問(wèn)題的最優(yōu)解是此問(wèn)題的最優(yōu)解是x* *=(3，3)，z*=33。顯然不是顯然不是松弛問(wèn)題的解松弛問(wèn)題的解4舍舍5入后的解入后的解(2,4)，該點(diǎn)不可行，也不是松弛問(wèn)題的解取整之后的解，該點(diǎn)不可行，也不是松弛問(wèn)題的解取整之后的解(2,3)，該點(diǎn)的目標(biāo)函數(shù)值是，該點(diǎn)的目標(biāo)函數(shù)值是25。第7頁(yè)/共36頁(yè)整數(shù)規(guī)劃問(wèn)題的分支定界法可以求解全整數(shù)規(guī)劃和混合整數(shù)規(guī)整數(shù)規(guī)劃問(wèn)題的分支定界法可以求解全整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題，其基本思想可描述為：劃問(wèn)題，其基本思想可描述為：1)1)首先求解相應(yīng)的松弛問(wèn)題；首先求解相應(yīng)的松弛問(wèn)題；2)2)如果最優(yōu)解不是整數(shù)解，將問(wèn)題的可行域分為兩

8、部分，如果最優(yōu)解不是整數(shù)解，將問(wèn)題的可行域分為兩部分，就是進(jìn)行就是進(jìn)行分支分支；3)3)分別求解這兩個(gè)分支可行域中的整數(shù)規(guī)劃問(wèn)題，對(duì)兩個(gè)分別求解這兩個(gè)分支可行域中的整數(shù)規(guī)劃問(wèn)題，對(duì)兩個(gè)分支重復(fù)這一分支過(guò)程，分支重復(fù)這一分支過(guò)程，當(dāng)某個(gè)分支的解是整數(shù)解，當(dāng)某個(gè)分支的解是整數(shù)解時(shí)，將此解的目標(biāo)函數(shù)值作為一個(gè)界，就是進(jìn)行時(shí)，將此解的目標(biāo)函數(shù)值作為一個(gè)界，就是進(jìn)行定界定界；4)4)在求解每個(gè)分支問(wèn)題時(shí)，如果松弛問(wèn)題在求解每個(gè)分支問(wèn)題時(shí)，如果松弛問(wèn)題無(wú)可行點(diǎn)無(wú)可行點(diǎn)或目標(biāo)或目標(biāo)函數(shù)值小于所定的函數(shù)值小于所定的界界( (極小問(wèn)題極小問(wèn)題) )，這一分支終止，否則，這一分支終止，否則繼續(xù)求解并繼續(xù)分支。繼續(xù)

9、求解并繼續(xù)分支。5)5)此求解過(guò)程可用一個(gè)二叉樹描述，原問(wèn)題的松弛問(wèn)題是此求解過(guò)程可用一個(gè)二叉樹描述，原問(wèn)題的松弛問(wèn)題是樹根，兩分支是左右子樹，終止分支的子問(wèn)題是樹葉。樹根，兩分支是左右子樹，終止分支的子問(wèn)題是樹葉。第8頁(yè)/共36頁(yè) 首先引入符號(hào)首先引入符號(hào) s 表示對(duì)表示對(duì)s 向下取整，向下取整，=s - s 表示表示s的小數(shù)部分的小數(shù)部分。 考慮如下整數(shù)規(guī)劃問(wèn)題考慮如下整數(shù)規(guī)劃問(wèn)題ZxxbAxtscxz，0. .min 設(shè)此問(wèn)題的松弛問(wèn)題的解為設(shè)此問(wèn)題的松弛問(wèn)題的解為x* *且且 ，則按如下，則按如下方式進(jìn)行分支方式進(jìn)行分支0*txZxxxxbAxtscxzt, 0. .min*Zxxxx

10、bAxtscxzt, 01. .min*第9頁(yè)/共36頁(yè)例例4.1的的整數(shù)規(guī)劃問(wèn)題的求解過(guò)程。整數(shù)規(guī)劃問(wèn)題的求解過(guò)程。此問(wèn)題的松弛問(wèn)題的解為此問(wèn)題的松弛問(wèn)題的解為x* *= =(9/4,15/4)T，x* *不是整數(shù)解。不是整數(shù)解。分支：分支：對(duì)對(duì)x1進(jìn)行分支，有如下兩個(gè)問(wèn)題：進(jìn)行分支，有如下兩個(gè)問(wèn)題：ZxxxxxxtsxxzP，054956. .65max)(2121210ZxxxxxxxtsxxzP，0254956. .65max)(12121211ZxxxxxxxtsxxzP，0354956. .65max)(12121212第10頁(yè)/共36頁(yè) 考慮兩問(wèn)題的可行考慮兩問(wèn)題的可行域，域，P

11、1的最優(yōu)點(diǎn)是的最優(yōu)點(diǎn)是x(1)=(2,35/9)T， P2的最的最優(yōu)點(diǎn)是優(yōu)點(diǎn)是x(2)=(3,3)T。顯然。顯然x(1)不是整數(shù)解，而不是整數(shù)解，而x(2)是是整數(shù)解，得出例整數(shù)解，得出例4.1的一的一個(gè)整數(shù)解。個(gè)整數(shù)解。定界：定界：當(dāng)?shù)玫揭粋€(gè)整數(shù)當(dāng)?shù)玫揭粋€(gè)整數(shù)解后可對(duì)原問(wèn)題進(jìn)行定解后可對(duì)原問(wèn)題進(jìn)行定界。界。z(2)=cx(2)=33，原問(wèn)題的界為，原問(wèn)題的界為33，此界在最大值問(wèn)題中是下，此界在最大值問(wèn)題中是下界，在最小值問(wèn)題中是上界。對(duì)界，在最小值問(wèn)題中是上界。對(duì)P1繼續(xù)分支定界，繼續(xù)分支定界， P1當(dāng)前當(dāng)前目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為10+35=45，繼續(xù)分支，得出以下兩個(gè)問(wèn)題：，繼續(xù)分支，

12、得出以下兩個(gè)問(wèn)題：第11頁(yè)/共36頁(yè)考慮兩問(wèn)題的可行域如圖：考慮兩問(wèn)題的可行域如圖：P3的最優(yōu)點(diǎn)是的最優(yōu)點(diǎn)是(2,3)T，目標(biāo)，目標(biāo)函數(shù)值是函數(shù)值是10+18=2833，停止分，停止分支；支； P4的最優(yōu)點(diǎn)是的最優(yōu)點(diǎn)是(9/5,4)T,目目標(biāo)標(biāo)函數(shù)值是函數(shù)值是9+24=33 繼續(xù)分支，繼續(xù)分支，得如下兩問(wèn)題。得如下兩問(wèn)題。ZxxxxxxxxtsxxzP，03254956.65max)(212121213ZxxxxxxxxtsxxzP，04254956.65max)(212121214第12頁(yè)/共36頁(yè)考慮兩問(wèn)題的可行域如圖：考慮兩問(wèn)題的可行域如圖：P5的最優(yōu)點(diǎn)的最優(yōu)點(diǎn)(1,40/9)T，目標(biāo)，

13、目標(biāo)函數(shù)值是函數(shù)值是5+80/3 0矛盾，從而割矛盾，從而割平面方程切割掉了平面方程切割掉了x* *及附近的可行區(qū)域。及附近的可行區(qū)域。2)2)割平面方程保留了所有整數(shù)解，如果割平面方程保留了所有整數(shù)解，如果x是原問(wèn)題的整是原問(wèn)題的整數(shù)可行解，則根據(jù)割平面方程的推導(dǎo)過(guò)程，數(shù)可行解，則根據(jù)割平面方程的推導(dǎo)過(guò)程，x顯然將顯然將滿足新的割平面方程，滿足原有方程是自然的，即滿足新的割平面方程，滿足原有方程是自然的，即沒(méi)有切割掉任何整數(shù)解。沒(méi)有切割掉任何整數(shù)解。3)3)建議取最接近建議取最接近0.5的的fi建立割平面方程。建立割平面方程。第21頁(yè)/共36頁(yè)割平面法的計(jì)算步驟：割平面法的計(jì)算步驟：1)1)

14、用單純形法求解整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題，得最優(yōu)用單純形法求解整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題，得最優(yōu)基可行解基可行解x(0)，令，令k=0=0；2)2)若若x(k)的所有分量均為整數(shù)，則即是原問(wèn)題的最優(yōu)解的所有分量均為整數(shù)，則即是原問(wèn)題的最優(yōu)解，算法停止；否則取，算法停止；否則取x(k)中最接近中最接近0.5的分量，不妨設(shè)的分量，不妨設(shè)該分量在單純形表的第該分量在單純形表的第i行，按前述方法構(gòu)造行，按前述方法構(gòu)造割平面割平面方程，并引入松弛變量方程，并引入松弛變量xn+k+1，得，得iknFjjijfxxf13)3)將該方程加入到單純形表中，同時(shí)增加對(duì)應(yīng)將該方程加入到單純形表中，同時(shí)增加對(duì)應(yīng)xn+k+1的

15、列，用對(duì)偶單純形法進(jìn)行迭代，求得新的松弛問(wèn)題的最優(yōu)基可行解的列，用對(duì)偶單純形法進(jìn)行迭代，求得新的松弛問(wèn)題的最優(yōu)基可行解x(k+1)，令，令k= =k+1+1，轉(zhuǎn)，轉(zhuǎn)2)。第22頁(yè)/共36頁(yè)例例4.7 用割平面法求解下述整數(shù)規(guī)劃問(wèn)題用割平面法求解下述整數(shù)規(guī)劃問(wèn)題Zxxxxxxtsxxz, 02452. .max212121解：化為標(biāo)準(zhǔn)型解：化為標(biāo)準(zhǔn)型Zxxxxxxxxtsxxz, 02452. .min42132121將第二個(gè)約束兩端乘以將第二個(gè)約束兩端乘以-1-1，交替使用單純形法和對(duì)偶單純形法迭代，對(duì)其松弛問(wèn)題進(jìn)行求解，得如下結(jié)果：，交替使用單純形法和對(duì)偶單純形法迭代，對(duì)其松弛問(wèn)題進(jìn)行求解，

16、得如下結(jié)果：第23頁(yè)/共36頁(yè)此松弛問(wèn)題的最優(yōu)基解為此松弛問(wèn)題的最優(yōu)基解為x=(7/6, 8/3)T， 不是整數(shù)解，用不是整數(shù)解，用所在行所在行( (第第1 1行行) )建立割平面：建立割平面：6165676161138313224145214141121*2334343432100011000014100011210145011200112101450112xxxxxxxxxxxx第24頁(yè)/共36頁(yè)引入松弛變量引入松弛變量x5，得，得0)3132(3243xx323132543xxx將此方程加入到單純形表中，如下所示：將此方程加入到單純形表中，如下所示：2121423212112616532

17、313256761611383132254321000231200001210010000100001010 xxxxxxxxxxx第25頁(yè)/共36頁(yè)x1=3/2仍不是整數(shù)解，用所在行仍不是整數(shù)解，用所在行( (第第2行行) )建立割平面：建立割平面：212121653xxx將此方程加入到最后一個(gè)單純形表中，如下所示：將此方程加入到最后一個(gè)單純形表中，如下所示：100000121010004510001110001201001000001000203120000012010010341221212121216523212112654321xxxxxxxxxxxxxx0)2121(2153xx第26頁(yè)/共36頁(yè)該單純形表給出了原問(wèn)題的最優(yōu)整數(shù)可行解該單純形表給出了原問(wèn)題的最優(yōu)整數(shù)可行解3,)2, 1(*zxT最后一個(gè)單純形表中的非基變量最后一個(gè)單純形表中的非基變量x5的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為0 0，讓進(jìn)，讓進(jìn)x5基，進(jìn)行單純形法迭代，又可得另一個(gè)最優(yōu)整數(shù)可行解：基，進(jìn)行單純形法迭代，又可得另一個(gè)最優(yōu)整數(shù)可行解：3,)1 ,2(*zxT第27頁(yè)/共36頁(yè)1.1.0-10-1規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形規(guī)劃問(wèn)題的標(biāo)準(zhǔn)