linprog

求解线性规划问题

全页折叠

语法

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,options)

x = linprog(problem)

[x,fval] = linprog(___)

[x,fval,exitflag,output] = linprog(___)

[x,fval,exitflag,output,lambda] = linprog(___)

[x,fval,exitflag,output,lambda,sensitivity] = linprog(___)

说明

非线性规划求解器

求以下问题的最小值：

$\min_{x} f^{T} x such that {\begin{matrix} bl \leq A \cdot x \leq b \\ Aeq \cdot x = beq \\ lb \leq x \leq ub . \end{matrix}$

f、x、b、bl、beq、lb 和 ub 是向量，而 A 和 Aeq 是矩阵。

注意

linprog 仅适用于基于求解器的方法。使用 solve 作为基于问题的方法。有关这两种优化方法的讨论，请参阅首先选择基于问题或基于求解器的方法。

x = linprog(f,A,b) 求解满足 A*x ≤ b 的最小 f'*x，或者，如果 b 是包含两个元素的元胞数组，则为 {bl,b}、bl ≤ 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 = []。

注意

如果问题的指定输入边界不一致，则输出 fval 为 []。

示例

x = linprog(f,A,b,Aeq,beq,lb,ub,options) 使用 options 所指定的优化选项执行最小化。使用 optimoptions 可设置这些选项。

示例

x = linprog(problem) 求 problem 的最小值，它是 problem 中所述的一个结构体。

您可以使用 mpsread 从 MPS 文件中导入 problem 结构体。您还可以使用 prob2struct 从 OptimizationProblem 对象创建 problem 结构体。

示例

对于任何输入参量，[x,fval] = linprog(___) 返回目标函数 fun 在解 x 处的值：fval = f'*x。

示例

[x,fval,exitflag,output] = linprog(___) 还返回说明退出条件的值 exitflag，以及包含优化过程信息的结构体 output。

示例

[x,fval,exitflag,output,lambda] = linprog(___) 还返回结构体 lambda，其字段包含在解 x 处的拉格朗日乘数。

示例

[x,fval,exitflag,output,lambda,sensitivity] = linprog(___) 还会返回一个 SensitivityAnalysis 对象，其中包含有关解随问题参数变化情况的信息。

示例

全部折叠

线性规划、线性不等式约束

打开实时脚本

求解由线性不等式定义的简单线性规划。

对于此示例，使用以下线性不等式约束：

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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

b = [2 1 2 1 -1 2];

使用目标函数 $- x (1) - x (2) / 3$ 。

f = [-1 -1/3];

求解线性规划。

x = linprog(f,A,b)

Optimal solution found.

具有线性不等式和等式的线性规划

打开实时脚本

求解由线性不等式和线性等式定义的简单线性规划。

对于此示例，使用以下线性不等式约束：

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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

b = [2 1 2 1 -1 2];

使用线性等式约束 $x (1) + x (2) / 4 = 1 / 2$ 。

Aeq = [1 1/4];
beq = 1/2;

使用目标函数 $- x (1) - x (2) / 3$ 。

f = [-1 -1/3];

求解线性规划。

x = linprog(f,A,b,Aeq,beq)

Optimal solution found.

具有所有约束类型的线性规划

打开实时脚本

求解具有线性不等式、线性等式和边界的简单线性规划。

对于此示例，使用以下线性不等式约束：

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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

b = [2 1 2 1 -1 2];

使用线性等式约束 $x (1) + x (2) / 4 = 1 / 2$ 。

Aeq = [1 1/4];
beq = 1/2;

设置以下边界：

$- 1 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 1.25 .$

lb = [-1,-0.5];
ub = [1.5,1.25];

使用目标函数 $- x (1) - x (2) / 3$ 。

f = [-1 -1/3];

求解线性规划。

x = linprog(f,A,b,Aeq,beq,lb,ub)

Optimal solution found.

使用 `"interior-point"` 算法的线性规划

打开实时脚本

使用 "interior-point" 算法求解线性规划。

对于此示例，使用以下线性不等式约束：

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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

b = [2 1 2 1 -1 2];

使用线性等式约束 $x (1) + x (2) / 4 = 1 / 2$ 。

Aeq = [1 1/4];
beq = 1/2;

设置以下边界：

$- 1 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 1.25 .$

lb = [-1,-0.5];
ub = [1.5,1.25];

使用目标函数 $- x (1) - x (2) / 3$ 。

f = [-1 -1/3];

设置选项以使用 "interior-point" 算法。

options = optimoptions("linprog",...
    Algorithm="interior-point");

使用 'interior-point' 算法求解线性规划。

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

Solution found during presolve.

为 `linprog` 使用基于问题的方法求解 LP

打开实时脚本

此示例说明如何使用基于问题的方法设立问题，然后使用基于求解器的方法求解问题。问题是

$\max_{x} (x + y / 3) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x + y \leq 2 \\ x + y / 4 \leq 1 \\ x - y \leq 2 \\ x / 4 + y \geq - 1 \\ x + y \geq 1 \\ - x + y \leq 2 \\ x + y / 4 = 1 / 2 \\ - 1 \leq x \leq 1.5 \\ - 1 / 2 \leq y \leq 1.25 \end{array}$

创建名为 prob 的 OptimizationProblem 对象来表示此问题。

x = optimvar("x",LowerBound=-1,UpperBound=1.5);
y = optimvar("y",LowerBound=-1/2,UpperBound=1.25);
prob = optimproblem(Objective=x + y/3,ObjectiveSense="max");
prob.Constraints.c1 = x + y <= 2;
prob.Constraints.c2 = x + y/4 <= 1;
prob.Constraints.c3 = x - y <= 2;
prob.Constraints.c4 = x/4 + y >= -1;
prob.Constraints.c5 = x + y >= 1;
prob.Constraints.c6 = -x + y <= 2;
prob.Constraints.c7 = x + y/4 == 1/2;

将问题对象转换为问题结构体。

problem = prob2struct(prob);

求解生成的问题结构体。

[sol,fval,exitflag,output] = linprog(problem)

Optimal solution found.

sol = 2×1

    0.1875
    1.2500

fval = 
-0.6042

exitflag = 
1

output = struct with fields:
         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex-highs'
      firstorderopt: 0

返回的 fval 为负数，即使解分量为正数也是如此。在内部，prob2struct 将最大化问题转换为目标函数的负值的最小化问题。请参阅对目标进行最大化。

sol 的哪个分量对应于哪个优化变量？查看 prob 的 Variables 属性。

prob.Variables

ans = struct with fields:
    x: [1×1 optim.problemdef.OptimizationVariable]
    y: [1×1 optim.problemdef.OptimizationVariable]

如您所料，sol(1) 对应于 x，sol(2) 对应于 y。请参阅算法。

返回目标函数值

打开实时脚本

计算简单线性规划的解和目标函数值。

不等式约束是

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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

b = [2 1 2 1 -1 2];

目标函数是 $- x (1) - x (2) / 3$ 。

f = [-1 -1/3];

求解问题并返回目标函数值。

[x,fval] = linprog(f,A,b)

Optimal solution found.

fval = 
-1.1111

获取更多输出结果以分析解过程

打开实时脚本

获取退出标志和输出结构体，以便更好地了解求解过程和质量。

对于此示例，使用以下线性不等式约束：

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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

b = [2 1 2 1 -1 2];

使用线性等式约束 $x (1) + x (2) / 4 = 1 / 2$ 。

Aeq = [1 1/4];
beq = 1/2;

设置以下边界：

$- 1 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 1.25 .$

lb = [-1,-0.5];
ub = [1.5,1.25];

使用目标函数 $- x (1) - x (2) / 3$ 。

f = [-1 -1/3];

设置选项以使用 "dual-simplex" 算法。

options = optimoptions("linprog",...
    Algorithm="dual-simplex");

求解线性规划并请求返回函数值、退出标志和输出结构体。

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

Optimal solution found.

fval = 
-0.6042

exitflag = 
1

output = struct with fields:
         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex-highs'
      firstorderopt: 0

目标函数值 fval 大于返回目标函数值，因为约束更多。
exitflag = 1 表示解可靠。
output.iterations = 0 表示 linprog 在预求解过程中即找到解，根本不必进行迭代。

获得解和拉格朗日乘数

打开实时脚本

求解简单的线性规划，并检查解和拉格朗日乘数。

使用目标函数

$f (x) = - 5 x_{1} - 4 x_{2} - 6 x_{3} .$

f = [-5; -4; -6];

使用线性不等式约束

$x_{1} - x_{2} + x_{3} \leq 20$

$3 x_{1} + 2 x_{2} + 4 x_{3} \leq 42$

$3 x_{1} + 2 x_{2} \leq 30 .$

A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20;42;30];

