上次介绍了回归模型,用到的方法主要是拟合和插值,如果把回归问题看成是预测问题的一类,其实我们还可以使用灰色预测和人工神经网络(ANN)等更高级的方法来进行求解。

本次主要介绍另一种比较常用的模型——规划模型。规划类问题是常见的数学建模问题,把一些优化问题进行离散化处理后就可以使用规划模型来进行求解,再加上这类问题占据了数学建模的“大片江山”,那么快速求解规划类问题就成为了参赛队员的基本素养。MATLAB作为一款强大的通用型数学软件,在处理这类问题上,也封装了一些标准函数,可以简单快速的得到所要的结果,但有一个缺点就是不直观、甚至有些难以理解,另一款专门用于求解规划问题的软件——Lingo就在方面做的好多了,这将会是下一次主要介绍的对象。所以,对于一个规划问题,首先选择的是Lingo,如果涉及到算法改进等方面才会去考虑用MATLAB,不过掌握基本的操作还是很必要的

这次主要介绍常见规划模型的MATLAB求解,包括线性规划、整数规划和非线性规划三个部分。一般说来,如果能熟练掌握这几部分的操作,可以解决绝大部分的规划模型的求解问题。对于像规划、优化这一类问题,除了有这些基本操作,还存在更“高级”的方法,如智能算法和计算机仿真等,这些会在后续介绍到,那就敬请期待吧。

线性规划

非线性规划

整数规划

数学规划是研究如何在有限资源的情况下取到最大效益的问题,是运筹学的一个重要分支,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。

事实上,线性规划对于我们来说已经是多年的“老朋友”了,在初高中就已经与它相遇了。那时,老师告诉我们,首先在纸上画一“十字架”,然后把各函数图像画上去,用笔或者尺子比划一下就可以得出答案了。承认这种方法简单方便,但是我们都已经不再是当年的“少年”了,我们有更好的工具了,追求的是自动化和系统化了,只希望几行代码就解决事。MATLAB在这方面做的还不错。由于MATLAB已经把规划模型给标准化了,我们就必须了解它是如何“理解”线性规划问题的。

规划问题无非就两类问题,目标函数的最大值和最小值问题。MATLAB很“聪明”,把两类问题合成了一类问题,也就是说在MATLAB中求解出来的是目标函数的最小值问题,那如果是最大值问题呢?目标函数前面添负号。

MATLAB中规定线性规划的标准形式为:

基本函数形式为linprog(c,A,b),它的返回值是向量x的值。还有其它的一些函数调用形式(在Matlab 指令窗运行help linprog 可以看到所有的函数调用形式),如:

