第九章 最优化方法要点

第九章 最优化方法

本章主要介绍线性规划、0-1规划、非线性规划等问题的MATLAB求解。 9.1 线性规划（Linear Programming，简写为LP）问题

线性规划问题就是求多变量线性函数在线性约束条件下的最优值。满足约束条件的解称为可行解，所有可行解构成的集合称为可行域，满足目标式的可行解称为最优解。

MATLAB解决的线性规划问题的标准形式为： min z=f￠?x

ìA祝xb??? s.t. í Ae?qxb eq?????lb＃xub其中f,x,b,beq,lb,ub为列向量，A,Aeq为矩阵。

其它形式的线性规划问题都可经过适当变换化为此标准形式。 在MATLAB中求解线性规划问题函数为linprog，其使用格式为：

[x, fval, exitflag, output, lambda] = linprog(f, A, b, Aeq, beq, lb, ub) 输入部分：其中各符号对应线性规划问题标准形式中的向量和矩阵，如果约束条件中有缺少，则其相应位置用空矩阵[]代替。

输出部分：其中x为最优解，用列向量表示；fval为最优值；exitflag为退出标志，若exitflag=1表示函数有最优解，若exitflag=0表示超过设定的迭代最大次数，若exitflag=-2，表示约束区域不可行，若exitflag=-3，表示问题无解，若exitflag=-4，表示执行迭代算法时遇到NaN，若exitflag=-5，表示原问题和对偶问题均不可行，若exitflag=-7，表示搜索方向太小，不能继续前进；output表明算法和迭代情况；lambda表示存储情况。

例1 用linprog函数求下面的线性规划问题

min -5x1-4x2-6x3ìx1-x2+x3?20????3x1+2x2+4x3?42??? 3x1+2x2?30??s.. tí?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)

注意：由于该问题没有等式约束，所以输入格式中相应的位置用[]代替，变量没有上限约束，所以ub也用[]代替，但由于其在最后，可以不写。

输出结果如下： Optimization terminated. x = % 最优解 0.0000 15.0000 3.0000 fval = %最优值 -78.0000

exitflag = %函数收敛于解 1 output = iterations: 6

algorithm: 'large-scale: interior point' cgiterations: 0

message: 'Optimization terminated.' lambda =

ineqlin: [3x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double]

例2 一家家具公司生产桌子和椅子，用于生产的全部劳动力共计450个工时，原料是400个单位的木材。每张桌子使用15个工时的劳动力，20个单位的木材，售价为80元。每张椅子使用10个工时，用料5个单位，售价45元。问为达到最大效益，应如何安排生产？

解 设生产桌子x个，椅子y个，建立如下模型：

max 80x+45yì20x+5y?400?????15x+10y?450 s.. tí?x30?????y30输入如下： >> f = [-80,-45]; A = [20, 5; 15, 10]; b = [400, 450]; lb = zeros(2,1);

[x, fval, exitflag] = linprog(f,A,b,[],[],lb) 结果如下：

Optimization terminated. x = 14.0000 24.0000 fval = -2.2000e+003 exitflag = 1

注意：由于linprog是求目标函数的最小值，如求目标函数f的最大值，可

先求出?f的最小值fval，则-fval就是f的最大值。本例只输出最优解、最优值和退出标志，可见生产14个桌子，24个椅子，可获得最大利润2200元。

9.2 0-1规划

0-1规划是一种特殊形式的整数规划，它的决策变量仅取值0或1.一般用0表示放弃，1表示选取，故0-1规划可以用来处理选址问题、指派问题、装箱问题、项目评价、资金分配、生产计划安排等问题。

在MATALB中求解0-1规划问题函数为bintprog，其针对下述0-1规划： min z=f￠?x

ìA祝xb??? s.t. í Ae?qxbeq

?????xi=0/1i,=1,2,n,其中f,x,b,beq为列向量，A,Aeq为矩阵。

使用格式为：

[x, fval, exitflag, output] = bintprog(f, A, b, Aeq, beq)

输入部分：其中各符号对应0-1规划问题标准形式中的向量和矩阵，如果约束条件中有缺少，则其相应位置用空矩阵[]代替。

输出部分：其中x为最优解，用列向量表示；fval为最优值；exitflag为退出标志，若exitflag=1表示函数有最优解，若exitflag=-1表示超过设定的迭代最大次数，若exitflag=-2，表示问题不可行，若exitflag=-4，表示搜索节点数超过了设定的搜索节点最大个数，若exitflag=-5，表示搜索时间超过了设定的指令运行的最大秒数，若exitflag=-6，表示LP求解器在某节点处求解LP松弛问题时的迭代次数超过了设定的迭代次数；output包含使用算法、迭代次数、搜索过的节点数、算法执行时间、算法终止原因。

例3 求解下述0-1规划问题。

max z?x1?2x2?2x3?6x4?4x5?3x1?2x2?x3?x4?2x5?5 ?s.. t2x?4x?2x?x?2x?5?12345?x?0或1(i?1,2,,5)?i利用bintprog函数求解如下： >> f=-[1;2;2;-6;-4];