数理最適化法演習(’20)【情報 専門科目】:シラバス概要
■ 講座情報
数理最適化法演習(’20)
【主任講師】
大西 仁(放送大学教授)
【教材・資料】
・インターネット視聴
■ 講義概要
本科目では、決定問題を数理モデルとして定式化して、
計算機で最適解を求める数理最適化法の講義と演習を行う。
決定問題は、工学のみならず、日常生活、経営、
行政等に遍く存在するため、
数理最適化法は多様な領域に応用されている。
数理最適化法の習得には、具体的な決定問題を実際に定式化して、
最適解を計算してみることが有効であることから、
計算機ソフトウェアを使用した演習を行う。
【授業の目標】
数理最適化法の典型的な例題の類題を定式化できるようになること、
および計算機ソフトウェアを用いて最適解を求めることが
できるようになることを目指す。
【履修上の留意点】
表計算ソフトウェアExcelを使用する。
Excelの代わりにLibreOffice Calc、R、Pythonの
いずれかでも受講可能であるが、履修登録に先立ち、
オンライン授業体験版(https://online-open.ouj.ac.jp)の
「数理最適化演習(’20)」の指示に従い、インストールをしておくこと。
放送授業「問題解決の数理(’17)」と関わりが深いが、
この科目単独でも受講可能。
【講義項目】
- 第1回 数理最適化法の概要、および線形最適化法(1):生産計画問題
- 第2回 ソルバーの導入、および線形最適化法(2):食事問題
- 第3回 組み合わせ最適化法:ナップサック問題と資材切り出し問題
- 第4回 線形最適化法(3):輸送問題と割り当て問題
- 第5回 ネットワーク最適化法(1):最短路問題
- 第6回 ネットワーク最適化法(2):最大流問題と最小費用流問題
- 第7回 スケジューリング
- 第8回 やや進んだ技法
■ 講義内容
各講義回の概要とキーワード
第1回 数理最適化法の概要、および線形最適化法(1):生産計画問題
数理最適化法の概要を説明する。
また、代表的な線形最適化問題である生産計画問題の定式化を行う。
■ 【キーワード】
数理最適化問題、数理最適化法、線形最適化問題、生産計画問題
第2回 ソルバーの導入、および線形最適化法(2):食事問題
最適解を計算する計算機ソフトウェア(ソルバー)により
最適解の計算を行う。
また、代表的な線形最適化問題である食事問題を取り上げ、
定式化と最適解の計算を行う。
■ 【キーワード】
ソルバー、線形最適化問題、食事問題
第3回 組み合わせ最適化法:ナップサック問題と資材切り出し問題
実用上重要な組み合わせ最適化問題のうち、
最も単純な例題であるナップサック問題と、
資材切り出し問題を取り上げ、定式化と最適解の計算を行う。
■ 【キーワード】
組み合わせ最適化問題、ナップサック問題、資材切り出し問題
第4回 線形最適化法(3):輸送問題と割り当て問題
線形最適化法の広い適用可能性を示唆する輸送問題と割当問題を取り上げ、
定式化と最適解の計算を行う。
■ 【キーワード】
輸送問題、割当問題
第5回 ネットワーク最適化法(1):最短路問題
ネットワーク構造を持つシステムに関する最適化問題のうち、
代表的問題である最短路問題を取り上げ、
定式化と最適解の計算を行う。
■ 【キーワード】
ネットワーク最適化問題、最短路問題
第6回 ネットワーク最適化法(2):最大流問題と最小費用流問題
最短路問題と並び、
ネットワーク最適化問題の代表的な問題である最大流問題と、
最小費用流問題を取り上げ、定式化と最適解の計算を行う。
■ 【キーワード】
ネットワーク最適化問題、最大流問題、最小費用流問題
第7回 スケジューリング
プロジェクトのスケジューリング問題を線形最適化問題として定式化して、
最適解の計算を行う。
■ 【キーワード】
スケジューリング、プロジェクト、クリティカルパス、PERT/CPM
第8回 やや進んだ技法
線形最適化法、整数最適化法の適用範囲を広げる技法を紹介し、
実用的な問題に適用するためのヒントを与える。
■ 【キーワード】
絶対値の扱い、最大値・最小値の扱い