オペレーションズ・リサーチ

本講義では， オペレーションズ・リサーチにおける重要なテーマのひとつである組合せ最適化を扱う． 組合せ最適化問題に対する種々の手法の中でも， とくに実践的解法を中心に解説する． まず組合せ最適化の定義と代表的な組合せ最適化問題を紹介する． 次に厳密解法の基本戦略である動的計画法と分枝限定法を紹介する． 近似解法としては，まず基本戦略として欲張り法や局所探索法を解説したのち， その発展形であるメタ戦略にもふれる．

• 2009年8月日24(月)─28日(金)
• 対象年次および学科: 3年 全学科
• 授業の目的・達成目標: 組合せ最適化問題に対し，実践的な問題解決手法の基本戦略を学び， それらを応用するための基礎力を身につけることを目標とする．
• 履修推奨科目: 離散数学の基礎的な知識を習得していることが望ましい．
• 単位取得基準: 講義終了時にレポートを提出してもらう． その得点が合格点以上であること.
• 参考書・参考資料など（講義の期間中一時的に一部の資料の電子ファイルを置きますが， 学会誌等に掲載された最終版とは若干異なります）
  • 柳浦, 茨木, 組合せ最適化: メタ戦略を中心として （経営科学のニューフロンティア2），朝倉書店, 2001.
  • 野々部，柳浦，``局所探索法とその拡張 ─ タブー探索法を中心として,'' 計測と制御，Vol.47, No.6, pp.493-499, 2008年6月. PDF
  • 柳浦，``局所探索法 ─ 反復改善に基づく最適化の基本戦略,'' オペレーションズ・リサーチ，Vol. 52, No. 9, pp. 538-542, 2007年9月.
  • 柳浦, 野々部, ``分枝限定法 ─ さらなる計算効率の希求,'' システム/制御/情報, Vol. 50, No. 9, pp. 350-356, 2006年9月. PDF
  • 柳浦, ``簡単そうで難しい組合せ最適化 ─ 身近な話題から,'' 数理工学のすすめ（改訂版），現代数学社，2005年1月, pp. 9-13. PDF, PS（gzipで圧縮）
  • 柳浦, ``組合せ最適化の数理: 計算困難問題への挑戦,'' 数理科学，第40巻12号，No. 474, pp. 21-27, 2002年12月． 内容
• 講義の補足資料
  • 巡回セールスマン問題に対する多断片法
  • 文書整形問題に対する動的計画法
  • 近傍グラフ
  • POPの概念

柳浦のホームページ