管理運(yùn)籌學(xué)第八章 整數(shù)規(guī)劃

管理運(yùn)籌學(xué)第八章整數(shù)規(guī)劃第八章整數(shù)規(guī)劃在整數(shù)規(guī)劃中：純整數(shù)規(guī)劃問(wèn)題：所有變量均為非負(fù)整數(shù)0-1規(guī)劃：變量的取值只限0和1

混合整數(shù)規(guī)劃問(wèn)題：部分變量為非負(fù)整數(shù)整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的分枝定界法本章內(nèi)容12340-1規(guī)劃的解法5§1整數(shù)規(guī)劃的圖解法例1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表。甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大。貨物每件體積/立方英尺

每件重量/百千克每件利潤(rùn)/百元甲19542乙273403托運(yùn)限制1365140§1整數(shù)規(guī)劃的圖解法解：設(shè)x1、x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：maxz=2x1+3x2約束條件：s.t.195x1+273x2≤1365(體積限制) x1≤4 4x1+40x2≤140(重量限制)x1,x2≥0,去掉最后一個(gè)約束，是一個(gè)線性規(guī)劃問(wèn)題。為整數(shù)x2§1整數(shù)規(guī)劃的圖解法利用圖解法

32101234x12x1+3x2=62x1+3x2=14.662x1+3x2=14××××××××××××線性規(guī)劃的最優(yōu)解為x1=2.44，x2=3.26，目標(biāo)函數(shù)值為14.66。由圖可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4，x2=2，目標(biāo)函數(shù)值為14.×整數(shù)規(guī)劃的最優(yōu)解不都是相應(yīng)的線性規(guī)劃的最優(yōu)解，通過(guò)“四舍五入”、“進(jìn)一法”或“去尾法”獲得。

§1整數(shù)規(guī)劃的圖解法性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的分枝定界法本章內(nèi)容21340-1規(guī)劃的解法5§2整數(shù)規(guī)劃的計(jì)算機(jī)求解例2

maxz=3x1+x2+3x3 s.t. ?x1+2x2+x3≤4 4x2?3x3≤2

x1?3x2+2x3≤3

x1,x2,x3≥0

x1,x2,x3為整數(shù)§2整數(shù)規(guī)劃的計(jì)算機(jī)求解

用管理運(yùn)籌學(xué)軟件求解§2整數(shù)規(guī)劃的計(jì)算機(jī)求解

maxz=3x1+x2+3x3 s.t. ?x1+2x2+x3≤4 4x2?3x3≤2

x1?3x2+2x3≤3

x1,x2,x3≥0

x1為整數(shù),x3為0?1變量例3§2整數(shù)規(guī)劃的計(jì)算機(jī)求解

用管理運(yùn)籌學(xué)軟件求解整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的分枝定界法本章內(nèi)容3140-1規(guī)劃的解法52§3整數(shù)規(guī)劃的應(yīng)用一、投資場(chǎng)所的選擇 例4．京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門(mén)市部，擬議中有10個(gè)位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定： 在東區(qū)由A1，A2，A3三個(gè)點(diǎn)至多選擇兩個(gè)； 在西區(qū)由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)； 在北區(qū)由A8，A9，A10三個(gè)點(diǎn)中至少選兩個(gè)。

§3整數(shù)規(guī)劃的應(yīng)用

Aj各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同而不同，預(yù)測(cè)情況如（單位：萬(wàn)元）。但投資總額不超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)最大？

A1A2A3A4A5A6A7A8A9A10投資額10012015080709080140160180利潤(rùn)36405022203025485861§3整數(shù)規(guī)劃的應(yīng)用解：設(shè)：0?1變量xi

=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒(méi)被選用）。建立數(shù)學(xué)模型：

maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10

s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xi≥0,且xi為0-1變量,i=1,2,3,…,10

在東區(qū)由A1，A2，A3三個(gè)點(diǎn)至多選擇兩個(gè)在西區(qū)由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)在南區(qū)由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)在北區(qū)由A8，A9，A10三個(gè)點(diǎn)中至少選兩個(gè)投資額約束§3整數(shù)規(guī)劃的應(yīng)用

應(yīng)用“管理運(yùn)籌學(xué)軟件”求解： 最優(yōu)目標(biāo)函數(shù)值為245。 最優(yōu)解為:x1=1,x2=1,x3=0,x4=0,x5=1,x6=1,x7=0,x8=0,x9=1,x10=1