将所有变量约束为正值：

$x_{1} \geq 0$

$x_{2} \geq 0$

$x_{3} \geq 0 .$

lb = zeros(3,1);

将 Aeq 和 beq 设置为 []，表示没有线性等式约束。

Aeq = [];
beq = [];

调用 linprog，获取拉格朗日乘数。

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

Optimal solution found.

检查解和拉格朗日乘数。

x,lambda.ineqlin,lambda.lower

对于 x 的第二个和第三个分量，lambda.ineqlin 为非零值。这表明等式满足第二个和第三个线性不等式约束：

$3 x_{1} + 2 x_{2} + 4 x_{3} = 42$

$3 x_{1} + 2 x_{2} = 30 .$

检查这是否属实：

A*x

对于 x 的第一个分量，lambda.lower 为非零值。这表明 x(1) 处于其下界 0 上。

获取灵敏度

打开实时脚本

编写一个线性规划程序。

f = [-2,-1];
A = [-1 -1;
    1 -1/2;
    -1 1];
bl = [-5 -Inf -Inf];
b = [Inf 2 3];
lb = [0 0];
ub = [];
Aeq = [];
beq = [];

求解该线性规划问题，并计算灵敏度。

[x,fval,exitflag,output,lambda,sensitivity] = ...
    linprog(f,A,b,Aeq,beq,lb,ub)

Optimal solution found.

fval = 
-24

exitflag = 
1

output = struct with fields:
         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex-highs'
      firstorderopt: 0

lambda = struct with fields:
           lower: [2×1 double]
           upper: [2×1 double]
           eqlin: [0×1 double]
    ineqlinLower: [3×1 double]
         ineqlin: [3×1 double]

