整数规划习题.docx
- 文档编号:7336594
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:23
- 大小:27.47KB
整数规划习题.docx
《整数规划习题.docx》由会员分享,可在线阅读,更多相关《整数规划习题.docx(23页珍藏版)》请在冰点文库上搜索。
整数规划习题
第五章整数规划习题
5.1考虑下列数学模型
min
z
f1(x1)
f2(x2)
且满足约束条件
(1)或x1
10,或x210;
(2)下列各不等式至少有一个成立:
2x1
x2
15
x1
x2
15
x1
2x2
15
(3)x1
x20或5或10
(4)x1
0,x20
其中
20
5x1,如x1
0
f1(x1)=0
如x1
0
12
6x2,如x2
0
f2(x2)
0
如x2
0
将此问题归结为混合整数规划的模型。
解:
minz10y15x112y2
6x2
(0)x1
y1
M;x2
y2
M
(
1)x1
10
y3
M
x2
10
(1
y3)
M
(2)x1
x2
15y4M
x1
x2
15
y5M
x1
2x2
15
y6M
y4
y5
y6
2
()
x2
0y7
5y8
5y9
10y10
11y11
3x1
y7
y8
y9
y10
y11
1
(4)x1
0
,
x20;yi
或(
=,
,)
01i
1.
11
5.2试将下述非线性的
0-1规划问题转换成线性的
0-1规划问题
2
3
maxzx1
x2x3x3
2x13x2x3
3
xj
0或1,(j
1,2,3)
1
,当x2
x3
1
解:
令y
0
否则
故有x2x3
2
3
y,又x1,x1分别与x1,x3等价,因此题中模型可转换为
max
z
x1
y
x3
2x1
3x2
x3
3
y
x2
y
x3
x2
x3
y
1
x1,x2,x3,y均为0
1变量
5.3某科学实验卫星拟从下列仪器装置中选若干件装上。
有关数据资料见表5-1
表5-1
仪器装置代号
体积
重量
实验中的价值
A1
v1
w1
c1
A2
v2
w2
c2
A3
v3
w3
c3
A4
v4
w4
c4
A5
v5
w5
c5
A6
v6
w6
c6
要求:
(1)装入卫星的仪器装置总体积不超过
1
3
V,总质量不超过W;
(2)A
与A
中最多安装一件;(3)A2与A4中至少安装一件;(4)A5同A6或者都安上,或者都
不安。
总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。
试建立
这个问题的数学模型。
解:
6
maxz
cjxj
j
1
6
vj
xj
V
j
1
6
wj
xj
W
j
1
x1
x3
1
x2x4
1
x5
x6
xj
1
安装Aj仪器
0
否则
5.4某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用最小。
若10个井位的代号为s1,s2,⋯s10,相应的钻探费用为c1,c2,⋯,c10,并且井位选择上要满足下列限制条件:
(1)或选择s1和s7,或选择钻探s8;
(2)选择了s3或s4就不能选择s5,或反过来也一样;
(3)在s5,s6,s7,s8,中最多只能选两个;试建立这个问题的整数规划模型。
解:
10
min
z
cj
xj
j1
10
xj
5
j1
x1
x8
1
x3
x5
1
x7
x8
1
x4
x5
1
x5
x6
x7
x8
2
x
1
选择钻探第
sj井位
1,否则
5.5用割平面法求解下列整数规划问题
(a)maxz
7x1
9x2
x1
3x2
6
7x1
x2
35
x1,x2,0且为整数
(b)
minz
4x1
5x2
3x1
2x2
7
x1
4x2
5
3x1
x2
2
x1,x2
0且为整数
(c)
max
z
4x1
6x22x3
4x1
4x2
5
x1
6x2
5
x1
x2
x3
5
x1,x2,x3,
0且为整数
(d)
max
z
11x1
4x2
x1
2x2
14
5x1
2x2
16
2x1
x2
4
x1,x2,
0且为整数
解:
(a)不考虑整数约束,用单纯形法求解相应线性给华问题得最终单纯形表,见表5A-1。
表5A-1
x1
x2
x3
x4
x2
7/2
0
1
7/22
1/22
x1
9/2
1
0
-1/22
3/22
cj-zj
0
0
-28/11
-15/11
从表中第1行得
7
x3
1
x4
7
x2
22
2
22
x23
1
7
x3
1
由此
x40
2
22
22
7
1
s1
1
x3
x4
即
22
22
2
将此约束加上,并用对偶单纯形法求解得表5A-2。
表5A-2
x1
x2
x3
x4
s1
x2
7/2
0
1
7/22
1/22
0
x1
9/2
1
0
-1/22
3/22
0
s1
-1/2
0
0
[-7/22]
-1/22
1
cj-zj
0
0
-28/11
-15/11
0
x2
3
0
1
0
0
1
x1
32/7
1
0
0
1/7
-1/7
x311/7
0
0
1
1/7
-22/7
cj-zj
0
0
0
-1
-8
由表5A-2的x行可写出
x1
1
)x4
6
4
(0
(1)s1(4
)
7
7
7
又得到一个新的约束
1
6
s1
4
7
x4
s2
7
7
再将此约束加上,并用对偶单纯形法求解得表5A-3。
表5A-3
x1
x2
x3
x4
s1
s2
x2
3
0
1
0
0
1
0
x1
32/7
1
0
0
1/7
-1/7
0
x3
11/7
0
0
1
1/7
-22/7
0
s2
-4/7
0
0
0
[-1/7]
-6/7
1
cj
-zj
0
0
0
-1
-8
0
x2
3
0
1
0
0
1
0
x1
4
1
0
0
0
-1
1
x3
1
0
0
1
0
-4
1
x44
0
0
0
1
6
-7
cj-zj
0
0
0
0
-2
-7
因此本题最优解为x1=4,x2=3,z=55
(b)本题最优解为x1=2,x2=1,z=13
(c)本题最优解为x1=2,x2=1,x3=6,z=26
(d)本题最优解为x1=2,x2=3,z=34
5.6分配甲、乙、丙、丁四个人去完成五项任务。
每人完成各项任务时间如表
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
29
31
42
37
乙
39
38
26
20
33
丙
34
27
28
40
32
丁
24
42
36
23
45
戊
24
27
26
20
32
对表5A-4再用匈牙利法求解,得最优分配方案为甲-B,乙-D和C,丙-E,丁-A,总计需要131小时。
5.7某航空公司经营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
4a
9a
64a
169a
225a
107
361a
400a
625a
36a
64a
108
225a
256a
441a
4a
16a
109
484a
529a
16a
81a
121a
110
196a
225a
400a
625a
9a
表5A-6
城市B
起飞
106
107
108
111
112
到达
101
256a
529a
9a
625a
36a
102
225a
484a
4a
576a
25a
103
100a
289a
441a
361a
576a
113
64a
225a
361a
289a
484a
114
256a
529a
9a
625a
36a
表5A-7城市C
起飞
109
110
113
114
到达
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,则问题的数学模型可表为:
minz100y1300y2
200y310x12x25x3
x1
x2
x3
2000
0
x1
600y
0
x2
800y
0
x3
1200
y
yj0或1
最优解为x1=0,x2=800,x3=1200,z=8100
5-9运筹学中著名的旅行商贩(货郎担)问题可以叙述如下:
某旅行商贩从某一城市出发,到其它几个城市去推销商品,规定每个城市均须到达而且只到达一次,然后回到原出发城市。
已知城市i和城市j之间的距离为dij,问该商贩应选择一条什么样的路线顺序旅行,使总的旅程为最短。
试对此问题建立整数规划模型。
1
旅行商贩从
i直接去
j
xij
,否则
解:
设
0
由此可写出其整数规划模型为
n
n
minz
dijxij
i1
j
n
xij
1
(j
i
1
n
xij
1
(i
j
ui
uj
nxij
ui
为连续变量(
1,...,n)
1,...,n)
n1
i1,...,n),也可取整数值
i
,
,,
n
,
ij
j1...
5.10有三个不同产品要在三台机床上加工,每个产品必须首先在机床1上加工,然后依次在机床2,3上加工。
在每台机床上加工三个产品的顺序应保持一样,假定用tij表示在第j机床上加工第i个产品的时间,问应如何安排,使三个产
品总的加工周期为最短。
试建立这个问题的数学模型。
解:
用xij表示第i中产品在j机床上开始加工的时刻,则问题的数学模型可表示为:
minzmaxx13t13,x23t23,x33t33
xij
tij
ti,j1
(i
1,2
3;j
1,2)加工顺序约束
xij
tij
xi1,j
Mi
xi
1,j
ti1,
j
xij
M
(1
i)
互斥性约束
i
1,2;
j
1,2,3;
0或1
xij
0
5.11某电子系统由三种元件组成,为使系统正常运转,每个元件都必须工作良好。
如一个或多个元件安装几个备用件将提高系统的可靠性。
已知系统运转可靠性为各元件可靠性的乘积,而每一元件的可靠性则是备用件数量的函数,具体数值见表5-5。
表5-5
备用件数
元件可靠性
1
2
3
0
0.5
0.6
0.7
1
0.6
0.75
0.9
2
0.7
0.95
1.0
3
0.8
1.0
1.0
4
0.9
1.0
1.0
5
1.0
1.0
1.0
又三种元件分别的价格和重量如表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.5y1
0.6y
(0.6y7
0.75y
2
0.7y3
0.8y4
0.9y5
y6)
8
0.95y9
y10)
(0.7y11
0.9y12
y13)
20x1
30x2
40x3150
2x1
4x2
6x3
20
6
yi
1
i1
10
yi
1
i
7
13
yi
1
i
11
xj
0(j
1,2,3)
yi
或(
i
1,...,13)
01
5.12用你认为合适的方法求解下述问题:
maxzx12x2
5x3
x1
10x2
3x3
15
2x1
x2
x3
10
x1,x2
x3
0
解:
将问题改写为
maxzx12x25x3
x1
10x2
3x3
15
My
x1
10x2
3x3
15
(1y)M
2x1
x
2
x310
xj
0(
j
1,2,3),y
0或1
求解得x1=0,x2=0,x3=10,y=1,z=50
5.13下述线性规划问题
maxz20x1
10x2
10x3
2x1
20x2
4x3
15
6x1
20x2
4x3
20
x1,
x2,x3
0,且取整数值
说明能否用先求解相应的线性规划问题然后凑整的办法来求得该整数规划的一个可行解。
解:
当不考虑整数约束,求解相应线性规划得最优解为x1=10/3,x2=x3=0。
用凑整法时令x1=3,x2=x3=0,其中第2个约束无法满足,故不可行。
5.14某市为方便学生上学,拟在新建的居民小区增设若干所小学。
已知备选校址代号及其能覆盖的居民小区编号如表5-7所示,问为覆盖所有小区至少应建多少所小学,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划 习题