第八章 整數(shù)規(guī)劃

第八章

整數(shù)規(guī)劃1整數(shù)規(guī)劃問題線性規(guī)劃的決策變量取值可以是任意非負(fù)實數(shù)，但許多實際問題中，只有當(dāng)決策變量的取值為整數(shù)時才有意義。例如，產(chǎn)品的件數(shù)、機(jī)器的臺數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃問題，稱為整數(shù)線性規(guī)劃，簡稱整數(shù)規(guī)劃(IntegerProgramming)。全部決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃(AllIP)；僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(MixedIP)；要求決策變量只能取0或1值，則稱為0-1規(guī)劃(0-1rogramming)。

2整數(shù)規(guī)劃問題為了滿足整數(shù)要求，似乎可以把線性規(guī)劃的小數(shù)最優(yōu)解進(jìn)行“舍入化整”以得到與最優(yōu)解相近的整數(shù)解。“舍入化整”一般是不可行的：化整后的解有可能成為非可行解；雖是可行解，卻不是最優(yōu)解。例如一、問題的提出

產(chǎn)品資源甲乙現(xiàn)有量A219B5735單臺利潤63

問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。3整數(shù)規(guī)劃問題解：設(shè)x1為甲產(chǎn)品的臺數(shù)，x2為乙產(chǎn)品的臺數(shù)。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)不考慮整數(shù)約束則是一個LP問題,稱為原整數(shù)規(guī)劃的松弛問題。不考慮整數(shù)約束的最優(yōu)解：x1

*=28/9=3.111，x2

*=25/9=2.778，Z

*=293/9=32.556舍入化整x1=3，x2=3，Z=33，不滿足約束條件5x1+7x2≤35，非可行解；x1=3，x2=2，Z=28，滿足約束條件，是可行解，但不是最優(yōu)解；x1=4，x2=1，Z=29，滿足約束條件，才是最優(yōu)解。45x1+7x2=352x1+x2=9?(3,3)??????????第一節(jié)、整數(shù)規(guī)劃的圖解法

x1x21231253445步驟：在線性規(guī)劃的可行域內(nèi)列出所有決策變量可能取的整數(shù)值，求出這些變量所有可行的整數(shù)解，比較它們相應(yīng)的目標(biāo)函數(shù)值，最優(yōu)的目標(biāo)函數(shù)值所對應(yīng)的解就是整數(shù)規(guī)劃的最優(yōu)解。實用性：只有兩個決策變量，可行的整數(shù)解較少。

第一節(jié)、整數(shù)規(guī)劃的圖解法

二、整數(shù)規(guī)劃的圖解法

6例1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運(yùn)所受限制如表所示。貨物每件體積（立方英尺）每件重量（百千克）每件利潤（百元）甲乙19527344023托運(yùn)限制1365140

第一節(jié)、整數(shù)規(guī)劃的圖解法甲種貨物至多托運(yùn)4件，問兩種貨物各托運(yùn)多少件，可使獲得利潤最大。解：設(shè)x1、

