Matlab数学规划问题.doc

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

其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵。
其它形式的线性规划问题都可经过适当变换化为此标准形式。
在MATLAB6.0版中，线性规划问题（Linear Programming）已用函数linprog取代了MATLAB5.x版中的lp函数。当然，由于版本的向下兼容性，一般说来，低版本中的函数在6.0版中仍可使用。

函数 linprog
调用格式：
x=linprog(f,A,b)
x=linprog(f,A,b,Aeq,beq)
x=linprog(f,A,b,Aeq,beq,lb,ub)
x=linprog(f,A,b,Aeq,beq,lb,ub,x0)
x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
[x,fval]=linprog(…)
[x, fval, exitflag]=linprog(…)
[x, fval, exitflag, output]=linprog(…)
[x, fval, exitflag, output, lambda]=linprog(…)

说明：
x=linprog(f, A, b) %求min f ' *x, sub.to 线性规划的最优解。返回值x为最优解向量。
x=linprog(f, A, b, Aeq, beq) %含有等式约束，若没有不等式约束，则令A=[ ]，b=[ ]。
x = linprog(f, A, b, Aeq, beq, lb, ub) %指定x的范围
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 (lambda.lower)表示下界lb，lambda=upper (lambda.upper)表示上界ub，lambda=ineqlin (lambda.ineqlin)表示不等式约束，lambda=eqlin (lambda.eqlin)表示等式约束，lambda中的非0元素表示对应的约束是有效约束；
output=iterations表示迭代次数，output=algorithm表示使用的运算规则，output=cgiterations表示PCG迭代次数。

Options函数描述：
对于优化控制，MATLAB提供了18个参数，这些参数的具体意义为：
options(1)-参数显示控制（默认值为0）。等于1时显示一些结果。
options(2)-优化点x的精度控制(默认值为1e-4)。
options(3)-优化函数F的精度控制(默认值为1e-4)。
options(4)-违反约束的结束标准(默认值为1e-6)。
options(5)-算法选择，不常用。
options(6)-优化程序方法选择，为0则为BFCG算法，为1则采用DFP算法。
options(7)-线性插值算法选择，为0则为混合插值算法，为1则采用立方插算法。
options(8)-函数值显示 (目标—达到问题中的Lambda )
options(9)-若需要检测用户提供的梯度，则设为1。
options(10)-函数和约束估值的数目。
options(11)-函数梯度估值的个数。
options(12)-约束估值的数目。
options(13)-等约束条件的个数。
options(14)-函数估值的最大次数（默认值是100×变量个数）
options(15)-用于目标 — 达到问题中的特殊目标。
options(16)-优化过程中变量的最小有限差分梯度值。
options(17)- 优化过程中变量的最大有限差分梯度值。
options(18)-步长设置 (默认为1或更小)。

例1 求下面的优化问题

sub.to
解：
>>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 =
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个下界是有效的
2. 0-1规划
对于0-1 规划问题，MATLAB7.0提供命令 bintprog 求解。
MATLAB 中0-1 规划的标准形式：
min f'*X s.t. A*X <= b, Aeq*X = beq
其中X的每个分量为 0 或者1。
（1）X = BINTPROG(f)
求解问题 min f'*X
（2）X = BINTPROG(f,A,b)
求解 min f'*X s.t. A*X <= b
（3）X = BINTPROG(f,A,b,Aeq,beq)
求解 min f'*X s.t. Aeq*X = beq, A*X <= b

3. 分枝定界法求解整数线性规划问题 (待完善)
%%本程序是用分枝定界法求解整数线性规划问题
%%问题的标准形式：
%%  min c'*x
%% s.t. A*x<=b
%%     Aeq*x=beq
function [y,fval]=BranchBound(c,A,b,Aeq,beq)
NL=length(c);  
UB=inf;
LB=-inf;
FN=[0];
AA(1)={A};
BB(1)={b};
k=0; 
flag=0;
while flag==0;
    [x,fval]=linprog(c,A,b,Aeq,beq);
if fval>UB|fval==UB
        FN(1)=[];
        if isempty(FN)==1
            flag=1;
        else
            k=FN(1);
            A=AA{k};
            b=BB{k};
        end
    else
        for i=1:NL
            if abs(x(i)-round(x(i)))>1e-7
                kk=FN(length(FN));
                FN=[FN,kk+1,kk+2];
                temp_A=zeros(1,NL);
                temp_A(i)=1;
                temp_A1=[A;temp_A];
                AA(kk+1)={temp_A1};
                b1=[b;fix(x(i))];
                BB(kk+1)={b1};
                temp_A2=[A;-temp_A];
                AA(kk+2)={temp_A2};
                b2=[b;-(fix(x(i))+1)];
                BB(kk+2)={b2};
                FN(1)=[];
                k=FN(1);
                A=AA{k};
                b=BB{k};
                break;
            end
        end
        if i==NL
            UB=fval;
            y=x;
            FN(1)=[];
            if isempty(FN)==1
                flag=1;
            else
                k=FN(1);
                A=AA{k};
                b=BB{k};
            end
        end
    end
