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

説明

線形計画法ソルバー

以下で指定された問題の最小値を見つけます。

$$\underset{x}{\min }{f}^{T}x\text{ such that }\{\begin{array}{c}A\cdot x\le b,\\ Aeq\cdot x=beq,\\ lb\le x\le ub.\end{array}$$

f、x、b、beq、lb、ub はベクトル、A と Aeq は行列です。

メモ

linprog は、ソルバーベースのアプローチのみに適用されます。問題ベースのアプローチの場合は、solve を使用してください。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。

x = linprog(f,A,b) は A*x ≤ b となるような最小の f'*x を解きます。

x = linprog(f,A,b,Aeq,beq) には、等式制約 Aeq*x = beq が含まれます。不等式が存在しない場合は A = [] および b = [] と設定してください。

x = linprog(f,A,b,Aeq,beq,lb,ub) は、解が常に lb ≤ x ≤ ub の範囲に存在するように、設計変数 x に上限と下限を定義します。等式が存在しない場合には 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(___) は、すべての入力引数に対して、解 x での目的関数 fun の値 (fval = f'*x) を返します。

[x,fval,exitflag,output] = linprog(___) は上記に加え、終了条件を記述する値 exitflag、および最適化プロセスに関する情報を含む構造体 output を返します。

[x,fval,exitflag,output,lambda] = linprog(___) は上記に加え、解 x におけるラグランジュ乗数をフィールドに含む、構造体 lambda を返します。

例

線形計画法、線形不等式制約

線形不等式で定義された単純な線形計画法を解きます。

この例では、次の線形不等式制約を使用します。

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

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

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

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

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

$$-x(1)+x(2)\le 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)\le 2$$

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

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

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

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

$$-x(1)+x(2)\le 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)\le 2$$

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

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

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

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

$$-x(1)+x(2)\le 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\le x(1)\le 1.5$$

$$-0.5\le x(2)\le 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' アルゴリズムを使用した線形計画法

'interior-point' アルゴリズムを使用して線形計画法を解きます。

この例では、次の線形不等式制約を使用します。

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

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

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

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

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

$$-x(1)+x(2)\le 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\le x(1)\le 1.5$$

$$-0.5\le x(2)\le 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.

x = 2×1

    0.1875
    1.2500

linprog の場合に問題ベースのアプローチを使用して LP を解く

この例では、問題ベースのアプローチを使用して問題を設定し、次にソルバーベースのアプローチを使用してその問題を解く方法を示します。問題は、次のとおりです。

$$\underset{x}{\max }(x+y/3)subjectto\{\begin{array}{l}x+y\le 2\\ x+y/4\le 1\\ x-y\le 2\\ x/4+y\ge -1\\ x+y\ge 1\\ -x+y\le 2\\ x+y/4=1/2\\ -1\le x\le 1.5\\ -1/2\le y\le 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: [1×1 optim.problemdef.OptimizationVariable]
    y: [1×1 optim.problemdef.OptimizationVariable]

予想どおり、sol(1) が x に、sol(2) が y に対応します。アルゴリズムを参照してください。

目的関数値を返す

単純な線形計画法の解および目的関数値を計算します。

非線形制約は次のとおりです。

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

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

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

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

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

$$-x(1)+x(2)\le 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)\le 2$$

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

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

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

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

$$-x(1)+x(2)\le 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\le x(1)\le 1.5$$

$$-0.5\le x(2)\le 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
          algorithm: 'dual-simplex-highs'
    constrviolation: 0
            message: 'Optimal solution found.'
      firstorderopt: 0

• 目的関数値 fval は、より多くの制約があるため、目的関数値を返すの場合より大きくなります。

• exitflag = 1 は、解が信頼できることを示します。

• output.iterations = 0 は、linprog が解決の前処理で解を見つけ、反復がまったく必要なかったことを示します。

解およびラグランジュ乗数の取得

単純な線形計画法を解き、解およびラグランジュ乗数を検証します。

次の目的関数を使用します。

$$f(x)=-5x_1-4x_2-6x_3.$$

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

次の線形不等式制約を使用します。

$$x_1-x_2+x_3\le 20$$

$$3x_1+2x_2+4x_3\le 42$$

$$3x_1+2x_2\le 30.$$

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

すべての変数が正になるように制約します。

$$x_1\ge 0$$

$$x_2\ge 0$$

$$x_3\ge 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 = 3×1

     0
    15
     3

ans = 3×1

         0
    1.5000
    0.5000

ans = 3×1

     1
     0
     0

