|
1
|
| 授業計画/Class |
【オンライン（オンデマンド型）】全体説明，線形計画(LP)とは- 目的関数，制約条件
線形計画とは何かを，例を用いて学ぶ．
教科書 3-16 Chapter 1 Introduction
|
|
|
2
|
| 授業計画/Class |
単体法1: 例題と標準形
線形計画の具体的な問題例を用いて，単体法を実行するための標準形を学ぶ．
教科書 13-28
Chapter 2 Simplex method,
2.1 An Example,
2.2 The Simplex Method,
2.3 Initialization,
2.4 Unboundedness,
2.5 Geometry |
|
|
3
|
| 授業計画/Class |
単体法2: 辞書表現とアルゴリズム
LPを辞書表現する方法と，そこから単体法のアルゴリズムを実行する方法を学ぶ．
教科書 29-44 Chapter 3 Degeneracy,
3.1 Definition of Degeneracy,
3.2 Two Examples of Degenerate Problems,
3.3 The Perturbation/Lexicographic Method,
3.4 Bland's Rule,
3.5 Fundamental Theorem of Linear Programming
|
|
|
4
|
| 授業計画/Class |
単体法3: 退化と双対理論
線形計画問題における退化と双対理論を学ぶ
教科書 39-57
Chapter 3 Degeneracy,
3.6 Geometry,
Chapter 5 Duality Theory,
5.1 Motivation - Finding Upper Bounds
5.2 The Dual Problem |
|
|
5
|
| 授業計画/Class |
双対問題
LPの具体的な問題例を用いて，双対問題の導入を行う．さらに，双対定理と相補性を学ぶ
教科書 58-68, 73-74
Chapter 5 Duality Theory,
5.3 The Weak Duality Theorem,
5.4 The Strong Duality Theorem,
5.5 Complementary Slackness,
5.8 The Dual of a Problem in General Form |
|
|
6
|
| 授業計画/Class |
双対問題 3 : 双対定理と相補性
線形計画問題における双対定理と，ラグランジュ双対を学ぶ。
教科書 74-79, 91-96
Chapter 5 Duality Theory,
5.9 Resource Allocation Problems,
5.10 Lagrangian Duality |
|
|
7
|
| 授業計画/Class |
行列表記による単体法
行列表記を用いた単体法の表現を学ぶ
教科書 89-96
Chapter 6 The Simplex Method in Matrix Notation,
6.1 Matrix Notation,
6.2 The Primal Simplex Method
|
|
|
8
|
| 授業計画/Class |
行列形式での線形計画問題と単体法の表現
行列を用いた線形計画問題と単体法の表現を学ぶ
教科書 96-105
Chapter 6 The Simplex Method in Matrix Notation,
6.3 An Example,
6.4 The Dual Simplex Method,
6.5 Two-Phase Methods |
|
|
9
|
| 授業計画/Class |
線形計画問題 - 演習
第8回までに学んだ範囲の演習を実施する。 |
|
|
10
|
| 授業計画/Class |
混合整数計画問題
線形計画問題に整数条件を課した混合整数計画問題の定式化を学ぶ
教科書 385-386, 390-392
Chapter 23 Integer Programming,
23.1 Scheduling Problems,
23.3 Fixed Costs,
23.4 Nonlinear Objective Functions |
|
|
11
|
| 授業計画/Class |
分枝限定法 1
混合整数計画問題を例として，分枝限定法の考え方を学ぶ
教科書 392-404,
Chapter 23 Integer Programming,
23.5 Branch-and-Bound |
|
|
12
|
| 授業計画/Class |
分枝限定法2
整数計画問題に対して具体的に分枝限定法を適用する方法を学ぶ
教科書 392-404,
Chapter 23 Integer Programming,
23.5 Branch-and-Bound |
|
|
13
|
| 授業計画/Class |
巡回セールスマン問題
巡回セールスマン問題とは何かを学ぶ
教科書 387-389
Chapter 23 Integer Programming
23.2 The Traveling Salesman Problem |
|
|
14
|
| 授業計画/Class |
計算機によるプログラミング
線形計画問題・整数計画問題を計算機によって解く方法を学ぶ |
|
|
15
|
|
| |
| 事前学習/Preparation |
教科書の予定範囲の内容を理解する。 |
| 事後学習/Reviewing |
学習範囲の内容の理解に不十分な点があれば，復習をして理解する。 |
|