- 学部・研究科
Faculty/Graduate School - 環
- 時間割コード
Course Code - 64181
- 科目名
Course title
サブテーマ
Subtitle - 最適化分析
- 授業形態/単位
Term/Credits - クラス
Class -
- 秋/2
- 担任者名
Instructor - 巽 啓司
- 曜限
Day/Period - 金1
- 授業概要
Course Description
到達目標
Course Objectives -
授業種別 / Teaching Types
講義（対面型）
言語 / Language
日本語(Japanese)
授業概要 / Course Description
都市の設計や都市における人間の諸活動においては、限られた資源を効率的に利用するため、また何らかの意味での公平性を確保するために、数理的な分析に基づき最適な施策を選択する必要がある。本講義では、そのような目的に利用できる一手法である数理計画法について学ぶ。
数理計画法は、対象となるシステムを数学的なモデルとして定式化すること、またそのモデルに対する最適解を得ること、さらにはその解の分析手法等の総称である。本講義の前半では、数理計画法の概要と、数理計画法で扱う典型的な問題である線形計画問題、またその解法について説明する。後半では、組合せ問題の解法、また都市と関係するいくつかの具体的な問題に関するトピックスについて学習することで、数理計画法の具体的な適用例について学習する。
本科目を学習するためには、線形代数 I/II、解析学 I/II などの科目を履修していることが望ましい。到達目標 / Course Objectives
本講義の到達目標は以下の通りである。
① シンプレックス法を用いて線形計画問題を解くことができる。
② 様々なクラスの数理計画問題があり、求解アルゴリズムが異なることを理解する。
③ 数理計画法の実問題への応用を理解する。授業手法 / Teaching Methods
・教員による資料等を用いた説明や課題等へのフィードバック
・学生による学習のふりかえり
- 授業計画
Course Content -
授業計画 / Course Content
第 1 回: 数理計画問題の概要
数理計画問題の概要について説明する。また、現実の問題を数理計画問題として定式化する方法を、都市に関係のある問題を例に挙げながら説明する。
第 2 回: 線形計画問題とその最適解
線形計画問題の定義について述べ、その最適解が満たす性質について説明する。
第 3 回: シンプレックス法
線形計画問題の基本的な解法であるシンプレックス法について説明する。
第 4 回: シンプレックス・タブロー
シンプレックス法を表形式で実現する手法について学ぶ。
第 5 回: ２段階法
シンプレックス法における初期解を生成する手法について説明する。
第 6 回: 双対定理および感度分析
線形計画問題の解を分析する際に重要になる双対定理、感度分析について説明する。
第 7 回: 前半部分のまとめ
本講義の前半部分で扱った内容についての演習を行う。
第 8 回:中間試験
第 9 回: 組合せ問題とその問題例
決定変数が0，1値となる最適化問題の性質とその問題例について説明する。
第 10 回: 最短経路問題
組合せ問題の代表的な問題の最短経路問題とダイクストラ法について学習する。
第 11 回: 問題の困難性
組合せ問題の求解上の困難性とNP困難について説明する。
第 12 回: 分枝限定法
組合せ問題に対する典型的な厳密解法である分枝限定法について説明する。
第 13 回: メタヒューリスティック解法
局所的最適解を求める近似解法であるメタヒューリスティック解法について説明する。
第 14 回: 後半部分のまとめ
本講義の後半部分で扱った内容についての演習を行う。
第 15 回：到達度の確認授業時間外学習 / Expected work outside of class
教科書等を参考に、しっかりと予習をして講義概要を理解して授業にのぞみ、授業後は学んだ手法について復習しておくこと。
- 成績評価の方法・基準・評価
Grading Policies /
Evaluation Criteria -
方法 / Grading Policies
定期試験を行わず、到達度の確認(筆記による学力確認)と平常成績で総合評価する。
講義中に実施する課題（出席調査を兼ねる）を30点、中間試験を30点、到達度の確認を30点として評価し、60点以上を合格とする。
履修者数が多数になった場合には、成績評価方法を「定期試験（16週目）」に変更することがあります。成績評価方法が変更になった場合は、インフォメーションシステム等で連絡します。基準・評価 / Evaluation Criteria・Assessment Policy
線形計画問題の解法（シンプレックス法）、ならびに数理計画法に関するいくつかのトピックスについての理解度を試す。
- 教科書
Textbooks
その他，必要に応じて 関大LMSやインフォメーションシステムを通じて資料を配布する．
-
参考書
References 福島雅夫 『新版 数理計画入門』（ISBN: 978-4254280043） （朝倉書店） ※旧版（朝倉書店 ISBN: 978-4254209754）をお持ちの方はこちらでも構いません．
柳浦睦憲、茨木俊秀 『組合せ最適化 メタ戦略を中心として』 （朝倉書店）
梅谷俊治 『しっかりと学ぶ数理最適化』 （講談社）
- フィードバックの方法
Feedback Method
- 担任者への問合せ方法
Instructor Contact オフィスアワー
授業の前後に対応する．
その他
必要であれば，メールにより連絡してください．
メールアドレス
k-tatsumi@otemon.ac.jp
- 備考
Other Comments 関連する学習・教育目標の項目：◎(Ｂ)、○(D, Ｅ)