跳到主要內容

OR|作業研究與資料科學 其一

作業研究(Operations Research,OR),是一門應用數學學科,其是利用統計學,數學模型和資料科學等方法,去尋找複雜問題中的最佳或近似最佳的解答。作業研究經常用於解決現實生活中的複雜問題,特別是改善或優化現有系統的效率。


Photo source :  Data Science Milan

上面這一段文字,是源自「作業研究」(以下簡稱為 OR)的中文維基百科的首段文字介紹,乍看之下,OR 跟資料科學(Data Science,以下簡稱為 DS)看起來似乎很雷同?都是將資料扔進各種數學工具當中,藉以解決一些困難的問題。

大方向而言的確如此,但兩者在目的與手段上仍存有一些差異,因此,我們就來聊聊兩者之間的同異之處。本文將先從「目的」的部份談起,並且先聚焦在 OR 的部分。


# 最佳化

我們回顧一下維基百科的那段描述:

它是利用統計學,數學模型和資料科學等方法,去尋找複雜問題中的最佳或近似最佳的解答。

這段描述當中,直接把 DS 給含括在 OR 裡面了,但是有個關鍵字:「最佳」。在相關學術及應用領域當中,OR 的問題,往往也被稱作「最佳化」(Optimization)的問題,要最佳化什麼呢?利潤、成本、時間、距離、或者任何可以被明確定義的計量單位。舉一些更完整的例子:

「求解一個物流配送車輛的路徑最佳化問題,使其移動的距離或者花費的時間最小化。」

「求解一間新開設的電信門市店址選擇問題,使其能夠涵蓋的服務範圍最大化。」

「求解一個家航空公司的機組人員排班問題,使其人力成本最小化。」


# 目標與限制

這些需要被「最佳化」的東西,就可以被轉譯成一堆數學公式,對應到各種的應用情境,它們就可能利潤函數、成本函數、距離函數等等,在 OR 當中,通通被稱作為「目標函數」。

但是 OR 當然不是只有目標函數,另一個重要的東西就作「限制式」,或被稱作「約束條件」(Constraints)以上述的例子來說,在求解物流配送車的路徑最佳化問題時,可能要滿足至少要送達多少個配送地點、或者要考慮到配送地點的先後順序。求解家航空公司的機組人員排班問題時,除了最小化成本之外,還須考慮到排班結果必須符合勞基法。

這些限制式亦會被轉譯成一堆數學公式,在求解目標函數的時候,一並納入。以數學的角度來說,也就是將這些條件化做各種變數,並限制其值域、變數類型,以及各個變數之間的關聯性。而這些出現在限制式當中的變數,同樣是我們希望透過 OR 方法來求解的東西。


舉一個更具體的例子,以新開設一家電信門市為例,假設我們考慮作為新門市的地點總共有三處,而我們只會選擇一處作為真正的新門市地點。我們就可以將「是否真的會成為新門市地點」這個條件,轉譯為變數 x1, x2, x3 三個變數。

因為門市地點只有「存在」或「不存在」兩種可能性,因此 x1, x2, x3 的變數類型為二元變數 0 或 1,同時我們令其值等於 1 的時候代表該地點是新門市的地址。

因為三處地點只會有一處真的成為新門市地點,所以 x1, x2, x3 之間的關聯,就可以寫作 x1 + x2 + x3 = 1。

透過 OR 的求解運算之後,我們就可以得知 x1 的值為 1,而 x2, x3 的值為 0(←假設答案是這樣),而所求解的最大涵蓋服務範圍為若干用戶數量、或者若干平方公里等等。以該命題而言就是 OR 當中所謂的非線性規劃問題。


# 更多目標與限制

上述所提到的,都只是一些相對較簡單的範例描述,而在真實情境當中,我們可能要處理更多複雜的限制條件關係、或者不只一項最佳化目標。

以物流配送車輛的路徑最佳化問題為例,我們可能希望在最小化總移動距離或者移動時間的情況下,同時最大化貨物配送量、或者最大化配送的門市數量,也就是所謂的「多目標最佳化問題」(Multi-Objective Optimization)。

然而我們可以想見,假設 E1 與 E2 是某兩個我們希望最小化的目標函數,當我們將 E1 最小化的時候,E2 就不見得是可能的最小值,反之亦然。因此,在多目標最佳化問題當中,我們還會透過其他的方法,來找到多個目標函數之間的平衡,例如:將 E1 與 E2 純量化(Scalarization),正規化(Regularization)。


# 命題與應用

有了上述的認知之後,我們便可以進一步來談 OR 的命題類型。若我們以問題的變數、方程式的定義及關聯加以區分,大多數的 OR 問題都可以歸納為以下三種問題類型:線性規劃、非線性規劃、與整數規劃。但需要特別留意的是,這裡只是粗淺地介紹 OR 當中常見的命題類型,在該領域當中,當然還有其他更複雜的命題類型,例如動態規劃(Dynamic Programming)、隨機規劃(Stochastic Programming)等等。

眼尖的讀者可能會發現,上述所說的內容,其實都是數學最佳化(Mathematical Optimization)的範疇。沒錯!OR 本身即是數學最佳化的一種代表性應用。若你從應用面的角度來看,你會發現 OR 經常被使用於運輸與指派規劃、網路最佳化、行銷組合問題、投資組合問題、生產與製造規劃等等領域。

OR 本身是一門應用性很強的學科。其所使用的規劃方法當然不限於數學最佳化,若你去翻閱 OR 的教科書,你可能會在目錄當中看到諸如:決策理論、專案排程、賽局理論、等候理論、存貨理論、馬克夫鏈、系統模擬等等。這些篇章所使用到的規劃方法,就是十分奠基於特定領域知識的模型,就不見得是所謂的數學最佳化模型。但是它們最終的目的都是一樣的,都是希望透過某種數學方法,在複雜問題當中尋求最佳或近似最佳的解答只是,當我們提到 OR 的時候,所指涉到的通常都是數學最佳化的問題,故這裡有必要特別說明之。

透過以上說明,我們便能粗略理解,OR 方法所求解的目標什麼。而有關於 OR 的「手段」,以及 OR 與 DS 的差異,則留待參考同標題的下一篇文章。


延伸閱讀:

  1. 演算法筆記 – Optimization
  2. 線性規劃 (一):標準型問題 | 線代啟示錄
  3. 數據與思考 : 工業工程與作業研究