[前へ戻る]
   

 授業科目
 Course Title
数理計画法特論
Mathematical Programming for System Theory
 担当者
 Instructor
教授   進藤 晋  前学期 月曜日1時限
 単 位
 Credit
2

到達目標 Target to be Reached
 本講義の到達目標は、受講生が、線形計画法のシンプレックス法の図形的な意味づけができるようになることと、マトロイドの抽象的概念を具体例をとおして理解できるようになることである。
 
授業内容 Course Content
 コンピュータの急激な発展とともに数理最適化の理論は急速に進展した。その中で、線形計画法は特に進展した分野であり、ORにおける最も重要な技法である。本講義の前半では、組合せ最適化問題を解くことを念頭においた線形計画法の基礎について解説する。また、組合せ最適化問題の多くは計算量的に難しい問題に属しているが、ベクトルの1次独立性の組合せ的抽象化であるマトロイド構造をもつ問題については効率的解法が知られている。そこで本講義の後半では、マトロイドの基礎理論について解説する。
 
授業計画 Course Planning
 各回の授業内容は次のように予定しているが、進捗状況により内容は前後することがある。なお、講義内容を理解するうえで例題を数多く解くことは極めて有用であるから、受講者はそのような習慣づけを心がけてほしい。

線形計画法(8回)
 線形計画法の基礎に解説する。
 1.シラバスの記載事項について確認し、授業の概要について述べる。さらに、線形不等式の解集合の性質について説明する。
 2.線形計画法で最も重要な双対性の概念について説明する。
 3.シンプレックス法(その1)
  線形計画問題を解く解法であるシンプレックス法について具体的に説明する。
 4.シンプレックス法(その2)
  シンプレックス法の収束性について説明する。
 5.凸多面体の基本的性質について説明する。
 6.組合せ最適化問題のラグランジュ緩和について説明する。
 7.完全ユニモジュラ行列について説明する。
 8.第1回小テストと解説
  ここまでの内容について小テスト(50分)を実施し、終了後にテスト内容についての解説を行う。
マトロイド(7回) 
 9.独立集合を用いて、マトロイドを定義する。
10.サーキットを用いて、マトロイドを定義する。
11.貪欲解法について説明する。
12.ランクの性質について説明する。
13.マトロイドの双対性について説明する。
14.マトロイド多面体について説明する。
15.第2回小テストと解説
  ここまでの内容について小テスト(50分)を実施し、終了後にテスト内容についての解説を行う。

 
授業運営 Course Management
 学部卒業程度の線形代数の知識を前提として授業を行う。必要に応じて知識の再確認を行う。
 
評価方法 Evaluation Method
 授業中に課す演習問題(40%)および2回の小テスト(60%)により評価する。

 
オフィスアワー Office Hour (s)
 火曜日13:30~16:10、23号館424研究室(内線3731)。なお、質問等は講義後にもその場で受け付ける。
 
使用書 Textbook (s)
必要に応じて資料を配布する。
参考書 Book (s) for Reference
授業内で指示する。
 
 
 
[前へ戻る]