バックナンバー ( 2013 Vol.1 ) 2013 年 1 月 30 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2013 Vol.1 ( 2013 年 1 月 30 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> RNUOPT のご紹介とセミナーのご案内 ■ <トピック> 数理計画問題の豆知識（第 15 回） ■ <トピック> NUOPT FAQ 更新 ■ <セミナー> 2 月はセミナー情報満載です！！ ■ <トピック> 書評「ネットワーク設計問題」片山直登著 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> RNUOPT のご紹介とセミナーのご案内 ****************************************************************** 統計解析パッケージに入っている重回帰プログラムは，コマンド一発でと ても手軽に使えます．ただ，パラメータにちょっとした制約を入れようと しても入りません．非線形な重回帰もやってみたものの，時間がかかる上 に本当に解が求まっているのかわからない． そんなことで困っている方はいらっしゃいませんか． じつは重回帰は最適化の一種ですから，「制約付きの重回帰」は NUOPT の 得意分野なのです．でも「ガチ」で最適化ではない．多くのデータは統計 解析パッケージの中にあるという方も多い．要するに 統計解析を「軸足」とした最適化が求められています． 統計解析を「軸足」とした最適化の代表格はポートフォリオ最適化ですね． 分散共分散行列や主成分分析の結果に対して，リスクの分布の特徴量を最 適化するわけです．最適化したポートフォリオが与える分布を目視で確認 したり，バックテストしてパフォーマンスを集計したいと考えるのはごく 自然なことです． RNUOPT はそんな目的のためのツールです．フリーな統計解析ツール R に NUOPT を組み込みました．最適化の核となる部分は NUOPT そのまま． SIMPLE も R 言語に移植されていてインタプリタでモデルが定義できて， 制約付き/非線形な重回帰，相関行列のキャリブレーションが自在にできる 環境になっています．金融ポートフォリオモデルも多数ビルトインされて います． 2 月 26 日 15:00 ～ 17:00 に RNUOPT セミナーを行います． ここでは最適化専門のパッケージだからできる様々な解析手法を統計解析 や広告最適化，金融工学の例を取って具体的に説明します．奮ってご参加 頂ければ幸いです． なお，セミナーの詳しい内容については下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/rnuopt.html （田辺 隆人） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 15 回） ****************************************************************** 突然ですが，皆さんは「生産スケジューリング」という言葉を聞いて，何を 思い浮かべるでしょうか? － SCM（サプライチェーンマネジメント）の一部 － トヨタ生産方式の「かんばん方式」 （Just In Time とほぼ同一の方式で，各生産工程で無駄な生産を 排除する） － ボトルネックを解消しながら，各製品の納期を遵守する計画を立案し ていく 等々，幅広い連想をされたのではないかと思います． 一概に生産スケジューリングと言いましても，受注方法や生産方式により， 様々な手法が存在します． 全てを紹介するのは，与えられた原稿上無理がありますので，今回はその 中でも，ジョブショップ型のスケジューリングを中心に紹介させていただ きます． 工場には複数の機械が用意されていて，各製品の各工程でそれらの機械を 共有して使用し，製品を製造するものとします． 各製品の製造工程で，使用する機械順が異なる問題のことを，ジョブショッ プ型スケジューリングといいます． このジョブショップ型スケジューリングは，資源制約付きプロジェクトス ケジューリングの代表的な問題の 1 つでして， － 各製品の製造工程間の先行制約 － 各時刻の使用リソース（各機械）上限制約 を満たすもとで，全体の作業完了時刻を最小化するようなスケジューリン グを考えます． （各製品の納期遅れ総和を最小化するケースもあります．） 一般的に大規模なジョブショップ型スケジューリングは，厳密解を得るの が非常に難しい問題となります． NUOPT ではそのような問題に対して，タブー探索をベースとした資源制約 付きスケジューリング用のアルゴリズム rcpsp を用いたアプローチを用意 しております． なお，一般的な資源制約付きプロジェクトスケジューリングではその他に， － 各製品の製造方法（モード） もあわせて決定することがしばしばあります． 先のジョブショップの例では，リソースは機械のみで考えましたが，例え ば人手でもその仕事を賄うことができることとします． 一般的には機械の方が短時間で製品を生産することができるかと思います が，特定の機械の使用がボトルネックになっていて，それを人手で代替し たほうが全体の作業が早く完了するといったケースも実際には起こり得ま す． このようなモードの自動選択も，NUOPT 搭載の rcpsp では考慮することが できます． 以上ご紹介したように，実務で登場するような大規模問題に対しても，十 分に満足できるスケジューリングを得ることができます． ただし実務でこのようなスケジューリングを扱う場合， (a) 突発的な機械の故障 (b) 機械の処理時間のブレ というのが現実的には起こり得ます． (a) に対しては，迅速にリスケジューリングを行うことができる仕組みを 用意しておく必要があります． 一方 (b) に対しては，同じ位よいスケジュール結果を複数用意します． それらに対し，処理時間を一定規則に従ってぶらすシミュレーションを行 います． シミュレーションの結果，全体の作業完了時刻，もしくは納期遅れ総和が そこまで大きく変化しないスケジュールを，頑健（ロバスト）なスケジュー リングとして採用します． このように (a)・(b) まで考慮することにより，本当の意味で実務で使え るスケジューリングが可能となります． 最後に，不定期ではございますが --- 生産スケジューリング・自動作成支援セミナー http://www.msi.co.jp/nuopt/seminar/scheduling.html --- を弊社では実施しております． このセミナーでは，具体例を交えた生産スケジューリングのご紹介および， (a)・(b) の具体的なアプローチをご説明いたします． 次回のセミナー日程が決まりましたらお知らせしますので，奮ってご参加 ください． （多田 明功） ****************************************************************** ■ <トピック> NUOPT FAQ 更新 ****************************************************************** 大好評の NUOPT FAQ 今回もお客様から寄せられる質問を追加しています！ http://www.msi.co.jp/nuopt/user/faq/index.html ご意見，ご要望等ございましたら，お気軽に NUOPT 担当 nuopt-info@ml.msi.co.jp までご連絡ください． NUOPT でお困りの方も，そうでない方もご一読いただければ幸いです． （村山 昇） ****************************************************************** ■ <セミナー> 2 月はセミナー情報満載です！！ ****************************************************************** セミナー全体は下記からご覧いただけます． http://www.msi.co.jp/nuopt/seminar/index.html ◆◇ ウェブマーケティングセミナー追加開催！ 夏に一度開催し大好評満員御礼のウェブマーケティングセミナー 2 月 20 日に追加開催が決定致しました．今回も前回同様，株式会社リクルート ライフスタイル様より特別講師をお招きしご講演頂きます． 最先端の事例から調査・研究までを紹介致します． ・膨大なデータを有効に活用したい方 ・最先端のソリューションを取り込みたい方 ・マーケティングの新しいヒントが欲しい方 にお勧めのセミナーになっております．本セミナーの話題としては，レコ メンド，アドネット，データフュージョン，テキストの活用方法等，デー タマイニングから数理最適化までの道のりをわかりやすく説明致します． 特別講演は以下のような内容になっております． 「フラッシュマーケティングサイトにおけるリコメンドメールの最適化 事例紹介」 特別講師： 株式会社リクルートライフスタイル ネットビジネス推進室 ウェブマーケティンググループ データチーム 大澤 健太郎 様 ◆◇ 名古屋初開催！ 最適化入門セミナー 2 月 14 日に名古屋会場にて開催致します．これまで新宿と大阪（年二回） で実施していましたが，今後年に一回を目途に名古屋でも開催致します． これまで遠くてなかなか参加できなかったという方是非ともご参加くださ い． ◆◇ RNUOPT セミナー開催！ こちらは本メールマガジンのトピックでもご紹介しております，第一回目 のセミナーです．2 月 26 日に開催致します． その他，通常運営のセミナーは以下のようになっております． ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・2 月 19 日（火）13:30 ～ 16:30 最適化入門セミナー ・2 月 27 日（水）13:30 ～ 17:00 NUOPT スキルアップセミナー基礎編 会場： （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） アクセスマップ: http://www.msi.co.jp/msi/location.html お申し込み方法： 「（株）数理システム << NUOPT >> セミナー申込み」 上記のタイトルで以下のメールアドレスにメールをお願いします． nuopt-info@ml.msi.co.jp メールの内容としましては, ・参加者のお名前 ・ご所属 ・何日のセミナーに参加を希望されるか をお書きください. セミナーの詳細： 内容については下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html また弊社開催の他のセミナーの詳細な日程については下記 URL をご参照 ください． http://www.msi.co.jp/packages/seminar_list.html ------------------------------------------------------------------ （佐藤 誠） ****************************************************************** ■ <トピック> 書評「ネットワーク設計問題」片山直登著 ****************************************************************** みなさんこんにちは． 今回の書評では片山直登先生著「ネットワーク設計問題」（朝倉書店）を 取り上げたいと思います． 自分は業務で最適化に携わっているけど，ネットワーク関係ではない，だ からいわゆる「ネットワーク問題」とは縁が薄い．．．そんなふうに考え ていませんか？ネットワーク問題は，ネットワーク設計者はもちろんそれ 以外の方も知っておいて損のない知識です．ネットワーク問題がどのよう にして広く現実の問題に応用されているかについては以下の過去記事もご 参考ください． http://www.msi.co.jp/nuopt/mailmagazine/backnumber1011.html#6 さて本書ですが「最小費用フロー問題」や「多品種フロー問題」等の基本 問題はもちろん，「固定費用をもつネットワーク設計問題」「ハブネット ワーク設計問題」等多種多様なネットワーク問題が扱われています．問題 の種類だけではなく，そのアプローチ方法についても数多く取り上げられ ていることも特色の一つです． 第一章「ネットワーク問題」には最短経路，最小木問題等基本的なネット ワーク問題が取り上げられています．これらは基礎となる大事な問題では ありますが，ここで取り上げられているアルゴリズムを完全に理解するこ とは必須ではないと思います．むしろここで挙げられているのは多項式時 間で解けるという意味で「易しい」問題ですので，どういった問題が易し いかを把握することが実務家にとっては大事かと思います． 第二章の「ネットワークフロー問題」には「最小費用フロー問題」「多品 種フロー問題」が取り上げられています．これらはネットワーク分野にと どまらず姿を変えて様々な問題で現れる，数理計画における基本問題と言 えます．さらに「利用者均衡フロー問題」というモデルが取り上げられて いる点がユニークに感じました．この興味深いモデルは，日本では田口東 先生によって東急田園都市線など首都圏の電車に適用されています（[1]）． またこの章で現れる多品種フロー問題の大規模解法である「資源主導によ る分解法」等は，コンピュータ技術の発達した今では活躍の場が少ない解 法かもしれません．しかしながら後の章で現れる Lagrange 緩和法等とつ ながる話ですので内容をおさえることは意味のあることと思います． 第三章以降は種々のネットワーク問題が取り上げられています．特徴的な のは各問題に対して様々な厳密解法・近似解法が取り上げられ，比較検討 されていることです．特に「予算制約をもつネットワーク設計問題」で取 り上げられている Lagrange 緩和法や Benders 分解はネットワーク問題の みならず一般の整数計画問題で有用な手法です．一部解法については計算 時間等の比較表が載っていますので，読者はこれを参考にしながら適切な 手法を検討することができます． 本書は「ネットワーク問題」の問題及び解法が網羅的に記述されており， 手元に置くと大変心強い一冊と言えます．ご興味ある方は本書を片手にネッ トワーク問題に是非挑戦してみてはいかがでしょうか． 最後に補足させていただきたいのは，ネットワーク問題を数理計画問題と して記述してソフトウェアに解かせるのは意外と骨が折れるということで す．ネットワークの始点・終点の考慮，実行不可能なケースへの対処方法 など注意すべきポイントがいくつもあります．「 NUOPT/SIMPLE 例題集」 には本書にある多品種フロー問題等を NUOPT/SIMPLE の例題として取り上 げています．ネットワーク問題に取り組まれる方は，是非こちらも参考に していただければと思います． [1] 田口東「首都圏電車ネットワークに対する時間依存通勤交通配分モデ ル」日本オペレーションズ・リサーチ学会和文論文誌,48(2005) 85-108 （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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 ==================================================================