シラバス参照
シラバス参照
| 科目一覧へ戻る | 2023/03/17 現在 |
| 科目名／Subject | 計画科学II |
|---|---|
| 担当教員（所属）／Instructor | 原口 和也 (商学部) |
| 授業科目区分／Category | 昼間コース 学科別専門科目 |
| 開講学期／Semester | 2021年度／Academic Year 前期／Spring Semester |
| 開講曜限／Class period | 他 |
| 対象所属／Eligible Faculty | 商学部／Faculty of Commerce |
| 配当年次／Years | 3年 , 4年 |
| 単位数／Credits | 2 |
| 研究室番号／Office | |
| オフィスアワー／Office hours |
| 更新日／Date of renewal | 2021/02/22 | ||
|---|---|---|---|
| 授業の目的・方法 ／Course Objectives and method |
この科目では，オペレーションズ・リサーチ（OR）における最も重要な研究領域の一つである離散最適化（組合せ最適化）問題について，Python言語と専用ライブラリを用いた実践的な解決方法を中心に学ぶ． 授業は講義とプログラミング実習を織り交ぜて実施する． |
||
| 達成目標 ／Course Goals |
曖昧模糊とした現実の問題から重要なエッセンスを抽出して離散最適化問題として定式化（モデル化）し，計算によって解を導くという問題解決の流れを体得してもらいたい． ・定式化ができるようになるためには馴れが必要である．講義では典型的な最適化問題をいくつか取り上げるが，それらが現実の事例をどのようにモデル化したものかを掴んでもらいたい． ・問題を解くための計算の手順をアルゴリズムという．いくつかの問題について代表的なアルゴリズムを紹介するが，計算手順を把握するのはもちろんのこと，どのようなロジックでアルゴリズムが組み立てられているのか，ある程度のレベルまで理解してもらいたい． ・最適化計算に関する実習を行う．具体的には，Python言語とそのpulpライブラリおよびNetworkXライブラリを用いて最適化問題を解くことの実習である．一定のレベルの最適化問題を自分で定式化し，プログラムを書いて解けるようになってもらいたい． |
||
| 授業内容 ／Course contents |
・ネットワーク最適化問題：最小木問題，最短路問題など ・より難しい最適化問題：ナップサック問題，巡回セールスマン問題など ・アルゴリズム設計技法：欲張り法，動的計画法，局所探索法 ・Pythonプログラミング |
||
| 事前学修・事後学修 ／Preparation and review class |
・事前配布する資料には目を通しておくこと．どのような論理で話が展開するのかを頭に入れておくことが望ましい． ・ほぼ毎回の講義で演習とその解説を行うが，講義後に改めて解き直し，理解に努めてもらいたい． |
||
| 使用教材 ／Teaching materials |
資料を配布する．manabaからもダウンロードできるようにする予定である．以下に参考書を示す． ・今野：ヒラノ教授の線形計画法物語，岩波書店． ・山本，久保：巡回セールスマン問題への招待，朝倉書店． ・穴井，斉藤：今日から使える ! 組合せ最適化離散問題ガイドブック，講談社． ・並木：Python による数理最適化入門 (実践Pythonライブラリー)，朝倉書店． ・辻：Pythonスタートブック，技術評論社． |
||
| 成績評価の方法 ／Grading |
実習およびレポートに基づいて評価する． | ||
| 成績評価の基準 ／Grading Criteria |
社会情報学科標準成績評価基準に従う． | ||
| 履修上の注意事項 ／Remarks |
・離散数学およびプログラミングに関連した科目を履修していると，学習内容を理解しやすいであろう． ・実習室を使用予定のため，履修制限を行う予定である．教務課からの履修制限に関する通知に注意すること． ・Pythonが使用可能なラップトップPC等を持つ履修者は，授業に持ち込んで使用することを歓迎する． |
||
| 実務経験者による授業 ／Courses conducted by the ones with practical experiences |
該当しない／No | ||
| 遠隔授業 ／Online class |
|
| No. | 回（日時） ／Time (date and time) |
主題と位置付け（担当） ／Subjects and instructor's position |
学習方法と内容 ／Methods and contents |
備考 ／Notes |
|---|---|---|---|---|
| 1 | 1, 2 | 最適化問題の導入 定式化に関する学習・演習・実習 |
線形計画問題 整数計画問題 |
|
| 2 | 3,4,5 | Python言語およびpulpライブラリに関する学習・演習・実習 | Python言語 pulpライブラリ |
|
| 3 | 6,7 | 定式化に関する総合実習 | ||
| 4 | 8,9,10 | グラフ上の最適化問題 グラフアルゴリズム NetworkXライブラリの導入 |
グラフ理論 グラフアルゴリズム グラフ上の最適化問題 |
|
| 5 | 11,12 | NetworkXライブラリに関する学習・演習・実習 | Python言語 NetworkXライブラリ |
|
| 6 | 13,14,15 | 計算困難問題に対するアプローチ | 厳密解法（動的計画法と分枝限定法） 近似解法（欲張り法と局所探索法） |