混合整數(shù)線性規(guī)劃

1、混合整數(shù)線性規(guī)劃張冰hbingjmaiLsysii 優(yōu)化問(wèn)題的一般形式優(yōu)化問(wèn)題三要素：決策變量；目標(biāo)函數(shù)；約束條件_r:一目標(biāo)函數(shù) min /(x)約束條件s.t. hf(x) = 0,z = 1，mg jM 0, j = 1,，/一決策變量g D cz 9? 7變量類型C連續(xù)變量：溫度、壓力和流程等，通常稱為操作變量決策變量Y離散變量：設(shè)備和流程選擇 等，通常稱為結(jié)構(gòu)變量5整數(shù)規(guī)劃問(wèn)題整數(shù)規(guī)劃問(wèn)題(IP):是指要求部分或全部決策變量的取值為整數(shù)的規(guī)劃問(wèn)題。松弛問(wèn)題：不考慮整數(shù)條件，由余下的 目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題。學(xué)習(xí)重點(diǎn)：整數(shù)線性規(guī)劃問(wèn)題(MIP)ma

2、x(min)Z =c jxj= inE a ij x j 5( = )b i7=1n 巧中取部分或全部為整數(shù)若變量全部取整數(shù)，稱此為純整數(shù)規(guī)劃。若其中 僅部分變量要求取整數(shù)，則稱為混合整數(shù)規(guī)劃，其解 法較一般線性規(guī)劃的解法要復(fù)雜些。9背包問(wèn)題(Knapsack Problem)一個(gè)旅行者，為了準(zhǔn)備旅行的必須用品，要在背包內(nèi)裝一些最有用的東西，但有個(gè)限制，最 多只能裝b公斤的物品,而每件物品只能整個(gè) 攜帶，這樣旅行者給每件物品規(guī)定了一個(gè)“價(jià)值”以表示其有用的程度，如果共有n件物品,第j件物品aj公斤，其價(jià)值為q.問(wèn)題變成:在 攜帶的物品總重量不超過(guò)b公斤條件下，攜帶 哪些物品，可使總價(jià)值最大？/

3、11解：如果令Xj=l表示攜帶物品j, Xj=O表示不攜帶物品j,則問(wèn)題表 示成Q-1規(guī)劃：Max Z = E CjXjs. t. EajXj bXj=O 或 1解法概述 當(dāng)人們開(kāi)始接觸整數(shù)規(guī)劃問(wèn)題時(shí)，常會(huì) 有如下兩種初始想法： 因?yàn)榭尚蟹桨笖?shù)目有限，因此經(jīng)過(guò)一一 比較后，總能求出最好方案，例如，背 包問(wèn)題充其量有21種方式；實(shí)際上這種 方法是不可行。13假設(shè)有35件物品,計(jì)算機(jī)每秒能比較10000個(gè)方式,那么要比較完234種方式，大約需要20天!先放棄變量的整數(shù)性要求，解一個(gè) 線性規(guī)劃問(wèn)題，然后用“四舍五入” 法取整數(shù)解，這種方法，只有在變 量的取值很大時(shí)，才有成功的可能 性，而當(dāng)變量的取值

4、較小時(shí)，特別 是0-1規(guī)劃時(shí)，往往不能成功。可行域OABD內(nèi)整數(shù)點(diǎn)，放棄整數(shù)要求后，最優(yōu) 解B(92, 2. 4)Z0=58. 8,而原整數(shù)規(guī)劃最優(yōu)解1(2, 4)Z0=58 ,實(shí)際上B附近四個(gè)整點(diǎn)(9, 2) (10, 2) (9, 3) (10, 3)都不是原規(guī)劃最優(yōu)解。max z = 5% +8x2s.t. X + x9 65x +9x2 0且為整數(shù)去掉整數(shù)限制后，可行域?yàn)辄c(diǎn)(0,0)，(6,0)，(0,5)，P (2.25,3-75)圍成的4邊形IP最優(yōu)解pP的舍入解最靠近P的可行解IP最優(yōu)解(2.25, 3.75)(2, 4)(2, 3)(0, 5)z=41.25不可行z=34z=4

5、O假如能求出可行域的“整點(diǎn)凸包，(包含所有整點(diǎn)的最小多邊形OEFGHIJ),則可在此凸包上求線性規(guī)劃的解，即為原問(wèn)題的解。但求“整點(diǎn)凸包，十分困難。X221整數(shù)規(guī)劃問(wèn)題對(duì)應(yīng)的松弛問(wèn)題取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對(duì) 應(yīng)的連續(xù)優(yōu)化問(wèn)題稱為原問(wèn)題的松弛問(wèn)題整數(shù)規(guī)劃問(wèn)題松弛1 f松弛問(wèn)題原問(wèn)題松弛丿最優(yōu)解.優(yōu)整數(shù)非整數(shù)下界（對(duì)Min問(wèn)題）上界（對(duì)Max問(wèn)題）混合整數(shù)線性規(guī)劃的分支定界法（BB: Branch and Bound ）基本思想：隱式地枚舉一切可行解（“分而治之”）所謂分支，就是逐次對(duì)解空間（可行域）進(jìn)行劃分；而 所謂定界，是指對(duì)于每個(gè)分支（或稱子域）,要計(jì)算原 問(wèn)題的最優(yōu)解

