最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。
linprog
線形計画問題を解く
線形計画法ソルバー
以下で指定された問題の最小値を見つけます。
f、x、b、beq、lb、ub はベクトル、A と Aeq は行列です。
メモ
linprog は、ソルバーベースのアプローチのみに適用されます。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。
構文
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(___)説明
例
線形計画法、線形不等式制約
線形不等式で定義された単純な線形計画法を解きます。
この例では、次の線形不等式制約を使用します。
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
b = [2 1 2 1 -1 2];目的関数 
を使用します。
f = [-1 -1/3];
線形計画法を解きます。
x = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
線形不等式および線形等式を含む線形計画法
線形不等式および線形等式で定義される単純な線形計画法を解きます。
この例では、次の線形不等式制約を使用します。
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
b = [2 1 2 1 -1 2];線形等式制約 
を使用します。
Aeq = [1 1/4]; beq = 1/2;
目的関数 
を使用します。
f = [-1 -1/3];
線形計画法を解きます。
x = linprog(f,A,b,Aeq,beq)
Optimal solution found.
x = 2×1
0
2
すべての制約タイプを含む線形計画法
線形不等式、線形等式、および範囲を含む単純な線形計画法を解きます。
この例では、次の線形不等式制約を使用します。
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
b = [2 1 2 1 -1 2];線形等式制約 
を使用します。
Aeq = [1 1/4]; beq = 1/2;
次の範囲を設定します。
lb = [-1,-0.5]; ub = [1.5,1.25];
目的関数 
を使用します。
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' アルゴリズムを使用して線形計画法を解きます。
この例では、次の線形不等式制約を使用します。
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
b = [2 1 2 1 -1 2];線形等式制約 
を使用します。
Aeq = [1 1/4]; beq = 1/2;
次の範囲を設定します。
lb = [-1,-0.5]; ub = [1.5,1.25];
目的関数 
を使用します。
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
linprog の場合に問題ベースのアプローチを使用して LP を解く
この例では、問題ベースのアプローチを使用して問題を設定し、次にソルバーベースのアプローチを使用してその問題を解く方法を示します。問題は、次のとおりです。
この問題を表す、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
constrviolation: 0
message: 'Optimal solution found.'
algorithm: 'dual-simplex'
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 に対応します。詳細は、アルゴリズムを参照してください。
目的関数値を返す
単純な線形計画法の解および目的関数値を計算します。
非線形制約は次のとおりです。
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
b = [2 1 2 1 -1 2];目的関数は 
です。
f = [-1 -1/3];
問題を解き、目的関数値を返します。
[x,fval] = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
fval = -1.1111
より多くの出力を取得することによる解法プロセスの検証
終了フラグおよび出力構造体を取得することによって、解法プロセスと解の質をよりよく把握できます。
この例では、次の線形不等式制約を使用します。
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
b = [2 1 2 1 -1 2];線形等式制約 
を使用します。
Aeq = [1 1/4]; beq = 1/2;
次の範囲を設定します。
lb = [-1,-0.5]; ub = [1.5,1.25];
目的関数 
を使用します。
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 = [-5; -4; -6];
次の線形不等式制約を使用します。
A = [1 -1 1
3 2 4
3 2 0];
b = [20;42;30];すべての変数が正になるように制約します。
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.0000
3.0000
ans = 3×1
0
1.5000
0.5000
ans = 3×1
1.0000
0
0
lambda.ineqlin は、x の 2 番目および 3 番目の成分について非ゼロです。これは、2 番目および 3 番目の線形不等式制約が次の等式で満たされることを示します。
これが真であることを確認します。
A*x
ans = 3×1
-12.0000
42.0000
30.0000
lambda.lower は、x の 1 番目の成分について非ゼロです。これは、x(1) が下限の 0 になっていることを示します。
入力引数
出力引数
アルゴリズム
参照
[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.
参考
intlinprog | mpsread | optimoptions | prob2struct | quadprog
