Main Content

混合整数線形計画法の基礎: ソルバーベース

ライブ スクリプトを開く

この例では、混合整数線形問題を解く方法を説明します。この例は複雑ではありませんが、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 つしか利用できません。

IngotWeightinTons%Carbon%MolybdenumCostTon1553$3502343$3303454$3104634$280

3 つのグレードの合金および 1 つのグレードの鋼鉄くずを購入できます。合金と鋼鉄くずは分割して購入できます。

Alloy%Carbon%MolybdenumCostTon186$500277$450368$400Scrap39$100

問題を定式化するには、まず制御変数を決定します。変数 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.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
3 rows, 8 cols, 24 nonzeros
3 rows, 8 cols, 18 nonzeros

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 = [] を設定し、整数制約なしで問題を解く効果を確認します。インゴットの断片を購入できないため、解は異なるものになり、現実的ではありません。

関連するトピック