§3整數(shù)規(guī)劃的應(yīng)用二、固定成本問(wèn)題 例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表。不考慮固定費(fèi)用，每種容器單位利潤(rùn)分別為4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板500噸，勞動(dòng)力300人/月，機(jī)器100臺(tái)/月，此外只要生產(chǎn)，須支付固定費(fèi)用：小號(hào)是l00萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元。制定一個(gè)生產(chǎn)計(jì)劃，使獲利最大。§3整數(shù)規(guī)劃的應(yīng)用

資源小號(hào)容器中號(hào)容器大號(hào)容器金屬板/t248勞動(dòng)力/（人/月）234機(jī)器設(shè)備/（臺(tái)/月）123§3整數(shù)規(guī)劃的應(yīng)用解：整數(shù)規(guī)劃問(wèn)題 設(shè)x1，x2，x3分別為小號(hào)、中號(hào)和大號(hào)容器的生產(chǎn)數(shù)量。固定費(fèi)用：設(shè)yi=1（當(dāng)生產(chǎn)第i種容器，即xi＞0時(shí)）或0（當(dāng)不生產(chǎn)第i種容器即xi=0時(shí)）。引入約束xi≤Myi，i=1，2，3，M充分大?！?整數(shù)規(guī)劃的應(yīng)用建立數(shù)學(xué)模型： maxz=4x1+5x2+6x3-100y1-150y2-200y3 s.t.2x1+4x2+8x3≤500（金屬板約束）2x1+3x2+4x3≤300（勞動(dòng)力約束） x1+2x2+3x3≤100（機(jī)器設(shè)備約束）xi≤Myi，i=1，2，3，M充分大xi≥0，yi為0-1變量，i=1,2,3

軟件計(jì)算：最大目標(biāo)函數(shù)值為300，最優(yōu)解為x1=100，x2=0，x3=0?！?整數(shù)規(guī)劃的應(yīng)用三、指派問(wèn)題有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使完成n項(xiàng)任務(wù)的總效率最高，即指派問(wèn)題。

§3整數(shù)規(guī)劃的應(yīng)用例6．有四個(gè)工人，分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如表，應(yīng)如何指派工作，才能使總消耗時(shí)間最少。

工作所需時(shí)間/小時(shí)工人ABCD甲15182124乙19232218丙26171619丁19212317§3整數(shù)規(guī)劃的應(yīng)用解：引入0?1變量xij，令xij=1(指派第i人去完成第j項(xiàng)工作)xij=0（不指派第i人去完成第j項(xiàng)工作）構(gòu)建0?1整數(shù)規(guī)劃問(wèn)題。

§3整數(shù)規(guī)劃的應(yīng)用Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.tx11+x12+x13+x14=1（甲只能干一項(xiàng)工作） x31+x32+x33+x34=1（丙只能干一項(xiàng)工作） x41+x42+x43+x44=1（丁只能干一項(xiàng)工作）x21+x22+x23+x24=1（乙只能干一項(xiàng)工作）x11+x21+x31+x41=1（A工作只能一人干）x12+x22+x32+x42=1（B工作只能一人干）x13+x23+x33+x43=1（C工作只能一人干）x14+x24+x34+x44=1（D工作只能一人干） xij為0?1變量，i,j=1,2,3,4

§3整數(shù)規(guī)劃的應(yīng)用應(yīng)用“管理運(yùn)籌學(xué)軟件”：最優(yōu)解為x21=1，x12=1，x33=1，x44=1.最小目標(biāo)函數(shù)值為70.

§3整數(shù)規(guī)劃的應(yīng)用m個(gè)人n項(xiàng)任務(wù)的一般的指派問(wèn)題：設(shè)Xij=1，第i人去完成j項(xiàng)工作；Xij=0，第i人不去完成j項(xiàng)工作；cij為第i人去完成j項(xiàng)任務(wù)的成本（如時(shí)間、費(fèi)用）一般指派問(wèn)題的模型為：約束條件：也可以使用“管理運(yùn)籌學(xué)軟件”中“整數(shù)規(guī)劃”子程序中的“指派問(wèn)題”來(lái)求解§3整數(shù)規(guī)劃的應(yīng)用四、分布系統(tǒng)設(shè)計(jì) 例7．某企業(yè)在A1地有一工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)（每千箱運(yùn)費(fèi)）如表。

§3整數(shù)規(guī)劃的應(yīng)用該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使總固定成本和運(yùn)輸費(fèi)用之和最小?若政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠？

§3整數(shù)規(guī)劃的應(yīng)用

