线性规划问题的matlab求解

用matlab求解线性规划问题

线性规划问题

线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB6.0解决的线性规划问题的标准形式为：

min f(x) x属于R

sub.to： A*x<=b;

Aeq*x=beq;

lb<=x<=ub;

其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵。

其它形式的线性规划问题都可经过适当变换化为此标准形式。

在MATLAB6.0版中，线性规划问题（Linear Programming）已用函数linprog取代了MATLAB5.x版中的lp函数。当然，由于版本的向下兼容性，一般说来，低版本中的函数在6.0版中仍可使用。

函数 linprog

格式 x = linprog(f,A,b) %求min f ' *x sub.to 线性规划的最优解。 x = linprog(f,A,b,Aeq,beq) %等式约束，若没有不等式约束 ，则A=[ ]，b=[ ]。 x = linprog(f,A,b,Aeq,beq,lb,ub) %指定x的范围 ，若没有等式约束 ，则Aeq=[ ]，beq=[ ]

x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值x0

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) % options为指定的优化参数

[x,fval] = linprog(…) % 返回目标函数最优值，即fval= f ' *x。

[x,lambda,exitflag] = linprog(…) % lambda为解x的Lagrange乘子。

[x, lambda,fval,exitflag] = linprog(…) % exitflag为终止迭代的错误条件。

[x,fval, lambda,exitflag,output] = linprog(…) % output为关于优化的一些信息

说明 若exitflag>0表示函数收敛于解x，exitflag=0表示超过函数估值或迭代的最大数字，exitflag<0表示函数不收敛于解x；若lambda=lower 表示下界lb，lambda=upper表示上界ub，lambda=ineqlin表示不等式约束，

用matlab求解线性规划问题

lambda=eqlin表示等式约束，lambda中的非0元素表示对应的约束是有效约束；output=iterations表示迭代次数，output=algorithm表示使用的运算规则，output=cgiterations表示PCG迭代次数。

例5-1 求下面的优化问题

min -5*x1－4*x2-6*x3

sub.to x1-x2+x3<=20

3*x1+2*x2+4*x3<=42

3*x1+2*x2<=30

0<=x1;0<=x2;0<=x3;

解：

>>f = [-5; -4; -6];

>>A = [1 -1 1;3 2 4;3 2 0];

>>b = [20; 42; 30];

>>lb = zeros(3,1);

>>[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb) 结果为：

x = %最优解

0.0000

15.0000

3.0000

fval = %最优值

-78.0000

exitflag = %收敛

1

output =

iterations: 6 %迭代次数

cgiterations: 0

algorithm: 'lipsol' %所使用规则

lambda =

用matlab求解线性规划问题

ineqlin: [3x1 double]

eqlin: [0x1 double]

upper: [3x1 double]

lower: [3x1 double]

>> lambda.ineqlin

ans =

0.0000

1.5000

0.5000

>> lambda.lower

ans =

1.0000

0.0000

0.0000

表明：不等约束条件2和3以及第1个下界是有效的.

有约束的一元函数的最小值

单变量函数求最小值的标准形式为 min f(x) sub.to x1<x<x2 在MATLAB5.x中使用fmin函数求其最小值。

函数 fminbnd

格式 x = fminbnd(fun,x1,x2) %返回自变量x在区间 上函数fun取最小值时x值，fun为目标函数的表达式字符串或MATLAB自定义函数的函数柄。 x = fminbnd(fun,x1,x2,options) % options为指定优化参数选项

[x,fval] = fminbnd(…) % fval为目标函数的最小值

[x,fval,exitflag] = fminbnd(…) %xitflag为终止迭代的条件

用matlab求解线性规划问题

[x,fval,exitflag,output] = fminbnd(…) % output为优化信息

说明 若参数exitflag>0，表示函数收敛于x，若exitflag=0，表示超过函数估计值或迭代的最大数字，exitflag<0表示函数不收敛于x；若参数output=iterations表示迭代次数，output=funccount表示函数赋值次数，output=algorithm表示所使用的算法。

例5-3 在[0，5]上求下面函数的最小值

f(x)=(x-3)^2-1

解：先自定义函数：在MATLAB编辑器中建立M文件为：

function f = myfun(x)

f = (x-3).^2- 1;

保存为myfun.m，然后在命令窗口键入命令：

>> x=fminbnd(@myfun,0,5)

则结果显示为：

x =

3

无约束多元函数最小值

多元函数最小值的标准形式为 min f(x)

其中：x为向量，如

在MATLAB5.x中使用fmins求其最小值。

命令 利用函数fminsearch求无约束多元函数最小值

函数 fminsearch

格式 x = fminsearch(fun,x0) %x0为初始点，fun为目标函数的表达式字符串或MATLAB自定义函数的函数柄。

用matlab求解线性规划问题

x = fminsearch(fun,x0,options) % options查optimset

[x,fval] = fminsearch(…) %最优点的函数值

[x,fval,exitflag] = fminsearch(…) % exitflag与单变量情形一致

[x,fval,exitflag,output] = fminsearch(…) %output与单变量情形一致 注意：fminsearch采用了Nelder-Mead型简单搜寻法。

命令 利用函数fminunc求多变量无约束函数最小值

函数 fminunc

格式 x = fminunc(fun,x0) %返回给定初始点x0的最小函数值点

x = fminunc(fun,x0,options) % options为指定优化参数

[x,fval] = fminunc(…) %fval最优点x处的函数值

[x,fval,exitflag] = fminunc(…) % exitflag为终止迭代的条件，与上同。

[x,fval,exitflag,output] = fminunc(…) %output为输出优化信息

[x,fval,exitflag,output,grad] = fminunc(…) % grad为函数在解x处的梯度值

