1.线性规划的求解方法

线性规划问题的标准形式为：

或者写成矩阵形式：

一般来说线性规划包括单纯形规划和多目标规划

1.1单纯形线性规划

单纯形法时从所有基本的可行解的一个较小部分中通过迭代过程选出最优解

matlab中求解线性规划的函数时linprog,使用方法如下：

一般情况下，Linprog命令的参数形式为[x,fval] = linprog(f,A,b,Aeq,beq,lb,ub,x0)，下面分别介绍各参数的含义.

[x,fval,exitflag,output,lamnda]：返回值中x为最优解，fval为最优值,output包含优化信息的输出变量

f：表示目标函数中各个变量前面的系数向量，如果是求最小值问题，那么f就是各个变量的系数，如果是求最大值问题，那么f就是各个变量的系数的相反数.

A,b:表示不等式约束

中的矩阵A和向量b,若不存在不等式关系

Aeq,beq:表示线性等式约束Aeq*x =beq中的矩阵Aeq和向量beq，若等式约束不存在则令Aeq=[ ],beq=[ ]

lb,ub :分别表示自变量的上下界组成的向量，如果没有上下界，该选项用[]表示，如果只有部分变量有上下界，其余的变量没有，那么可以把没有上下界的变量的上下界设为-inf或者inf使lb或者ub的长度符合要求.

x0:表示变量的初始值，可以缺省。

有如下例子：

由于没有等式约束，所以Aeq=[ ],beq=[ ]

不等式的条件系数为：

由于没有上界要求：

clear all

clc

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

exitflag =1表示正常收敛于解x处。

1.2 多目标线性规划

多目标线性规划有着两个或两个以上的目标函数

约束条件为：

给出如下例子：

1.2.1 理想点法

先求解r个单目标问题，设其最优值分别为

,称为值域中的一个理想点，寻求距离

最近的Z作为近似值，最直接的方法就是构造最短距离理想点法，构造评价函数：

然后最小化评价函数，将他的最优解

作为最优解.

在matlab中流程如下，先单个求解

clear all

clc

f=[3;-2];

A=[2,3;2,1];

b=[18;10];

lb=[0;0];

[x,fval]=linprog(f,A,b,[],[],lb)

>>

fval =

-12.0000

clear all

clc

f=[-4;-3];

A=[2,3;2,1];

b=[18;10];

lb=[0;0];

[x,fval]=linprog(f,A,b,[],[],lb)

>>

fval =

-24.0000

于是得到理想点(12，24)

然后求解如下模型：

clear all

clc

A = [2,3;2,1];

b = [18,10];

x0 = [1,1];

lb = [0,0];

x = fmincon('((-3*x(1)+2*x(2)-12)^2+(4*x(1)+3*x(2)-24)^2)^(1/2)',x0,A,b,[],[],lb,[])

>>

x =

0.5268 5.6488

得到最优的x

1.2.2 线性加权和方法

人们总希望给重要的指标较大的权重，将多目标问题转化为了所有目标加权求和的单目标问题

构造评价函数如下：

对于前面例子权重系数分别取0.5和0.5，进行求解

clear all

clc

f=[-0.5;-2.5];

A=[2,3;2,1];

b=[18;10];

lb=[0;0];

[x,fval]=linprog(f,A,b,[],[],lb)

>>

x =

0.0000

6.0000

fval =

-15.0000

1.2.3 最大最小法

在决策时采用保守策略时最为稳妥的，在最坏的情况下，寻求最好的结果，可以构造如下的评价函数

然后求解

function f = ex1019(x)

f(1) = 3*x(1)-2*x(2);

f(2) = -4*x(1)-3*x(2);

clear all

clc

x0=[1;1];

A=[2,3;2,1];

b=[18;10];

lb=zeros(2,1);

[x,fval]=fminimax('ex1019',x0,A,b,[],[],lb,[]) %这里使用fminimax函数

1.3 整数规划

当在实际问题中，部分自变量取整数时可以使用整数规划的方法，通过调用matlab中的intlinprog()实现,调用格式如下：

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options)：需要注意其中的intcon，intcon = [1,2,7] 表示 x(1), x(2), x(7) 只能取整数

给出例子如下：

clc

clear all

intcon = 3;

f = [-3;-2;-1];

A = [1,1,1];

b = 7;

Aeq = [4,2,1];

beq = 12;

lb = zeros(3,1);

ub = [Inf,Inf,1]; % x3的上界为1保证x3只能取0，1

[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);

x

fval

>>

x =

0

5.5000

1.0000

fval =

-12.0000

2.非线性规划

非线性规划安约束条件可以分为以下三类：

无约束非线性规划

等式约束非线性规划

不等式约束非线性规划

2.1 非线性规划的标准形式

2.2 二次规划

