2013參考數(shù)學(xué)建模常用方法：整數(shù)規(guī)劃資料

其次章整數(shù)規(guī)劃1．整數(shù)規(guī)劃的基本概念2．分枝定界法解整數(shù)規(guī)劃3．０－１規(guī)劃4.指派問題的解法第一節(jié)概述人們探討某些線性規(guī)劃問題，有時必需把全部或部分決策變量限制為整數(shù)。這樣的線性規(guī)劃問題，通常稱為整數(shù)規(guī)劃。作為線性規(guī)劃的特殊狀況，整數(shù)規(guī)劃也有最小化和最大化之別。此外，整數(shù)規(guī)劃還可以分成純整數(shù)規(guī)劃和混整數(shù)規(guī)劃。二者的區(qū)分在于：前者的決策變量必定全部取整數(shù)。而后者的決策變量只是部分取整數(shù)。例1某醫(yī)藥公司現(xiàn)有兩個制藥廠A1和A2，三個銷售店B1、B2和B3。公司準(zhǔn)備由兩個擬建的制藥廠A3和A4中選擇一個，來興建新廠。各銷售店每周藥品需求量見表2-1。各制藥廠每周藥品產(chǎn)量和每箱藥品運(yùn)費(fèi)見表2-2。新廠投產(chǎn)后，估計每周的操作費(fèi)（含折舊費(fèi)）：A3是100元，A4是120元。在兩個擬建的制藥廠中，應(yīng)當(dāng)選擇哪個呢？銷售店需求量（箱/周）

B150

B260

B330產(chǎn)量制藥廠(箱/周)運(yùn)資(元/箱)

B1

B2

B3

A150323

A2701058

A3201310

A420453表2－1表2－2

設(shè)：制藥廠Ai每周運(yùn)到銷售店Bj的藥品為xij箱（i=1,2，3，4；j=1，2，3）；解：建立數(shù)學(xué)模型

兩個老廠A1和A2及一個新廠A3和A4每周的總費(fèi)用為y元。新廠廠址的選擇應(yīng)當(dāng)確保y達(dá)到最小值。于是，y是目標(biāo)函數(shù)，xij、u和v都是決策變量。它們之間的關(guān)系可以表述為：y=3x11+2x12+3x13（A1每周的運(yùn)費(fèi)）+10x21+5x22+8x23（A2每周的運(yùn)費(fèi)）+x31+3x32+10x33（A3每周的運(yùn)費(fèi)） +4x41+5x42+3x43（A4每周的運(yùn)費(fèi)） +100u（A3每周的操作費(fèi)） +120v（A4每周的操作費(fèi)）(1)u和v全是0－1變量：約束條件：x11+x

12+x13≤50x21+x

22+x23≤70x31+x

32+x33≤20ux41+x

42+x43≤20vu,v=0,1(2)由A3和A4選擇一個來興建新廠：u+v=1(3)每個制藥廠每周運(yùn)到各銷售店的藥品不會超過其產(chǎn)量：(4)每個銷售店每周藥品的需求量能夠得到各制藥廠的充分供應(yīng)：（5）藥品箱數(shù)確定取非負(fù)值：

xij≥0x11+x21+x31+x41=50

x12+x22+x32+x42=60

x13+x23+x33+x43=30例1的數(shù)學(xué)模型為：Miny=3x11+2x12+3x13+10x21+5x22+8x23+x31+3x32+10x33+4x41+5x42+3x43+100u+120vx11+x

12+x13≤50

x21+x

22+x23≤70

x31+x

32+x33≤20u

x41+x

42+x43≤20vx11+x21+x31+x41=50

x12+x22+x32+x42=60

x13+x23+x33+x43=30xij≥0(i=1,2,3,4;j=1,2,3)u,v=0,1

