最新最全整数规划习题(完整版)

第五章整数规划习题

5.1

考虑以下数学模型

min z = fiXi) + f (x)

(

22

且满意约束条件

(1) X2 0

或 ,或河

：

(2)

以下各不等式至少有一个成立：

2x x *5

〔

+

2

+ X2 >15

x+2x2 215

〔

(3) Xi -X2 =05 10

或 或

(4) No , X2 2 0

为

其中

20 + 5xi,>0

如

fi(xO 10

=

，如=°

12 + 6x2,>0

如

f(X2= .0

2

)

，如=

0

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

minz = 1°y* 5xi 12y2 -6x2

〔 十

（）

0xi V yi ,M; x y ? M

22

（）

1 % >10- y

3

X2 10 — （1 — y3） ? M

己

（

2 X1 +

）

x A5- yM

24

Xi +X2 2 15- yM

5

X1

+ 2x 2 15 - yeM

2

第

+y + y6 < 2

5

5.20-10-1

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

（）

3 x _ =y -5y 5y -10y 11yn

1X20789w

++

工

y8 + y9 + Yw + y” = 1

（） xi >0x - 0; yi =

4

，

2

0

或

max z - % x x - x

_ 2 + 3

233

一

2xi + 3x2 + X3 <3

Xj = 01, = 1,2,3

或

)

，当

=Xs = 1

解：令

y =

故有

xx3 =y,

2

X

2

2 3

又〔，分别与、等价，因此题中模型可转换为

XXiXX3

max z = % + y - X3

—2xi + 3x2 X3 — 3

y WX2

\"X3

X2 * X3 V y F

一均为 一变

XiX2X3y1

，，，

5.35-1

某科学试验卫星拟从以下仪器装置中选如干件装上； 有关数据资料见表

试验中的价值 仪器装置代号

Ci Vi Wi

C2 V2

C3 V3

C4 W4 V4

C5 W5 V5

C6 Wfe V6

表

5-1

Ai

体积

重量

A

N2

N

A

As

A

B

要求：装入卫星的仪器装置总体积不超过 总质量不超过 与中最多安装

(

1)V,W (2) AA

一件；氏与中至少安装一件；同玲或者都安上，或者都 担心；总的目的是

(

3)4(4) As

装上取的仪器装置使该科学卫星发挥最大的试验价值； 试建立

这个问题的数学模型； 解：

6

max z = Z CjXj j =

\'6

三

VjXj -V jT

? Wj Xj - w jT

Xi x -1 X2

3

+

I

6

十

X4 Z 1

X5 = X6

1 AjX

，安装仪器

?

=<

J

0

，否就

5.4 105

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

小；如个井位的代号为相应的钻探费用为并且井位选择上要满意以

10

Si , S2, S10,C1 , C2, ,C 10,

下限制条件：

(1)

或选择和或选择钻探

S1S7,S8

；

(2)

选择了 或就不能选择或反过来也一样；

S3S4S5,

(3)

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

S5,S6,S7,S8,

解：

10

min z = ? CjXj j=3

\'

10

E Xj = 5 jm

X1 + X8 = 1 X3 + Xs < 1

X7 =1 X4 + X5 1

?彘三

X5 + X6 + X7 + X8 M 2

，选择钻探第井

Sj

‘0

,否就

5.5

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

(a)

maxz = 7x9x—q 3x2 — 6 7Xi x V 35 x x, -

〔 一 且为整

2 21s2

+

(b)

minz 45x2

=数对

% +2X2 V Xi -4x2 - 5 3xi + X2 -2 x 20

XlJ2

且为整

、

I \' ?

max z 4xi 6x

一

2

+ 2x3

(c)

4xi — 4J 5

X

2

-Xi 6X2 — 5

?

一

Xi + X2 + X3 -5

*,X2X3,20

，

且为整

(d) max z = \"Xi +4x2

0

-x+2x2 ?14 5x 2 <16 2xi - X2 4

〔 三

12

X

+

KM*

。且为整

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

(a)

5A-1

；

表

5A-1

Xi X4

x 7/2

2

Xi 9/2 1 0 -1/22 3/22

Cj-z j 0 -15/11

0

1 7/22 1/22

1

7 1

— v — v e =——

「

从表中第行得

工

7

0

由此

即

将此约束加上，并用对偶

表

5A-2

x —X3

2

二

22 22 _ 2

1 7 1

X2 -3 =—

一一 -

—X3

2 22 22

7 1

1

L

X4 — 0

22 22 2

单纯形法求解得表

5A-2

；

34 1

X2 7/2

xi 9/2 1 0 -1/22 3/22 0

si -1/2 0 0

Cj -z j 0 0

X2 3 0 1 0 0 1

xi 32/7 1 0

x 11/7 1/7

3

Xi X2

0 1 7/22 1/22 0

0 0 1 -22/7

0 0 -1 -8 Cj -Zj 0

1

X3 X4 Si

[-7/22] -1/22 1

-28/11

0 1/7 -1/7

-15/11 0

由表的行可写出

5A-2x

Xi (0-)x

4

++

」

4 x 4 4

+++

6

(-1~)s = (4 -)

1

又得到一个新的约束

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

表

5A-3

5A.3

；

Xi X2 X3 X4 Si S2

X2 3 0 1 0 0 1 0

x 1 32/7 1 0 0 1/7 -1/7 0

x11/7 0 1 1/7 -22/7 0

3

s 2 -4/7 0 0 0 [-1/7] -6/7 1

0

0 0 0 0 Cj-z j -1

X2 3 0 1 0 0 1 0

X1 4 1 1

X3 1 0 0 1 0 -4 1

X4 4

0 0 0 6

0 0 0 0 -2 -7 Cj-Zj

0 0 0

1 -7

-1

因此此题最优解为

xi=4, X2=3, =55

Z

(b)xi=2, X2=1, z=13

此题最优解为

(c)

此题最优解为

Xi=2, x=1, X3=6,

2

(d)

此题最优解为

xi=2, X2=3, =34

Z

z=26

5.65-

安排甲，乙，丙，丁四个人去完成五项任务；每人完成各项任务时间如表

2

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

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

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

造表为

5A-4

表

5A-4

A B C D E

29 31 25

38 26 20 33 39

27 28 40 32 34

42 37

甲

乙

丙

T

24 42 36 23 45

24 27 32

26 20

戊

对表再用匈牙利法求解，得最优安排方案为甲乙和丙?

5A.4B,.DC,E, T-A,

?

总计需要小时;

131

5.7 A, B, C

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

如表所示；

5-3

表

5-3

航班号

101 A B

102 A B

103 A B

104 A C

起飞城市 起飞时间 到达城市

9 00 12 00

：：

10 00 13 00

：：

15 00 18 00

：：

20 00 24 00

：：

到达时间

105 C 00

106 B A

107

108 B 00 A 18 00

A

B A

：

7

109 C 00 A 11 00

：

15

00 19

00

A

C

110

：

13

111 B 00 C 18 00

：

18

112 B 00 C 23 00

：

15

113 C 00 B 20 00

：

712 00

00

B

C

114

：

设飞机在机场停留的缺失费用大致与停留时间的平方成正比, 乂每架&机从降落

222

00

： ：

47

00

： ：

00

11

：

15

00

00 14

=J

到下班起飞至少需要小时预备时间，试打算一个使停留费用缺失为最小的飞行

2

方案;

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

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

A, B, C

各列出一个指派问题；各指派问题效率矩阵的数字为飞机停留的损 失的费用；

设飞机在机场停留一小时缺失为 元，就停留小时缺失为元，

a24a

停留小时缺失为依次类推；

39a,

对三个城市建立的指派问题得效率矩阵分别见表 表表

A, B, C5A-6,5A.7,

5A-8

；

表城市

5A-5 A

起飞

101 102 103 104 105

到科、

106 4a 9a 64a 169a 225a

107 400a

108 225a 256a 441a

109 484a 529a 16a 81a 121a

110 196a 225a 400a 625a 9a

361a 625a

起飞

107 112 106 108 111

36a

4a 16a

64a

表

5A-6

城市

B

到

101 256a 529a 9a 625a 36a

102 4a

103 100a

113 225a

225a

64a

256a 529a 9a 625a 36a 114

起飞

484a 576a 25a

289a

110 109

441a 361a 576a

361a 484a

289a

114

表城市

5A-7C

113

104 49a 225a 225a 49a

169a 169a 25a 105 25a

441a 441a 169a 169a

256a 256a 64a 112 64a

111

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

5-8 2000A,B,C

需制造件的某种产品，这种产品可利用设备的任意一种加工,

已知每种设备的生产预备终止费用， 生产该产品时的单件成本，以及每种设备的

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

5-4

表

5-4

设备 最大加工数（件）

预备终止费（元）

生产成本（元/件）

■

■

A 100 10 600

B 300 2 800

c 200 5 1200

设为在第台设备上生产的产品数，就问题的数学模型可表为:

xjj=A, B, C,

min z = 100 yi + 300+ 200 y3 + 10xi + 2x2 + 5x3

Xi + X2 + X3 2 2000 0< < 600 y

0 < x 800 y o< x <1200y = 0

23

v

、

或

最优解为

Xi=0, X2=800, X3=1200, =8100

Z

5-9

运筹学中闻名的旅行商贩（货郎担）问题可以表达如下：某旅行商贩从某 一城市动

身，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一 次，然后回到

原动身城市；已知城市和城市之间的距离为，问该商贩应 选择一条什么样的路

ijdu

线次序旅行， 使总的旅程为最短；试对此问题建立整数规划 模型；

1i

，旅行商贩从直接去

解：设

1°

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

J

min z = ? ? djj

n n

为

—j

? Xij = 1 (j n)

n

? 乂寸

=1 (j

J

1 Uj -Uj + nxij - n -1

qi = 1,…n)

为连续变量( 也可取整数值

，，

ij = nij

，，

。

5.10 1

有三个不同产品要在三台机床上加工， 每个产品必需第一在机床上加工, 然后

依次在机床上加工；在每台机床上加工三个产品的次序应保持一样，

2, 3

假定用0表示在第机床上加工第个产品的时间，问应如何支配，使三个产 品总的

ji

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

A?

T

用表示第

Xji

中产品在机床上开头加工的时刻，就问题的数学模型可表

j

示为:

min z = max^x + 1 ,x + 1, x + t)

131323233333

Xj +tjj (j =1,2,3 j =1,2)

iJ4f

；

加工次序约束

Xij pj VMS

:Xi?H,j +ti *j -Xjj < M (1 -&i )

i =1,2; j =1,2,3; 6 = 0

或

Xjj >0

＞互斥性约束

5.11

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

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

牢靠性的乘积，而每一元件的牢靠性就是备用件数量的函数，详细数 值见表；

5-5

表

5-5

备用件数

0 0.5 0.6 0.7

1 0.6 0.75 0.9

2 0.95 1.0

3 1.0 1.0

4 0.9 1.0 1.0

5 1.0 1.0 1.0

元件牢靠性

1

0.7

0.8

2 3

又三种元件分别的价格和重量如表

5-6

所示；已知全部备用件的费用预算限制为

15020

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

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

5

表

5-6

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

1 20 2

2 30 4

3

40 6

解：用分别表示三个元件安装的备用件数量；依据题中条件及费 用，重

x,x,x1, 2, 3

量的限制，元件的备件最多安装个，元件备件最多个，元件的备件最多安

15253

装个；故问题的数学模型可表示为：

3

maxz = (0.5yi

+ 0.6y 0.7y + 0.8y + 0.9y y)

23456

(0.6y 0.75y 0.95y + y) - (0.7y+ 0.9y/ y)

789w13

、

++

++x

20xi + 30X2 + 40X3 < 150

2xi 4620

十 十 《

XX

23

6

Z y =1 | i J fe

10

yi=1 13

三

y =1

Xj >0(j =1,2,3)

yi

= ° 或

i = 1,…,13)

