integer-program

整数规划（IP）

整数规划及其概念

整数规划分类

整数规划分为三大类：

1)变量全限制为整数，纯整数规划；

2)变量部分限制为整数，混合整数规划。

3)决策变量只能取0或1的整数规划，0-1整数规划。

注：整数规划的最优解不能按照实数最优解简单取整而获得。

整数规划特点

• 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
• 原线性规划有最优解，当自变量限制为整数后，整数规划可能无可行解。也可能有可行解（当然就存在最优解），但最优解值变差。
• 整数规划最优解不能按照实数最优解简单取整而获得。

整数线性规划模型及问题

可以联想算法中的0-1背包问题，非常类似

整数规划和线性规划的关系

非线性约束条件的线性化

相互排斥的约束条件

整数规划模型求解及应用

从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。

适用范围

数学规划中的变量（部分或全部）限制为整数时，若符合线性规划的适用范围，则使用整数线性规划。

模型求解

首先不考虑整数约束，得到线性规划问题（一般称为松弛问题或伴随问题），在得到可行解后，再寻找整数最优解。

分枝定界法

割平面法

匈牙利解法

匈牙利解法用于0-1整数规划的典型问题——指派问题的解决。

指派问题的标准形式

指派问题的数学模型

非标准形式的指派问题

指派问题的匈牙利解法的一般步骤

MATLAB代码示例

c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5; 8 4 2 3 5;9 10 6 9 10];
c=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);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1));
X=reshape(x,5,5)
opt=y

整数线性规划的计算机求解

Matlab求解整数线性规划的命令：

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)