。銷地運(yùn)費(fèi)單價(jià)/元產(chǎn)地B1B2B3產(chǎn)量/千箱A184330A252310A343420A497530A5104240銷量/千箱302020§3整數(shù)規(guī)劃的應(yīng)用解：（1）設(shè)xij為從Ai運(yùn)往Bj的運(yùn)輸量（單位：千箱）yk=1（Ak被選中）yk=0（Ak沒(méi)被選中），k=2,3,4,5．

§3整數(shù)規(guī)劃的應(yīng)用 minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53構(gòu)建整數(shù)規(guī)劃問(wèn)題：§3整數(shù)規(guī)劃的應(yīng)用s.tx11+x12+x13≤30(A1廠的產(chǎn)量限制)x21+x22+x23≤10y2(A2廠的產(chǎn)量限制)x31+x32+x33≤20y3(A3廠的產(chǎn)量限制)x41+x42+x43≤30y4(A4廠的產(chǎn)量限制)x51+x52+x53≤40y5(A5廠的產(chǎn)量限制)x11+x21+x31+x41+x51=30(B1銷地的限制)x12+x22+x32+x42+x52=20(B2銷地的限制)x13+x23+x33+x43+x53=20(B3銷地的限制)xij≥0,且為整數(shù)，i=1,2,3,4,5；j=1,2,3，yk為0?1變量，k=2,3,4,5。注：求解可用“管理運(yùn)籌學(xué)”軟件中整數(shù)規(guī)劃子程序?！?整數(shù)規(guī)劃的應(yīng)用最優(yōu)解：y5=1,x52=20,x53=20,x11=30,最優(yōu)值為860（千元）?！?整數(shù)規(guī)劃的應(yīng)用（2）加入約束條件：y2+y3=1，得到問(wèn)題（2）的數(shù)學(xué)模型 s.tx11+x12+x13≤30(A1廠的產(chǎn)量限制) x21+x22+x23≤10y2(A2廠的產(chǎn)量限制)x31+x32+x33≤20y3(A3廠的產(chǎn)量限制)x41+x42+x43≤30y4(A4廠的產(chǎn)量限制)x51+x52+x53≤40y5(A5廠的產(chǎn)量限制)x11+x21+x31+x41+x51=30(B1銷地的限制) x12+x22+x32+x42+x52=20(B2銷地的限制) x13+x23+x33+x43+x53=20(B3銷地的限制)

y2+y3=1 xij≥0,且為整數(shù)，i=1,2,3,4,5；j=1,2,3， yk為0?1變量，k=2,3,4,5?！?整數(shù)規(guī)劃的應(yīng)用最優(yōu)解：y2=1,y4=1,x22=10,x41=30,x12=10,x13=20,其余變量均為零。最優(yōu)值為940（千元）?！?整數(shù)規(guī)劃的應(yīng)用五、投資問(wèn)題例8．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬(wàn)元，第二、三、四年不限；項(xiàng)目B：第三年初需要投資，到第五年末能回收本利128%，但規(guī)定最低投資金額為3萬(wàn)元，最高金額為5萬(wàn)元；項(xiàng)目C：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元，或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元。項(xiàng)目D：五年內(nèi)每年初可購(gòu)買(mǎi)公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。該部門(mén)現(xiàn)有資金10萬(wàn)元，問(wèn)應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大？

§3整數(shù)規(guī)劃的應(yīng)用解：（1）設(shè)xiA、xiB、xiC、xiD

（i＝1，2，3，4，5）分別表示第i年年初給項(xiàng)目A，B，C，D的投資額；

設(shè)yiA，yiB，是0?1變量，取1時(shí)分別表示第i年給A、B投資，否則取0（i=1,2,3,4,5）。

設(shè)y2C

是非負(fù)整數(shù)變量，X2c=20000y2c：當(dāng)y2c=4，則第2年投資C項(xiàng)目8萬(wàn)元；當(dāng)y2c=3，則第2年投資C項(xiàng)目6萬(wàn)元；當(dāng)y2c=2，則第2年投資C項(xiàng)目4萬(wàn)元；當(dāng)y2c=1，則第2年投資C項(xiàng)目2萬(wàn)元；當(dāng)y2c=0，則第2年不投資C項(xiàng)目。

§3整數(shù)規(guī)劃的應(yīng)用建立決策變量：

