シラバス参照

講義概要/Course Information

2020/04/28 現在

科目基礎情報/General Information

授業科目名 /Course title (Japanese)	数理計画法
英文授業科目名 /Course title (English)	Mathematical Programming
科目番号 /Code	INS601c INS601d
開講年度 /Academic year	2020年度	開講年次 /Year offered	3
開講学期 /Semester(s) offered	後学期	開講コース・課程 /Faculty offering the course	情報理工学域
授業の方法 /Teaching method	講義	単位数 /Credits	2
科目区分 /Category	専門科目
開講学科・専攻 /Cluster/Department	Ⅰ類
担当教員名 /Lecturer(s)	村松　正和
居室 /Office	西4-510
公開E-Mail /e-mail	MasakazuMuramatsu@uec.ac.jp
授業関連Webページ /Course website	http://jsb.cs.uec.ac.jp/~muramatu/opt20/
更新日 /Last updated	2020/02/20 12:01:13	更新状況 /Update status	公開中 /now open to public

講義情報/Course Description

主題および 達成目標 /Topic and goals	(a) 主題： 私たちの日常的な行動から，社会活動，経済活動，工学、そして生命・物理現象まで，様々な場面で「最適な方法で＊＊したい」という欲求が現れます．このような「何かを最適にしたい」という問題を意識して、数学的に定式化したものを「数理計画問題」といい、それを解くことを「最適化」といいます。 本講義は、数理計画問題の基本である線形計画問題と、その離散版である整数計画問題を扱います。本講義の目指すところは、それらを解くための最適化アルゴリズムとその背後にある数理について、理解を深めることです。 ２年後期の科目「オペレーションズ・リサーチ基礎」において線形計画問題を学んだ方も多いかと思いますが、本講義では線形計画問題の数理的・理論的側面をより深く学びます。 「オペレーションズ・リサーチ基礎」を履修していなくても理解できるように授業は設計されています。 (b) 達成目標: いろいろな最適化問題の種類の違いを理解すること。 線形計画問題について、その数学的構造および主要なアルゴリズムの一つである単体法について理解すること。 整数計画問題については、線形計画問題との関係を理解すること、基本的な解法を理解すること、そしてソルバーを使えるようになること。
前もって履修 しておくべき科目 /Prerequisites	数値計算、離散数学
前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation	オペレーションズ・リサーチ基礎、グラフとネットワーク、アルゴリズム論第一
教科書等 /Course textbooks and materials	（線形計画法）教科書：「最適化法」 田村明久・村松正和著，共立出版. （整数計画法）特になし
授業内容と その進め方 /Course outline and weekly schedule	(a) 授業内容 １：数理計画問題とは ２：線形計画問題の理論的側面：双対定理 ３：線形計画問題に対するアルゴリズム：単体法 ４：整数計画問題とは ５：整数計画問題の解法 ６：整数計画問題の使用例 (b) 授業の進め方： 最適化、数理計画に関する知識を得るだけではなく、その背後にある論理を自在に操れるようになってほしいと思い、そのように授業を設計しています。最適化は論理の宝庫であり、最適化を適用・応用しようと思ったらどうしてもそういう力が必要となるからです。 そのためには、まずは自分の手を動かすことです。基本的に板書を用いる古いスタイルの授業であり、手でノートを取ってもらいます。さらに、毎回宿題を出します。宿題の達成には毎週２〜３時間程度費やすことになると思われます。わからない場合には、質問時間を取りますので遠慮なく質問してください。少しのアドバイスで、見通しが良くなるものです。 スライドを見て知識を詰め込む授業ではなく、自ら考えたり理解したり説明したりできるようになることを目指す授業ですので覚悟してください。 ただし、限られた授業時間では詳しい証明まで立ち入ることができない場合もあるので、そのときには教科書の該当個所を熟読してください。 下記はとりあえずの計画ですが、実際には学生諸君の理解度を毎回見ながら調節することになるでしょう。 第一回　導入：最適化問題とは 第二回　最適化問題の実行可能性 第三回　線形計画問題の標準形 第四回　双対問題 第五回　双対定理と相補性定理 第六回　様々な双対問題 第七回　単体法 第八回　改訂単体法 第九回　中間試験 第十回　中間試験の解説＆２段階単体法 第十一回　整数計画問題と分枝限定法 第十二回　整数計画問題の応用例１ 第十三回　整数計画問題の応用例２ 第十四回　期末試験 第十五回　期末試験の解説
実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience
授業時間外の学習 （予習・復習等） /Preparation and review outside class	授業は積み重ねの部分が多いので、毎回出席し、宿題を必ず提出することが大切です。週に２〜３時間は宿題に費やしてください。宿題について友人と相談・議論することは構わないし、むしろ推奨します。しかし、理解しないままに他人の回答をコピーしていては試験が通らないでしょう。もし宿題が自分たちだけではできなければ、授業が終わったあとに聞きに来てください。 また、授業だけではなかなか細かい証明などまで説明できないので、授業の後、該当部分の教科書を読んで理解を深めてください。
成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading	(a) 評価方法： 毎回の宿題２０％ 中間試験４０％ 期末試験４０％ (b) 評価基準：以下は最低達成基準である。 任意の線形計画問題について、その双対問題を書けること。 双対定理，単体法を理解していること． 整数計画問題の解法を理解していること。 簡単な問題を整数計画問題として定式化できること。
オフィスアワー： 授業相談 /Office hours	授業の終わりに質問時間を設けるので、まずはそのときに相談してください。それ以外の時間に質問したいときには、メールでアポイントを取ってください。メールでの質問も受け付けます。
学生へのメッセージ /Message for students	私は定刻の数分前に教室へ行き、時刻通りに授業を始めます。いきなり重要な話をすることもあるので、遅刻しないようにしてください。一方、授業自体は定刻より（ときにだいぶ）早く終わります。そのあとは質問タイムですので、何かわからないことがあれば私のところへ来て質問してください。 今年から授業のやり方が変わります。時間をかけて勉強しなければならなくなりますので、そのつもりで来てください。大変かもしれませんが、その分、力もつくと期待しています。
その他 /Others	なし
キーワード /Keyword(s)	オペレーションズ・リサーチ, 最適化問題，線形計画問題，非線形計画問題， 双対性，最適性条件，アルゴリズム.