疟疾知识-国庆英语手抄报

整数规划的数学模型及解的特点

整数规划IP (integer pr ogramming)：在许多规划问题中，如果要求一部分
或全部决策变量必须取整数。例如，所求的 解是机器的台数、人数、车辆船只
数等，这样的规划问题称为整数规划，简记IP。

松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件
构成的规划问题称为该整数规划问题的松弛问题。

若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer
linear programming)。

一、整数线性规划数学模型的一般形式
max(或min)Z

c
j
x
j
j1
n

s.t

ax
ij
j1
n
j
(,)b
i
j1,2,...m
x
j
0
i1,2,...,n
x
1
,x
2
,...x
n
中部分或全部取整数


整数线性规划问题可以分为以下几种类型

1、纯整数线性规划(pure integer linear programming)：指全部决策变量都
必须取整数值的整数线 性规划。有时，也称为全整数规划。

2、混合整数线性规划(mixed integer liner programming)：指决策变量中有
一部分必须取整数值，另一 部分可以不取整数值的整数线性规划。

3、0—1型整数线性规划(zero—one integer liner programming)：指决策变
量只能取值0或1的整数线性规划。

1 解整数规划问题
maxz3x
1
x
2


3 x
1
2x
2
3


5x
1
 4x
2
10

2x
1
x
2
5


x
1
,x
2
0且为整数


maxzx
1
x
2


x
95 1
1
x
2


1414


 2x
1
1
x
2


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

0—1型整数规划

0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值 0或1，这时的

变量xi称为0—1变量，或称为二进制变量。
0—1型整数规划中0—1变量作为逻辑变量(logical variable)，常被用来表
示系统是否处于某一特定状态，或者决策时是否取某个方案。

1如果决策i为是或有
x
i



0如果决策i为否或无

一、0—1型整数规划的典型应用问题
例1：背包 问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳
索、帐篷、照相器材、通信器材等。 每种物品的重量和重要性系数如表所示。
设登山队员可携带的最大重量为25kg,试选择该队员所应携 带的物品。

序号
物品
重量Kg
1 2 3 4 5 6 7
食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备
5 5
15
2
18
6
14
12
8
2
4
4
10 重要性系数 20

解：引入0—1变量xi, xi=1表示应携带物品i，,xi=0表示不应携带物品i

naxz20x
1
15x
2
18x
3
14x
4
8x
5
4x
6
10x
7

5x
1
5x< br>2
2x
3
6x
4
12x
5
2x6
4x
7
25


x
i
0或1 ,i1,2,...,7

整数规划问题，解得： 上述问题就是一个标准的
X*=(1,1,1,1,0,1,1)’ Z*=81

0-1

例2：集合覆盖和布点问题
某市消防队布点问题。该市共有6 个区，每个区都可以建消防站，市政府希望
设置的消防站最少，但必须满足在城市任何地区发生火警时， 消防车要在15min
内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。

地区1
地区2
地区3
地区4
地区5
地区6
地区1
0
10
16
28
27
20
地区2
10
0
24
32
17
10
地区3
16
24
0
12
27
21
地区4
28
32
12
0
15
25
地区5
27
17
27
15
0
14
地区6
20
10
21
25
14
0
解：引入0—1变量xi, xi=1表示在该区设消防站，,xi=0表示不设
minzx
1
x
2
x
3
x
4
x
5
x
6
< br>x
1

x

1



< br>




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

二、特殊约束的处理
1.矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只能两者取一或，
例如下面两个约束 < br>x
2
x
2
x
3
x
3
x
2
x
i
1或0
x
4
x
4
x
4
x
5
x
5
x
5
x
6
 x
6
x
6
1
1
1
1
1
1

f(x)3
f(x)0
(1)
(2)

，
3f(x)0(3)
先不等式同向处理，原式可化为：
f(x)0(4)
再引入一个0－1变量y, 及一个很大的正数M，
3f(x)My(5)
f(x)M(1y)(6)


y=0时，(5)与(1)相同，(6)自然满足，实际上不起作用
y=1时，(6)与(2)相同，(5)自然满足，实际上起作用

对于形似
f(x)a(a0)
，可以用以下一对约束代替
f(x)a
f(x)a

约束同向处理，改为
f(x) af(x)aMy
f(x)a
引入0—1变量后，
f(x)aM (1y)


2.多中选一的约束

模型希望在下列几个约束中，只能有一个约束有效：
f
i
(x)0(i1,2,...,n)(1)

