【优化算法】01. 线性规划

一般线性规划问题的标准型为

非标准型可转化为标准型，例如

可转化为

满足约束条件的解称为线性规划问题的可行解，所有可行解构成的集合称为问题的可行域，记为R，使得目标函数达到最小值的可行解称为最优解。

基于“若线性规划问题有有限最优解，则一定有某个最优解是可行域的一个极点”，1947年，G.B. Dantzig提出了单纯形法：先找出可行域的一个极点，根据一定规则判断其是否最优，否则转换到与之相邻的另一个极点，并使目标函数值更优，依次做下去，直到找到某一个最优解。

Matlab中线性规划的标准形式为：

其中，和为维列向量；

为维列向量；

为矩阵。

调用格式：

[x,
fval, exitflag, output, lambda]=linprog(c, A, b, Aeq, beq, LB, UB, X0, options)

其中，x返回最优解；

fval返回目标函数值；

A和b对应不等式约束Ax≤b;

Aeq和beq对应等式约束Ax=b;

LB和UB分别是变量x的下界和上界；

x0为x的初始值；

options为控制参数；

exitflag返回算法停止的原因：1表示成功找到最优解，0表示达到最大迭代次数，不能继续寻找最优解，<0表示优化失败（-2未找到可行解，-3问题没有定义边界，-4 NaN存在导致算法退出，-5原始对偶问题没有可行解，-7算法搜索方向存在问题）；

output返回algorithm采用的算法（大中小型），迭代次数等优化信息；

lambda返回最优解x处的拉格朗日乘子的一些参数。

options参数设置：

1）options=optimset(‘optimfun’)

若已有设置好的参数项设置，直接使用其名称即可；

2）opts=optimset(‘param1’,
value1, ‘param2’, value2, …)

创建一个名为opts的参数设置，分别指定参数值，未指定的保持默认。例如，要设置使用大型算法、显示每次迭代、允许误差为10

-8

：

opts=optimset(‘LargeScale’,
‘on’, ‘Display’, ‘iter’, ‘TolFun’, 1e-8)

例1 求解下列线性规划问题：

Matlab代码：

f=-[2 1 -1];

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

b=[4;12];

Aeq=[1 1 2];

beq=6;

lb=zeros(3,1);

x0=[0; 0; 0];

options=optimset('LargeScale', 'on', 'Display', 'iter', 'TolFun', 1e-3);

[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,[],x0,options)

lambda.lower

运行结果（部分）：

x=4.6667
0.0000 0.6667

fval=-8.6667

exitflag=1

表示优化成功，最优解为x=[4.6667, 0.0000, 0.6667]，目标值为8.6667。

注：若在参数选项设置最大迭代次数为3次：

options=optimset('LargeScale',
'on', 'Display',
'iter', 'TolFun',
1e-3, 'maxiter', 3);

fval=-8.2110

exitflag=0 说明达到最大迭代次数，不能继续寻找最优解。

Lingo代码：

model:
max=2*x1+x2-x3;
x1+x2+2*x3=6;
x1+4*x2-x3<4;     !Lingo中<表示<=;
2*x1-2*x2+x3<12; !Lingo默认所有变量非负, 要取消该限制, 用@free(x);
end

运行结果：Global optimal
solution found.

Objective value:
8.666667

Variable Value

X1
4.666667

X2 0.000000

X3 0.6666667

1. Matlab优化工具箱：线性优化，MATLAB中文论坛
2. 卓金武 等. Matlab在数学建模中的应用，北京：北京航空航天大学出版社，2011
   
3. 谢金星，薛毅. 优化建模与LINDO/LINGO软件，北京：清华大学出版社，2006