整數(shù)規(guī)劃方法

1、1 整數(shù)規(guī)劃的一般模型；整數(shù)規(guī)劃的一般模型； 整數(shù)規(guī)劃解的求解方法；整數(shù)規(guī)劃解的求解方法； 整數(shù)規(guī)劃的整數(shù)規(guī)劃的軟件求解方法；軟件求解方法； 0-10-1規(guī)劃的模型與求解方法；規(guī)劃的模型與求解方法； 整數(shù)規(guī)劃的應(yīng)用案例分析。整數(shù)規(guī)劃的應(yīng)用案例分析。 2 1. 問題的提出問題的提出:固定資源分配問題固定資源分配問題3 4 在這個(gè)問題中，所求解均是整數(shù)，初看起來，在這個(gè)問題中，所求解均是整數(shù)，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整舍入化整”就可以了，實(shí)際上這常常是不行的，就可以了，實(shí)際上這常常是不行的，因?yàn)榛蟛灰姷檬强尚薪?，或雖是可

2、行解但不因?yàn)榛蟛灰姷檬强尚薪?，或雖是可行解但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整數(shù)規(guī)劃。數(shù)規(guī)劃。 整數(shù)規(guī)劃中如果所有的變量都限制為（非負(fù)）整數(shù)規(guī)劃中如果所有的變量都限制為（非負(fù)）整數(shù)，稱為純整數(shù)規(guī)劃；如果僅一部分變量限制整數(shù)，稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，稱為混合整數(shù)規(guī)劃；整數(shù)規(guī)劃一種特殊為整數(shù)，稱為混合整數(shù)規(guī)劃；整數(shù)規(guī)劃一種特殊的情形是的情形是0-1規(guī)劃，它的變量取值僅限于規(guī)劃，它的變量取值僅限于0和和1。5 2. 整數(shù)規(guī)劃模型的一般形式整數(shù)規(guī)劃模型的一般形式 問題是如何求解整數(shù)規(guī)劃問題呢？問題是如何求解整數(shù)規(guī)劃問題呢？能否

3、設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？實(shí)際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題實(shí)際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題6 1 .分枝定界法的基本思想分枝定界法的基本思想 7 1 .分枝定界法的基本思想分枝定界法的基本思想 繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止止。 8 2. 分枝定界法一般步驟分枝定界法一般步驟 問題問題(B)(B)無可行解，則無可行解，則(A)(A)也無可行解，停止；也無可行解，停止； 9 2. 分枝定界法一

4、般步驟分枝定界法一般步驟 10 2. 分枝定界法一般步驟分枝定界法一般步驟 11 2.分枝定界法一般步驟分枝定界法一般步驟 分枝定界法分枝定界法.ppt12 3. 割平面法的思想割平面法的思想 將原整數(shù)規(guī)劃問題將原整數(shù)規(guī)劃問題(A)(A)去掉整數(shù)約束變?yōu)榫€性規(guī)去掉整數(shù)約束變?yōu)榫€性規(guī)劃問題劃問題(B)(B)，引入線性約束條件，引入線性約束條件( (稱為稱為GomoryGomory約束約束，幾何術(shù)語割平面幾何術(shù)語割平面) )使問題使問題(B)(B)的可行域逐步縮小的可行域逐步縮小. . 每次切割掉的是問題非整數(shù)解的一部分，不切每次切割掉的是問題非整數(shù)解的一部分，不切掉任何整數(shù)解，直到最后使目標(biāo)函數(shù)

5、達(dá)到最優(yōu)的整掉任何整數(shù)解，直到最后使目標(biāo)函數(shù)達(dá)到最優(yōu)的整數(shù)解成為可行域的一個(gè)頂點(diǎn)時(shí)，即問題最優(yōu)解。數(shù)解成為可行域的一個(gè)頂點(diǎn)時(shí)，即問題最優(yōu)解。 利用線性規(guī)劃的求解方法逐步縮小可行域，最利用線性規(guī)劃的求解方法逐步縮小可行域，最后找到整數(shù)規(guī)劃的最優(yōu)解。后找到整數(shù)規(guī)劃的最優(yōu)解。 考慮純整數(shù)規(guī)劃問題：考慮純整數(shù)規(guī)劃問題：取整數(shù)jjinjjijnjjjxnjxmibxaxcz, 2 , 10, 1max11設(shè)其中設(shè)其中aij和和bi皆為整數(shù)（若不為整數(shù)時(shí)，可乘上一個(gè)倍數(shù)化皆為整數(shù)（若不為整數(shù)時(shí)，可乘上一個(gè)倍數(shù)化為整數(shù)）。為整數(shù)）。割平面法是割平面法是R.E.Gomory于于1958年提出的一種方法，它主要