引入n个0－1整数变量yi, i=1,2,…,n.

f
i
(x)M(1y
i
)
则上式可改写为：
(i1,2,...,n) (2)
(3)y
1
y
2
...y
n
1yi=0时，（2）自然满足，此时约束不起作用
yi=1时，约束起作用。
而和式保证了在0—1整数变量中有一个且也只有一个取值1，其余取0值。

若希望有k个约束有效，只需将(3)改为
y
1
y
2
...y
n
k


3、某市为方便学生，拟在新建的7个居民小区增设若干所学校。已知各备选校
址代 号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应
建多少所学校？对应的校址代号 是哪些？
表1
备选校址 A B C D E F
小区编号 1，5，7 1，2，5 1，3，5 2，4，5 3，6 4，6

解：对每一个学校定义一个变量
x
j

1，当某居民小区可由第j个学校负责

x
j
＝
0，当某居民小区不可由第j个学校负责

则对于第1个小区：
x
1< br>x
2
x
3
1

对于第2个小区：
x
2
x
4
1

对于第3个小区：
x
3
x
5
1

对于第4个小区：
x
4
x
6
1

对于 第5个小区：
x
1
x
2
x
3
x
4< br>1

对于第6个小区：
x
5
x
6
1

对于第7个小区：
x
1
1

Min z =
解得：


例2 有两个相互排斥的约束条件
5x
1
4x
2
24
或
7x
1
3x
2
45
。

X
j1
6
j

T
X
*


1,0,0,1,1,0


Z
=3
*
为了统一在一个问题中，引入
01
变量
y
，则上述约束条件可改写为：

5x
1
4x
224yM


7x
1
3x
2
45( 1y)M

y0或1



其中
M
是充分大的数。
例3 约束条件
x
1
0
或
500x
1
800


500yx
1
800y
可改写为



y0
或
1


3.1.3 关于固定费用的问题（Fixed Cost Problem）

在讨论线性规划时， 有些问题是要求使成本为最小。那时总设固定成本为常数，
并在线性规划的模型中不必明显列出。但有些 固定费用（固定成本）的问题不
能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。
例5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生
产方式投资高 （选购自动化程度高的设备），由于产量大，因而分配到每件产品
的变动成本就降低；反之，如选定的生 产方式投资低，将来分配到每件产品的
变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择 ，令
x
j
c
j
k
j
表示采用第
j
种方式时的产量；
表示采用第
j
种方式时每件产品的变动成本；
表示采用第
j
种方式时的固定成本。
为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分
别为


k
j
c
j
x
j
,
当
x
j
0
P
j


0,
当
x
j
0



j1,2,3
.
在构成目标函数时，为了统一在一个问题中讨论，现引入
01
变量
y
j
，令


1,
当采用第j种生产方式，即x
j
0时，
y
j


0,
当不采用第j种生产方式，即x
j
0时
.



于是目标函数
minz(kycx)(kycx)(kycx)
3
（3）
（3）式这个规定可表为下述3个线性约束条件：

y
j

x
j
y
j
M,j1,2,3
（4）
其中

是一个充分小的正常数，
M
是个充分大的正常数。（ 4）式说明，当
x
j
0
时

y
j
必 须为1；当
x
j
0
时只有
y
j
为0时才有意义， 所以（4）式完全可以代替（3）
式。
例8 求解下列指派问题，已知指派矩阵为

38

87


64


8 4


910
210
29
2
2
6
7
3
9
3

7


5


5

10




，求最小指派问题。
数学模型为：
Min z=3*x11+8*x12+2*x13+10*x14+3*x15
+8*x21+7*x22+…+
……

a
j1i1
55
ij
*x
ij

+9*x51+10*x52+6*x53+9*x54+10*x55
X11+x12+x13+x14+x15=1
……

x
j1
5
ij
1i1..5

X51+x52+x53+x54+x55=1
X11+x21+x31+x41+x51=1
…..
X15+x25+x35+x45+x55=1
Xi,j=0,1

Lingo程序为：
model:

sets:
row1..5:
col1..5:
link(row,col):a,x;
endsets

data:
a=3 8 2 10 3
8 7 2 9 7
6 4 2 7 5
8 4 2 3 5
9 10 6 9 10;
enddata