sensitivity = 
  SensitivityAnalysis with properties:

   Variables Sensitivity:
    ObjectiveCoefficient: [2×5 table]
              LowerBound: [2×5 table]
              UpperBound: [2×5 table]

   Constraints Sensitivity:
           InequalityLHS: [3×5 table]
           InequalityRHS: [3×5 table]
             EqualityRHS: [0×5 table]

分析灵敏度。

sensitivity.ObjectiveCoefficient

ans=2×5 table
    LowerLimit    UpperLimit    ObjectiveValueAtLowerLimit    ObjectiveValueAtUpperLimit    ObjectiveValueChangeRate
    __________    __________    __________________________    __________________________    ________________________

       -Inf           1                    -Inf                           -3                            7           
       -Inf           1                    -Inf                           -4                           10

sensitivity.LowerBound

ans=2×5 table
    LowerLimit    UpperLimit    ObjectiveValueAtLowerLimit    ObjectiveValueAtUpperLimit    ObjectiveValueChangeRate
    __________    __________    __________________________    __________________________    ________________________

       -Inf            7                   -24                           -24                           0            
       -Inf           10                   -24                           -24                           0

sensitivity.InequalityLHS

ans=3×5 table
    LowerLimit    UpperLimit    ObjectiveValueAtLowerLimit    ObjectiveValueAtUpperLimit    ObjectiveValueChangeRate
    __________    __________    __________________________    __________________________    ________________________

       -Inf          -17                   -24                           -24                           0            
       -Inf            2                   -24                           -24                           0            
       -Inf            3                   -24                           -24                           0

sensitivity.InequalityRHS

ans=3×5 table
    LowerLimit    UpperLimit    ObjectiveValueAtLowerLimit    ObjectiveValueAtUpperLimit    ObjectiveValueChangeRate
    __________    __________    __________________________    __________________________    ________________________

        -17          Inf                   -24                            -24                           0           
       -1.5          Inf                    -3                           -Inf                          -6           
         -2          Inf                    -4                           -Inf                          -4

有关返回的灵敏度的说明，请参阅SensitivityAnalysis。

输入参数

全部折叠

`f` — 系数向量
实数向量 | 实数数组

系数向量，指定为实数向量或实数数组。系数向量表示目标函数 f'*x。该表示法假设 f 是列向量，但您也可以使用行向量或数组。linprog 在内部将 f 转换为列向量 f(:)。

示例: f = [1,3,5,-6]

数据类型: double

`A` — 线性不等式约束
实矩阵

线性不等式约束，指定为实矩阵。A 是 M×N 矩阵，其中 M 是不等式的数目，而 N 是变量的数目（x0 中的元素数）。对于大型问题，将 A 作为稀疏矩阵传递。

A 以如下形式编写 M 个线性不等式

A*x <= b,

其中 x 是 N 个变量 x(:) 组成的列向量，而 b 是一个包含 M 个元素的向量。

当 b 是一个包含两个元素的元胞数组 {bl,b} 时，A 表示以下线性不等式：

bl <= A*x <= b. (1)

例如，假设有以下不等式：

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30。

通过输入以下约束来指定不等式。

A = [1,2;3,4;5,6];
b = [10;20;30];

同样地，如果您还有以下额外约束条件：

4 x₁ – x₂ ≥2,

(2)

然后指定

bb = {[-inf;-inf;-inf;2] [b;inf]};
AA = [A;[4 -1]];

并将 AA 和 bb 作为线性不等式约束。

示例: 要指定 x 分量总和等于或小于 1，请使用 A = ones(1,N) 和 b = 1。

数据类型: single | double

`Aeq` — 线性等式约束
实矩阵

线性等式约束，指定为实矩阵。Aeq 是 Me×N 矩阵，其中 Me 是等式的数目，而 N 是变量的数目（f 的长度）。对于大型问题，将 Aeq 作为稀疏矩阵传递。

Aeq 以如下形式编写 Me 个线性等式

Aeq*x = beq,

其中，x 是由 N 个变量组成的列向量 x(:)，beq 是具有 Me 个元素的列向量。

例如，请参考以下等式：

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20。

通过输入以下约束来指定等式。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

示例: 要指定 x 分量之和为 1，请指定 Aeq = ones(1,N) 和 beq = 1。

数据类型: double

`b` — 线性不等式约束
实数向量 | 由实数数组组成的两元元胞数组

线性不等式约束，指定为一个实数向量或一个由两个元素组成的、包含实数数组的元胞数组。

如果 b 是一个由 M 个元素组成的向量，那么 b 表示 M 个线性不等式
A*x <= b, (3)
其中，x 是由 N 个变量组成的列向量 x(:)，A 是大小为 M×N 的矩阵。
如果 b 是一个包含两个元素的元胞数组 {bl,b}，则 bl 或 b（或两者）必须是非空的。b 中非空的条目包含 M 元素，这些元素编码了线性不等式
bl <= A*x <= b, (4)
其中，x 是由 N 个变量组成的列向量 x(:)，A 是大小为 M×N 的矩阵。

如果将 b 或 bl 作为行向量传入，求解器会在内部将其转换为列向量 b(:) 或 bl(:)。

例如，假设有以下不等式：

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30。

通过输入以下约束来指定不等式。

