鼻翼薄-家风家训

第五章 整数规划习题

考虑下列数学模型

minzf
1
(x
1
)f
2
(x
2< br>)

且满足约束条件
（1）或
x
1
10
，或
x
2
10
；
（2）下列各不等式至少有一个成立：

2x
1
x
2
15


x
1
x
2
15

x2x15
2


1

（3）
x
1
x
2
0
或5或10
（4）
x
1
0
，
x
2
0

其中

205x
1
,如x
1
0
< br>,如x
1
0

f(x)

11
=

0

126x
2
,如x
2
0

,如x
2
0

f(x)

0

22

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

解：
minz10y
1
5x
1
12y
2
6x
2


（

0）x
1
y
1
•M；x
2
y< br>2
•M

1（

）x
1
10y
3
•M

x
2
10(1y
3
)•M

（

2）x
1
x
2
15y
4M


x
1
x
2
15y
5M


x
1
2x
2
15y
6< br>M

y
4
y
5
y
6
2

（

3）x
1
x
2
0y
7
5y
8
5y
9
10y
10
11y
11< br>
yyyyy1
7891011

（1i＝1，.•••， 11）

(4)x
1
0，x
2
0;y
i
0或




试将下述非线性的0-1规划问题转换成线性的0-1规划问题
3
maxzx< br>1
2
x
2
x
3
x
3


2x
1
3x
2
x
3
3

x0或1，（j1,2,3）


j


1，当x
2
x
3
1

y

0,否则
解：令
23
xxyxx
23
11
故有，又，分别与
x
1
，
x3
等价，因此题中模型可转换为
maxzx
1
yx
3


2x
1
3x
2
x
3
3


yx
2


yx
3

xxy1
3
< br>2



x
1
,x
2
,x
3
,y均为01变量


某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表
5-1
表 5-1
仪器装置代体积 重量 实验中的价
号 值
A
1
v
1
w
1
c
1
A
2
v
2
w
2
c
2
A
3
v
3
w
3
c
3
A
4
v
4
w
4
c
4
A
5
v
5
w
5
c
5
A
6
v
6
w
6
c
6

要求：（1）装入卫星的仪器装置总体积不 超过V，总质量不超过W；（2）A
1
与A
3
中最多安装一件；（3）A2
与A
4
中至少安装一件；（4）A
5
同A
6
或者都安上，
或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。
试 建立这个问题的数学模型。
解：
maxz

c
j
x
j
j1
6


6


v
j
x
j
V

j1

6


w
j
x
jW

j1

xx1
3

1

x
2
x
4
1


x
5
x
6


x

1,安装A
j
仪器< br>
j

0,否则





某钻井队要从以下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
,s8
,中最多只能选两个；试建立这个问题的整数规划模型。

解：

minz

c
j
x
j
j1
10


10


x
j
5

j 1

xx1xx1
1835



x7
x
8
1x
4
x
5
1
xxxx2
678

5


1,选择钻探第s
j
井位

x



0，否则




用割平面法求解下列整数规划问题
（a）
maxz7x
1
9x
2


 x
1
3x
2
6


7x
1
 x
2
35

x,x,0且为整数


12

（b）
minz4x
1
5x
2


3x
1
2x
2
7

x4x5

12


3x
1
x
2
2



x
1
,x
2
0且为整数

（c）
maxz4x
1
6x
2
2x
3

4x
1
4x
2
5

x6x5
12


x
1
x
2
x
3
5



x
1
,x
2,x
3
,0且为整数

（d）
maxz11x
1
4x
2


x1
2x
2
14

5x2x16

12


2x
1
x
2
4



x
1
,x
2
,0且为整数

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



表5A-1
x
1
x
2
x
3
x
4
x
2
72 0 1 722 122
x
1
1 0 -122 322
92
c
j
-z
j
0 0 -2811 -1511

从表中第1行得
717
x
2
x
3
x
4

22222

171
x
2
3x
3
x
4
022222
由此
711
x
3< br>x
4
s
1

222
即
22
将此约束加上，并用对偶单纯形法求解得表5A-2。
表5A-2
x
1
x
2
x
3
x
4
s
1
x
2
0 1 722 122 0
72 1 0 -122 322 0
x
1
0 0 [-722-122 1
92 ]
s
1

