最佳化導論

Introduction to Optimization, Spring 2002

2002年春季
是大學程度講授優化理論及應用的課目。課程包含優化模型及其在許多方面的應用,涉及交通,物流,生產製造,電腦科學,電子商務,專案管理,金融以及其他多種領域。同時,本課程還將介紹啟發式演算法,以及與線形、非線性規劃、動態規劃、整數規劃等相關的演算法和理論。
概括整個課題,可以用描述每次講課,也可以描述課程涉及的各種方法。我們有每次講課的描述,不過首先探討一些貫穿始...

指定教科書

W. Winston《運籌學》Operations Research;《應用與演算法》Applications and Algorithms,Duxbury Press, 1995.

Bertsimas D. 與Tsitsiklis《線性最佳化導論》Introduction to Linear Optimization, Athena Scientific, 1997.

Ahuja, R.、Magnanti, T. 與Orlin, J.《網路流:理論、演算法和應用》Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993.

課綱與詳述事項

教學大綱

 

15.053的主題思想

1. 無處不在的優化。我們討論優化思想在各領域的應用,包括營運管理、金融、市場營銷、工程、策略計畫、大學運營以及個人決策問題。我們也介紹不同的優化模型和概念框架,如線性規劃、整數規劃、非線性規劃、動態規劃以及啟發式演算法。

 

2. 演算法。秉承麻省理工學院的一貫傳統,我們探索演算法的內在機理。僅僅使用Excel內置的求解線性規劃的工具是不夠,必須要知道演算法如何運作。學習演算法有如下幾個重要意義。首先,有些問題容易求解,而有些卻存在固有「不可解性」。通過演算法的學習,我們能區分兩者。其次,理解演算法是相當重要的基礎,有了這基礎才能理解使用演算法得出的結果,從而更深入洞悉優化問題的本質。最後,只有瞭解了演算法的內在機理,才能修改現有的演算法或自己設計演算法。

 

3. 建模的目的在於把握問題的本質,而非數字。我們建立的模型只是對現實的局部反映,而非現實的全部。在管理與運籌學中,建模的本質在於對現實的模擬,從而能為決策提供支援。模型能使管理人員探索一系列的場景,並由此確定哪些決策在不同假設條件下是穩健的。同樣,通過模型分析,我們能確定哪些參數最重要,而另一些參數的改變對決策影響不大。靈敏性分析及其變化形式是深入剖析的另一項主要理論工具。電子商務對建模的影響告誡我們不能拘泥於數字。許多電子商務的應用要求在短時間內解答上千個模型,這意味著我們沒有時間對模型的輸出一一檢視,因此我們需要建立穩健且可信賴的模型。

 

4. 性能的保證。優化(和數學規劃)的特點是不僅能提供最佳解,同時還能提供最佳解的保證。即使當一個問題本身難於求解,優化法的技巧也能提供某種性能的保證,一個特別有用的保證就是與最佳解之間的最大距離。有兩個主要的理論工具可以獲得與最佳解之間的距離:「線性規劃的對偶間隙」以及「分支界定法」。

 

5. 搜索技術以及啟發式演算法。在許多情況下,需要求解的問題太難處理以至無法獲得最佳解,甚至連次優解都得不到。在這種情況下,我們需要制定策略來獲得比較好的解。這些策略往往被稱為啟發式演算法。課程中我們將介紹各種啟發式演算法,包括領域搜索法、模擬退火法、禁忌搜索以及遺傳演算法。

 

出勤

雖然15.053課程不要求出勤,但強烈建議學生來聽課。從過去幾個學期的經驗來看,有上課的學生大都發現課程材料變得簡單易懂,在期中考試及測驗獲得較好成績。無論是否來上課,學生都必須掌握課堂教授的內容,某些內容講述的方式不一定是透過書本。

 

前來上課的學生應儘量按時到達。遲到會打斷課堂流程,這是缺乏專業素養的表現(當然這視其表現而定)。另外,除非萬不得已,學生也不能早退。上課時間有衝突,無法按時趕到的學生應事先發電子郵件告知Orlin教授。同樣的,課程衝突需要早退的學生也要提前告知Orlin教授。

 

辦公室時間以及復習

助教和教授的辨公時間將會在學期初安排,並在網站公佈。

 

每周安排一次復習課,時間為週五2:30 到 4:00,地點為上課教室。復習課是選修,不會講述新內容。

 