年份投資額項(xiàng)目12345Ax1Ax2Ax3Ax4ABx3BCX2c=20000y2cDx1Dx2Dx3Dx4Dx5D§3整數(shù)規(guī)劃的應(yīng)用（3）目標(biāo)函數(shù)及模型：maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.tx1A+x1D=100000，?1.06x1D+x2A+x2C+x2D=0，?1.15x1A?1.06x2D+x3A+x3B+x3D=0，?1.15x2A?1.06x3D+x4A+x4D=0，?1.15x3A?1.06x4D+x5D=0，x1A?40000y1A≥0，x1A?200000y1A≤0，x3B?30000y3B≥0，x3B?50000y3B≤0，x2C?20000y2C=0，y2C≤4，xiA，xiB，xiC，xiD≥0(i=1、2、3、4、5)，y2C為非負(fù)整數(shù)，y1A，y3B為0?1變量。第一年：年初有100000元，D項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x1A+x1D=100000；第二年：A的投資第二年末才可收回，故第二年年初的資金為1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的資金為1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的資金為1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的資金為1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。

關(guān)于項(xiàng)目A的投資額規(guī)定：x1A≥40000y1A，x1A≤200000y1A，200000是足夠大的數(shù)；保證當(dāng)y1A=0時(shí)，x1A=0；當(dāng)y1A=1時(shí)，x1A≥40000。關(guān)于項(xiàng)目B的投資額規(guī)定:x3B≥30000y3B，x3B≤50000y3B；保證當(dāng)y3B=0時(shí)，x3B=0；當(dāng)y3B=1時(shí)，50000≥x3B≥30000。關(guān)于項(xiàng)目C的投資額規(guī)定：x2C=20000y2C，y2C=0，1，2，3，4。§3整數(shù)規(guī)劃的應(yīng)用應(yīng)用“管理運(yùn)籌學(xué)”軟件：最優(yōu)值為147879.234。最優(yōu)解為x2C=60000， x3B=49905.641， x1A=43396.23， x1D=56603.777， y3B=1， y2C=3， y1A=1.§3整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用引入整數(shù)變量，尤其是0-1變量，可將實(shí)際管理中無(wú)法歸結(jié)為線性規(guī)劃模型的問(wèn)題，構(gòu)建整數(shù)規(guī)劃模型?！?整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用1、解決固定成本問(wèn)題(例5）生產(chǎn)成本最小的整數(shù)規(guī)劃模型：約束條件：其他原始限制條件§3整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用2、解決選擇取值問(wèn)題（例7）約束條件的右端項(xiàng)可能是n個(gè)值中的某一個(gè)§3整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用3、解決n個(gè)變量中選取k個(gè)變量的問(wèn)題（例4、例6）n個(gè)取1個(gè)：n個(gè)取k個(gè)：n個(gè)至少取k個(gè)：n個(gè)至多取k個(gè)：§3整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用4、解決變量離散值的問(wèn)題（例8）§3整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用5、解決部分約束的問(wèn)題m個(gè)約束只有k個(gè)起作用m個(gè)約束條件：設(shè)：假定第i個(gè)約束條件不起作用假定第i個(gè)約束條件起作用則：§3整數(shù)規(guī)劃的應(yīng)用六、0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用6、解決邏輯關(guān)系約束的問(wèn)題若f(x)<0成立，則g(x)≤0必須成立；若f(x)<0不成立，則g(x)無(wú)限制。引入一個(gè)0-1變量y來(lái)解決這一邏輯關(guān)系：f(x)≥-M(1-y)g(x)≤My§3整數(shù)規(guī)劃的應(yīng)用七、關(guān)于靈敏度分析的討論在整數(shù)規(guī)劃中，某個(gè)參數(shù)很小的變化可能會(huì)使最優(yōu)值產(chǎn)生相對(duì)較大的變化。max50x1+80x2+100x3+150x4約束條件：31x1+50x2+70x3+90x4≤120xi為0-1變量i=1,2,3,4最優(yōu)解：x1=0,x2=1,x3=1,x4=0,最優(yōu)值z(mì)=180.當(dāng)預(yù)算資金由120萬(wàn)元變?yōu)?21萬(wàn)元時(shí)，最優(yōu)解？最優(yōu)解：x1=1,x2=0,x3=0,x4=1,最優(yōu)值z(mì)=200.§3整數(shù)規(guī)劃的應(yīng)用七、關(guān)于靈敏度分析的討論解決整數(shù)規(guī)劃問(wèn)題的靈敏度分析，通常需要高速計(jì)算機(jī)的幫助。通常建議在實(shí)施最優(yōu)解前對(duì)參數(shù)稍加修改，多解幾次。整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的分枝定界法本章內(nèi)容410-1規(guī)劃的解法523§4整數(shù)規(guī)劃的分枝定界法分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法。多數(shù)求解整數(shù)規(guī)劃的商用軟件基于分枝定界法。

