第五章整数规划
、学习目的与要求
1、 熟悉分支定界法和割平面法的原理及其应用; 2、 掌握求解0―― 1规划问题的隐枚举法； 3、 掌握求解指派问题的匈牙利法。
二、课时9学时
第一节整数规划的数学模型及解的特点
整数规划IP (integer programming):在许多规划问题中，如果要求一部分或全部决策变量必须取整数。
例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记
IP。
松弛问题(slack problem):不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整 数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划 (integer linear programming)。一、 整数线性规划数学模型的一般形式
n
max(或 min) z 八 c j xj
j a
\n
Z aij Xj <(或=,或 X)bi (i =1,2,…,m)
j =1
s.t.」Xj X0( j =1,2，…,n)
I
X-X2,…,xn中部分或全部取整数
整数线性规划问题可以分为以下几种类型 1、 纯整数线性规划(pure integer linear programming):指全部决策变量都必须取整数值的整数线性规划。
有时，也称为全整数规划。
2、 混合整数线性规划(mixed integer liner programming):指决策变量中有一部分必须取整数值，另一部分
可以不取整数值的整数线性规划。
3、 0—1型整数线性规划(zero— one integer liner programming)：指决策变量只能取值 0或1的整数线性规划。
二、 整数规划的例子
例1某服务部门各时段(每 2h为一时段)需要服务员的人数见下表。按规定，服务员连续工作 四个时段为一班)。现在求安排服务员的工作时间，使服务部门服务员总数最少？
时段 1 2 3 4 5 6 7 8 服务员最少数目 10 8「 9 11 P 13 8 5 3
解：设在第j时段开始上班的服务员的人数为
x。问题的数学模式略。
1
8h (即
例2现有资金总额为B。可选择投资项目有n个，项目j所需投资额和预期收益分别为 aj和Cj( j=1，2，,，
2
n）。此外由于种种原因，有三个附加条件：若选择项目 1就必须选择项目2。反这则不一定；第二，项
目3和项目4中至少选择一个；第三，项目 5、项目6和项目7恰好选择两个。应当怎样选择投资项目，才能 使预期收益最大？
解：每一个投资项目都有被选择和不被选择两种可能，为此令
项目j投资 (j =1,2, ,n)
项目j不投资
这样，问题可表示为
n
max z 八 cjXj
j 2
严n
Z a j Xj = B
j
三
X2 兰 Xi
S.t. X5 + X6 + X7 = 2 Xj =0或 1( j =1,2,…，n) 例3 工厂Ai和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有 A3和A4两个。这种物资的需求地有 Bi，B2, B3，B4四个。各工厂年生产能力、各地所需求量、各厂至各 需求地的单位物资运费 Cij（ i,j=i,2, , ,4）见下表。 生产能力 B1 B2 B3 B4 （kt/ 年） A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 需求量（kt/年） 350 400 300 150 工厂A3或A4开工后，每年的生产费用估计分别为 1200万元或1500万元。现要决定应该建设工厂 还是A4,才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少？ 解：这是全个物资运输问题，其特点是事先不能确定应该建 A3或A4中哪一个，因而不知道新厂投产 后的实际生产费用。引入 0— 1变量 y = < 1 若建工厂A3 0 若建工厂 A4 再设Cij为由Ai运往Bj的物资数量（i,j=1,2, , ,4），单位是千吨，z表示总费用。 问题数学模型为 4 4 min z - 、q 刍 y1200 （1 - y）1400 j i 3 A3
运筹学课件第五章整数规划
