課程名稱 |
環境系統最佳化與網流分析 Optimization and network flows for environmental systems |
開課學期 |
109-1 |
授課對象 |
生物資源暨農學院 生物環境系統工程學系 |
授課教師 |
胡明哲 |
課號 |
BSE5168 |
課程識別碼 |
622 U5240 |
班次 |
|
學分 |
3.0 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期四2,3,4(9:10~12:10) |
上課地點 |
農工九 |
備註 |
總人數上限:30人 |
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1091BSE5168_ |
課程簡介影片 |
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
The course addresses optimization and network flows. Both the general theory and characteristics of these optimization problems as well as effective solution algorithms are presented. The course is organized into three parts: linear programming, network flows, and nonlinear programming. The linear programming part consists of simplex methods, optimality conditions, and duality. The part on network flows deals with minimal cost, transportation, assignment, maximal flow, shortest path, and multicommodity flow problems. Nonlinear programming part discusses unconstrained optimization, and penalty and barrier functions. |
課程目標 |
(1) Linear algebra, convex analysis, polyhedral sets, and the simplex methods
(2) Optimality conditions
(3) Duality and sensitivity analysis
(4) Minimal cost network flows
(5) The transportation and assignment problems
(6) Maximal flow, shortest path, multicommodity flow
(7) Unconstrained optimization
(8) Penalty and barrier functions |
課程要求 |
Midterm exam
Homework
Final project |
預期每週課後學習時數 |
|
Office Hours |
|
指定閱讀 |
待補 |
參考書目 |
Linear Programming and Network Flows/ Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali
Nonlinear Programming: Theory and Algorithms/ Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty |
評量方式 (僅供參考) |
|
週次 |
日期 |
單元主題 |
第1週 |
9/17 |
Introduction |
第2週 |
9/24 |
Linear algebra, convex analysis, polyhedral sets, and the simplex methods (I) |
第3週 |
10/01 |
*** National Holiday (No class) |
第4週 |
10/08 |
Linear algebra, convex analysis, polyhedral sets, and the simplex methods (II) [** Presentation: 3.7 Simplex method] |
第5週 |
10/15 |
Optimality conditions [** Presentation: 5.4 The KKT optimality conditions] |
第6週 |
10/22 |
Duality and sensitivity analysis [** Presentation: 6.2 Primal-dual relationships] |
第7週 |
10/29 |
Dual simplex method [** Presentation: 6.5 Dual simplex method] [PuLP: https://coin-or.github.io/pulp/CaseStudies/a_blending_problem.html] |
第8週 |
11/05 |
Minimal cost network flows (I) [** Presentation: 9.5 Simplex method for network flow problems] |
第9週 |
11/12 |
*** Midterm week (NO class) |
第10週 |
11/19 |
Minimal cost network flows (II) |
第11週 |
11/26 |
The transportation and assignment problems (I) [Presentation: Python PuLP solver] |
第12週 |
12/03 |
The transportation and assignment problems (II) [** Presentation: 10.7 Assignment problem: (Kuhn's) Hungarian algorithm] |
第13週 |
12/10 |
Maximal flow, shortest path, multicommodity flow [** Presentation: 12.2 Shortest path problem] |
第14週 |
12/17 |
Unconstrained optimization (I) |
第15週 |
12/24 |
Unconstrained optimization (II) [** Presentation: 13.6 Newton's method] |
第16週 |
12/31 |
Penalty and barrier functions (I) [** Presentation: 14.5 Penalty and barrier methods] |
第17週 |
1/07 |
Penalty and barrier functions (II) [** Presentation: 14.3-14.4 Lagrange multiplier methods, KKT optimality conditions] [** Presentation: 14.7 Quadratic programming methods] |
第18週 |
1/14 |
*** Final project |
|