Nuorium Optimizer C++SIMPLE例題集 V26

2.1 配合問題

　配合問題の例として，ここでは特定の組成を持つ合金を生成する問題を扱います．この他にも薬剤の調合や必要な栄養素を含む献立を考えるダイエット問題など配合問題として扱えるものは多岐にわたります．

　この問題をNuorium Optimizerで解くために定式化を行います．本例題は文献[1]からの引用です．

　まず，変数として市販の合金1,2,3,...,9の混合比率，つまり混ぜ合わせる割合を，それぞれとしましょう．

　次に，最小化するべき目的関数は，各市販の合金について「単位量当たりのコスト」と「混合比率」の積の総和として表現することができます．

　最後に制約条件です．まず，混合比率は負の値をとれませんので，各変数に対して非負制約が必要です．混合比率の総和は1ですので，その制約も加えます．また，生成する合金の組成についての制約は，鉛，亜鉛，スズに対して，各市販の合金についての「構成比率」と「混合比率」の積の総和が，それぞれ30%，30%，40%と等しい，という形になります．

　以上のことから，次のように定式化することができます．

　この問題は，目的関数，制約式全て線形なので，線形計画問題となります．

　定式化した結果をC++SIMPLEで記述すると以下のようになります．

// 変数
Variable x1(name = "市販の合金1の混合比率");
Variable x2(name = "市販の合金2の混合比率");
Variable x3(name = "市販の合金3の混合比率");
Variable x4(name = "市販の合金4の混合比率");
Variable x5(name = "市販の合金5の混合比率");
Variable x6(name = "市販の合金6の混合比率");
Variable x7(name = "市販の合金7の混合比率");
Variable x8(name = "市販の合金8の混合比率");
Variable x9(name = "市販の合金9の混合比率");

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = 7.3 * x1 + 6.9 * x2 + 7.3 * x3 + 7.5 * x4 + 7.6 * x5 + 6.0 * x6 + 5.8 * x7 + 4.3 * x8 + 4.1 * x9;

// 非負制約
x1 >= 0;
x2 >= 0;
x3 >= 0;
x4 >= 0;
x5 >= 0;
x6 >= 0;
x7 >= 0;
x8 >= 0;
x9 >= 0;

// 混合比率の制約
x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 == 1;
0.2 *x1 + 0.5 * x2 + 0.3 * x3 + 0.3 * x4 + 0.3 * x5 + 0.6 * x6 + 0.4 * x7 + 0.1 * x8 + 0.1 * x9 == 0.3;
0.3 *x1 + 0.4 * x2 + 0.2 * x3 + 0.4 * x4 + 0.3 * x5 + 0.3 * x6 + 0.5 * x7 + 0.3 * x8 + 0.1 * x9 == 0.3;
0.5 *x1 + 0.1 * x2 + 0.5 * x3 + 0.3 * x4 + 0.4 * x5 + 0.1 * x6 + 0.1 * x7 + 0.6 * x8 + 0.8 * x9 == 0.4;

// 求解
solve();

// 出力
z.val.print();

　より汎用的に問題を定式化すると以下のようになります．

　次に，定数（構成比率，コスト，目標比率）をデータファイルから与えるC++SIMPLEモデルを示します．このようにモデルとデータを分離することにより，市販の合金の数や構成金属の種類の数が変わったとしてもデータファイルを変更するだけで対応できるようになります．

// 集合と添字
Set Alloy(name = "市販の合金集合");
Element i(set = Alloy);
Set Blend(name = "構成金属集合");
Element j(set = Blend);

// パラメータ
Parameter r(name = "構成比率", index = (i, j));
Parameter c(name = "コスト", index = i);
Parameter b(name = "目標比率", index = j);

// 変数
Variable x(name = "混合比率", index = i);

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = sum(c[i] * x[i], i);

// 非負制約
x[i] >= 0;

// 混合比の制約
sum(x[i], i) == 1;
sum(r[i, j] * x[i], i) == b[j];

// 求解
solve();

// 出力
z.val.print();
x.val.print();

　データファイル（.dat形式）は以下のようになります．

構成比率 =
[1, Lead] 0.2 [1, Zinc] 0.3 [1, Tin] 0.5
[2, Lead] 0.5 [2, Zinc] 0.4 [2, Tin] 0.1
[3, Lead] 0.3 [3, Zinc] 0.2 [3, Tin] 0.5
[4, Lead] 0.3 [4, Zinc] 0.4 [4, Tin] 0.3
[5, Lead] 0.3 [5, Zinc] 0.3 [5, Tin] 0.4
[6, Lead] 0.6 [6, Zinc] 0.3 [6, Tin] 0.1
[7, Lead] 0.4 [7, Zinc] 0.5 [7, Tin] 0.1
[8, Lead] 0.1 [8, Zinc] 0.3 [8, Tin] 0.6
[9, Lead] 0.1 [9, Zinc] 0.1 [9, Tin] 0.8
;

コスト =
[1] 7.3
[2] 6.9
[3] 7.3
[4] 7.5
[5] 7.6
[6] 6.0
[7] 5.8
[8] 4.3
[9] 4.1
;

目標比率 =
[Lead] 0.3
[Zinc] 0.3
[ Tin] 0.4
;

　このモデルを実行すると，市販の合金6を40%，市販の合金8を60%混ぜ合わせるのが最適で，そのときの総コストは4.98であることがわかります．

---

 

 

上に戻る