MATLAB规划问题——线性规划和非线性规划
1.线性规划
求线性规划问题的最优解有两种方法,一种方法是使用linprog命令,另一种是使用optimtool工具箱,下面分别介绍这两种方法.
①linprog命令
一般情况下,Linprog命令的参数形式为[x,fval] = linprog(f,A,b,Aeq,beq,lb,ub,x0),下面分别介绍各参数的含义.
[x,fval]返回值中x为最优解,fval为最优值.
f表示目标函数中各个变量前面的系数向量,如果是求最小值问题,那么f就是各个变量的系数,如果是求最大值问题,那么f就是各个变量的系数的相反数.
A和b 表示不等式约束A*x <=b中的矩阵A和向量b.
Aeq和beq 表示等式约束Aeq*x =beq中的矩阵Aeq和向量beq.
lb和ub 分别表示自变量的上下界组成的向量,如果没有上下界,该选项用[]表示,如果只有部分变量有上下界,其余的变量没有,那么可以把没有上下界的变量的上下界设为-inf或者inf使lb或者ub的长度符合要求.
x0 表示变量的初始值,可以缺省.
例,求如下的线性规划问题
由目标函数可知f=[-5;-4;-6];
由约束条件可知矩阵A = [1 -11;3 2 4;3 2 0];右端向量为b = [20;42;30];
由自变量都大于零可知lb =[0;0;0];
所以求该线性规划问题最优解的代码如下
f = [-5;-4;-6];
A = [1 -1 1;3 24;3 2 0];
b = [20;42;30];
lb = [0;0;0];
[x,fval] =linprog(f,A,b,[],[],lb)
其中Aeq和beq都为空,因为没有等式约束条件,只有不等式约束条件.
②optimtool工具箱
在Command窗口输入optimtool,即可弹出optimtool工具箱,如下
工具箱可以大致分为5个部分.第5部分为说明文档,第4部分为优化选项,第3部分为最优解和最优值的显示区域,第2部分为约束条件输入区,第1部分可以填入目标函数值,初始值等.
利用工具箱求解①的问题,填入相应的数据,然后点击【start】按钮,得到结果如下
可以看到,最优解与linprog命令的方式求得的结果是相同的,但最优值不是-78,因为这是迭代的结果,只有在迭代次数区域无穷的时候,才能得到准确值-78.
再举一例,利用MATLAB求解下面这个线性规划问题
这是求最大值问题,要先将问题化为求解最小值的问题,再进行求解.
利用linprog命令求解上述问题的代码如下
f = [-2;-3;5];
A = [-2 5 -1];b= [-10];
Aeq = [1 11];beq = [7];
lb = [0;0;0];
[x,feval] = linprog(f,A,b,Aeq,beq,lb)
利用optimtool工具箱来求解过程如下图可以验证,两种求解方法的结果是相同的.最后取最优值为图中显示的最优值的相反数.
——————————————————————分割线——————————————————————
2.非线性规划
也有两种求解的方法,一种是fmincon命令,另一种是optimtool工具箱.
①fmincon命令
fmincon命令的一般参数形式为fmincon(‘fun’,x0,A,b,Aeq,beq,lb,ub,’nonlinearcondition’),其中各个参数含义如下
fun 目标函数(以求最小值为目标函数)
x0 最优解迭代的初始值
A,b 线性约束不等式A*x<= b
Aeq,beq 线性约束等式Aeq*x =beq
lb,ub 自变量的上下界
nonlinearcondition 非线性约束函数,它有两个返回值,其中一个为非线性不等式约
束,另一个是非线性等式约束(具体举例说明该项参数的设置)
在具体编写代码过程中,可以将线性约束也写在非线性约束函数nonlinearcondition中,简化代码.
例1,求下面这个非线性规划问题的最优值
首先,编写目标函数的M函数文件,并保存为fun.m代码如下
function f =fun(x)
f = x(1)^2 + x(2)^2 + 8;
end
其次,编写线性和非线性约束的等式或不等式,编写M函数文件,并保存为nonlinearcondition.m,代码如下
function [f,ceq] = nonlinearcondition(x)
f = - x(1)^2 + x(2);
ceq = - x(1) - x(2)^2 + 2; %非线性等式约束
end
最后,在Command窗口输入如下代码
[x,fval] =fmincon('fun',[0;0],[],[],[],[],[0;0],[],'nonlinearcondition')
即可得到最优值和最优解为x = [1;1],fval = 10.
例2,求下面这个非线性规划问题的最优值
首先,编写目标函数的M函数文件,由于求得是最大值,所以先化为求最小值问题,再原目标函数前面添加负号即可,M函数文件如下,保存为fun.m.
function f =fun(x)
f = -(sqrt(x(1)) + sqrt(x(2)) + sqrt(x(3)) +sqrt(x(4)));
end
然后,编写线性和非线性约束不等式已经非线性约束等式的M函数文件,保存为nonlinearcondition.m,代码如下
function [f,ceq]= nonlinearcondition(x)
%非线性和线性不等式有4个
f(1) =x(1) - 400;
f(2) =1.1*x(1) + x(2) - 440;
f(3) =1.21*x(1) + 1.1*x(2) + x(3) - 484;
f(4) =1.331*x(1) + 1.21*x(2) + 1.1*x(3) + x(4) - 532.4;
ceq = 0;%由于没有非线性约束等式,所以这一项写 0
end
最后,在Command窗口输入如下代码
[x,fval] =fmincon('fun',[0;0;0;0],[],[],[],[],[0;0;0;0],[],'nonlinearcondition')
即可得到最优解和最优值,最优值分别为
x =
86.1883
104.2879
126.1883
152.6879
fval = -43.0860
目标函数最优值为z = -fval=43.0860.
由于线性问题也可以看做是非线性问题的特殊情况,所以可用求解非线性问题的方法求解线性规划问题.例3,利用fmincon命令求解1.①中的线性规划问题
首先,编写目标函数的M函数文件,M函数文件如下,保存为fun.m.
function f =fun(x)
f = -5*x(1) - 4*x(2) - 6*x(3);
end
然后,编写线性和非线性约束不等式已经非线性约束等式的M函数文件,保存为nonlinearcondition.m,代码如下
function [f,ceq]= nonlinearcondition(x)
%由于有3个线性约束,所以f返回一个三维向量
f(1) =x(1) - x(2) + x(3) - 20;
f(2) =3*x(1) + 2*x(2) + 4*x(3) - 42;
f(3) =3*x(1) + 2*x(2) - 30;
ceq = 0;%没有非线性等式
end
最后,在Command窗口输入如下代码
[x,fval] =fmincon('fun',[0;0;0],[],[],[],[],[0;0;0],[],'nonlinearcondition')
得到的结果与1.线性规划问题的1.①中所用的线性方法所得结果相同.
②optimtool工具箱
同样,非线性规划也可以利用optimtool工具箱,因为其中有一项是填写非线性约束条件的,如下利用工具箱求解在2.①中的一个问题
首先,编写目标函数的M函数文件,由于求得是最大值,所以先化为求最小值问题,再原目标函数前面添加负号即可,M函数文件如下,保存为fun.m.
function f =fun(x)
f = -(sqrt(x(1)) + sqrt(x(2)) + sqrt(x(3)) +sqrt(x(4)));
end
然后,编写线性和非线性约束不等式已经非线性约束等式的M函数文件,保存为nonlinearcondition.m,代码如下
function [f,ceq]= nonlinearcondition(x)
%非线性和线性不等式有4个
f(1) =x(1) - 400;
f(2) =1.1*x(1) + x(2) - 440;
f(3) =1.21*x(1) + 1.1*x(2) + x(3) - 484;
f(4) =1.331*x(1) + 1.21*x(2) + 1.1*x(3) + x(4) - 532.4;
ceq = 0;%由于没有非线性约束等式,所以这一项写 0
end
在optimtool工具箱中输入相应参数,如下,即可得到相应结果所得结果与利用fmincon命令所得结果相同.
小结
规划问题中还有特殊的一些问题,例如特殊的线性规划问题——0-1规划,特殊的非线性规问题——二次规划问题,而线性规划问题又是特殊的非线性规划问题,所以这几种规划问题都可以用【非线性规划问题】求解.
参考文献
[1] 卓金武, 魏永生, 秦健, 李必文. MATLAB在数学建模中的应用[M]. 北京: 北京航空航天大学 2011: 18-24 .