A = [1,2;3,4;5,6];
b = [10;20;30];

请考虑这一额外约束条件

4 x₁ – x₂ ≥2,

(5)

将约束条件指定为线性不等式矩阵 AA 和 bb，它们是 A 和 b 的扩展。

bb = {[-inf;-inf;-inf;2] [b;inf]};
AA = [A;[4 -1]];

示例: 要指定 x 分量总和等于或小于 1，请使用 A = ones(1,N) 和 b = 1。

数据类型: single | double

`beq` — 线性等式约束
实数向量

线性等式约束，指定为实数向量。beq 是与 Aeq 矩阵相关的包含 Me 个元素的向量。如果将 beq 作为行向量传入，求解器会在内部将其转换为列向量 beq(:)。

beq 以如下形式编写 Me 个线性等式

Aeq*x = beq,

其中，x 是由 N 个变量组成的列向量 x(:)，Aeq 是大小为 Me×N 的矩阵。

例如，请参考以下等式：

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20。

通过输入以下约束来指定等式。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

示例: 要指定 x 分量总和为 1，请使用 Aeq = ones(1,N) 和 beq = 1。

数据类型: single | double

`lb` — 下界
实数向量 | 实数数组

下界，指定为实数向量或实数数组。如果 f 的长度等于 lb 的长度，则 lb 指定

x(i) >= lb(i)（对于全部 i）。

如果 numel(lb) < numel(f)，则 lb 指定

x(i) >= lb(i) (1 <= i <= numel(lb))。

在这种情况下，求解器会发出警告。

示例: 要指定所有 x 分量都为正，请指定 lb = zeros(size(f))。

数据类型: double

`ub` — 上界
实数向量 | 实数数组

上界，指定为实数向量或实数数组。如果 f 的长度等于 ub 的长度，则 ub 指定

x(i) <= ub(i)（对于全部 i）。

如果 numel(ub) < numel(f)，则 ub 指定

x(i) <= ub(i) (1 <= i <= numel(ub))。

在这种情况下，求解器会发出警告。

示例: 要指定所有 x 分量都小于 1，请使用 ub = ones(size(f))。

数据类型: double

`options` — 优化选项
`optimoptions` 的输出 | `optimset` 返回的结构体

优化选项，指定为 optimoptions 的输出或 optimset 返回的结构体。

一些选项适用于所有算法，其他选项则与特定算法相关。有关详细信息，请参阅优化选项参考。

optimoptions 显示中缺少某些选项。这些选项在下表中以斜体显示。有关详细信息，请参阅查看优化选项。

所有算法
`Algorithm`	选择优化算法： `"dual-simplex-highs"`（默认值） `"interior-point"` `"interior-point-legacy"` 有关选择算法的信息，请参阅线性规划算法。
Diagnostics	显示关于要最小化或求解的函数的诊断信息。选择 `"off"`（默认值）或 `"on"`。
`Display`	显示级别（请参阅迭代输出）： `"final"`（默认值）仅显示最终输出。 `"off"` 或 `"none"` 不显示输出。 `"iter"` 在每次迭代时显示输出。
`MaxIterations`	允许的最大迭代次数，非负整数。默认值为： `intmax`（对于 `"dual-simplex-highs"` 算法，大约为 `2.1475e+09`） `200`（对于 `"interior-point"` 算法） `85`（对于 `"interior-point-legacy"` 算法）请参阅容差和停止条件和迭代和函数计算次数。对于 `optimset`，名称为 `MaxIter`。请参阅当前选项名称和旧选项名称。
`OptimalityTolerance`	对偶可行性的终止容差，非负标量。默认值为： `1e-7`（对于 `"dual-simplex-highs"` 算法） `1e-6`（对于 `"interior-point"` 算法） `1e-8`（对于 `"interior-point-legacy"` 算法）对于 `optimset`，名称为 `TolFun`。请参阅当前选项名称和旧选项名称。
对偶单纯形 Highs 算法
`ConstraintTolerance`	约束的可行性容差，非负标量。`ConstraintTolerance` 测量原始可行性容差。默认值为 `1e-7`。
`MaxTime`	算法运行的最长时间（以秒为单位）。默认值为 `Inf`。
预求解	对偶单纯形算法迭代之前的 LP 预求解级别。指定 `"auto"`（默认值）、`"off"` 或 `"on"`。
内点算法
`ConstraintTolerance`	约束的可行性容差，非负标量。`ConstraintTolerance` 测量原始可行性容差。默认值为 `1e-6`。对于 `optimset`，名称为 `TolCon`。请参阅当前选项名称和旧选项名称。
预求解	在算法迭代之前，对线性规划 (LP) 进行预求解的程度。指定 `"auto"`（默认值）、`"off"` 或 `"on"`。
代码生成
`Algorithm`	必须是 `"interior-point"`
`ConstraintTolerance`	约束的可行性容差，非负标量。`ConstraintTolerance` 测量原始可行性容差。默认值为 `1e-6`。
`Display`	显示级别： `"off"`、`"none"` 或 `"final"` 不显示任何输出。 `"iter"` 在每次迭代时显示输出。生成的代码不显示退出消息。
`MaxIterations`	允许的最大迭代次数，非负整数。默认值为 `200`。请参阅容差和停止条件和迭代和函数计算次数。
`OptimalityTolerance`	相对对偶间隙的终止容差，非负标量。有关定义，请参阅公式 5。默认值为 `1e-6`。
预求解	在算法迭代之前，对线性规划 (LP) 进行预求解的程度。指定 `"auto"`（默认值）、`"off"` 或 `"on"`。

