第五章整數(shù)規(guī)劃第1頁，共60頁，2023年，2月20日，星期三2023/5/42

在很多場合，我們建立最優(yōu)化模型時(shí)，實(shí)際問題要求決策變量只能取整數(shù)值而非連續(xù)取值。此時(shí)，這類最優(yōu)化模型就稱為整數(shù)規(guī)劃（離散最優(yōu)化）模型。

整數(shù)規(guī)劃的求解往往比線性規(guī)劃求解困難得多，而且，一般來說不能簡單地將相應(yīng)的線性規(guī)劃的解取整來獲得。第2頁，共60頁，2023年，2月20日，星期三2023/5/43整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式整數(shù)規(guī)劃（IP）松弛問題整數(shù)線性規(guī)劃（ILP）的數(shù)學(xué)模型：一、整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)5.1c5.1d5.1a5.1b第3頁，共60頁，2023年，2月20日，星期三2023/5/44——決策變量只能取值0或1。整數(shù)規(guī)劃問題的類型純整數(shù)線性規(guī)劃(pureintegerlinearprogramming)——全部決策變量都必須取整數(shù)值?；旌险麛?shù)線性規(guī)劃(mixedintegerlinearprogramming)——決策變量中一部分必須取整數(shù)值，

另一部分可以不取整數(shù)值。0-1型整數(shù)線性規(guī)劃(zero-oneintegerlinearprogramming)第4頁，共60頁，2023年，2月20日，星期三2023/5/45例1、某公司準(zhǔn)備投資50萬元為其產(chǎn)品做廣告，廣告代理商給公司的有關(guān)廣告方式的費(fèi)用和其效果情況如下表，公司面臨的管理決策問題是廣告總費(fèi)用不超過50萬元的基礎(chǔ)上選擇哪些廣告方式，使得潛在顧客數(shù)盡可能地多。廣告方式電視臺報(bào)紙雜志電臺廣告費(fèi)（萬元）40152010潛在顧客數(shù)（萬人）40202510整數(shù)規(guī)劃問題實(shí)例第5頁，共60頁，2023年，2月20日，星期三2023/5/46

xi=

1選擇第i種廣告方式0不選擇第i種廣告方式MaxZ=40x1+20x2+25x3+10x440x1+15x2+20x3+10x4≤50x1

，x2

，x3

，x4=0或1例1、模型設(shè)：xi（i=1,2,3,4）——

表示4種廣告方式。第6頁，共60頁，2023年，2月20日，星期三2023/5/47

例2、某公司在城市的東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（地點(diǎn)）Ai（i=1，2，…，7）可供選擇。公司規(guī)定：在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在南區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在西區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。如果選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。問公司選擇哪幾個(gè)點(diǎn)可使年總利潤最大？第7頁，共60頁，2023年，2月20日，星期三2023/5/48

例2、模型設(shè)：Ai=

1

選擇Ai

建立門市0不選擇Ai

建立門市

MaxZ=∑ciAi

∑bi

Ai

≤BA1+A2+A3

≤2A4+A5

≥1A6+A7

≥1Ai=0或1，（i=1，2，3，4，5，6，7）第8頁，共60頁，2023年，2月20日，星期三2023/5/49例某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油，使總的鉆探費(fèi)用為最小。若10個(gè)井位的代號為S1…S10，相應(yīng)的鉆探費(fèi)用為c1…c10，并且井位選擇上要滿足下列限制條件：①或選擇S1和S7，或選擇S8；②選擇了S3或S4就不能選S5，反之，選了S5，則不能選S3或S4；③在S5~S8中最多選兩個(gè)。建立這個(gè)問題的0-1型整數(shù)規(guī)劃模型第9頁，共60頁，2023年，2月20日，星期三2023/5/410解：令（i＝1，…，10）第10頁，共60頁，2023年，2月20日，星期三2023/5/411

設(shè)：工序B有兩種方式完成方式（1）的工時(shí)約束:0.3X1+0.5X2≤150方式（2）的工時(shí)約束:0.2X1+0.4X2≤120

