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

1

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

線性規(guī)劃的最優(yōu)解有時候可能是分?jǐn)?shù)或小數(shù)，事實上，線性規(guī)劃是連續(xù)變量的線性優(yōu)化問題。但在實際中，常有要求解答必須是整數(shù)的情形（稱為整數(shù)解）。例如，所求解是機(jī)器的臺數(shù)、完成工作的人數(shù)或裝貨的車數(shù)等，分?jǐn)?shù)或小數(shù)的解答就不合要求。把帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整”常常是不行的，因為化整后不一定是可行解；或者雖是可行解但不一定是最優(yōu)解。因此，對求最優(yōu)整數(shù)解的問題需要另行研究。我們稱這樣的問題為整數(shù)線性規(guī)劃。2整數(shù)線性規(guī)劃的可行解集為點集對應(yīng)與其松弛問題的可行解的整數(shù)點集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無可行解R4:A2A5A6AX1=4x2=2Z=12A5A64整數(shù)規(guī)劃：要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題。整數(shù)規(guī)劃問題的松弛問題：不考慮整數(shù)要求，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題。整數(shù)線性規(guī)劃：若松弛問題是一個線性規(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。指派問題就是一種特殊的0-1規(guī)劃。6例1某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如下表所示。問兩種貨物各托運多少箱，可使獲得利潤為最大？貨物體積(米3/箱)重量(百公斤/箱)利潤(千元/箱)甲5220乙4510裝運限制24137解：設(shè)X1,X2為甲、乙兩貨物各托運箱數(shù)5X1+4X2

242X1+5X2

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

10X28例2背包問題背包可裝入8單位重量，10單位體積物品物品名稱重量體積價值1書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ī)劃問題的數(shù)學(xué)模型11(1)、Xi為i物品攜帶數(shù)量

ai為i物品單位重量

ci為i物品重要性估價

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

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

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

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

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

yij(i=1,2,3,j=1…4)由i倉庫向j商店運貨量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變量通常表示“是”或“否”這樣的邏輯是非判斷，可以在很多問題中應(yīng)用。

1.可用于相互排斥計劃中例4運輸方式：火車、船?；疖嚕?X1+4X2

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

45(體積)15maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My1

火車7X1+3X2

45+M(1-y1

)船X1,

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

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

y1

=1船16maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My1

火車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個約束，只有一個起作用ai1x1+…+ainxn

bi+yiM

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

=0，Ai點不建門市部Maxz=∑CiXiSt∑biXi≤BX1+X2+X3≤2X4+X5≥1X6+X7≥1Xi=0,120覆蓋選址問題以最少數(shù)目的地點覆蓋所有區(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地點1x2+x4≥1地點2x3+x5≥1地點3x4+x5+x6≥1地點4x1+x2+x3+x4+x6+x7≥1地點5x5+x6+x7≥1地點6x1+x2+x7≥1地點7xi=0,122分公司選址問題某銷售公司打算通過在武漢或長春設(shè)立分公司（也許在2個城市都設(shè)分公司）增加市場份額，管理層同時也計劃在新設(shè)分公司的城市至多建一個配送中心，也可以不建配送中心。經(jīng)過財務(wù)和技術(shù)經(jīng)濟(jì)專家的計算，每種選擇對公司收益的凈現(xiàn)值、每種選擇所需的費用如下，總的預(yù)算費用不得超過20萬元。目標(biāo)是在滿足以上約束的條件下使總的凈現(xiàn)值最大。23問題決策變量凈現(xiàn)值(萬元)所需資金(萬元)

是否在長春設(shè)分公司x11812是否在武漢設(shè)分公司x2106是否在長春建配送中心x31210是否在武漢建配送中心x48424maxZ=18x1+10x2+12x3+8x4st12x1+6x2+10x3+4x4≤20x3+x4≤1x3≤x1x4≤x2xj=0,1，j=1,2,3,4253.固定成本問題關(guān)于固定費用問題Xj表示產(chǎn)量Cj單位變動成本Kj表示固定成本Pj為總成本Pj=Kj+CjXj,Xj>0=0,Xj=0,j=1,2,326固定成本核算產(chǎ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