[前へ戻る]
   

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

関連するディプロマポリシー Related Diploma Policy
時代の課題と社会の要請に応えた専門的知識と技能/Expert knowledge and skills to address the issues of the age and the demands of society
 
到達目標 Target to be Reached
 本講義の到達目標は、受講生が、線形計画法のシンプレックス法の図形的な意味づけを理解し、マトロイドの抽象的概念を具体例をとおして理解することである。さらにその理解を、他者に表現して伝え、互いの理解を吟味できるようになることを目的とする。
 工学専攻のカリキュラム・ポリシーに従い、学部卒業程度の線形代数の知識があることが望ましい。

 
授業内容 Course Content
 コンピュータの急激な発展とともに数理最適化の理論は急速に進展した。その中で、線形計画法は特に進展した分野であり、ORにおける最も重要な技法である。本講義の前半(第1回~第7回)では、組合せ最適化問題を解くことを念頭においた線形計画法の基礎について解説する。また、組合せ最適化問題の多くは計算量的に難しい問題に属しているが、ベクトルの1次独立性の組合せ的抽象化であるマトロイド構造をもつ問題については効率的解法が知られている。そこで本講義の後半(第8回~第14回)では、マトロイドの基礎理論について解説する。
 
授業計画 Course Planning
授業計画
 各回の授業内容は次のように予定しているが、進捗状況により内容は前後することがある。なお、講義内容を理解するうえで例題を数多く解くことは極めて有用であるから、受講者はそのような習慣づけを心がけてほしい。
予習としては、事前に配布する資料の各回の該当分をよく読んでおくことが必要不可欠である。
 また、復習としては、資料の演習問題を解くことで講義内容を再確認することを勧める。
 なお、予習・復習合わせて各回あたり4時間の自己学習を想定している。
線形計画法(第1回~第7回) 線形計画法の基礎について解説する。 図形的な意味づけに重点をおく。
第1回:シラバスの記載事項について確認し、授業の概要について述べる。さらに、線形不等式の解集合の性質について説明する。
第2回:線形計画法で最も重要な双対性の概念について説明する。
第3回:シンプレックス法(その1) 線形計画問題を解く解法であるシンプレックス法について具体的に説明する。
第4回:シンプレックス法(その2) シンプレックス法の収束性について説明する。
第5回:凸多面体の基本的性質について説明する。
第6回:組合せ最適化問題のラグランジュ緩和,完全ユニモジュラ行列について説明する。
第7回:小テストと解説1 第6回までの内容について小テスト(60分)を実施し、終了後にテスト内容についての解説(40分)を行う。

マトロイド(第8回~第14回) マトロイドの基礎について解説する。マトロイドの抽象的な構造の理解を深めるために、行列やグラフの例を多く取り上げる。
第8回:独立集合を用いて、マトロイドを定義する。
第9回:サーキットを用いて、マトロイドを定義する。
第10回:貪欲解法について説明する。
第11回:ランクの性質について説明する。
第12回:マトロイドの双対性について説明する。
第13回:マトロイド多面体について説明する。
第14回:小テストと解説2 第8回から第13回までの内容について小テスト(60分)を実施し、終了後にテスト内容についての解説(40分)を行う。


 
授業運営 Course Management
すべて講義形式による.
 
評価方法 Evaluation Method
毎回授業中に課す演習問題(40%)および2回の小テスト(60%)により評価する。
 
オフィスアワー Office Hour (s)
火曜日13:00~14:00、23号館424研究室(内線3731)。なお、質問等は講義後にもその場で受け付ける。
 
使用書 Textbook (s)
資料を配布する。
参考書 Book (s) for Reference
John Lee,A First Course in Combinatorial Optimization,Cambridge UP,2004
James Oxley『Matroid Theory』[Oxford UP]2011

 
 
 
[前へ戻る]