示例: options = optimoptions("linprog",Algorithm="interior-point",Display="iter")

`problem` — 问题结构体
结构体

问题结构体，指定为含有以下字段的结构体。

字段名称	条目
`f`	线性目标函数向量 `f`
`Aineq`	线性不等式约束的矩阵
`bineq`	线性不等式约束中的向量 `Aineqx` ≤ `bineq`，或满足 `bl` ≤ `Aineqx` ≤ `b` 的元胞数组 `{bl,b}`。如果使用元胞数组，请确保该数组为单个 1×1 元胞，例如 bcons = {bl b}; problem.bineq = {bcons};
`Aeq`	线性等式约束的矩阵
`beq`	线性等式约束的向量
`lb`	由下界组成的向量
`ub`	由上界组成的向量
`solver`	`'linprog'`
`options`	用 `optimoptions` 创建的选项

您必须在 problem 结构体中至少提供 solver 字段。

小心

problem 参量必须是一个标量结构体。如果将线性约束定义为元胞数组 {bl,b}，则生成的问题结构可以是非标量结构体数组。为确保 problem 是标量，请传入 {{bl,b}}。

数据类型: struct

输出参量

全部折叠

`x` — 解
实数向量 | 实数数组

解，以实数向量或实数数组形式返回。x 的大小与 f 的大小相同。

`fval` — 解处的目标函数值
实数

解处的目标函数值，以实数形式返回。通常，fval = f'*x。

`exitflag` — `linprog` 停止的原因
整数

linprog 停止的原因，以整数形式返回。

`3`	解关于相对 `ConstraintTolerance` 容差可行，但关于绝对容差不可行。
`1`	函数收敛于解 `x`。
`0`	迭代次数超过 `options.MaxIterations` 或求解时间（以秒为单位）超过 `options.MaxTime`。
`-2`	找不到可行点。
`-3`	问题无界。
`-4`	执行算法过程中遇到 `NaN` 值。
`-5`	原始问题和对偶问题均不可行。
`-7`	搜索方向的模变得太小。无法取得进一步进展。
`-8`	步骤未定义，算法因奇异系统而无法继续。仅使用稀疏数据生成代码。切换到完整数据而非稀疏数据可帮助求解器顺利完成求解。
`-9`	求解器失去可行性。
`-10`	问题在于数值不稳定（仅限于 codegen）。

生成的代码可返回退出标志 1、0、-2、-3、-7、-8 和 -10。

退出标志 3 和 -9 与不可行性较大的解相关。此类问题通常源于具有较大条件数的线性约束矩阵，或源于具有较大解分量的问题。要纠正这些问题，请尝试缩放系数矩阵，消除冗余线性约束，或对变量给出更严格的边界。

`output` — 有关优化过程的信息
结构体

有关优化过程的信息，以包含下列字段的结构体形式返回。

`iterations`	迭代次数
`algorithm`	使用的优化算法
`cgiterations`	0（仅限于内点算法，包含以实现向后兼容，不存在于生成的代码中）
`message`	退出消息（不存在于生成的代码中）
`constrviolation`	约束函数的最大值
`firstorderopt`	一阶最优性测度

`lambda` — 解处的拉格朗日乘数
结构体

解处的拉格朗日乘数，以包含下列字段的结构体形式返回。

`lower`	对应于 `lb` 的下界
`upper`	对应于 `ub` 的上界
`ineqlin`	对应于 `A` 和 `b` 的线性不等式
`ineqlinLower`	当线性约束向量为元胞数组 `{bl b}` 时，与 `A` 和 `bl` 对应的线性不等式
`eqlin`	对应于 `Aeq` 和 `beq` 的线性等式

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

$\begin{array}{l} f + A^{T} λ_{ineqlin} - A^{T} λ_{i}_{neqlinLower} + ... \\ {Aeq}^{T} λ_{eqlin} + λ_{upper} - λ_{lower} = 0, \end{array}$

基于拉格朗日函数

$\begin{matrix} f^{T} x + λ_{ineqlin}^{T} (A x - b) + λ_{ineqlinLower}^{T} (b - A x) + ... \\ λ_{eqlin}^{T} (Aeq x - beq) + λ_{upper}^{T} (x - ub) + λ_{lower}^{T} (lb - x) . \end{matrix}$

此符号约定与非线性求解器的符号约定一致（请参阅受约束的最优性理论）。然而，此符号与许多线性规划文献中的符号相反，因此 linprog 拉格朗日乘数是关联的“影子价格”的负数。

`sensitivity` — 线性规划系数的灵敏度
`SensitivityAnalysis` 对象

线性规划系数的灵敏度，以 SensitivityAnalysis 对象形式返回。目前，sensitivity 仅适用于 "dual-simplex-highs" 算法。有关详细信息，请参阅 SensitivityAnalysis。

详细信息

全部折叠

增强版退出消息

接下来的几项列出了可能增强的退出消息 linprog。增强的退出消息在消息的第一句中给出了详细信息的链接。

