最適化理論２

Optimization Theory 2

9914616

14MAAPM307

胡　艶楠

Yannan HU

2026年度後期

2026年度

②Second semester

火曜3限

Tuesday,  3rd. Period

理学部第一部　応用数学科

Department of Applied Mathematics, Faculty of Science Division Ⅰ

2.00単位

講義

Lecture

-

⑤ [対面]ブレンド型授業/ [On-site] Blended format (must include 50%-or-more classes held on-site)

自然科学・工学・社会科学などのいろいろな分野で発生する組合せ最適化について勉強する．

組合せ最適化（特にネットワーク最適化）を身近な問題を中心に学ぶ．
本学科のディプロマ・ポリシーに定める『グローバル化する社会情勢の中で，解決困難な様々な課題に対し，状況を的確に把握・分析して，自らの数学的・論理的思考力によって柔軟に対応し積極的に問題解決を図る能力』を養成するための科目である．

1．組合せ最適化問題とはどのような問題を指し、実社会のどんな場面で利用されているのかを説明できる．
2．組合せ最適化、特にネットワークに関する最適化を学び、その代表的アルゴリズムを理解し説明できる．また具体的な問題が解けるようになる．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

組合せ最適化問題に対するアルゴリズムを学習するので，プログラミングに関する授業を履修済みであることが望ましい．

小テストの実施　Quiz type test／反転授業　Flipped classroom

-

講義資料を見返して前回の内容を復習し，理解度を深める．
疑問や理解しにくいところがあれば，その要点をまとめておき，授業時に質問する．

毎回課題を出題し，期末テストを実施する．
課題の解答と期末テストの成績により総合的に評価する．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://gomykits.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://gomykits.kinokuniya.co.jp/tokyorika/

[1] 久保幹雄「組合せ最適化とアルゴリズム」（共立出版）
[2] 茨木俊秀 「Cによるアルゴリズムとデータ構造」（オーム社）
[3] 小島政和，土谷隆，水野眞治，矢部博　「内点法」（朝倉書店）

1. イントロダクション
2. グラフ理論-オイラー閉路と最小木-
3. グラフ理論-有向グラフと巡回セールスマン問題 -
4. 計算量とアルゴリズム
5. 線形計画
6. 線形計画(単体法)
7. 双対問題
8. 最短路1（Ford法）
9. 最短路2（Bellman-Ford法,Dijkstra法）
10. グラフ探索アルゴリズム
11. 最大流と最小カット
12. 最小費用流
13. 分枝限定法
14. 多面体的アプローチ
15. Lagrange緩和


本科目は反転授業の形態で行い，講義時間に演習解題を解いて，提出することを求められる．
原則として全授業回数のうち，半数以上の授業回を対面で受講することが求められます．
ただし，残りの半数の授業回を出席しなくてよいことを意図するものではありません．

-

-

-

Y

N