【正文】 例：變量 x可取 0與 9之間的任意整數(shù)。第 3節(jié) 01型整數(shù)規(guī)劃 一、 01型變量的含義 變量只能取值 0或 1。: 2 , , ( ): 4 , ( 1 , 4 ) , 1 8 .5 , ( ): 2 0 2 0 .2 8 。: 3 , ( 3 , 3 ) , 1 9 .5 , ( ):: 4 , ( 1 .8 , 4 ) , 2 0 .5zLxLLx?????第 二 次 剪 支*3121 9 .5 2 0 .5 。 作業(yè) 13 作業(yè) 13：用分支定界法求解 例 2。 第 2節(jié) 分支定界法 例 5：用分支定界法求解下述整數(shù)規(guī)劃問(wèn)題。若除保留下來(lái)的可行解外，其余分支都被剪去，則該可行解是整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。（若所有子問(wèn)題的最優(yōu)解都不是整數(shù)規(guī)劃問(wèn)題可行解，則選取邊界值最大（求極大時(shí)）或最?。ㄇ髽O下時(shí)）的子問(wèn)題進(jìn)一步再細(xì)分子問(wèn)題，并求解） 第 2節(jié) 分支定界法 第四步：比較與剪支。 ? ? ? ? +1i i i ix b x b??和第 2節(jié) 分支定界法 第三步：定界。 第 2節(jié) 分支定界法 第二步：分支。 第 2節(jié) 分支定界法 三、分支定界法的步驟 第一步：求解松弛問(wèn)題。 max z =x1+4x2 2x1+3x2≤3 x1+2x2≤8 x1， x2≥0 x1， x2整數(shù) 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ?小結(jié) （ 1）對(duì)整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題的最優(yōu)解中不符合整數(shù)要求的分量進(jìn)行簡(jiǎn)單地取整，所得到的整數(shù)解可能不一定是整數(shù)規(guī)劃問(wèn)題的最優(yōu)解，甚至也不一定是整數(shù)規(guī)劃問(wèn)題的可行解 （ 2）對(duì)于復(fù)雜的模型，完全枚舉法費(fèi)時(shí)，甚至不可能實(shí)現(xiàn) 第 2節(jié) 分支定界法 一、分支定界法的思路 分支定界法是先求解整數(shù)規(guī)劃的松弛問(wèn)題，如果其最優(yōu)解不符合整數(shù)條件，則用增加約束的辦法求出整數(shù)規(guī)劃問(wèn)題的上下界，并把松弛問(wèn)題的可行域分成互不重疊的子區(qū)域，再求解這些子區(qū)域的松弛問(wèn)題，不斷縮小整數(shù)規(guī)劃問(wèn)題上下界的差距，最后取得整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。那么，管理層應(yīng)如何決策才能使這批鉆石獲利最大？ 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 例 2： 解：設(shè) x1， x2分別為切磨成皇冠形和切磨成心形的鉆石粒數(shù) max z =+4x2 x1+x2≤6 5x1+9x2≤45 x1≤4 x1， x2≥0 x1， x2整數(shù) 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ? 完全枚舉法 對(duì)于可行域有界的整數(shù)規(guī)劃問(wèn)題，整數(shù)規(guī)劃的可行解是一個(gè)有限集，將這個(gè)集內(nèi)的每一個(gè)點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值都一一計(jì)算出來(lái)，然后從中找出最優(yōu)者，則為整數(shù)規(guī)劃的最優(yōu)解。若切磨成皇冠形則每粒需要 5個(gè)工作日，若切磨成心形則每粒需要 9個(gè)工作日，由于工廠切工師傅較忙，最多只有 45個(gè)工作日來(lái)做這批工作。 時(shí)段 1 2 3 4 5 6 7 8 服務(wù)員最少數(shù)目 10 8 9 11 13 8 5 3 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 例 1： 解：設(shè)在第 j時(shí)段開(kāi)始時(shí)上班的服務(wù)員人數(shù)為 xj。按規(guī)定，服務(wù)員連續(xù)工作 8h（即四個(gè)時(shí)段）為一班。若松弛問(wèn)題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。第五章 整數(shù)規(guī)劃 Integer Programming 第五章 整數(shù)規(guī)劃 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 第 2節(jié) 分支定界法 第 3節(jié) 01型整數(shù)規(guī)劃 第 4節(jié) 指派問(wèn)題 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 一、整數(shù)規(guī)劃的含義 要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問(wèn)題。 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ?整數(shù)規(guī)劃的松弛問(wèn)題 不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題。 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ?整數(shù)線性規(guī)劃的數(shù)學(xué)模型 1112m a x( m in)( ) 1 20 1 2njjjnij j ijjnz c xa x b i mx j nx x x????? ? ? ?????????????或或 ， 或 ， ， ， ， ， ， ， ， ， 中 部 分 或 全 部 取 整 數(shù)第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ?整數(shù)線性規(guī)劃問(wèn)題的類型 （ 1）純（全）整數(shù)線性規(guī)劃：全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃 （ 2）混合整數(shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃 （ 3） 01型整數(shù)線性規(guī)劃：決策變量只能取值 0或 1的整數(shù)線性規(guī)劃 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 例 1：某服務(wù)部門(mén)各時(shí)段（每 2h為一時(shí)段）需要的服務(wù)員人數(shù)見(jiàn)下表?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門(mén)服務(wù)員總數(shù)最少。 1 2 3 4 51121 2 31 2 3 423453454551 2 3 4 5m in108911138530z x x x x xxxxx x xx x x xx x x xx x xxxxx x x x x? ? ? ? ???????? ? ? ??? ? ? ???? ? ? ???? ? ??? ????????， ， ， ， ， 且 均 取 整 數(shù) 值第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 二、整數(shù)規(guī)劃的解的特點(diǎn) ?整數(shù)規(guī)劃問(wèn)題的可行域是它的松弛問(wèn)題可行域的子集 ?整數(shù)規(guī)劃問(wèn)題的可行解是它的松弛問(wèn)題的可行解 ?整數(shù)規(guī)劃問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值不優(yōu)于它的松弛問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 三、整數(shù)規(guī)劃的解法 例 2：某寶石加工廠最近新到 6粒大小、質(zhì)量等級(jí)相似的鉆石毛料，管理層有兩種選擇，一是切磨成一般的皇冠形，每?？色@利 ；一是切磨成雖然較難切磨但當(dāng)前市場(chǎng)較流行的心形，每?？色@利 4千元。另外，由于毛料自身形狀的關(guān)系，其中只有 4粒毛料可以切磨成皇冠形，而 6粒毛料中任何一粒都可以切磨成心形。 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 例 3：用完全枚舉法求解下述整數(shù)規(guī)劃問(wèn)題。 第 2節(jié) 分支定界法 二、分支定界法的含義 分支定界法是一種部分枚舉法，通過(guò)不斷地分割松弛問(wèn)題的可行域并進(jìn)行比較，最終求得整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。 （ 1）松弛問(wèn)題無(wú)可行解，則整數(shù)規(guī)劃問(wèn)題無(wú)可行解，計(jì)算停止； （ 2）松弛問(wèn)題有最優(yōu)解，并且符合整數(shù)規(guī)劃問(wèn)題的整數(shù)條件，則松弛問(wèn)題的最優(yōu)解就是整數(shù)規(guī)劃問(wèn)題的最優(yōu)解，計(jì)算停止； （ 3）松弛問(wèn)題有最優(yōu)解，但是不符合整數(shù)規(guī)劃問(wèn)題的整數(shù)條件，則松弛問(wèn)題的最優(yōu)值是整數(shù)規(guī)劃問(wèn)題最優(yōu)值的上界值（求極大時(shí)）或下界值（求極小時(shí)），下界值（求極大時(shí)）可暫定為 ∞ 或上界值（求極小時(shí)）可暫定為 +∞ 。 在松弛問(wèn)題的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量 xi，其值為 bi，用 [bi]表示小于 bi的最大整數(shù)，構(gòu)造以下兩個(gè)約束條件： 將這兩個(gè)約束條件分別加入整數(shù)規(guī)劃問(wèn)題，形成兩個(gè)子問(wèn)題，再求解這兩個(gè)子問(wèn)題的松弛問(wèn)題。 以每個(gè)子問(wèn)題的松弛問(wèn)題為一分支標(biāo)明求解的結(jié)果，與其他問(wèn)題的解的結(jié)果相比較： （ 1）若解滿足子問(wèn)題的整數(shù)條件，則找到了一個(gè)整數(shù)規(guī)劃問(wèn)題的可行解，為新的下界值 （求極大時(shí)）或上界值（求極小時(shí)） ；（若計(jì)算中同時(shí)出現(xiàn)兩個(gè)及以上整數(shù)規(guī)劃問(wèn)題可行解，則選取其中最大 （求極大時(shí)）或最小（求極下時(shí)）的一個(gè)保留 ） （ 2）若解不滿足子問(wèn)題的整數(shù)條件，則為新的 上界