問題是完成工序B只能從兩種方式中任選一種，如何將這兩個(gè)互斥的約束條件統(tǒng)一在一個(gè)線性規(guī)劃模型中呢？例3、應(yīng)用0-1變量解決含互斥約束條件問題第11頁，共60頁，2023年，2月20日，星期三2023/5/412

例3、模型引入0-1變量y1=0若工序B采用方式（1）完成1若工序B不采用方式（1）完成y2=0若工序B采用方式（2）完成1若工序B不采用方式（2）完成于是前面兩個(gè)互斥的約束條件可以統(tǒng)一為如下三個(gè)約束條件：

0.3X1+0.5X2≤150+M1y1

0.2X1+0.4X2≤120+M2y2

y1+y2=1其中M1

，M2

都是足夠大的正數(shù)。第12頁，共60頁，2023年，2月20日，星期三2023/5/413

有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見下表。要求制定一個(gè)生產(chǎn)計(jì)劃，使總收益最大。

ⅠⅡⅢ資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)81012

例4．固定費(fèi)用問題第13頁，共60頁，2023年，2月20日，星期三2023/5/414

解：設(shè)xj為第j種產(chǎn)品的生產(chǎn)數(shù)量，j=1,2,3；yj=1當(dāng)生產(chǎn)第j種產(chǎn)品,即

xj＞0時(shí)0

當(dāng)不生產(chǎn)第j種產(chǎn)品即

xj=0時(shí)

引入約束

xi≤Myi，i=1，2，3，M充分大，以保證當(dāng)

yi=0

時(shí)，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≥0yj

為0--1變量，i=1,2,3第14頁，共60頁，2023年，2月20日，星期三2023/5/415例5、人員時(shí)間安排

某航空公司希望更有效地安排售票員的工作時(shí)間，以減少工資支出。每個(gè)售票員上班后將連續(xù)工作8個(gè)小時(shí)，但并非每時(shí)每刻都有一樣多的顧客，因此，適當(dāng)?shù)貙⒁惶旆殖?個(gè)時(shí)段，每個(gè)時(shí)段2小時(shí)（假定每天的8：00至24：00為售票工作時(shí)間）。應(yīng)該如何計(jì)劃每個(gè)時(shí)段初的上班售票員人數(shù)，才能使一天雇傭的售票員總?cè)藬?shù)最少？（數(shù)據(jù)資料見下表）第15頁，共60頁，2023年，2月20日，星期三2023/5/416

例5、人員時(shí)間安排時(shí)段起始時(shí)間結(jié)束時(shí)間需售票員人數(shù)18：0010：0010210：0012：008312：0014：009414：0016：0011516：0018：0013618：0020：008720：0022：005822：000：003第16頁，共60頁，2023年，2月20日，星期三2023/5/417

例5、模型MinZ=x1+x2+x3+x4+x5

x1≥10x1+x2≥8x1+x2+x3≥9x1+x2+x3+x4≥11x2+x3+x4+x5≥13x3+x4+x5≥8x4+x5≥5x5≥3xi≥0，且為整數(shù)

設(shè)：決策變量xi為第i時(shí)間段初上班的售票員人數(shù)第17頁，共60頁，2023年，2月20日，星期三2023/5/418

例6、合理下料造某種機(jī)床，需要A，B，C三種軸件，其規(guī)格與數(shù)量如下表，各類軸件都用5.5米長的同一種圓鋼下料。若計(jì)劃生產(chǎn)100臺機(jī)床，最少要用多少根圓鋼？軸類規(guī)格：長度（米）每臺機(jī)床所需軸件數(shù)A3.11B2.12C1.24第18頁，共60頁，2023年，2月20日，星期三2023/5/419

例6、模型分析該問題后，發(fā)現(xiàn)較合理的下料方案有：軸類方案1方案2方案3方案4方案5A（3.1）11000B（2.1）10012C（1.2）02421用料長5.25.54.84.55.4余料0.300.710.1第19頁，共60頁，2023年，2月20日，星期三2023/5/420