-12
c
j
-z
j
0 0 -2811 -1511 0
x
2
3 0 1 0 0 1
x
1
1 0 0 17 -17
327 0 0 1 17 -227
x
3
117
c
j
-z
j
0 0 0 -1 -8
由表5A-2的x行可写出
164
x
1
(0)x
4
(1)s
1
(4)
777

又得到一个新的约束
164
x
4
s
1
s< br>2

77

7
再将此约束加上，并用对偶单纯形法求解得表5A-3。
表5A-3
x
1
x
2
x
3
x
4
s
1
s
2
x
2
0 1 0 0 1 0

3
x
1

327
x
3

117
s
2

-47
c
j
-z
j

x
2

3
x
1

4
x
3

1
x
4

4
c
j
-z
j



1
0
0
0
0
0
0
1
0
17
17
[-17
]
-1
7
-22
7
-6
7
-8
1
-1
-4
6
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
-1
0
0
0
1
0
0
1
1
-7
0 0 0 0 -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

任务
A B C D E
人
甲 25 29 31 42 37
乙 39 38 26 20 33
丙 34 27 28 40 32
丁 24 42 36 23 45
解：
加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，
构造表为5A-4
表5A-4

任务
A B C D E
人
甲
乙
丙
丁

25
39
34
24
29
38
27
42
31
26
28
36
42
20
40
23
37
33
32
45

戊 24 27 26 20 32
对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，
丁-A，总计需要 131小时。

某航空公司经营A，B，C三个城市之间的航线，这些航线每天班机起飞与
到达时间如表5-3所示。
表5-3
航班号 起飞城市 起飞时间 到达城市 到达时间
101 A 9：00 B 12：00
102 A 10：00 B 13：00
103 A 15：00 B 18：00
104 A 20：00 C 24：00
105 A 22：00 C 2：00
106 B 4：00 A 7：00
107 B 11：00 A 14：00
108 B 15：00 A 18：00
109 C 7：00 A 11：00
110 C 15：00 A 19：00
111 B 13：00 C 18：00
112 B 18：00 C 23：00
113 C 15：00 B 20：00
114 C 7：00 B 12：00
设飞机在机场停留的损失费用大致与停 留时间的平方成正比，又每架飞机从
降落到下班起飞至少需要2小时准备时间，试决定一个使停留费用损 失为最小的
飞行方案。
解：把从某城市起飞的飞机当作要完成的任务，到达的飞机看作分配去 完成
任务的人。只要飞机到达后两个小时，即可分配去完成起飞的任务。这样可以分
别对城市A ，B，C各列出一个指派问题。各指派问题效率矩阵的数字为飞机停留
的损失的费用。设飞机在机场停留 一小时损失为a元，则停留2小时损失为4a
元，停留3小时损失为9a，依次类推。
对A， B，C三个城市建立的指派问题得效率矩阵分别见表5A-6，表5A-7，
表5A-8。
表5A-5 城市A

起飞
101 102 103 104 105
到达
106
107
108
109
110

起飞
到达
4a
361a
225a
484a
196a
106
9a 64a
400a 625a
256a 441a
529a 16a
225a 400a
表5A-6 城市B
107 108
169a
36a
4a
81a
625a
111
225a
64a
16a
121a
9a
112

101
102
103
113
114

起飞
到达
256a
225a
100a
64a
256a
109
529a 9a
484a 4a
289a 441a
225a 361a
529a 9a
表5A-7城市C
110 113
625a
576a
361a
289a
625a
114
36a
25a
576a
484a
36a
104 49a 225a 225a 49a
105 25a 169a 169a 25a
111 169a 441a 441a 169a
112 64a 256a 256a 64a
对上述指派问题用匈牙利法求解，即可得到一个使停留费用损失最小的方
案。