6、的下界（對(duì)極小化問(wèn)題）.這些下界用來(lái) 在求解過(guò)程中判定是否需要對(duì)目前的分支進(jìn)一步劃分, 也就是盡可能去掉一些明顯的非最優(yōu)點(diǎn)，避免完全枚舉.對(duì)于極小化問(wèn)題，在子域上解LP,其最優(yōu)值是IP限定 在該子域時(shí)的下界；IP任意可行點(diǎn)的函數(shù)值是IP的上界23定界：為求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn) 題(A),先求出其松弛問(wèn)題(B)的最優(yōu)解， 作為問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值的下界，同時(shí) 選擇任意整數(shù)可行解作為A的最優(yōu)目標(biāo)函數(shù) 值的上界。分支：將應(yīng)為整數(shù)解，但尚是非整數(shù)解之一 的決策變量取值分區(qū)，并入松弛問(wèn)題中，形 成兩個(gè)分支松弛問(wèn)題，分別求解。依結(jié)果考 調(diào)整上下界。JImin z =坷 + 3x2 x2 3.13

7、R: 8.12 和兀1 9和X1 9R、: 3.1322兀 +34%n 285Xj 8R2: 3.1322jT +34x2 285（2 ）在尺內(nèi)求最優(yōu)，得:= 9,x2 = 3.13, zmin = LB2 = 18.39#(3) 同樣地，在 鳥(niǎo)內(nèi)求最優(yōu)，得：坷二& 兀2 = 3.12, zmin = LB3 = 17.62(4) 由于(2)、(3)所得的解都不是整數(shù)解，且S VLB?,所以乙価在&內(nèi)的值就可能比在尺 內(nèi)的值小，于是進(jìn)一步將盡分成兩個(gè)區(qū)域,注意到 由(3)所得的非整數(shù)解西=3.21 ,且要求勺是整數(shù)，曹 對(duì)尺追加條件2 4和勺3,對(duì)應(yīng)地將 尺分成坨1 和 22(5) 求出R2X

8、內(nèi)的最優(yōu)解：円=6.77 心=4，贏=LB4 =18.77(在R22中因新的約束x2 3.13 解.矛盾，故R22(6) 對(duì)區(qū)域K和/?21進(jìn)行比LB24和兀23,對(duì)應(yīng)地得到兩個(gè)約束區(qū)域:xx9x2 3.1322 + 34兀2 285Rj%! 9 x9 3.1322xj + 34x2 285(7) 盡2顯然無(wú)可行解，在中的最優(yōu)解是：西=7,花=4,牯=LB5 =21這個(gè)解滿足整數(shù)解的條件，但是否是最優(yōu)解 呢？因有l(wèi)b4lb5 ,故最優(yōu)解可能位于心 中.對(duì)心分別追加條件旺7和x6 ,心又 分成兩不局部區(qū)域7?211和尺212。人211中的最優(yōu)解是：= 7, x2 = 4,4山=LB& = 19尺

9、212的最優(yōu)解是：兀=6,吃=4.5, Zmjn = LB-j 19.5可見(jiàn)，凡11中的最優(yōu)解滿足整數(shù)條件。同時(shí),目標(biāo)函數(shù)的下限值LB.比其它局部區(qū)域的下限值小，即:LB6 LB LB5所以人212或沒(méi)有必要進(jìn)一步搜索, 因此，最后得到所求的最優(yōu)整數(shù)解為：兀7，；2 =4,務(wù)=感=19MaxZ=4 Oxt+90x 29x7x2 W56 7x1+20x2 70 xpx20xpx2 都為整數(shù)35問(wèn)題BZ=356x2=4.81 9x2=L82 Z=356問(wèn)題Bx1=4x2=2.1 Z=349問(wèn)題B 2Xj=5 2=1.57 Z-341Z=349Z=0問(wèn)題B3兀1=4, x2=2 Z=340問(wèn)題B4 x i=1.42 工2=3 Z=327問(wèn)題B5 x 1=544 兀2=1 Z=308Z=349Z=340問(wèn)題 6 無(wú)可行 解ZJ34037作業(yè):現(xiàn)有資金總額為?？晒┻x擇購(gòu)買的化工產(chǎn)品有兀#個(gè)，產(chǎn)品j的價(jià)格和預(yù)期利潤(rùn)分別為幻和q,此外, 因供貨商對(duì)產(chǎn)品的采購(gòu)約束，有3個(gè)附加條件： 第一，若選擇產(chǎn)品1必須同時(shí)選擇項(xiàng)目2,反之,