2006/3
--第 4章 整数规划 --
--1--
2006/3
--第 4章 整数规划 --
--2--
Integer Programming 整数规划
All Integer Programming 全整数规划
Mixed Programming 混合整数规划
第四章 整数规划
2006/3
--第 4章 整数规划 --
--3--
4.1 一般整数规划问题的特点及分枝定界法
一、引例
某厂拟用集装箱托运甲、乙两种货物，每箱的体
积、重量、可获利润及托运时所受的限制如下表所示，
问如何托运能使总收益最大？
货物 体积 (米 3/箱 ) 重量 (吨 /箱 ) 利润 (千元 /箱 )
甲
乙
2 2 3
3 1 2
14 米 3 9 吨托运限制
2006/3
--第 4章 整数规划 --
--4--
建模：
解：设 托运甲货物 x1箱，乙货物 x2箱
Max z=3 x1 +2 x2
st, 2 x1+3 x2?14
2 x1 + x2?9
x1?0,x2?0,且为整数
2006/3
--第 4章 整数规划 --
--5--
2 4 6
2
4
(3.25,2.5)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
2006/3
--第 4章 整数规划 --
--6--
2 4 6
2
4
(3.5,2)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(2.5,3)
2006/3
--第 4章 整数规划 --
--7--
2 4 6
2
4
(4,1)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(2.5,3)
(3,2)
2006/3
--第 4章 整数规划 --
--8--
分枝定界法,
L0,z0=14.75
x1=3.25,x2=2.5
L1,z1=14.5 L2,z2=13.5
L3,z3=13 L4,z4=14
x1=3.5,x2=2 x1=2.5,x2=3
x1=3,x2=2 x1=4,x2=1
?
2006/3
--第 4章 整数规划 --
--9--
LINDO软件及 EXCEL求解：
LINDO程序软件：同求解 LP模型时的输入及编辑修改过
程,在使用‘ GO ’命令求解之前，对整数变量给予说明。
命令格式,GIN <变量名 >。
EXCEL求解：
2006/3
--第 4章 整数规划 --
--10--
4.2 0-1规划问题及模型
一,0-1规划问题的概念
? 在整数规划问题中，若变量取值为 0或者 1，则为 0-1
规划问题。
? 0-1变量通常用来表示逻辑性选择的决策。
2006/3
--第 4章 整数规划 --
--11--
二,0-1变量的应用
例 1：某油田在 10个有油气构造处要选择若干个钻探
采油，设第 j个构造开采时需投资 aj元，投产后预计年收
益为 cj元，若该油田投资的总限额为 b元，问：应选择哪
几个构造开采最为有利？
设 xj= 10 --- 选择开采第 j个构造---不选择开采第 j个构造
max z=Σcjxj
j=1
10
∑ajxj? b
xj＝ 0或 1 (j=1,2,---,10)
j=1
10
-----年总收益
----投资额限制
1、表示选择性决策
2006/3
--第 4章 整数规划 --
--12--
2,表示选择性约束
例 2：上述例题中，如果在开采中需用电力，解决的方案或由电网
供电或由自备的柴油机发电。已知第 j个构造开采时每天耗电量为 dj度，
电网每天供电量限制为 f 度。当使用自备柴油机发电时，每度电平均耗
油 0.3公斤，而柴油供应量限额为每天 p公斤。试在模型中表示出该限制
条件。
采用电网供电,∑djxj? f
采用自备柴油机发电,∑0.3djxj? p
j=1
10
j=1
10
+(1－ y1)M
+(1－ y2)M
y1+y2=1
y1,y2 =0或 1
M-----非常大的正数
2006/3
--第 4章 整数规划 --
--13--
3,表示条件性约束
例 3：若在开采时还需满足下述条件：
（ a）若开采 8号，则必须同时开采 6号；
（ b）若开采 5号，则不许开采 3号；
（ c） 2 号和 4号至少开采一个；
（ d） 8 号与 7号必须同时开采；
（ e） 1号,4号,6号,9号开采时不能超过两个，
试表示上述约束条件。
2006/3
--第 4章 整数规划 --
--14--
（ a）当 x8=1 x6=1,x6≠0
当 x8=0 x6=1,x6=0
∴ x8 ? x6
（ b）当 x5 =1 x3=0,x3 ≠1
当 x5 =0 x3=0,x3 =1
∴ x5 + x3 ? 1
（ c） x2 + x4 ? 1
（ d） x8 = x7
（ e） x1 + x4 + x6 + x9 ? 2
2006/3
--第 4章 整数规划 --
--15--
4,两组条件满足其中一组
若 x1? 4，则 x2?1，否则 (x1?4)，则 x2? 3。
设 yi= 1
0
第 i 组条件起作用
第 i 组条件不起作用 则i=1,2
x1? 4＋ (1-y1) M
x2? 1－ (1-y1) M
M—— 充分大正数x
1? 4－ (1-y2) M
x2? 3＋ (1-y2) M
y1＋ y2=1
y1,y2=0或 1
2006/3
--第 4章 整数规划 --
--16--
5,分段函数线性表示
设有 f(xj)= Kj+cjxj 当 xj>0
0 当 xj=0，
将 min f (xj) 表示成
线性函数。
设 yj= 1
0
当 xj>0
当 xj=0
Min f(xj) = kjyj+cjxj
st,xj?yjM
xj?0,yj=0或 1
M— 非常大的正常数
则
f(xj) = kjyj+cjxj
xj?yjM
yj?xjM
xj?0,yj=0或 1
或为：
2006/3
--第 4章 整数规划 --
--17--
三、隐枚举法
步骤：
① 化标准形 (隐枚举法 ),1) 目标函数极小化 2) 约束条件化成 ?
3) 使目标函数系数皆为非负,若 xj系数为负值,则令 xj=1-xj?
4) 使目标函数按变量系数由小 → 大顺序排列，约束条件变
量排列的顺序要与之对应。
② 令所有变量 xj=0，计算边界目标函数值 z，检查是否满足所有约
束条件，若满足，即为最优解；否则，分枝计算。
③ 分枝：按变量次序依次令各变量取,1”和,0”值，计算边界值，
然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。
④ 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。
(a) 对可行解，保留边界值最小的一枝 zmin，其余全剪掉；
(b) >zmin分枝，剪掉；
(c) 能判断出为无可行解的分枝，剪掉；
(d) 非上述情况，继续分枝。
2006/3
--第 4章 整数规划 --
--18--
例：求解下述 0-1规划问题：
Max z=8x1+2x2-4x3-7x4-5x5
st,3x1+3x2+x3+2x4+3x5 ?4
5x1+3x2- 2x3 - x4+ x5 ?4
xj=0或 1 (j=1,2,3,4,5)
1) 目标函数极小化, min z?=-8x1-2x2+4x3+7x4+5x5
① 化标准形：
2) 约束条件 ?,-3x1-3x2-x3-2x4-3x5?-4
-5x1-3x2+ 2x3 + x4- x5 ?-4
xj=0或 1 (j=1,2,3,4,5)
2006/3
--第 4章 整数规划 --
--19--
3) 使目标函数系数皆为正,令 x1=1-x1?, x2=1-x2?
min z?=-8+8 x1? -2+2 x2? +4x3+7x4+5x5
st,-3+3 x1? -3+3 x2? -x3-2x4-3x5 ?-4
-5+5 x1? -3+3 x2? + 2x3 + x4- x5 ?-4
x1?,x2?,xj=0或 1 (j=3,4,5)
4) 变量按顺序排列：
min z?= 2 x2? +4x3 +5x5 +7x4+8 x1? -10
st,3 x2? -x3 -3x5 -2x4 +3 x1? ?2
3 x2? + 2x3 - x5 + x4+5 x1? ?4
x1?,x2?,xj=0或 1 (j=3,4,5)
2006/3
--第 4章 整数规划 --
--20--
求解图示：
1
2
3
4
5
6
7
8
9
10
11
z?=-10
z? =-8
z?=-4
z?=-6
z?=-5
z?=-1
z?=1
z?=-5
z?=-3
z?=-6x
3=1
z?=-3
√
×
×
×
×
×
2006/3
--第 4章 整数规划 --
--21--
4.4 分配问题及匈牙利算法 (Assignment Problem)
一、问题的提出和数学模型
例：有一份说明书，要分别译
成英、日、德、俄四种文字，
交与甲、乙、丙、丁四个人去
完成，因各人专长不同，他们
完成翻译不同文字所需要的时
间（小时）如表所示。规定每
项工作只能交与其中的一个人
完成，每个人只能完成其中的
一项工作。
问：如何分配，能使所需的
总时间最少？
甲 乙 丙 丁工作 人
译英文
译日文
译德文
译俄文
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
2006/3
--第 4章 整数规划 --
--22--
建立模型：
设 xij=
1
0
译英文,x11+ x12 + x13 + x14 =1
译日文,x21+ x22 + x23 + x24 =1
译德文,x31+ 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
xij =0或 1 (i=1,2,3,4; j=1,2,3,4)
Min z=?? aijxij (aij---效率 )i=1j=14 4
若第 i项工作交与第 j个人完成
若第 i项工作不交与第 j个人完成
2006/3
--第 4章 整数规划 --
--23--
分配问题一般数学模型结构：
设有 m项工作要交与 m个人完成，其中第 i项工作交与
第 j个人完成时所需花费的时间为 aij。规定每项工作只能
交与其中的一个人完成，而每个人只能完成其中的一项
工作。问：如何分配，可使所需的总时间最少？
Min z=?? aijxij
st,?xij =1
?xij =1
i=1j=1
j=1
i=1
m m
m
m
xij =0或 1 (i=1,2,··,m; j=1,2,··,m)
(i=1,2,··,m)
(j=1,2,··,m)
2006/3
--第 4章 整数规划 --
--24--
二、匈牙利法：
基本思想：
4 (0) 5 6
5 4 (0) 5
7 6 3 (0)
(0) 5 6 2
克尼格定理 (konig),如果从效率矩阵 [aij]的每一
行元素中分别减去 (或加上 )一个常数 ui,从每列中分别减
去 (或加上 )一个常数 vj,得到一个新的效率矩阵 [bij],其
中 bij=aij-ui-vj,则以 [bij]为效率矩阵的最优解等价于以
[aij]为效率矩阵的最优解,
2006/3
--第 4章 整数规划 --
--25--
证明,
以 [aij]为效率矩阵的目标函数值,z0=?? aijxij
以 [bij]为效率矩阵的目标函数值,z?=??bijxij
m m
i=1j=1
i=1j=1
m m
∵ bij=aij-ui-vj
∴ z?=?? (aij-ui-vj)xij = ?? aijxij - ?? uixij - ?? vjxij
=z0- ?ui?xij -?vj?xij
m m m m m m
m m m m
=z0- ?ui- ?vj =z0-constant
m m
i=1j=1 i=1j=1 i=1j=1 i=1j=1
i=1 j=1 j=1 i=1
i=1 j=1
m m
2006/3
--第 4章 整数规划 --
--26--
三、步骤
⑴ 使每行、每列都出现 0元素
方法：每行减该行最小元素；
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
-2
-4
-11
-4
min
0 8 7 5
11 0 10 4
2 3 5 0
0 11 9 5
min -0 -0 -5 -0
0 8 2 5
11 0 5 4
2 3 0 0
0 11 4 5
-2
-2
-2
+2 +2
0 8 0 3
11 0 3 2
4 5 0 0
0 11 2 3
?每列减该列最小元素。
2006/3
--第 4章 整数规划 --
--27--
⑵ 寻找位于不同行不同列的 0元素
准则：
A）从第一行开始，若只有一个 0，则记（ 0），同时作直线覆盖该列
的元素。否则，转下行；
B）从第一列开始，若只有一个 0，则记（ 0），同时作直线覆盖该行
的元素。否则，转下列；
C）重复 A）,B），至再找不出这样的 0元素，转 D）
D）可能出现三种情况：
① 每行均有（ 0）元素，则在有（ 0）位置构成最优解中 xij=1；
② 多于两行和两列存在未被直线覆盖的 0元素，即存在 0元素的闭回路，
则沿回路顶点每间隔一个 0记（ ），同时作直线覆盖该列的元素；
③ 所有 0元素均有直线覆盖，但记（ 0）的个数 <m个，转⑶。
2006/3
--第 4章 整数规划 --
--28--
0 0
0 0
0 0
⑶ 迭代，寻找新的位于不同行不同列的 0元素
a）从未被直线覆盖的元素中找出一个最小的元素 amin；
b）对行，若无直线覆盖，则 - amin；
c）对列，若有直线覆盖，则 + amin；
⑷ 转⑵ 。
2006/3
--第 4章 整数规划 --
--29--
特殊问题处理：
1．人数与工作数不等的处理：
当人数 >工作数时：假想工作数，使得与人数能够匹
配,对应的效率设定为 0值。
当工作数 >人数时：假想人数，使得与工作数能够匹
配,对应的效率设定为 0值。
2．若目标函数为求 max z的处理：（如效益）
∵ max z= - min (-z ) = - min ( z?)
∴ 等价于求解 min z ? =∑∑(-aij)xij
i=1 j=1
m m
2006/3
--第 4章 整数规划 --
--30--
4 3 5 6 7
3 6 4 5 6
4 7 5 2 4
8 9 6 5 3
甲 乙 丙 丁 戊
A
B
C
D
E 0 0 0 0 0
A
B
C
D
E
甲 乙 丙 丁 戊
4 7 6 5
8 5 4 6
4 8 6 5
5 9 2 7
3 4 8 7
0
0
0
0
0
-2 -8 -7 -6
-5 -7 -6 -4
-3 -6 -4 -3
-4 -9 -5 -4
2006/3
--第 4章 整数规划 --
--31--
4.5 整数规划模型的应用
例 1,在未来四个月中，某制鞋厂必须按时完成下述合
同要求，第一个月 300双，第二个月 500双，第三个月 100
双，第四个月 100双。在一月初，工厂已有 50双鞋（以前
的存货）和 3名工人，每名工人的月薪为 1500元，每月可
工作 160小时（正常工作时间）。一名工人最多还可有 20
小时的加班工作时间（规定），在加班工作时，每小时需
付 25元的加班费用。制作一双鞋需耗费 4个工时和 5元的原
料费。在每月的开始，可以租用和解雇工人。每雇用一名
工人需支付 1600元的费用，每解雇一名工人需支付 2000元
的解雇费用。在每月末，要为留在仓库里未交货的每双鞋
支付 30元的保管维护费用。一个月生产的产品可用于满足
多个月的需求。试用 ILP方法确定最佳的生产计划和用工
政策。
2006/3
--第 4章 整数规划 --
--32--
问题分析：
需要解决的问题：
☆ 每月租进、解雇、使用的工人数
☆ 每月所需的加班时间
☆ 每月在正常时间、加班时间生产的鞋子的数量
☆ 每月开始和结束时库存鞋子的数量
☆ 费用明细：雇工费、解雇费、用工费、加班费、原料费
2006/3
--第 4章 整数规划 --
--33--
月初
人数
本月
雇用
本月
解雇
本月
使用
用工过程图示：
生产过程图示：
正常
生产
加班
生产
月初
库存
月末
库存
交货
数量
工人数
鞋子数
2006/3
--第 4章 整数规划 --
--34--
建模思路：
? 每月可用工人 ≥0
? 每月库存鞋子 ≥0
可用工人数 =月初数 +租进数 - 解雇数 =月末数
月末库存量 =月初库存 +正常生产 +加班生产 -交货量
? 目标函数 =总费用
=月薪 +雇用费 +解雇费 +加班费 +原料费 +库存费
2006/3
--第 4章 整数规划 --
--35--
例 2：
某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练
基地中的一个进行训练，从每个征兵中心运送一个新兵至某一个训练基
地的费用如表 1所示（单位：元） 。
每年在中心 1征招 1000名士兵，
中心 2征召 600名，中心 3征召 700
名。基地 1可训练 1000名，基地 2
可训练 800名，基地 3可训练 700名。
from
to Base1 Base2 Base3
Center1
Center2
Center3
240 200 300
300 400 220
300 400 250
新兵受训后，要送到海军部队。运送时可采用小船或大船两种工
具，共有 7条小船和 3条大船可供使用。若使用小船，则每条船要花费
5000元加上每海里 2元的费用；使用大船要花费 10000元加上每海里 3
元的费用。一条小船可运送 200人，沿途最多可经过 2个训练基地；一
条大船可运送 500人，最多可经过 3个训练基地。可能的航线如表 2中
所示。现问，应怎样决策，能使发生的总费用最少？
表 1
2006/3
--第 4章 整数规划 --
--36--
途径训练基地 航程（海里）航线
1
2
3
4
5
6
7
B— 1— B 370
B— 1— 2— B 515
B— 2— 3— B 665
B— 2— B 460
B— 3— B 600
B— 1— 3— B 640
B— 1— 2— 3— B 720
表 2需要解决的问题：
(1) Center i→Base j 运送的人数
(2) Base j 实际训练人数
(3) 第 i航线运送第 j基地人数
(4) 第 i航线使用小船数量
(5) 第 i航线使用大船数量
(6) 征兵中心至训练基地运送费用
(7) 训练基地至海军部队运送费用
(8) 总费用
2006/3
--第 4章 整数规划 --
--37--
例 3：仓库位置问题
韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表 1
所示。生产出来的番茄酱可储存在三个成品库中，从各工厂运送一吨
产品到各成品库的费用如表 2所示。由于某些因素，公司销售看淡，
现只有四家客户，其需求量如表 3所示。从各成品库运送成品到各客
户的需求地的单位费用如表 4所示。每个工厂和每个成品库运营的年
固定费用如表 5所示。公司想确定关闭那些工厂和仓库，会使总费用
最低。
表 1 生产能力
工 厂 1 2 3 4 5
能力 (吨 ) 300 200 300 200 400
表 3 客户需求
客 户 1 2 3 4
需求 (吨 ) 200 300 150 250
表 2 工厂 — 成品库运费表
成品库 1 成品库 2 成品库 3
1
2
3
4
5
800 1000 1200
700 500 700
800 600 500
500 600 700
700 600 500
(元 /吨 )
2006/3
--第 4章 整数规划 --
--38--
表 4 成品库 — 客户运输费用 （元 / 吨）
成品库
客户
成品库 1
成品库 2
成品库 3
1 2 3 4
40 80 90 50
70 40 60 80
80 30 50 60
表 5 年运营固定费用 （元）
工厂 1 工厂 2 工厂 3 工厂 4 工厂 5 成品库 1 成品库 2 成品库 3
35000 45000 40000 42000 40000 40000 20000 60000
2006/3
--第 4章 整数规划 --
--39--
建模思路
xi—— 0-1变量，第 i厂是否开；
yj—— 0-1变量，第 j库是否开。
0-1规划与运输问题的混合模型。
费用：工厂 —— 成品库运输费用 +开工费；
成品库 —— 客户运输费用 +成品库运营费。
2006/3
--第 4章 整数规划 --
--40--
例 4：资产运作滚动计划
某养殖场饲养 6头黑熊（资产），
在未来三年内对该 6头黑熊的预期收
入如表中所示（以千元计）。为维持
养殖场的正常的资金周转，该厂必须
在第一年获取 20000元的收入，第二
年获取 30000元的收入，第三年获取
35000元的收入。试确定，该养殖场
应采取怎样的销售计划，可使三年中
获得的总收入最大？
1
2
3
4
5
6
year1 year2 year3
15 20 24
16 18 21
22 30 36
10 20 30
17 19 22
19 25 29
黑熊
建模提示：
⑴ 利用 0-1变量表示在某年出售与否的关系；
⑵ 三年内熊必须出售且只能出售一次；
⑶ 每年的销售收入必须能保证需求；
⑷ 每年的剩余资金可移作第二年使用。
2006/3
--第 4章 整数规划 --
--41--
例 5：
市政对四个建设项目招
标，有三个建筑队投标，
标底情况如表示。由于建
筑队 1力量所限，只能完成
其中一个项目，而 2和 3最
多都可承担两项。试确定，
如何分配可使总费用最少？
1
2
3
1 2 3 4
50 46 42 40
51 48 44 —
? 47 45 45
单位：万元
问题分析：
⑴ 可利用匈牙利方法求解分配问题解决
⑵ 要考虑不能做的项目和可以多做项目的处理方式。
☆ 如果要建立模型，该如何表示？
2006/3
--第 4章 整数规划 --
--42--
例 6：
校篮球队教练要确定比赛的首发阵容。全队共有 7名球员，根据技
术水平，对每名运动员的控球（ ball-handing）、投篮（ shooting）、蓝
板（ rebounding）、防守（ defense）的能力都评出等级分,1分最低,3
分最高。各球员的位置（ position）及各项能力的等级分值如表示。五
名出场队员应满足下述要求,（ 1）至少有 3名队员能打后卫，至少
有 2名队员能打前锋，至少有 1名队员能打中锋；（ 2）平均控球、投篮、
蓝板能力在 1.8分以上； （ 3） 2号队员或 3号队员必须在首发阵容中。
目标是首发阵容中防守能力最强。
1
2
3
4
5
6
7
运动员 位置（ P） 控球（ B） 投篮（ S） 蓝板（ R） 防守（ D）
Guard
Center
G/Forward
F/C
G/F
F/C
G/F
3 3 1 3
2 1 3 2
2 3 2 2
1 3 3 1
1 3 1 2
3 1 2 3
3 2 2 1
2006/3
--第 4章 整数规划 --
--43--
设 xj= 1 0 —— 第 j号队员入选—— 第 j号队员没入选
Max z=∑djxj —— 防守能力总分
j=1
7
∑xj =5 —— 上场队员数
j=1
7
∑bjxj ?9 —— 控球能力总分
∑sjxj ?9 —— 投篮能力总分
∑rjxj ?9 —— 蓝板能力总分
x1+ x3 + x5 + x7 ?3 —— 后卫人数
x3+ x4+ x5 + x6 + x7 ?2 —— 前锋人数
x2+ x4 + x6 ?1 —— 中锋人数
j=1
j=1
j=1
7
7
7
xj=0或 1 (j=1,··,7)
St.
x2+ x3 ?1 2号,3号要求
--第 4章 整数规划 --
--1--
2006/3
--第 4章 整数规划 --
--2--
Integer Programming 整数规划
All Integer Programming 全整数规划
Mixed Programming 混合整数规划
第四章 整数规划
2006/3
--第 4章 整数规划 --
--3--
4.1 一般整数规划问题的特点及分枝定界法
一、引例
某厂拟用集装箱托运甲、乙两种货物，每箱的体
积、重量、可获利润及托运时所受的限制如下表所示，
问如何托运能使总收益最大？
货物 体积 (米 3/箱 ) 重量 (吨 /箱 ) 利润 (千元 /箱 )
甲
乙
2 2 3
3 1 2
14 米 3 9 吨托运限制
2006/3
--第 4章 整数规划 --
--4--
建模：
解：设 托运甲货物 x1箱，乙货物 x2箱
Max z=3 x1 +2 x2
st, 2 x1+3 x2?14
2 x1 + x2?9
x1?0,x2?0,且为整数
2006/3
--第 4章 整数规划 --
--5--
2 4 6
2
4
(3.25,2.5)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
2006/3
--第 4章 整数规划 --
--6--
2 4 6
2
4
(3.5,2)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(2.5,3)
2006/3
--第 4章 整数规划 --
--7--
2 4 6
2
4
(4,1)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(2.5,3)
(3,2)
2006/3
--第 4章 整数规划 --
--8--
分枝定界法,
L0,z0=14.75
x1=3.25,x2=2.5
L1,z1=14.5 L2,z2=13.5
L3,z3=13 L4,z4=14
x1=3.5,x2=2 x1=2.5,x2=3
x1=3,x2=2 x1=4,x2=1
?
2006/3
--第 4章 整数规划 --
--9--
LINDO软件及 EXCEL求解：
LINDO程序软件：同求解 LP模型时的输入及编辑修改过
程,在使用‘ GO ’命令求解之前，对整数变量给予说明。
命令格式,GIN <变量名 >。
EXCEL求解：
2006/3
--第 4章 整数规划 --
--10--
4.2 0-1规划问题及模型
一,0-1规划问题的概念
? 在整数规划问题中，若变量取值为 0或者 1，则为 0-1
规划问题。
? 0-1变量通常用来表示逻辑性选择的决策。
2006/3
--第 4章 整数规划 --
--11--
二,0-1变量的应用
例 1：某油田在 10个有油气构造处要选择若干个钻探
采油，设第 j个构造开采时需投资 aj元，投产后预计年收
益为 cj元，若该油田投资的总限额为 b元，问：应选择哪
几个构造开采最为有利？
设 xj= 10 --- 选择开采第 j个构造---不选择开采第 j个构造
max z=Σcjxj
j=1
10
∑ajxj? b
xj＝ 0或 1 (j=1,2,---,10)
j=1
10
-----年总收益
----投资额限制
1、表示选择性决策
2006/3
--第 4章 整数规划 --
--12--
2,表示选择性约束
例 2：上述例题中，如果在开采中需用电力，解决的方案或由电网
供电或由自备的柴油机发电。已知第 j个构造开采时每天耗电量为 dj度，
电网每天供电量限制为 f 度。当使用自备柴油机发电时，每度电平均耗
油 0.3公斤，而柴油供应量限额为每天 p公斤。试在模型中表示出该限制
条件。
采用电网供电,∑djxj? f
采用自备柴油机发电,∑0.3djxj? p
j=1
10
j=1
10
+(1－ y1)M
+(1－ y2)M
y1+y2=1
y1,y2 =0或 1
M-----非常大的正数
2006/3
--第 4章 整数规划 --
--13--
3,表示条件性约束
例 3：若在开采时还需满足下述条件：
（ a）若开采 8号，则必须同时开采 6号；
（ b）若开采 5号，则不许开采 3号；
（ c） 2 号和 4号至少开采一个；
（ d） 8 号与 7号必须同时开采；
（ e） 1号,4号,6号,9号开采时不能超过两个，
试表示上述约束条件。
2006/3
--第 4章 整数规划 --
--14--
（ a）当 x8=1 x6=1,x6≠0
当 x8=0 x6=1,x6=0
∴ x8 ? x6
（ b）当 x5 =1 x3=0,x3 ≠1
当 x5 =0 x3=0,x3 =1
∴ x5 + x3 ? 1
（ c） x2 + x4 ? 1
（ d） x8 = x7
（ e） x1 + x4 + x6 + x9 ? 2
2006/3
--第 4章 整数规划 --
--15--
4,两组条件满足其中一组
若 x1? 4，则 x2?1，否则 (x1?4)，则 x2? 3。
设 yi= 1
0
第 i 组条件起作用
第 i 组条件不起作用 则i=1,2
x1? 4＋ (1-y1) M
x2? 1－ (1-y1) M
M—— 充分大正数x
1? 4－ (1-y2) M
x2? 3＋ (1-y2) M
y1＋ y2=1
y1,y2=0或 1
2006/3
--第 4章 整数规划 --
--16--
5,分段函数线性表示
设有 f(xj)= Kj+cjxj 当 xj>0
0 当 xj=0，
将 min f (xj) 表示成
线性函数。
设 yj= 1
0
当 xj>0
当 xj=0
Min f(xj) = kjyj+cjxj
st,xj?yjM
xj?0,yj=0或 1
M— 非常大的正常数
则
f(xj) = kjyj+cjxj
xj?yjM
yj?xjM
xj?0,yj=0或 1
或为：
2006/3
--第 4章 整数规划 --
--17--
三、隐枚举法
步骤：
① 化标准形 (隐枚举法 ),1) 目标函数极小化 2) 约束条件化成 ?
3) 使目标函数系数皆为非负,若 xj系数为负值,则令 xj=1-xj?
4) 使目标函数按变量系数由小 → 大顺序排列，约束条件变
量排列的顺序要与之对应。
② 令所有变量 xj=0，计算边界目标函数值 z，检查是否满足所有约
束条件，若满足，即为最优解；否则，分枝计算。
③ 分枝：按变量次序依次令各变量取,1”和,0”值，计算边界值，
然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。
④ 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。
(a) 对可行解，保留边界值最小的一枝 zmin，其余全剪掉；
(b) >zmin分枝，剪掉；
(c) 能判断出为无可行解的分枝，剪掉；
(d) 非上述情况，继续分枝。
2006/3
--第 4章 整数规划 --
--18--
例：求解下述 0-1规划问题：
Max z=8x1+2x2-4x3-7x4-5x5
st,3x1+3x2+x3+2x4+3x5 ?4
5x1+3x2- 2x3 - x4+ x5 ?4
xj=0或 1 (j=1,2,3,4,5)
1) 目标函数极小化, min z?=-8x1-2x2+4x3+7x4+5x5
① 化标准形：
2) 约束条件 ?,-3x1-3x2-x3-2x4-3x5?-4
-5x1-3x2+ 2x3 + x4- x5 ?-4
xj=0或 1 (j=1,2,3,4,5)
2006/3
--第 4章 整数规划 --
--19--
3) 使目标函数系数皆为正,令 x1=1-x1?, x2=1-x2?
min z?=-8+8 x1? -2+2 x2? +4x3+7x4+5x5
st,-3+3 x1? -3+3 x2? -x3-2x4-3x5 ?-4
-5+5 x1? -3+3 x2? + 2x3 + x4- x5 ?-4
x1?,x2?,xj=0或 1 (j=3,4,5)
4) 变量按顺序排列：
min z?= 2 x2? +4x3 +5x5 +7x4+8 x1? -10
st,3 x2? -x3 -3x5 -2x4 +3 x1? ?2
3 x2? + 2x3 - x5 + x4+5 x1? ?4
x1?,x2?,xj=0或 1 (j=3,4,5)
2006/3
--第 4章 整数规划 --
--20--
求解图示：
1
2
3
4
5
6
7
8
9
10
11
z?=-10
z? =-8
z?=-4
z?=-6
z?=-5
z?=-1
z?=1
z?=-5
z?=-3
z?=-6x
3=1
z?=-3
√
×
×
×
×
×
2006/3
--第 4章 整数规划 --
--21--
4.4 分配问题及匈牙利算法 (Assignment Problem)
一、问题的提出和数学模型
例：有一份说明书，要分别译
成英、日、德、俄四种文字，
交与甲、乙、丙、丁四个人去
完成，因各人专长不同，他们
完成翻译不同文字所需要的时
间（小时）如表所示。规定每
项工作只能交与其中的一个人
完成，每个人只能完成其中的
一项工作。
问：如何分配，能使所需的
总时间最少？
甲 乙 丙 丁工作 人
译英文
译日文
译德文
译俄文
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
2006/3
--第 4章 整数规划 --
--22--
建立模型：
设 xij=
1
0
译英文,x11+ x12 + x13 + x14 =1
译日文,x21+ x22 + x23 + x24 =1
译德文,x31+ 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
xij =0或 1 (i=1,2,3,4; j=1,2,3,4)
Min z=?? aijxij (aij---效率 )i=1j=14 4
若第 i项工作交与第 j个人完成
若第 i项工作不交与第 j个人完成
2006/3
--第 4章 整数规划 --
--23--
分配问题一般数学模型结构：
设有 m项工作要交与 m个人完成，其中第 i项工作交与
第 j个人完成时所需花费的时间为 aij。规定每项工作只能
交与其中的一个人完成，而每个人只能完成其中的一项
工作。问：如何分配，可使所需的总时间最少？
Min z=?? aijxij
st,?xij =1
?xij =1
i=1j=1
j=1
i=1
m m
m
m
xij =0或 1 (i=1,2,··,m; j=1,2,··,m)
(i=1,2,··,m)
(j=1,2,··,m)
2006/3
--第 4章 整数规划 --
--24--
二、匈牙利法：
基本思想：
4 (0) 5 6
5 4 (0) 5
7 6 3 (0)
(0) 5 6 2
克尼格定理 (konig),如果从效率矩阵 [aij]的每一
行元素中分别减去 (或加上 )一个常数 ui,从每列中分别减
去 (或加上 )一个常数 vj,得到一个新的效率矩阵 [bij],其
中 bij=aij-ui-vj,则以 [bij]为效率矩阵的最优解等价于以
[aij]为效率矩阵的最优解,
2006/3
--第 4章 整数规划 --
--25--
证明,
以 [aij]为效率矩阵的目标函数值,z0=?? aijxij
以 [bij]为效率矩阵的目标函数值,z?=??bijxij
m m
i=1j=1
i=1j=1
m m
∵ bij=aij-ui-vj
∴ z?=?? (aij-ui-vj)xij = ?? aijxij - ?? uixij - ?? vjxij
=z0- ?ui?xij -?vj?xij
m m m m m m
m m m m
=z0- ?ui- ?vj =z0-constant
m m
i=1j=1 i=1j=1 i=1j=1 i=1j=1
i=1 j=1 j=1 i=1
i=1 j=1
m m
2006/3
--第 4章 整数规划 --
--26--
三、步骤
⑴ 使每行、每列都出现 0元素
方法：每行减该行最小元素；
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
-2
-4
-11
-4
min
0 8 7 5
11 0 10 4
2 3 5 0
0 11 9 5
min -0 -0 -5 -0
0 8 2 5
11 0 5 4
2 3 0 0
0 11 4 5
-2
-2
-2
+2 +2
0 8 0 3
11 0 3 2
4 5 0 0
0 11 2 3
?每列减该列最小元素。
2006/3
--第 4章 整数规划 --
--27--
⑵ 寻找位于不同行不同列的 0元素
准则：
A）从第一行开始，若只有一个 0，则记（ 0），同时作直线覆盖该列
的元素。否则，转下行；
B）从第一列开始，若只有一个 0，则记（ 0），同时作直线覆盖该行
的元素。否则，转下列；
C）重复 A）,B），至再找不出这样的 0元素，转 D）
D）可能出现三种情况：
① 每行均有（ 0）元素，则在有（ 0）位置构成最优解中 xij=1；
② 多于两行和两列存在未被直线覆盖的 0元素，即存在 0元素的闭回路，
则沿回路顶点每间隔一个 0记（ ），同时作直线覆盖该列的元素；
③ 所有 0元素均有直线覆盖，但记（ 0）的个数 <m个，转⑶。
2006/3
--第 4章 整数规划 --
--28--
0 0
0 0
0 0
⑶ 迭代，寻找新的位于不同行不同列的 0元素
a）从未被直线覆盖的元素中找出一个最小的元素 amin；
b）对行，若无直线覆盖，则 - amin；
c）对列，若有直线覆盖，则 + amin；
⑷ 转⑵ 。
2006/3
--第 4章 整数规划 --
--29--
特殊问题处理：
1．人数与工作数不等的处理：
当人数 >工作数时：假想工作数，使得与人数能够匹
配,对应的效率设定为 0值。
当工作数 >人数时：假想人数，使得与工作数能够匹
配,对应的效率设定为 0值。
2．若目标函数为求 max z的处理：（如效益）
∵ max z= - min (-z ) = - min ( z?)
∴ 等价于求解 min z ? =∑∑(-aij)xij
i=1 j=1
m m
2006/3
--第 4章 整数规划 --
--30--
4 3 5 6 7
3 6 4 5 6
4 7 5 2 4
8 9 6 5 3
甲 乙 丙 丁 戊
A
B
C
D
E 0 0 0 0 0
A
B
C
D
E
甲 乙 丙 丁 戊
4 7 6 5
8 5 4 6
4 8 6 5
5 9 2 7
3 4 8 7
0
0
0
0
0
-2 -8 -7 -6
-5 -7 -6 -4
-3 -6 -4 -3
-4 -9 -5 -4
2006/3
--第 4章 整数规划 --
--31--
4.5 整数规划模型的应用
例 1,在未来四个月中，某制鞋厂必须按时完成下述合
同要求，第一个月 300双，第二个月 500双，第三个月 100
双，第四个月 100双。在一月初，工厂已有 50双鞋（以前
的存货）和 3名工人，每名工人的月薪为 1500元，每月可
工作 160小时（正常工作时间）。一名工人最多还可有 20
小时的加班工作时间（规定），在加班工作时，每小时需
付 25元的加班费用。制作一双鞋需耗费 4个工时和 5元的原
料费。在每月的开始，可以租用和解雇工人。每雇用一名
工人需支付 1600元的费用，每解雇一名工人需支付 2000元
的解雇费用。在每月末，要为留在仓库里未交货的每双鞋
支付 30元的保管维护费用。一个月生产的产品可用于满足
多个月的需求。试用 ILP方法确定最佳的生产计划和用工
政策。
2006/3
--第 4章 整数规划 --
--32--
问题分析：
需要解决的问题：
☆ 每月租进、解雇、使用的工人数
☆ 每月所需的加班时间
☆ 每月在正常时间、加班时间生产的鞋子的数量
☆ 每月开始和结束时库存鞋子的数量
☆ 费用明细：雇工费、解雇费、用工费、加班费、原料费
2006/3
--第 4章 整数规划 --
--33--
月初
人数
本月
雇用
本月
解雇
本月
使用
用工过程图示：
生产过程图示：
正常
生产
加班
生产
月初
库存
月末
库存
交货
数量
工人数
鞋子数
2006/3
--第 4章 整数规划 --
--34--
建模思路：
? 每月可用工人 ≥0
? 每月库存鞋子 ≥0
可用工人数 =月初数 +租进数 - 解雇数 =月末数
月末库存量 =月初库存 +正常生产 +加班生产 -交货量
? 目标函数 =总费用
=月薪 +雇用费 +解雇费 +加班费 +原料费 +库存费
2006/3
--第 4章 整数规划 --
--35--
例 2：
某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练
基地中的一个进行训练，从每个征兵中心运送一个新兵至某一个训练基
地的费用如表 1所示（单位：元） 。
每年在中心 1征招 1000名士兵，
中心 2征召 600名，中心 3征召 700
名。基地 1可训练 1000名，基地 2
可训练 800名，基地 3可训练 700名。
from
to Base1 Base2 Base3
Center1
Center2
Center3
240 200 300
300 400 220
300 400 250
新兵受训后，要送到海军部队。运送时可采用小船或大船两种工
具，共有 7条小船和 3条大船可供使用。若使用小船，则每条船要花费
5000元加上每海里 2元的费用；使用大船要花费 10000元加上每海里 3
元的费用。一条小船可运送 200人，沿途最多可经过 2个训练基地；一
条大船可运送 500人，最多可经过 3个训练基地。可能的航线如表 2中
所示。现问，应怎样决策，能使发生的总费用最少？
表 1
2006/3
--第 4章 整数规划 --
--36--
途径训练基地 航程（海里）航线
1
2
3
4
5
6
7
B— 1— B 370
B— 1— 2— B 515
B— 2— 3— B 665
B— 2— B 460
B— 3— B 600
B— 1— 3— B 640
B— 1— 2— 3— B 720
表 2需要解决的问题：
(1) Center i→Base j 运送的人数
(2) Base j 实际训练人数
(3) 第 i航线运送第 j基地人数
(4) 第 i航线使用小船数量
(5) 第 i航线使用大船数量
(6) 征兵中心至训练基地运送费用
(7) 训练基地至海军部队运送费用
(8) 总费用
2006/3
--第 4章 整数规划 --
--37--
例 3：仓库位置问题
韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表 1
所示。生产出来的番茄酱可储存在三个成品库中，从各工厂运送一吨
产品到各成品库的费用如表 2所示。由于某些因素，公司销售看淡，
现只有四家客户，其需求量如表 3所示。从各成品库运送成品到各客
户的需求地的单位费用如表 4所示。每个工厂和每个成品库运营的年
固定费用如表 5所示。公司想确定关闭那些工厂和仓库，会使总费用
最低。
表 1 生产能力
工 厂 1 2 3 4 5
能力 (吨 ) 300 200 300 200 400
表 3 客户需求
客 户 1 2 3 4
需求 (吨 ) 200 300 150 250
表 2 工厂 — 成品库运费表
成品库 1 成品库 2 成品库 3
1
2
3
4
5
800 1000 1200
700 500 700
800 600 500
500 600 700
700 600 500
(元 /吨 )
2006/3
--第 4章 整数规划 --
--38--
表 4 成品库 — 客户运输费用 （元 / 吨）
成品库
客户
成品库 1
成品库 2
成品库 3
1 2 3 4
40 80 90 50
70 40 60 80
80 30 50 60
表 5 年运营固定费用 （元）
工厂 1 工厂 2 工厂 3 工厂 4 工厂 5 成品库 1 成品库 2 成品库 3
35000 45000 40000 42000 40000 40000 20000 60000
2006/3
--第 4章 整数规划 --
--39--
建模思路
xi—— 0-1变量，第 i厂是否开；
yj—— 0-1变量，第 j库是否开。
0-1规划与运输问题的混合模型。
费用：工厂 —— 成品库运输费用 +开工费；
成品库 —— 客户运输费用 +成品库运营费。
2006/3
--第 4章 整数规划 --
--40--
例 4：资产运作滚动计划
某养殖场饲养 6头黑熊（资产），
在未来三年内对该 6头黑熊的预期收
入如表中所示（以千元计）。为维持
养殖场的正常的资金周转，该厂必须
在第一年获取 20000元的收入，第二
年获取 30000元的收入，第三年获取
35000元的收入。试确定，该养殖场
应采取怎样的销售计划，可使三年中
获得的总收入最大？
1
2
3
4
5
6
year1 year2 year3
15 20 24
16 18 21
22 30 36
10 20 30
17 19 22
19 25 29
黑熊
建模提示：
⑴ 利用 0-1变量表示在某年出售与否的关系；
⑵ 三年内熊必须出售且只能出售一次；
⑶ 每年的销售收入必须能保证需求；
⑷ 每年的剩余资金可移作第二年使用。
2006/3
--第 4章 整数规划 --
--41--
例 5：
市政对四个建设项目招
标，有三个建筑队投标，
标底情况如表示。由于建
筑队 1力量所限，只能完成
其中一个项目，而 2和 3最
多都可承担两项。试确定，
如何分配可使总费用最少？
1
2
3
1 2 3 4
50 46 42 40
51 48 44 —
? 47 45 45
单位：万元
问题分析：
⑴ 可利用匈牙利方法求解分配问题解决
⑵ 要考虑不能做的项目和可以多做项目的处理方式。
☆ 如果要建立模型，该如何表示？
2006/3
--第 4章 整数规划 --
--42--
例 6：
校篮球队教练要确定比赛的首发阵容。全队共有 7名球员，根据技
术水平，对每名运动员的控球（ ball-handing）、投篮（ shooting）、蓝
板（ rebounding）、防守（ defense）的能力都评出等级分,1分最低,3
分最高。各球员的位置（ position）及各项能力的等级分值如表示。五
名出场队员应满足下述要求,（ 1）至少有 3名队员能打后卫，至少
有 2名队员能打前锋，至少有 1名队员能打中锋；（ 2）平均控球、投篮、
蓝板能力在 1.8分以上； （ 3） 2号队员或 3号队员必须在首发阵容中。
目标是首发阵容中防守能力最强。
1
2
3
4
5
6
7
运动员 位置（ P） 控球（ B） 投篮（ S） 蓝板（ R） 防守（ D）
Guard
Center
G/Forward
F/C
G/F
F/C
G/F
3 3 1 3
2 1 3 2
2 3 2 2
1 3 3 1
1 3 1 2
3 1 2 3
3 2 2 1
2006/3
--第 4章 整数规划 --
--43--
设 xj= 1 0 —— 第 j号队员入选—— 第 j号队员没入选
Max z=∑djxj —— 防守能力总分
j=1
7
∑xj =5 —— 上场队员数
j=1
7
∑bjxj ?9 —— 控球能力总分
∑sjxj ?9 —— 投篮能力总分
∑rjxj ?9 —— 蓝板能力总分
x1+ x3 + x5 + x7 ?3 —— 后卫人数
x3+ x4+ x5 + x6 + x7 ?2 —— 前锋人数
x2+ x4 + x6 ?1 —— 中锋人数
j=1
j=1
j=1
7
7
7
xj=0或 1 (j=1,··,7)
St.
x2+ x3 ?1 2号,3号要求
