實用線性規劃理論與應用 - 國立清華大學外文系(畢業) 蔡雅欣(隨班附讀)
課程名稱►實用線性規劃理論與應用 授課教師►數學系 許瑞麟老師
心得分享者►國立清華大學外文系畢業 蔡雅欣(隨班附讀)
修課動機
雖然是文學院畢業，但我一直對金融＆數據科學有興趣，大學期間也修了很多相關課程。畢業後我成為了數據分析師，但深感要精進自己，就必須加強自己的數理、計量，和最佳化等知識，才能提出更好的模型。最佳化等題目大多隸屬於工業工程下，但我沒有工業工程相關的背景，而且因為工作，我很難配合一般大專院校的時間表去附讀。我也試過從Coursera、Udacity、Udemy等網站找資源自學。但我發現，學校外的課程大多集中於資訊工程。如果想要找數理基礎的課程，除了大專院校規劃的平台課程（e.g. OCW）幾乎沒有可以建立基礎的素材。另一方面，我計劃在今年申請碩班，希望能對自己想要專攻的領域有更多的了解。因此我向成大理學院模組化課程申請選修了這門數學系許瑞麟老師開設的實用線性規劃。希望能透過短時間、高強度的學習模式，建立相關基礎，也盡量探索自己對於未來的規劃。
課程內容
課程頭兩天，許教授把授課內容集中在建立基礎線性規劃的概念，其中穿插一些基礎線性代數和高中關於最佳化的內容。教授首先介紹了線性規劃的由來，以及這個科目和作業研究的關係，後續在哪些場域有應用情景。之後教授透過數學公式解釋了線性規劃的基本模型，並利用 The Diet Problem 和 Support Vector Machine 作為例子，向我們演示了線性規劃的實務運作。
教授在第二天的課程裡，延續了第一天的教學內容，並往下延伸，透過更多不同的例子解釋了不同的應用場景裡可能遇到的 Linear Programming Model，像是 Ice Cream Production Scheduling 裡，Objective Function 含有絕對值時該如何處理，以及 Network Flow Problem 裡，我們如何將這些 Path、Vertex 轉換成 Linear Programming Model。
第三天我們正式進入到了線性規劃的內容。其中教授提到了標準的 Linear Programming Model，同時也提出了幾個非標準Linear Programming Model 的情況時可能解法，例如 Slack Variable、Surplus Variable、BFS，以及 Simplex Method 等這樣透過降維、代數替換等方法實現標準Linear Programming Model的方法。
第四天時，教授開始介紹 Duality，並用Farkas Lemma 證明。透過 Duality，我們可以確保 Model 的上界，由此推導出 Programming 的最佳解。
最後一天，教授介紹了 Zero-Sum Game 的博弈思維及worst case optimal strategy 並利用 Linear Programming 求出 Nash 均衡解。最後推廣到 Bimatrix game，講解Bimatrix 的觀念與應用，並說明 Bimatrix game 一定存在 Nash 均衡解，但是目前並無有效率的演算法去求出來。
授課風格
這們課是英文授課。個人認為整體節奏偏快，但許教授的授課方式又不至於讓我覺得很緊湊或難以消化。平時上課會以投影片為主。教授會針對每一張投影片深入講解，我自己也會盡量當天就將上課的內容、筆記統整跟消化，這樣更能能幫助自己接續緊湊的課程。
修課心得
對於一個生活中就是重度選擇障礙症患者的我來說，這門課帶給我挺多啟發的。
首先是「應用性」。許教授不僅會在課程中帶入很多基礎理論，同時向我們演示這些理論如何套用到實際例子上，像是在 Zero-Sum Game 時他會用美式足球當作基礎題材，向我們解釋雙方在做決策時可能出現的情況總和，又像是在 Bimatrix 時提到的 social welfare，以及後續提到的兩家競爭廠商各推促銷策略的例子，看似達到Nash均衡解卻是一個雙輸的局面。這些應用的例子都讓我對線性規劃有更深的了解。
其次是「解釋角度」。大學時期我修過幾門統計和資訊工程的課，當中有提到 OLS 、SVM 、Shortest Path Problem 等內容，都只是以統計或是資訊工程的角度對模型做解釋。但在這門課中，同樣的例子教授透過線性規劃的框架，將這幾個我原先在不同系統裡學到的知識重新串連了起來，讓我對這些模式有了更深刻的認識 。
最後是「實用性」。許教授不會只專注在理論和例子，課程中他還提到很多實務經驗。我最有印象的是他在教我們 AMPL 程式語言時，提到他過去在 AT&T 貝爾實驗室參與開發這些模型的經驗。他把這份經驗轉化成工業工程裡的語言，讓我們看到了知識價值在市場上會隨時間變化導致邊際效應遞減的可能。這讓我能將這門課所學，整合進人生成長。
短短五天能夠學到關於線性規劃的內容其實不深。但許老師的講解卻是我最能理解的方式。尤其是當我發現我能激勵自己，在短時間內用MatLab寫出零和遊戲的simulation code時，那種成就感真的是之前作為文組生無可比擬的。我學到很多，也推薦線性規劃有興趣的同學來選修。
關鍵字 #成大模組化 #線性規劃 #應用 #程式 #跨領域
瀏覽數:
分享