[x,fval,exitflag,output,grad,hessian] = fminunc(…) %目标函数在解x处的海赛（Hessian）值

注意：当函数的阶数大于2时，使用fminunc比fminsearch更有效，但当所选函数高度不连续时，使用fminsearch效果较好。

例5-5 求 f(x)=3*x1^2+2*x1*x2+x2^2 的最小值。

>> fun='3*x(1)^2+2*x(1)*x(2)+x(2)^2';

>> x0=[1 1];

>> [x,fval,exitflag,output,grad,hessian]=fminunc(fun,x0) 结果为：

x =

1.0e-008 *

-0.7591 0.2665

fval =

1.3953e-016

exitflag =

用matlab求解线性规划问题

1

output =

iterations: 3

funcCount: 16

stepsize: 1.2353

firstorderopt: 1.6772e-007

algorithm: 'medium-scale: Quasi-Newton line search' grad =

1.0e-006 *

-0.1677

0.0114

hessian =

6.0000 2.0000

2.0000 2.0000

或用下面方法：

>> fun=inline('3*x(1)^2+2*x(1)*x(2)+x(2)^2')

fun =

Inline function:

fun(x) = 3*x(1)^2+2*x(1)*x(2)+x(2)^2

>> x0=[1 1]；

>> x=fminunc(fun,x0)

x =

1.0e-008 *

-0.7591 0.2665

用matlab求解线性规划问题

有约束的多元函数最小值

非线性有约束的多元函数的标准形式为：

min f(x)

sub.to C(x)<=0

Ceq(x)=0

A*x<=b

Aeq*x=beq

lb<=x<=ub

其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是返回向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。

在MATLAB5.x中，它的求解由函数constr实现。

函数 fmincon

格式 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)

x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)

[x,fval] = fmincon(…)

[x,fval,exitflag] = fmincon(…)

[x,fval,exitflag,output] = fmincon(…)

[x,fval,exitflag,output,lambda] = fmincon(…)

[x,fval,exitflag,output,lambda,grad] = fmincon(…)

[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(…)

参数说明：fun为目标函数，它可用前面的方法定义；

用matlab求解线性规划问题

x0为初始值；

A、b满足线性不等式约束 ，若没有不等式约束，则取A=[ ]，b=[ ]； Aeq、beq满足等式约束 ，若没有，则取Aeq=[ ]，beq=[ ]；

lb、ub满足 ，若没有界，可设lb=[ ]，ub=[ ]；

nonlcon的作用是通过接受的向量x来计算非线性不等约束 和等式约束 分别在x处的估计C和Ceq，通过指定函数柄来使用，如：>>x =

fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon)，先建立非线性约束函数，并保存为mycon.m：function [C,Ceq] = mycon(x)

C = … % 计算x处的非线性不等约束 的函数值。

Ceq = … % 计算x处的非线性等式约束 的函数值。

lambda是Lagrange乘子，它体现哪一个约束有效。

output输出优化信息；

grad表示目标函数在x处的梯度；

hessian表示目标函数在x处的Hessiab值。

例5-6 求下面问题在初始点（0，1）处的最优解

min x1^2+x2^2-x1*x2-2*x1-5*x2

sub.to -(x1-1)^2+x2>=0

2*x1-3*x2+6>=0

解：约束条件的标准形式为

sub.to (x1-1)^2-x2<=0

-2*x1+3*x2-6<=0

先在MATLAB编辑器中建立非线性约束函数文件：

function [c, ceq]=mycon (x)

c=(x(1)-1)^2-x(2);

ceq=[ ]; %无等式约束

然后，在命令窗口键入如下命令或建立M文件：

>>fun='x(1)^2+x(2)^2-x(1)*x(2)-2*x(1)-5*x(2)'; %目标

用matlab求解线性规划问题

函数

>>x0=[0 1];

>>A=[-2 3]; %线性不等式约束

>>b=6;

>>Aeq=[ ]; %无线性等式约束

>>beq=[ ];

>>lb=[ ]; %x没有下、上界

>>ub=[ ];

>>[x,fval,exitflag,output,lambda,grad,hessian]

=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,@mycon)

则结果为

x =

3 4

fval =

-13

exitflag = %解收敛

1

output =

iterations: 2

funcCount: 9

stepsize: 1

algorithm: 'medium-scale: SQP, Quasi-Newton, line-search' firstorderopt: [ ]

cgiterations: [ ]

lambda =

lower: [2x1 double] %x下界有效情况，通过lambda.lower可查看。 upper: [2x1 double] %x上界有效情况，为0表示约束无效。

eqlin: [0x1 double] %线性等式约束有效情况，不为0表示约束有效。 eqnonlin: [0x1 double] %非线性等式约束有效情况。

用matlab求解线性规划问题

ineqlin: 2.5081e-008 %线性不等式约束有效情况。 ineqnonlin: 6.1938e-008 %非线性不等式约束有效情况。 grad = %目标函数在最小值点的梯度

1.0e-006 *

-0.1776

hessian = %目标函数在最小值点的Hessian值

1.0000 -0.0000

-0.0000 1.0000

例5-7 求下面问题在初始点x=(10, 10, 10)处的最优解。 Min f(x)=-x1*x2*x3

Sub.to 0<=x1+2*x2+2*x3<=72

解：约束条件的标准形式为

sub.to -1*x1-2*x2-2*x3<=0

x1+2*x2+2*x3<=72

>> fun= '-x(1)*x(2)*x(3)';

>> x0=[10,10,10];

>> A=[-1 -2 -2;1 2 2];

>> b=[0;72];

>> [x,fval]=fmincon(fun,x0,A,b)

结果为：

x =

24.0000 12.0000 12.0000

fval =

-3456