x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：Maxz=2x1+3x2約束條件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0為整數(shù)。如果去掉最后一個約束，就是一個線性規(guī)劃問題。利用圖解法，7得到線性規(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。性質(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ù)值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=6第一節(jié)、整數(shù)規(guī)劃的圖解法??????????8例2：Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0為整數(shù)例3：Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3為整數(shù)x3為0-1變量用《管理運(yùn)籌學(xué)》軟件求解得：

x1=5x2=2x3=2用《管理運(yùn)籌學(xué)》軟件求解得：

x1=4x2=1.25x3=1z=16.25第二節(jié)、整數(shù)規(guī)劃的計算機(jī)求解9第三節(jié)、整數(shù)規(guī)劃的應(yīng)用

例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：

在東區(qū)由A1，A2，A3三個點至多選擇兩個；在西區(qū)由A4，A5兩個點中至少選一個；在南區(qū)由A6，A7兩個點中至少選一個；在北區(qū)由A8，A9，A10三個點中至少選兩個。一、投資場所的選擇Aj各點的設(shè)備投資及每年可獲利潤由于地點不同都是不一樣的，預(yù)測情況見下表所示(單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點，可使年利潤為最大?10解：設(shè)：0--1變量xi=1(Ai點被選用）或0(Ai點沒被選用）。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.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≥2xj≥0xj為0--1變量，i=1,2,3,……,10第三節(jié)、整數(shù)規(guī)劃的應(yīng)用11Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.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≥2xj≥0xj為0--1變量，i=1,2,3,……,10最優(yōu)解：x1=1,x2=1,x3=0,

x4=0,x5=1,

x6=1,

x7=0,x8=0,x9=1,

x10=1最大利潤245萬元。即在A1,A2,A5,A6,A9,A10等6個地點建立銷售門市部。實際投資額為100+120+70+90+160+180=720第三節(jié)、整數(shù)規(guī)劃的應(yīng)用12例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人月，機(jī)器有100臺月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號是l00萬元，中號為150萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。二、固定成本問題第三節(jié)、整數(shù)規(guī)劃的應(yīng)用13解：這是一個整數(shù)規(guī)劃的問題。設(shè)x1，x2，x3分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時才投入，為了說明固定費(fèi)用的這種性質(zhì)，設(shè)yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時)或0（當(dāng)不生產(chǎn)第i種容器即xi=0時）引入約束xi≤Myi，i=1，2，3，M充分大，以保證當(dāng)yi=0時，xi=0。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0xj∈Nyj為0--1變量，i=1,2,3第三節(jié)、整數(shù)規(guī)劃的應(yīng)用14例6．有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最少。三、指派問題:有n項不同的任務(wù)，恰好n個人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各項任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個人去完成一項任務(wù)，怎樣把n項任務(wù)指派給n個人，使得完成n項任務(wù)的總的效率最高，這就是指派問題。第三節(jié)、整數(shù)規(guī)劃的應(yīng)用15解：引入0—1變量xij，并令xij=1(當(dāng)指派第i人去完成第j項工作時)或0（當(dāng)不指派第i人去完成第j項工作時)．這可以表示為一個0--1整數(shù)規(guī)劃問題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一項工作)

x21+x22+x23+x24=1(乙只能干一項工作)x31+x32+x33+x34=1(丙只能干一項工作)x41+x42+x43+x44=1(丁只能干一項工作)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∈N為0--1變量，i,j=1,2,3,4

***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用16

對于有m

個人，n項任務(wù)的一般指派問題，設(shè)：第三節(jié)、整數(shù)規(guī)劃的應(yīng)用并設(shè)：cij

為第i人去完成第n項任務(wù)的成本（如時間、費(fèi)用等）則一般指派問題的模型可以寫為：約束條件：xij為0-1變量，對所有的i和j.17因為m不一定等于n，當(dāng)m>n，即人數(shù)多于任務(wù)數(shù)時，就有人沒有任務(wù)，所以前面?zhèn)€約束條件都是“小于等于1”，這是說每個人至多承擔(dān)一項任務(wù)，而后面n個約束條件說明每項工作正好有一人承擔(dān)，所以都是“等于1”.當(dāng)n>m時，需要設(shè)假想的n-m個人便獲得可行解.第三節(jié)、整數(shù)規(guī)劃的應(yīng)用18第三節(jié)、整數(shù)規(guī)劃的應(yīng)用還有一種指派問題叫做多重指派問題，它于一般的指派問題的區(qū)別在于：一般的指派問題中每個人至多承擔(dān)一項任務(wù)，而多重指派問題中一個人可以根據(jù)自己能力的大小承擔(dān)一項、兩項或更多項的任務(wù).這時約束條件中的前個條件不是而是改為其中ai是第i個人至多承擔(dān)的任務(wù)的數(shù)，對于不同的i

，ai可以是不一樣的.19四、分布系統(tǒng)設(shè)計

例7．某企業(yè)在A1地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(每千箱運(yùn)費(fèi))如下表所示。（1）

問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小?

（2）

如果由于政策要求必須在A2，A3地建一個廠，應(yīng)在哪幾個地方建廠?第三節(jié)、整數(shù)規(guī)劃的應(yīng)用20解：

a)設(shè)xij為從Ai運(yùn)往Bj的運(yùn)輸量(單位千箱)，yi=1(當(dāng)Ai被選中時)或0（當(dāng)Ai沒被選中時)．這可以表示為一個整數(shù)規(guī)劃問題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項為固定投資額，后面的項為運(yùn)輸費(fèi)用。s.t.x11+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≥0xj∈N，yi為0--1變量，i=1,2,3,4,5；j=1,2,3

***求解可用《管理運(yùn)籌學(xué)》軟件中整數(shù)規(guī)劃方法。

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用21b)如果由于政策要求必須在A2，A3地建一個廠，應(yīng)在哪幾個地方建廠?

解：設(shè)xij為從Ai運(yùn)往Bj的運(yùn)輸量(單位千箱)，yi=1(當(dāng)Ai被選中時)或0（當(dāng)Ai沒被選中時)．這可以表示為一個整數(shù)規(guī)劃問題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項為固定投資額，后面的項為運(yùn)輸費(fèi)用。s.t.x11+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(必須在A2，A3地建一個廠)xij≥0yi為0--1變量，i=1,2,3,4,5；j=1,2,322五、投資問題例8．某公司在今后五年內(nèi)考慮給以下的項目投資。已知：

