最適化手法(2014年度)
テキスト
初回を除き, 講義時に配布しませんので, 各自ダウンロードして下さい.
スライド資料の印刷に際しては割り付け印刷や両面コピーなどにより, 紙資源の節約を心がけましょう.
- 第1回(4/9) ガイダンス、LPとIPの図解法 [スライド][演習問題](初回配布) [4/8]
- 第2回(4/16) IPによるモデリング [スライド][演習問題][4/15]
- 第3回(4/23) 緩和問題とその威力 [スライド][演習問題][4/21; 4/23(スライド修正版)]
- 第4回(4/30) 分枝限定法 [スライド][演習問題][4/23]
- 第5回(5/7) 切除平面法 [スライド][演習問題][5/3]
- 第6回(5/14) ネットワークによるモデリング [スライド][演習問題][5/7]
- 第8回(5/28) 最短路問題 [スライド][演習問題][5/26]
- 第9回(6/4) 最大流問題 [スライド][演習問題][6/2]
- 第10回(6/11) 最大流問題の応用(1) [スライド][演習問題][6/10]
- 第12回(6/25) 最大流問題の応用(2) [スライド][演習問題][6/24]
- 第13回(7/2) 最小費用流問題 [スライド][演習問題][7/1]
- 第14回(7/9) 最小費用流問題の応用(1) [スライド][演習問題][7/7]
- 第15回(7/16) 最小費用流問題の応用(2) [スライド][7/10](演習問題はありません)
本年度「最適化手法」の講義資料ならびに演習問題の多くは、電気通信大学岡本吉央先生が2013年度「最適化手法」をご担当された際に作成、使用されたものを、後藤が適宜改編の上、使用しています。快く使用を認めていただきました岡本先生に感謝申し上げます。なお、本年度資料の誤りは後藤に帰します。誤りなどのご指摘は後藤まで連絡してください。
お知らせ
- [4/23]第3回スライドp.28のナップサック問題の制約を修正しました。(授業中に訂正を指示した部分です。追加の修正はありません。)
- [5/9]第7回(5/21)は中間試験1です.教室は5335教室です(いつもの教室と異なるので要注意).13時00分に着席しているようにしてください.通路に沿うように座り(島の中央には座らず),前方から詰めて座ってください.出題範囲は第1回から第5回までの整数計画法です.資料の参照(持ち込み)は不可です.
- [6/4]第11回(6/18)は中間試験2です.教室は5335教室です(いつもの教室と異なるので要注意).13時00分に着席しているようにしてください.通路に沿うように座り(島の中央には座らず),前方から詰めて座ってください.出題範囲は第6回から第10回までの(ただし第7回は除く)ネットワーク最適化です.資料の参照(持ち込み)は不可です.
参考資料
【Windows版 LPSolveについて】windows版LPSolveについては下記のサイトからダウンロードできます。
情報については適当に検索しましょう.
【EXCELソルバーについて】EXCELソルバーの使い方を忘れてしまった人は以下を参考にして下さい.
【Windows版 gnuplotについて】windows版gnuplotについては下記のサイトからダウンロードできます。
情報については適当に検索しましょう.
【質問・感想】
第3回(4/23)
- 問題3.2が難しかったです。
-->難しいくらいが丁度よいと思います。問題は3.2は問題3.1と違い、単に手順をなぞるだけでなく、本質を理解しているかを問うている問題と言えます。
- ウェブ上に解答を載せて頂けると嬉しいです。-->初回に言ったとおり、模範解答のようなものは存在しません。逆に、毎回毎回の授業を確実に理解していくという緊張感を持ってもらえればというのが狙いです。もちろん、考え方が正しいかどうかわからない・どこから考えればいいかわからないといった場合には、質問してください。
第1回(4/9)
- 1, 2年の復習ができてよかった。
-->次回以降は今回の内容をベースに新しいことを説明していきます。
- 今日はこれまでにやった部分の復習といった感じで、あまり新鮮味がなかったので、次回以降の新しい内容を早く身につけたい。
-->一応、整数計画法の図解法あたりは新しい内容だったと思うのですが...。少し授業のスピードが遅く思えるのかもしれません。授業ではそれぞれの方法の入門的なところしか扱えません。もしより深く、新しいことを学びたい場合には相談してください。適当な教科書を紹介したいと思います。
- 今日の授業を通して今までの復習が出来て良かった。
-->是非復習・予習をお忘れなく。
- LPの問題などの解き方は覚えていたが、用語や単体法などのやり方を忘れてしまっていたので、復習に多くの時間を使う必要がありそうです。
-->短期記憶を長期的な記憶、もしくは、「感覚的にわかる」状態にするには、授業以外の学習が必要だと思います。テキストを理解して、友達などに説明するような機会(輪読といいます)などをすると、どこがわかっていて、どこがわかっていないかが明確になるのでお奨めです。
- 復習のところで法線ベクトルを用いた最適解を求める考え方は知らなかったので基本となることも授業内で少しずつ説明していただけるとありがたいです。
-->授業ではなるべく前へ前へ(新しいことを)扱うのを第一義としています。とはいえ、多くの人が知らないor忘れている基礎知識があれば、適宜補いたいと思いますが、そこはバランスの問題になるかと思います。もし皆さんにとって未知の概念であることを、私が気づいていないようであれば、状況に応じて対策を提案します(ので、その場合は教えてください)。
- 復習の解説もわかりやすく、面白かったです。今後も頑張ります。
-->是非頑張ってください。是非、予習・復習など授業時間外の学習時間も確保してください。また、参考書として挙げたテキストを参考にするなどして、より専門的な学習ができるとなおよいと思います。
- 今日の講義を聞いて、LPなどの問題の解く手順を昔よりもイメージすることができた。最適解を求める際に法線ベクトルを用いていることは知らなかった。
-->実は、LPより一般的な最適化問題である非線形計画法では、法線ベクトルの概念が多用されます。
- 最適化手法はORの延長上であるので、非常に興味ある授業だった。
-->最適化手法は、たくさんあるORの道具立ての1つですが、インパクトという点で、応用の範囲が最も広いと言えると思います。色々な方法論に興味がある人は、より網羅的な教科書、たとえば、洋書なら Hillier, LiebermanのIntroduction to Operations Research, 和書なら森,松井「オペレーションズ・リサーチ」(朝倉書店)などを読むなどして、各自で学習を進めることもお勧めします。(特に、前者は演習問題も豊富です。)
- OR第2は、他の先生だったのですが、やっぱり後藤先生の方が落ち着きます。P.S.フロリダでの大学の話を聞きたいです。現在留学を考えているので、受け入れ大学を紹介して欲しいです!
-->正直、私自身は学生として留学したわけではないので、詳しくは分かりません。一番簡単なものでは大学が交流協定を締結している大学との交換留学や短期留学制度があります。これらについては履修要項を参照して、しかるべき窓口に相談するとよいと思います。