例6、模型設(shè)：xi

——

采用方案i下料所用的原料根數(shù)。MinZ=x1+x2+x3+x4+x5

x1+x2=100x1+x4+2x5=2002x2+4x3+2x4+x5=400x1

，x2

，x3

，x4

，x5≥0，且為整數(shù)第20頁，共60頁，2023年，2月20日，星期三2023/5/421

例7、指派問題某企業(yè)正在考慮4名人員——4項(xiàng)工作的分派問題，由于每項(xiàng)工作只需要一個(gè)人去完成，而每名人員也只能去完成某一項(xiàng)工作，各人員完成各工作的成本如下表，管理人員應(yīng)該如何分派工作才能使總成本最??？工作人員ABCD甲乙丙丁2109715414813141611415139第21頁，共60頁，2023年，2月20日，星期三2023/5/422例7、模型設(shè)：Xij=0不指派第i人完成第j項(xiàng)工作1指派第i人完成第j項(xiàng)工作其中Cij

為第i人完成第j項(xiàng)工作的費(fèi)用第22頁，共60頁，2023年，2月20日，星期三2023/5/423例、某公司計(jì)劃在m個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)有A1,A2…Am

，他們的生產(chǎn)能力分別是a1,a2,…am（假設(shè)生產(chǎn)同一產(chǎn)品）。第i個(gè)工廠的建設(shè)費(fèi)用為fi

(i=1.2…m),又有n個(gè)地點(diǎn)B1,B2,…Bn

需要銷售這種產(chǎn)品，其銷量分別為b1.b2…bn

。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)為Cij。試決定應(yīng)在哪些地方建廠，既滿足各地需要，又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最省？第23頁，共60頁，2023年，2月20日，星期三2023/5/424單銷地廠址價(jià)生產(chǎn)能力建設(shè)費(fèi)用銷量第24頁，共60頁，2023年，2月20日，星期三2023/5/425

設(shè)：

xij

表示從工廠運(yùn)往銷地的運(yùn)量(i=1.2…m、j=1.2…n),1在Ai建廠又設(shè)Yi＝（i=1.2…m）

0不在Ai建廠模型：第25頁，共60頁，2023年，2月20日，星期三2023/5/426（三）整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得倒的解是整數(shù)可行解。舉例說明。第26頁，共60頁，2023年，2月20日，星期三2023/5/427例：設(shè)整數(shù)規(guī)劃問題如下

首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。第27頁，共60頁，2023年，2月20日，星期三2023/5/428用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)

現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。

第28頁，共60頁，2023年，2月20日，星期三2023/5/429

因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點(diǎn)為最大值，Z=4。

目前，常用的求解整數(shù)規(guī)劃的方法有：

分支定界法和割平面法；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。第29頁，共60頁，2023年，2月20日，星期三2023/5/430（一）基本思路

考慮純整數(shù)問題：整數(shù)問題的松弛問題：二、分枝定界法第30頁，共60頁，2023年，2月20日，星期三2023/5/431

maxZ=CXAX=bX0(A)IPmaxZ=CXAX=bX0X為整數(shù)

(B)LP(B)為(A)的松弛問題。第31頁，共60頁，2023年，2月20日，星期三2023/5/432

分枝定界法一般步驟：(1)先解(A)的松弛問題(B)(2)①(B)無可行解→(A)無可行解。②(B)最優(yōu)解符合(A)要求，停。③(B)最優(yōu)解不符合(A)要求，轉(zhuǎn)(3)。(3)估整數(shù)解S0

，定界（上界、下界）(4)選(B)解中不符合整數(shù)條件的分量Xj

(Xj=bj)分枝，作(B)的后續(xù)問題(C)、(D)。(C)：(B)加約束Xj

[bj]+1(D)：(B)加約束Xj[bj]第32頁，共60頁，2023年，2月20日，星期三2023/5/433

剪枝條件:①(C)，[(D)]無可行解

②(C)（(D)）對應(yīng)的目標(biāo)值Sc

(Sd)

