混合整数線形計画法の基礎: ソルバーベース
この例では、混合整数線形問題を解く方法を説明します。この例は複雑ではありませんが、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 から引用されたものです。これらの要旨は https://doi.org/10.1287/inte.7.2.39 で参照できます。
このために 4 つの鋼鉄のインゴットを購入できます。各インゴットの 1 つしか利用できません。
3 つのグレードの合金および 1 つのグレードの鋼鉄くずを購入できます。合金と鋼鉄くずは分割して購入できます。
問題を定式化するには、まず制御変数を決定します。変数 x(1) = 1 を取るとインゴット "1" の購入を意味し、x(1) = 0 を取るとインゴットを購入しないことを意味します。同様に、変数 x(2) ～ x(4) は、インゴット 2 ～ 4 を購入するかどうかを示す 2 値変数です。
変数 x(5) ～ x(7) は購入する合金 1、2、および 3 の量をトン単位で示し、x(8) は購入する鋼鉄くずの量を示します。
MATLAB® での定式化
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 は空の行列 ([]) になります。
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,A,b,Aeq,beq,lb,ub);
Running HiGHS 1.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [3e-02, 6e+00]
Cost [1e+02, 2e+03]
Bound [1e+00, 1e+00]
RHS [1e+00, 2e+01]
Presolving model
3 rows, 8 cols, 24 nonzeros 0s
3 rows, 8 cols, 18 nonzeros 0s
Solving MIP model with:
3 rows
8 cols (4 binary, 0 integer, 0 implied int., 4 continuous)
18 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
0 0 0 0.00% 8125.6 inf inf 0 0 0 4 0.0s
R 0 0 0 0.00% 8495 8495 0.00% 5 0 0 5 0.0s
Solving report
Status Optimal
Primal bound 8495
Dual bound 8495
Gap 0% (tolerance: 0.01%)
Solution status feasible
8495 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 5 (total)
0 (strong br.)
1 (separation)
0 (heuristics)
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
解を表示します。
x,fval
x = 8×1
1.0000
1.0000
0
1.0000
7.2500
0
0.2500
3.5000
fval = 8495
最適購入コストは $8,495 です。インゴット 1、2、4 を購入し、3 を購入しません。合金 1 を 7.25 トン、合金 3 を 0.25 トン、鋼鉄くずを 3.5 トン購入します。
intcon = [] を設定し、整数制約なしで問題を解く効果を確認します。インゴットの断片を購入できないため、解は異なるものになり、現実的ではありません。
