バックナンバー ( 2015 Vol.4 ) 2015 年 7 月 15 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2015 Vol.4 ( 2015 年 7 月 15 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 「運用」と「経営」の問題を同時に解く ■ <トピック> 最適化読本と続・最適化読本 ■ <セミナー> Numerical Optimizer セミナーのご案内 ■ < tips > 数理計画問題の豆知識（第 20 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 「運用」と「経営」の問題を同時に解く ****************************************************************** いわゆるシフトスケジューリングは，在籍人員とその属性と勤務量を所与 として勤務表を求めます．一方，そもそもの在籍メンバーの数と属性はど のようにして決めるべきでしょうか．メンバーの夏休みが増えるお盆の時 期には現場は回らないので増員が必要やもしれませんが，年中そうとは限 りませんし，増員するメンバーのスキルにも配慮が必要です． プラントの運転計画問題はボイラーなど熱源機器の属性と一日の需要を所 与として，機器の運転を求めます．では，熱源機器の更新の意思決定はど のように行うべきでしょうか．需要の多い夏場を見込んで大容量の機器を 導入してしまうと，冬場で活用し切れず，無駄な設備投資になってしまう かもしれません． 数理計画法を用いた案件の多くには，在籍人員や機器属性を所与として「 運用」を最適化したい，という動機と，「運用」を見込んで在籍人員や機 器属性そのものを最適化したい，という問題設定にかかわる「経営」上の 動機の二つが含まれています． 言うまでもなく「運用」と「経営」は相互に依存しているので，そもそも 切り離して考えることは難しいのですが，通常の会社組織では「運用」は 「現場」，「経営」は「本社」といった具合に決定の主体が分離している のがむしろ普通．言ってみれば「現場」と「本社」の壁が「全体最適」を 妨げています． 数理計画法は「運用」と「経営」を同時に考慮することで，その壁を超え ることができる手法です．例えば先日の本メールマガジンで紹介した車両 計画問題は，「運用」にあたる車両のルーティングと，「経営」にあたる 車両の導入台数を一気に解いてしまいます． また，上述した人員の配置や設備設計の問題も「運用」を下敷にした最適 な「経営」，すなわち設備投資を導くことが実際にできています． これが可能になった背景にはもちろん，昨今の計算機パワーの増大もあり ますが，モデルを適切に階層化し，「運用」問題と「経営」問題で情報（ 双対変数）をうまく受け渡して反復する列生成法/ラグランジュ緩和法と いったアルゴリズムの進展も寄与しています． 「運用」/「経営」すなわち，「現場」/ 「本社」の擦り合わせに「双対 変数」といった数学的な実体が寄与している，というのはなんだか面白い ところではありますね． （田辺 隆人） ****************************************************************** ■ <トピック> 最適化読本と続・最適化読本 ****************************************************************** 当社のセミナー等にご参加頂きました方や，直接お打合せさせて頂いた方 へ，名刺代わりにお渡ししている「最適化読本」「続・最適化読本」につ いてのウェブページを公開致しました． http://www.msi.co.jp/nuopt/download/dokuhon/index.html 「統計解析・データ分析」といった分野と比較すると「数理計画・最適化」 の認知度はまだまだ伸びしろがある状態と感じており，少しでも「数理計 画・最適化」の醍醐味を多くの方々に伝えたいという想いから作成した小 冊子が「最適化読本」「続・最適化読本」で御座います． 実務上の課題解決ツールとしてのお話を，アルゴリズムの中身や数式には 頼らない形で書きました．ちょっとした空き時間や移動中に気軽にお読み 頂ければ幸いです． ウェブ上では第一章のみダウンロードしてご覧頂けます．お問合せ頂けれ ば，無料で郵送致しますのでご興味がある方は是非とも一読頂ければ幸い で御座います． （佐藤 誠） ****************************************************************** ■ <セミナー> Numerical Optimizer セミナーのご案内 ****************************************************************** -----[ 定例セミナーがリニューアルします！ ] ---------------------- これまで「最適化セミナー」「スキルアップセミナー・入門編／実践編」 として，最適化・数理計画による実務へのアプローチや，Numerical Optimizer の紹介をしてきた定例セミナーですが，この 8 月からそれぞれ の「色」をはっきり魅せるリニューアルをします． ◆ 課題解決!!最適化ソリューション無料体験セミナー 最適化セミナーのテーマ「最適化って何？という疑問にお答えします」を さらに掘り下げて，最適化ソリューションで実務の課題をどのように解決 するかを取り上げます． - 次回日時 ・ 8 月 11 日 (火) 13:30 ～ 16:30 ・ 9 月 3 日 (木) 13:30 ～ 16:30 ◆ 最適化ソルバーセミナー ～Numercial Optimzier ハンズオン実習～ Numerical Optmizer による実習を通して，数理計画ソルバーを扱う基本を 学ぶセミナーです．Numerical Optimizer の利用方法の他，「数理計画問 題としての定式化」について詳しく解説します． - 次回日時 ・ 9 月 4 日 (金) 13:30 ～ 17:00 ◆ Numerical Optimzer スキルアップセミナー スキルアップセミナー・実践編を引き継いだ内容です．現実問題と数式の ギャップをどのように埋めるかという数理計画の肝や，最適化アルゴリズ ムの解説や Numerical Optimizer のマニアックな使い方なども紹介します． 10 月からの開催を予定しております． 会場 : (株) NTT データ数理システム セミナールーム （東京都新宿区信濃町 35 信濃町煉瓦館 1F） アクセスマップ http://www.msi.co.jp/msi/location.html ------------------------------------------------------------------ 新しいセミナーにご期待ください． お申込み・詳細は下記のページをご覧ください． http://www.msi.co.jp/event/index_nuopt.html （中野 雄介） ****************************************************************** ■ < tips > 数理計画問題の豆知識（第 20 回） ****************************************************************** 今回は「シフトスケジューリング問題」について紹介させていただきます． シフトスケジューリングとは，制約条件を満たすように人に仕事を割り当 てる問題を指します． ここでの制約条件は，たとえば - 「日勤」を行う要員は各日 2 人とする． - 「夜勤」を行う要員は各日 1 人とする． - 「夜勤」の次の日に「日勤」は行わない． といった仕事上の要請から来るものから， - A さんは水曜日に「夜勤」を行うことはできない． というような要員個人の事情から来るものまで様々です． では，以上の条件を満たすように，A～D の 4 人の要員で月曜日から金曜 日までのシフトを組んでみましょう． ---- [ シフト例 1 ] --------------------------------------------- 月曜 火曜 水曜 木曜 金曜 A 夜勤 夜勤 休み 夜勤 夜勤 B 休み 日勤 夜勤 休み 日勤 C 日勤 日勤 日勤 日勤 日勤 D 日勤 休み 日勤 日勤 休み ------------------------------------------------------------------ いかがでしょうか． 全ての制約条件を満たしてはいますが， - A さんが 4 日も夜勤を担当している． - C さんは夜勤はないものの，毎日日勤で休みがない． - D さんは 2 日も休みがあり，夜勤もない． と，かなり不平等なシフトになってしまっています． これらの問題を改善するには， - シフトにおける各要員の負荷をできるだけ公平にする． という制約を加える必要があります． では，ひとことで「要員の負荷を公平にする」といってもどうすればよい のでしょうか． これを実現するひとつの方法として，「日勤」と「夜勤」のそれぞれの「 つらさ」を数値化して日ごとの総和を要員の負荷とし，そのばらつきが小 さくなるようにする，とする方法があります． 上の例で，「日勤のつらさ」を 1，「夜勤のつらさ」を 3 とすると，各要 員の負荷は A：12, B：5, C：5, D：3 となります．A さんに負荷が集中していることが一目瞭然ですね． 今回の例では， ---- [ シフト例 2 ] --------------------------------------------- 月曜 火曜 水曜 木曜 金曜 A 日勤 夜勤 休み 日勤 日勤 B 日勤 日勤 夜勤 休み 日勤 C 休み 日勤 日勤 夜勤 休み D 夜勤 休み 日勤 日勤 夜勤 ------------------------------------------------------------------ というシフトを組むことで，各要員の負荷を A：6, B：6, C：5, D：8 とすることができます． 上の例に比べて，要員間の不平等がかなり解消されていることが分かりま す． では，ある週に上のシフト例 2 を採用したとします．同じようにして次の 週のシフトを組んでみましょう． ---- [ シフト例 3 ] --------------------------------------------- 月曜 火曜 水曜 木曜 金曜 A 日勤 夜勤 休み 日勤 日勤 B 日勤 日勤 夜勤 休み 日勤 C 休み 日勤 日勤 夜勤 休み D 夜勤 休み 日勤 日勤 夜勤 ------------------------------------------------------------------ シフト例 2 とまったく同じですね．同じ問題を解いているので，至極当然 の結果です． しかし，毎週この同じシフトを使い続けてもいいものでしょうか．シフト 例 1 よりは要員の負荷のばらつきが少ないとはいえ，C さんと D さんの 負荷には違いがあります．毎週このシフトを使い続けると，D さんから不 満が出るのは避けられないでしょう． このような場合の解決策として，負荷の「累積」を考える，という方法が あります．これにより，ある週に負荷の大きい勤務をこなした要員が，続 けて負荷の大きい勤務を行うことを避けることができます． 負荷の累積を考えた場合の次の週のシフトは，たとえば次のようになりま す． ---- [ シフト例 4 ] --------------------------------------------- 月曜 火曜 水曜 木曜 金曜 A 休み 日勤 日勤 夜勤 休み B 日勤 夜勤 休み 日勤 日勤 C 夜勤 休み 日勤 日勤 夜勤 D 日勤 日勤 夜勤 休み 日勤 ------------------------------------------------------------------ このときの先週からの累積の負荷は， A：11, B：12, C：13, D：14 となります．同じシフトを使い続けた場合に比べ，累積の負荷のばらつき が小さくなっているのが分かります． シフトスケジューリングは実務においてよく現れる問題である一方，問題 が大規模になりやすく最適解を求めることが難しい問題です．Numerical Optimizer では，メタヒューリスティクスアルゴリズム WCSP により，実 務上十分な解を現実的な時間内に求めることが可能です．シフト作成でお 困りの方は是非 Numerical Optimizer をお役立てください． （田中 大毅） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 数理システム Numerical Optimizer に関するお問い合わせを頂いたこ とのある方，および本メールマガジンの配信を希望された方にお送り しています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください．なお，反映作業の都合上，数日間は旧情報にてメー ルが届く場合がございます．なにとぞご容赦ください． 発行：株式会社 NTT データ数理システム << 数理システム Numerical Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================