本數(shù)學(xué)模型屬于最小化混整數(shù)規(guī)劃例2某醫(yī)療器械廠生產(chǎn)A1和A2兩種產(chǎn)品。出廠前，每種產(chǎn)品均須經(jīng)過兩道工序：先用機(jī)器B1制造，后由機(jī)器B2包裝。每臺產(chǎn)品的利潤和加工時間見表2-3。在下周內(nèi)，機(jī)器B1和B2分別可以運(yùn)用45小時和6小時。問怎樣支配下周的生產(chǎn)任務(wù)，才能使所獲利潤最大？解：建立數(shù)學(xué)模型設(shè)：在下周產(chǎn)品A1和A2分別生產(chǎn)x1合和x2合，所獲利潤為y百元。例2的數(shù)學(xué)模型為：產(chǎn)品利潤（百元/合）加工時間（小時/合）B1B2A1551A2891表2-3最大化純整數(shù)規(guī)劃其中：“xk′為整數(shù)”,稱為整數(shù)條件。一般地，可把整數(shù)規(guī)劃的數(shù)學(xué)模型寫為：整數(shù)規(guī)劃問題及其數(shù)學(xué)模型一律簡稱為整數(shù)規(guī)劃；整數(shù)規(guī)劃刪去整數(shù)條件之前和之后，分別稱為原整數(shù)規(guī)劃和相應(yīng)線性規(guī)劃。依據(jù)四舍五入的規(guī)則，使相應(yīng)線性規(guī)劃的最優(yōu)解整數(shù)化，在通常狀況下，不能作為原整數(shù)規(guī)劃的最優(yōu)解。這可以從兩個方面來說明：其一、相應(yīng)線性規(guī)劃的最優(yōu)解化整后，已經(jīng)不是原整數(shù)規(guī)劃的可行解，當(dāng)然也就不行能是它的最優(yōu)解。其二、相應(yīng)線性規(guī)劃的最優(yōu)解化整后，雖然是原整數(shù)規(guī)劃的可行解，但是有可能不是它的最優(yōu)解。例2是最大化純整數(shù)規(guī)劃，其相應(yīng)線性規(guī)劃為：下面求解這個相應(yīng)線性規(guī)劃。我們接受圖解法。并且最優(yōu)解是：(x1,x2)=（2.25,3.75）。依據(jù)四舍五入的規(guī)則，將這個最優(yōu)解整數(shù)化，就得到：(x1,x2)=（2，4）。它對應(yīng)于點(diǎn)D，而點(diǎn)D卻位于可行域R之外，因此,D（2，4）不是例2的可行解。從而，D（2，4）也不行能是例2的最優(yōu)解。簡潔斷定，點(diǎn)A（0，5）才是例2的最優(yōu)解。圖解法:相應(yīng)線性規(guī)劃的可行域R為圖中的四邊形OABC，5x1+9x2=45x1+

x2=6B(2.25,3.75)D(2,4)x2ox19C(6,0)RA最優(yōu)解A(0,5)整數(shù)規(guī)劃常用的解法是分枝定界法和割平面法。一旦遇到僅含兩個決策變量的狀況，可以接受圖解法，其計算方法與線性規(guī)劃圖解法大同小異，就不再贅述。求解整數(shù)規(guī)劃不宜接受枚舉法。其次節(jié)分枝定界法分枝定界法可以用來求解純整數(shù)規(guī)劃和混整數(shù)規(guī)劃，它是整數(shù)規(guī)劃的常用解法。分枝定界法可以劃分為三步。現(xiàn)就每一步的主要特征、理論依據(jù)和具體作法說明如下：

第一步第一步的具體作法是：首先，刪去整數(shù)條件，把原整數(shù)規(guī)劃化成相應(yīng)線性規(guī)劃。其次，求解相應(yīng)線性規(guī)劃。最終，假如相應(yīng)線性規(guī)劃的最優(yōu)解也是原整數(shù)規(guī)劃的最優(yōu)解，那么整個計算過程即告結(jié)束；否則，便轉(zhuǎn)入其次步。實(shí)現(xiàn)放寬之后，能夠得到三個結(jié)論：原整數(shù)規(guī)劃的可行域真包含于相應(yīng)線性規(guī)劃的可行域。不失一般性，單就最大化問題而言（下同），原整數(shù)規(guī)劃的最優(yōu)值不大于相應(yīng)線性規(guī)劃的最優(yōu)解。若相應(yīng)線性規(guī)劃的最優(yōu)解滿足原整數(shù)規(guī)劃的整數(shù)條件，則它也是原整數(shù)規(guī)劃的最優(yōu)解。主要特征就是放寬。指通過刪去整數(shù)條件，把原整數(shù)規(guī)劃化成相應(yīng)線性規(guī)劃。其次步主要特征是分枝。從相應(yīng)線性規(guī)劃的最優(yōu)解中，隨意選擇一個不滿足原整數(shù)規(guī)劃整數(shù)條件的決策變量xj=bj。以使相應(yīng)線性規(guī)劃增加一個約束條件；xj小于bj的最大整數(shù)（或xj大于bj的最小整數(shù)），因而得到兩個新的線性規(guī)劃，稱為分枝。其中每個新的線性規(guī)劃，統(tǒng)稱為枝。經(jīng)過分枝之后，就有如下結(jié)論：原整數(shù)規(guī)劃的可行域真包含于兩枝可行域的并集。原整數(shù)規(guī)劃的最優(yōu)解不大于兩枝最優(yōu)值的最大值。其次步的具體作法是：先列出兩枝各自的數(shù)學(xué)模型，后計算每枝的最優(yōu)解和最優(yōu)值。