§4整數(shù)規(guī)劃的分枝定界法分枝定界法計(jì)算過(guò)程：整數(shù)規(guī)劃整數(shù)規(guī)劃上、下界線性規(guī)劃整數(shù)規(guī)劃最優(yōu)解是否解為整數(shù)，且上界=下界線性規(guī)劃分枝可行解有整數(shù)規(guī)劃無(wú)可行解無(wú)剪枝比較§4整數(shù)規(guī)劃的分枝定界法例9.用分枝定界法求解整數(shù)規(guī)劃 max2x1+3x2 s.t.195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1,x2≥0且x1,x2為整數(shù)

§4整數(shù)規(guī)劃的分枝定界法求解過(guò)程與結(jié)果線性規(guī)劃1Z1=14.66X1=2.44X2=3.26z=13,z=14.58線性規(guī)劃2Z2=13.90X1=2X2=3.30線性規(guī)劃3Z3=14.58X1=3X2=2.86z=13,z=14.66z=14,z=14線性規(guī)劃4Z4=14.00X1=4X2=2線性規(guī)劃5無(wú)可行解x1≥3x1≤2x2≤2x2≥3選擇目標(biāo)函數(shù)較優(yōu)者 解：（1）先求出以下線性規(guī)劃的解。 max2x1+3x2 s.t.195x1+273x2≤1365 4x1+40x2≤140 x1≤4x1,x2≥0 得z1=14.66，x1=2.44，x2=3.26確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*初始上界和下界。分析后，知道上界為14.66，由觀察法得下界為13（當(dāng)x1=2,x2=3時(shí)）。將線性規(guī)劃1分解為兩支： 線性規(guī)劃2：max2x1+3x2 s.t.195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≤2 x1,x2≥0解得z2=13.90,x1=2,x2=3.30

線性規(guī)劃3：max2x1+3x2 s.t.195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≥3 x1，x2≥0解得z3=14.58,x1=3,x2=2.86線性規(guī)劃4：max2x1+3x2s.t.195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1≥3 x2≤2 x1,x2≥0 解得z4=14,x1=4,x2=2

線性規(guī)劃5：max2x1+3x2s.t.195x1+273x2≤1365 4x1+40x2≤140x1≤4 x1≥3 x2≥3 x1,x2≥0 線性規(guī)劃5無(wú)可行解。整數(shù)規(guī)劃最優(yōu)解§4整數(shù)規(guī)劃的分枝定界法性質(zhì)2：當(dāng)整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界z等于其下界z時(shí)，該整數(shù)規(guī)劃的最優(yōu)解已經(jīng)被求出。整數(shù)規(guī)劃的最優(yōu)解即為其目標(biāo)函數(shù)值取此下界的對(duì)應(yīng)線性規(guī)劃的整數(shù)可行解。整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的分枝定界法本章內(nèi)容510-1規(guī)劃的解法234§50-1規(guī)劃的解法

求解0-1規(guī)劃問(wèn)題的方法：2.隱枚舉法檢查全部變量組合的一部分，求得問(wèn)題的最優(yōu)解。1.窮舉法檢查每個(gè)變量取值為0或1的所有組合，找出滿足全部約束條件的所有組合，并比較目標(biāo)函數(shù)的值，求得最優(yōu)解。分支定界法也是一種隱枚舉法。§50-1規(guī)劃的解法

例10.有以下0-1規(guī)劃maxz=4x1+x2+5x3約束條件：2x1+3x2-x3≤3（1）x1+3x2+2x3≥2（2）x1+2x2≤2（3）3x1+2x2+x3≥2（4）xi=1或0,i=1,2,3.§50-1規(guī)劃的解法

解：可行解：X1=(0,1,1)，z1=6.增加約束條件：4x1+x2+5x3≥6（0）(過(guò)濾條件)§50-1規(guī)劃的解法maxz=4x1+x2+5x3約束條件：4x1+x2+5x3≥6（0）按照（0）-（4)順序?qū)s束條件進(jìn)行排列2x1+3x2-x3≤3（1）x1+3x2+2x3≥2（2）x1+2x2≤2（3）3x1+2x2+x3≥2（4）xi=1或0,i=1,2,3.可行解：X1=(0,1,1)，z1=6.增加約束條件：4x1+x2+5x3≥6（0）(過(guò)濾條件)§50-1規(guī)劃的解法

解：應(yīng)用窮舉法，將解依次帶入約束條件，求出目標(biāo)函數(shù)值并檢驗(yàn)是否符合過(guò)濾條件。