整數(shù)規(guī)劃數(shù)學(xué)模型完整版

1

整數(shù)線性規(guī)劃（IntegerLinearProgramming）§1整數(shù)線性規(guī)劃問(wèn)題的提出

線性規(guī)劃的最優(yōu)解有時(shí)候可能是分?jǐn)?shù)或小數(shù)，事實(shí)上，線性規(guī)劃是連續(xù)變量的線性優(yōu)化問(wèn)題。但在實(shí)際中，常有要求解答必須是整數(shù)的情形（稱為整數(shù)解）。例如，所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)或裝貨的車(chē)數(shù)等，分?jǐn)?shù)或小數(shù)的解答就不合要求。把帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過(guò)“舍入化整”常常是不行的，因?yàn)榛蟛灰欢ㄊ强尚薪猓换蛘唠m是可行解但不一定是最優(yōu)解。因此，對(duì)求最優(yōu)整數(shù)解的問(wèn)題需要另行研究。我們稱這樣的問(wèn)題為整數(shù)線性規(guī)劃。2整數(shù)線性規(guī)劃的可行解集為點(diǎn)集對(duì)應(yīng)與其松弛問(wèn)題的可行解的整數(shù)點(diǎn)集maxz=x1+4x2s.t.-2x1+3x2≤

3x1+2x2≤

8x1,x2≥0,且為整數(shù)***********oAB(18/7,19/7)312R1:X1=18/7x2=19/7Z=13.430A1A2ABCA3A4R2:OA1A4Cx1=2x2=7/3Z=11.33R3:A2AA3x1=3x2=5/2z=13無(wú)可行解R4:A2A5A6AX1=4x2=2Z=12A5A64整數(shù)規(guī)劃：要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問(wèn)題。整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題：不考慮整數(shù)要求，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題。整數(shù)線性規(guī)劃：若松弛問(wèn)題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。5整數(shù)規(guī)劃中，如果所有的變量都要求是（非負(fù)）整數(shù)，就稱為純整數(shù)規(guī)劃(PureIntegerProgramming)或全整數(shù)規(guī)劃(AllIntegerProgramming)；如果僅是其中一部分變量取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(MixedIntegerProgramming)。整數(shù)線性規(guī)劃的一種特殊情形是0-1規(guī)劃，它的變量取值僅限于0或1。指派問(wèn)題就是一種特殊的0-1規(guī)劃。6例1某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如下表所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？貨物體積(米3/箱)重量(百公斤/箱)利潤(rùn)(千元/箱)甲5220乙4510裝運(yùn)限制24137解：設(shè)X1,X2為甲、乙兩貨物各托運(yùn)箱數(shù)5X1+4X2

242X1+5X2

13X1,X20X1,X2為整數(shù)maxZ=20X1+

10X28例2背包問(wèn)題背包可裝入8單位重量，10單位體積物品物品名稱重量體積價(jià)值1書(shū)52202攝像機(jī)31303枕頭14104休閑食品23185衣服45159解：Xi為是否帶第i種物品maxZ=20X1+

30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5

82X1+X2+4X3+3X4+5X510Xi為0,110,整數(shù)§2整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型11(1)、Xi為i物品攜帶數(shù)量

ai為i物品單位重量

ci為i物品重要性估價(jià)

b為最大負(fù)重(2)、投資決策

Xi為在i地區(qū)建廠規(guī)模

ai為在i地區(qū)建廠基建費(fèi)用

ci為在i地區(qū)建廠單位利潤(rùn)

b為最大資本(3)、Xi取0或1時(shí)，可作項(xiàng)目投資模型12例3選址問(wèn)題A1A3B2B4B3B1A2Ai:可建倉(cāng)庫(kù)地點(diǎn)，容量ai,投資費(fèi)用bi，建2個(gè)Bj:商店，需求dj(j=1…4)Cij:倉(cāng)庫(kù)i到商店j的單位運(yùn)費(fèi)問(wèn)：選擇適當(dāng)?shù)攸c(diǎn)建倉(cāng)庫(kù)，在滿足商店需求條件下，總費(fèi)用最小。13解：設(shè)Xi(i=1,2,3)為是否在Ai建倉(cāng)庫(kù)

yij(i=1,2,3,j=1…4)由i倉(cāng)庫(kù)向j商店運(yùn)貨量y11+y21=d1y12+y22+y32=d2y23+y33=d3y14+y24+y34=d4x1+x2+x3=2y11+y12+y14a1x1y21+y22+y23+y24a2x2y32+y33+y34a3x3xi為0－1，yij0混合整數(shù)規(guī)劃14

