2020年整数规划和多目标规划模型.doc

1整数规划的MATLAB求解方法(一)用MATLAB求解一般混合整数规划问题由于MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函数,因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱能够解决该类问题。这里我们给出开罗大学的Sherif和Tawfik在MATLABCentral上发布的一个用于求解一般混合整数规划的程序,在此命名为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=[-42;42;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= %整数规划的最优解21fval2=(二)用MATLAB求解0-1规划问题在MATLAB优化工具箱中,提供了专门用于求解0-1规划问题的函数bintprog,其算法基础即为分枝界定法,在MATLAB中调用bintprog函数求解0-1规划时,需要遵循MATLAB中对0-1规划标准性的要求。0-1规划问题的MATLAB标准型在上述模型中,目标函数f需要极小化,以及需要满足的约束条件,不等式约束一定要化为形式为“”。假设为维设计变量,且问题具有不等式约束个,等式约束个,那么:、均为维列向量,为维列向量,为维列向量,为维矩阵,为维矩阵。如果不满足标准型的要求,则需要对原问题进行转化,化为标准型之后才能使用相关函数,标准化的方法和线性规划中的类似。0-1规划问题的MATLAB求解函数MATLAB优化工具箱中求解0-1规划问题的命令为bintprogbintprog的调用格式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)该函数调用格式求解如下形式的0-1规划问题在前一个调用格式的基础上同时设置求解算法的初始解为x0,如果初始解x0不在0-1规划问题的可行域中,算法将采用默认的初始解5)x=bintprog(c,A,b,Aeq,beq,x0,options)用options指定的优化参数进行最小化。能够使用optimset来设置这些参数上面的函数调用格式仅设置了最优解这一输出参数,如果需要更多的输出参数,