最適化問題として定式化するために、次の3つのことを考えていきます
- 始めに決定変数を定義します。最適化のゴールはこれら変数の値を決定することです。
- 次に最適化の目的関数を定義します。これは最適化によって何を実現したいかを示す関数です。この関数を最小化または最大化することが目的となります。
- 最後に守るべき制約を定義します。
Gurobi Optimizerは、与えられた線形制約を満たす決定変数への値の割り当てをすべて検討し、その中で定義された目的関数を最適化するものを返します。
今回の問題の変数は非常に単純です。最適化の中ではそれぞれのコインを何枚作るかを決定する必要があります。このとき、決定変数にわかりやすい名前を付けると便利です。ここではそれぞれの変数をPennies, Nickels, Dimes, Quarters, Dollarsと呼ぶこととします。さらに、各種の鉱物が利用される量を表す変数を導入します。これらはCu, Ni, Zi, Mnと呼ぶことにします。
今回の最適化問題の目的は生産された硬貨の価値(ドル)の合計を最大化することでした。生産される1ペニーは0.01ドル、1ニッケルは0.05ドルなどの価値があります。これを使って、次のような線形目的関数が得られます：
maximize: 0.01 Pennies + 0.05 Nickels + 0.1 Dimes + 0.25 Quarters
+ 1 Dollars
今回の最適化モデルの制約は、各硬貨を1つ生産するためには鉱物がそれぞれ一定量消費され、かつ鉱物の供給量には限りがあるという事実から導かれます。この関係を2つの要素に分けて考えます。まず、それぞれの鉱物について、消費される鉱物の量を表す式を作ります。例えば銅の場合、その式は次のようになります：
Cu = 0.06 Pennies + 3.8 Nickels + 2.1 Dimes + 5.2 Quarters
+ 7.2 Dollars
この式の係数は、先ほどの硬貨の規格表から得たもので、1ペニーは0.06gの銅を使い、1ニッケルは3.8gを使う、といったことを意味しています。
最適化モデルでは、各鉱物の利用可能量も表現しなければなりません。仮に1000gの銅が入手可能であれば、制約条件は次のようになります：
Cu <= 1000
今回の例では、1000gの銅と50gの他の鉱物があると仮定します。
最適化モデルが問題の物理的な事象を正確に反映するためには、実はもう1つの制約が必要です。例えば10セント硬貨1枚は10セントの価値がありますが、半分だけしかない10セント硬貨は5セントの価値もありません。すなわちそれぞれのコインの生産枚数を表す変数は整数である必要があります。
コメント
0件のコメント
記事コメントは受け付けていません。