找到满足约束的最小值

求解器找到一个满足所有边界约束和线性约束的最小化点。由于问题是凸问题，该最小化点是全局最小值。有关详细信息，请参阅局部最优与全局最优。

预求解期间找到解

求解器在预求解阶段找到了解。这意味着有了此边界、线性约束和 f（线性目标系数）可以立即找到解。有关详细信息，请参阅预求解/后求解。

超过迭代限制

linprog 超出了迭代限制。linprog 使用 MaxIterations 选项 (容差) 作为停止标准。

您可以使用圆点表示法来更改选项的值：

options.MaxIterations = 5e4;

您也可以使用 optimoptions 来更改该值：

options = optimoptions(options,MaxIterations=5e4);

超出了时间限制

linprog 使用 MaxTime 选项 (容差) 作为停止标准。

您可以使用圆点表示法来更改选项的值：

options.MaxTime = 5e4;

您也可以使用 optimoptions 来更改该值：

options = optimoptions(options,MaxTime=5e4);

问题无界。

linprog 停止，因为线性规划问题没有解。对于任何目标值，都有目标函数值小于该目标的可行点。

超出了分配给它的内存

linprog 导致内存不足。重新表示问题可能会得到一个解；请参阅 Williams [1]。

找不到可行的解

linprog 停止，因为它找不到可行点。该问题可能不可行。要继续，请检查您的约束，或尝试不同的 linprog 算法。有关检查不一致的线性约束的帮助，请参阅调查线性不可行性。

此问题不可行

在预求解过程中，求解器发现问题的表达式不一致。不一致意味着并非所有约束都能在一个点 x 上得到满足。有关详细信息，请参阅预求解/后求解。

此问题无界

在预求解过程中，求解器找到一个可行方向，在该方向上目标函数无边界地递减。有关详细信息，请参阅预求解/后求解。

问题似乎是无界问题

linprog 停止，因为线性规划问题没有解。对于任何目标值，似乎都有目标函数值小于该目标的可行点。

退出消息的定义

接下来的几项包含以下术语的定义 linprog 退出消息。

容差

一般来说，容差是一个阈值，超过阈值时将终止求解器的迭代。有关容差的详细信息，请参阅容差和停止条件。

运行不同算法

您的选项有 LargeScale 等于 "off"。linprog 现在忽略 LargeScale 选项。

以前，将 LargeScale 设置为 "off" 会导致 linprog 使用中等规模算法。

要避免警告和错误：

请勿使用 LargeScale 选项。
使用 Algorithm 选项选择算法。

提示

使用 optimoptions 设置选项以避免警告。

选择不同的算法

linprog "active-set"、"simplex" 和 "dual-simplex-legacy" 算法已删除。您当前的选项设置指定了其中一种算法。为避免出现警告，并确保代码正确运行，请将 Algorithm 选项设置为默认的 "dual-simplex-highs" 算法，或者 "interior-point" 或 "interior-point-legacy" 算法之一。有关选择算法的详细信息，请参阅线性规划算法。

算法

全部折叠

对偶单纯形 Highs 算法

有关描述，请参阅对偶单纯形 Highs 算法。

内点传统算法

"interior-point-legacy" 方法基于 LIPSOL（线性内点求解器，[3]），它是 Mehrotra 预测-校正算法 [2]（一种原始-对偶内点方法）的变体。在算法开始迭代之前，您需要采取许多预处理步骤。请参阅内点传统线性规划。

算法的第一阶段可能涉及约束的一些预处理（请参阅内点传统线性规划）。一些情况可能会导致 linprog 退出，并显示不可行性消息。在每种情况下，linprog 都返回一个负值 exitflag，表示失败。

如果在 Aeq 中检测到一行全部为零，但 beq 的对应元素不为零，则退出消息为

Exiting due to infeasibility: An all-zero row in the
constraint matrix does not have a zero in corresponding
right-hand-side entry.

如果发现 x 的元素之一无下界，则退出消息为

Exiting due to infeasibility: Objective f'*x is unbounded below.

如果 Aeq 的某一行只有一个非零元素，则 x 中与之对应的值称为单值变量。在这种情况下，可以根据 Aeq 和 beq 计算 x 的该分量的值。如果计算的值违反另一个约束，则退出消息为
```
Exiting due to infeasibility: Singleton variables in
equality constraints are not feasible.
```

如果单值变量可以得到求解，但该解违反上界或下界，则退出消息为

Exiting due to infeasibility: Singleton variables in
the equality constraints are not within bounds.

注意

预处理步骤是累积的。例如，即使约束矩阵一开始没有全部为零的行，其他预处理步骤也可能导致出现这样的行。

预处理完成后，算法的迭代部分开始执行，直到满足终止条件。（有关残差、原始问题、对偶问题和相关终止条件的详细信息，请参阅内点传统线性规划。）如果残差在增大而不是减小，或残差既不增大也不减小，则对应显示以下两条终止消息之一，

One or more of the residuals, duality gap, or total relative error 
has grown 100000 times greater than its minimum value so far:

或

One or more of the residuals, duality gap, or total relative error 
has stalled:

显示上述消息后，还将显示以下消息之一，表明对偶问题、原始问题或两者似乎都不可行。

