【授業の目的】
自然科学、数理情報科学分野のみならず、計量・数理社会科学分野にも広く用いられる数理最適化の基礎理論を学ぶ。 数理最適化の基礎理論を、数理計画法、とりわけ線形計画法とその主要なクラスであるネットワーク計画問題を中心に講義する。時間があれば、非線形計画法の概略についても触れるつもりである。
【授業の到達目標】
線形計画法の基礎理論と計算法(単体法)を習得し、ネットワーク計画法に関する主要な組合せ最適化問題のアルゴリズムを理解出来るようになること。
【授業概要(キーワード)】
数理最適化問題 線形計画法 線形計画問題の双対定理 単体法 ネットワーク計画法 組合せ最適化問題 最短路問題 最大流問題 最大流最小カットの定理 最小費用流問題 アルゴリズムと計算量 非線形計画法 クーン・タッカー条件 学生主体型授業
【学生主体型授業(アクティブラーニング)について】
A-1.ミニッツペーパー、リフレクションペーパー等によって、自分の考えや意見をまとめ、文章を記述し提出する機会がある。:76~100% B-1.学生同士の話し合いの中で互いの意見に触れる機会がある。:76~100% C-1.自分の意見をまとめて発表する機会がある。:76~100% D-1.演習、実習、実験等を行う機会がある。:76~100% A-2.小レポート等により、事前学習(下調べ、調査等含む)が必要な知識の上に思考力を問う形での文章を記述する機会がある。:76~100% D-2.事前学習(下調べ、調査等含む)で習得した知識等を踏まえて演習、実習、実験等を行う機会がある。:76~100%
【科目の位置付け】
この授業は,情報科学に関する基本的知識と発展的事項として、線形計画法の計算・アルゴリズムを理解する力を身につけるものである(理学部理学科カリキュラム・ポリシー(学生便覧参照)。)
【SDGs(持続可能な開発目標)】
04.質の高い教育をみんなに 09.産業と技術革新の基盤をつくろう
【授業計画】
・授業の方法
主として講義形式で行うが、能動的学習を促すため、各回につき、講義内容の理解に必要な演習問題を学生に解かせる時間を設けることにより、学生主体型授業を展開する。
・日程
第1回 線形計画問題とは何か 第2回 標準形と正準形 第3回 基底形式 第4回 基底解 第5回 単体法とは何か 第6回 単体法の解き方 第7回 巡回とブランドのルール 第8回 幾何学的解釈 第9~10回 線形計画法の双対定理 第11回 ネットワーク計画法その1:最短路問題 第12回 ネットワーク計画法その2:最大流問題 第13回 ネットワーク計画法その3:最小費用流問題 第14~15回 非線形計画法の基礎理論
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
授業中理解できなかったところはそのままにせず、授業後に質問などを行い、理解の捕捉に努めること。
・授業時間外学習(予習・復習)のアドバイス
1)自主的な学修時間の目安は4時間/週です。(注)大学設置基準で、1単位の授業科目は45時間の学修を必要とする内容をもって構成することが標準と定められています。 2)授業の進捗状況に応じて、適宜講義の最後に宿題を出しますので、出された週の翌週までに、これを完成させ、授業内容の理解を深めるように努力して下さい。
【成績の評価】
・基準
期末試験と授業中に実施する演習及び宿題の得点を合算して評価得点を算出し,それをもとに評価を決定します.
・方法
期末試験 60% + 授業中に実施する演習及び宿題 40% として評価する。
【テキスト・参考書】
授業の初日と、その後の進展に沿って数種類の本を紹介する。 テキスト:一森 哲男 著「数理計画法」共立出版株式会社 参考書:田村 明久・村松 正和 著「最適化法」共立出版株式会社 参考書:今野 浩 著「線形計画法」日科技連 参考書:並木 誠 著「線形計画法」朝倉書店
【その他】
・学生へのメッセージ
基本的なところから地道にコツコツと学習を積み重ねることが重要である。
・オフィス・アワー
感染拡大防止の観点から、まず、webclssなどを利用し、メールによるコンタクトを取って下さい。 随時オンラインにより、対応致します。
(これはコロナ禍以前の記載内容です。)授業時間外に学生の質問に答える「オフィスアワー」を佐久間研究室(地域教育文化学部2号館4階システム情報資料室Ⅲ)において、水曜日の18時00分から20時00分までとしますが、これに限らず在室している時は随時対応します。
|