最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。
この例では、混合整数線形計画法を解く方法を説明します。この例は複雑ではありませんが、intlinprog
の構文で問題を定式化する一般的な手順を説明します。
この問題への問題ベースのアプローチについては、混合整数線形計画法の基礎: 問題ベースを参照してください。
さまざまな化学組成の鋼鉄を融合して、特定の化学組成の 25 トンの鋼鉄を精製するものとします。精製された製品には、重量で炭素 5% とモリブデン 5% (つまり、炭素が 25 トン*5% = 1.25 トン、モリブデンが 1.25 トン) が含まれている必要があります。目的は鋼鉄の融合コストを最小化することです。
この問題は、Carl-Henrik Westerberg、Bengt Bjorklund および Eskil Hultman "An Application of Mixed Integer Programming in a Swedish Steel Mill" Interfaces February 1977 Vol. 7, No. 2 pp. 39–43 から引用されたものです。これらの抜粋は http://interfaces.journal.informs.org/content/7/2/39.abstract
で参照できます。
このために 4 つの鋼鉄のインゴットを購入できます。各インゴットの 1 つしか利用できません。
インゴット | 重量 (トン) | 炭素比率 (%) | モリブデン比率 (%) | トンあたりコスト |
---|---|---|---|---|
1 | 5 | 5 | 3 | $350 |
2 | 3 | 4 | 3 | $330 |
3 | 4 | 5 | 4 | $310 |
4 | 6 | 3 | 4 | $280 |
3 つのグレードの合金を購入できますが、その 1 つは鋼鉄くずのグレードです。合金と鋼鉄くずは分割して購入できます。
合金 | 炭素比率 (%) | モリブデン比率 (%) | トンあたりコスト |
---|---|---|---|
1 | 8 | 6 | $500 |
2 | 7 | 7 | $450 |
3 | 6 | 8 | $400 |
鋼鉄くず | 3 | 9 | $100 |
問題を定式化するには、まず制御変数を決定します。変数 x(1) = 1
を取るとインゴット 1 の購入を意味し、x(1) = 0
を取るとインゴットを購入しないことを意味します。同様に、変数 x(2)
~ x(4)
は、インゴット 2 ~ 4 の購入を示す 2 値変数です。
変数 x(5)
~ x(7)
は購入する合金 1、2、および 3 の量をトン単位で示し、x(8)
は購入する鋼鉄くずの量を示します。
intlinprog
の入力を指定することにより問題を定式化します。該当する intlinprog
構文は次のとおりです。
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
intlinprog
の入力を、最初 (f
) から最後 (ub
) まで作成します。
f
はコスト係数のベクトルです。インゴットのコストを表す係数はインゴットの重量 x トン当たりコストです。
f = [350*5,330*3,310*4,280*6,500,450,400,100];
整数値は最初の 4 つです。
intcon = 1:4;
2 値変数を指定するには、intcon
の変数が整数となるように設定し、下限に 0
、上限に 1
を指定します。
線形不等式制約はないので、A
と b
は空の行列 ([]
) になります。
3 つの等式制約があります。最初の制約は総重量が 25 トンであることです。
5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) + x(6) + x(7) + x(8) = 25
2 番目の制約は炭素の重量が 25 トンの 5% (1.25 トン) であることです。
5*0.05*x(1) + 3*0.04*x(2) + 4*0.05*x(3) + 6*0.03*x(4)
+ 0.08*x(5) + 0.07*x(6) + 0.06*x(7) + 0.03*x(8) = 1.25
3 番目の制約はモリブデンの重量が 1.25 トンであることです。
5*0.03*x(1) + 3*0.03*x(2) + 4*0.04*x(3) + 6*0.04*x(4)
+ 0.06*x(5) + 0.07*x(6) + 0.08*x(7) + 0.09*x(8) = 1.25
行列形式は Aeq*x = beq
です。ここで、
Aeq = [5,3,4,6,1,1,1,1; 5*0.05,3*0.04,4*0.05,6*0.03,0.08,0.07,0.06,0.03; 5*0.03,3*0.03,4*0.04,6*0.04,0.06,0.07,0.08,0.09]; beq = [25;1.25;1.25];
各変数は 0 以下に制限されます。整数変数は 1 以上に制限されます。
lb = zeros(8,1); ub = ones(8,1); ub(5:end) = Inf; % No upper bound on noninteger variables
すべての入力を指定したら、ソルバーを呼び出します。
[x,fval] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
解を表示します。
x,fval
x = 1.0000 1.0000 0 1.0000 7.2500 0 0.2500 3.5000 fval = 8.4950e+03
最適購入コストは $8,495 です。インゴット 1、2、4 を購入し、3 を購入しません。合金 1 を 7.25 トン、合金 3 を 0.25 トン、鋼鉄くずを 3.5 トン購入します。
intcon = []
を設定し、整数制約なしで問題を解く効果を確認します。インゴットの断片を購入できないため、解は異なるものになり、妥当ではありません。