整数规划求解方法
2011-01-02 17:00阅读：
整数规划
整数规划的数学模型及解的特点
解纯整数规划的割平面法
分支定界法
0—1型整数规划
指派问题与匈牙利法
整数规划的数学模型及解的特点
整数规划IP (integer
programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。
松弛问题(slack
problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear
programming)。
一、整数线性规划数学模型的一般形式
整数线性规划问题可以分为以下几种类型
1、纯整数线性规划(pure
integer linear
programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。
2、混合整数线性规划(mixed integer liner
programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3、0—1型整数线性规划(zero—one integer liner
programming)：指决策变量只能取值0或1的整数线性规划。
二、整数规划的解的特点
相对于松弛问题而言，二者之间既有联系，又有本质的区别
(1)整数规划问题的可行域是其松弛问题的一个子集
(2)整数规划问题的可行解一定是其松弛问题的可行解
(3)一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，更不是最优解
(4)对松弛问题的最优解中非整数变量简单的取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解
(5)求解还是要先求松弛问题的最优解，然后用分支定界法或割平面法。
解纯整数规划的割平面法
基本思路：通过增加新的约束来切割可原问题伴随规划的可行域，使它在不断缩小的过程中，将原问题的整数最优解逐渐暴露且趋于可行域极点的位置，这样就有可能用单纯形法求出。
增加的新约束称为割平面方程或切割方程
例 用割平面法解整数规划问题
解：将原整数规划问题称为原问题A
0，不考虑整数条件的伴随规划称为问题B
0，求解过程如下：
1．用单纯形法求解B
0，得最优单纯形表
Cj
|
1
|
1
|
0
|
0
|
CB
|
XB
|
|
x1
|
x2
|
x3
|
x4
|
1
1
|
x2
x1
|
7/4
3/4
|
0
1
|
1
0
|
3/4
-1/4
|
1/4
1/4
|
|
-Z
|
-5/2
|
0
|
0
|
-1/2
|
-1/2
|
2．求一个割平面方程
(1)
在最终表上任选一个含有不满足整数条件基变量的约束方程。
本例中，x
1=3/4,x
2=7/4均不满足整数条件
若选x
1，则含x
1的约束方程为：
(1)
(2)将所选的约束方程中非基变量的系数及常数项进行拆分处理。具体规则是：将上述系数和常数均拆成一个整数加一个非负的真分数之和。
如： 7/4=1+3/4
-5/2=-3+1/2
1/4=0+1/4
则(1)式变为
(2)
(3)将上述约束方程重新组合。组合的原则是：将非基变量系数及常数项中的非负真分数部分移到等号左端，将其他部分移到等式右端，即得
(3)
(4)求割平面方程
分析式(3)，等式右端由三部分组成，常数项得整数部分，基变量及非基变量(含松弛变量或剩余变量)，前两部分都是整数或应取整数，而松弛变量根据约束方程来看也应取非负整数(对于这一点，当原问题A0得约束方程组中的系数或常数项中有非整数时，要求将该约束方程先化成整数系数及整数常数项，然后再标准化，就可满足)，因此式(3)右端应为整数，同时由于等式左端的特殊性，右端的整数应是大于等于零的整数。这是因为可将(3)式改写成
(4)
式(4)左端是非负数，右端第一项是一个真分数，如果第二项为负整数(即≤－1的整数)，则不能保证左端为非负数。因此，(3)式的左端应大于等于零
即
这就是一个割平面方程。
将上述方法进行一般化描述：
(1)设 是伴随规划最终单纯形表上第I行约束方程所对应的基变量，其取值为非整数，则其约束方程式为
(1)
(2)将 拆分
记
(2)
式中
将(2)式代入(1)式
或
由于 ， ，及 为大于等于0的整数，因此有
或
加入松弛变量xs，化为等式：
就是割平面方程的最基本形式。
3．将割平面方程加到伴随规划的最终单纯形表中，用对偶单纯形法继续求解
本例中选择
新的单纯形表如下：
Cj
|
1
|
1
|
0
|
0
|
0
|
CB
|
XB
|
|
x1
|
x2
|
x3
|
x4
|
x5
|
1
1
0
|
x2
x1
x5
|
7/4
3/4
-3/4
|
0
1
0
|
1
0
0
|
3/4
-1/4
[-3/4]
|
1/4
1/4
-1/4
|
0
0
1
|
|
-Z
|
-5/2
|
0
|
0
|
-1/2
|
-1/2
|
0
|
|
|
|
|
|
2/3
|
2
|
|
1
1
0
|
x2
x1
x3
|
1
1
1
|
0
1
0
|
1
0
0
|
0
0
1
|
0
1/3
1/3
|
1
-1/3
-4/3
|
|
-Z
|
-2
|
0
|
0
|
0
|
-1/3
|
-2/3
|
X*=(1,1)’
Z*=2
4．若没有得到整数最优解，则继续做割平面，转2。
（画图说明原理，即图解法）
割平面法解整数规划问题的基本步骤
第一步：用单纯形法解松弛问题，得到最优单纯形表。
第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。
第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。
练习 用割平面法解整数规划问题
分支定界法
分支定界法的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加新约束——缩小可行域；将原整数规划问题分支——分为两个子规划，再解子规划的伴随规划……，最后得到原整数规划的伴随规划。这就是所谓的“分支”。
所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可以作为衡量处理其它分支的一个依据。
“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。
例 用分支定界法求解整数规划问题
(1)首先解该整数规划的伴随规划，如图所示，用图解法
其最优解为X*=(3/2,10/3)’，图中点A，Z*=29/6。
不符合整数要求，可任选一个变量，如x
1=3/2进行分支。由于最接近3/2的整数是1和2，因而可以构造两个约束条件x
1≥2
和x
1≤1，分别并入原来的约束条件，形成两个分支，记为LP
1,LP
2
分支定界法的计算步骤
第一步：计算原问题目标函数值的初始上界
第二步：计算原问题目标函数值的初始下界
第三步：增加约束条件将原问题分支
第四步：分别求解一对分支
第五步：修改上、下界
第六步：比较上、下界大小，如有上界＝下界，停止计算，找到最优解，否则转3
练习 用分支定界法求解整数规划问题
0—1型整数规划
0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi称为0—1变量，或称为二进制变量。
即
0—1型整数规划中0—1变量作为逻辑变量(logical
variable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。
一、0—1型整数规划的典型应用问题
例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。
序号
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
物品
|
食品
|
氧气
|
冰镐
|
绳索
|
帐篷
|
照相器材
|
通信设备
|
重量/Kg
|
5
|
5
|
2
|
6
|
12
|
2
|
4
|
重要性系数
|
|
