文档介绍：1 整数规划的MATLAB求解方法
(一) 用MATLAB求解一般混合整数规划问题
由于MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函数,因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif和Tawfik在MATLAB Central上发布的一个用于求解一般混合整数规划的程序,在此命名为intprog,在原程序的基础上做了简单的修改,将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种,即:选择与整数值相差最大的非整数变量首先进行分枝。intprog函数的调用格式如下:
[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)
该函数解决的整数规划问题为:
在上述标准问题中,假设为维设计变量,且问题具有不等式约束个,等式约束个,那么:、均为维列向量,为维列向量,为维列向量,为维矩阵,为维矩阵。
在该函数中,输入参数有c,A,b,Aeq,beq,lb,ub,M和TolXInteger。其中c为目标函数所对应设计变量的系数,A为不等式约束条件方程组构成的系数矩阵,b为不等式约束条件方程组右边的值构成的向量。Aeq为等式约束方程组构成的系数矩阵,beq为等式约束条件方程组右边的值构成的向量。lb和ub为设计变量对应的上界和下界。M为具有整数约束条件限制的设计变量的序号,例如问题中设计变量为,要求和为整数,则M=[2;3;6];若要求全为整数,则M=1:6,或者M=[1;2;3;4;5;6]。TolXInteger为判定整数的误差限,即若某数x和最邻近整数相差小于该误差限,则认为x
即为该整数。
在该函数中,输出参数有x, fval和exitflag。其中x为整数规划问题的最优解向量,fval为整数规划问题的目标函数在最优解向量x处的函数值,exitflag为函数计算终止时的状态指示变量。
例1 求解整数规划问题:
算法:
c=[-1;-1];
A=[-4 2;4 2;0 -2];
b=[-1;11;-1];
lb=[0;0];
M=[1;2]; %均要求为整数变量
Tol=1e-8; %判断是否整数的误差限
[x,fval]=linprog(c,A,b,[],[],lb,[]) %求解原问题松弛线性规划
[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol) %求最优解整数解
结果:
x = %松弛线性规划问题的最优解
fval =
-
x1 = %整数规划的最优解
2
1
fval2 =
-
(二) 用MATLAB求解0-1规划问题
在MATLAB优化工具箱中,提供了专门用于求解0-1规划问题的函数bintprog,其算法基础即为分枝界定法,在MATLAB中调用bintprog函数求解0-1规划时,需要遵循MATLAB中对0-1规划标准性的要求。
0-1规划问题的MATLAB标准型
在上述模型中,目标函数f 需要极小化,以及需要满足的约束条件,不等式约束一定要化为形式为“”。
假设为维设计变量,且问题具有不等式约束个,等式约束个,那么:、均为维列向量,为维列向量,为维列向量,为维矩阵,为维矩阵。
如果不满足标准型的要求,则需要对原问题进行转化,化为标准型之后才能使用相关函数,标准化的方法和线性规划中的类似。
0-1规划问题的MATLAB求解函数
MATLAB优化工具箱中求解0-1规划问题的命令为bintprog
bintprog的调用格式
x = bintprog(f)
x = bintprog(f,A,b)
x = bintprog(f,A,b,Aeq,beq)
x = bintprog(f,A,b,Aeq,beq,x0)
x = bintprog(f,A,b,Aeq,Beq,x0,options)
[x,fval] = bintprog(...)
[x,fval,exitflag] = bintprog(...)
[x,fval,exitflag,output] = bintprog(...)
命令详解
1)x = bintprog(f)
该函数调用格式求解如下形式的0-1规划问题
2)x = bintprog(c,A,b)
该函数调用格式求解如下形式的0-1规划问题
3)x = bintprog (c,A,b,Aeq,beq)
该函数调用格式求解如下形式的0-1规划问题:
4)x = bintprog (c,A,b,Aeq,beq,x0)
该函数调用格