第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
蒙塔卡罗算法 excel仿真.doc
第二章 整数规划
§1 概论
1.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，
变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：
1o 变量全限制为整数时，称纯（完全）整数规划。
2o 变量部分限制为整数的，称混合整数规划。
3o 变量只能取 0 或 1 时，称之为 0-1 整数规划。
整数规划特点
（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例 1 原线性规划为
x
1
4
x
2
,0 2
x
x
1
min
min
s.t.
z
2
x
1
x
2
,0
x
1
。
0
z
,
其最优实数解为：
③有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。
例 2 原线性规划为
z
2
x
1
,6
x
1
,
min
z
min
s.t.
2
。
0
x
2
x
1
其最优实数解为：
,5
5
4
x
1
4
x
,0 2
x
,1 2
x
x
2
3
2
2
x
5
4
,0
3
2
2
x
1
,1
min
z
。
若限制整数得：
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类：
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜
索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，
称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定
-11-
界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，
这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由
Land Doig 和 Dakin 等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是
解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工
厂选址问题、背包问题及分配问题等。
设有最大化的整数规划问题 A ，与它相应的线性规划为问题 B ，从解问题 B 开始，
若其最优解不符合 A 的整数条件，那么 B 的最优目标函数必是 A 的最优目标函数 *z 的
上界，记作 z ；而 A 的任意可行解的目标函数值将是 *z 的一个下界 z 。分枝定界法就
是将 B 的可行域分成子区域再求其最大值的方法。逐步减小 z 和增大 z ，最终求到 *z 。
现用下例来说明：
Max
例 3 求解下述整数规划
1 90
40
z
x
x
9
7
56
x
x
2
1
7
20
70
x
x
1
,
0
xx
且为整数
1
s.t.
2
2
2
解 （i）先不考虑整数限制，即解相应的线性规划 B ，得最优解为：
x
1
.1
,
8168
z
355.8779
.4
8092
,
x
2
可见它不符合整数条件。这时 z 是问题 A 的最优目标函数值 *z 的上界，记作 z 。而
，是 *z 的一个下界，记作 z ，
x
1
即
显然是问题 A 的一个整数可行解，这时 0z
。
1, xx 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 1x
,0 2
0
x
*
0
356
z
（ii）因为
2
进行分枝，把可行集分成 2 个子集：
[
4.8092]
x
1
因为 4 与 5 之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。
4.8092]
51
x
1
，
4
[
这一步称为分枝。这两个子集的规划及求解如下：
2
x
x
1
s.t.
Max
问题 1B ：
9
7
0
,0.4
x
2
Max
问题 2B ：
1 90
40
z
x
7
56
x
x
1
2
20
70
x
x
1
2
,4
0
x
x
1
2
,1.2
349
z
。
1
1 90
40
z
x
x
9
56
7
x
x
2
1
20
7
70
x
x
1
2
,5
0
x
x
1
2
,0.5
,57.1
341
x
z
2
1
*
349
0
z
。
再定界：
s.t.
x
1
2
4.
。
最优解为：
最优解为：
-12-
x
（iii）对问题 1B 再进行分枝得问题 11B 和 12B ，它们的最优解为
B
11
B
12
x
1
x
1
340
:
:
再定界：
（iv）对问题 2B 再进行分枝得问题 21B 和 22B ，它们的最优解为
,2
,4
z
11
2
,00.3
1.43,
x
2
*
341
，并将 12B 剪枝。
z
340
z
12
327.14
083
:
x
x
1
,00.1
5.44,
B
21
22B 无可行解。
21, BB
剪枝。
22
于是可以断定原问题的最优解为：
z
2
22
将
x
1
,4
x
2
*
,2
z
340
从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的整数规划问题称为问题 A ，将与它相应的线性规划问题称为问
题 B 。
（i）解问题 B 可能得到以下情况之一：
（a） B 没有可行解，这时 A 也没有可行解，则停止．
（b） B 有最优解，并符合问题 A 的整数条件， B 的最优解即为 A 的最优解，则
停止。
（c） B 有最优解，但不符合问题 A 的整数条件，记它的目标函数值为 z 。
（ii）用观察法找问题 A 的一个整数可行解，一般可取
,
n
求得其目标函数值，并记作 z 。以 *z 表示问题 A 的最优目标函数值；这时有
x j
,0
,1
j
，试探，
z
*
z
z
进行迭代。
第一步：分枝，在 B 的最优解中任选一个不符合整数条件的变量 jx ，其值为 jb ，
以 ]
[ jb 表示小于 jb 的最大整数。构造两个约束条件
x
j
[ j
b
]
和
x
j
[
b
j
1]
将这两个约束条件，分别加入问题 B ，求两个后继规划问题 1B 和 2B 。不考虑整数条件
求解这两个后继问题。
定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出
最优目标函数值最大者作为新的上界 z 。从已符合整数条件的各分支中，找出目标函数
值为最大者作为新的下界 z ，若无作用 0z
。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于 z 者，则剪掉这枝，即
以后不再考虑了。若大于 z ，且不符合整数条件，则重复第一步骤。一直到最后得到
z *
为止。得最优整数解
,1
。
n
z
j
,
,*
x j
§3
10 型整数规划
10 型整数规划是整数规划中的特殊情形，它的变量 jx 仅取值 0 或 1。这时 jx 称
为 10 变量，或称二进制变量。 jx 仅取值 0 或 1 这个条件可由下述约束条件：
-13-
0
jx
1
，整数
10 变
所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入
量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们
先介绍引入 10 变量的实际问题，再研究解法。
3.1 引入 10 变量的实际问题
3.1.1 投资场所的选定——相互排斥的计划
例 4 某公司拟在市 东、西、南三区建立门市 部。拟议中有 7 个位置（点）
在南区：由
如选用 iA 点，设备投资估计为 ib 元，每年可获利润估计为 ic 元，但投资总额不能
两个点中至少选一个。
(
,2,1
iAi
)7,
在东区：由
在西区：由
,
可供选择。规定
AAA
1
3
2
4, AA
5
6, AA
7
三个点中至多选两个；
,
两个点中至少选一个；
超过 B 元。问应选择哪几个点可使年利润为最大？
解题时先引入 10 变量
(
ixi
,2,1
)7,
令
ix
,1
0
，
当
，
iA
点被选中
iA
当
.
点没被选中
,2,1 i
7,
.
于是问题可列写成：
Max
7
z
i
1
ixc
i
B
7
i
xb
i
1
i
x
1
x
x
x
2
x
x
5
4
6
2
s.t.
x
3
1
,1
3.1.2 相互排斥的约束条件
① 有两个相互排斥的约束条件
5
x
1
4
x
3
x
24
x
1
或
7
2
7
2
x
10
或
i
45
。
为了统一在一个问题中，引入 10 变量 y ，则上述约束条件可改写为：
2
5
4
x
x
1
7
3
x
x
2
1
10
或y
其中 M 是充分大的数。
24
45
yM
1(
)
My
② 约束条件
1 x
0
或
500
x
1
800
可改写为
-14-
800
y
500
x
y
1
10
或y
③ 如果有 m 个互相排斥的约束条件：
i
xa
11
i
xa
in
b
i
n
,2,1
,
m
为了保证这 m 个约束条件只有一个起作用，我们引入 m 个 10 变量
和一个充分大的常数 M ，而下面这一组 1m 个约束条件
(
iyi
,2,1
,
m
)
xa
11
i
y
m
y
1
xa
in
m
n
1
b
i
iMy
i
,2,1
,
m
（1）
（2）
0
，
* iy
就合于上述的要求。这是因为，由于（2）， m 个 iy 中只有一个能取 0 值，设
代入（1），就只有
i 的约束条件起作用，而别的式子都是多余的。
*i
3.1.3 关于固定费用的问题（Fixed Cost Problem）
在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并
在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线
性规划来描述，但可改变为混合整数规划来解决，见下例。
例 5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产
方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成
本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。
所以必须全面考虑。今设有三种方式可供选择，令
jx 表示采用第 j 种方式时的产量；
jc 表示采用第 j 种方式时每件产品的变动成本；
jk 表示采用第 j 种方式时的固定成本。
为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为
P
i
k
i
,0
xc
i
i
,
x
当
x
当
0
0
j
j
3,2,1j
.
在构成目标函数时，为了统一在一个问题中讨论，现引入 10 变量 jy ，令
jy
,1
,0
于是目标函数
当采用第
j
当不采用第
j
种生产方式，即
jx
种生产方式，即
0
时，
.0
时
jx
（3）
)
xc
2
2
（3）式这个规定可表为下述 3 个线性约束条件：
yk
11
xc
11
min
yk
2
z
(
)
(
2
x
3,2,1
其中 M 是个充分大的常数。（4）式说明，当
为 0 时才有意义，所以（4）式完全可以代替（3）式。
jMy
j
0jx
,
j
(
yk
3
3
xc
33
)
时 jy 必须为 1；当
（4）
时只有 jy
0jx
10 型整数规划解法之一（过滤隐枚举法）
3.2
解 10 型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，
即检查变量取值为 0 或 1 的每一种组合，比较目标函数值以求得最优解，这就需要检查
变量取值的 n2 个组合。对于变量个数 n 较大（例如 10n
），这几乎是不可能的。因此
-15-
常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方
法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对有
些问题隐枚举法并不适用，所以有时穷举法还是必要的。
下面举例说明一种解 10 型整数规划的隐枚举法。
例 6
Max
x
2
3
5
2
4
3
3
2
3
x
z
1
2
x
x
1
4
x
x
1
x
x
1
4
x
2
,
,
xx
1
2
x
x
x
2
3
s.t.
2
6
x
3
10
或x
3
求解思路及改进措施：
（i） 先试探性求一个可行解，易看出
个可行解，且相应的目标函数值为 3z 。
2
x
1
2
x
2
Max
(
xxx
1
)
,
,
3
2
)0,0,1(
满足约束条件，故为一
（ii） 因为是求极大值问题，故求最优解时，凡是目标值 3z 的解不必检验是否
满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：
3
5
3
x
3
3
2
x
3
5
2
4
3
，称该条件为过滤条件(Filtering Contraint)。从而原问题等价于：
3
z
x
1
3
2
x
x
1
2
x
x
1
4
x
x
1
x
x
1
4
x
2
,
,
xx
1
2
x
5
2
x
x
2
3
2
6
x
3
10
或x
3
)
(
a
)(
b
)(
c
)
(
d
)(
e
)
(
f
2
3
3
2
s.t.
若用全部枚举法，3 个变量共有 8 种可能的组合，我们将这 8 种组合依次检验它
是否满足条件(a)—(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)—(e)即
可行性条件不必再检验；若它满足(a)—(e)且相应的目标值严格大于 3，则进行（iii）。
（iii） 改进过滤条件。
（iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值 z 大
按上述思路与方法，例 6 的求解过程可由下表来表示：
的组合，这样可提前抬高过滤门槛，以减少计算量。
(
x ，
1
x
2
,
x
3
)
目标值
)0,0,0(
)0,0,1(
)0,1,0(
)1,0,0(
0
3
-2
5
-16-
e
c
约束条件
d
b
a
√ √ √ √ √
√ √ √ √ √
过滤条件
3
x
1
2
x
2
5
3
3
3
x
1
2
x
2
5
3
5
)0,1,1(
)1,0,1(
)1,1,1(
)1,1,0(
*
(
x
1
从而得最优解
1
8
6
3
*
x
3
)
,
x
*
2
,
§4 蒙特卡洛法（随机取样法）
√ √ √ √ √
)1,0,1(
，最优值
* z
3
x
1
2
x
2
5
3
8
8
。
前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线
性整数规划目前尚未有一种成熟而有效的求解方法，因为非线性规划本身的通用有效解
法尚未找到，更何况是非线性整数规划。
然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限
个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图
用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一
定的计算量的情况下，完全可以得出一个满意解。
2
4
例 7 已知非线性整数规划为：
2
2
2
x
x
3
4
3
x
x
3
4
,1
(
)5,
i
400
x
x
4
5
6
x
x
4
200
3
200
2
2
Max
3
x
x
z
2
1
2
8
x
x
1
0
99
xi
x
x
x
1
3
2
2
x
1
2
6
x
1
2
5
x
x
x
x
x
2
x
x
s.t.
5
4
3
2
3
2
x
5
2
x
5
800
5
对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算
)
个点，其计算量非常之大。然而应用蒙特卡洛去随机计算 610 个点，便可
100(
找到满意解，那么这种方法的可信度究竟怎样呢？
10
10
5
下面就分析随机取样采集 610 个点计算时，应用概率理论来估计一下可信度。
不失一般性，假定一个整数规划的最优点不是孤立的奇点。
假设目标函数落在高值区的概率分别为 0.01，0.00001，则当计算 610 个点后，有
任一个点能落在高值区的概率分别为
100(99
1000000
99.01
.01
解 （i）首先编写 M 文件 mente.m 定义目标函数 f 和约束向量函数 g，程序如下：
99.0
1000000
.0
999954602
99999
多位）
，
。
function [f,g]=mengte(x);
f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)...
-x(4)-2*x(5);
g(1)=sum(x)-400;
g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;
g(3)=2*x(1)+x(2)+6*x(3)-200;
g(4)=x(3)+x(4)+5*x(5)-200;
-17-
（ii）编写如下程序求问题的解：
rand('state',sum(clock));
p0=0;
tic
for i=1:10^5
x=99*rand(5,1);
x1=floor(x);x2=ceil(x);
[f,g]=mengte(x1);
if sum(g<=0)==4
if p0<=f
x0=x1;p0=f;
end
end
[f,g]=mengte(x2);
if sum(g<=0)==4
if p0<=f
x0=x2;p0=f;
end
end
end
x0,p0
toc
§5 整数规划的计算机解法
3
8
6
8
9
3
7
5
5
10
解：编写 Matlab 程序如下：
10
9
7
3
9
8
7
4
4
10
2
2
2
2
6
整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划规划问题，
无法直接利用 Matlab 的函数，必须利用 Matlab 编程实现分枝定界解法和割平面解法。
但对于指派问题等特殊的 10 整数规划问题或约束矩阵 A 是幺模矩阵时，有时可以直
接利用 Matlab 的函数 linprog。
例 8 求解下列指派问题，已知指派矩阵为
8 4 2 3 5;9 10 6 9 10];
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5
c=c(:);
a=zeros(10,25);
for i=1:5
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
end
b=ones(10,1);
-18-
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
