はじめに

皆様は「最適化」という言葉に、どのようなイメージをお持ちでしょうか。
文字通り、「一番いいもの」を導き出すもの　なのですが、一番いいもの　とは、どのようなものを指すのでしょうか？

• 一般的なケースにおいては、最もコストがかからず、かつ、利益が最大になるもの　です。
• 人員計画においては、コストがかからず、かつ、従業員の不公平がなく、かつ、従業員のわがままをできるだけ聞いてくれるもの　です。
• 物流では需要に対して切らすことなく製品を提供できる、最小の在庫配置をするもの　です。
• 年間の試合日程では、選手の負担を軽くしつつ、最も集客が望めそうな試合パターン　です。

・・・

と、一番いいもの　を見つけ出すには、結局、何かと何かのバランスを見つけ出さなければならないのです。で、そのバランスの中で一番いいところが、最適化　ということになります。

IBMが提供する最適化は、ILOG CPLEX, CP という、世界最高速レベルの最適化エンジン、OPL(Optimization Programming Language) Studio という最適化モデルを記述するための開発環境、ODM (Optimization Decision Manager)という、最適化モデルを含んだアプリケーションを作成する環境　を提供しています。

また、最適化エンジンを使用した事例は非常に多岐にわたっており、本文をお読みの皆様も知らない間に利用されているかと思います。下記は発表されている一例です。

サッカーの対戦予定作成の例　(@IT 様ページ)

上に戻る

最適化ソリューションの手法

ではどのようにして一番いいものを見つけ出すのでしょうか。

一般に最適化ソリューションは、下記のような手順で行います。

1. 現状の分析
   何をゴールとするのか、どのような条件があるのか　を整理します。文書化されているもののみならず、お客様の頭の中にある経験則なども洗い出します。ゴールがある値の最小化なのか、最大化なのか、平準化なのか　によっても、その後のアプローチが変わってきます。
2. モデルの作成
   現実問題を整理し、不等式などの数式で表現していきます。　モデル化をしていく上で、OR (Operations Research)の知識を必要とするケースが多いです。
3. プログラミング
   モデルを、最適化エンジンが理解できるよう、プログラミングを行います。IBM ILOG製品だと、OPL Studio というものがあります。
4. データの準備
   問題を解くために必要なデータを準備します。データベースに用意するケースが多いですが、平易な構造であればファイルから読み込むことも可能です。
5. 最適化エンジンの実行
   モデルにデータをぶつけて、答えを探します。　矛盾する制約などを記述している場合は答えがないケースもあります。
6. 可視化
   出てくるものは計算結果（数値）　ですので、それを人間が見てわかるように、可視化してあげます。これにはILOG JViews と組み合わせてアプリケーションとするケースがほとんどです。
7. What-If 分析
   値を変えてみて、この場合だったらどうだろう、といろいろなパターンで確認していきます。業務ユーザ側がいろいろ分析しながら利用し、現状よりもより良いケースを探していきます。

ここでは、簡単な線形計画法に基づく例を見てみましょう。

上に戻る

鯛焼きと今川焼の販売

あるお店で、鯛焼きと今川焼を販売したいと思っています。
鯛焼きと今川焼では、あんこの量、生地の量、がちょっと違うのです。

鯛焼き　生地の量 20g　あんこ 40g
今川焼　生地の量 40g　あんこ 30g

今日の仕入れは、あんこ4000g、生地3800g です。

これを、鯛焼き　1匹120円、今川焼 1つ100円　が定価としています。
今日はいったいそれぞれいくつ作ると、売上が良くなるでしょうか。

パッと見、小学生が解く「つるかめ算」のようです。

それでは、それぞれを式にしてみましょう。
鯛焼きの数を x、今川焼の数を y とします。

売上金額（これを目的関数　と言います）は、x*120 + y*100 と表現できます。
制約条件は、
x*20 + y*40 <= 3800 （生地の制約）
x*40 + y*30 <= 4000 （あんこの制約）
x > 0, y > 0
と表現できます。