5-8 需制造2000件的某种产品，这种产品可利用A，B，C设备的任意一种
加工，已 知每种设备的生产准备结束费用，生产该产品时的单件成本，以及每种
设备的最大加工量如表5-4所示 ，试对此问题建立整数规划模型并求解。
表5-4
设 备 准备结束费生产成本（元最大加工数
（元） 件） （件）
A 100 10 600
B 300 2 800
C 200 5 1200
设x为在第j台设备上生产的产品数，j=A，B，C，则问题的数学模型可表
为：

minz100y
1
300y
2
200y
3
10x
1
2x
2
5x
3


x1
x
2
x
3
2000


0 x
1
600y


0x
2
800y

0x1200y
3


y0或1


j

最优解为x
1
=0，x
2
=800 ，x
3
=1200，z=8100

5-9 运筹学中著名的旅行商贩（ 货郎担）问题可以叙述如下：某旅行商贩
从某一城市出发，到其它几个城市去推销商品，规定每个城市均 须到达而且只到
达一次，然后回到原出发城市。已知城市i和城市j之间的距离为d
ij
，问该商
贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数
规划 模型。

1,旅行商贩从i直接去j
x
ij



0，否则
解：设
由此可写出其整数规划模型为

nn
j


minz

d
ij
x
ij
i1
< br>
n


x
ij
1(j1,...,n)

i1

n


x
ij
1(i1 ,...,n)

j


u
i
u
jnx
ij
n1

...，n），也可取整数值

u
i
为连续变量（i1，

i，j1，...，n，ij
< br>





有三个不同产品要在三台 机床上加工，每个产品必须首先在机床1上加
工，然后依次在机床2，3上加工。在每台机床上加工三个 产品的顺序应保持一
样，假定用t
ij
表示在第j机床上加工第i个产品的时间，问应 如何安排，使三
个产品总的加工周期为最短。试建立这个问题的数学模型。
解：用x
ij
表示第i中产品在j机床上开始加工的时刻，则问题的数学模型
可表示为：

minzmax

x
13
t
13
,x
23
t
23
,x
33
t
33




x
ij
t
ij
t
i,j1
(i1,2,3;j1,2)加工顺序约束



x
ij
t
ij
x
i1,j
 M

i


x
i1,j
t
i1, j
x
ij
M(1

i
)

互斥性约 束

i1,2;j1,2,3;

0或1


x
ij
0



某电子系统由三种元 件组成，为使系统正常运转，每个元件都必须工作良
好。如一个或多个元件安装几个备用件将提高系统的 可靠性。已知系统运转可靠
性为各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体 数
值见表5-5。
表 5-5
备用件数 元件可靠性
1 2 3
0
1
2
3
4
5
又三种元件分别的价格和重量如表5-6所示。已知全部备用件的费用预算限

制为150元，重量限制为20千克，问每个元件各安装多少备用件（每个元 件备
用件不得超过5个），是系统可靠性为最大。试列出这个问题的整数规划模型。
表 5-6
元件 每件价格（元） 重量（千克件）
1 20 2
2 30 4
3 40 6
解：用x,x,x分别表示1，2，3三个元件安装的备用件数量。根据题中条 件
及费用、重量的限制，元件1的备件最多安装5个，元件2备件最多5个，元件
3的备件最多 安装3个。故问题的数学模型可表示为：
maxz(0.5y
1
0.6y
2
0.7y
3
0.8y
4
0.9y
5
y
6
)

(0.6y
7
0.75y
8
0.95y
9
y
10
)(0.7y
11< br>0.9y
12
y
13
)


20x1
30x
2
40x
3
150


2x
1
4x
2
6x
3
20

6< br>

y
i
1

i1


10


y
i
1

i7

13


y
i
1

i11

x
j
0(j1,2,3)


（1i1,...,13)

y
i
0或


用你认为合适的方法求解下述问题：
maxzx
1
2x
2
5x
3

< br>x
1
10x
2
3x
3
15


2x
1
x
2
x
3
10

x,x,x0

123
解：
将问题改写为

maxzx
1
2x
2
5x
3

< br>
x
1
10x
2
3x
3
15My

x10x3x15(1y)M
23

1


2x
1
x
2
x
3
10

x
j
0(j1,2,3),y0或1



求解得x
1
=0,x
2
=0,x
3< br>=10,y=1,z=50

下述线性规划问题

maxz20x
1
10x
2
10x
3


