第五章 整数规划
一、学习目的与要求
1、熟悉分支定界法和割平面法的原理及其应用； 2、掌握求解0——1规划问题的隐枚举法； 3、掌握求解指派问题的匈牙利法。 二、课时 9学时
第一节整数规划的数学模型及解的特点
整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。
松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。 一、整数线性规划数学模型的一般形式
nmax(或min)z??cj?1jxj?n??aijxj?(或?,或?)bi(i?1,2,?,m)
?j?1?s.t.?xj?0(j?1,2,?,n)??x1,x2,?,xn中部分或全部取整数??整数线性规划问题可以分为以下几种类型
1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。
2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3、0—1型整数线性规划(zero—one integer liner programming)：指决策变量只能取值0或1的整数线性规划。 二、整数规划的例子
例1 某服务部门各时段（每2h为一时段）需要服务员的人数见下表。按规定，服务员连续工作8h（即四个时段为一班）。现在求安排服务员的工作时间，使服务部门服务员总数最少？
1 2 3 4 5 6 7 8 时段 10 8 9 11 13 8 5 3 服务员最少数目 解：设在第j时段开始上班的服务员的人数为xj。问题的数学模式略。
例2 现有资金总额为B。可选择投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j=1，2，?，
1
n）。此外由于种种原因，有三个附加条件：若选择项目1，就必须选择项目2。反这则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7恰好选择两个。应当怎样选择投资项目，才能使预期收益最大？
解：每一个投资项目都有被选择和不被选择两种可能，为此令
?1xj???0项目j投资项目j不投资n(j?1,2,?,n)
这样，问题可表示为
maxz??cj?1jxj
?n??ajxj?B?j?1?x2?x1?s.t.?x3?x4?1 ?x?x?x?267?5?xj?0或1(j?1,2,?,n)??
例3 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地所需求量、各厂至各需求地的单位物资运费cij（i,j=1,2, ?,4）见下表。
生产能力 B1 B2 B3 B4 （kt/年） A1 A2 A3 A4 需求量（kt/年） 2 8 7 4 350 9 3 6 5 400 3 5 1 2 300 4 7 2 5 150 400 600 200 200 工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3
还是A4，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少？
解：这是全个物资运输问题，其特点是事先不能确定应该建A3或A4中哪一个，因而不知道新厂投产后的实际生产费用。引入0—1变量
若建工厂A3?1y??
若建工厂A4?0再设cij为由Ai运往Bj的物资数量（i,j=1,2, ?,4），单位是千吨，z表示总费用。 问题数学模型为
44ijminz???cj?1i?1xij?y1200?(1?y)1400
2
?4???i?1?4???i?1?4???i?1?4???i?14??s.t.???i?1?4???i?1?4???i?1?4???i?1?x?ij??xi1?350xi2?400xi3?300xi4?150x1j?400x2j?600x3j?200yx4j?200(1?y)?0(i,j?1,2,3,4),y?0或1
三、整数规划的解的特点
相对于松弛问题而言，二者之间既有联系，又有本质的区别 (1)整数规划问题的可行域是其松弛问题的一个子集 (2)整数规划问题的可行解一定是其松弛问题的可行解
(3)一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，更不是最优解
(4)对松弛问题的最优解中非整数变量简单的取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解
(5)求解还是要先求松弛问题的最优解，然后用分支定界法或割平面法。
例4 考虑下面的整数规划问题：
maxz?x1?4x2??2x1?3x2?3?s.t.?x1?2x2?8??x1,x2?0且取整数
x2 6 0 9 12
x1
3
运筹学课件第五章整数规划
