第3章 アニーリングマシンと2次式と離散値の関係
第1節 1次式になる問題、線形計画問題
線形計画問題とは、1次関数で表すことができる問題です。最適化問題の中でも、比較的容易に解くことができるといわれており、イジングモデルに表すことはできますが、アニーリングマシンで解いてもあまりメリットがありません。どのような問題かを感じて頂くため、例として次のような状況を考えましょう。ミックスジュース店で最も利益を最大化するにはどうしたらいいでしょうか。この店のメニューはイチゴスペシャル、マンゴースペシャル、バナナスペシャルの3つです。
イチゴスペシャルにはイチゴ100gとマンゴー40gが使われています。マンゴースペシャルにはマンゴー80gとバナナ30gが使われています。バナナスペシャルにはバナナ110gとイチゴ50gが使われています。ある日仕入れた材料はイチゴ1000g、マンゴー500g、バナナ1500gでした。イチゴスペシャル、マンゴースペシャル、バナナスペシャルの販売価格はそれぞれ700円、900円、500円です。最も売り上げ高が高くなるようにするためには、それぞれを何個売ればよいでしょうか。
表 ミックスジュースのメニューとそれぞれに用いる材料
| メニュー／材料 | イチゴ1000g | マンゴー500g | バナナ1500g | 単価 |
|---|---|---|---|---|
| イチゴスペシャル | イチゴ100g | マンゴー40g | - | 700円 |
| マンゴースペシャル | - | マンゴー80g | バナナ30g | 900円 |
| バナナスペシャル | イチゴ50g | - | バナナ110g | 500円 |
この場合イチゴスペシャル、マンゴースペシャル、バナナスペシャルの販売数を$x, y, z$とすると売上高は以下の式で表されます。
となり、これらを満たす$x,y,z$の組合せを求めるという最適化問題です。
コスト関数(1)を1次式といいます。変数を何個かけているかで決まり、$700x$の項も1次、$900y$の項も1次、$500z$の項も1次です。もしこのどれか1つでも$x^2$や$xy$を持っていたら、2次式であるということになります。
このミックスジュース問題は、自力で解く場合は制約式を3次元グラフに表して交点を求めることで解きます。計算機上では、効率的に問題を解くソルバーという仕組みが提供されています。このようなソルバーは表計算ソフトのアドインで提供されているものもあり、すぐに使うことができます。したがって、このような1次式の最適化問題はアニーリングマシンでこそ本領を発揮する問題とは言えないということです。この問題の答えは、イチゴスペシャル4個、マンゴースペシャルが4個、バナナスペシャルが12個となります。
