1、整 數(shù) 規(guī) 劃 (Integer Programming),整數(shù)規(guī)劃的模型,分支定界法,割平面法,01 整數(shù)規(guī)劃,指派問題,（一） 整數(shù)規(guī)劃問題實(shí)例,例一、合理下料問題 設(shè)用某型號(hào)的圓鋼下零件A1, A2,Am 的毛坯。在一根圓鋼上下料的方式有B1,B2, Bn 種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得既滿足需要，所用的原材料又最少？,一、整數(shù)規(guī)劃的模型,設(shè)：xj 表示用Bj (j=1.2n) 種方式下料根數(shù) 模型：,例二、某公司計(jì)劃在m個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)有A1,A2Am ，他們的生產(chǎn)能力分別是a1,a2,am（假設(shè)生產(chǎn)同一產(chǎn)品）

2、。第i個(gè)工廠的建設(shè)費(fèi)用為fi (i=1.2m),又有n個(gè)地點(diǎn)B1,B2, Bn 需要銷售這種產(chǎn)品，其銷量分別為b1.b2bn 。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最省？,設(shè)： xij 表示從工廠運(yùn)往銷地的運(yùn)量(i=1.2m、j=1.2n), 1 在Ai建廠 又設(shè) Yi （i=1.2m） 0 不在Ai建廠 模型：,例三、機(jī)床分配問題 設(shè)有m臺(tái)同類機(jī)床，要加工n種零件。已知各種零件的加工時(shí)間分別為a1,a2,an ，問如何分配，使各機(jī)床的總加工任務(wù)相等，或者說盡可能平衡。,設(shè)： 1 分配第i臺(tái)機(jī)床加工第j種零件； xij （i=1.

3、2m,j=1.2n） 0 相反。 于是，第i臺(tái)機(jī)床加工各種零件的總時(shí)間為：,又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有,因此，求xij ，使得,（二） 整數(shù)規(guī)劃的數(shù)學(xué)模型,一般形式,依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、01整數(shù)規(guī)劃。,純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量可以不要求取整數(shù)）。,全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時(shí)引進(jìn)的松弛變量也必須是整數(shù)）。,混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。,01整數(shù)規(guī)劃：所有決策變量只能取 0 或 1 兩個(gè)

4、整數(shù)。,（三） 整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系,從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。 舉例說明。,例：設(shè)整數(shù)規(guī)劃問題如下,首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。,用圖解法求出最優(yōu)解 x13/2, x2 = 10/3 且有Z = 29/6,x1,x2,3,3,(3/2,10/3),現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)即(1，3) (2，3)(1，4)(2，4)。顯然，它們都

5、不可能是整數(shù)規(guī)劃的最優(yōu)解。,按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。,因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。 如上例：其中（2，2）（3，1）點(diǎn)為最大值，Z=4。,目前，常用的求解整數(shù)規(guī)劃的方法有： 分支定界法和割平面法； 對(duì)于特別的01規(guī)劃問題采用隱枚舉法和匈牙利法。,（一） 基本思路,考慮純整數(shù)問題：,整數(shù)問題的松弛問題：,二、分枝定界法,1、先不考慮整數(shù)約束，解( IP )的松弛問題( LP )，可能得到以下情況之一： 若( LP )沒有可行解，則( IP )也沒有可行解

6、，停止計(jì)算。 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算。 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)( LP )的最優(yōu)解為：,2、定界： 記( IP )的目標(biāo)函數(shù)最優(yōu)值為Z* ,以Z(0) 作為Z* 的上界，記為 Z(0) 。再用觀察法找的一個(gè)整數(shù)可行解 X，并以其相應(yīng)的目標(biāo)函數(shù)值 Z作為Z* 的下界，記為Z Z，也可以令Z，則有： Z Z* ,3、分枝： 在( LP )的最優(yōu)解 X(0)中，任選一個(gè)不符合整數(shù)條件的變量，例如xr= （不為整數(shù)），以 表示不超過 的最大整數(shù)。構(gòu)造兩個(gè)約

7、束條件 xr 和xr 1,如此反復(fù)進(jìn)行，直到得到ZZ* 為止，即得最優(yōu)解 X* 。,將這兩個(gè)約束條件分別加入問題( IP ) ，形成兩個(gè)子問題( IP1)和( IP2 ) ，再解這兩個(gè)問題的松弛問題( LP1)和( LP2) 。,4、修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。 在各分枝問題中，找出目標(biāo)函數(shù)值最大者作為新的上界； 從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。,5、比較與剪枝 ： 各分枝的目標(biāo)函數(shù)值中，若有小于Z 者，則剪掉此枝，表明此子問題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。,例一：用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計(jì)算）,記為（IP）,解：首先去掉整數(shù)約束，變成

