シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
数理計画法 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Mathematical Programming | ||
| 科目番号 /Code |
INS601c INS601d | ||
| 開講年度 /Academic year |
2021年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
村松 正和 | ||
| 居室 /Office |
西4-510 | ||
| 公開E-mail |
MasakazuMuramatsu@uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://jsb.cs.uec.ac.jp/~muramatu/opt20/（使いません。Google Classroom をみてください） | ||
| 更新日 /Last update |
2021/03/24 15:32:41 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
(a) 主題： 私たちの日常的な行動から，社会活動，経済活動，工学、そして生命・物理現象まで，様々な場面で「最適な方法で＊＊したい」という欲求が現れます．このような「何かを最適にしたい」という問題を意識して、数学的に定式化したものを「数理計画問題」もしくは「最適化問題」といい、それを解くことを「最適化」といいます。 本講義は、数理計画問題の基本である線形計画問題と、その離散版である整数計画問題を扱います。本講義の目指すところは、それらを解くための最適化アルゴリズムとその背後にある数理について、理解を深めることです。 ２年後期の科目「オペレーションズ・リサーチ基礎」において線形計画問題を学んだ方も多いかと思いますが、本講義では線形計画問題の数理的・理論的側面をより深く学びます。 「オペレーションズ・リサーチ基礎」を履修していなくても理解できるように授業は設計されています。 (b) 達成目標: いろいろな最適化問題の種類の違いを理解すること。また各種最適化問題への定式化に関する基本を身につけること。 線形計画問題について、その数学的構造および主要なアルゴリズムの一つである単体法について理解すること。 整数計画問題については、線形計画問題との関係を理解すること、基本的な解法を理解すること、そしてソルバーを使えるようになること。 |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
数値計算、離散数学 |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
オペレーションズ・リサーチ基礎、グラフとネットワーク、アルゴリズム論第一 |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
（線形計画法）教科書：「最適化法」 田村明久・村松正和著，共立出版. （整数計画法）特になし |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
(a) 授業内容 １：数理計画問題とは ２：線形計画問題の理論的側面：双対定理 ３：線形計画問題に対するアルゴリズム：単体法 ４：整数計画問題とは ５：整数計画問題の解法 ６：整数計画問題の使用例 (b) 授業の進め方： 最適化、数理計画に関する知識を得るだけではなく、その背後にある論理を自在に操れるようになってほしいと思い、そのように授業を設計しています。最適化は論理の宝庫であり、最適化を適用・応用しようと思ったらどうしてもそういう力が必要となるからです。 そのためには、まずは自分の手を動かすことです。毎回課題を出します。課題の達成には毎週２〜３時間程度費やすことになると思われます。わからない場合には、質問時間を取りますので遠慮なく質問してください。少しのアドバイスで、見通しが良くなるものです。 対面授業の回とZoom を用いたリアルタイム授業の回、オンデマンドの回を混合しようと考えています。それぞれどのくらいの割合になるのかは未定です。Zoom に関しては見そびれた人のために録画も提供しますが、なるべくリアルタイムで参加してください。 内容は以下のとおりです。（それぞれが一回の授業というわけではありません。） 1. 最適化問題とは 2. 標準形の線形計画問題とブロック行列表示 3. 双対問題 4. 諸定理 5. ネットワーク問題とその双対 6. 単体法 7. 中間試験 8. 改訂単体法、双対単体法 9. 多面体 10. ネットワーク問題 11. 整数計画問題 12. 分枝限定法 13. 分枝カット法 14. 期末試験 15. 期末試験の振り返り |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
授業は積み重ねの部分が多いので、毎回出席し、課題を必ず提出することが大切です。週に２〜３時間は課題に費やしてください。課題について友人と相談・議論することは構わないし、むしろ推奨します。しかし、理解しないままに他人の回答をコピーしていては試験が通らないでしょう。もし課題が自分たちだけではできなければ、Zoom 授業が終わったあとに聞いてください。 また、授業だけではなかなか細かい証明などまで説明できないので、授業の後、該当部分の教科書を読んで理解を深めてください。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
(a) 評価方法： 毎回の宿題０％ 中間試験５０％ 期末試験５０％ （ただし、どちらか一方でも対面による試験が不可能となった場合には、毎回の宿題の割合を上げることがある。） (b) 評価基準：以下は最低達成基準である。 任意の線形計画問題について、その双対問題を書けること。 双対定理，単体法を理解していること． 整数計画問題の解法を理解していること。 簡単な問題を整数計画問題として定式化できること。 |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
授業の終わりに質問時間を設けるので、まずはそのときに相談してください。それ以外の時間に質問したいときには、Google Classroom でお願いします。 |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
昨年は全部遠隔授業でしたが、今年は少しでも対面授業を取り入れたいと考えています。いずれにしても、時間をかけて勉強しなければわかるようになりません。大変かもしれませんが、その分、力もつくと期待しています。 |
| その他 /Others |
特になし None |
| キーワード /Keywords |
オペレーションズ・リサーチ, 最適化問題，線形計画問題，非線形計画問題， 双対性，最適性条件，アルゴリズム. |