運籌學(第5章割平面)_

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

2、 簡記（） 問題 1、去掉整數(shù)約束的規(guī)劃問題 的最優(yōu)解與整數(shù)規(guī)劃的最優(yōu) 解有何關系？ 2、如何建立整數(shù)規(guī)劃模型？ 如何求解整數(shù)規(guī)劃問題？ 例5-1 求解整數(shù)規(guī)劃 (1.5, 3.33) 最優(yōu)值是最優(yōu)值是-4.83 v放松整數(shù)約束得到的線性規(guī)劃問題 為該整數(shù)規(guī)劃松弛問題 v任何一個整數(shù)規(guī)劃都可以看成是一 個線性規(guī)劃松弛問題再加上整數(shù)約 束構(gòu)成 v整數(shù)規(guī)劃的可行域是線性規(guī)劃松弛 問題可行域的一個子集. 整數(shù)規(guī)劃最優(yōu)解和線性規(guī)劃 松弛問題最優(yōu)解的關系 v對于最大化問題 松弛問題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解 v對于最小化問題 松弛問題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解 5.1整數(shù)規(guī)劃模型 1、固定費用問題 2、選擇性約束條

3、件 固定費用問題 例5-2某工廠生產(chǎn)1#、2#和3#三種產(chǎn) 品，每種產(chǎn)品需經(jīng)過三道工序，有關 信息如下表所示。若j#產(chǎn)品投產(chǎn)，無論 產(chǎn)量大或小，都需要一筆固定的費用dj， 問每種產(chǎn)品各生產(chǎn)多少，可使這一周 內(nèi)生產(chǎn)的產(chǎn)品所獲利潤最大?試建立整 數(shù)規(guī)劃模型 若固定費用dj: 100 ， 200 ， 150 定額 （工時/件） j# 每周可利用 有效工時 1#2#3# 工序A1.21.0 1.1 5400 B0.70.9 0.6 2800 C0.90.8 1.0 3600 利潤（元/件） Cj 101512 工廠生產(chǎn)信息表工廠生產(chǎn)信息表 解解 設一周內(nèi)設一周內(nèi)j產(chǎn)品的生產(chǎn)件數(shù)為產(chǎn)品的生產(chǎn)件數(shù)為xj

4、若不考慮固定費用若不考慮固定費用 max f= 10 x1+15x2+12x3 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. 又設又設0-1變量變量 本問題的數(shù)學模型（本問題的數(shù)學模型（ 考慮固定費用考慮固定費用 ） 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 x336

5、00 xj0, j=1,2,3. 其中其中M為充分大的正數(shù)為充分大的正數(shù) 1,0 12 3 0 j j x yj 當， ， ， ，否則， 12 3 jj xMyj， ， 選擇性約束條件選擇性約束條件 例例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)在模型中？件如

6、何體現(xiàn)在模型中？ 0, 1 y 選擇材料甲， ，否則。 約束條件約束條件 2x1+5x2 +6x3 180+My 4x1+3x2 +7x3 240+M(1-y) 其中其中M為充分大的正數(shù)為充分大的正數(shù) 解解 引進引進0-1變量變量 例例5-10 旅行售貨員問題旅行售貨員問題 P151 52 純整數(shù)規(guī)劃的割平面法 521割平面法的幾何特征 記（AIP）的可行域為KAIPAIP。若將（AIP）中 要求變量為整數(shù)這個約束去掉，則得到相應的 線性規(guī)劃（LP），記（LP）的可行域為KLPLP。 例5-13求解下列（AIP）： min f= -7x1-9x2 s.t. -x1 +3x2 6 7x1 + x

7、2 35 xj0, 整數(shù)， j=1,2。 介紹一些相關概念介紹一些相關概念 522 柯莫利割柯莫利割 設設B為為(LP)的一個基，的一個基，X為為(AIP)的一個可的一個可 行解由行解由KAIP KLP，所以，所以x也是也是(LP)的一個的一個 可行解，因此，可行解，因此，x應滿足單純形表應滿足單純形表T(B)所表示所表示 的方程組：的方程組： (1) 該條件是該條件是(AIP)任何一個可行解任何一個可行解x必須滿足的必須滿足的 條件，我們稱它為條件，我們稱它為柯莫利割柯莫利割 (2) (1)-(2)得： 例5-14用割平面法求解例513 min f= -7x1-9x2 s.t. -x1 +3

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