2x
1
20x
2
4x
3
15


6x
1
20x
2< br>4x
3
20

x,x,x0,且取整数值


123

说明能否用先求解相应的线性规划问题然后凑整的办法来求得该整数规划
的一个可行解。 解：当不考虑整数约束，求解相应线性规划得最优解为x
1
=103,x
2
=x
3
=0。用
凑整法时令x
1
=3,x
2
=x
3
=0,其中第2个约束无法满足，故不可行。

某市为方便学生上学 ，拟在新建的居民小区增设若干所小学。已知备选校
址代号及其能覆盖的居民小区编号如表5-7所示， 问为覆盖所有小区至少应建多
少所小学，要求建模并求解。
表5-7
备选校址代号 覆盖的居民小区编号
A 1,5,7
B 1,2,5
C 1,3,5
D 2,4,5
E 3,6
F 4,6

1,在第i备选校址 建校
x


0，否则
解：令

minzx
A
x
B
x
C
x
Dx
E
x
F


x
A
x
B
x
C
1x
A
x
B
x
C
x
D
1

xx1

BD

x
C
x
E
1x
E
x
F
1


x
D
x
F
1x
A
1

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

已知下列五名运动员各种姿势的游泳成 绩（各为50米）如表5-8所示，试
问如何从中选拔一个参加200米混合泳的接力队，使语气比赛成 绩为最好。
表5-8 单
位：秒
赵 钱 张 王 周
仰泳
蛙泳
蝶泳
自由泳
解：由下列运动员组成混合接力队：张游仰泳， 王游蛙泳，钱游蝶泳，赵游
自由泳，预期总成绩为秒。

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

791012


13121617



15161415


11121516

（a）


382103


87297



64275


84235


（b）

9106910


解：（a ）最优指派方案为x
13
=x
22
=x
34
=x
4 1
=1, 最优值为48；
（b）最优指派方案为x
15
=x< br>23
=x
32
=x
44
=x
51
=1；最优 值为21
5-17 从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作。已知每人完
成各 项工作的时间如表5-9所示。规定每项工作只能由一个人去单独完成，每个
人最多承担一项任务。又假 定对甲必须保证分配一项任务，丁因某种原因决定不
同意承担第4项任务。在满足上述条件下，如何分配 工作，使完成四项工作总的
花费时间为最少。
表5-9
人 甲 乙 丙 丁 戊
工作
1 10 2 3 15 9
2 5 10 15 2 4
3 15 5 14 7 15
4 20 15 13 6 8
解：先增加一种假想工作5，再据题中给的条件列出表5A-9
表5A-8
人 甲 乙 丙 丁 戊
工作
1 10 2 3 15 9
2 5 10 15 2 4
3 15 5 14 7 15
4 20 15 13 ∞ 8
5 ∞ 0 0 0 0
对表5A-9用匈牙利法求解得最优分配方案为：甲-2，乙-3，丙-1，戊-4，对丁不分配工作。

5-18 设有m个某种物资的生产点，其中第i个点（i=1，… ，m）的产量为
a
i
。该种物资销往n个需求点，其中第j个需求点所需量为b
j
（j=1，…，n）。
a
i


b
j

j
已知
i
。已知。又知从各生产点往需求点发运时，均需经过p个中间编组站之一转运，若启用第k个中间编组站，不管转运量多少，均发生固定费用
f，而第k个中间编 组站转运最大容量限制为q
k
（k=1，…，p）。用c
ik
和c
k j
分别
表示从i到k和从k 到j的单位物资的运输费用，试确定一个使总费用为最小

的该种物资的调运方案。

1,启用第k个编组站
y
k



0，否则
解： 设
则问题的数学模型可表述为：
minz

f
k
•yk


c
ik
•x
ik


kikk



x
ik
a
i
(i1,...,m)

k

xb(j1,...,n)
k jj


k



x
ik
q< br>k
(k1,...,p)

i



x< br>ik


x
kj
(k1,...,p)

ij



x
ik
M•y
k
(k1, ...,p)

i


x
ik
0,x
k j
0y
k
0或1




c
j
kj
x
kj

精心搜集整理，只为你的需要