跳到主要內容區

實用線性規劃理論與應用 - 林佳霈

banner

什麼是線性規劃?

線性規劃英譯為 Linear Programming,令人意外的是在這裡 programming 和電 腦編程並沒有直接關係,這得要從線性規劃的發展開始說起。線性規劃起源於 1940 年代,那時電腦是非常罕見的高科技,而為了解決第二次世界大戰部隊派 遣人力的需求,軍方將有用的資訊寫成數學式子並求解,這也是現在「作業研究」 這個學科的雛形。那到底什麼是線性規劃呢? 簡單來說,線性規劃方法是在數學 模型中以線性關係表示目標函數和條件限制式,並從而獲得最佳解(例如:最大 利潤或最低成本)。

 

線性規劃可以怎麼應用 ?

首先,舉一個簡單的作業研究問題為例,現代人為追求飲食均衡,每天攝取不同 種類食物,而在營養需求中每一種成分的攝取皆有不同的限制,那我們可以將其 限制寫成數學模型並以線性不等式關係來表示出獲取不同成分營養所需攝取各

種食物的數量組合。除此之外,數據科學中常見的分類問題也是線性規劃的應用, 例如支援向量機(SVM)的分類器求取一個分隔不同資料特徵的線性邊界(例如:平 面),將已知收集的資料劃分為兩個區域。當出現新的觀測值時,將它映射到此 特徵空間(feature space)中,並根據它們落在平面的哪一側來預測此新的數據 是屬於哪個類別。還有,著名的賽局理論也可以應用線性規劃方法,零和賽局使 用 minmax (最小最大)的方法找到奈許均衡點,而 minmax 問題是將最大損失最 小化,這個 minmax 的問題我們可以等價化成一個線性規劃問題,並從而獲得最 佳解(奈許均衡點)。在老師上課舉完許多例子後,我比較瞭解線性規劃是什麼。 其實,線性規劃在生活中的應用無所不在,如果還有興趣想多看看,不妨上網搜 尋一下唷!

 

這是一堂怎麼樣的課 ?

此堂模組化課程開課時間約為八月下旬為期五天,由於模組化課程為一學分的密 集課程,因此,上課內容精簡濃縮,節奏也相對較快。本課程為全英文授課,如 果對課程有興趣或之後想出國念書,都很適合來試試看。這門課的授課老師為數 學系的許瑞麟教授,老師的講解方式會先針對課程的大綱做介紹,並舉多個線性 規劃的例子,接著推導線性規劃基本理論及對偶定理。而在理論證明部分著重邏 輯思考。我覺得如果有修習過線性代數,學習效率會較好。此外,本課程著重於 模型應用,如果能懂得原理,就可以看懂更多模型。除了上課之外,每天都會有 作業練習。作業涵蓋理論推導以及 code 實際操作。Code 主要寫的是 AMPL 語法 並上傳到 Neos(專門解 numerical optimization problems 的伺服器)。上課時老師 會大致講解 AMPL 語法,所以,不會寫 AMPL 也不用太緊張。最後上完五天的課程後,需要撰寫一篇報告,報告的內容包含兩部分:一、以數學的方法總結這五天 所學的主題;二、針對學習上有興趣的部分提出想法及應用或是上課心得及收穫。 總體而言,對於課程的設計我認為是一門扎實的好課。

 

上這門課我收穫到什麼 ?

在高中數學裡,就初步提到線性規劃的想法,一開始選這門課是期望更了解線性 規劃結合實際生活中的例子及應用,而的確在這門課中,許老師也舉了很多在不 同領域裡線性規劃的應用。此外,老師也會舉自己工作經驗作為例子,比如如何安排及規劃船隻貨櫃輪流停靠港口與貨櫃作業流程使成本最低且更有效率的應用 碼頭空間,讓線性規劃這門學問更加生活化。 我認為修習這門課我有三大收穫:一、練習英文聽力並提高專注力。在周遭皆為 中文環境的情況之下,我原先對於英文聽力並不敏銳,雖然一開始不習慣所以上 課較容易分心,但是,會有漸入佳境的感覺。二、培養我的邏輯思考的能力。在 理論證明中,並沒有太難的代數運算,大部分為邏輯性的推論及一些線性代數的 基礎,我是認為有些難度,但在這堂課的訓練下,我跟著老師的步調去練習,發 現自己邏輯思考能力在短時間內就有進步。三、讓我針對特定領域,快速學習。 由於模組化課程是密集課程,課程也因此更加精簡濃縮,這能幫助我們對於特定 領域能有初步快速的了解。 整體而言,我認為課程安排與我的預期目標相符,除了學習如何應用線性規劃之 外,還有理論作為支持,這能幫助我看懂更多模型,之後如果有興趣,我也具備 再修習相關課程的能力知識背景。

 

關鍵字 #成大模組化 #線性規劃 #作業研究 #SVM #賽局理論 #Neos

bottombanner

 

瀏覽數: