最佳化導論

• 課程重點

這課程包含完整的講稿和複習課，和一些延伸Microsoft® Excel功能的工具。.

 

• 技術需求

建議使用Microsoft® Excel software開啟並瀏覽課程的 .xls檔案。免費的Microsoft® Excel  viewer software可以觀看 .xls檔案。任何軟件都可以讀取課程網頁的.dll檔案，這些檔案都可以執行。特定指示或建議請參考課程教材。

 

教學大綱

• 主題描述和目標

15.053是最佳化的理論和實踐的學士生課程，學習最佳化模組廣泛應用於運輸、後勤、生產、電腦科學、電子商務、項目管理、財務和許多其他領域。這科目研究一些最佳化的應用，並提出在線性規劃、網絡流，動態規劃、整數規劃和決策樹的演算法和理論。

概述一門課程，方法之一是敘述每一課的內容，或是敘述課程使用的方法。我們列出每一課的內容，但現在先通盤介紹幾個主題。

15.053課程的主題

最佳化處處都在：我們展示最佳化的廣泛應用，範圍包含維運管理、財務、市場行銷、工程、策略規劃、以及大學運作和個人決策模式。我們呈現最佳化的多個模式和概念框架，包括線性規劃、整數規劃、決策樹及動態規劃。

演算法：麻省理工學院的傳統是學習演算法的內部運作，不能只是說Excel的演算功能解答線性規劃，我們必須知道演算是如何運作。學習演算法有幾個重要的意義。第一，有些問題是容易解答，但有些問題本質上是非常難處理。學習演算法有助分辨兩者，並知道計算的難度從何而來。第二，了解演算法行為是重要的一步，以解讀和應用演算結果，進一步了解最佳化問題。第三，只有了解演算法的內部運作，才可以設計我們本身的演算法，或修改現有的演算法。

模型的目標是洞識，不是數字：我們建立模型，不是反映現實，只是反映現實的部份。〈管理科學和運籌學〉的模型，本質上是近似現實以支援決策。模型支援決策，一個有用方法是這容許管理人員探討不同的情景，有助了解在某些假設下，那些決策是紮實的。同樣可以分析模型以決定那些數字是重要，那些數字即使改變也幾乎不會影響決定。幫助洞識的主要理論工具是敏感度分析及其多種變體。要提出警告：許多電子商務的應用要在短時間內解答千百種模型，人力根本沒時間評估模型的結果，因此需要設計出紮實和可信賴的模型。

效果保證：最佳化（以及數學規劃）其中一個標誌就是提供最佳解決方案，同時有最佳化的簡潔保證。就算本質是艱難的問題，以最佳化為基礎的技術可能提供一些保證。尤其有用的保證就是與最佳化保持最大的相對距離。

 

• 教材

必備課本

Winston, Wayne.《運籌學：應用與演算》Operations Research: Applications and Algorithms. Boston, MA: Duxbury Press, 1994. ISBN: 0534209718。

（除決策分析的資料外，以下書本有課程所需的所有資料。可以買較便宜的二手書。）

Winston, Wayne and Munirpallam Venkataraman.《數學規劃導論：應用與演算》 Introduction to Mathematical Programming - Applications and Algorithms. Boston, MA: Duxbury Press, 2002. ISBN: 0534359647.)

其他教材有課堂筆記、閱讀資料和試算表。所有試算表要用Excel，有些要用Excel Solver。

 

• 期中考、複習課、小考、成績和問題集

有兩次期中試。第二次期中考的範圍是第一次期中考之後的範圍。期末考包含決策樹、動態規劃、線性規劃及整數規劃的模型。期末考範圍不包含全部。期中及期末試是閉卷試。

必須出席星期五的複習課，大多數有10分鐘的小考，成績是期末總分2%。小考包含當周課程的基本內容，以及一兩項與上星期作業有關的基本練習。這樣的設計，有上課（或熟悉內容）和熟悉之前的作業，都會取得優異成績。

評分

成績計算方式如下：

事項（比重）

作業（25%，每份2.5%）

第一次期中考（19%）

第二次期中考（19%）

每週小考（16%，每次2%）

其他成績（最多5%）

期末考（21%）

 

每週都有6至8題作業，每份作業佔2.5分，作業評分根據以下方式轉換為2.5的等級：

作業成績（轉換為）

85% 至100%(25)

75% 至84%(2)

60% 至74%(1.5)

50% 至59%(1)

49% 或 較少(0)

 

作業評分的目的：

