歷年數(shù)學(xué)建模優(yōu)秀02084整數(shù)

1、整數(shù)規(guī)劃的模型分支定界法割平面法01 整數(shù)規(guī)劃指派問題整數(shù)規(guī)劃整數(shù)規(guī)劃一般形式依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、01整數(shù)規(guī)劃。整數(shù)規(guī)劃的數(shù)學(xué)模型部分或者全部為整數(shù)純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時引進的松弛變量和剩余變量可以不要求取整數(shù)）。全整數(shù)規(guī)劃：除所有決策變量要求取非負(fù)整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時引進的松弛變量和剩余變量也必須是整數(shù)）?；旌险麛?shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實數(shù)。 01整數(shù)規(guī)劃：所有決策變量只能取 0 或 1 兩個整數(shù)。從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式

2、，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時甚至不能保證所得到的解是整數(shù)可行解。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系例：設(shè)整數(shù)規(guī)劃問題如下 首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。且為整數(shù) 用圖解法求出最優(yōu)解x13/2, x2 = 10/3且有Z = 29/6x1x233(3/2,10/3)現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3), (2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且

3、為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。目前，常用的求解整數(shù)規(guī)劃的方法有：分支定界法和割平面法；對于特別的01規(guī)劃問題采用隱枚舉法和匈牙利法?？紤]純整數(shù)問題：整數(shù)問題的松弛問題：分枝定界法1、先不考慮整數(shù)約束，解( IP )的松弛問題( LP )，可能得到以下情況之一： .若( LP )沒有可行解，則( IP )也沒有可行解，停止計算。 .若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計

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

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

6、4， 取值x1 1， x1 2對于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)解即可。x1x233(18/11,40/11) 先求（LP1）,如圖所示。此時B 在點取得最優(yōu)解。x11, x2 =3, Z(1)16找到整數(shù)解，問題已探明，此枝停止計算。11同理求（LP2） ,如圖所示。在C 點取得最優(yōu)解。即x12, x2 =10/3, Z(2) 56/318.7 Z2

7、Z116 原問題有比（16）更小的最優(yōu)解，但 x2 不是整數(shù)，利用 3 10/34 加入條件。BAC加入條件： x23, x24 有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。x1x233(18/11,40/11)11BAC先求（LP3）,如圖所示。此時D 在點取得最優(yōu)解。即 x112/52.4, x2 =3, Z(3)-87/5-17.4 Z(5) F如對 Z(6) 繼續(xù)分解，其最小值也不會低于15.5 ，問題探明,剪枝。 至此，原問題（IP）的最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) 17以上的求解過程可以用一個樹形圖表示如右：LP1x1=1, x2=3Z(1) 16

8、LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4無可行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13 除了用分支界定法來解決整數(shù)規(guī)劃問題外，還有一種割平面法，這種方法的基礎(chǔ)仍然是用線性規(guī)劃的方法去解整數(shù)規(guī)劃問題。 這種方法的主要想法是：首先不考慮變量是整數(shù)這一條件，但增加線性約束條件使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解。這個方法就是指出怎樣找到適當(dāng)?shù)母钇矫?，?/p>

9、切割后最終得到這樣的可行域，它的一個有整數(shù)坐標(biāo)的極點恰好是問題的最優(yōu)解。割平面法11（一）、計算步驟：1、用單純形法求解( IP )對應(yīng)的松弛問題( LP )： .若( LP )沒有可行解，則( IP )也沒有可行解，停止計算。 .若( LP )有最優(yōu)解，并符合( IP )的整數(shù)條件，則( LP )的最優(yōu)解即為( IP )的最優(yōu)解，停止計算。 .若( LP )有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)入下一步。 2、從(LP)的最優(yōu)解中，任選一個不為整數(shù)的分量xr,將最優(yōu)單純形表中該行的系數(shù) 和 分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，按下式作割平面方程： 3、將所得的割平面方程作為一