lambda.ineqlin は、x の 2 番目および 3 番目の成分について非ゼロです。これは、2 番目および 3 番目の線形不等式制約が次の等式で満たされることを示します。

$$3x_1+2x_2+4x_3=42$$

$$3x_1+2x_2=30.$$

これが真であることを確認します。

A*x

ans = 3×1

   -12
    42
    30

lambda.lower は、x の 1 番目の成分について非ゼロです。これは、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 は 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 を使用します。

データ型: single | double

beq — 線形等式制約

実数ベクトル

実数ベクトルで指定される線形等式制約です。beq は、行列 Aeq に関連する Me 要素ベクトルです。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 を使用します。

データ型: 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	反復の最大許容回数 (非負の整数)。既定値は以下のとおりです。 "dual-simplex-highs" アルゴリズムの場合は intmax (約 2.1475e+09) "interior-point" アルゴリズムの場合は 200 "interior-point-legacy" アルゴリズムの場合は 85 詳細については、許容誤差と停止条件および反復と関数カウントを参照してください。 optimset の場合、名前は MaxIter です。新旧のオプション名を参照してください。
OptimalityTolerance	双対実行可能性に関する終了許容誤差 (非負のスカラー)。既定値は以下のとおりです。 "dual-simplex-highs" アルゴリズムの場合は 1e-7 "interior-point" アルゴリズムの場合は 1e-6 "interior-point-legacy" アルゴリズムの場合は 1e-8 optimset の場合、名前は TolFun です。新旧のオプション名を参照してください。
HiGHS 双対シンプレックス法アルゴリズム
ConstraintTolerance	制約の実行可能性の許容誤差で非負のスカラー。ConstraintTolerance は、主実行可能性の許容誤差を測定します。既定値は 1e-7 です。
MaxTime	アルゴリズムを実行する秒単位の最長時間。既定値は Inf です。
Presolve	双対シンプレックス法アルゴリズムの反復前に行われる LP の解決の前処理のレベル。"auto" (既定の設定)、"off"、または "on" を指定します。
内点法アルゴリズム
ConstraintTolerance	制約の実行可能性の許容誤差で非負のスカラー。ConstraintTolerance は、主実行可能性の許容誤差を測定します。既定値は 1e-6 です。 optimset の場合、名前は TolCon です。新旧のオプション名を参照してください。
コード生成
Algorithm	"interior-point" でなければなりません。
ConstraintTolerance	制約の実行可能性の許容誤差で非負のスカラー。ConstraintTolerance は、主実行可能性の許容誤差を測定します。既定値は 1e-6 です。
Display	表示レベル: "off"、"none"、または "final" — 出力を表示しない。 "iter" — 各反復の出力を表示する。 生成されたコードでは、終了メッセージは表示されません。
MaxIterations	反復の最大許容回数 (非負の整数)。既定値は 200 です。 詳細については、許容誤差と停止条件および反復と関数カウントを参照してください。
OptimalityTolerance	相対的な双対性ギャップに関する終了許容誤差 (非負のスカラー)。定義については、式 5を参照してください。既定値は 1e-6 です。

例: 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	探索方向が小さくなりすぎ、これ以上進むことができないことを示します。
-8	未定義のステップ。システムが特異であるため、アルゴリズムを続行できません。スパース データのみを使用したコード生成です。スパースではなく非スパース データに切り替えると、ソルバーを正常に完了できます。
-9	ソルバーが実行可能性を失いました。
-10	問題が数値的に不安定です (codegen のみ)。

生成されたコードは、終了フラグ 1、0、-2、-3、-7、-8、および -10 を返す場合があります。

終了フラグ 3 と -9 は、実行可能性が大きい解に関連しています。これらは通常、条件数が大きい線形制約行列、または大きな解の成分を含む問題から生じます。これらの問題を修正するには、係数行列のスケーリング、冗長な線形制約の除去、または変数に対するより狭い範囲の指定を試します。

output — 最適化プロセスに関する情報

構造体

最適化プロセスに関する情報。次のフィールドをもつ構造体として返されます。

iterations	反復回数
algorithm	使用される最適化アルゴリズム
cgiterations	0 (内点法アルゴリズムのみ。下位互換性のために含められ、生成されたコードにはありません)
message	終了メッセージ (生成されたコードにはありません)
constrviolation	制約関数の最大値
firstorderopt	1 次の最適性の尺度

lambda — 解におけるラグランジュ乗数

構造体

解におけるラグランジュ乗数。次のフィールドをもつ構造体として返されます。

lower	lb に対応する下限
upper	ub に対応する上限
ineqlin	A および b に対応する線形不等式
eqlin	Aeq および beq に対応する線形等式

