整數(shù)規(guī)劃方法ppt課件.ppt

《整數(shù)規(guī)劃方法ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第十一章整數(shù)規(guī)劃方法第十一整數(shù)規(guī)劃方法整數(shù)規(guī)劃的一般模型；整數(shù)規(guī)劃解的求解方法；整數(shù)規(guī)劃的軟件求解方法；0-1規(guī)劃的模型與求解方法；整數(shù)規(guī)劃的應(yīng)用案例分析。1一、整數(shù)規(guī)劃的一般模型21.問題的提出:固定資源分配問題3固定資源分配問題一、整數(shù)規(guī)劃的一般模型在這個(gè)問題中，所求解均是整數(shù)，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整”就可以了，實(shí)際上這常常是不行的，因?yàn)榛蟛灰姷檬强尚薪猓螂m是可行解但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整數(shù)規(guī)劃。整數(shù)規(guī)劃中如果所有的變量都限制為（非負(fù)）整數(shù)，稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)

2、，稱為混合整數(shù)規(guī)劃；整數(shù)規(guī)劃一種特殊的情形是0-1規(guī)劃，它的變量取值僅限于0和1。452.整數(shù)規(guī)劃模型的一般形式一、整數(shù)規(guī)劃的一般模型問題是如何求解整數(shù)規(guī)劃問題呢？能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對(duì)其最優(yōu)解進(jìn)行取整處理呢？實(shí)際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題．61.分枝定界法的基本思想二、整數(shù)規(guī)劃求解方法71.分枝定界法的基本思想繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止。二、整數(shù)規(guī)劃求解方法82.分枝定界法一般步驟問題(B)無可行解，則(A)也無可行解，停止；二、整數(shù)規(guī)劃求解方法92.分枝定界法一般步驟二、整數(shù)規(guī)劃求解方

3、法102.分枝定界法一般步驟二、整數(shù)規(guī)劃求解方法112.分枝定界法一般步驟二、整數(shù)規(guī)劃求解方法分枝定界法.ppt123.割平面法的思想將原整數(shù)規(guī)劃問題(A)去掉整數(shù)約束變?yōu)榫€性規(guī)劃問題(B)，引入線性約束條件(稱為Gomory約束，幾何術(shù)語割平面)使問題(B)的可行域逐步縮小.每次切割掉的是問題非整數(shù)解的一部分，不切掉任何整數(shù)解，直到最后使目標(biāo)函數(shù)達(dá)到最優(yōu)的整數(shù)解成為可行域的一個(gè)頂點(diǎn)時(shí)，即問題最優(yōu)解。利用線性規(guī)劃的求解方法逐步縮小可行域，最后找到整數(shù)規(guī)劃的最優(yōu)解。二、整數(shù)規(guī)劃求解方法考慮純整數(shù)規(guī)劃問題：設(shè)其中aij和bi皆為整數(shù)（若不為整數(shù)時(shí)，可乘上一

4、個(gè)倍數(shù)化為整數(shù)）。割平面法是R.E.Gomory于1958年提出的一種方法，它主要用于求解純ILP。割平面法是用增加新的約束來切割可行域，增加的新約束稱為割平面方程或切割方程。其基本思路為：若其松弛問題的最優(yōu)解X*不滿足整數(shù)約束，則從X*的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件，將其加入原松弛問題中，形成一個(gè)新的線性規(guī)劃，然后求解之。若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應(yīng)當(dāng)兩個(gè)基本性質(zhì)：（1）已獲得的不符合整數(shù)要求的LP最優(yōu)解不滿足該線性約束條件

5、，從而不可能在以后的解中出現(xiàn)；（2）凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)解始終被保留在每次剩余的線性規(guī)劃可行域中。例1用割平面法求解整數(shù)規(guī)劃問題步驟1：標(biāo)準(zhǔn)化其松弛問題B0Cj?1100CBXBbx1x2x3x411x2x17/43/401103/4－1/41/41/4cj-zj00－1/2－1/2引進(jìn)一個(gè)割平面來縮小可行域，割平面要切去松弛問題的非整數(shù)最優(yōu)解而又不要切去問題的的任一個(gè)整數(shù)可行解。步驟2：求一個(gè)割平面方程（1）在最終表上任選一個(gè)含有不滿足整數(shù)條件基變量的約束方程。如選x1，則含x1的約束方程為（2）將所選擇的約束方程中非基變量

6、的系數(shù)及常數(shù)項(xiàng)進(jìn)行拆分處理。具體規(guī)則是：將上述系數(shù)和常數(shù)項(xiàng)均拆分成一個(gè)整數(shù)加上一個(gè)非負(fù)真分?jǐn)?shù)（純小數(shù)）之和。則（3）式變?yōu)椋汉苊黠@，（5）左端為整數(shù)，右端<1，則有其右端?0，即（3）將上述約束方程（4）重新組合。組合的原則是：將非負(fù)基變量系數(shù)及常數(shù)項(xiàng)中的非負(fù)真分?jǐn)?shù)移到等號(hào)右端，將其他部分移到等號(hào)左端，即得：等式左端實(shí)際上由三部分組成，常數(shù)項(xiàng)的整數(shù)部分，基變量及非基變量（含松弛變量或剩余變量），前兩部分都是整數(shù)或應(yīng)取整數(shù)，而松弛變量x3、x4由松弛問題標(biāo)準(zhǔn)型知，也應(yīng)取非負(fù)整數(shù)（對(duì)于這一點(diǎn)，當(dāng)原問題的約束方程組中的系數(shù)或常數(shù)項(xiàng)中有非整數(shù)時(shí)，要求將約束方程

7、先化為成整數(shù)系數(shù)及整數(shù)常數(shù)項(xiàng)，然后再標(biāo)準(zhǔn)化，就可滿足）。（4）將割平面方程加到松弛問題的約束方程中，構(gòu)成新的松弛問題并求解（對(duì)偶單純形法）。割平面方程Cj?11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/4001cj-zj00-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3cj-zj00－1/3－2/3注釋：（1）本題注只用一次割平面就求得了最優(yōu)解，但大多數(shù)問題中不是只用一、二次割平面就能求得整數(shù)最優(yōu)解。若一次割平面不能求得整數(shù)

8、最優(yōu)解，則按步驟2中的4個(gè)步驟，在松弛問題的最終單純形表中找出第二個(gè)割平面方程，將此割平面方程