整数规划

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费

用为最小。若10个井位的代号为S

1

,S

2

．…，S

10

相应的钻探费用为C

1

,C

2

,…

C

10

，并且井位选择要满足下列限制条件：

(1)在s

1

，s

2

，S

4

中至多只能选择两个；

（2）在S

5

，s

6

中至少选择一个；（3）在s

3

，s

6

，S

7

，S

8

中至少选择两个。

试建立这个问题的整数规划模型

解：设x

j

（j=1,…,10）为钻井队在第i个井位探油

minZ=

j

j

j

xc





10

1

背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐

篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队

员可携带的最大重量为25kg,试选择该队员所应携带的物品。

序号1234567

物品食品氧气冰镐绳索帐篷照相器材通信设备

重量/Kg55261224

重要性系数2

解：引入0—1变量x

i

,x

i

=1表示应携带物品i，,x

i

=0表示不应携带物品I













7,...,2,1,10

2542126255

1

7654321

7654321

ix

xxxxxxx

xxxxxxxnaxz

i

或

集合覆盖和布点问题

某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设

置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内

赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少

的计划。

地区1地区2地区3地区4地区5地区6

地区1

地区2

地区3

地区4

地区5

地区6

0

10

16

28

27

20

10

0

24

32

17

10

16

24

0

12

27

21

28

32

12

0

15

25

27

17

27

15

0

14

20

10

21

25

14

0

解：引入0—1变量x

i

,x

i

=1表示在该区设消防站，,x

i

=0表示不设







































01

1

1

1

1

1

1

min

652

654

543

43

621

21

654321

或

i

x

xxx

xxx

xxx

xx

xxx

xx

xxxxxxz

解得：X*=(0,1,0,1,0,0)’Z*=2

某公司现有5个项目被列入投资计划，各项目的投资额和期望的投资收益如

下表所示：

项目编号投资额（万元）投资收益（万元）

1

2

3

4

5

210

300

100

130

260

150

210

60

80

180

该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下条件的

约束：（1）在项目1、2和3中必须有一项被选中，（2）项目3和项目4只能选

中一项，（3）项目5被选中的前提是项目1必须被选中。试就这一问题建立运筹

学研究模型。

某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址

代号及其能覆盖的居民小区编号如表5–2所示，问为覆盖所有小区至少应建多

少所小学，要求建模并求解。

表5–12

备选校址代号覆盖的居民小区编号

A1，5，7

B1，2，5

C1，3，5

D2，4，5

E3，6，

F4，6，

一货船，有效载重量为24吨，可运输货物重量及运费收入如表5-13所示，

现货物2、4中优先运2，货物1、5不能混装，试建立运费收入最多的运输方案。

表5-13

货物123456

重量（吨）59871023

收入（万

元）

144357

运筹学中著名的旅行商贩（货朗担）问题可以叙述如下：某旅行商贩从某一城市出发，到

其他几个城市推销商品，规定每个城市均需到达且只到达一次，然后回到原出发城市。已知

城市i和城市j之间的距离为dij问商贩应选择一条什么样的路线顺序旅行，使总的旅程最

短。试对此问题建立整数规划模型。

有一组物品S，共有9件，其中第i件重i

w

，价值i

v

，从S中取出一些物品

出来装背包，使总价值最大，而不超过总重量的给定上限30kg。

i123456789

i

w

(kg)

211106543

i

v

(元)

1

工程上马的决策问题

某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千

元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪

些工程，方能使该部门可能的期望收益最大。

工程

费用

期望收益

第1年第2年第3年

1518

4710

392

8610

20

40

20

30

2

3

4

可用资金182224

为解决污水对河流的污染问题，某城市拟建污水处理站，备选的站址有A、B、C

三个，其投资等技术经济参数如下表：

投资（万元）处理能力

（万吨∕

年）

水处理成本

（元∕万

吨）

水处理指标（吨∕万吨）

污染物1污染物2

A5

B4

C30

按环保部门的要求，每年至少要从污水中清除8万吨的污染物1和6万吨的污染

物2，构建一个整数规划模型，在满足环保要求的前提下使投资和运行费用最少。

123123

123

123

11

