標題: 線性規劃
Linear Porgramming
作者: 方述誠
Open Education Office
開放教育推動中心
公開日期: 2010
摘要: 本課程是由交通大學 運輸與物流管理學系提供。



This course provides the fundamental understanding to the theory and algorithms of linear optimization. It involves mathematical analysis, theorem proving, algorithm design and numerical methods.



本課程為方述誠老師應邀授課,授課內容與課程大綱稍有不同。
課程目標/概述
This course provides the fundamental understanding to the theory and algorithms of linear optimization. It involves mathematical analysis, theorem proving, algorithm design and numerical methods. 

本錄影課程為方述誠老師應邀授課,授課內容與課程大綱稍有不同。

課程章節




課程章節

單元主題


第一週


Examples of LP problems
Mastering LP 


第二週


Basic terminologies
Hyperplanes, halfspaces, and polyhedral sets
Affine sets, convex sets, and cones
Extreme points and basic feasible solutions

第三週


Nondegeneracy and adjacency
Resolution theorem for convex polyhydrons
Fundamental theorem of linear programming


第四週


Elements of iterative scheme
Basics of the simplex methods
Algebra of the simplex method

第五週


Starting the simplex method
Degeneracy and cycling
The revised simplex method

第六週


Midterm Examine

第七週


Chinese Memorial Day

第八週


Dual linear program
Duality theory

第九週


Complementary slackness and optimality conditions
An economic interpretation of the dual problems

第十週


The dual simplex method
Sensitivity analysis

第十一週


The primal dual simplex method

第十二週


Midterm Examine 

第十三週


Primal affine scaling algorithm

第十四週


Dual affine scaling algorithm

第十五週


Primal-Dual affine scaling algorithm

第十六週


Moving along different algebraic paths
Extensions of algebraic paths

第十七週


Geometric interpretation of the moving directions 

第十八週


Final examine

課程書目

Shu-Cherng Fang and Sarat Puthenpura, Linear Optimization and Extensions: Theory and Algorithm, Prentice Hall International Edition, New York, 1994.

評分標準



項目
百分比



作業
20%



第一次考試
25%



第二次考試

25%

第三次考試

30%
授課對象:研究所學生
預備知識:Matrix Theory、Linear Algebra
URI: http://ocw.nctu.edu.tw/course_detail.php?bgid=3&nid=245
http://hdl.handle.net/11536/108446
顯示於類別:開放式課程