The dual appears to be infeasible (and the primal unbounded). (The primal residual < OptimalityTolerance.)
The primal appears to be infeasible (and the dual unbounded). (The dual residual < OptimalityTolerance.)
The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(OptimalityTolerance). (The primal residual < 10*OptimalityTolerance.)
The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(OptimalityTolerance). (The dual residual < 10*OptimalityTolerance.)
The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.
The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.
Both the primal and the dual appear to be infeasible.

例如，原始（目标）可以无界，原始残差（用于测量原始约束的满足程度）可以很小。

内点算法

"interior-point" 算法类似于 "interior-point-legacy"，但具有更高效的分解例程和不同的预处理。请参阅内点 linprog 算法。

代码生成算法

linprog 使用 coneprog 求解器生成代码。在这种情况下，coneprog 求解器不使用二阶锥约束。迭代输出显示与 coneprog 求解器相同的字段。有关 coneprog 算法的详细信息，请参阅二阶锥规划算法。

替代功能

App

优化实时编辑器任务为 linprog 提供了一个可视化界面。

参考

[1] Dantzig, G.B., A. Orden, and P. Wolfe. “Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints.” Pacific Journal Math., Vol. 5, 1955, pp. 183–195.

[2] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp. 575–601.

[3] Zhang, Y., “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment.” Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.

扩展功能

全部展开

C/C++ 代码生成
使用 MATLAB® Coder™ 生成 C 代码和 C++ 代码。

用法说明和限制：

linprog 支持使用 codegen (MATLAB Coder) 函数或 MATLAB^® Coder™ 生成代码。您必须拥有 MATLAB Coder 许可证才能生成代码。
目标硬件必须支持标准双精度浮点计算。
代码生成目标与 MATLAB 求解器不使用相同的数学核心函数库。因此，代码生成解可能不同于求解器解，尤其是对于病态问题。
在生成代码时，linprog 不支持 problem 参量。
```
[x,fval] = linprog(problem) % Not supported
```
所有的 linprog 输入矩阵，如 A、Aeq、lb 和 ub，都可以是满矩阵或稀疏矩阵。要使用稀疏输入，必须启用动态内存分配。请参阅Code Generation Limitations (MATLAB Coder)。当非零项的占比很小时，求解器在使用稀疏输入的情况下表现良好。
参量 lb 和 ub 的条目数必须与线性目标函数向量 f 相同，否则，它们必须为空 []。
如果您的目标硬件不支持无限边界，请使用 optim.coder.infbound。
对于涉及嵌入式处理器的高级代码优化，您还需要 Embedded Coder^® 许可证。
您必须包括适用于 linprog 的选项，并使用 optimoptions 指定这些选项。选项必须包括设置为 "interior-point" 的 Algorithm 选项。
```
options = optimoptions("linprog",Algorithm="interior-point");
[x,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb,ub,options);
```
代码生成支持以下选项：
- Algorithm - 必须为 "interior-point"
- ConstraintTolerance
- Display - 指定为 "off"、"none" 或 "final"（对于无输出），或指定为 "iter"（对于迭代输出）
- MaxIterations
- OptimalityTolerance
- 预求解 - 指定为 "auto"（默认）、"off" 或 "on"。一个“隐藏”选项；请参阅隐藏选项。

生成的代码只会对选项进行有限的错误检查。更新选项的推荐方法是使用点符号，而不是 optimoptions。

opts = optimoptions("linprog",Algorithm="interior-point");
opts = optimoptions(opts,MaxIterations=1e4); % Not recommended
opts.MaxIterations = 1e4; % Recommended

linprog 支持传递给求解器的选项，而不仅仅是在代码中创建的选项。
如果您指定了不受支持的选项，在代码生成过程中通常会忽略该选项。为了获得可靠的结果，请仅指定支持的选项。

版本历史记录

在 R2006a 之前推出

全部展开

R2026a: 使用 `"dual-simplex-highs"` 算法返回灵敏度信息

使用 "dual-simplex-highs" 算法时，您可以获取该解的灵敏度信息。该信息作为 SensitivityAnalysis 对象，在 linprog 的第六个输出中返回。有关详细信息（包括拉格朗日乘子与灵敏度信息的比较），请参阅对象参考页面。

R2026a: 使用线性范围约束求解

linprog 求解器支持线性范围约束，即上界和下界线性约束：

$bl \leq A x \leq b .$

将线性约束向量指定为元胞数组 {bl b}。有关示例，请参阅线性范围约束。

输出拉格朗日乘子结构体中包含一个名为 ineqlinLower 的字段，该字段与输入 bl 相关联。

R2026a: `"interior-point"` 算法的 `Presolve` 选项

现在，您可以通过预求解选项为 linprog "interior-point" 算法指定预求解的级别。此选项也可用于代码生成。Presolve 选项仍然是一个“隐藏”选项，即 optimoptions 不会显示该选项或其设置。请参阅隐藏选项。

R2025a: 为 `linprog` 生成代码

linprog "interior-point" 算法可生成 C 或 C++ 代码。所有输入矩阵，如 A、Aeq、lb 和 ub，都可以是满矩阵或稀疏矩阵。有关详细信息，请参阅linprog 背景下的代码生成。

R2025a: 对 `linprog` `"interior-point"` 算法进行不同的预处理

