バックナンバー ( 2012 Vol.5 ) 2012 年 9 月 19 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2012 Vol.5 ( 2012 年 9 月 19 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 数理計画問題の豆知識（第 13 回） ■ <トピック> NUOPT FAQ 更新 ■ <トピック> 出展のご報告 ■ <セミナー> NUOPT セミナーのご案内 ■ <トピック> 書評「応用に役立つ 50 の最適化問題」 藤沢克樹・梅谷俊治著 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 13 回） ****************************************************************** 9 月も後半となり，プロ野球もいよいよ大詰めのシーズンとなってきまし た．ファンの方々にとっては日々の楽しみが増えてきた一方で，同時に贔 屓の球団がクライマックスシリーズに進出できるか気になる頃ではないで しょうか． どの球団が，あと最低何勝すれば必ずクライマックスシリーズに進出でき るのかを示すクライマックスシリーズ進出ナンバー（以下，CS 進出ナン バー）が 8 月 17 日より時事通信社様から配信されています． 実は，この算出の計算エンジンとして弊社の数理計画ソルバー NUOPT が採 用されているのです．一見関係ないように思われる野球と数理計画法，い ったいどのような関係があるのでしょう． 第 13 回となる今回は，スポーツの分野の問題を数理計画の視点からアプ ローチし，解決する試みをスポーツソリューションと題して，CS 進出ナン バーを始めとしたスポーツソリューションについて紹介いたします． 詳しくは以下の「スポーツソリューション」ページも参照ください． http://www.msi.co.jp/nuopt/solution/sports/index.html スポーツに関する種々の問題は純粋な論理的問題としてモデル化され，学 術的にも興味のある研究対象となります．しかし，実務においては様々な 固有の条件が存在し，理論の発展はもとより計算機の進歩を待たなければ ならなかったことで，実用に耐えうるまでの成果が出始めたのは最近のこ とです． スポーツソリューションの分野に属する問題として，スポーツスケジュー リングや入賞問題などが挙げられます．前者は，選手や試合日程の順番や 組み合わせを決定する問題です．具体的には，費用の最小化，収益の最大 化だけでなく，様々な観点から「公平」なスケジュールを決定する問題も 含まれ，純粋なモデルでも様々な未解決問題が存在します．後者は「あと どのくらいで勝ち進むことができるのか」，といった数を決定する問題で， CS 進出ナンバーの計算はこの入賞問題に属します． 入賞問題の難点は大きく分けて二点あります．今回の CS 進出ナンバーを 例にとって考えてみます． 一つ目は「引き分け」が存在することです．日本プロ野球ではまず，交流 戦を含めた最終勝率で順位が判断されます．勝率は「勝ち数/（勝ち数+負 け数）」で計算されるので，普通に定式化すると問題が非線形になります． しかも勝ち数は整数なので整数変数を含む非線形問題になってしまいます． また，引き分けの存在による試合結果のパターンの増加も大きな問題です． もう一つは「同着」の存在です．最終勝率が同一になってしまう，という 稀ながら起こり得る事象への対応です．順位をつける必要がある以上，同 着の場合は何か他の基準が必要になってきますが，プロ野球においても（ ややこしいことにセ・リーグ，パ・リーグ違うのですが）これらの基準は きちんと定められています． したがって，モデルを作成する際には同率が出現するケースを正確に表現 することが必要です．クライマックスシリーズに進出するためには 3 位以 上になる必要があるので同率で 3 位が存在するときに判定が面倒になりま す．同率で 3 位が存在したときまで考慮しながら，残り試合の全パターン の結果をシミュレートすることが大変であることは想像に難くないでしょ う． 具体的には「4 位以下にならねばならない」という制約を持つ数理計画問 題を構成し，「この問題に実行可能解が存在しないならば 3 位以内しかあ りえない」というところから出発します．つづいて「同率 3 位以下になら ねばならない」という制約を持つ問題を構成して「同率 3 位」になるケー スを抽出します． 実際には各球団，上位の各組み合わせに対してこの計算を行っています． このような「引き分け」，「同着」の処理は CS 進出ナンバーの計算だけ に限らず，一般の入賞問題で配慮が必要となります． 以下のページでは CS 進出ナンバーの求めかたについてさらに詳しく紹介 しております． http://www.msi.co.jp/nuopt/solution/sports/csnumber.html 日本ではまだ，あまり馴染みのないスポーツソリューションですが，少し ずつ適用例が増えてきています．今後，日本においてもこの流れは加速し ていくことでしょう． はたして今年の栄光を手にするのはどの球団でしょうか，ますます目が離 せません！今年の秋はビール片手に数理計画法に思いを馳せてみてはいか がでしょうか． （池田 悠） ****************************************************************** ■ <トピック> NUOPT FAQ 更新 ****************************************************************** 大好評の NUOPT FAQ 今回もお客様から寄せられる質問を追加しています！ http://www.msi.co.jp/nuopt/user/faq/index.html ご意見，ご要望等ございましたら，お気軽に NUOPT 担当 nuopt-info@ml.msi.co.jp までご連絡ください． NUOPT でお困りの方も，そうでない方もご一読いただければ幸いです． （村山 昇） ****************************************************************** ■ <トピック> 出展のご報告 ****************************************************************** 2012 年 9 月 6 日～ 7 日に FIT2012 金融国際情報技術展にて展示を致し ました．展示ブースに多数ご来場いただき，誠にありがとうございました． また，7 日にはセミナーにて講演を致しました． 2012 年 9 月 9 日～ 12 日に 2012 年度統計関連学会連合大会にて展示を 致しました．展示ブースに多数ご来場いただき，誠にありがとうございま した．また，10 日にはソフトウェア・デモンストレーションセッションに て発表を致しました．ご清聴誠にありがとうございました． 2012 年 9 月 12 日～ 13 日に日本オペレーションズ・リサーチ学会 2012 年秋季研究発表会にて展示を致しました．展示ブースに多数ご来場いただ き，誠にありがとうございました． 今後も様々なイベントに参加予定でございますので，どうぞよろしくお願 い致します． （佐藤 誠） ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・10 月 15 日（月）13:30 ～ 16:30 （大阪開催）最適化入門セミナー ・10 月 17 日（水）13:30 ～ 17:00 スキルアップセミナー・実践編 ・10 月 23 日（火）13:30 ～ 16:30 最適化入門セミナー 会場： << 東京開催 >> （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） << 大阪開催 >> AP 梅田大阪（西梅田） （大阪市北区曽根崎新地 2-3-21 ax ビル 4F） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > セミナーの詳細： 下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html ------------------------------------------------------------------ 10 月は年に 2 回程行っている大阪でのセミナーがございます．データマ イニングやテキストマイニングのセミナーも同時開催です．普段東京に出 られないという方は是非ともお見逃しなく． （佐藤 誠） ****************************************************************** ■ <トピック> 書評「応用に役立つ 50 の最適化問題」 藤沢克樹・梅谷俊治著 ****************************************************************** みなさんこんにちは． NUOPT メールマガジンの新企画として，最適化・数理計画法関係の本の書 評を始めます．弊社研究員が独断と偏見を織り交ぜながら色んな本をご紹 介していければと思います． 皆さんは，数理計画法の本を選ぶのに悩んだ経験はないですか？仕事で数 理計画法に携わることになり，さて勉強しようかと本屋におもむいてみた ものの，どれをとったらいいかわからない．とってみたものの，延々と書 かれた単体法のアルゴリズムの説明や双対定理の証明に途中で挫折．．油 田問題などの例があるが，業務で扱う問題とのギャップの大きさに呆然．． もちろん双対定理が大事な場面もありますし，まずは油田問題などの簡単 な例で親しむことも大事．しかし敢えて言わせてもらいますと，数理計画 法を「使う」という視点から書かれた本は意外と少ないのが実情ではない でしょうか． 我々もお客様から「どんな本で勉強したらいいですか」という声をよくお 聞きします．この書評ではそういった状況を踏まえた上で，数理計画法を 使う上で参考になると我々が考える本をピックアップします． 今回ご紹介する本は藤沢克樹先生と梅谷俊治先生が書かれた「応用に役立 つ 50 の最適化問題」です． この本は書名で銘打っている通り，実務問題 で応用できる最適化の技術が数多く取り上げられています．特徴的なのは， 半正定値計画問題やグリッド環境における最適化など，将来が有望視され る最新技術についても解説されていることです． この本の良い所は，1 章から 3 章までの数理計画法の基本的事柄を抑えれ ば，あとは読者の興味ある分野をつまみ読みできることではないでしょう か．個人的におすすめなのは 6 章・7 章です．6 章の集合被覆問題は，立 地戦略，配車計画等ビジネスの様々な場面で活躍します．本書ではこの問題 への解法が，旧来の手法から最新の手法まで余すことなく取り上げらると 同時にその比較実験まで掲載しており，これほど参考になる文献はありま せん．7 章の看護師スケジューリング問題には，シフトスケジュールにお ける様々な定式化技術が取り上げられております．NUOPT をお使いの方も， 定式化を考えるにあたり是非この章を参考にしてもらえればと思います． ところで「列生成法」という言葉を聞いたことはありますか？数理計画法を より強力に使う方法で，我々も受託作業等でよく使っております．「なん かよくわからないけど使ってみたい．．．」と考える方もいらっしゃるの ではないでしょうか．そんな人におすすめなのは「8.3 一次元資材切り出 し問題」です．この問題の詳細については，本書はもちろん以下の弊社 Web ページも参考にしていただければと思います． http://www.msi.co.jp/nuopt/solution/shift/cutting.html あまり自分の業務と関係ないな，と思われたかもしれませんが，実はこの 問題はとても良い列生成法の例題なのです．本書にはその解説も丁寧に書 かれており，NUOPT をお持ちの方は是非この例題で列生成法を試していた だければと思います． 最適化の最新動向に興味のある方は 5 章「半正定値計画問題」や 9 章「 最適化問題に対する情報技術の適用」がおすすめでしょうか．半正定値計 画問題は頑健なポートフォリオ作成へや D 最適計画法など様々な応用が提 案されており，新たなビジネスの可能性があります．また 9 章で語られて いるように，グリッド環境での最適化計算の研究は進み，同時にニーズも 高まっております．弊社もそうした要望に応えるべく分枝限定法の並列処 理など様々な技術開発に取り組んでいます． いかがでしたでしょうか．「応用に役立つ 50 の最適化問題」は数理計画 法を使う上で助けになる本と思います．是非手にとってみてください．ま た，最初にこのような本は意外と少ないなどと言ってしまいましたが，い やいやありますよ！という方がいましたら是非ご一報ください．ほかにも， 「こんな本を紹介してほしい！」という要望がありましたらご連絡お待ち しております！ （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に NUOPT に関するお問い合わせを頂いたことのある方，および本メール マガジンの配信を希望された方にお送りしています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください．なお，反映作業の都合上，数日間は旧情報にてメー ルが届く場合がございます．なにとぞご容赦ください． 発行：株式会社 数理システム << NUOPT >> 担当 東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================