10、個新的約束條件置于最優(yōu)單純形表中（同時增加一個單位列向量），用對偶單純形法求出新的最優(yōu)解，返回1。的小數(shù)部分的小數(shù)部分例一：用割平面法求解整數(shù)規(guī)劃問題解：增加松弛變量x3和x4 ，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/200-1/4-1/4 此題的最優(yōu)解為：X*= (1 , 3/2) Z = 3/2 但不是整數(shù)最優(yōu)解，引入割平面。以x2 為源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2,

11、 我們已將所需要的數(shù)分解為整數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為: 也即：將 x3=6-3x1-2x2 , x4=3x1-2x2 ,帶入x1x233第一個割平面得到等價的割平面條件： x2 1,見下圖。Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1 此時，X1 (2/3, 1), Z=1,仍不是整數(shù)解。繼

12、續(xù)以x1為源行生成割平面，其條件為： 用上表的約束解出x4 和s1 ，將它們帶入上式得到等價的割平面條件：x1 x2 ，見圖：x1x233第一個割平面第二個割平面將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21

13、x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最優(yōu)表，其最優(yōu)解為 X= (1 , 1) , Z = 1, 這也是原問題的最優(yōu)解。 有以上解題過程可見，表中含有分?jǐn)?shù)元素且算法過程中始終保持對偶可行性，因此，這個算法也稱為分?jǐn)?shù)對偶割平面算法。 01 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策變量xi 只取兩個值0或1，一般的解法為隱枚舉法。例一、求解下列01 規(guī)劃問題01 整數(shù)規(guī)劃 解：對于01 規(guī)劃問題，由于每個變量只取0，1兩個值，一般會用窮舉法來解，即將所有的0，1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作

14、量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過加入一定的條件，就能較快的求得最優(yōu)解。x1 . x2. x3約束條件滿足條件Z 值 (1) (2) (3) (4)是 否( 0. 0. 0 ) 0 0 0 00( 0. 0. 1 ) 1 1 0 15( 0. 1. 0 ) 2 4 1 42( 1. 0. 0 ) 1 1 1 03( 0. 1. 1 ) 1 5( 1. 0. 1 ) 0 2 1 18( 1. 1. 0 ) 3( 1. 1. 1 ) 2 6由上表可知，問題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 )由上表可知： x1 =0 x2=0 x3=1 是一個可行解，為盡快找到最優(yōu)解，可將

15、3 x12 x25 x3 5 作為一個約束，凡是目標(biāo)函數(shù)值小于5 的組合不必討論，如下表。x1 . x2. x3約束條件滿足條件Z 值(0) (1) (2) (3) (4)是 否( 0. 0. 0 ) 0 0 0 0 00( 0. 0. 1 ) 5 1 1 0 15( 0. 1. 0 )-2( 0. 1. 1 ) 3( 1. 0. 0 ) 3( 1. 0. 1 ) 8 0 2 1 18( 1. 1. 0 ) 1( 1. 1. 1 ) 4 指派問題的數(shù)學(xué)模型設(shè)n 個人被分配去做n 件工作，已知第i 個人去做第j 件工作的的效率為Cij(i=1.2n;j=1.2n)并假設(shè)Cij 0。問應(yīng)如何分配才

16、能使總效率（ 時間或費用）最高？指派問題設(shè)決策變量 1 分配第i 個人去做第j 件工作 xij = 0 相反 ( I,j=1.2. n )解題步驟：第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即(1) 從（cij）的每行元素都減去該行的最小元素；(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。第二步：進行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為： (1)從只有一個0元素的行(列)開始，給

17、這個0元素加圈，記作 。然后劃去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。(2)給只有一個0元素的列(行)中的0元素加圈，記作；然后劃去 所在行的0元素，記作 (3)反復(fù)進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素。可反復(fù)進行，直到所有0元素都已圈出和劃掉為止。 （5）若 元素的數(shù)目m 等于矩陣的階

18、數(shù)n，那么這指派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。第三步：作最少的直線覆蓋所有0元素。(1)對沒有的行打號；(2)對已打號的行中所有含元素的列打號；(3)再對打有號的列中含 元素的行打號；(4)重復(fù)(2)，(3)直到得不出新的打號的行、列為止；(5)對沒有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。l 應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若 lm n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打各行都減去這最小元素；打各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。 任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119249742有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