1[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval 返回目标函数的值;Aeq和beq对应等式Ax = b;LB 和UB 分别是变量x的下界和上界;x0是x的初始值;OPTIONS 是控制参数。

如果是求解目标函数最大值问题

看如下一个例子:求解线性规划问题:

1c = [2;3;1];2a = [1,4,2;3,2,0];3b = [8,6];4[x,y] = linprog(c,-a,-b,[],[],zeros(3,1))输出结果为:

再来看一个例子:

1format long2f = [-170.8582 17.7254 -41.2582 -2.2182 -131.8182 ];3A = [1 -0.17037 -0.5324 0 1 0;0 0.17037 0.5324 0 0 0;1 0.32 1 0 0 0;0 1 0 0 0 0;0 0 1 1 0 0;0 0 0 -1 -1 0];4b = [0;888115;166805;521265.625;683400;-660000];5Aeq = [0 0 0 0 0 1];6beq = [1];7lb = [0;0;0;0;0;0];8[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb,[])结果为:

如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题,简称NP。一般说来,解非线性规划要比解线性规划问题困难得多。而且,也不像线性规划有单纯形法这一通用方法,非线性规划目前还没有适于各种问题的一般算法,各个方法都有自己特定的适用范围。

MATLAB 中非线性规划的数学模型写成以下形式:

1X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x,其中FUN 是用M 文件定义的函数f(x);X0 是x的初始值;A,B,Aeq,Beq 定义了线性约束A* X ≤ B, Aeq * X = Beq ,如果没有线性约束,则A=[],B=[],Aeq=[],Beq=[];LB 和UB 是变量x的下界和上界,如果上界和下界没有约束,则LB=[],UB=[],如果x无下界,则LB 的各分量都为-inf,如果x无上界,则UB的各分量都为inf;NONLCON 是用M 文件定义的非线性向量函数C(x),Ceq(x);OPTIONS定义了优化参数,可以使用Matlab 缺省的参数设置。

看如下一个例子:

1function f = fun00(x)2f = -(sqrt(x(1)) + sqrt(x(2))+ sqrt(x(3))+ sqrt(x(4)));3end编写M文件,定义约束条件:

1function[g,ceq] = mycon0(x)2g(1) = x(1)-400;3g(2) = 1.1*x(1) + x(2) - 440;4g(3) = 1.21*x(1) +1.1* x(2) + x(3) - 480;5g(4) = 1.331*x(1) +1.21*x(2)+1.1*x(3)+x(4) - 532.4;6ceq = 0;7end编写主程序:

1x0 = [1;1;1;1];2lb = [0;0;0;0];3ub =[];4A = [];5b = [];6Aeq = [];7beq =[];8[x,fval] = fmincon('fun00',x0,A,b,Aeq,beq,lb,ub,'mycon0')结果为:

若某非线性规划的目标函数为自变量x 的二次函数,约束条件又全是线性的,就称这种规划为二次规划,这一类规划问题比较特殊,MATLAB专门有函数求解,简单介绍一下。

MATLAB 中二次规划的数学模型可表述如下:

1[X,FVAL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)返回值X 是决策向量x的值,返回值FVAL 是目标函数在x处的值。(具体细节可以参看在Matlab 指令中运行help quadprog 后的帮助)。

看如下一个例子:

1h = [4,-4;-4,8];2f = [-6;-3];3a = [1,1;4,1];4b = [3;9];5[x,value] = quadprog(h,f,a,b,[],[],zeros(2,1))结果:

利用罚函数法,可将非线性规划问题的求解,转化为求解一系列无约束极值问题,因而也称这种方法为序列无约束最小化技术,简记为SUMT (Sequential Unconstrained Minization Technique)。

罚函数法求解非线性规划问题的思想是,利用问题中的约束函数作出适当的罚函数,由此构造出带参数的增广目标函数,把问题转化为无约束非线性规划问题。主要有两种形式,一种叫外罚函数法,另一种叫内罚函数法,下面介绍外罚函数法。考虑问题:

看如下一个例子:

1function g =test0(x)2M = 50000;3f = x(1)^2 + x(2)^2 +8;4g = f - M*min(x(1),0) - M*min(x(2),0) - M*min(x(1)^2 - x(2),0 + M*abs(-x(1) - x(2)^2 + 2));5end6在MATLAB命令行窗口输入:

1 [x,y] = fminunc('test0',rand(2,1))即可求出答案。

规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。因此下面简单介绍几种整数规划类型和求解方法。

0 −1型整数规划是整数规划中的特殊情形,它的变量xj仅取值0 或1。这时xj称为0 −1变量,或称二进制变量。xj仅取值0 或1 这个条件可由下述约束条件:0 ≤ xj≤ 1,整数所代替,是和一般整数规划的约束条件形式一致的。在实际问题中,如果引入0 −1变量,就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。看如下一个例子并给出了思路:

先试探性求一个可行解,易看出(x1, x2, x3)= (1 0 , 0 , )满足约束条件,故为一个可行解,且z = 3。

因为是求极大值问题,故求最优解时,凡是目标值z < 3的解不必检验是否满足约束条件即可删除,因它肯定不是最优解,于是应增加一个约束条件(目标值下界):

改进过滤条件。

由于对每个组合首先计算目标值以验证过滤条件,故应优先计算目标值z大的组合,这样可提前抬高过滤门槛,以减少计算量。

按上述思路,最后求解得:

非线性规划的求解本身就是一个难题,更何况非线性整数规划呢.目前对于非线性整数规划尚未有一种成熟而准确的求解方法,但是考虑到整数解是有限个,因而可以考虑枚举法。当然,当自变量维数很大和取值范围很宽情况下,企图用显枚举法(即穷举法)计算出最优值是不现实的,但是应用概率理论可以证明,在一定的计算量的情况下,完全可以得出一个满意解。

考虑如下一个问题:

首先编写M 文件mente.m定义目标函数f 和约束向量函数g,程序如下:

1function [f,g]=mente(x)2f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-...3x(4)-2*x(5);4g=[sum(x)-4005x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-80062*x(1)+x(2)+6*x(3)-2007x(3)+x(4)+5*x(5)-200];8end编写M文件ainint.m如下求问题的解:

1rand('state',sum(clock)); 2p0=0; 3tic 4for i=1:10^6 5    x=99*rand(5,1); 6    x1=floor(x);x2=ceil(x); 7    [f,g]=mente(x1); 8    if sum(g<=0)==4 9        if p0<=f10            x0=x1;p0=f;11        end12    end13    [f,g]=mente(x2);14    if sum(g<=0)==415        if p0<=f16            x0=x2;p0=f;17        end18    end19end20x0,p021toc由于是随机取样,因而每次运行的结果可以不一样,但差别不大。

编辑不易,欢迎推广