Matlab中的线性规划
Matlab中的线性规划
目录- Matlab中的线性规划
- 线性规划问题简介
- 线性规划的Matlab标准形式
- 语法及说明
- 输入参数
- f——系数向量
- A——线性不等式约束;b——线性不等式约束
- Aeq——线性等式约束;beq——线性等式约束
- lb——下界;ub——上界
- 输出参数
- x——解
- fval——解处的目标函数值
- lambda——解处的拉格朗日乘数
- 示例:
线性规划问题简介
在一组线性约束条件的限制下,求一线性目标函数最大或者最小的问题
线性:一次
线性规划的Matlab标准形式
语法及说明
x=linprog(f,A,b)
%求解 min f'*x,满足 A*x ≤ b。
x = linprog(f,A,b,Aeq,beq)
%包括等式约束 Aeq*x = beq。如果不存在不等式,请设置 A = [] 和 b = []。
x = linprog(f,A,b,Aeq,beq,lb,ub)
%定义设计变量 x 的一组下界和上界,使解始终在 lb ≤ x ≤ ub 范围内。如果不存在等式,请设置 Aeq = [] 和 beq = []。
x = linprog(f,A,b,Aeq,beq,lb,ub,options)
%使用 options 所指定的优化选项执行最小化。使用 optimoptions 可设置这些选项。
x = linprog(problem)
%求 problem 的最小值,它是 problem 中所述的一个结构体。
[x,fval] = linprog(___)
%输入任何参数,返回目标函数 fun 在解 x 处的值:fval = f'*x。
[x,fval,exitflag,output] = linprog(___)
%不仅返回fval;还返回说明退出条件的值 exitflag,以及包含优化过程信息的结构体 output。
[x,fval,exitflag,output,lambda] = linprog(___)
%不仅返回fval,exitflag,output;还返回结构体 lambda,其字段包含在解 x 处的拉格朗日乘数。
进入Matlab的帮助文档可以看到linprog函数求解的是线性规划的标准型:
\[\min_x f^{T} x ~such~that \left\{\begin{aligned} A \cdot x & \leq b, \\ A e q \cdot x &=b e q, \\ l b & \leq x \leq u b . \end{aligned}\right. \]f,x,b,beq,lb和ub是向量;A和Aeq是矩阵。
输入参数
f——系数向量
系数向量,指定为实数向量或实数数组。系数向量表示目标函数 f'*x
。
例如:
\[f=[1,3,5,-6] \]A——线性不等式约束;b——线性不等式约束
? 线性不等式约束,指定为实矩阵。A
是 M
×N
矩阵,其中 M
是不等式的数目,而 N
是变量的数目(f
的长度)。对于大型问题,将 A
作为稀疏矩阵传递。
A
以如下形式编写 M
个线性不等式
A*x <= b
,
其中,x
是由 N
个变量组成的列向量 x(:)
,b
是具有 M
个元素的列向量。
? 线性不等式约束,指定为实数向量。b
是与 A
矩阵相关的包含 M
个元素的向量。如果将 b
作为行向量传递,求解器会在内部将 b
转换为列向量 b(:)
。对于大型问题,将 b
作为稀疏向量传递。
b
以如下形式编写 M
个线性不等式
A*x <= b
,
其中,x
是由 N
个变量组成的列向量 x(:)
,A
是大小为 M
×N
的矩阵。
例如,假设有以下不等式:
\[x_1 + 2x_2 ≤ 10\\ 3x_1 + 4x_2 ≤ 20\\ 5x_1 + 6x_2 ≤ 30。 \]通过以下输入来约束不等式。
\[A = [1,2;3,4;5,6];\\ b = [10;20;30]; \]Aeq——线性等式约束;beq——线性等式约束
? 线性等式约束,指定为实矩阵。Aeq
是 Me
×N
矩阵,其中 Me
是等式的数目,而 N
是变量的数目(f
的长度)。对于大型问题,将 Aeq
作为稀疏矩阵传递。
Aeq
以如下形式编写 Me
个线性等式
Aeq*x = beq
,
其中,x
是由 N
个变量组成的列向量 x(:)
,beq
是具有 Me
个元素的列向量。
? 线性等式约束,指定为实数向量。beq
是与 Aeq
矩阵相关的包含 Me
个元素的向量。如果将 beq
作为行向量传递,求解器会在内部将 beq
转换为列向量 beq(:)
。对于大型问题,将 beq
作为稀疏向量传递。
beq
以如下形式编写 Me
个线性等式
Aeq*x = beq
,
其中,x
是由 N
个变量组成的列向量 x(:)
,Aeq
是大小为 Me
×N
的矩阵。
例如,假设有以下不等式:
\[x1 + 2x_2 + 3x_3 = 10\\ 2x_1 + 4x_2 + x_3 = 20。 \]通过以下输入来约束不等式。
\[A = [1,2,3;2,4,1];\\ b = [10;20]; \]lb——下界;ub——上界
? 下界,指定为实数向量或实数数组。如果 f
的长度等于 lb
的长度,则 lb
指定
x(i) >= lb(i)
(对于全部 i
)。
如果 numel(lb) < numel(f)
,则 lb
指定
x(i) >= lb(i)
(1 <= i <= numel(lb)
)。
在这种情况下,求解器会发出警告。
? 上界,指定为实数向量或实数数组。如果 f
的长度等于 ub
的长度,则 ub
指定
x(i) <= ub(i)
(对于全部 i
)。
如果 numel(ub) < numel(f)
,则 ub
指定
x(i) <= ub(i)
(1 <= i <= numel(ub)
)。
在这种情况下,求解器会发出警告。
列如:
- 要指定所有 x 分量都为正,请指定
lb = zeros(size(f))
。 - 要指定所有 x 分量都小于
1
,请使用ub = ones(size(f))
。
输出参数
x——解
解,以实数向量或实数数组形式返回。x
的大小与 f
的大小相同。
fval——解处的目标函数值
解处的目标函数值,以实数形式返回。通常,fval
= f'*x
。
lambda——解处的拉格朗日乘数
解处的拉格朗日乘数,以包含下列字段的结构体形式返回。
lower | 对应于 lb 的下界 |
---|---|
upper | 对应于 ub 的上界 |
ineqlin | 对应于 A 和 b 的线性不等式 |
eqlin | 对应于 Aeq 和 beq 的线性等式 |
线性约束的拉格朗日乘数满足以下具有 length(f)
个分量的方程:
基于拉格朗日乘数
\[\mathrm{f}^{T} x+\lambda_{\text {ineqlin }}^{T}( A x-\mathrm{b})+\lambda_{\text {eqlin }}^{T}(Aeq x- beq )+\lambda_{\text {upper }}^{T}(x-\mathrm{ub})+\lambda_{\text {lower }}^{T}(\mathrm{lb}-x) \]示例:
例1:
\[\max z=2 x_{1}+3 x_{2}-5 x_{3}~~s, t\left\{\begin{array}{c}x_{1}+x_{2}+x_{3}=7 \\ 2 x_{1}-5 x_{2}+x_{3} \geq 10 \\ x_{1}+3 x_{2}+x_{3} \leq 12 \\ x_{1}, x_{2}, x_{3} \geq 0\end{array}\right. \]解:
(1)化为Matlab标准型:
\[\min w=-2 x_{1}-3 x_{2}+5 x_{3}~~s,t \left\{\begin{array}{c}{\left[\begin{array}{ccc}-2 & 5 & -1 \\ 1 & 3 & 1\end{array}\right]\left[\begin{array}{l}x_{1} \\ x_{2} \\ x_{3}\end{array}\right] \leq\left[\begin{array}{c}-10 \\ 12\end{array}\right]} \\ {[1,1,1] *\left[x_{1}, x_{2}, x_{3}\right]^{T}=7,\left[x_{1}, x_{2}, x_{3}\right]^{T} \geq[0,0,0]^{T}}\end{array}\right. \]Matlab中只有min的形式,所以将每个系数乘-1,max自然变为min。
(2)编写Matlab脚本:
f=[-2;-3;5];
a=[-2,5,-1;1,3,1];
b=[-10;12];
aeq=[1,1,1];
beq=7;
[x,y]=linprog(f,a,b,aeq,beq,zeros(3,1));
x
y=-y
脚本运行结果:
>> untitled
Optimal solution found.
x =
6.4286
0.5714
0
y =
14.5714
求得的最优解为x1=6.4286,x2=0.5714,x3=0,对应的最优值为z=14.5714.
例2:
\[\min z=2 x_{1}+3 x_{2}+x_{3}~~s,t\left\{\begin{array}{c}x_{1}+4 x_{2}+2 x_{3} \geq 8 \\ 3 x_{1}+2 x_{2} \geq 6 \\ x_{1}, x_{2}, x_{3} \geq 0\end{array}\right. \]解:
(1)化为Matlab标准型:
\[\min w=2 x_{1}3 x_{2}+x_{3}~~s,t \left\{\begin{array}{c}{\left[\begin{array}{ccc}1 & 4 & 2 \\ 3 & 2 & 0\end{array}\right]\left[\begin{array}{l}x_{1} \\ x_{2} \\ x_{3}\end{array}\right] \geq\left[\begin{array}{c}8\\ 6\end{array}\right]} \\ {[1,1,1] *\left[x_{1}, x_{2}, x_{3}\right]^{T}=7,\left[x_{1}, x_{2}, x_{3}\right]^{T} \geq[0,0,0]^{T}}\end{array}\right. \](2)编写Matlab脚本:
c=[2;3;1];
a=[1,4,2;3,2,0];
b=[8;6]
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))
%这里没有等式约束,对应的矩阵为空矩阵
脚本运行结果:
>> untitled
b =
8
6
Optimal solution found.
x =
2.0000
0
3.0000
y =
7
求得的最优解为x1=2,x2=0,x3=3,对应的最优值为z=7