第三步主要特征就是定界，由各枝的最優(yōu)值中選最大值，稱為定界。而該最大值，稱為界。最優(yōu)值稱為界的枝，稱為界枝。完成定界之后，即可得到這樣的結(jié)論：若界枝的最優(yōu)解滿足原整數(shù)規(guī)劃的最優(yōu)條件，則它也是原整數(shù)規(guī)劃的最優(yōu)解。第三步的具體做法為：進(jìn)行定界，找出界枝。若界枝的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解，則計算過程便告結(jié)束；否則，回到其次步。

解：它是例2的數(shù)學(xué)模型，并且屬于最大化純整數(shù)規(guī)劃。為便于敘述，我們將其記作A?，F(xiàn)在利用分枝定界法求解之。例3

利用分枝定界法求解：A放寬：由A得到相應(yīng)線性規(guī)劃，記作B。實(shí)行圖解法或單純形法，求得B的最優(yōu)解（x1,x2）=（2.25,3.75）最優(yōu)值ymax=41.25。BB的最優(yōu)解不滿足A的整數(shù)條件，所以它并非A的最優(yōu)解。分枝：由B的最優(yōu)解中，選擇決策變量x2=3.75，依據(jù)既定的原則寫出B的兩枝：把它們依次記作B1和B2。解B1得：最優(yōu)解（x1，x2）=（3，3）,最優(yōu)值ymax=39解B2得：最優(yōu)解（x1，x2）=（1.8,4）,最優(yōu)值ymax=41B1B2

B

x1=2.25x2=3.75y=41.25

B1

x1=3

x2=3

y=39

B2

x1=1.8

x2=4

y=41x2≤3x2≥4已完成的求解過程和所得到的計算結(jié)果可用框圖來表示，見下圖。定界：由圖可知。界為max{39，41}=41。于是界枝是B2。但是，B2的最優(yōu)解不滿足A的整數(shù)條件，從而它不是A的最優(yōu)解。因此，應(yīng)當(dāng)再次分枝。其次次分枝：由B2的最優(yōu)解中，選擇決策變量x1=1.8，寫出B2的兩枝：解B21得：最優(yōu)解（x1，x2）=（1，4），最優(yōu)值ymax=40.不難推斷，B22無可行解。B21B22至此，已完成的求解過程和所得到的計算結(jié)果運(yùn)用框圖來表示，如圖所示：

B

x1=2.25

x2=3.75

y=41.25

B1

x1=3

x2=3

y=39

B2

x1=1.8

x2=4

y=41

B21

x1=1

x2=40/9

y=365/9

B22

無可行解x2≤3x2≥4x1≤1x1≥2第三次分枝：解B211得：最優(yōu)解（x1,x2）=（1,4）,最優(yōu)值ymax=37。解B212得：最優(yōu)解（x1,x2）=（0,5）,最優(yōu)值ymax=40。B212B211其次次定界：由上圖可知，界為max{39，365/9}=365/9。界枝為B21.因為B21最優(yōu)解不滿足A的整數(shù)條件，不是A的最優(yōu)解。由B21最優(yōu)解中，選擇變量把B21分成兩枝：現(xiàn)在，已完成的求解過程和所得到的計算結(jié)果見下圖：

B

x1=2.25

x2=3.75

y=41.25

B1

x1=3

x2=3

y=39

B2

x1=1.8

x2=4

y=41

B21

x1=1

x2=40/9

y=365/9

B22

無可行解x2≤

3x2≥

4x1≤

1x1≥

2B211x1=1x2=4y=37B212x1=0x2=5y=40x2≥

5x2≤

4

第三次定界：由上圖可知，界為max{39,37,40}=40.所以，界枝是B212。由于B212的最優(yōu)解滿足A的整數(shù)條件，它確定也是A的最優(yōu)解。于是，原整數(shù)規(guī)劃的最優(yōu)解為：（x1，x2）=（0，5），最優(yōu)值ymax=40。例3是一個利用分枝定解法求解純整數(shù)規(guī)劃問題，其基本步驟也適用于混整數(shù)規(guī)劃問題。A1A2A3A4A5A6A7A8需要量（根）