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

1、會計學(xué)1線性規(guī)劃理論與模型應(yīng)用線性規(guī)劃理論與模型應(yīng)用整數(shù)規(guī)劃問題就是決策變量取整數(shù)值的線性或非線性整數(shù)規(guī)劃問題就是決策變量取整數(shù)值的線性或非線性規(guī)劃，由于非線性整數(shù)規(guī)劃目前還沒有一般解法，因此本章規(guī)劃，由于非線性整數(shù)規(guī)劃目前還沒有一般解法，因此本章僅討論整數(shù)線性規(guī)劃。在第一章例僅討論整數(shù)線性規(guī)劃。在第一章例4中的截料問題即是一個中的截料問題即是一個整數(shù)線性規(guī)劃問題。整數(shù)線性規(guī)劃問題又可分為：整數(shù)線性規(guī)劃問題。整數(shù)線性規(guī)劃問題又可分為：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ī)劃問題的整數(shù)規(guī)劃問題的松弛問題松弛問題是指在整數(shù)規(guī)劃中去掉整數(shù)性約束是指在整數(shù)規(guī)劃中去掉整數(shù)性約束后的線性規(guī)劃問題，求解整數(shù)規(guī)劃常常借助于松弛問題。后的線性規(guī)劃問題，求解整數(shù)規(guī)劃常常借助于松弛問題。在本章中我們用在本章中我們用Z表示整數(shù)集合；表示整數(shù)集合；4.1 整數(shù)規(guī)劃模型及窮舉法整數(shù)規(guī)劃模型及窮舉法第1頁/共36頁一一. . 整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型 例例4.1 某廠生產(chǎn)甲、乙兩種大型設(shè)備，生產(chǎn)中所需物某廠生產(chǎn)甲、乙兩種大型設(shè)備，生產(chǎn)中所需物質(zhì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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