鼓勵學生做好作業 學生做作業時可請教他人，但不是「過多的請教」。

尤其，我們不想獨立做作業的學生受到變相懲罰。

 

作業必須以書面方式繳交，不可使用電子檔案。

學生請緊記，不繳交任何作業等同每次期中考中失去62.5分。不出席任何一次複習課的小考等同每次期中考失去40分。

評分人員和（或）助教會對評分所有作業，每個問題都給出答案。

 

加分題

每份作業有一兩題特別困難的加分題，可選答，並且計分。但是，即便不選答這些問題也可以拿滿分2.5分。這些問題是提供給專注和希望更深了解運籌學的學生。期末評分時，回答加分題對評級邊緣的學生有幫助，也有助決定誰可拿到A+。

其他加分

在這個學期，學生有機會可以完成一個小型項目，有額外5分。請與助教連絡。加分項目的一些建議如下：

1. 製作短片

（兩至四位學生成一組）製作一兩套短片，各約1至2分鐘，可稱之為「最佳化的一分鐘」。短片是關於學生認為15.053課程吸引興趣的題材和學習經驗，說明運籌學的應用或重要的技術觀點。（鼓勵幽默，但不要過火，免得將來在班上放映時尷尬。）短片放在你的網站，別的網站也可以串流播放。

 

2. 作業出題

（獨自或兩位學生協作）。創作3至5條吸引學生的習題，日後也適用於家課，可能包括加分題或試算表練習。

 

3.有創意的項目設計

（二至四位學生）決定一個有趣的方法在實際情況中應用「最佳化」，說明應如何利用。提供問題的背景資料，決定要收集那些數據，你認為有什麼限制，以及什麼需要「最佳化」。盡可能不多於3頁。 

作業遲交規定

作業應在指定日期上課前繳交。可以親自在堂上遞交，或以電子檔傳給助教，或是交給Orlin教授的助理。不接受遲交功課，但整個學期可以有一份作業在過期24小時內繳交，但必須附上遲交的理由。

 

獨自和小組作業規定

學生可以選擇結伴以合作方式完成作業。除了和夥伴分享，學生不得與他人分享答案，也不可以抄襲他人或上一學期的答案。抄答案一律0分。

網站資源

James B. Orlin的網頁

The MIT Operations Research Center. MIT運籌學中心網址．重點是研究生項目。

 

運籌學的資訊

The page formerly known as Mike Trick's.以前稱為Mike Trick的網頁，很多很棒的資料！

INFORMS.〈運籌與管理科學學院〉．是最多人訪問的運籌學網站。

Operations Research Links..網站由OpsResearch.com維護．

The Student Union〈運籌與管理科學學院學生會〉立志成為服務運籌學和管理科學及相關領域的學生和研究生的最佳網站．盡可能滿足網路上最重要的需要。

What is Operations Research? 〈什麼是運籌學〉網站由美國勞工部維護，描述運籌學這行業和就業機會的統計。

WORMS. (World of Operations Research and Management Science). 〈運籌與管理科學的世界〉，優秀的大眾化網站，由墨爾本大學（University of Melbourne）維護。

Yahoo 的運籌學網站

 

Excel 和 Excel Solver

Excel Tutorial〈Excel指導〉。這個指導教材網站由Duke大學 Fuqua學院的Paula Ecklund教授開發．不論你是初學者或是想學習Excel的進階操作，這是非常棒的教材．包含pivot tables, data tables, solver, analysis tools, graphing including scatter plots, array formulae和其他許多資料。

Add-ins for Excel.由Paul Jensen開發。

Add-in site for Excel由Tom Grossman維護，表列運籌學的附加軟件（主要是商業軟件）。

Excel Solver Tutorial from Frontline Systems. Frontline Systems是開發Excel Solver的公司。

 

線性規劃

Learning Tool for Linear Programming〈線性規劃的學習工具〉由Jean-Marie Bourjolly提供的一套非常好的線性規劃教材。

Frequently Asked Questions on Linear and Nonlinear Programming〈線性和非線性規劃的常見問題〉由John Gregory創始的常見問題彙集，目前由Bob Fourer維護．為NEOS Guide的部份，提供的資訊超出線性及非線性規劃。例如，非線性的指導部分提供許多啟發性搜尋的資料。

NEOS Guide to Optimization (Network Enabled Optimization System網絡促成最佳化系統)提供許多線性規劃，非線性規劃及網路最佳化的資料．此項服務由Argonne國家實驗室Optimization Technology Center最佳化科技中心提供．包含取材自More and Wright書中的Optimization Software〈最佳化軟體〉。有Argonne個案研究的列表。

