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——线性不等式约束

? 线性不等式约束,指定为实矩阵。AM×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——线性等式约束

? 线性等式约束,指定为实矩阵。AeqMe×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 对应于 Ab 的线性不等式
eqlin 对应于 Aeqbeq 的线性等式

线性约束的拉格朗日乘数满足以下具有 length(f) 个分量的方程:

\[\mathrm{f}+\mathrm{A}^{T} \lambda_{\text {ineqlin }}+\mathrm{Aeq}^{T} \lambda_{\text {eqlin }}+\lambda_{\text {upper }}-\lambda_{\text {lower }}=0 \]

基于拉格朗日乘数

\[\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

相关