科目ナンバー

SG-IG5-8C41

履修条件・関連科目等

線形計画法の基本知識があることが望ましい。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

実社会の問題の多くは離散的な条件や決定を含む。したがって、これらの問題を最適化問題として扱うためには、組合せ最適化に関する技術が重要となる。講義では整数計画問題に焦点を当て、組合せ最適化問題の解法について理論と実用の両面から講義する。さらに、実際に解法をプログラミングすることで、その性能について理解を深める。

科目目的

組合せ最適化問題に関する基礎的な知識を身につけ、組合せ最適化問題へのモデル化、およびそれを解く手法の習得を目標とする。

到達目標

整数計画問題によるモデリングを習得し、組合せ最適化問題を解くプログラムを構築する技術を身につける。

授業計画と内容

第1回 組合せ最適化問題の紹介
第2回 線形計画問題と整数計画問題
第3回 双対理論
第4回 完全単模性と線形計画問題の整数性
第5回 最大マッチング・最小被覆定理
第6回 整数計画問題の解法：分枝限定法
第7回 整数計画問題の解法：釘付けテスト
第8回 整数計画問題の解法：切除平面法
第9回 巡回セールスマン問題の定式化と持ち上げ操作
第10回 巡回セールスマン問題に対する最小1-木緩和
第11回 巡回セールスマン問題に対する分枝切除法
第12回 機械スケジューリング問題の紹介
第13回 機械スケジューリング問題の解法
第14回 最適化ソフトウェアの紹介

授業時間外の学修の内容

その他

授業時間外の学修の内容（その他の内容等）

授業中に適宜演習を行うので、解けなかった問題を復習する。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

資料を配布する。
参考書：森雅夫，松井知己 著「オペレーションズ・リサーチ」（朝倉書店，2004年発行，4,620円）

その他特記事項

参考URL