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

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

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

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

一、整数线性规划数学模型的一般形式

max(或min)Z??cjxjj?1n

s.t?axijj?1nj?(?,?)bij?1,2,...mxj?0i?1,2,...,nx1,x2,...xn中部分或全部取整数

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

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

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

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

1 解整数规划问题

maxz?3x1?x2??3x1?2x2?3??5x1?4x2?10?2x1?x2?5??x1,x2?0且为整数??

maxz?x1?x2??x9511?x2??1414???2x11?x2? ?3?x1,x2?0且为整数

0—1型整数规划

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

变量xi称为0—1变量，或称为二进制变量。

0—1型整数规划中0—1变量作为逻辑变量(logical variable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。

?1如果决策i为是或有xi?? 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?20x1?15x2?18x3?14x4?8x5?4x6?10x7?5x1?5x2?2x3?6x4?12x5?2x6?4x7?25??xi?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?x1?x2?x3?x4?x5?x6?x1?x?1????????

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

二、特殊约束的处理

1.矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只能两者取一或，例如下面两个约束

?x2?x2x3x3x2xi?1或0?x4?x4x4?x5?x5?x5?x6?x6?x6?1?1?1?1?1?1

f(x)?3f(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)?af(x)??a

约束同向处理，改为

?f(x)??a?f(x)??a?Myf(x)??a引入0—1变量后，f(x)??a?M(1?y)

2.多中选一的约束

模型希望在下列几个约束中，只能有一个约束有效：

fi(x)?0(i?1,2,...,n)(1)

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

fi(x)?M(1?yi)则上式可改写为：

(i?1,2,...,n)(2)(3)y1?y2?...?yn?1yi=0时，（2）自然满足，此时约束不起作用 yi=1时，约束起作用。

而和式保证了在0—1整数变量中有一个且也只有一个取值1，其余取0值。

若希望有k个约束有效，只需将(3)改为

y1?y2?...?yn?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

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

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

则对于第1个小区：

x1?x2?x3?1

对于第2个小区：x2?x4?1 对于第3个小区：x3?x5?1 对于第4个小区：x4?x6?1 对于第5个小区：x1?x2?x3?x4?1 对于第6个小区：x5?x6?1 对于第7个小区：x1?1 Min z =解得：

例2 有两个相互排斥的约束条件

5x1?4x2?24 或 7x1?3x2?45。

?Xj?16j

TX*??1,0,0,1,1,0? Z=3

*

为了统一在一个问题中，引入0?1变量y，则上述约束条件可改写为：

?5x1?4x2?24?yM??7x1?3x2?45?(1?y)M?y?0或1 ?

其中M是充分大的数。 例3 约束条件

x1?0 或 500?x1?800

?500y?x1?800y可改写为?

?y?0或1

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

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

xjcjkj表示采用第j种方式时的产量；

表示采用第j种方式时每件产品的变动成本； 表示采用第j种方式时的固定成本。

为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为

??kj?cjxj,当xj?0Pj??0, 当xj?0 ?? j?1,2,3.

在构成目标函数时，为了统一在一个问题中讨论，现引入0?1变量yj，令

??1,当采用第j种生产方式，即xj?0时，yj??0,当不采用第j种生产方式，即xj?0时.??

于是目标函数

minz?(ky?cx)?(ky?cx)?(ky?cx)111122223333 （3）

（3）式这个规定可表为下述3个线性约束条件：

yj??xj?yjM,j?1,2,3 （4） 其中?是一个充分小的正常数，M是个充分大的正常数。（4）式说明，当xj?0时

yj必须为1；当xj?0时只有yj为0时才有意义，所以（4）式完全可以代替（3）

式。

例8 求解下列指派问题，已知指派矩阵为

?38?87??64??84??910210292267393?7??5??5?10??

，求最小指派问题。

数学模型为：

Min z=3*x11+8*x12+2*x13+10*x14+3*x15

+8*x21+7*x22+…+ ……

??aj?1i?155ij*xij

+9*x51+10*x52+6*x53+9*x54+10*x55 X11+x12+x13+x14+x15=1

……

?xj?15ij?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:

row/1..5/: ; col/1..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的产量为x1，且

?0，其他?0，其他y11??y12???1，0?x1?40 ?1，40?x1?100 ?0，其他?0，其他y14??y13???1，x1?150 ?1，100?x1?150

设产品B的产量为x2，且：

?0，其他?0，其他y21??y22???1，0?x2?50 ?1，50?x2?100

?0，其他y23???1，x2?100

设产品C产量为x3，且：

?0，其他y31???1，0?x3?100?0，其他y32???1，x3?100

设总利润为：y

Maxy??12?(10y11?9y12?8y13?7y14)?x1??7?(6y21?4y22?3y23)?x2??6?(5y31?4y32)?x3?x1?x2?x3?100,10x1?42x2?5x3?700,3x1?2x2?x3?400??y11?y12?y13?y14?1,y21?y22?y23?1,y31?y32?1??0?x1y11?40,40?x1y12?100,100?x1y13?150s..t?xy?150,0?x2y21?50,50?x2y22?100,?114?x3y23?100,0?x3y31?100,x3y32?100,xj?0(j?1,2,3)???y1j?0或1(j?1,2,3)，y2j?0或1(j?1,2,3)，y3j?0或1(j?1,2)

2 某钻井队要从以下10个可供选择的井位中确定5个钻井采油，目的是使总的钻井费用最小。若10个钻井位代号为S1,S2,,S10,相应的钻控费用为

c1,c2,,c10，并且井位的选择要满足下列条件：

若选择S1和S7，或选择钻探S8：

选择了S3 或S4，就不能选择 S5，反过来也是一样。

在S2,S6,S9,S10中最多只能选择两个。试建立这个问题的整数规划模型。

设xj?0或1，其中xj?0代表Sj点未入选，xj?1代表Sj点入选； 于是可构造如下数学模型：

maxz??Cjxjj?110

x1?x8?1 x7?x8?1 x3?x5?1 x4?x5?1x5?x6?x7?x8?2

10?xj?1j?5

xj?0or1?j?1,2,10?

考虑下列数学模型

minZ?f(x1)?g(x2)

其中

?10?6x1,若x1?0?15?10x2,若x2?0f(x1)??,g(x2)??若x1?0若x2?0 ?0,?0,满足约束条件 （1）x1≥8或x2≥6

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