運(yùn)籌學(xué)(第5章割平面)_

1、第五章整數(shù)規(guī)劃51整數(shù)規(guī)劃模型 52純整數(shù)規(guī)劃的割平面法54分支定界法57最優(yōu)分配問題本章基本要求v掌握整數(shù)規(guī)劃的數(shù)學(xué)模型的建摸技巧；v掌握0-1規(guī)劃模型v了解割平面公式；v掌握分支定界法；v掌握匈牙利法解決最優(yōu)分配問題。 整數(shù)規(guī)劃v整數(shù)規(guī)劃：決策變量全體或部分約束為整數(shù)的數(shù)學(xué)規(guī)劃問題.v整數(shù)規(guī)劃又分線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃.v線性整數(shù)規(guī)劃也叫整數(shù)線性規(guī)劃(ILP),簡(jiǎn)稱整數(shù)規(guī)劃,簡(jiǎn)記(IP).整數(shù)線性規(guī)劃的分類v純整數(shù)規(guī)劃:所有的決策變量均取整數(shù).簡(jiǎn)記（）v混合整數(shù)規(guī)劃:只有部分決策變量取整數(shù)值.簡(jiǎn)記（）v0-1整數(shù)規(guī)劃:整數(shù)變量只能取0或1.簡(jiǎn)記（）問題1、去掉整數(shù)約束的規(guī)劃問題的最優(yōu)

2、解與整數(shù)規(guī)劃的最優(yōu)解有何關(guān)系？ 2、如何建立整數(shù)規(guī)劃模型？如何求解整數(shù)規(guī)劃問題？例5-1 求解整數(shù)規(guī)劃(1.5, 3.33)最優(yōu)值是最優(yōu)值是-4.83v放松整數(shù)約束得到的線性規(guī)劃問題為該整數(shù)規(guī)劃松弛問題v任何一個(gè)整數(shù)規(guī)劃都可以看成是一個(gè)線性規(guī)劃松弛問題再加上整數(shù)約束構(gòu)成v整數(shù)規(guī)劃的可行域是線性規(guī)劃松弛問題可行域的一個(gè)子集.整數(shù)規(guī)劃最優(yōu)解和線性規(guī)劃松弛問題最優(yōu)解的關(guān)系v對(duì)于最大化問題松弛問題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解v對(duì)于最小化問題松弛問題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解5.1整數(shù)規(guī)劃模型1、固定費(fèi)用問題 2、選擇性約束條件 固定費(fèi)用問題例5-2某工廠生產(chǎn)1#、2#和3#三種產(chǎn)品，每種產(chǎn)品需經(jīng)過三道工序，有關(guān)信息

3、如下表所示。若j#產(chǎn)品投產(chǎn)，無論產(chǎn)量大或小，都需要一筆固定的費(fèi)用dj，問每種產(chǎn)品各生產(chǎn)多少，可使這一周內(nèi)生產(chǎn)的產(chǎn)品所獲利潤(rùn)最大?試建立整數(shù)規(guī)劃模型若固定費(fèi)用dj: 100 ， 200 ， 150定額（工時(shí)/件）j# 每周可利用有效工時(shí)1#2#3#工序A1.21.0 1.1 5400B0.70.9 0.6 2800C0.90.8 1.0 3600利潤(rùn)（元/件）Cj101512工廠生產(chǎn)信息表工廠生產(chǎn)信息表解解 設(shè)一周內(nèi)設(shè)一周內(nèi)j產(chǎn)品的生產(chǎn)件數(shù)為產(chǎn)品的生產(chǎn)件數(shù)為xj若不考慮固定費(fèi)用若不考慮固定費(fèi)用 max f= 10 x1+15x2+12x3 s.t . 1.2x1+1.0 x2 +1.1x3 54

4、00 0.7x1+0.9x2 +1.0 x3 2800 0.9x1 +0.8x2+ 1.0 x33600 xj0, j=1,2,3.又設(shè)又設(shè)0-1變量變量 本問題的數(shù)學(xué)模型（本問題的數(shù)學(xué)模型（ 考慮固定費(fèi)用考慮固定費(fèi)用 ） max f= 10 x1+15x2+12x3-100y1-200y2-150y3 s.t . 1.2x1+1.0 x2 +1.1x3 5400 0.7x1+0.9x2 +1.0 x3 2800 0.9x1 +0.8x2+ 1.0 x33600 xj0, j=1,2,3. 其中其中M為充分大的正數(shù)為充分大的正數(shù) 1,012 30jjxyj當(dāng)， ，否則，12 3jjxMyj，

