最適化セミナーのご案内

2.1 配合問題

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

例題

　鉛，亜鉛，スズの構成比率が，それぞれ30%，30%，40%となるような合金を，市販の合金を混ぜ合わせ，できるだけ安いコストで生成することを考えます．現在手に入れることができる市販の合金は9種類で，それらの構成比率と単位量あたりのコストは以下の通りです．

市販の合金 1 2 3 4 5 6 7 8 9
鉛（%） 20 50 30 30 30 60 40 10 10
亜鉛（%） 30 40 20 40 30 30 50 30 10
スズ（%） 50 10 50 30 40 10 10 60 80
コスト（$/lb） 7.3 6.9 7.3 7.5 7.6 6.0 5.8 4.3 4.1

　

　所望の組成を持つ合金をコストを一番安く生成するには，市販の合金をどのように混ぜ合わせれば良いでしょうか．

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

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

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

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

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

変数
$x_1$ 市販の合金1の混合比率
$x_2$ 市販の合金2の混合比率
$x_3$ 市販の合金3の混合比率
$x_4$ 市販の合金4の混合比率
$x_5$ 市販の合金5の混合比率
$x_6$ 市販の合金6の混合比率
${x_7}$ 市販の合金7の混合比率
${x_8}$ 市販の合金8の混合比率
${x_9}$ 市販の合金9の混合比率
　
目的関数（最小化）
$7.3x_1 + 6.9x_2 + 7.3x_3 + 7.5x_4 + 7.6x_5 + 6.0x_6 + 5.8x_7 + 4.3x_8 + 4.1x_9$ 総コスト
　
非負制約
$x_1 \ge 0$ 　
$x_2 \ge 0$ 　
$x_3 \ge 0$ 　
$x_4 \ge 0$ 　
$x_5 \ge 0$ 　
$x_6 \ge 0$ 　
$x_7 \ge 0$ 　
$x_8 \ge 0$ 　
$x_9 \ge 0$ 　
　
混合比率の制約
$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 1$ 　
$0.2x_1 + 0.5x_2 + 0.3x_3 + 0.3x_4 + 0.3x_5 + 0.6x_6 + 0.4x_7 + 0.1x_8 + 0.1x_9 = 0.3$ 　
$0.3x_1 + 0.4x_2 + 0.2x_3 + 0.4x_4 + 0.3x_5 + 0.3x_6 + 0.5x_7 + 0.3x_8 + 0.1x_9 = 0.3$ 　
$0.5x_1 + 0.1x_2 + 0.5x_3 + 0.3x_4 + 0.4x_5 + 0.1x_6 + 0.1x_7 + 0.6x_8 + 0.8x_9 = 0.4$ 　

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

　定式化した結果を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();

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

集合
$Alloy = \{ 1,2,3,4,5,6,7,8,9\}$ 市販の合金の種類の集合
$Blend = \{ Lead,Zinc,Tin\}$ 構成金属の集合
　
定数
$r_{ij}, i \in Alloy, j \in Blend$ 市販の合金$i$における構成金属$j$の比率
$c_i, i \in Alloy$ 市販の合金$i$の単位量あたりのコスト
$b_j, j \in Blend$ 構成金属$j$の目標比率
　
変数
$x_i, i \in Alloy$ 市販の合金$i$の混合比率
　
目的関数（最小化）
$\displaystyle \sum_{i \in Alloy} c_i x_i$ 総コスト
　
制約
$x_i \ge 0, \forall i \in Alloy$ 非負制約
$\displaystyle \sum_{i \in Alloy} x_i = 1$ 比率の総和が1という制約
$\displaystyle \sum_{i \in Alloy} r_{ij} x_i = b_j, \forall j \in Blend$ 混合比の制約

　次に，定数（構成比率，コスト，目標比率）をデータファイルから与える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であることがわかります．

2. 例題の紹介
2.2 輸送問題

 

 

上に戻る