min = @sum(link(i,j):a(i,j)*x(i,j));
@for(row(i):@sum(col(j):x(i,j))=1);
@for(col(j):@sum(row(i)|i#le#2:x(i,j))+
@sum(row(i)|i#ge#3:x(i,j))=1);

end

篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高和擅长位置见
下表：

出现阵容应
条件：
队员
1
2
3
4
5
6
7
8
身高（米）
1.92
1.90
1.88
1.86
1.85
1.83
1.80
1.78
擅长位置
中锋
中锋
前锋
前锋
前锋
后卫
后卫
后卫
满足以下
中锋只能有一个上场；x1+x2=1
至少有一名后卫；x6+x7+x8>=1
如1号和4号上场，则6号不出场； y=x1+x4 ,if y=2 x6=0
X1 <= x6
2号和6号至少保留一个不出场。X2+x6 <=1
应当选择哪5名队员上场，才能使出场队员平均身高最高？

公司生产 A、B、C三种产品，售价分别为12元、7元和6元。生产每单位A需
要1小时技术服务、10小时直 接劳动、3千克材料；生产每单位B需要2小时
技术服务、4小时直接劳动、2千克材料；生产每单位C 需要1小时技术服务、
5小时直接劳动、1千克材料；现在最多能提供100小时技术服务、700小时 直
接劳动、400千克材料；生产成本是生产量的非线性函数，如下所示：
产品A 产品B 产品C
单位成本
产量
（元）
0~40
40~100
100~150
150以上
10
9
8
7
产量 单位成本
（元）
产量 单位成本
（元）
0~50
5~100
6
4
0~100 5
100以上 4
100以上 3

要求建立一个总利润最大的生产计划数学模型。

设产品A的产量为
x
1
，且

0，其他

0，其他
y
11


y
12



1，0x
1
40


1，40x
1
100


0，其他

0，其他
y
14


y
13



1，x
1
150


1，100x
1
150

设产品B的产量为
x
2
，且：

0，其他
0，其他
y
21


y
22


1，0x
2
50


1，50x
2
100


0 ，其他
y
23



1，x
2
100< br>
设产品C产量为
x
3
，且：


0，其 他
y
31



1，0x
3
100< br>
0，其他
y
32



1，x
3
100

设总利润为：y
Maxy

12(10y
11
9y
12
8y13
7y
14
)

x
1


7(6y
21
4y
22
3y
23
)
x
2


6(5y
31
4y
32
)

x
3

x
1
x
2
x3
100,10x
1
42x
2
5x
3
 700,3x
1
2x
2
x
3
400


y
11
y
12
y
13
y
14< br>1,y
21
y
22
y
23
1,y
3 1
y
32
1


0x
1
y
11
40,40x
1
y
12
100,100x
1< br>y
13
150
s..t

xy150,0x
2
y
21
50,50x
2
y
22
100,
114

x
3
y
23
100,0x3
y
31
100,x
3
y
32
100,x
j
0(j1,2,3)



y
1j
0或1(j1,2,3)，y
2j
0或1(j1,2,3)，y
3j
0或1(j1,2)



2 某钻井队要从以下10个可供选择的井 位中确定5个钻井采油，目的是使总
的钻井费用最小。若10个钻井位代号为
S
1,S
2
,,S
10
,相应的钻控费用为
c
1
, c
2
,,c
10
，并且井位的选择要满足下列条件：
若选择
S
1
和
S
7
，或选择钻探
S
8
：
选择了
S
3
或
S
4
，就不能选择
S
5
，反过来也是一样。
在
S
2
,S
6
,S
9
,S
10
中最多只能选择两个。试建立这个问题的整数规划模 型。


设
x
j
0
或
1
，其 中
x
j
0
代表
S
j
点未入选，
x
j
1
代表
S
j
点入选；
于是可构造如下数学模型：

maxz

C
j
x
j
j1
10

x
1
x
8
1
x
7
x
8
1
x
3
x
5
1
x
4
x
5
1
x
5
x
6
x
7
x
8
 2

10

x
j1
j
5


x
j
0or1

j1,2,10


考虑下列数学模型
minZf(x
1
)g(x
2
)

其中 
106x
1
,若x
1
0

1510x
2
,若x
2
0
f(x
1
)

,g(x
2
)

若x
1
0若x
2
0


0,

0,
满足约束条件
（1）x1≥8或x2≥6
（3）x1+2x2≥20、2x1+x2≥20及x1+x2≥20 三个约束中至少一个满足
将此问题归结为混合整数规划的数学模型。