第3章整數(shù)1分支定界

第

3

章Integer

ProgrammingI

P整數(shù)規(guī)劃3.1整數(shù)規(guī)劃問題及其建模3.2分支定界法3.3割平面法3.40-1型整數(shù)線性規(guī)劃的解法3.5指派問題第3章整數(shù)規(guī)劃第3章整數(shù)規(guī)劃2基本概念整數(shù)規(guī)劃：變量取整數(shù)的線性規(guī)劃；純整數(shù)規(guī)劃：所有變量都取整數(shù)的線性規(guī)劃；混合整數(shù)規(guī)劃：部分變量取整數(shù)的線性規(guī)劃；0-1規(guī)劃：所有變量都取0、1兩個(gè)值的規(guī)劃；0-1混合規(guī)劃：部分變量取0、1兩個(gè)值的規(guī)劃。整數(shù)規(guī)劃問題及其建模

問題的提出例1

某廠在一計(jì)劃期內(nèi)擬生產(chǎn)甲、乙兩種大型設(shè)備。該廠有充分的生產(chǎn)能力來加工制造這兩種設(shè)備的全部零部件，所需原材料和能源也可滿足供應(yīng)，不過有A、B兩種緊缺物資的供量受到嚴(yán)格控制，與此有關(guān)的數(shù)據(jù)如下表所示。問該廠在計(jì)劃期內(nèi)應(yīng)安排生產(chǎn)甲、乙設(shè)備各多少臺，才能使利潤達(dá)到最大？設(shè)備原料甲乙單臺所需原料數(shù)量A（噸）

B

(千克)2157可供量935單臺利潤（萬元）65x1x2z整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃的幾個(gè)典型問題及其模型投資決策問題

設(shè)有n個(gè)投資項(xiàng)目，其中第j個(gè)項(xiàng)目需要資金aj萬元，將來可獲利潤cj萬元。若現(xiàn)有資金總額為b萬元，則應(yīng)選擇哪些投資項(xiàng)目，才能獲利最大？

1，若對第j個(gè)項(xiàng)目投資，

0，不然；

設(shè)z為可獲得的總利潤(萬元)

，則數(shù)學(xué)模型為xj=s.t.(j=1,2,…,n)

設(shè)0-1背包問題xj=0或

1，j=1，2，···，najxj≤bj=1

n

maxz

=

cjxj

j=1

n整數(shù)規(guī)劃問題及其數(shù)學(xué)模型s.t.設(shè)

yi＝購買設(shè)備Ａi的臺數(shù)

xij＝將設(shè)備Ａi裝置于Ｂj處的臺數(shù)

z＝預(yù)計(jì)總利潤數(shù)學(xué)模型為設(shè)備購置問題

某廠擬用M元資金購買m種設(shè)備A1，A2，···，Am，其中設(shè)備Ai單價(jià)為pi（i＝１，２，···，m）?，F(xiàn)有n個(gè)地點(diǎn)B1，B2

，···，Bn可裝置這些設(shè)備，其中Bj

處最多bj臺（j＝１，２，···，n）。預(yù)計(jì)將一臺設(shè)備Ai裝備于Bj處可獲純利cij元，則應(yīng)如何購置這些設(shè)備，才能使預(yù)計(jì)總利潤為最大？xij

≥

0，

yi

≥

0xij,yi均為整數(shù)

xij

–yi

≤0，

i=1，2，···

，mj=1n

xij

≤

bj

，

j

=1，2，···

，ni=1mmax

z

=

cijxijj=1i=1nmpiyi

≤

Mi=1m整數(shù)規(guī)劃問題及其數(shù)學(xué)模型工廠選址問題

某種商品有n個(gè)銷地,各銷地的需求量分別為bj噸/天，j

=1，2，···，n?，F(xiàn)擬在m個(gè)地點(diǎn)中選址建廠，來生產(chǎn)這種產(chǎn)品以滿足供應(yīng)，且規(guī)定一址最多只能建一個(gè)工廠。若選i址建廠，將來生產(chǎn)能力為ai噸/天，固定費(fèi)用為di元/天，i=1，2，···，m.已知i址至銷地j的運(yùn)價(jià)為cij元/噸。應(yīng)如何選擇廠址和安排調(diào)運(yùn)，使總的費(fèi)用最少？設(shè)yi

=xij

≥0，

yi

=

0或1s.t.1，若在

i址建廠

0，否則xij=從廠址

i到銷地

j

的運(yùn)量(噸/天)z

=

總費(fèi)用(元/天)

min

z

=

cij

xij

+diyii=1

m

j=1ni=1

m

j=1n

xij

≤

aiyi

，i

=

1，2，···，mi=1

m

xij

=bj,

j

=

1，2，···，n該問題的數(shù)學(xué)模型為線性規(guī)劃與整數(shù)規(guī)劃的關(guān)系8線性規(guī)劃整數(shù)規(guī)劃X*=（13/5，19/5）Z*=89/5=17.8X*=（5，3）Z*=17整數(shù)規(guī)劃問題的求解？maxz=6x1+5x22x1+x2≤9①5x1+7x2≤35②

x1≥0,x2≥0③

x1,

x2為整數(shù)s.t.伴隨LP問題——

整數(shù)性約束LP解

x1

x2

z可行？最優(yōu)？是

1

93

7

92

5

