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(___)

说明

非线性规划求解器

求以下问题的最小值：

$\min_{x} f^{T} x such that {\begin{matrix} A \cdot x \leq b, \\ A e q \cdot x = b e q, \\ l b \leq x \leq u b . \end{matrix}$

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

注意

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

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 = []。

注意

如果问题的指定输入边界不一致，则输出 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 (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)

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in feasible directions, to within the function tolerance, and constraints are satisfied to within the constraint tolerance.

为 `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
          algorithm: 'dual-simplex-highs'
    constrviolation: 0
            message: 'Optimal solution found.'
      firstorderopt: 0

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

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

prob.Variables

ans = struct with fields:
    x: [1x1 optim.problemdef.OptimizationVariable]
    y: [1x1 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
          algorithm: 'dual-simplex-highs'
    constrviolation: 0
            message: 'Optimal solution found.'
      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` — 系数向量
实数向量 | 实数数组

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

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

数据类型: double

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

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

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

A*x <= b,

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

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

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

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

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

示例: 要指定 x 的各个分量加起来等于或小于 1，请指定 A = ones(1,N) 和 b = 1。

数据类型: 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 是与 A 矩阵相关的包含 M 个元素的向量。如果将 b 作为行向量传递，求解器会在内部将 b 转换为列向量 b(:)。对于大型问题，将 b 作为稀疏向量传递。

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

A*x <= b,

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

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

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

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

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

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

数据类型: double

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

线性等式约束，指定为实数向量。beq 是与 Aeq 矩阵相关的包含 Me 个元素的向量。如果将 beq 作为行向量传递，求解器会在内部将 beq 转换为列向量 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。

数据类型: 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'`（默认值） `'dual-simplex-legacy'` `'interior-point'` `'interior-point-legacy'` 有关选择算法的信息，请参阅线性规划算法。
Diagnostics	显示关于要最小化或求解的函数的诊断信息。选择 `'off'`（默认值）或 `'on'`。
`Display`	显示级别（请参阅迭代输出）： `'final'`（默认值）仅显示最终输出。 `'off'` 或 `'none'` 不显示输出。 `'iter'` 在每次迭代时显示输出。
`MaxIterations`	允许的最大迭代次数，非负整数。默认值为： `intmax`（对于 `'dual-simplex-highs'` 算法，大约为 `2.1475e+09`） `10*(numberOfEqualities + numberOfInequalities + numberOfVariables)`（对于 `'dual-simplex-legacy'` 算法） `200`（对于 `'interior-point'` 算法） `85`（对于 `'interior-point-legacy'` 算法）请参阅容差和停止条件和迭代和函数计算次数。对于 `optimset`，名称是 `MaxIter`。请参阅当前选项名称和旧选项名称。
`OptimalityTolerance`	对偶可行性的终止容差，非负标量。默认值为： `1e-7`（对于 `'dual-simplex-highs'` 和 `'dual-simplex-legacy'` 算法） `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-4`。对于 `optimset`，名称是 `TolCon`。请参阅当前选项名称和旧选项名称。
`MaxTime`	算法运行的最长时间（以秒为单位）。默认值为 `Inf`。
Preprocess	对偶单纯形算法迭代前的 LP 预处理的级别。指定 `'basic'`（默认值）或 `'none'`。
内点算法
`ConstraintTolerance`	约束的可行性容差，非负标量。`ConstraintTolerance` 测量原始可行性容差。默认值为 `1e-6`。对于 `optimset`，名称是 `TolCon`。请参阅当前选项名称和旧选项名称。

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

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

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

字段名称	条目
`f`	线性目标函数向量 `f`
`Aineq`	线性不等式约束的矩阵
`bineq`	线性不等式约束的向量
`Aeq`	线性等式约束的矩阵
`beq`	线性等式约束的向量
`lb`	由下界组成的向量
`ub`	由上界组成的向量
`solver`	`'linprog'`
`options`	用 `optimoptions` 创建的选项

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

数据类型: 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`	搜索方向的模变得太小。无法取得进一步进展。
`-9`	求解器失去可行性。

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

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

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

`iterations`	迭代次数
`algorithm`	使用的优化算法
`cgiterations`	0（仅内点算法，包含它是为了支持向后兼容性）
`message`	退出消息
`constrviolation`	约束函数的最大值
`firstorderopt`	一阶最优性测度

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

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

`lower`	对应于 `lb` 的下界
`upper`	对应于 `ub` 的上界
`ineqlin`	对应于 `A` 和 `b` 的线性不等式
`eqlin`	对应于 `Aeq` 和 `beq` 的线性等式

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

$f + A^{T} λ_{ineqlin} + {Aeq}^{T} λ_{eqlin} + λ_{upper} - λ_{lower} = 0,$

基于拉格朗日函数

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

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

算法

全部折叠

对偶单纯形 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 算法。

替代功能

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.

版本历史记录

在 R2006a 之前推出

全部展开

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 — 解处的拉格朗日乘数 结构体

算法

对偶单纯形 Highs 算法

对偶单纯形传统算法

内点传统算法

内点算法

替代功能

App

参考

版本历史记录

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

另请参阅

主题

WeChat

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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