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

2、行解但不因為化整后不見得是可行解，或雖是可行解但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整數(shù)規(guī)劃。數(shù)規(guī)劃。 整數(shù)規(guī)劃中如果所有的變量都限制為（非負）整數(shù)規(guī)劃中如果所有的變量都限制為（非負）整數(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ù)約束，即變?yōu)榫€性能否設想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進行取整處理呢？規(guī)劃問題求解，再對其最優(yōu)解進行取整處理呢？實際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題實際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題6 1 .分枝定界法的基本思想分枝定界法的基本思想 7 1 .分枝定界法的基本思想分枝定界法的基本思想 繼續(xù)求解定界，重復下去，直到得到最優(yōu)解為繼續(xù)求解定界，重復下去，直到得到最優(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約束約束，幾何術語割平面幾何術語割平面) )使問題使問題(B)(B)的可行域逐步縮小的可行域逐步縮小. . 每次切割掉的是問題非整數(shù)解的一部分，不切每次切割掉的是問題非整數(shù)解的一部分，不切掉任何整數(shù)解，直到最后使目標函數(shù)

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

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

7、要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則重復上述步驟，直到獲得整數(shù)最優(yōu)解為止。解；否則重復上述步驟，直到獲得整數(shù)最優(yōu)解為止。為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應當兩為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應當兩個基本性質：個基本性質：（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：標準化其松弛問題：標準化其松弛問題B0Cj1100CBXBbx1x2x3x411x2x17/43/401103/41/41/41/4cj-zj001/21/2引進一個割平面來縮小可行域，割平面要切去松弛問題的非整引進一個割平面來縮小可行域，割平面要切去松弛問題的非整數(shù)最優(yōu)解而又不要切去問題的的任一個整數(shù)可行解。數(shù)最優(yōu)解而又不要切去問題的的任一個整數(shù)可行解。 步驟步驟2：求

9、一個割平面方程：求一個割平面方程（1）在最終表上任選一個含有不滿足整數(shù)條件基變量的）在最終表上任選一個含有不滿足整數(shù)條件基變量的約束方程。如選約束方程。如選x1，則含，則含x1的約束方程為的約束方程為)3(434141431xxx（2）將所選擇的約束方程中非基變量的系數(shù)及常數(shù)項進行）將所選擇的約束方程中非基變量的系數(shù)及常數(shù)項進行拆分處理。具體規(guī)則是：將上述系數(shù)和常數(shù)項均拆分成一個拆分處理。具體規(guī)則是：將上述系數(shù)和常數(shù)項均拆分成一個整數(shù)加上一個非負真分數(shù)（純小數(shù)）之和。則（整數(shù)加上一個非負真分數(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實驗室開放時間為上午實驗室開放時間為上午8:008:00至晚上至晚上10:00;10:00;開放時間內(nèi)須有且僅段一名學生值班開放時間內(nèi)須有且僅段一名學生值班; ;規(guī)定大學生每周值班不少于規(guī)定大學生每周值班不少于8 8小時小時; ;研究生每周值班不少于研究生每周值班不少于7 7小時小時; ;每名學生每周值班不超每名學生每周值班不超3 3次次; ;每次值班不少于每次值班不少于2 2小時小時; ;每天安排值班的學生不超過每天安排值班的學生不超過3 3人，且其中必須人，且其中必須有一名研究生有一名研究生. . 試為該實驗室安排一張人員的值班表，使總試為該實驗室安排一張人員的值班表，使總支付的報酬這最少。支付的報酬這最少。 1. 問題的提出