線形計画法

岡本 吉央

概要

• 研究室の学生向けに線形計画法の理論の基礎に関して講義と演習を行ないます。
• 線形計画法は生産計画，流通，などの経営分野だけではなく、 制御理論やシステム解析などの工学分野の至るところに応用があり、 また，情報科学においては、 アルゴリズム設計における基本的な道具としても用いられています。 より一般的で、より多くの応用をもつ最適化の理論の枠組においても、 線形計画法の理論が確立した方法論は基礎となっています。
• 講義と演習では理論的な側面に焦点を絞ります． 実用上の側面や具体的な応用までは手が届かないことになります．
• 演習には「復習問題」と「理解度増強問題」があります． 復習問題は講義内容の復習になるような語句の確認や計算問題などが中心です． 理解度増強問題は，講義内容に関連した問題を通して理解を深めます． 講義で扱わなかったものでも重要なものが理解度増強問題として出てくることもあります．

予定

• 毎日の予定
  • 10:00--11:30 講義 前半
  • 11:30--12:00 演習 前半
  • 13:30--15:00 講義 後半
  • 15:00--16:00 演習 後半
• 1週間の予定
  • 11日前半 (演習) 線形計画問題の定義，例，標準形
  • 11日後半 (演習) 線形計画問題の幾何，図解法
  • 12日前半 (演習) 双対問題，双対定理
  • 12日後半 (演習) 双対定理 (続)，相補性定理，双対問題の幾何
  • 13日前半 (演習) 単体法
  • 13日後半 (演習) 単体法 (続)
  • 14日前半 (演習) 整数線形計画問題，緩和問題
  • 14日後半 (演習) 分枝限定法
  • 15日前半 (演習) 整数多面体，完全ユニモジュラ性
  • 15日後半 (演習) 最大フロー問題，最大マッチング問題，最小頂点被覆問題

その他

• ソフトウェア
• 巡回が起こる例