如何解决线性规划问题

线性规划问题是指目标函数与约束函数都是变量X的线性函数。其一般形式为

minf^TX

s.t. AX≤b

A_eqX=b_eq

lb≤X≤ub

其中，X为n维未知向量；f^T=（f₁f₂ … f_n）为目标函数系数向量，小于或等于约束系数矩阵，b为其右端m维列向量；A_eq为等式约束系数矩阵；b_eq为等式约束右端常数列向量；lb、ub为自变量取值上界和下界的n维常数向量。

线性规划问题一般用linprog函数求最优解。

1）语法：

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（…）

2）说明：

x=linprog（f，A，b）返回值x为最优解向量。

x=linprog（f，A，b，Aeq，beq）作有等式约束的问题。若没有不等式约束，则令A=[]，b=[]。

x=linprog（f，A，b，Aeq，beq，lb，ub，x0，options）中lb、ub为变量x的下界和上界，x0为初始点，options为指定优化参数进行最小化。

options的参数描述：

①Display显示水平。选择“off”不显示输出；选择“iter”显示每一步迭代过程的输出；选“final”显示最终结果。

②MaxFunEvals为函数评价的最大允许次数。

③Maxiter为最大允许迭代次数。

④TolX为x处的终止容限。

[x，fval]=linprog（…）为左端fval返回解x处的目标函数值。

[x，fval，exitflag，output，lambda]=linprog（f，A，b，Aeq，beq，lb，ub，x0）的输出部分。

exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。

output返回优化信息：output.iterations表示迭代次数；output.algorithm表示所采用的算法。

output.funcCount表示函数评价次数。

lambda为返回x处的Lagrange乘子。它有以下属性：

lambda.lower——lambda的下界。

lambda.upper——lambda的上界。

lambda.ineqlin——lambda的线性不等式。

lambda.eqlin——lambda的线性等式。(www.xing528.com)

例4-6 求解如下数学模型

maxf=0.15x₁+0.1x₂+0.08x₃+0.12x₄

s.t.x₁-x₂-x₃-x₄≤0

x₂+x₃-x₄≥0

x₁+x₂+x₃+x₄=1

x_j≥0 （j=1，2，3，4）

首先需要将上述数学模型转化为求极小值的模型

minf=-0.15x₁-0.1x₂-0.08x₃-0.12x₄

s.t.x₁-x₂-x₃-x₄≤0

-x₂-x₃+x₄≤0

x₁+x₂+x₃+x₄=1

x_j≥0 （j=1，2，3，4）

MATLAB代码如下：

＞＞f=[-0.15；-0.1；-0.08；-0.12]；

A=[1-1-1-1；0-1-11]；

b=[0；0]；

Aeq=[1 1 1 1]；

beq=[1]；

lb=zeros（3，1）；

[x，fval，exitflag]=linprog（f，A，b，Aeq，beq，lb）

f=-fval

计算结果：

x=

0.5000

0.2500

0.0000

0.2500

fval=

-0.1300

exitflag=

1

f=

0.1300上述结果中exitflag为正数，则说明过程收敛。