22

33

123123

min5001000

8

6

800

500

400

,,0;,,0,1

zyyyxxx

xxx

xxx

xy

xy

xy

xxxyyy





































为变量

为解决污水对河流的污染问题，某城市拟建污水处理站，备选的站址有A、B、C

三个，其投资等技术经济参数如下表：

投资（万元）处理能力

（万吨∕

年）

水处理成本

（元∕万

吨）

水处理指标（吨∕万吨）

污染物1污染物2

A5

B4

C30

按环保部门的要求，每年至少要从污水中清除8万吨的污染物1和6万吨的污染

物2，构建一个整数规划模型，在满足环保要求的前提下使投资和运行费用最少。

第五章整数规划习题

考虑下列数学模型

)()(min

2211

xfxfz

且满足约束条件

（1）或

10

1

x

，或

10

2

x

；

（2）下列各不等式至少有一个成立：

















152

15

152

21

21

21

xx

xx

xx

（3）

0

21

xx

或5或10

（4）

0

1

x

，

0

2

x

其中

)(

11

xf

=











0,0

0,520

1

11

x

xx

如

如

)(

22

xf











0,0

0,612

2

22

x

xx

如

如

将此问题归结为混合整数规划的模型。

解：2211

612510minxyxyz



































•••













•

•

••

），，＝（或，

）（

）（

）（

；）（

11.110;00)4(

1

11105503

2

152

15

152

)1(10

101

0

21

1110987

111098721

654

621

521

421

32

31

2211

iyxx

yyyyy

yyyyyxx

yyy

Myxx

Myxx

Myxx

Myx

Myx

MyxMyx

i

试将下述非线性的0-1规划问题转换成线性的0-1规划问题

3

332

2

1

maxxxxxz











），（或3,2,110

332

321

jx

xxx

j

解：令

y









否则

，当

,0

11

32

xx

故有

yxx

32，又

2

1

x

，

3

1

x

分别与1

x

，3

x

等价，因此题中模型可转换为

31

maxxyxz





























变量均为10,,,

1

332

321

32

3

2

321

yxxx

yxx

xy

xy

xxx

某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1

表5-1

仪器装置代号体积重量实验中的价值

A

1

A

2

A

3

A

4

A

5

A

6

v

1

v

2

v

3

v

4

v

5

v

6

w

1

w

2

w

3

w

4

w

5

w

6

c

1

c

2

c

3

c

4

c

5

c

6

要求：（1）装入卫星的仪器装置总体积不超过V，总质量不超过W；（2）A

1

与A

3

中最多安装一件；（3）A

2

与A

4

中至少安装一件；（4）A

5

同A

6

或者都安上，或者都

不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立

这个问题的数学模型。

解：

j

j

j

xcz





6

1

max

























































否则

仪器安装

,0

,1

1

1

65

42

31

6

1

6

1

j

j

j

jj

j

jj

A

x

xx

xx

xx

Wxw

Vxv

某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费

用最小。若10个井位的代号为s

1

，s

2

,…s

10

,相应的钻探费用为c

1

，c

2

,…,c

10

,

并且井位选择上要满足下列限制条件：

（1）或选择s

1

和s

7

，或选择钻探s

8

；

（2）选择了s

3

或s

4

就不能选择s

5

，或反过来也一样；

（3）在s

5

,s

6

,s

7

,s

8

,中最多只能选两个；试建立这个问题的整数规划模型。

解：







10

1

min

j

jj

xcz













































，否则

井位选择钻探第

0

s,1

2

11

11

5

j

8765

5487

5381

10

1

j

x

xxxx

xxxx

xxxx

x

j

用割平面法求解下列整数规划问题

（a）21

97maxxxz

















且为整数0,,

357

63

21

21

21

xx

xx

xx

（b）21

5x4xminz























且为整数0x,x

2x3x

54xx

72x3x

21

21

21

21

（c）321

264maxxxxz























且为整数0,,,

5

56

544

321

321

21

21

xxx

xxx

xx

xx

（d）21

411maxxxz























且为整数0,,

42

1625

142

21

21

21

21

xx

xx

xx

xx

解：（a）不考虑整数约束，用单纯形法求解相应线性给华问题得最终单纯形表，

见表5A-1。

表5A-1

x

1

x

2

x

3

x

4

x

2

7/2

x

1

9/2

0

1

1

0

7/22

-1/22

1/22

3/22

c

j

-z

j

00-28/11-15/11

从表中第1行得

2

7

22

1

22

7

432

xxx

由此

0

22

1

22

7

2

1

3

432

xxx

即

2

1

22

1

22

7

143

sxx

将此约束加上，并用对偶单纯形法求解得表5A-2。

表5A-2

x

1

x

2

x

3

x

4

s

1

x

2

7/2

x

1

9/2

s

1

-1/2

0

1

0

1

0

0

7/22

-1/22

[-7/22]

1/22

3/22

-1/22

0

0

1

c

j

-z

j

00-28/11-15/110

x

2

3

x

1

32/7

x

3

11/7

0

1

0

1

0

0

0

0

1

0

1/7

1/7

1

-1/7

-22/7

c

j

-z

j

000-1-8

由表5A-2的x行可写出

)