非线性规划的目标函数为自变量的二次函数，约束条件全是线性函数，这种规划称为二次规划。

其标准数学模型为：

其中

为矩阵，其余为列向量

matlab中利用quadprog求解二次规划问题，调用格式为：

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options): 其中lb,ub为上下界，options为指定优化方法。

[x,fval,exitflag,output,lambda] = quadprog(...): 基本与此前函数类似，其中lambda为拉格朗日函数的乘子。

【例】求解以下最优化问题

目标函数为：

目标函数可以修改为：

其中：

clc

clear all

H = [1,-1;-1,2];

f = [-2,-6];

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

b = [27,2,3];

lb = [0,0];

[x,fval,exitflag] = quadprog(H,f,A,b,[],[],lb,[]);

x

fval

>>

x =

0.8000

1.4000

fval =

-8.8400

2.3 无约束规划

1. fminbnd函数

用来求固定区间内单变量函数的最小值

其调用格式如下：

x = fminbnd(fun,x1,x2,options,p1,p2...) : 其中x1,x2为区间，options为优化方法，如果没有options，令options = [ ].

[x,fval,exitflag,output] = fminbnd(...) :与之前函数类似

clc

clear all

[x,f_min] = fminbnd('sin(2*x)',0,2pi);

2. fminsearch函数

用于求多变量无约束的函数的最小值，格式为：

[x,fval,exitflag,options] = fminsearch(fun,x0,options): x0为初值

【注意】：

对于求解二次以上问题，fminunc更加有效，但对于高度非线性不连续问题则相反

fminsearch不适合求平方和问题，lsqnonlin更有效

3. fminunc函数(重要)

常用于求多变量无约束的函数的最小值

[x,fval,exitflag,output,grad,hessian] = fminunc(fun,x0,options): grad是解x处的梯度值，hessian将解x处的Hessian矩阵返回

clear all

clc

x0=[-1.2,1];

[x,fval]=fminunc('100*(x(2)-x(1)^2)^2+(1-x(1))^2',x0)

>>

x =

1.0000 1.0000

fval =

2.8336e-11

2.4 有约束规划

1. fmincon函数

求解多变量有约束的非线性函数的最小值，调用格式如下：

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

x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,noncon,options) ：其中noncon是计算非线性等式约束

和非线性不等式约束

给出丧心病狂的例子如下：

【例】

创建目标函数：

function f = ex10_6a(x)

f = x(1)*x(1)*(x(2)+2)*x(3);

创建非线性约束条件函数：

function[c,ceq] = ex10_6b(x)

c(1) = ...

c(2) = ...

c(3) = ...

c(4) = ...

c(5) = ...

ceq = 0;

求解程序如下：

clear all

clc

x0=[2 25 20]';

lb=[1 4.5 10]';

ub=[4 50 30]';

[x,fval,exitflag]=fmincon(@ex10_6a,x0,[],[],[],[],lb,ub,@ex10_6b)

2. fseminf 函数

上述问题的 Matlab 命令格式为：

X=FSEMINF(FUN,X0,NTHETA,SEMINFCON,A,B,Aeq,Beq)

其中 FUN 用于定义目标函数，X0 为 x 的初始值；NTHETA 是半无穷约束

的个数；函数 SEMINFCON 用于定义非线性不等式约束

,非线性等

式约束

和半无穷约束

的每一个分量函数，函数 SEMINFCON 有两个输入参量 X和S,S是推荐的取样步长，也许不被使用。

【例】

约束为：

function f = fun6(x)

f = sum((x-0.5).^2);

function [c,ceq,k1,k2,s]=fun8(x,s);

c=[];ceq=[];

if isnan(s(1,1))

s=[0.2,0;0.2 0];

end

%取样值

w1=1:s(1,1):100;

w2=1:s(2,1):100;

%半无穷约束

k1=sin(w1*x(1)).*cos(w1*x(2))-1/1000*(w1-50).^2-sin(w1*x(3))-x(3)-1;

k2=sin(w2*x(2)).*cos(w2*x(1))-1/1000*(w2-50).^2-sin(w2*x(3))-x(3)-1;

%画出半无穷约束的图形

plot(w1,k1,'-',w2,k2,'+');

[x,y] = fseminf(@fun6,rand(3,1),2,@fun7)

>>

x =

0.9525

0.8183

0.3714

y =

0.3227

3.fminimax()函数

上述问题的 Matlab 命令为

X=FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON)

【例】

求函数族取最大最小值时得x值

function f=fun9(x);

f=[2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304

-x(1)^2-3*x(2)^2

x(1)+3*x(2)-18

-x(1)-x(2)

x(1)+x(2)-8];

[x,y] = fminimax(@fun9,rand(2,1))

>>

x =

4.0000

4.0000

y =

0.0000

-64.0000

-2.0000

-8.0000

-0.0000