5、，選擇性約束條件選擇性約束條件例例5-3某工廠生產(chǎn)第某工廠生產(chǎn)第j種產(chǎn)品的數(shù)量為種產(chǎn)品的數(shù)量為xj,j=1,2,3.其使用的材料在材料甲及材料乙中其使用的材料在材料甲及材料乙中選擇一種選擇一種。材料消耗的約束條件分別為。材料消耗的約束條件分別為 2x1+5x2 +6x3 180或或 4x1+3x2 +7x3 240，（其他資源未列出），試問這類選擇性約束條（其他資源未列出），試問這類選擇性約束條件如何體現(xiàn)在模型中？件如何體現(xiàn)在模型中？0,1y選擇材料甲，否則。 約束條件約束條件 2x1+5x2 +6x3 180+My 4x1+3x2 +7x3 240+M(1-y) 其中其中M為充分大的正數(shù)為充

6、分大的正數(shù)解解 引進(jìn)引進(jìn)0-1變量變量例例5-10 旅行售貨員問題旅行售貨員問題 P15152 純整數(shù)規(guī)劃的割平面法521割平面法的幾何特征記（AIP）的可行域?yàn)镵AIPAIP。若將（AIP）中要求變量為整數(shù)這個(gè)約束去掉，則得到相應(yīng)的線性規(guī)劃（LP），記（LP）的可行域?yàn)镵LPLP。例5-13求解下列（AIP）：min f= -7x1-9x2s.t. -x1 +3x2 6 7x1 + x2 35 xj0, 整數(shù)， j=1,2。介紹一些相關(guān)概念介紹一些相關(guān)概念522 柯莫利割柯莫利割設(shè)設(shè)B為為(LP)的一個(gè)基，的一個(gè)基，X為為(AIP)的一個(gè)可的一個(gè)可行解由行解由KAIP KLP，所以，所以x也

7、是也是(LP)的一個(gè)的一個(gè)可行解，因此，可行解，因此，x應(yīng)滿足單純形表應(yīng)滿足單純形表T(B)所表示所表示的方程組：的方程組：(1)該條件是該條件是(AIP)任何一個(gè)可行解任何一個(gè)可行解x必須滿足的必須滿足的條件，我們稱它為條件，我們稱它為柯莫利割柯莫利割(2)(1)-(2)得：例5-14用割平面法求解例513 min f= -7x1-9x2s.t. -x1 +3x2 6 7x1 + x2 35 xj0, 整數(shù)， j=1,2。解引進(jìn)松弛變量x3和x4，將問題化成標(biāo)準(zhǔn)型： min f= -7x1-9x2s.t. -x1 +3x2 + x3 = 6 7x1 + x2 + x4 = 35 xj0, 整

8、數(shù)， j=1,，4。因?yàn)樗沙谧兞?x3=6+ x1-3x2，x4=35-7xl-x2，所以當(dāng)x1和x2為整數(shù)時(shí)，x3和x4也一定是整數(shù)應(yīng)用單純形法求解相應(yīng)的線性規(guī)劃(LP)，得最優(yōu)表（5-23）（5-24）應(yīng)用對(duì)偶單純形法應(yīng)用對(duì)偶單純形法于是，X*=（x1，x2）T=（4，3）T 最優(yōu)值f*=-55。5.2.3柯莫利割平面法v割平面法的基本思路：先用單純形法解松弛問題，得最優(yōu)解0，如果0是整數(shù)，則問題已經(jīng)解決，如果不全是整數(shù)，給松弛問題一個(gè)線性約束條件割平面方程，它將松弛問題的可行域割去一塊，且這個(gè)0恰被割去,原問題的可行解都不會(huì)被割去.把松弛問題的最優(yōu)表添加割約束,得改進(jìn)的松弛問題,用對(duì)偶單純形法求解,直至最優(yōu)解為整數(shù)