このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

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 は、ソルバーベースのアプローチのみに適用されます。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)

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.

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: [1x1 optim.problemdef.OptimizationVariable]
    y: [1x1 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 をスパース ベクトルとして渡します。

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	反復の最大許容回数 (非負の整数)。既定値は以下のとおりです。 'dual-simplex-highs' アルゴリズムの場合は intmax (約 2.1475e+09) 'dual-simplex-legacy' アルゴリズムの場合は 10*(numberOfEqualities + numberOfInequalities + numberOfVariables) 'interior-point' アルゴリズムの場合は 200 'interior-point-legacy' アルゴリズムの場合は 85 詳細については、許容誤差と停止条件と反復と関数カウントを参照してください。 optimset の場合、名前は MaxIter です。詳細については、新旧のオプション名を参照してください。
OptimalityTolerance	双対実行可能性に関する終了許容誤差 (非負のスカラー)。既定値は以下のとおりです。 'dual-simplex-highs' アルゴリズムおよび 'dual-simplex-legacy' アルゴリズムの場合は 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-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	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 のラグランジュ乗数は、関連する "シャドウ プライス" の負の値になります。

アルゴリズム

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 にビジュアル インターフェイスを提供します。

参照

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

参考

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

トピック

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