不論是生活中或是工作中，我們一直都在做各種決定。
今天要搭配什麼樣的衣服？中午要吃什麼？週末要去哪裡玩？要用多少時間花多少錢做哪些事情？會思考甚至煩惱，就是我們想要盡可能的追求最佳解，讓效益最大化。
當然，人生不（一定）會有最佳解，所以才有趣也值得去探索🌸
但是在某種程度上，如果可以量化這些變數，理論上就有可能找到最佳的解答。
一些例子像是：
行銷部門如何在有限預算下決定廣告商來達到最好的效果；
控管供應鏈，決定我這一季要進多少貨，要雇用多少作業員，達到合理最大的產能；
老闆決定要關哪幾家工廠來最佳降低總成本（包含固定營運成本跟運輸成本）
理財顧問幫助客人如何在可接受的風險下選擇投資組合報酬最佳化；
如何在有限的資源下找出最佳化分配（resource allocation optimization），做出最好的決定，是大大小小企業一直不斷追求的目標。
有鑑於此，今天我們要來稍微看一下一個叫做Linear Programming的工具，以及如何搭配Python來使用它。
Linear Programming
Linear Programming，英文可能聽起來像什麼程式，其實不是😅。中文叫做線性規劃。簡單來說是一套數學工具，用來幫助我們在已知限制條件（constraints）下找到目標（objective）的最佳解。前提是問題的本質必須是線形系統（Linear system）以及不等式（Inequality）所組成的（我們就不多討論複雜的數學模型，有興趣的可以在網路上參考）。
基本上簡單的例子像是：
求x + 2y 的最大值，條件是
y <= 50
x + y <= 120
聰明的你可能很快就算出來了，最佳解就是：
x + 2y = 170
x = 70
y = 50
反過來把上面的式子（或稱之為model）用生活的例子帶入的話，可能就像是：
我想要買兩個玩具跟一本書，最多我可以花多少錢？條件是
玩具一個不能超過50元。
一個玩具加一本書不能超過120元
當然，現實中的情況往往是更加的複雜，設計一套模型通常沒那麼容易，加上如果模型的複雜度高（譬如說有很多變數），不但得高度仰賴專業（domain）的判斷，計算上也會變得吃重。
那麼接下來，我們稍稍來看一下如何用Python來幫我們model這些條件及目標，進而計算出最佳解吧～。
例子 1
首先，我們會用到一個第三方library -- pulp。
pip install pulppulp提供的工具讓我們可以輕鬆的model我們目標（objective）以及限制條件（constraints）。
作法上，第一步是生成一個LpProblem的物件，代表的是我們要處理的Linear Programming Problem。
sense這個參數需要我們去決定model要做的事：可以是最大化（LpMaximize）或是最小化（LpMinimize）。
下一步，定義決策變數（decision variables），基本上就就像我們剛剛看到的x跟y。爲方便理解，這裡利用上述的例子來做兩個變數：一個叫做toy，另一個就叫它book。
這裡我們可以直接指定下限（lowBound）為0，意即不能有負數。當然還有上限（upBound）也可以使用。
接著，就是我們的限制條件（constraints）了。剛剛有說到玩具不能超過50元，而一個玩具加一本書不能超過120元：
這裡我們使用.addConstraint並給它一個我們制定的條件表現。
第二個argument是我們給條件的命名。
接下來，設定我們想最佳化的目標（objective）：
使用.setObjective這個method來將目標加入model中。
OK，這樣一來我們的model就算是設定好了！最後我們只要去執行.solve這個method就完成了。
執行.solve會回傳計算結果的status code，要理解status code我們可以用LpStatus來對照，基本上1就代表成功的算出最佳值。
想要看到目標值，我們可以用model.objective.value()來取得：
如果要知道變數的解，可以用直接用我們剛剛定義（LpVariable）的.value()來取得：
因此，我們也可以簡單寫一個function來告訴我們結果：
例子 2
當然，上述的例子只有兩個變數，是相當單純的線性問題，但是作法上大致相同。我們現在來看一個較複雜的例子吧。
假設我是生產拼圖的公司，今天我有四種拼圖的產品，分別是寶可夢，冰雪奇緣，鋼鐵人，以及米老鼠。各自的利潤如下：
寶可夢：$30
冰雪奇緣：$33
鋼鐵人：$28
米老鼠：$25
限制條件如下：
基於產能限制，一天最多能生產100套拼圖
一套寶可夢需要用到三組木板
一套冰雪奇緣需要用到兩組木板跟一組塑膠版
一套鋼鐵人需要用到一組木板跟兩組塑膠版
一套米老鼠需要用到三組塑膠版
木板一天的供應量最多到100組
塑膠版一天的供應量最多到95組
今天的目的是找出生產各個拼圖的數量，來最大化我們的利潤。
跟之前的作法一樣，首先來定義模型以及各個變數：
接著，加入限制條件，
lpSum讓我們可以直接提供需要加總的變數，省得去寫那麼多加號(+)。
這裡我們稍微做了一些調整，以一天所需及可用的木板跟塑膠版的方式來呈現
然後再設定我們的目標 - 求利潤的最大化：
最後利用.solve，以及剛剛做出來的print_result來看一下結果：
Bravo！我們成功的算出了最佳解！它告訴我們最大的利潤是2025，以及為了達到這個利潤，必須要生產50組Frozen的拼圖以及15組的Mini Mouse。看起來為了達到最好的利潤我們必須放掉寶可夢和鋼鐵人😭～或許這也是現實生活可能發生的情況。
這裡我們看到利用pulp，像這樣相對複雜的問題也可以被輕鬆的解開😀！
小結
今天簡單的跟大家介紹了一下：
什麼是Linear Programming
LP應用的範圍及簡例
利用pulp來設計並計算Linear Programming Problem
Linear Programming本身也是相當深奧的一門學問，也有一些公司（譬如說Gurobi）專門在這一領域提供企業的解決方案，如果有興趣可以參考網路上有相當多關於Linear Programming的資源。今天的重點還是了解這個工具能夠對我們有什麼幫助，如果大家有機會在工作或生活中應用到的話就太棒囉~~✨
Comments