ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

linprog

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

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

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

構文

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,x0)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
x = linprog(problem)
[x,fval] = linprog(...)
[x,fval,exitflag] = linprog(...)
[x,fval,exitflag,output] = linprog(...)
[x,fval,exitflag,output,lambda] = linprog(...)

説明

linprog は線形計画法を解きます。

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 = [] と設定してください。

x = linprog(f,A,b,Aeq,beq,lb,ub,x0) は開始点を x0 に設定します。linprog は、active-set アルゴリズムでのみ x0 を使用します。linprog は、interior-point アルゴリズムと simplex アルゴリズムを使用すると x0 を無視します。

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) は、options で指定された最適化オプションを使って最小化します。optimoptions を使用してこれらのオプションを設定してください。

x = linprog(problem) は、problem の最小値を求めます。ここで、problem は「入力引数」に説明されている構造体です。

作業のエクスポート」で説明されているように、最適化アプリケーションから問題をエクスポートして problem 構造体を作成します。

[x,fval] = linprog(...) は、解 x における、目的関数 fun の値を返します。 fval = f'*x.

[x,fval,exitflag] = linprog(...) は、終了条件を記述する値 exitflag を返します。

[x,fval,exitflag,output] = linprog(...) は最適化の情報を含む構造体 output を返します。

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

    メモ:    問題の指定された入力範囲に矛盾がない場合、出力 xx0、出力 fval[] です。

入力引数

関数の引数linprog に渡される引数の一般的な説明を含みます。オプションoptions 値の関数に固有な詳細を説明します。

problem

f

線形目的関数ベクトル f

Aineq

線形不等式制約の行列

bineq

線形不等式制約のベクトル

Aeq

線形等式制約の行列

beq

線形等式制約のベクトル
lb下限のベクトル
ub上限のベクトル

x0

x の初期点、有効制約法アルゴリズムのみ

solver

'linprog'

options

optimoptions で作成されたオプション

出力引数

linprog が返す引数の一般的な説明は 関数の引数 にあります。この節では、exitflaglambdaoutput の各関数に固有な詳細を示します。

exitflag

アルゴリズムが停止した理由を示す整数。以下の表は exitflag の値とそれに対応したアルゴリズムが終了した理由を示します。

1

関数が解 x に収束したことを示します。

0

反復数が options.MaxIter を超えたことを示します。

-2

実行可能な点が見つかりません。

-3

問題が非有界です。

-4

アルゴリズムの実行中に NaN の値があったことを示します。

-5

主問題 および 双対問題とも実行不可能です。

-7

探索方向が小さくなりすぎ、これ以上進むことができないを示します。

lambda

x でのラグランジュ乗数を含む構造体 (制約タイプにより分類) です。構造体のフィールドは、次のとおりです。

lower

下限 lb

upper

上限 ub

ineqlin

線形不等式

eqlin

線形等式

output

最適化に関する情報を含む構造体。構造体のフィールドは、次のとおりです。

iterations

反復回数

algorithm

使用される最適化アルゴリズム

cgiterations

0 (内点法アルゴリズムのみ。下位互換性のために含められます)

message

終了メッセージ

constrviolation

制約関数の最大値

firstorderopt

1 次の最適性の尺度

オプション

linprog により使用される最適化オプションです。いくつかのオプションはすべてのアルゴリズムに使用できますが、内点法アルゴリズムを使用する場合のみに適用されるオプションもあります。options を設定または変更するには optimoptions を使用します。詳細は 最適化オプション リファレンス を参照してください。

すべてのアルゴリズム

すべての linprog アルゴリズムは以下のオプションを使用します。

Algorithm

最適化アルゴリズムを選択します。

  • 'interior-point' (既定の設定)

  • 'active-set'

  • 'simplex'

アルゴリズムの選択についての詳細は、「アルゴリズムの選択」を参照してください。

Diagnostics

最小化または計算する関数に関する情報を表示します。選択肢は 'on' または 'off' (既定の設定) です。

Display

表示レベル。

  • 'off' または 'none' は出力を表示しません。

  • 'iter' は各反復の出力を表示します。'iter' オプションは内点法アルゴリズムとシンプレックス アルゴリズムのみに対応します。

  • 'final' (既定の設定) は、最終出力のみ表示します。

LargeScale

代わりに Algorithm を使用します。

'on' (既定の設定) に設定されている場合は大規模アルゴリズムを使用します。'off' に設定されている場合は中規模アルゴリズムを使用します (simplex アルゴリズムのみSimplex を参照)。アルゴリズムの選択についての詳細は、「アルゴリズムの選択」を参照してください。

MaxIter

可能な反復の最大数 (正の整数)。既定値は以下のとおりです。

  • 内点法アルゴリズムでは 85

  • 10*numberOfVariables はシンプレックス アルゴリズム用

  • 有効制約法アルゴリズムでは 10*max(numberOfVariables, numberOfInequalities + numberOfBounds)

TolFun

