3.3 整数规划数学模型
在某些线性规划模型中，变量取整数时才有意义。例如，不可分解产品的数目，如汽车、房屋、飞机等，或只能用整数来记数的对象。这样的线性规划称为整数线性规划，简称整数规划，记为IP。整数规划分为两类：一类为纯整数规划，记为PIP，它要求问题中的全部变量都取整数；另一类是混合整数规划，记之为MIP，它的某些变量只能取整数，而其他变量则为连续变量。整数规划的特殊情况是0-1规划，其变量只取0或者1。
例3.5 最佳组队问题
某班准备从5名游泳队员中选择4人组成接力队，参加学校的4×100m混合泳接力比赛。5名队员4种泳姿的百米成绩如下表所示，问应如何选拔队员组成接力队？
表3-11 运动员训练成绩表
问题分析
从5名队员中选出4人组成接力队，每人一种泳姿，且4人的泳姿各不相同，使接力队的成绩最好。容易想到的一个办法是穷举法，组成接力队的方案共有5! =120种，逐一计算并做比较，即可找到最优方案。显然，这不是解决这类问题的好办法，随着问题规模的变大，穷举法的计算量将是无法接受的。可以用0-1变量表示一个队员是否入选接力队，从而建立这个问题的0-1规划模型，借助现成的数学软件求解。
模型设计
记甲、乙、丙、丁、戊分别为队员i=1,2,3,4,5；记蝶泳、仰泳、蛙泳、自由泳分别为泳姿j=1,2,3,4。记队员i的第j 种泳姿的百米最好成绩为cij（s），即：
表3-12 运动员训练成绩表
引入0-1变量xij，若选择队员i参加泳姿j 的比赛，记xij=1，否则记xij=0。根据组成接力队的要求，xij应该满足两个约束条件：
● 每人最多只能入选4种泳姿之一；
● 每种泳姿必须有1人而且只能有1人入选；
当队员i入选泳姿j 时，cijxij表示他（她）的成绩，否则cijxij=0。于是接力队的成绩可
以表示为，这就是该问题的目标函数。
综上，这个问题的0-1规划模型可写作：
程序设计
LINDO程序的源代码如下：
Min66.8x11+75.6x12+87x13+58.6x14+57.2x21+66x22+66.4x23+53x24+78x31+
67.8x32+84.6x33+59.4x34+70x41 +74.2x42+69.6x43 +57.2x44+67.4x51 +71x52+
83.8x53+62.4x54
s.t.x1 1+x1 2+x1 3+x1 4＜=1 x2 1+x22+x23+x24＜=1 x3 1+x32+x33+x34＜=1
x41+x42+x43+x44＜=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1
x13+x23+x33+x43=1 x14+x24+x34+x44=1
end
int 2 0
最后一行表示20个决策变量全部为0-1变量。
Global optimal solution found.
Objective value: 253.2000
Objective bound: 253.2000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 0
Model Class: PILP
Total variables: 20
Nonlinear variables: 0
Integer variables: 20
Total constraints: 9
Nonl inear constraints: 0
Total nonzeros: 52
Nonlinear nonzeros: 0
Variable Value Reduced Cost
X11 0.000000 66.80000
X12 0.000000 75.60000
X13 0.000000 87.00000
X14 1.000000 58.60000
X21 1.000000 57.20000
X22 0.000000 66.00000
X23 0.000000 66.40000
X24 0.000000 53.00000
X31 0.000000 78.00000
X32 1.000000 67.80000
X33 0.000000 84.60000
X34 0.000000 59.40000
X41 0.000000 70.00000
X42 0.000000 74.20000
X43 1.000000 69.60000
X44 0.000000 57.20000
X51 0.000000 67.40000
X52 0.000000 71.00000
X53 0.000000 83.80000
X54 0.000000 62.40000
求解得到结果为：x14=x21=x32=x43=1，其他变量为0，成绩为253.2″。即当选派甲、乙、丙、丁4人组成接力队，分别参加自由泳、蝶泳、仰泳、蛙泳的比赛。
例3.6 体操队最佳阵容排序问题
有一场由四个项目（高低杠、平衡木、跳马、自由体操）组成的女子体操团体赛，赛程规定：每个队至多允许10名运动员参赛，每一个项目可以有6名选手参加。每个选手参赛的成绩评分从高到低依次为：10,9.9,9.8, …,0.1,0。每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者。此外，还规定每个运动员只能参加全能比赛（四项全参加）与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三项单项。每个队应有4人参加全能比赛，其余运动员参加单项比赛。
现某代表队的教练已经对其所带领的10名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩稳定在4个得分点上（见表3-13），她们得到这些成绩的相应概率也由统计得出（见表中第二个数据。如：8.4和0.15表示取得8.4分的概率为0.15）。试解答以下问题：
表3-13 运动员各项目得分及概率分布表
1．每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高。
2．若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计为不少于236.2分，该队为了夺冠应排出怎样的阵容？以该阵容出战，其夺冠前景如何？得分前景（即期望值）又如何？
模型设计
通过对题目的分析可知：所有运动员的所有项目得分总和即为该团体总分，记为P。引入0-1变量xij表示运动员i是否入选项目j。bij表示运动员i在项目j 的最低得分。依题意，当运动员i入选项目j 时，bijxij表示她在该项目得分最低的分数，否则bijxij=0。
于是，队员在各单项得分按得分最低的分值估算时，该队团体总分可表示为：
这就是在这种最悲观情况下该问题的目标函数。下面来分析约束条件：
由“每个队应有4人参加全能比赛”，即每个队参加全能比赛的人有且仅有4名，得：
由每个项目可以有6名选手参加，每个项目的参赛选手不能超过6名，得：
因此，在每个队员成绩确定的情况下，排出该队的一个出场阵容，使其团体总分尽可能高。可建立如下0-1规划模型：
最悲观估计理解为参赛选手在各单项得分最差的情况。求解所得结果为：
表3-14 悲观估计下运动员排布表
程序设计：
sets：
ry/1..1 0/；
xm/1..4/；
fa（ry, xm）:b, x；
endsets
data：
b=8.4 8.4 9.1 8.7
9.3 8.4 8.4 8.9
8.4 8.1 8.4 9.5
8.1 8.7 9 8.4
8.4 9 8.3 9.4
9.4 8.7 8.5 8.4
9.5 8.4 8.3 8.4
8.4 8.8 8.7 8.2
8.4 8.4 8.4 9.3
9 8.1 8.2 9.1；
enddata
max=@sum（fa∶b*x）；
@for（xm（j）:@sum（ry（i）:x（i, j））＜=6）；
@for（fa:@bin（x））；
@sum（ry（i）:@prod（xm（j）:x（i, j）））=4；
通过对于问题的分析，可知团队总分呈现类似正态分布。优化模型的目标函数调整如下：
将非标准正态分布转化为标准正态分布：
其中，eij表示运动员i入选项目j 时的平均得分，dij表示运动员i 入选项目j 时的得分方差。
Prob{μ≥μ0}=1-ϕ（μ0）
为了使得Prob{μ≥μ0}获得最大值，可以转化为ϕ（μ0）的最小值。可以建立如下的优化数学模型：
