文档介绍：最优化计算方法
一、实验目的
第一节线性规划问题的计算方法
1、了解线性规划问题及可行解、最优解的概念;
2、掌握Matlab软件关于求解线性规划的语句和方法。
二、实验原理和方法:
在生活实践中,很多重要的实际问题都是线性的(至少能
够用线性函数很好的近似表示),所以我们一般把这些问
题化为线性的目标函数和约束条件进行分析,通常将目标
函数和约束都是线性表达式的规划问题称为线性规划。
它的一般形式是:
也可以用矩阵形式来表示:
线性规划的可行解是满足约束条件的解;线性规划的最优解是使目标函数达到最优的可行解。
线性规划关于解的情况可以是:
1、无可行解,即不存在满足约束条件的解;
2、有唯一最优解,即在可行解中有唯一的最优解;
4、有可行解,但由于目标函数值无界而无最优解。
3、有无穷最优解,即在可行解中有无穷个解都可使目
标函数达到最优;
一般求解线性规划的常用方法是单纯形法和改进
的单纯形法,这类方法的基本思路是先求得一个可行
解,检验是否为最优解;若不是,可用迭代的方法找
到另一个更优的可行解,经过有限次迭代后,可以找
到可行解中的最优解或者判定无最优解。
三、内容与步骤:
在Matlab优化工具箱中,linprog函数是使用单纯形法求解
下述线性规划问题的函数。
它的命令格式为:
其中:A为约束条件矩阵,b,c分别为目标函数的系数向量和
约束条件中最右边的数值向量;也可设置解向量的上界vlb和
下界vub,即解向量必须满足vlb<=x<=vub;还可预先设置
初始解向量x0。
如果没有不等式,只有等式时,A=[ ],b=[ ];
输出的结果:x表示最优解向量;fval表示最优值。
【例 1】
求解线性规划问题:
解:考虑到linprog函数只解决形如
的线性规划。所以先要将线性规划
变为如下形式:
然后建立M文件如下:
c=[-3;1;1];A=[1 -2 1;4 -1 -2];b=[11;-3];
aeq=[2 0 -1];beq=-1;vlb=[0;0;0];
[x,fval]=linprog(c,A,b,aeq,beq,vlb)
以lianxi1作为文件名保存此M文件后,在命令窗口
输入lianxi1后即可得到结果:
x =
同时返回fval=-2
对应到原来的线性规划中即知目标函数的最大值为2,此时
x1=4,x2=1,x3=9。