この連立不等式を解いて、x, y が最大になるところを探せばよいのです。
グラフにしてみるとこんな感じです。

答えは、緑の線（あんこの割合線）と青の線（生地の割合線）が交わるところになります。
つまり、あんこと生地の両方を使いきるところになります。
それは、鯛焼き＝46個、今川焼＝72個　というところです。
これが全部売れるとすると、12,720円の売り上げになります。

生地は、実は小麦粉と卵と牛乳、砂糖等で作られています。
ではその原材料の配分の最適なところはどこでしょう？　コストを考え、「儲け」を最大化するところはどこでしょう？
それぞれの焼き上がりにかかる時間、メンテナンスの時間、職人の勤務時間を考えるとどうなるでしょう？
さらに、全国180店舗においての、季節変動などの売上予測からのその日の仕入れをどのようにすればよいでしょうか？

こうなってくると、もう人手による計算では無理なことは明白です。
ではJavaで計算させるプログラムを書きましょうか？

“数理計画法 Java”　で検索すると、たくさんのサンプルソースコードが見ることができます。
ご覧になっていただければわかりますが、数次元の配列とfor 文だらけです。
これらをまねて書くだけでも、結構大変です。
しかも、シンプレックス法、射影変換法など、いろいろなアルゴリズムがあり、どれで実装するのがよいのか？
正直、ウンザリするくらいのソースコードを書かなければなりません。
パラメータの数が膨大になると、for 文の嵐で整理できなくなり、仮に書いて実行しても実行に非常に時間がかかってしまいます。

そこで、最適化エンジン　というものが出てきます。
IBM ILOG OPL Studio を使って、このモデルを書いてみましょう。

上に戻る

OPLを使っての最適化ソリューションの作成

OPL Studio を立ち上げ、OPLプロジェクトを作成します。

プロジェクト名と場所を決めます。
今回はTaiyaki-Imagawayaki というプロジェクト名、場所はC:\WorkSpace\OPL としています。

オプション項目の、「デフォルトの実行構成の追加」と「モデルの作成」というところにチェックを入れておきます。

このような画面が出てきます。

Taiyaki-Imagawayaki.mod ファイルに、モデルを記述していきます。
モデルは先出のものです。

/*********************************************
 * OPL 6.3 Model
 * Author: Masahiko UMENO
 * Creation Date: 2010/03/16 at 14:29:04
 *********************************************/
dvar int+ x;
dvar int+ y;

maximize x*120+y*100;
subject to{
x*20+y*40<=3800;
x*40+y*30<=4000;
};
    

見慣れない変数宣言「dvar」がありますが、これはOPL特有の「決定変数」というものです。
それを、 int+ という、正の整数であることを宣言する、これまたOPL特有のタイプで定義しています。

Maximize という宣言で、最大化したい式を定義します。この場合は売上高（目的関数）になります。
Subject to { } 内に、関係式を記述します。
ここで、「不等式をそのまま！」　書いていることに注目してください。

そうなんです。OPLを使用した記述は、for 文など要らないのです。
現実世界の問題を数式に表わしたら、そのまま計算させることが可能なのです。
しかも、たったこれだけのコーディングです。面倒なところは全部、エンジンがやってくれます。

では実行させてみましょう。
モデルを保存したら、構成1 を右クリックして、「これを実行」　してみましょう。

おおおお。答えが瞬時に出てきました。

上に戻る

まとめ

いかがでしょうか。
今回はいちばん簡単なモデルでの説明でしたが、OPLの特徴は、モデルが簡単に記述できる　ということです。
また、線形計画法を解くエンジン、CPLEX で実行させてみました。
次回以降は、制約プログラミング（CP）の例や、より複雑なモデルでの実際の使用例をご紹介していきたいと思います。

著者について

この記事を評価する

コメント

上に戻る

目次

• はじめに
• 最適化ソリューションの手法
• 鯛焼きと今川焼の販売
• OPLを使っての最適化ソリューションの作成
• まとめ
• 著者について
• コメント