5.12

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

max z = 2x2 + 5

为 十

X

3

i — +10X2 — 3xs —15

2xi + X2 +X3 ?10

Xi, X2,X3 2°

解：

将问题改写为

max z = xi + 2x2 + 5x

3

Xi -10X2 +3X315 + My

〈-

— Xi +IOX2 - 3X3^-15+(1 - y)M

2xi + X2 + X3 10

三

Xj > oj =1,2,3), y = o

(

或

求解得

Xi =0,x 2=0,X3=10,y=1 ,z=50

5.13

下述线性规划问题

max z = 20xi ^10x \'Oxa

2

2xi +20X2 +4x315

《

:6xi + 20X2 + 4 = 20

X

3

为, 。,且取整数值

X2, X3 2

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

解；

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

xi=10/3,x =X3=0

2

；

时令其中第个约束无法满意，故不行行；

X=3,X2=X3=0,2

I

5.14

某市为便利同学上学，拟在新建的居民小区增设如干所学校；巳知备选校 址代号

及其能掩盖的居民小区编号如表 所示，问为掩盖全部小区至少应建多 少所学校，

5-7

要求建模并求解；

表

5-7

备选校址代号

掩盖的居民小区编号

A 1,5,7

B

C

D

E

F 4,6

1 i

，在第备选校址建

x = k

校

解：令

1°

min z = ++++

XA XB XC XD XEXF

土

X +X + Xc

A

B

21 X+X + Xc X 2 1

A BD

十

1,2,5

1,3,5

2,4,5

3,6

X

B

+X

D

>1

I

+X >1

E

X

C

X+XA

E F

X +X >1 X 21

D

FA

答案为在三个备选校址建校;

A, D, E

5.155058

已知以下五名运动员各种姿态的游泳成果 （各为米）如表所示，试

?

问如何从中选拔一个参与米混合泳的接力队，使语气竞赛成果为最好；

200

表单位：秒

58

?

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

赵

张 王 周

钱

仰泳

蛙泳

蝶泳

自由泳

37.7 32.9

43.4 33.1

33.3 28.5

29.2 28.5 31.1 29.6

26.4

33.8 37.0 35.4

42.2 34.7 41.8

38.9 33.6

30.4

预期总成果为秒；

126.2

5-16

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

一

7

9 10

12\"

13 12 16 17

15 16 14 15

(a)

16 J1 12 15

■3 31

2 10

7 2 9 7

2 7 5 6 4

5 4 2 3

10 10 6 9

(b)

一

9

最优值为

48

；

解:

（a）

最优指派方案

X13=X22=X34=X41 =

1 ,

为

X15=X23=X32=X44=X51 =

1 21

； 最优值为

5-17

从甲，乙，丙，丁,

戊五人中选择四人去完成四项工作；已知每人完成各

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

5-9

多承担一项任务；又假定对甲必需保证安排一项任务,

丁因某种缘由打算不同意

承担第项任务；在满意上述条件下，如何安排工作，使完成四项工作总的花费 时

4

间为最少；

不安排工

5-18m

设有个某种物资的生产点，其中

ii=1 , , m)a.

个点(的产量为

；

该种物资销往个需求点，其中第个需求点

nj

,n)

；

已知

所需量为

bj (j=1 , ? 3 bj

[ j

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

p

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

kf,

而第个中间编组站转运最大容量限制为 用8和分别表

kq (k=1, , p)Ckj

k

；

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

ikkj

资的调运方案；

_ 1 k

，启用第个编组

、站

yk

解：设 。

I

=

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

minz = ? fk yk ? Gk ,Xk +? ? c x

?

+ 三

kjkj

k i k k j

Za (i

为

k v

k

?冲

=bj (j =1,...,n)

k

? 为

k < qk ? =1,...,P

)

)i

Xk = X (k=1,...p)

^kj

，

I i j

I

E < M *y (k =1,..., p)

k

1

为洵 =° 或

k No,Xkj yk