Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

linprog

求解线性规划问题

说明

非线性规划求解器

求以下问题的最小值:

minxfTx such that {Axb,Aeqx=beq,lbxub.

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 结构体。您还可以使用 prob2structOptimizationProblem 对象创建 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)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)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 = 2×1

    0.6667
    1.3333

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)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 = 2×1

     0
     2

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)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;

设置以下边界:

-1x(1)1.5

-0.5x(2)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.
x = 2×1

    0.1875
    1.2500

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)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;

设置以下边界:

-1x(1)1.5

-0.5x(2)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 selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.
x = 2×1

    0.1875
    1.2500

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

maxx(x+y/3)subjectto{x+y2x+y/41x-y2x/4+y-1x+y1-x+y2x+y/4=1/2-1x1.5-1/2y1.25

创建名为 probOptimizationProblem 对象来表示此问题。

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'
      firstorderopt: 0

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

sol 的哪个分量对应于哪个优化变量?查看 probVariables 属性。

prob.Variables
ans = struct with fields:
    x: [1x1 optim.problemdef.OptimizationVariable]
    y: [1x1 optim.problemdef.OptimizationVariable]

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

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

不等式约束是

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)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.
x = 2×1

    0.6667
    1.3333

fval = -1.1111

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

-x(1)/4-x(2)1

-x(1)-x(2)-1

-x(1)+x(2)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;

设置以下边界:

-1x(1)1.5

-0.5x(2)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.
x = 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'
      firstorderopt: 0

  • 目标函数值 fval 大于 返回目标函数值,因为约束更多。

  • exitflag = 1 表示解可靠。

  • output.iterations = 0 表示 linprog 在预求解过程中即找到解,根本不必进行迭代。

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

使用目标函数

f(x)=-5x1-4x2-6x3.

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

使用线性不等式约束

x1-x2+x320

3x1+2x2+4x342

3x1+2x230.

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

将所有变量约束为正值:

x10

x20

x30.

lb = zeros(3,1);

Aeqbeq 设置为 [],表示没有线性等式约束。

Aeq = [];
beq = [];

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

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

检查解和拉格朗日乘数。

x,lambda.ineqlin,lambda.lower
x = 3×1

         0
   15.0000
    3.0000

ans = 3×1

         0
    1.5000
    0.5000

ans = 3×1

    1.0000
         0
         0

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

3x1+2x2+4x3=42

3x1+2x2=30.

检查这是否属实:

A*x
ans = 3×1

  -12.0000
   42.0000
   30.0000

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

输入参数

全部折叠

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

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

数据类型: double

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

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

A*x <= b

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

例如,假设有以下不等式:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30。

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

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

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

数据类型: double

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

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

Aeq*x = beq

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

例如,请参考以下等式:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20。

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

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

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

数据类型: double

线性不等式约束,指定为实数向量。b 是与 A 矩阵相关的包含 M 个元素的向量。如果将 b 作为行向量传递,求解器会在内部将 b 转换为列向量 b(:)。对于大型问题,将 b 作为稀疏向量传递。

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

A*x <= b

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

例如,假设有以下不等式:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30。

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

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

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

数据类型: double

线性等式约束,指定为实数向量。beq 是与 Aeq 矩阵相关的包含 Me 个元素的向量。如果将 beq 作为行向量传递,求解器会在内部将 beq 转换为列向量 beq(:)。对于大型问题,将 beq 作为稀疏向量传递。

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

Aeq*x = beq

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

例如,请参考以下等式:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20。

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

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

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

数据类型: double

下界,指定为实数向量或实数数组。如果 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

上界,指定为实数向量或实数数组。如果 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

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

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

optimoptions 显示中缺少某些选项。这些选项在下表中以斜体显示。有关详细信息,请参阅View Options

所有算法
Algorithm

选择优化算法:

  • 'dual-simplex'(默认值)

  • 'interior-point-legacy'

  • 'interior-point'

有关选择算法的信息,请参阅线性规划算法

Diagnostics

显示关于要最小化或求解的函数的诊断信息。选择 'off'(默认值)或 'on'

Display

显示级别(请参阅迭代输出):

  • 'final'(默认值)仅显示最终输出。

  • 'off''none' 不显示输出。

  • 'iter' 在每次迭代时显示输出。

MaxIterations

允许的迭代最大次数,为正整数。默认值为:

  • 85(对于 'interior-point-legacy' 算法)

  • 200(对于 'interior-point' 算法)

  • 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)(对于 'dual-simplex' 算法)

请参阅容差和停止条件迭代和函数计算次数

对于 optimset,名称是 MaxIter。请参阅当前选项名称和旧选项名称

OptimalityTolerance

对偶可行性的终止容差,正标量。默认值为:

  • 1e-8(对于 'interior-point-legacy' 算法)

  • 1e-7(对于 'dual-simplex' 算法)

  • 1e-6(对于 'interior-point' 算法)

对于 optimset,名称是 TolFun。请参阅当前选项名称和旧选项名称

内点算法
ConstraintTolerance

约束的可行性容差,1e-101e-3 范围内的标量。ConstraintTolerance 度量原始可行性容差。默认值为 1e-6

对于 optimset,名称是 TolCon。请参阅当前选项名称和旧选项名称

Preprocess

算法迭代前的 LP 预处理的级别。指定 'basic'(默认值)或 'none'

对偶单纯形算法
ConstraintTolerance

约束的可行性容差,1e-101e-3 范围内的标量。ConstraintTolerance 度量原始可行性容差。默认值为 1e-4

对于 optimset,名称是 TolCon。请参阅当前选项名称和旧选项名称

MaxTime

算法运行的最长时间(以秒为单位)。默认值为 Inf

Preprocess

对偶单纯形算法迭代前的 LP 预处理的级别。指定 'basic'(默认值)或 'none'

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

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

字段名称条目

f

线性目标函数向量 f

Aineq

线性不等式约束的矩阵

bineq

线性不等式约束的向量

Aeq

线性等式约束的矩阵

beq

线性等式约束的向量
lb由下界组成的向量
ub由上界组成的向量

solver

'linprog'

options

optimoptions 创建的选项

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

数据类型: struct

输出参数

全部折叠

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

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

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

3

解关于相对 ConstraintTolerance 容差可行,但关于绝对容差不可行。

1

函数收敛于解 x

0

迭代次数超过 options.MaxIterations 或求解时间(以秒为单位)超过 options.MaxTime

-2

找不到可行点。

-3

问题无界。

-4

执行算法过程中遇到 NaN 值。

-5

原始问题和对偶问题均不可行。

-7

搜索方向的模变得太小。无法取得进一步进展。

-9

求解器失去可行性。

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

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

iterations

迭代次数

algorithm

使用的优化算法

cgiterations

0(仅内点算法,包含它是为了支持向后兼容性)

message

退出消息

constrviolation

约束函数的最大值

firstorderopt

一阶最优性度量

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

lower

对应于 lb 的下界

upper

对应于 ub 的上界

ineqlin

对应于 Ab 的线性不等式

eqlin

对应于 Aeqbeq 的线性等式

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

f+ATλineqlin+AeqTλeqlin+λupperλlower=0,

基于拉格朗日函数

fTx+λineqlinT(Axb)+λeqlinT(Aeqxbeq)+λupperT(xub)+λlowerT(lbx).

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

算法

全部折叠

对偶单纯形算法

有关说明,请参阅对偶单纯形算法

内点传统算法

'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 中与之对应的值称为单值变量。在这种情况下,可以根据 Aeqbeq 计算 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 之前推出