6、年提出的一種方法，它主要用于求解純用于求解純ILP。 割平面法是用增加新的約束來切割可行域，增加的新約束割平面法是用增加新的約束來切割可行域，增加的新約束稱為割平面方程或切割方程。其稱為割平面方程或切割方程。其基本思路為：基本思路為： 若其松弛問題的最優(yōu)解若其松弛問題的最優(yōu)解X*不滿足整數(shù)約束，則從不滿足整數(shù)約束，則從X*的的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件，將其非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件，將其加入原松弛問題中，形成一個(gè)新的線性規(guī)劃，然后求解之加入原松弛問題中，形成一個(gè)新的線性規(guī)劃，然后求解之。若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu)。若新的最優(yōu)解滿足整數(shù)

7、要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。解；否則重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應(yīng)當(dāng)兩為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應(yīng)當(dāng)兩個(gè)基本性質(zhì)：個(gè)基本性質(zhì)：（1）已獲得的不符合整數(shù)要求的）已獲得的不符合整數(shù)要求的LP最優(yōu)解不滿足該線性最優(yōu)解不滿足該線性約束條件，從而不可能在以后的解中出現(xiàn)；約束條件，從而不可能在以后的解中出現(xiàn)；（2）凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)）凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)解始終被保留在每次剩余的線性規(guī)劃可行域中。解始終被保留在每次剩余的線性規(guī)劃可行域中。

8、 是整數(shù)2121212121,0,431. .maxxxxxxxxxtsxxz例例1 用割平面法求解整數(shù)規(guī)劃問題用割平面法求解整數(shù)規(guī)劃問題0,431. .max432142132121xxxxxxxxxxtsxxz步驟步驟1：標(biāo)準(zhǔn)化其松弛問題：標(biāo)準(zhǔn)化其松弛問題B0Cj1100CBXBbx1x2x3x411x2x17/43/401103/41/41/41/4cj-zj001/21/2引進(jìn)一個(gè)割平面來縮小可行域，割平面要切去松弛問題的非整引進(jìn)一個(gè)割平面來縮小可行域，割平面要切去松弛問題的非整數(shù)最優(yōu)解而又不要切去問題的的任一個(gè)整數(shù)可行解。數(shù)最優(yōu)解而又不要切去問題的的任一個(gè)整數(shù)可行解。 步驟步驟2：求

9、一個(gè)割平面方程：求一個(gè)割平面方程（1）在最終表上任選一個(gè)含有不滿足整數(shù)條件基變量的）在最終表上任選一個(gè)含有不滿足整數(shù)條件基變量的約束方程。如選約束方程。如選x1，則含，則含x1的約束方程為的約束方程為)3(434141431xxx（2）將所選擇的約束方程中非基變量的系數(shù)及常數(shù)項(xiàng)進(jìn)行）將所選擇的約束方程中非基變量的系數(shù)及常數(shù)項(xiàng)進(jìn)行拆分處理。具體規(guī)則是：將上述系數(shù)和常數(shù)項(xiàng)均拆分成一個(gè)拆分處理。具體規(guī)則是：將上述系數(shù)和常數(shù)項(xiàng)均拆分成一個(gè)整數(shù)加上一個(gè)非負(fù)真分?jǐn)?shù)（純小數(shù)）之和。則（整數(shù)加上一個(gè)非負(fù)真分?jǐn)?shù)（純小數(shù)）之和。則（3）式變?yōu)椋┦阶優(yōu)椋?4(430410431431xxx很明顯，（很明顯，（5）左

10、端為整數(shù)，右端）左端為整數(shù)，右端=b(i);); for(arrange(j):x(j)=0;); for(arrange(j):BIN(x(j);); END 11min(1,2,)01(1,2, )njjjnijjijjzc xa xb imxorjn34 1. 問題的提出問題的提出35實(shí)驗(yàn)室開放時(shí)間為上午實(shí)驗(yàn)室開放時(shí)間為上午8:008:00至晚上至晚上10:00;10:00;開放時(shí)間內(nèi)須有且僅段一名學(xué)生值班開放時(shí)間內(nèi)須有且僅段一名學(xué)生值班; ;規(guī)定大學(xué)生每周值班不少于規(guī)定大學(xué)生每周值班不少于8 8小時(shí)小時(shí); ;研究生每周值班不少于研究生每周值班不少于7 7小時(shí)小時(shí); ;每名學(xué)生每周值班不超每名學(xué)生每周值班不超3 3次次; ;每次值班不少于每次值班不少于2 2小時(shí)小時(shí); ;每天安排值班的學(xué)生不超過每天安排值班的學(xué)生不超過3 3人，且其中必須人，且其中必須有一名研究生有一名研究生. . 試為該實(shí)驗(yàn)室安排一張人員的值班表，使總試為該實(shí)驗(yàn)室安排一張人員的值班表，使總支付的報(bào)酬這最少。支付的報(bào)酬這最少。 1. 問題的提出