MATLAB求解线性规划问题

第七章最优化计算方法一、实验目的：第一节线性方程组的应用1、了解线性规划问题及可行解、最优解的概念；2、掌握Matlab软件关于求解线性规划的语句和方法。二、实验原理和方法：在生活实践中，很多重要的实际问题都是线性的（至少能够用线性函数很好的近似表示），所以我们一般把这些问题化为线性的目标函数和约束条件进行分析，通常将目标函数和约束都是线性表达式的规划问题称为线性规划。它的一般形式是：)n,,2,1i(0xbxaxaxabxaxaxabxaxaxa.t.sxcxcxcfminimnmn22m11m2nn22221211nn1212111nn2211也可以用矩阵形式来表示：0x,bAx.t.sxcfminT线性规划的可行解是满足约束条件的解；线性规划的最优解是使目标函数达到最优的可行解。线性规划关于解的情况可以是：1、无可行解，即不存在满足约束条件的解；2、有唯一最优解，即在可行解中有唯一的最有解；4、有可行解，但由于目标函数值无界而无最优解。3、有无穷最优解，即在可行解中有无穷个解都可使目标函数达到最优；一般求解线性规划的常用方法是单纯形法和改进的单纯形法，这类方法的基本思路是先求得一个可行解，检验是否为最优解；若不是，可用迭代的方法找到另一个更优的可行解，经过有限次迭代后，可以找到可行解中的最优解或者判定无最优解。三、内容与步骤：在Matlab优化工具箱中，linprog函数是使用单纯形法求解下述线性规划问题的函数。vubxvlbbeqaeqxbAxtsxcfT;,..min它的命令格式为：)0,,,,,,,(],[),,,,,,(],[xvubvlbbeqaeqbAclinprogfvalxvubvlbbeqaeqbAclinprogfvalx其中：A为约束条件矩阵，b,c分别为目标函数的系数向量和约束条件中最右边的数值向量；也可设置解向量的上界vlb和下界vub，即解向量必须满足vlb=x=vub；还可预先设置初始解向量x0。如没有不等式，而只有等式时，A=[],b=[];输出的结果：x表示最优解向量；fval表示最优值。【例1】求解线性规划问题：3,2,1i,0x1xx23x2xx411xx2x.t.sxxx3fmaxi31321321321解：考虑到linprog函数只解决形如的线性规划。所以先要将线性规划变为如下形式：0;,..minxbeqaeqxbAxtsxcfT3,2,1i,0x3x2xx411xx2x1xx2.t.sxxx3fmini32132131321然后建立M文件如下：c=[-3;1;1];A=[1-21;4-1-2];b=[11;-3];aeq=[20-1];beq=-1;vlb=[0;0;0];[x,fval]=linprog(c,A,b,aeq,beq,vlb)Matlab程序：ch701.m以ch701作为文件名保存此M文件后，在命令窗口输入ch701后即可得到结果：x=4.00001.00009.0000同时返回fval=-2对应到原来的线性规划中即知目标函数的最大值为2，此时x1=4,x2=1,x3=9。第二节无约束规划计算方法一、实验目的1、了解无约束规划问题的求解原理与方法；2、会用Matlab软件求解无约束规划问题。二、实验原理和方法无约束规划问题的解法一般按目标函数的形式分为两大类：一类是一元函数的一维搜索法，如黄金分割法、插值法等；另一类是求解多元函数的下降迭代法。迭代的基本思想和步骤大致可分为以下四步：继续迭代返回否则，令如果是，则结束运算；优解。是否满足精度要求的最检验新得到的点由此得到下一个点使得方向选取适当的步长出发，沿由）的值时下降的；目标函数使得沿着这个方向的后，选取一个搜索方向得到并令选取初始点)2(,1)4)()(,3)(,)2;0,)1110kkxPxxxfPxfPxxfPxkxkkkkkkkkkkkkkk三、实验内容与步骤在Matlab软件中，求解无约束规划的常用命令是：x=fminunc(‘fun’,x0)其中，fun函数应预先定义到M文件中，并设置初始解向量为x0。【例2】求解1212221x2xxx21x23)x(fmin取T)0()4,2(x解：首先建立函数文件fun702.m)1(2)2()1(2)^2(2/12)^1(2/3)(702xxxxxfxfunffunction以fun702为文件名保存此函数文件。在命令窗口输入：x0=[-2;4];x=fminunc('fun702',x0)结果显示：f=-1.0000x=1.00001.0000即极小值为-1，是x1=1,x2=1时取得。Matlab程序：ch702.m【例3】解非线性方程组01)5.0()2(012221221xxxx解：解此非线性方程组等价于求解无约束非线性规划问题：222212221)1)5.0()2(()1(minxxxx然后建立函数文件fun703.m2)^12)^5.0)2((2)^2)1(((2)^1)2(2)^1(()(703xxxxfxfunffunction在命令窗口输入：x0=[0;0];x=fminunc(‘fun703’,x0)结果显示：f=5.2979e-011x=1.06730.1392则非线性方程组的解为x1=1.0673,x2=0.1392。Matlab程序：ch703.m第三节约束非线性规划计算方法一、实验目的1、了解约束非线性规划问题的求解原理与方法；2、会用Matlab软件求解约束非线性规划问题。二、实验原理和方法对于约束非线性规划，随着目标函数和约束条件的不同，解法也不同，一般来说，有两类方法：（1）、将约束问题化为无约束问题的求解方法；（2）、用线性规划来逼近非线性规划；三、实验内容与步骤约束非线性规划的一般形式为：)(minxfxubxlbxceqxgbeqxaeqbAxts）（非线性约束线性约束0)(,0)()(*,.其中，f(x)为多元实值函数;g(x)为向量函数,并且f(x),g(x)中至少有一个函数是非线性函数的（否则成为线性规划问题）。x=fmincon(‘fun’,x0,A,b)x=fmincon(‘fun’,x0,A,b,Aeq,beq)x=fmincon(‘fun’,x0,A,b,Aeq,beq,lb,ub)x=fmincon(‘fun’,x0,A,b,Aeq,beq,lb,ub,nonlcon)在Matlab优化工具箱中，fmincon函数是用SQP算法来解决一般的约束非线性规划的函数，它的命令格式为：【例4】求解约束非线性规划：3..)3(max222222111xetsxexexxx(初值为[1;1])解:首先建立一个m文件fun7041.mfunctiony=fun7041(x)y=-exp(x(1))*x(2)^2*(3-exp(x(1))-x(2)^2);存储为fun7041.m首先将问题转化为matlab要求的格式;即求出fun,A,b,Aeq,Beq,X0,Lb,Ub然后建立一个m文件fun7042.mfunction[c,cep]=fun7042(x)c=[];%c为非线性不等式,且为c=0cep=exp(x(1))+x(2)^2-3;%cep为非线性等式然后存储为fun7042.m最后在命令窗口中输入：A=[];b=[];Aeq=[];Beq=[];Lb=[];Ub=[];[x,f]=fmincon(‘fun7041’,[1;1],[],[],[],[],[],[],’fun7042’)-f因题目中有非线性约束条件，所以建立非线性约束m-文件。Matlab程序：ch704.m结果为:x=0.88520.7592f=6.2043e-016ans=-6.2043e-016最后的结果为:-6.2043e-016【例5】求解约束非线性规划：]1;1;1;1[0102335..)4()3()2()1(min4321432124232221初值为ixxxxxxxxxtsxxxx解：首先建立一个m文件fun705.mfunctiony=fun705(x)y=(x(1)-1)^2+(x(2)-2)^2+(x(3)-3)^2+(x(4)-4)^2;存储为fun705.m文件.x0=[1;1;1;1];A=[1111;3321];B=[5;10];Aeq=[];Beq=[];Lb=[0;0;0;0];[x,g]=fmincon(‘fun705’,x0,A,B,Aeq,Beq,Lb)答案为:x=0.00000.66671.66652.6668g=6.3333Matlab程序：ch705.m