linprog "interior-point" 算法使用的是 HiGHS 预处理（也称为预分解），而不是传统的预处理模块。在大多数测试案例中，linprog 通过 HiGHS 预处理提高了速度，且结果变化可忽略不计。

在使用 HiGHS 预处理时，如果您的问题未能得到快速解决，或者您有一个非正值退出标志，则可以尝试放松 OptimalityTolerance 和 ConstraintTolerance 选项。例如，尝试使用 optimoptions 将其中一个或两个都设置为 1e-5。在几乎所有的测试案例中，这种调整都能使 linprog "interior-point" 算法快速准确地解决问题。

R2025a: `"dual-simplex-legacy"` 算法已删除

linprog "dual-simplex-legacy" 算法已删除。

R2024b: `"dual-simplex-legacy"` 算法将被删除

linprog "dual-simplex-legacy" 算法将在未来的版本中被删除。

R2024a: 新的 `"dual-simplex-highs"` 算法成为默认值

linprog 增加了一个 "dual-simplex-highs" 算法，该算法现在成为默认算法。对于大多数问题，此算法的性能优于先前的默认算法，后者已重命名为 "dual-simplex-legacy"。"dual-simplex-highs" 算法基于 HiGHS 开源代码。

要使用先前的默认算法，请使用 optimoptions 将 Algorithm 选项设置为 "dual-simplex-legacy"。迭代输出与以前不同。

另请参阅

linprog

语法

说明

示例

线性规划、线性不等式约束

具有线性不等式和等式的线性规划

具有所有约束类型的线性规划

使用 "interior-point" 算法的线性规划

为 linprog 使用基于问题的方法求解 LP

返回目标函数值

获取更多输出结果以分析解过程

获得解和拉格朗日乘数

获取灵敏度

输入参数

f — 系数向量 实数向量 | 实数数组

A — 线性不等式约束 实矩阵

Aeq — 线性等式约束 实矩阵

b — 线性不等式约束 实数向量 | 由实数数组组成的两元元胞数组

beq — 线性等式约束 实数向量

lb — 下界 实数向量 | 实数数组

ub — 上界 实数向量 | 实数数组

options — 优化选项 optimoptions 的输出 | optimset 返回的结构体

problem — 问题结构体 结构体

输出参量

x — 解 实数向量 | 实数数组

fval — 解处的目标函数值 实数

exitflag — linprog 停止的原因 整数

output — 有关优化过程的信息 结构体

lambda — 解处的拉格朗日乘数 结构体

sensitivity — 线性规划系数的灵敏度 SensitivityAnalysis 对象

详细信息

增强版退出消息

找到满足约束的最小值

预求解期间找到解

超过迭代限制

超出了时间限制

问题无界。

超出了分配给它的内存

找不到可行的解

此问题不可行

此问题无界

问题似乎是无界问题

退出消息的定义

容差

运行不同算法

选择不同的算法

算法

对偶单纯形 Highs 算法

内点传统算法

内点算法

代码生成算法

替代功能

App

参考

扩展功能

C/C++ 代码生成 使用 MATLAB® Coder™ 生成 C 代码和 C++ 代码。

版本历史记录

R2026a: 使用 "dual-simplex-highs" 算法返回灵敏度信息

R2026a: 使用线性范围约束求解

R2026a: "interior-point" 算法的 Presolve 选项

R2025a: 为 linprog 生成代码

R2025a: 对 linprog "interior-point" 算法进行不同的预处理

R2025a: "dual-simplex-legacy" 算法已删除

R2024b: "dual-simplex-legacy" 算法将被删除

R2024a: 新的 "dual-simplex-highs" 算法成为默认值

另请参阅

主题

使用 `"interior-point"` 算法的线性规划

为 `linprog` 使用基于问题的方法求解 LP

`f` — 系数向量
实数向量 | 实数数组

`A` — 线性不等式约束
实矩阵

`Aeq` — 线性等式约束
实矩阵

`b` — 线性不等式约束
实数向量 | 由实数数组组成的两元元胞数组

`beq` — 线性等式约束
实数向量

`lb` — 下界
实数向量 | 实数数组

`ub` — 上界
实数向量 | 实数数组

`options` — 优化选项
`optimoptions` 的输出 | `optimset` 返回的结构体

`problem` — 问题结构体
结构体

`x` — 解
实数向量 | 实数数组

`fval` — 解处的目标函数值
实数

`exitflag` — `linprog` 停止的原因
整数

`output` — 有关优化过程的信息
结构体

`lambda` — 解处的拉格朗日乘数
结构体

`sensitivity` — 线性规划系数的灵敏度
`SensitivityAnalysis` 对象

C/C++ 代码生成
使用 MATLAB® Coder™ 生成 C 代码和 C++ 代码。

R2026a: 使用 `"dual-simplex-highs"` 算法返回灵敏度信息

R2026a: `"interior-point"` 算法的 `Presolve` 选项

R2025a: 为 `linprog` 生成代码

R2025a: 对 `linprog` `"interior-point"` 算法进行不同的预处理

R2025a: `"dual-simplex-legacy"` 算法已删除

R2024b: `"dual-simplex-legacy"` 算法将被删除

R2024a: 新的 `"dual-simplex-highs"` 算法成为默认值