每次復習課前的周三會發放復習課的習題列表以及涉及的其他內容。總體而言,復習課的習題會與當周佈置的作業相類似,也會涉及其他內容,如EXCEL SOLVER plus Ad Ins的使用等。

 

個人作業的相關政策

學生可以用小組形式合作,但作業必須獨立完成。小組成員不能提交相同的答案。我們禁止同學互相(或接近)抄襲彼此的作業。

 

如果在完成作業過程中得到同學大力幫助,必須在作業第一頁列明(接受幫助不會影響作業得分)。

 

生病或家中有急事

由於生病或家中有急事,有時學生不得不錯過一些作業或測驗。有這些情況,學生應在第一時間告知(1) 導師,(2) 輔導老師(如適當的話),(3)Orlin教授。

 

史隆管理學院專業守則

麻省理工學院史隆管理學院致力營造氛圍,使各成員能在相互尊重基礎一起學習工作。做出個人決定時,都應謹記其他夥伴的利益。

為了達到相互尊重這一共同目標,教職員工以及學生都必須時刻牢記:

準時上課和授課,保證持續上課。
─準時開課,按時下課。 保持專業氛圍。
─包括,但不局限於: 評價與開玩笑都必須尊重他人。 注意舉止禮儀, 特別是處置食物和飲料。
─合理使用電腦和其他科技產品(例如,關閉無線裝置、上課期間不上網、不發郵件)。
─避免干擾以及不尊重他人的舉動(例如,避免堂上隨便說話和小動作)。
─遵從與招募人員和講者的約會安排,如需取消請及時通知。
─與史隆有關的一切活動,必須對嘉賓和與會者彬彬有禮。
─如果不知道應該遵從哪條守則,請遵守最保守的標準。

 

以上的例子是鼓勵學生反思個人對史隆團隊的影響。

 

遵守上述要求與標準是史隆管理學院教職員以及學生的共同權利與義務。作為教學活動的團隊,我們必須身體力行。

相關連結

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〈運籌與管理科學學院學生會〉立志成為服務運籌學和管理科學及相關領域的學生和研究生的最佳網站.盡可能滿足網路上最重要的需要。

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

Yahoo 的運籌學網站

 

EXCEL以及EXCEL Solver®

Excel Tutorial. 〈Excel 教程〉由南達科他大學的Brad James教授撰寫。如果你不精通EXCEL,這是快速入門。當然,這不是為麻省理工學院學生編寫。

Add-ins for Excel.〈Excel插件〉由Paul Jensen開發。

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

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

Excel Solver® 教程 Excel、Excel Solver以及Visual Basic教程。

 

優化

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

Mathematical Programming Glossary〈數學規劃辭彙〉表由Harvey Greenberg編寫,提供線性規劃以及許多擴展內容的定義。也包括許多數學規劃的資訊。

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

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

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

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

NEOS Diet Problem〈NEOS飲食選擇問題〉如何以最小花費獲得最好的飲食選擇。(遺憾的是遺漏了口味)。

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

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

Optimization Software〈優化軟體〉 NEOS關於優化的指南,摘自More和Wright的書本。

Web sites for Integer Programming and Combinatorial Optimization〈整數規劃以及組合優化的網站〉Harvey Greenberg提供的網站清單。

Software for Optimization : A Buyer's Guide〈優化用軟體:買家手冊 第一部分〉作者:Rob Fourer。
Optimization : A Buyer's Guide〈優化用軟體:買家手冊 第二部分〉作者:Rob Fourer。

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

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

 

 

動態規劃

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

Dynamic Programming tutorial for DNA sequence alignment〈DNA排序的動態規劃〉DNA排序演算法的教程,由Needleman and Wunsch編寫。

 

啟發式演算法

Constraint Programming〈約束規劃〉 關於約束規劃的站點,資料很多,包括常見問題。

GA PlayGround〈遺傳演算法遊樂場〉遺傳演算法的JAVA小程式及應用

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

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

NP-completeness and more〈線性規劃:完備問題及其他〉 這是一個線性規劃-完備以及線性規劃-難問題的綱要,列舉了這些問題是否可以獲得次優解

 

圖形演算法以及網路流問題

GIDEN: A Graphical Implementation Development Environment for Networks.〈GIDEN: 圖形化執行網路的開發環境〉展示了許多網路演算法,包括最短路徑問題,最大流演算法以及網路單純形法。(示範版不能使用單純形法)。

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

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

講者介紹

Prof. James Orlin

翻譯工作人員

翻譯人員夏凌

繁體編輯劉契良

簡體編輯劉慕華

檔案後製處理馬景文