整数规划

1.整数规划概论

定义： 数学规划中的变量（部分或者全部）限制为整数时，称为整数规划。 若在线性规划模型中，变量限制为整数，则称为整数线性规划。

分类： 大致分为两类： （1）：变量全限制为整数时，称为纯（完全）整数规划。 （2）：变量部分限制为整数时，称为混合整数规划。

特点： （1）：原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况。 a，原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 b，整数规划无可行解。 c，有可行解（当然就存在最优解），但最优解值变差。 （2）：整数规划最优解不能按照实数最优解简单取整而获得。

求解方法分类： （1）：分枝定界法——可求纯或者混合整数线性规划 （2）：割平面法——可求纯或者混合整数线性规划 （3）：隐枚举法——求解“0-1”整数规划 a.过滤隐枚举法 b.分枝隐枚举法 （4）：匈牙利法——解决指派问题（“0-1”规划特殊情形） （5）：蒙特卡洛法——求解各种类型规划

2.非线性规划的Matlab标准形式及问题求解

式中： f,x,inction,b,beq,lb,ub 为列向量；A，Aeq为矩阵。 其中intcon表示整数变量的位数，例若变量中 x1，x2为整数变量，则intcon=[1,2]。

3.整数线性规划例题

例1：求解下列整数规划。 解：求解的matlab程序如下：

c=[2;3;4];
a=[1.5,3,5;280,250,400];
b=[600;60000];
intcon=[1,2,3];
[x,y]=intlinprog(-c,intcon,a,b,[],[],zeros(3,1))
x,y=-y

程序运行结果如下： 求得当x1=64，x2=168，x3=0时，最大值y=632。

例2：求解下列整数规划。 解：求解的matlab程序如下：

f=[5;5.1;5.4;5.5;0.2;0.2;0.2];
a=[1 0 0 0 0 0 0;0 1 0 0 0 0 0 ;0 0 1 0 0 0 0;0 0 0 1 0 0 0];
b=[30;40;45;20];
aeq=[1 0 0 0 -1 0 0;0 1 0 0 1 -1 0 ;0 0 1 0 0 1 -1;0 0 0 1 0 0 1];
beq=[15;25;35;25];
intcon=[1,2,3,4,5,6,7];
[x,y]=intlinprog(f,intcon,a,b,aeq,beq,zeros(7,1))

程序运行结果如下： 求得当x1=15，x2=40，x3=25，x4=20，y1=0，y2=15，y3=5时，最小值y=528。