7

4

4()

7

6

1()

7

1

0(

141

sxx

又得到一个新的约束

7

4

7

6

7

1

214

ssx

再将此约束加上，并用对偶单纯形法求解得表5A-3。

表5A-3

x

1

x

2

x

3

x

4

s

1

s

2

x

2

3

x

1

32/7

x

3

11/7

s

2

-4/7

0

1

0

0

1

0

0

0

0

0

1

0

0

1/7

1/7

[-1/7]

1

-1/7

-22/7

-6/7

0

0

0

1

c

j

-z

j

000-1-80

x

2

3010010

x

1

4

x

3

1

x

4

4

1

0

0

0

0

0

0

1

0

0

0

1

-1

-4

6

1

1

-7

c

j

-z

j

0000-2-7

因此本题最优解为x

1

=4，x

2

=3，z=55

（b）本题最优解为x

1

=2，x

2

=1，z=13

（c）本题最优解为x

1

=2，x

2

=1，x

3

=6，z=26

（d）本题最优解为x

1

=2，x

2

=3，z=34

分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-2

所。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每

人完成一项。试确定总花费时间为最少的指派方案。

表5-2

任务

人

ABCDE

甲

乙

丙

丁

25

39

34

24

29

38

27

42

31

26

28

36

42

20

40

23

37

33

32

45

解：

加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构

造表为5A-4

表5A-4

任务

人

ABCDE

甲2529314237

乙

丙

丁

戊

39

34

24

24

38

27

42

27

26

28

36

26

20

40

23

20

33

32

45

32

对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，丁-A，

总计需要131小时。

某航空公司经营A，B，C三个城市之间的航线，这些航线每天班机起飞与到达

时间如表5-3所示。

表5-3

航班号起飞城市起飞时间到达城市到达时间

101

102

103

104

105

106

107

108

109

110

111

112

113

114

A

A

A

A

A

B

B

B

C

C

B

B

C

C

9：00

10：00

15：00

20：00

22：00

4：00

11：00

15：00

7：00

15：00

13：00

18：00

15：00

7：00

B

B

B

C

C

A

A

A

A

A

C

C

B

B

12：00

13：00

18：00

24：00

2：00

7：00

14：00

18：00

11：00

19：00

18：00

23：00

20：00

12：00

设飞机在机场停留的损失费用大致与停留时间的平方成正比，又每架飞机从降落

到下班起飞至少需要2小时准备时间，试决定一个使停留费用损失为最小的飞行

方案。

解：把从某城市起飞的飞机当作要完成的任务，到达的飞机看作分配去完成任务

的人。只要飞机到达后两个小时，即可分配去完成起飞的任务。这样可以分别对

城市A，B，C各列出一个指派问题。各指派问题效率矩阵的数字为飞机停留的损

失的费用。设飞机在机场停留一小时损失为a元，则停留2小时损失为4a元，

停留3小时损失为9a，依次类推。

对A，B，C三个城市建立的指派问题得效率矩阵分别见表5A-6，表5A-7，表

5A-8。

表5A-5城市A

起飞

到达

105

106

107

108

109

110

4a

361a

225a

484a

196a

9a

400a

256a

529a

225a

64a

625a

441a

16a

400a

169a

36a

4a

81a

625a

225a

64a

16a

121a

9a

表5A-6城市B

起飞

到达

112

101

102

103

113

114

256a

225a

100a

64a

256a

529a

484a

289a

225a

529a

9a

4a

441a

361a

9a

625a

576a

361a

289a

625a

36a

25a

576a

484a

36a

表5A-7城市C

起飞

到达

1

104

105

111

112

49a

25a

169a

64a

225a

169a

441a

256a

225a

169a

441a

256a

49a

25a

169a

64a

对上述指派问题用匈牙利法求解，即可得到一个使停留费用损失最小的方案。

5-8需制造2000件的某种产品，这种产品可利用A，B，C设备的任意一种加工，

已知每种设备的生产准备结束费用，生产该产品时的单件成本，以及每种设备的

最大加工量如表5-4所示，试对此问题建立整数规划模型并求解。

表5-4

设备准备结束费（元）生产成本（元/件）最大加工数（件）

A

B

C

100

300

200

10

2

5

600

800

1200

设x为在第j台设备上生产的产品数，j=A，B，C，则问题的数学模型可表为：

321321

521minxxxyyyz





























10

12000

8000

6000

2000

3

2

1

321

或

j

y

yx

yx

yx

xxx

最优解为x

1

=0，x

2

=800，x

3

=1200，z=8100

5-9运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某

一城市出发，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一

次，然后回到原出发城市。已知城市i和城市j之间的距离为d

ij

，问该商贩应

选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划

模型。

解：设









，否则

直接去旅行商贩从

0

ji,1

ij

x

由此可写出其整数规划模型为







n

i

n

j

ijij

xdz

1

min















































jin...1ji

n...1i

1

),...,1(1

),...,1(1

1

，，，，

），也可取整数值，，为连续变量（

i

ijji

n

j

ij

n

i

ij

u

nnxuu

nix

njx

有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然

后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假

定用t

ij

表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品

总的加工周期为最短。试建立这个问题的数学模型。

解：用x

ij

表示第i中产品在j机床上开始加工的时刻，则问题的数学模型可表

示为：



333323231313

,,maxmintxtxtxz

互斥性约束

或

加工顺序约束













































0

10;3,2,1;2,1

)1(

)2,1;3,2,1(

,1,1

,1

1,

ij

iijjiji

ijiijij

jiijij

x

ji

Mxtx

Mxtx

jittx







某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良好。

如一个或多个元件安装几个备用件将提高系统的可靠性。已知系统运转可靠性为

各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体数值见

表5-5。

表5-5

备用件数元件可靠性

123

0

1

2

3

4

5

又三种元件分别的价格和重量如表5-6所示。已知全部备用件的费用预算限制为

150元，重量限制为20千克，问每个元件各安装多少备用件（每个元件备用件

不得超过5个），是系统可靠性为最大。试列出这个问题的整数规划模型。

表5-6

元件每件价格（元）重量（千克/件）

1

2

3

20

30

40

2

4

6

解：用x,x,x分别表示1，2，3三个元件安装的备用件数量。根据题中条件及费

用、重量的限制，元件1的备件最多安装5个，元件2备件最多5个，元件3

的备件最多安装3个。故问题的数学模型可表示为：

)9.07.0()95.075.06.0(

)9.08.07.06.05.0(max

654321

yyyyyyy

yyyyyyz

































































)13,...,110

)3,2,1(0

1

1

1

20642

150403020

13

11

10

7

6

1

321

321

iy

jx

y

y

y

xxx

xxx

i

j

i

i

i

i

i

i

（或

用你认为合适的方法求解下述问题：

321

52maxxxxz

















0,,

102

15310

321

321

321

xxx

xxx

xxx

解：

将问题改写为

321

52maxxxxz























10),3,2,1(0

102

)1(15310

15310

321

321

321

或yjx

xxx

Myxxx

Myxxx

j

求解得x

1

=0,x

2

=0,x

3

=10,y=1,z=50

下述线性规划问题

321

101020maxxxxz

















且取整数值,0,,

204206

154202

321

321

321

xxx

xxx

xxx

说明能否用先求解相应的线性规划问题然后凑整的办法来求得该整数规划的一

个可行解。

解：当不考虑整数约束，求解相应线性规划得最优解为x

1

=10/3,x

2

=x

3

=0。用凑整

法时令x

1

=3,x

2

=x

3

=0,其中第2个约束无法满足，故不可行。

某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代

号及其能覆盖的居民小区编号如表5-7所示，问为覆盖所有小区至少应建多少所

小学，要求建模并求解。

表5-7

备选校址代号覆盖的居民小区编号

A

B

C

D

E

F

1,5,7

1,2,5

1,3,5

2,4,5

3,6

4,6

解：令









，否则

备选校址建校在第

0

i,1

x

FEDCBA

xxxxxxzmin























11

11

1

11

AFD

FEEC

DB

DCBACBA

xxx

xxxx

xx

xxxxxxx

答案为在A，D，E三个备选校址建校。

已知下列五名运动员各种姿势的游泳成绩（各为50米）如表5-8所示，试问如

何从中选拔一个参加200米混合泳的接力队，使语气比赛成绩为最好。

表5-8单位：秒

赵钱张王周

仰泳

蛙泳

蝶泳

自由泳

解：由下列运动员组成混合接力队：张游仰泳，王游蛙泳，钱游蝶泳，赵游自由

泳，预期总成绩为秒。

5-16用匈牙利法求解下述指派问题，已知效率矩阵分别如下：

（a）

























16151211

15141615

17161213

121097

（b）

































1096109

53248

57246

79278

310283

解：（a）最优指派方案为x

13

=x

22

=x

34

=x

41

=1,最优值为48；

（b）最优指派方案为x

15

=x

23

=x

32

=x

44

=x

51

=1；最优值为21

5-17从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作。已知每人完成各

项工作的时间如表5-9所示。规定每项工作只能由一个人去单独完成，每个人最

多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意

承担第4项任务。在满足上述条件下，如何分配工作，使完成四项工作总的花费

时间为最少。

表5-9

人

工作

甲乙丙丁戊

1

2

3

4

10

5

15

20

2

10

5

15

3

15

14

13

15

2

7

6

9

4

15

8

解：先增加一种假想工作5，再据题中给的条件列出表5A-9

表5A-8

人

工作

甲乙丙丁戊

1

2

3

4

5

10

5

15

20

∞

2

10

5

15

0

3

15

14

13

0

15

2

7

∞

0

9

4

15

8

0

对表5A-9用匈牙利法求解得最优分配方案为：甲-2，乙-3，丙-1，戊-4，对丁

不分配工作。

5-18设有m个某种物资的生产点，其中第i个点（i=1，…，m）的产量为a

i

。

该种物资销往n个需求点，其中第j个需求点所需量为b

j

（j=1，…，n）。已知



j

j

i

i

ba

。已知。又知从各生产点往需求点发运时，均需经过p个中间编组

站之一转运，若启用第k个中间编组站，不管转运量多少，均发生固定费用f，

而第k个中间编组站转运最大容量限制为q

k

（k=1，…，p）。用c

ik

和c

kj

分别表

示从i到k和从k到j的单位物资的运输费用，试确定一个使总费用为最小的

该种物资的调运方案。

解：设









，否则

个编组站启用第

0

k,1

k

y

则问题的数学模型可表述为：

••

j

kjkj

kk

ikik

i

k

k

k

xcxcyfzmin

































•



















100,0

),...,1(

),...,1(

),...,1(

),...,1(

),...,1(

或

kkjik

i

kik

ij

kjik

i

kik

k

jkj

k

iik

yxx

pkyMx

pkxx

pkqx

njbx

miax

某单位5个备选投资项目，其所需投资额度和预期收益如表：

项目所需投资额（万元）期望收益（万元）

A610

B48

C27

D46

E59

1、.A、C、E之间必须选择一个，却仅需选择一项。

2、B、D之间需选择，也仅需选择一项。

3、C和D密切相关，C的实施必须以D的实施为前提

该单位有15万元现金，问如何投资使收益最大。