シラバス
授業科目名 | 年度 | 学期 | 開講曜日・時限 | 学部・研究科など | 担当教員 | 教員カナ氏名 | 配当年次 | 単位数 |
---|---|---|---|---|---|---|---|---|
組合せ最適化特論 | 2025 | 前期 | 月2 | 理工学研究科博士課程前期課程 | 髙松 瑞代 | タカマツ ミズヨ | 1年次配当 | 2 |
科目ナンバー
SG-IG5-8C41
履修条件・関連科目等
線形計画法の基本知識があることが望ましい。
授業で使用する言語
日本語
授業で使用する言語(その他の言語)
授業の概要
実社会の問題の多くは離散的な条件や決定を含む。したがって、これらの問題を最適化問題として扱うためには、組合せ最適化に関する技術が重要となる。講義では整数計画問題に焦点を当て、組合せ最適化問題の解法について理論と実用の両面から講義する。さらに、実際に解法をプログラミングすることで、その性能について理解を深める。
科目目的
組合せ最適化問題に関する基礎的な知識を身につけ、組合せ最適化問題へのモデル化、およびそれを解く手法の習得を目標とする。
到達目標
整数計画問題によるモデリングを習得し、組合せ最適化問題を解くプログラムを構築する技術を身につける。
授業計画と内容
第1回 組合せ最適化問題の紹介
第2回 線形計画問題と整数計画問題
第3回 双対理論
第4回 完全単模性と線形計画問題の整数性
第5回 最大マッチング・最小被覆定理
第6回 整数計画問題の解法:分枝限定法
第7回 整数計画問題の解法:釘付けテスト
第8回 整数計画問題の解法:切除平面法
第9回 巡回セールスマン問題の定式化と持ち上げ操作
第10回 巡回セールスマン問題に対する最小1-木緩和
第11回 巡回セールスマン問題に対する分枝切除法
第12回 機械スケジューリング問題の紹介
第13回 機械スケジューリング問題の解法
第14回 最適化ソフトウェアの紹介
授業時間外の学修の内容
その他
授業時間外の学修の内容(その他の内容等)
授業中に適宜演習を行うので、解けなかった問題を復習する。
授業時間外の学修に必要な時間数/週
・毎週1回の授業が半期(前期または後期)または通年で完結するもの。1週間あたり4時間の学修を基本とします。
・毎週2回の授業が半期(前期または後期)で完結するもの。1週間あたり8時間の学修を基本とします。
成績評価の方法・基準
種別 | 割合(%) | 評価基準 |
---|---|---|
レポート | 80 | 与えられた問題を整数計画問題として定式化することができ、整数計画問題の基本的な解法を構築することができるかを評価する。 |
平常点 | 20 | 出席および講義中の提出物により評価する. |
成績評価の方法・基準(備考)
課題や試験のフィードバック方法
授業時間内で講評・解説の時間を設ける
課題や試験のフィードバック方法(その他の内容等)
アクティブ・ラーニングの実施内容
実施しない
アクティブ・ラーニングの実施内容(その他の内容等)
授業におけるICTの活用方法
実施しない
授業におけるICTの活用方法(その他の内容等)
実務経験のある教員による授業
いいえ
【実務経験有の場合】実務経験の内容
【実務経験有の場合】実務経験に関連する授業内容
テキスト・参考文献等
資料を配布する。
参考書:森雅夫,松井知己 著「オペレーションズ・リサーチ」(朝倉書店,2004年発行,4,620円)