項目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬元，第二、三、四年不限；

項目B：第三年初需要投資，到第五年未能回收本利128％，但規(guī)定最低投資金額為3萬元，最高金額為5萬元；

項目C：第二年初需要投資，到第五年未能回收本利140%，但規(guī)定其投資額或為2萬元或為4萬元或為6萬元或為8萬元。

項目D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項投資金額不限。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大?第三節(jié)、整數(shù)規(guī)劃的應(yīng)用23解：1)設(shè)xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分別表示第i年年初給項目A，B，C，D的投資額；設(shè)y1A，y3B，是0—1變量，并規(guī)定:

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用設(shè)y2C是非負(fù)整數(shù)變量，并規(guī)定：第2年投資C項目8萬元時，取值為4；第2年投資C項目6萬元時，取值為3；第2年投資C項目4萬元時，取值為2；第2年投資C項目2萬元時，取值為1；第2年不投資C項目時，取值為0；

24這樣我們建立如下的決策變量：

第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C(=20000y2C)

D

x1D

x2D

x3D

x4D

x5D

第三節(jié)、整數(shù)規(guī)劃的應(yīng)用252）約束條件：第一年：年初有100000元，D項目在年末可收回投資，故第一年年初應(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；第三節(jié)、整數(shù)規(guī)劃的應(yīng)用26關(guān)于項目A的投資額規(guī)定:x1A≥40000y1A，x1A≤200000y1A，200000是足夠大的數(shù)；保證當(dāng)

y1A=0時，x1A=0；當(dāng)y1A=1時，x1A≥40000。關(guān)于項目B的投資額規(guī)定:x3B≥30000y3B，x3B≤50000y3B；保證當(dāng)

y3B=0時，x3B=0；當(dāng)y3B=1時，50000≥x3B≥30000。關(guān)于項目C的投資額規(guī)定:x2C=20000y2C，y2C=0，1，2，3，4。第三節(jié)、整數(shù)規(guī)劃的應(yīng)用273）目標(biāo)函數(shù)及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=100000；x2A+x2C+x2D=1.06x1D；

x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A≥40000y1A，

x1A≤200000y1A，x3B≥30000y3B，

x3B≤50000y3B；x2C=20000y2C，y1A，y3B=0或1，y2C=0，1，2，3，4xiA，xiB，xiC，xiD≥0(i=1、2、3、4、5）第三節(jié)、整數(shù)規(guī)劃的應(yīng)用28第四節(jié)分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整數(shù)規(guī)劃相應(yīng)的LP(即不考慮整數(shù)限制)的最優(yōu)解，若求得的最優(yōu)解符合整數(shù)要求，則是原IP的最優(yōu)解；若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)規(guī)劃的最優(yōu)解。

29第四節(jié)分枝定界法定界的含義：整數(shù)規(guī)劃是在相應(yīng)的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的約束條件，整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于相應(yīng)線性規(guī)劃的最優(yōu)解。對極大化問題來說，相應(yīng)線性規(guī)劃的目標(biāo)函數(shù)最優(yōu)值是原整數(shù)規(guī)劃函數(shù)值的上界；對極小化問題來說，相應(yīng)線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值是原整數(shù)規(guī)劃目標(biāo)函數(shù)值的下界。30第四節(jié)分枝定界法例maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)第一步,不考慮變量的整數(shù)約束,求相應(yīng)LP(問題1)的最優(yōu)解：x1=28/9，x2=25/9，Z1=293/9第二步,定界過程這個解不滿足整數(shù)約束，這時目標(biāo)函值Z1是整數(shù)規(guī)劃的目標(biāo)上界；因為x1=x2=0是整數(shù)規(guī)劃問題的可行解，所以下界為0。第三步,分枝過程將不滿足整數(shù)約束的變量x1進(jìn)行分枝，x1稱為分枝變量，構(gòu)造兩個新的約束條件：

x1≤[28/9]=3，x1≥[28/9]+1=4

31第四節(jié)分枝定界法這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個部分，如圖所示。??????????5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4問題2：maxZ=

6x1+5x2問題3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)32第四節(jié)分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題2相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2=20/7，Z2=226/7問題3相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=4，x2=1，Z3=29第四步，定界過程LP3的解滿足整數(shù)約束，不必再分枝，它的目標(biāo)函數(shù)值是29，大于原有下界0，則新的下界為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為226/7。LP2的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值226/7大于現(xiàn)有下界，則應(yīng)繼續(xù)分枝。第五步，分枝過程將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個新的約束條件：

x2≤[20/7]=2，x2≥[20/7]+1=3

33??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3第四節(jié)分枝定界法問題4：maxZ=

6x1+5x2問題5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0