end
y=round(y);
fval=c*y;
4. MATLAB非线性规划函数
在 MATLAB\toolbox\optim中有两个M文件：constr．m和fminu．m，分别包含了用于约束优化问题和无约束优化问题的两组函数．下面介绍其中最有用的两个函数．
1．约束优化
[X,OPTIONS]=constr(‘FUN’,X,OPTIONS,VLB,VUB)
此函数求解下列约束优化（非线性规划）问题：
min F(X)
s.t.
G1(X)=0(m equalities)
G2(X)<=0(p inequalities)(G=[G1;G2])
VLB<=x<=VUB
FU N：M文件‘FU N．M”中定义了函数[F，G]=FUN（X），F=F（X）是目标函数
（求极小），以G（X）=[G1（X）；G2（X）]代表等式和不等式（＜＝）约束函数；
X：输入参数X是决策变量的初始点（最优点的一个估计，可以随便给，当然越准求解越快），输出参数X是决策变量的最优点；
OPTIONS：可选的参数向量，其中最有用的有两个：
输出参数options(8)=目标函数最优值；
输人参数options(13)=等式约束的个数=m；
VLB和 VUB：决策变量的下界和上界．
2．无约束优化
[X,OPTIONS]=fminu(‘FUN’,X0,……)
此函数求解下列无约束优化问题：
min F（X）
其中：
FUN：M文件“FUN．M’中定义了函数．F=FUN(X),F=F(X)就是目标函数（求极小）；
X：输人参数X是决策变量的初始点（最优点的一个估计，可以随便给，当然越准求解越快）输出参数X是决策变量的最优点；
OPTIONS：可选向量，其中最有用的是：
输出参数options(8)=目标函数最优值．
在fminu中，默认的无约束优化算法是BFGS算法，直线搜索是二次和三次混合拟合搜索，
**********************************************************
提示：1）MATLAB函数的定义形式独具一格，它非常明白地表达了函数 参数的三种情况：输入、输出、输入-输出，这是一般计算机语言都不及的（就我所见！）
2）求解非线性规划问题首先要编一个M文件，代表你要解的问题．
5. matlab多目标规划
[x,fval,attainfactor,exitflag]=fgoalattain(fun,x0,goal,...,weight,a,b,aeq,beq,lb,ub).
在输入部分:
fun是目标函数，x0是初始值，goal是目标函数希望达到的值，weight是目标权重。
（1） 当目标权重为正时，指令fgoalattain试图使对象小于目标值。为了使目标函数大于目标值，可使权重设置为负。
（2）一般设置为weight=goal或weight=abs(goal)
a,b给出线性不等式约束;aeq,beq给出线性等式约束；lb，ub为x的上界和下界。如无某类约束，可用[]代替。
在输出部分：
exitflag为输出标记。当exitflag>0,解收敛，所给出的x,fval有效；当exitflag<=0,解没有收敛，所给出的x,fval无效。
x为多目标问题的解，当exitflag>0,x称满意解，fval称目标达到值。
attainfactor是指目标达到情况。当attainfactor>=0,目标达到值fval没有溢出goal;
当attainfactor<0,fval有溢出goal的情况。
例2：某工厂因生产需要，欲采购一种原料，市场上这种原材料有两个等级，甲级单价2元/kg,乙级单价1元/kg，现要求总费用不超过200元，购得原料总量不少于100kg,其中甲级原料不少于50kg，问如何确定最好的采购方案。
列出方程
x1>=50
x1*2+x2*1<=200
x1+x2>=100
x1,x2>=0

min f1=x1*2+x2*1
min f2=-x1-x2
min f3=x1
s.t   :
x1*2+x2*1<=200
-x1-x2<=-100
-x1<=-50
x1,x2>=0
matlab程序
fun='[2*x(1)+x(2),-x(1)-x(2),-x(1)]';
a=[2 1;-1 -1;-1 0];
b=[200 -100 20]';
goal=[200,-100,-50];
weight=goal;
x0=[55,55];
lb=[0,0]';
[x,fval,attainfactor,exitflag]=fgoalattain(fun,x0,goal,weight,a,b,[],[],lb,[])
Optimization terminated: Search direction less than 2*options.TolX
 and maximum constraint violation is less than options.TolCon.
Active inequalities (to within options.TolCon = 1e-006):
  lower      upper     ineqlin   ineqnonlin
                          2          2
                                     3
x =
   50.0000   50.0000

fval =
  150.0000 -100.0000  -50.0000

attainfactor =
 -1.4476e-024

exitflag =
     4

- 7 -