関数値に関する終了許容誤差 (正のスカラー)。既定値は以下のとおりです。

  • 内点法アルゴリズムでは 1e-8

  • 1e-6 はシンプレックス アルゴリズム用

  • このオプションは中規模有効制約法アルゴリズムには使用されません

simplex アルゴリズムのみ

simplex アルゴリズムでは以下のオプションを使用します。

Simplex

代わりに Algorithm を使用します。

'on' の場合、LargeScale'off' であれば、linprog はシンプレックス アルゴリズムを使用します。シンプレックス アルゴリズムは組み込みの出発点を使用し、開始点 x0 が与えられた場合は無視します。既定値は 'off'、すなわち linprog は有効制約法アルゴリズムを使用します。詳細と例は 有効制約法アルゴリズムとシンプレックス アルゴリズム を参照してください。

以下を最小にする x を求めます。

f(x) = –5x1 – 4x2 –6x3,

制約条件

x1 – x2 + x3 ≤ 20
3x1 + 2x2 + 4x3 ≤ 42
3x1 + 2x2 ≤ 30
0 ≤ x1, 0 ≤ x2, 0 ≤ x3.

まず、係数を入力します。

f = [-5; -4; -6];
A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20; 42; 30];
lb = zeros(3,1);

次に、線形計画法のルーチンを呼び出してください。

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

解とラグランジュ乗数を検証します。

x,lambda.ineqlin,lambda.lower

x = 
     0.0000
    15.0000
     3.0000

ans =
     0.0000
     1.5000
     0.5000

ans =
     1.0000
     0.0000
     0.0000

lambda のフィールド内のベクトルの中で非ゼロの部分は、解での Active 制約を示します。この場合、(lambda.ineqlin 内の) 2 番目と 3 番目の不等式制約および (lambda.lower 内の) はじめの下限制約は Active になります (すなわち、解は制約範囲上に存在します)。

Diagnostics

Interior-Point アルゴリズム

アルゴリズムの第 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 つを表示した後、双対、主または両方共が実行不可能である場合、そのいずれかを示す次の 6 つのメッセージの中の 1 つが表示されます。計測される問題が実行不可能であるか非有界であるかに応じて、メッセージは異なります。

The dual appears to be infeasible (and the primal unbounded).(The 
primal residual < TolFun.)
The primal appears to be infeasible (and the dual unbounded). (The 
dual residual < TolFun.)
The dual appears to be infeasible (and the primal unbounded) since 
the dual residual > sqrt(TolFun).(The primal residual < 
10*TolFun.)
The primal appears to be infeasible (and the dual unbounded) since 
the primal residual > sqrt(TolFun).(The dual residual < 
10*TolFun.)
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.

たとえば、主 (目的) 関数が非有界になるか、また主残差 (これは主制約の満足度の尺度) が小さくなる可能性があることに注意してください。

有効制約法アルゴリズムとシンプレックス アルゴリズム

linprog は問題が実行不可能な場合に警告を表示します。

Warning: The constraints are overly stringent;
there is no feasible solution.

この場合、linprog は最悪のケースの制約違反を最小化する結果を出力します。

等式制約に矛盾する場合 linprog は次のように出力します。

Warning: The equality constraints are overly
stringent; there is no feasible solution.

の解が非有界の場合は、以下の警告が表示されます。

Warning: The solution is unbounded and at infinity;
the constraints are not restrictive enough.

この場合、linprog は制約を満たす x の値を返します。

制限

有効制約法

この場合、optionsDisplay オプションで使用される表示レベルは 'off' および 'final' のみであり、'iter' を使用する反復出力は使用不可能です。

Interior-Point アルゴリズム

収束と必要条件

大規模問題に対して

A と Aeq はスパース行列です。

詳細

すべて展開する

アルゴリズム

Interior-Point アルゴリズム

内点法は LIPSOL (Linear Interior Point Solver、[3]) をベースにしています。この方法は Mehrotra 予測子修正子アルゴリズム ([2]) と主双対内点法のバリエーションです。アルゴリズムの中で、反復が始まる前に、数手順の前処理が行われます。内点線形計画法を参照してください。

有効制約法アルゴリズムとシンプレックス アルゴリズム

linprogquadprog アルゴリズムで使用するものと同じ射影法を使用します。linprog は有効制約法であり、線形計画法[1] として有名なシンプレックス法を変更したものです。最初に別の線形計画法を解くことで、初期の実行可能解を求めます。

または以下のように入力して、linprog シンプレックス アルゴリズム で説明されているシンプレックス アルゴリズムを使用できます。

options = optimoptions('linprog','Algorithm','simplex')

この optionslinprog の入力引数として渡します。シンプレックス アルゴリズムは、頂点での最適解を返します。

    メモ:   interior-point アルゴリズムと simplex アルゴリズムでは、linprogx0 を無視して独自の初期点を計算します。linprogactive-set アルゴリズムでのみ x0 を使用します。

参考文献

[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, pp. 183–195, 1955.

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

[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.

この情報は役に立ちましたか?