NEOS Portfolio Problem〈NEOS投資組合的難題〉。如何選擇最低風險，但保證有不錯預期回報的投資組合（有權衡取捨風險和回報的其他方法）。

LP Explorer. 二維線性規劃。

The MPL On-Line Tutorial.〈MPL在線教件〉是一套線性規劃和其延伸的建模語言的教件。

 

最佳化

Algorithm Animations.〈演算法動畫〉取材自Robert Sedgewick的教科書《C++的演算法》Algorithms in C++. Addison Wesley Longman, 1992。也有其他動畫的連結。

Decision Tree for Optimization Software〈最佳化軟件的決策樹〉將非商用的編碼分類，列出教件和許多有趣的最佳化資料。

e-optimization〈電子最佳化〉是最佳化社群的網站，由ILOG贊助；ILOG是最佳化商業軟體的最好供應商之一。

Integer Programming Puzzles〈整數規劃謎團〉收集好玩並且可以用整數規劃解決的數學題目。

RIOT〈遠端互動最佳化測試平台〉．二維線性規劃，多維線性規劃．由Berkeley研究員開發。

The TSP page 很棒的網站，講述「推銷員走訪客戶問題」的歷史，還有演算法及照片。

The Traveling Salesman Problem 〈推銷員走訪客戶問題〉 有解決問題的Java程式。

Tutorial on Integer Programming.. Mike Trick的整數規劃教件。

 The Science and Technology of Decision Making 〈決策的科學程科技〉由David Bernstein開發，有許多有趣的Java圖解。

dmoz: the Open Directory Project.由dmoz贊助的最佳化網站列表，。

Tom Cavalier's site提供最佳化網站及其他連結。

Tom Cavalier's site提供最佳化網站的連結。

 

動態規劃

Lecture notes on dynamic programming〈動態規劃講稿〉劍橋大學的教材。

Lecture notes from 6.231 麻省理工學院開放式課程〈動態規劃與最佳化控制〉的內容。

A tutorial on dynamic programming 〈動態規劃教件〉 Mike Trick的講義。

〈第四次進攻要做什麼〉What to do on fourth down. 。 David Romer的技術文件，利用動態規劃來展示美式足球隊，在不同情況下如何組織第四次進攻。(英PDF - 2.9MB)

 

啟發法（捷思法）

The GA Archives 〈基因演算法檔案室〉有許多基因（遺傳）演算法（Genetic Algorithms）資料。

GAlib 有許多Ｃ＋＋基因演算法物件。這個圖書館的工具可在任何Ｃ＋＋程式利用基因演算法求解最佳化。

Ant Colony Optimization 〈蟻群最佳化〉課程沒有包含這個過份吹捧的想法。然而用虛擬螞蟻來解決最佳化問題卻是非常巧妙。

Tutorial on Genetic Algorithms〈基因演算法教件〉由Darrell Whitley撰寫。

Heuristics and Artificial Intelligence in Finance and Investment〈金融和投資的啟發法和人工智能〉有許多金融業利用啟發法的參考資料，包含神經網絡，模擬退火法，基因演算法和禁忌搜索。

 

圖形演算法和網路流量

Dijkstra's Shortest Path Algorithm解決最短路徑問題的小應用程式。

Graph Algorithms 〈圖形演算法〉網站由Dr. Thomas Emden-Weinert維護，有很多有趣的連結。

Graph Theory Terminology 〈圖形理論術語〉彙集圖形理論的專有名詞和定義．由Stephen Locke維護。

Graph Theory Glossary〈圖形理論詞彙〉，由Chris Caldwell維護。

Network Flow Algorithms. Andrew Goldberg和合作者開發這公共領域的〈網路流演算法〉網站，，現在由Andrew Goldberg維護．頗有效率。

Stanford GraphBase.由《規劃的藝術》Art of Programming與《TeX》知名作者」Donald Knuth開發。

The Stony Brook Algorithm Repository. 這演算法檔案庫有一套用於數據架構和圖形問題的演算法。

15.082J/6.855J, Network Optimization. Jim Orlin的〈網絡最佳化〉主題，特別針對網路流量。

 

其他主題

Operations Research and Radiation Oncology〈運籌學與放射腫瘤科〉網站由Allen Holder維護。

Sports Timetabling.（編註：網站鏈結失效）。