线性规划
LP(Linear programming,线性规划)是一种优化方法,在优化问题中目标函数和约束函数均为向量变量的线性函数,LP问题可描述为:
min x
s.t.
A·x b
Aeq·x=beq
vlb x vub
其中 ，b,beq均为向量，A,Aeq为矩阵，x为向量变量.矩阵A和向量b是线性不等式约束条件的系数，Aeq和beq是等式约束条件的系数.
在MATLAB中，用于LP的求解函数为linprog.其调用格式为：
[x,fval,lambda]=linprog
(f,A,b,Aeq,beq,vlb,vub,x0,options)
其中f,A,b,是不可缺省的输入变量，x是不可缺省的输出变量，它是问题的解.vlb,vub均是向量，分别表示x的下界和上界，x0为x的起始点，options为optimset函数中定义的参数的值，fval是目标函
数在解x处的值，lambda为在解x处的lagrange乘子.lambda.lower对应于vlb，lambda.upper对应于ulb，lambda.ineqlin是对应于线性不等式约束的，lambda.eqlin是对应于线性等式约束的.
下面举一个小例子看看函数的作用：
minZ=-4a+b+7c
s.t.
a+b-c=5 3a-b+c<=4
a+b-4c<=-7 a,b>=0
问a，b，c分别取何值时，Z有最小值
编写M文件
c=[-4 1 7];
A=[3 -1 1;1 1 -4];
b=[4; -7];
Aeq=[1 1 -1];
beq=[5];vlb=[0, 0];
vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
结果：x = 2.2500 6.7500 4.0000fval = 25.7500
即a，b，c分别取2.2500 6.7500 4.0000时，Z有最小值25.7500
更加详细的例子如下，因为上面没有讲明最大值与最小值的区别，补充如下：
函数格式:linprog(f,a,b,a1,b1,xstart,xend)
f:求解最小函数的表达式系数矩阵是m*1的矩阵
a:≤不等式条件约束矩阵其均为形式
b:a对应不等式右边的常数项
a1:=等式条件约束矩阵
b1:a1对应不等式右边的常数项
xstart:x的取值范围的最小值的系数矩阵为n*1的矩阵
xend:x的取值范围的最大值的系数矩阵为n*1的矩阵
函数说明:不存在的项填写[]即可
函数功能:线性规划求最优值.
例子1:
求f=3*x1+6*x2+2*x3的最大值
满足的条件是
3*x1+4*x2+x3≤2
x1+3*x2+2*x3≤1
且x1、x2、x3均大于等于0
Matlab求解如下
a =[ 3 4 1
1 3 2 ]
b =[ 2
1 ]
f=[ -3
-6
-2 ]%这里为什么会是负数,因为Matlab求的是f的最小值,要求最大值则取要求系数的相反数即可.
x=[ 0
0
0 ]
linprog(f,a,b,[],[],x,[])%执行的matlab命令后输出的如下内容.注意这里的[]表示那一项不存在.当然最后那一个[]也可以不要即linprog(f,a,b,[],[],x)
Optimization terminated.
ans =
0.4000
0.2000
0.0000%即x1=0.4,x2=0.2,x3=0为最优解.带回原式我可以知道f的最大值=3*0.4+6*0.2=2.4
例子2:
求f=-2*x1-3*x2-x3的最小值
满足的条件是
x1+x2+x3≤3
x1+4*x2+7*x3+x4=9
且x1、x2、x3、x4均大于等于0
Matlab求解如下
原题等价于求f=-2*x1-3*x2-x3+0*x4的最小值
其条件等价于
x1+x2+x3+0*x4≤3
x1+4*x2+7*x3+x4=9
则在Matlab输入如下内容
a=[1 1 1 0]
b=[3]
a1=[1 4 7 1]
b1=[9]
x=[ 0
0
0
0]
f=[ -2
-3
-1
0]
linprog(f,a,b,a1,b1,x)%执行命令或者输入linprog(f,a,b,a1,b1,x,[])
Optimization terminated.
ans =
1.0000
2.0000
0.0000
0.0000%说明x1=1,x2=2,x3=0,x4=0取得最小值