線性規劃

Abstract

本課程是由交通大學 運輸與物流管理學系提供。

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