932圓整四舍五入33否只舍不入3228IP解4129是否是?整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃的圖解法······················65123412345A(3,

2)19790B(3,3)x1x2①②

?(4,1)x1*

=4x2*

=1z*

=29具體的幾個(gè)問題分支定界法割平面法0-1整數(shù)規(guī)劃指派問題由此得到兩個(gè)新約束：

①x2≤2

,②x2≥3整數(shù)規(guī)劃的一般解法分支定界法試用分支定界法求解例1中的IP問題解先求其松弛問題，其最優(yōu)解為:1

937

925

932x1=

,

x2=

；z=比如x2=

,7

92由于它非整數(shù)解，所以要以它為試點(diǎn)對問題進(jìn)行分支。為此，可從非整數(shù)值的x1,x2中任選一個(gè),

整數(shù)規(guī)劃的一般解法1234512345x1x20(5)無可行解(1)(2)(3)(4)(6)(7)(8)(9)最優(yōu)解A(3,

2)19796.2

整數(shù)規(guī)劃的一般解法x2≤2x2≥3(6)x1=3x2=2z=28(7)x1=4x2=1z=29x1≤3x1≥4x1≤2x1≥3(5)無可行解x√√(8)x1=2x2=3z=27x2≥4x2≤3√x(1)19x1=359z=3279x2=2(2)x2=2z=3112x1=3(3)x2=345x1=245z=31(4)x1=247x2=367z=29(9)x2=425x1=125z=28探明？停+選上界大的先分支-x1*=4x2*=1z*=29步驟：第一步具體作法是：首先，刪去整數(shù)條件，把原整數(shù)規(guī)劃化成相應(yīng)線性規(guī)劃。其次，求解相應(yīng)線性規(guī)劃。

主要特征就是放寬條件。最后，①如果相應(yīng)線性規(guī)劃沒有可行解，則原整數(shù)規(guī)劃也沒有可行解。則停止；

②如果相應(yīng)線性規(guī)劃有最優(yōu)解，且符合原整數(shù)規(guī)劃問題的整數(shù)條件，則這個(gè)最優(yōu)解也是原整數(shù)規(guī)劃的最優(yōu)解，那么整個(gè)計(jì)算過程結(jié)束；

③如果相應(yīng)線性規(guī)劃有最優(yōu)解，但不符合原整數(shù)規(guī)劃問題的整數(shù)條件，則這個(gè)最優(yōu)解不是原整數(shù)規(guī)劃的最優(yōu)解，

記此最優(yōu)值為原整數(shù)規(guī)劃問題Z*的上界,

然后,用觀察法求出下界，轉(zhuǎn)入第二步。主要特征是分支。

具體作法：從相應(yīng)線性規(guī)劃的最優(yōu)解中，任意選擇一個(gè)不滿足原整數(shù)規(guī)劃整數(shù)條件的決策變量xj=bj以使相應(yīng)線性規(guī)劃增加一個(gè)約束條件；

xj小于bj的最大整數(shù)（或xj大于bj的最小整數(shù)），因而得到兩個(gè)新的線性規(guī)劃稱為分支，也稱為后繼問題。列出兩分支各自的數(shù)學(xué)模型，計(jì)算每支的最優(yōu)解和最優(yōu)值。步驟：第二步：

經(jīng)過分支之后，就有如下結(jié)論：分支后并沒有減少整數(shù)解，故原整數(shù)規(guī)劃的可行域真包含于兩支可行域的并集。原整數(shù)規(guī)劃的最優(yōu)解不大于兩支最優(yōu)值的最大值。主要特征就是定界.

具體作法：以每個(gè)后繼問題為一分支標(biāo)明求解的結(jié)果，與其他問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界；從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界z，若無可行解，z=0步驟：第三步：z步驟：第四步：比較與剪支：各分支的最優(yōu)目標(biāo)函數(shù)中若有小于z

者，則剪掉這支，即以后不再考慮了。若有大于z,但不符合整數(shù)條件，則繼續(xù)分支，一直到最后得到z*=z為止，得最優(yōu)整數(shù)解xj*，j=1，…，n用分支定界法可解純整數(shù)線性規(guī)劃問題和混合整數(shù)線性規(guī)劃問題。它比窮舉法優(yōu)越。因?yàn)樗鼉H在一部分可行解的整數(shù)解中尋求最優(yōu)解，計(jì)算量比窮舉法小。若變量數(shù)目很大，其計(jì)算工作量也是相當(dāng)可觀的。例：第一步：放寬——刪除整數(shù)條件L0：L0的最優(yōu)解為(3.25，2.5)，z*=14.75轉(zhuǎn)第二步.得整數(shù)規(guī)劃的松弛問題如下：x1x2O第二步：分支與定界.L0的最優(yōu)解為(3.25，2.5).z*=14.75L1：L2：L1的最優(yōu)解為(3.5，2)，z1=14.5L2的最優(yōu)解為(2.5，3)，z2=13.5××××××××××23未失去整數(shù)解即整數(shù)規(guī)劃的可行域被全部保留其中ｚ1>z2，對L1繼續(xù)分枝L1的最優(yōu)解為(3.5，2)，z1=14.5將整數(shù)解化為一個(gè)分枝的可行域的極點(diǎn)x1x2××××××××××O圖4-4L11：L11的最優(yōu)解為(3，2)，z11=13L12的最優(yōu)解為(4，1)，z12=14L12：其中ｚ11<z12L1：L2的最優(yōu)