シラバス参照

授業情報／Course information

科目一覧へ戻る 2023/03/17 現在

科目名／Subject 計画科学II
担当教員（所属）／Instructor 原口　和也 (商学部)
授業科目区分／Category 昼間コース　学科別専門科目
開講学期／Semester 2018年度／Academic Year 　後期／Fall Semester
開講曜限／Class period 月/Mon　2
対象所属／Eligible Faculty 商学部／Faculty of Commerce
配当年次／Years 3年 , 4年
単位数／Credits 2
研究室番号／Office
オフィスアワー／Office hours
更新日／Date of renewal 2018/02/23
授業の目的・方法
／Course Objectives and method		 　「計画科学Ⅰ」および「計画科学Ⅱ」のテーマは「最適化問題」である．最適化問題とは，与えられた条件を満たす解のうち，「最良の」ものを求める問題である．この問題はオペレーションズ・リサーチにおける最も重要な研究分野の一つで，現実における様々な計画や意思決定の場面に応用を持つ．また近年では人工知能や機械学習，更にはビッグデータの解析など，分野横断的に最適化の技術が応用されることも少なくない．
　「計画科学Ⅱ」では，解が「組合せ的構造」を持つような最適化問題である，「組合せ最適化問題」について学ぶ．何をもって「組合せ的」と呼ぶか，その定義は簡単ではないが，たとえば解が組合せ，順列，整数ベクトルで表されるような問題は，一般に組合せ最適化問題として取り扱われることが多い．
　授業はいわゆる講義形式で実施し，基本的に板書によって進める．ほぼ毎回の講義で演習を行い，受講者の理解を促す．
達成目標
／Course Goals		   曖昧模糊とした現実の事例を，組合せ最適化問題としてモデル化（定式化）し，計算によって解を導くという，問題解決の流れを体得してもらいたい．
● モデル化ができるようになるためには馴れが必要である．講義では典型的な最適化問題をいくつか取り上げるが，それらが現実の事例をどのようにモデル化したものかを掴んでもらいたい．
● 問題を解くための計算の手順をアルゴリズムという．計算手順を把握するのはもちろんのこと，どのようなロジックでアルゴリズムが組み立てられているのか，ある程度のレベルまで理解してもらいたい．
● 最適化計算に関する実習を行う．具体的には，Python言語とそのpulpライブラリおよびNetworkXライブラリを用いて最適化問題を解くことの実習である．一定のレベルの最適化問題を自分で定式化し，プログラムを書いて解けるようになってもらいたい．
授業内容
／Course contents		 ● ネットワーク最適化問題：最小木問題，最短路問題など
● より難しい最適化問題：ナップサック問題，巡回セールスマン問題など
事前学修・事後学修
／Preparation and review class		 ● 事前配布する資料には目を通しておくこと．どのような論理で話が展開するのかを頭に入れておくことが望ましい．
● ほぼ毎回の講義で演習とその解説を行うが，講義後に改めて解き直し，理解に努めてもらいたい．
使用教材
／Teaching materials		 資料を配布する．manabaからもダウンロードできるようにする予定である．以下に参考書を示す．
● 今野：ヒラノ教授の線形計画法物語，岩波書店．
● 森，松井：オペレーションズ・リサーチ，朝倉書店．
● 福島：新版 数理計画入門，朝倉書店．
● 山本，久保：巡回セールスマン問題への招待，朝倉書店．
成績評価の方法
／Grading		 筆記試験およびレポートに基づいて評価する．
成績評価の基準
／Grading Criteria		 社会情報学科標準成績評価基準に従う．
履修上の注意事項
／Remarks		 離散数学およびプログラミングに関連した科目を履修していると，学習内容を理解しやすいであろう．特に，「計画科学Ⅰ」と併せて履修することを強く勧める．

【平成29年度以前入学生への注意事項】
・平成30年度より「計画科学（4単位）」は，「計画科学Ⅰ（2単位）」と「計画科学Ⅱ（2単位）」に分割されることとなった．（※学則上は「計画科学」が廃止され，「計画科学Ⅰ」と「計画科学Ⅱ」が新たに開設されたこととなる．）
・平成29年度以前入学生についても「計画科学Ⅰ」「計画科学Ⅱ」を独立した科目とみなして履修可能である．
・ただし，既に「計画科学」を履修済みの学生は「計画科学Ⅰ」及び「計画科学Ⅱ」を履修することはできない．
遠隔授業
／Online class
□ 遠隔授業／Online class
No. 回（日時）
／Time (date and time)		 主題と位置付け（担当）
／Subjects and instructor's position		 学習方法と内容
／Methods and contents		 備考
／Notes
1 1 オリエンテーション
2 2-3 グラフの導入 グラフの基本的な性質，グラフ探索アルゴリズム
3 5-8 ネットワーク最適化問題 最小木問題，最短路問題，最大フロー問題，最小費用流問題
4 9 Python実習 pulp, NetworkX
5 10-13 より難しい組合せ最適化問題 PとNP，厳密解法，近似解法
6 14-15 Python実習 pulp, NetworkX

科目一覧へ戻る