8、一般線性規(guī)劃問題,記為（LP）,（二） 例題,用圖解法求（LP）的最優(yōu)解，如圖所示。,x1,x2,3,3,(18/11,40/11),對(duì)于x118/111.64， 取值x1 1， x1 2 對(duì)于x2 =40/11 3.64，取值x2 3 ，x2 4 先將（LP）劃分為（LP1）和（LP2）,取x1 1, x1 2,x118/11, x2 =40/11 Z(0) =218/11(19.8) 即Z 也是（IP）最小值的下限。,有下式：,現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。,x1,x2,3,3,(18/11,40/11),先求（LP1）,如圖所示。此時(shí)B 在點(diǎn)取得最優(yōu)解。 x11, x2

9、 =3, Z(1)16 找到整數(shù)解，問題已探明，此枝停止計(jì)算。,1,1,同理求（LP2） ,如圖所示。 在C 點(diǎn)取得最優(yōu)解。 即x12, x2 =10/3, Z(2) 56/318.7 Z2 Z116 原問題有比（16）更小的最優(yōu)解，但 x2 不是整數(shù)，故利用 3 10/34 加入條件。,B,A,C,加入條件： x23, x24 有下式：,只要求出（LP3）和（LP4）的最優(yōu)解即可。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,先求（LP3）,如圖所示。此時(shí)D 在點(diǎn)取得最優(yōu)解。 即 x112/52.4, x2 =3, Z(3)-87/5-17.4Z-19.8 但x112

10、/5不是整數(shù)，可繼續(xù)分枝。即 3x12。,D,求（LP4），如圖所示。 無可行解，不再分枝。,在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3x12有下式：,只要求出（LP5）和（LP6）的最優(yōu)解即可。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求（LP5）,如圖所示。此時(shí)E 在點(diǎn)取得最優(yōu)解。 即 x12, x2 =3, Z(5)17 找到整數(shù)解，問題已探明，此枝停止計(jì)算。,E,求（LP6），如圖所示。此時(shí) F在點(diǎn)取得最優(yōu)解。 x13, x2 =2.5, Z(6)31/215.5 Z(5),F,如對(duì) Z(6) 繼續(xù)分解，其最小值也不會(huì)低于15.5 ，問題探明,剪枝。,至

11、此，原問題（IP）的最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) 17 以上的求解過程可以用一個(gè)樹形圖表示如右：,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP3 x1=12/5, x2=3 Z(3) 17.4,LP4 無可 行解,LP5 x1=2, x2=3 Z(5) 17,LP6 x1=3, x2=5/2 Z(6) 15.5,x11,x12,x23,x24,x12,x13,練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題 （圖解法）,x11,x12,x22,x23,x2

12、2,x23,x12,x13,LP1 x1=1, x2=7/3 Z(1) 10/3,LP x1=2/3, x2=10/3 Z(0) 29/6,LP2 x1=2, x2=23/9 Z(2) 41/9,LP3 x1=33/14, x2=2 Z(3) 61/14,LP4 無可 行解,LP7 x1=2, x2=2 Z(7) 4,LP8 x1=3, x2=1 Z(8) 4,x11,x12,x22,x23,x12,x13,解:用單純形法解對(duì)應(yīng)的(LP)問題,如表所示,獲得最優(yōu)解。,初始表,最終表,例二、用分枝定界法求解整數(shù)規(guī)劃問題（單純形法）,x1=13/4 x2=5/2 Z(0) =59/414.75 選

13、 x2 進(jìn)行分枝，即增加兩個(gè)約束，2 x2 ，x2 3 有下式：,分別在(LP1)和(LP2)中引入松弛變量x5和x6 ，將新加約束條件加入上表計(jì)算。即 x2+ x5= 2 , x2+x6=3 得下表:,x1=7/2, x2=2 Z(1) =29/2=14.5 繼續(xù)分枝，加入約束 3 x1 4,LP1,LP2,x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考慮分枝,接(LP1)繼續(xù)分枝，加入約束 4 x1 3，有下式：,分別引入松弛變量x7 和 x8 ，然后進(jìn)行計(jì)算。,x1=3, x2=2 Z(3) =13 找到整數(shù)解，問題已探明，停止計(jì)算。,LP3,x1=

14、4, x2=1 Z(4) =14 找到整數(shù)解，問題已探明，停止計(jì)算。,LP4,樹形圖如下：,LP1 x1=7/2, x2=2 Z(1)29/2=14.5,LP x1=13/4, x2=5/2 Z(0) 59/4=14.75,LP2 x1=5/2, x2=3 Z(2)27/2=13.5,LP3 x1=3, x2=2 Z(3) 13,LP4 x1=4, x2=1 Z(4) 14,x22,x23,x13,x14,練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題 （單純形法）,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10