S0（極大化）③(C)（(D)）對應(yīng)的目標(biāo)值Sc(Sd)

>S0

（極小化）

且解為整數(shù)解，令Sc(Sd)

S0

且解為非整數(shù)解，令(C)，[(D)]取代(B)返回(4)(6)全部枝剪完，停(5)解(C)、(D)第33頁，共60頁，2023年，2月20日，星期三2023/5/434例1：用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計(jì)算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（LP）例題

第34頁，共60頁，2023年，2月20日，星期三2023/5/435用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2

≤3，x2

≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。第35頁，共60頁，2023年，2月20日，星期三2023/5/436有下式：

現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。第36頁，共60頁，2023年，2月20日，星期三2023/5/437x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如圖所示。此時(shí)在B

點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計(jì)算。11同理求（LP2）

,如圖所示。在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原問題有比（－16）更小的最優(yōu)解，但x2不是整數(shù)，故利用

3≥10/3≥4

加入條件。BAC第37頁，共60頁，2023年，2月20日，星期三2023/5/438加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。第38頁，共60頁，2023年，2月20日，星期三2023/5/439x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。D求（LP4），如圖所示。無可行解，不再分枝。第39頁，共60頁，2023年，2月20日，星期三2023/5/440

在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。第40頁，共60頁，2023年，2月20日，星期三2023/5/441x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時(shí)E

在點(diǎn)取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問題已探明，此枝停止計(jì)算。E求（LP6），如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F

如對Z(6)

繼續(xù)分解，其最小值也不會(huì)低于－15.5

，問題探明,剪枝。第41頁，共60頁，2023年，2月20日，星期三2023/5/442

至此，原問題（IP）的最優(yōu)解為：

x1=2，

x2=3,

Z*=Z(5)

＝－17以上的求解過程可以用一個(gè)樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4無可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃第42頁，共60頁，2023年，2月20日，星期三2023/5/443練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題

（圖解法）

第43頁，共60頁，2023年，2月20日，星期三2023/5/444LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)

＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃第44頁，共60頁，2023年，2月20日，星期三2023/5/445LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=2/3,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃第45頁，共60頁，2023年，2月20日，星期三2023/5/4463200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對應(yīng)的(LP)問題,如表所示,獲得最優(yōu)解。初始表最終表例2、用分枝定界法求解整數(shù)規(guī)劃問題（單純形法）

第46頁，共60頁，2023年，2月20日，星期三2023/5/447x1=13/4

x2=5/2Z(0)=59/4≈14.75

選x2進(jìn)行分枝，即增加兩個(gè)約束，2≥x2≥3有下式：

分別在(LP1)和(LP2)中引入松弛變量x5和x6

，將新加約束條件加入上表計(jì)算。即x2+x5=2,－x2+x6=－3

得下表:第47頁，共60頁，2023年，2月20日，星期三2023/5/44832000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2

Z(1)=29/2=14.5繼續(xù)分枝，加入約束

3≥x1≥4LP1第48頁，共60頁，2023年，2月20日，星期三2023/5/44932000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考慮分枝第49頁，共60頁，2023年，2月20日，星期三2023/5/450接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。第50頁，共60頁，2023年，2月20日，星期三2023/5/451CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3x1=3,x2=2

Z(3)=13找到整數(shù)解，問題已探明，停止計(jì)算。LP3第51頁，共60頁，2023年，2月20日，星期三2023/5/452CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1x1=4,x2=1

Z(4)=14找到整數(shù)解，問題已探明，停止計(jì)算。LP4第52頁，共60頁，2023年，2月20日，星期三2023/5/453樹形圖如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)

＝13LP4x1=4,x2=1Z(4)

＝14x2≤2x2≥3x1≤3x1≥4＃＃＃第53頁，共60頁，2023年，2月20日，星期三2023/5/454練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題

（單純形法）第54頁，共60頁，2023年，2月20日，星期三2023/5/455cj-1-5000cBxBbx1x2x3x4x50x32-111000x4

30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1

18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/110第55頁，共60頁，2023年，2月20日，星期三2023/5/456LP