線形制約のラグランジュ乗数は、length(f) 個の成分をもつ以下の方程式を満たします。

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

これは、以下のラグランジュ関数に基づきます。

$${\text{f}}^{T}x+{\lambda }_{\text{ineqlin}}^T\left(\text{A}x-\text{b}\right)+{\lambda }_{\text{eqlin}}^T\left(\text{Aeq}x-\text{beq}\right)+{\lambda }_{\text{upper}}^T\left(x-\text{ub}\right)+{\lambda }_{\text{lower}}^T\left(\text{lb}-x\right).$$

この符号規則は、非線形ソルバーの符号規則と一致します (制約付きの最適性の理論を参照)。ただし、この符号は多くの線形計画法の文献における符号とは逆です。そのため、linprog のラグランジュ乗数は、関連する "シャドウ プライス" の負の値になります。

詳細

より詳細な終了メッセージ

次のいくつかの項目は、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 (Linear Interior Point Solver、[3]) をベースにしています。この方法は、主双対内点法である Mehrotra 予測子修正子アルゴリズム[2]に変更を加えたものです。アルゴリズムの中で、反復が始まる前に、いくつかの前処理手順が行われます。レガシ内点線形計画法を参照してください。

アルゴリズムの第 1 ステージでは、何らかの制約の前処理を伴います(レガシ内点線形計画法 を参照)。いくつかの条件では 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 の要素の 1 つが制約の下限を満たしていない場合、終了メッセージは次のようになります。

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

• Aeq の行の中で、非ゼロ要素が 1 つしかない場合、x の中でそれに対応する値を "シングルトン" 変数と言います。この場合、x のその構成要素の値を Aeq および beq から計算することができます。計算した値が別の制約に違反する場合、終了メッセージは次のようになります。

  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.

メモ:

前処理手順は累積的な性質をもちます。そのため、制約行列に行全体がすべてゼロであるような行が存在しない場合でさえ、他の前処理手順により、すべての要素がゼロになる可能性もあります。

前処理が終了すると、停止条件を満たすまで、反復部分のアルゴリズムが始まります。(残差、主問題、双対問題、および関連する停止条件の詳細については、レガシ内点線形計画法を参照。) 残差が少なくならずに大きくなる場合、または残差が大きくも小さくもならない場合、次の 2 つの終了メッセージのどちらかが表示されます。

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:

これらのメッセージの 1 つを表示した後、双対、主、またはその両方が実行不可能である場合、そのいずれかを示す次のメッセージの中の 1 つが表示されます。

• 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 ソルバーは 2 次錐制約を使用しません。反復表示では、coneprog ソルバーと同じフィールドが表示されます。coneprog アルゴリズムの詳細については、2 次錐計画法アルゴリズムを参照してください。

代替機能

アプリ

[最適化] ライブ エディター タスクが 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 など) はすべて完全でもスパースでもかまいません。スパース入力を使用するには、動的メモリ割り当てを有効にする必要があります。コード生成の制限 (MATLAB Coder)を参照してください。非ゼロのエントリの割合が少ない場合、スパース入力を使用するとソルバーは良好なパフォーマンスを示します。

• lb 引数と ub 引数は、線形目的関数ベクトル f と同じ数のエントリをもつか、空の [] でなければなりません。

• ターゲット ハードウェアが無限境界をサポートしていない場合は、optim.coder.infbound を使用します。

• 組み込みプロセッサを使用する高度なコード最適化には、Embedded Coder^® ライセンスも必要です。

• linprog のオプションを含め、関数 optimoptions を使用して指定しなければなりません。オプションには Algorithm オプションを含め、"interior-point" に設定しなければなりません。

  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

• 生成コードでは、オプションに対して限られたエラー チェックしか行われません。オプションの更新方法として、optimoptions ではなく、ドット表記を使用することを推奨します。

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

• linprog は、コードで作成されたオプションだけでなく、ソルバーに渡されたオプションをサポートします。

• サポートされていないオプションを指定すると、通常はコード生成の際にそのオプションは無視されます。信頼できる結果を得るために、サポートされているオプションのみを指定します。

バージョン履歴

R2006a より前に導入

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" に設定します。反復表示は以前とは異なります。

参考

intlinprog | mpsread | optimoptions | prob2struct | quadprog | 最適化

トピック

• 線形計画法の設定、ソルバーベース
• 一般的な線形計画問題
• 線形計画法を使用した長期投資の運用最大化: ソルバーベース
• ソルバーベースの最適化問題の設定
• 線形計画法のアルゴリズム