15、/3 Z(2) 18.5,LP3 x1=12/5, x2=3 Z(3) 17.4,LP4 無可 行解,LP5 x1=2, x2=3 Z(5) 17,LP6 x1=3, x2=5/2 Z(6) 15.5,x11,x12,x23,x24,x12,x13,（一） 計(jì)算步驟： 1、用單純形法求解( IP )對(duì)應(yīng)的松弛問題( LP )： 若( LP )沒有可行解，則( IP )也沒有可行解，停止計(jì)算。 若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算。 若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。,三、割平面法,2、從

16、(LP)的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量xr,將最優(yōu)單純形表中該行的系數(shù) 和 分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，按下式作割平面方程：,3、將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量），用對(duì)偶單純形法求出新的最優(yōu)解，返回1。,的小數(shù)部分,的小數(shù)部分,例一：用割平面法求解整數(shù)規(guī)劃問題,解：增加松弛變量x3和x4 ，得到(LP)的初始單純形表和最優(yōu)單純形表：,此題的最優(yōu)解為：X= (1 , 3/2)T Z = 3/2 但不是整數(shù)最優(yōu)解，引入割平面。以x2 為源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我們已將所需要的數(shù)分解為整

17、數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為:,現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：,此時(shí)，X1 (2/3, 1), Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成割平面，其條件為：,將生成的割平面條件加入松弛變量，然后加到表中：,至此得到最優(yōu)表，其最優(yōu)解為 X= (1 , 1) , Z = 1, 這也是原問題的最優(yōu)解。,有以上解題過程可見，表中含有分?jǐn)?shù)元素且算法過程中始終保持對(duì)偶可行性，因此，這個(gè)算法也稱為分?jǐn)?shù)對(duì)偶割平面算法。,例二：用割平面法求解整數(shù)規(guī)劃問題,初 始 表,最優(yōu)表,割平面方程：,引入松弛變量s1 后得到下式，將此約束條件加到上表中，繼續(xù)求解。,得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)

18、解，而且此整數(shù)規(guī)劃有兩個(gè)最優(yōu)解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。,（2 ，3）,01 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量xj 只取兩個(gè)值0或1，一般的解法為隱枚舉法。,例一、求解下列01 規(guī)劃問題,四、01 整數(shù)規(guī)劃,解：對(duì)于01 規(guī)劃問題，由于每個(gè)變量只取0，1兩個(gè)值，一般會(huì)用窮舉法來解，即將所有的0，1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過加入一定的條件，就能較快的求得最優(yōu)解。,由上表可知，問題的最優(yōu)解為 X*=(1,0,1 )T 由上表可知： x1 =0 x2=

19、0 x3=1 是一個(gè)可行解，為盡快找到最優(yōu)解，可將3 x12 x25 x3 5 作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5 的組合不必討論，如下表。,例二、求解下列01 規(guī)劃問題,解：由于目標(biāo)函數(shù)中變量x1, x2 , x4 的系數(shù)均為負(fù)數(shù)，可作如下變換：,令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4帶入原題中，但需重新調(diào)整變量編號(hào)。令 x3 = x1, x4 = x2得到下式。,可以從( 1.1.1.1 )開始試算， x(3)( 1.1.0.1 )T最優(yōu)解。 x(3)( 1.0.1.0 )T是原問題的最優(yōu)解，Z* =2,例三、求解下列01 規(guī)劃問題,令 y1=x5

20、, y2=x4, y3=x2, y4=x3, y5=x1 得到下式,所以， Y*= （0.0.0.1.0），原問題的最優(yōu)解為： X* （0.0.1.0.0）T，Z* =8,（0 . 1 . 1 . 0 . 0）,練習(xí)：用隱枚舉法求解01規(guī)劃問題,在實(shí)際中經(jīng)常會(huì)遇到這樣的問題，有n 項(xiàng)不同的任務(wù)，需要n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問題稱為指派問題或分派問題。,（一） 指派問題的數(shù)學(xué)模型 設(shè)n 個(gè)人被分配

21、去做n 件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j 件工作的的效率（ 時(shí)間或費(fèi)用）為Cij(i=1.2n;j=1.2n)并假設(shè)Cij 0。問應(yīng)如何分配才能使總效率（ 時(shí)間或費(fèi)用）最高？,五、指派問題,設(shè)決策變量 1 分配第i 個(gè)人去做第j 件工作 xij = 0 相反 ( i,j=1.2. n ),其數(shù)學(xué)模型為：,（二） 解題步驟：,指派問題是0-1 規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點(diǎn)可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨(dú)立 0 元素的

22、最多個(gè)數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。,第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 (1) 從（cij）的每行元素都減去該行的最小元素； (2) 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。,第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為： (1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作 。然后劃去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務(wù)已

23、指派完，不必再考慮別人了。 (2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作；然后劃去 所在行的0元素，記作 (3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。,(4) 若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。 （5）若 元素的數(shù)目m 等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。 第三步：作最少的直線覆蓋所有0元素。 (1)對(duì)沒有的行打號(hào)； (2)對(duì)已打號(hào)的行