ドキュメンテーション

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

混合整数線形計画法の基礎: 問題ベース

この例では、混合整数線形計画法を解く方法を説明します。この例は複雑ではありませんが、問題ベースのアプローチで問題を定式化する一般的な手順を示しています。この例を示すビデオについては、Solve a Mixed-Integer Linear Programming Problem using Optimization Modeling を参照してください。

この問題へのソルバーベースのアプローチについては、混合整数線形計画法の基礎: ソルバーベースを参照してください。

問題の説明

さまざまな化学組成の鋼鉄を融合して、特定の化学組成の 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 つしか利用できません。

インゴット重量 (トン)炭素比率 (%)モリブデン比率 (%)トンあたりコスト
1553$350
2343$330
3454$310
4634$280

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

合金炭素比率 (%)モリブデン比率 (%)トンあたりコスト
186$500
277$450
368$400
鋼鉄くず39$100

問題の定式化

問題を定式化するには、まず制御変数を決定します。変数 ingots(1) = 1 を取るとインゴット 1 の購入を意味し、ingots(1) = 0 を取るとインゴットを購入しないことを意味します。同様に、変数 ingots(2)ingots(4) は、インゴット 24 を購入するかどうかを示す 2 値変数です。

変数 alloys(1)alloys(3) は購入する合金 12、および 3 の量をトン単位で示します。scrap は購入する鋼鉄くずの量をトン単位で示します。

最適化問題と変数を作成します。

steelprob = optimproblem;
ingots = optimvar('ingots',4,'Type','integer','LowerBound',0,'UpperBound',1);
alloys = optimvar('alloys',3,'LowerBound',0);
scrap = optimvar('scrap','LowerBound',0);

変数と関連付けられたコストの式を作成します。

weightIngots = [5,3,4,6];
costIngots = weightIngots.*[350,330,310,280];
costAlloys = [500,450,400];
costScrap = 100;
cost = costIngots*ingots + costAlloys*alloys + costScrap*scrap;

問題に目的関数としてコストを含めます。

steelprob.Objective = cost;

3 つの等式制約があります。最初の制約は総重量が 25 トンであることです。鋼鉄の重量を計算します。

totalWeight = weightIngots*ingots + sum(alloys) + scrap;

2 番目の制約は炭素の重量が 25 トンの 5% (1.25 トン) であることです。鋼鉄内の炭素の重量を計算します。

carbonIngots = [5,4,5,3]/100;
carbonAlloys = [8,7,6]/100;
carbonScrap = 3/100;
totalCarbon = (weightIngots.*carbonIngots)*ingots + carbonAlloys*alloys + carbonScrap*scrap;

3 番目の制約はモリブデンの重量が 1.25 トンであることです。鋼鉄内のモリブデンの重量を計算します。

molybIngots = [3,3,4,4]/100;
molybAlloys = [6,7,8]/100;
molybScrap = 9/100;
totalMolyb = (weightIngots.*molybIngots)*ingots + molybAlloys*alloys + molybScrap*scrap;

制約を問題に含めます。

steelprob.Constraints.conswt = totalWeight == 25;
steelprob.Constraints.conscarb = totalCarbon == 1.25;
steelprob.Constraints.consmolyb = totalMolyb == 1.25;

問題を解く

すべての入力を指定したら、ソルバーを呼び出します。

[sol,fval] = solve(steelprob);
LP:                Optimal objective value is 8125.600000.                                          

Cut Generation:    Applied 3 mir cuts.                                                              
                   Lower bound is 8495.000000.                                                      
                   Relative gap is 0.00%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of
the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables
are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).

解を表示します。

sol.ingots
sol.alloys
sol.scrap
fval
ans =

     1
     1
     0
     1


ans =

    7.2500
         0
    0.2500


ans =

    3.5000


fval =

   8.4950e+03

最適購入コストは $8,495 です。インゴット 124 を購入し、3 を購入しません。合金 1 を 7.25 トン、合金 3 を 0.25 トン、鋼鉄くずを 3.5 トン購入します。

関連するトピック