§30－1決策變量的應(yīng)用0-1變量通常表示“是”或“否”這樣的邏輯是非判斷，可以在很多問(wèn)題中應(yīng)用。

1.可用于相互排斥計(jì)劃中例4運(yùn)輸方式：火車(chē)、船?；疖?chē)：5X1+4X2

24(體積)船：7X1+3X2

45(體積)15maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My1

火車(chē)7X1+3X2

45+M(1-y1

)船X1,

X20整數(shù)y1為0或1

M>0當(dāng)y1=0火車(chē)

y1

=1船16maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My1

火車(chē)7X1+3X2

45+My2船X1,

X20整數(shù)y1+y2=1當(dāng)y1,y2=0,117例5.ai1x1+ai2x2+…+ainxn

bi(i=1,…,m)互相排斥m個(gè)約束，只有一個(gè)起作用ai1x1+…+ainxn

bi+yiM

(i=1,…,m)y1+…+ym=m-1yi為0或1M>0182.投資選址某公司擬在市東，西，南三區(qū)建門(mén)市部，擬議中有7個(gè)位置可供選擇，規(guī)定在東區(qū)，A1,A2,A3三個(gè)點(diǎn)至多選2個(gè)在西區(qū)，A4,A5兩個(gè)點(diǎn)至少選1個(gè)在南區(qū)，A6,A7兩個(gè)點(diǎn)至少選1個(gè)若選Ai點(diǎn)，投資bi,每年利潤(rùn)C(jī)i,總投資不超過(guò)B。19xi=1,Ai點(diǎn)建門(mén)市部

=0，Ai點(diǎn)不建門(mén)市部Maxz=∑CiXiSt∑biXi≤BX1+X2+X3≤2X4+X5≥1X6+X7≥1Xi=0,120覆蓋選址問(wèn)題以最少數(shù)目的地點(diǎn)覆蓋所有區(qū)域可能的分布地址覆蓋區(qū)域

Ax11，5，7Bx21，2，5，7Cx31，3，5Dx42，4，5Ex53，4，6Fx64，5，6Gx71，5，6，721Minz=x1+x2+x3+x4+x5+x6+x7

(Xi分別代表ABCDEFG)Stx1+x2+x3+x7≥1地點(diǎn)1x2+x4≥1地點(diǎn)2x3+x5≥1地點(diǎn)3x4+x5+x6≥1地點(diǎn)4x1+x2+x3+x4+x6+x7≥1地點(diǎn)5x5+x6+x7≥1地點(diǎn)6x1+x2+x7≥1地點(diǎn)7xi=0,122分公司選址問(wèn)題某銷(xiāo)售公司打算通過(guò)在武漢或長(zhǎng)春設(shè)立分公司（也許在2個(gè)城市都設(shè)分公司）增加市場(chǎng)份額，管理層同時(shí)也計(jì)劃在新設(shè)分公司的城市至多建一個(gè)配送中心，也可以不建配送中心。經(jīng)過(guò)財(cái)務(wù)和技術(shù)經(jīng)濟(jì)專家的計(jì)算，每種選擇對(duì)公司收益的凈現(xiàn)值、每種選擇所需的費(fèi)用如下，總的預(yù)算費(fèi)用不得超過(guò)20萬(wàn)元。目標(biāo)是在滿足以上約束的條件下使總的凈現(xiàn)值最大。23問(wèn)題決策變量?jī)衄F(xiàn)值(萬(wàn)元)所需資金(萬(wàn)元)

是否在長(zhǎng)春設(shè)分公司x11812是否在武漢設(shè)分公司x2106是否在長(zhǎng)春建配送中心x31210是否在武漢建配送中心x48424maxZ=18x1+10x2+12x3+8x4st12x1+6x2+10x3+4x4≤20x3+x4≤1x3≤x1x4≤x2xj=0,1，j=1,2,3,4253.固定成本問(wèn)題關(guān)于固定費(fèi)用問(wèn)題Xj表示產(chǎn)量Cj單位變動(dòng)成本Kj表示固定成本Pj為總成本Pj=Kj+CjXj,Xj>0=0,Xj=0,j=1,2,326固定成本核算產(chǎn)品利潤(rùn)原料1原料2原料3固定成本添加劑400.40.6200溶劑300.50.20.350清潔劑500.60.10.340020噸5噸21噸27不考慮固定成本maxZ=40x1+30x2+50x30.4x1+0.5x2+0.6x3≤20