第二?/p>
整数规划
§
1
概论
1.1
定义
规划中的变量
(部分或全部?/p>
限制为整数时?/p>
称为整数规划?/p>
若在线性规
划模型中?/p>
变量限制为整数,
则称为整数线性规划?/p>
目前所流行的求解整数规划的方法?/p>
往往只?/p>
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划?/p>
1.2
整数规划的分?/p>
如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类?/p>
1
o
变量全限制为整数时,称纯(完全)整数规划?/p>
2
o
变量部分限制为整数的,称混合整数规划?/p>
1.2
整数规划特点
?/p>
i
?/p>
原线性规划有最优解?/p>
当自变量限制为整数后?/p>
其整数规划解出现下述情况?/p>
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致?/p>
②整数规划无可行解?/p>
?/p>
1
原线性规划为
min
z
?/p>
x
1
?/p>
x
2
2
x
1
?/p>
4
x
2
?/p>
5,
x
1
?/p>
0,
x
2
?/p>
0
5
5
其最优实数解为:
x
1
?/p>
0,
x
2
?/p>
,
min
z
?/p>
?/p>
4
4
③有可行解(当然就存在最优解?/p>
,但最优解值变差?/p>
?/p>
2
原线性规划为
min
z
?/p>
x
1
?/p>
x
2
2
x
1
?/p>
4
x
2
?/p>
6,
x
1
?/p>
0,
x
2
?/p>
0
3
3
其最优实数解为:
x
1
?/p>
0,
x
2
?/p>
,
min
z
?/p>
?/p>
2
2
若限制整数得?/p>
x
1
?/p>
1,
x
2
?/p>
1,
min
z
?/p>
2
?/p>
?/p>
ii
?/p>
整数规划最优解不能按照实数最优解简单取整而获得?/p>
1.3
求解方法分类?/p>
?/p>
i
)分枝定界法—可求纯或混合整数线性规划?/p>
?/p>
ii
)割平面法—可求纯或混合整数线性规划?/p>
?/p>
iii
)隐枚举法—求解?/p>
0-1
”整数规划:
①过滤隐枚举法;
②分枝隐枚举法?/p>
?/p>
iv
)匈牙利法—解决指派问题(
?/p>
0-1
”规划特殊情形)
?/p>
?/p>
v
)蒙特卡洛法—求解各种类型规划?/p>
下面将简
要介绍常用的几种求解整数规划的方法?/p>
§
2
分枝定界?/p>
对有约束条件的最优化问题
(其可行解为有限数)
的所有可行解空间恰当地进行系
统搜索,
这就是分枝与定界内容?/p>
通常?/p>
把全部可行解空间反复地分割为越来越小的子
集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题)
,这?/p>
为定界?/p>
在每次分枝后?/p>
凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,
-16-