研究所考試
在日常生活中或企業決策裡，我們經常面臨這樣的挑戰：如何在有限的資源下，達到最好的效果？舉例來說，某家工廠希望在現有的原料與人力限制下，最大化產品的總利潤；或是物流公司希望在車隊數與時間限制下，最小化運輸的總成本。這些問題在數學與作業研究中，都有一個共同的核心結構：在有限資源和相互競爭的限制條件下，去追求一個目標的最大化或最小化。
如果我們可以進一步將這個目標寫成某些變數的線性函數（Linear Function），且將所有的「資源限制」與「邊界條件」也寫成這些變數的線性等式（Equalities）或線性不等式（Inequalities），那麼這類型的問題就被定義為線性規劃問題（Linear-Programming Problem），也可以簡稱爲 LP。線性規劃是現代應用數學、資訊工程與管理科學中最重要的最佳化工具之一。在本次專欄中，我們將透過一個「政治宣傳」範例，帶領大家一步步了解如何將現實世界的複雜問題，轉化為嚴謹的線性規劃數學模型。
假設你是一位正在競選的政治家，你的核心目標是「贏得這場選區選舉」。為了有效執政，你設定了一個具體的目標：在選區內的各個區域，都必須贏得至少一半以上登記選民的選票。經由幕僚統計，你的選區主要分為三種截然不同的地理與人口結構：
- 城市（Urban）：共有 100,000 名登記選民。
- 郊區（Suburban）：共有 200,000 名登記選民。
- 農村（Rural）：共有 50,000 名登記選民。
根據你的執政願景，你希望在城市贏得至少 50,000 票（10萬的一半）、郊區贏得至少 100,000 票（20萬的一半）、農村贏得至少 25,000 票（5萬的一半）。
你是一位非常有原則的候選人，絕不支持自己不相信的政見。然而，競選團隊在進行市場調查後發現，不同的政策議題在不同的區域，宣傳效果（換取選票的效率）大不相同。你的團隊提出了四個你深信不疑的主要競選議題：為喪屍末日做準備（Zombie Apocalypse）、為鯊魚配備雷射（Sharks with Lasers）、為飛行汽車建造高速公路（Highways for Flying Cars）以及允許海豚投票（Dolphins Voting）。
數據分析 競選團隊透過大數據與民意調查，估算出在各個議題上每投入 $1,000 美元的廣告費，預期會為你帶來的選票變動量（以「千人」為單位）。其中，正數代表獲得選票，負數則代表該政見引起該區選民反感，會導致選票流失。詳細數據如下表所示：
| 政策議題 (Policy) | 城市選票變動量 (Urban) | 郊區選票變動量 (Suburban) | 農村選票變動量 (Rural) |
|---|---|---|---|
| 1. 喪屍末日 | -2 | 5 | 3 |
| 2. 鯊魚雷射 | 8 | 2 | -5 |
| 3. 飛行汽車公路 | 0 | 0 | 10 |
| 4. 海豚投票 | 10 | 0 | -2 |
表格解讀範例：若在「鯊魚雷射」議題上投資 $1,000 美元的廣告費，可以在城市贏得 8,000 張選票，在郊區贏得 2,000 張選票，但在農村會流失 5,000 張選票。
盲目嘗試與局限性 在沒有學過線性規劃前，候選人通常只能靠經驗或「反覆試驗法（Trial and Error）」來決定預票配置。 例如，競選經理提出了一個直覺的策略：花費 $20,000 宣傳「喪屍末日」、花費 $0 宣傳「鯊魚雷射」、花費 $4,000 宣傳「飛行汽車公路」以及花費 $9,000 宣傳「海豚投票」。此時，我們來計算這個策略的總花費與最終得票數（注意：經費以「千美元」為單位，即投資量分別為 20、0、4、9）：
- 總廣告花費：20 + 0 + 4 + 9 = 33（千美元），也就是 $33,000 美元。
- 城市得票數：(20 × -2) + (0 × 8) + (4 × 0) + (9 × 10) = 50（千票），剛好達到 50,000 票的門檻。
- 郊區得票數：(20 × 5) + (0 × 2) + (4 × 0) + (9 × 0) = 100（千票），剛好達到 100,000 票的門檻。
- 農村得票數：(20 × 3) + (0 × -5) + (4 × 10) + (9 × -2)= 82（千票），大於 25,000 票的門檻。
問題是，這個策略雖然成功達成了所有目標，但它是花費最少的策略嗎？有沒有可能只花 $30,000 就能達到同樣的效果？為了回答這個問題，我們必須擺脫盲目猜測，改用數學建模的方法，也就是要進行線性規劃。
要將任何現實問題轉化為線性規劃模型，必須依序確立三個核心要素：決策變數、限制條件與目標函數。
決策變數（Decision Variables） 決策變數是指決策者可以控制與調整的未知數，它們的數值決定了最終的結果。在這個政治問題中，我們的決策是「要在各個議題上花多少宣傳費」。因此，我們引入四個決策變數：
- x1：花在為「喪屍末日」做準備的廣告金額（單位：千美元）。
- x2：花在為「鯊魚配備雷射」的廣告金額（單位：千美元）。
- x3：花在「建造飛行汽車高速公路」的廣告金額（單位：千美元）。
- x4：花在「允許海豚投票」的廣告金額（單位：千美元）。
限制條件（Constraints） 限制條件是指決策過程中必須遵守的法律、資源、物理或政策限制。在本案中，限制條件來自於「三個選區的最低得票數要求」。根據數據表格與決策變數，我們可以建立以下的不等式：
- 城市選票限制：城市得票數必須大於或等於 50（千票）。
- 郊區選票限制：郊區得票數必須大於或等於 100（千票）。
- 農村選票限制：農村得票數必須大於或等於 25（千票）。
此外，還有一個容易被忽視但極其重要的隱含限制：在現實中，我們雖然可以進行負面文宣，但無法購買「負成本」的廣告（即我們無法透過不宣傳來平白獲得預算）。因此，所有的廣告花費都必須大於或等於零。這在數學上稱為非負限制（Non-negativity Constraints）：
目標函數（Objective Function） 目標函數是衡量決策好壞的數學表達式，決策者的目標是讓這個函數的值達到最大（如利潤）或最小（如成本）。在本題中，候選人希望「花最少的錢」，也就是將總廣告經費最小化。因此，目標函數為：
線性規劃模型建立將上述三個要素結合，我們就可以寫出該政治問題的完整線性規劃模型（Linear Programming Model）。在學術與工程上，我們通常會以標準對齊的形式來呈現：
這個嚴謹的數學結構，就能透過例如單體法（Simplex Method）等演算法，直接讀取並求出最佳解。只要利用電腦軟體（如 Excel Solver、Python 的 SciPy 或 MATLAB）輸入這組方程式，就能在極短的時間內算出真正最省錢的黃金宣傳策略。透過單體法來計算，本次競選的策略可以更換為：花費 $20,000 宣傳「喪屍末日」、花費 $0 宣傳「鯊魚雷射」、花費 $0 宣傳「飛行汽車公路」以及花費 $9,000 宣傳「海豚投票」。此時城市與郊區選票限制會恰好達標，而農村選票限制會大於25,000 票的門檻，就能夠節省 $4,000，總共花費 $29,000 就能成功達成目標。
今天的專欄，我們透過一場政治競選扮演競選團隊去制定策略，希望能在選區內的各個區域，都必須贏得至少一半以上登記選民的選票。透過建立線性規劃的數學模型，我們依序定義決策變數、列出限制條件，最後寫出目標函數，確立整個線性規劃問題的樣貌，最後再透過演算法找出最合適的解。線性規劃的應用範圍極廣，除了政治宣傳與經費配置外，它在計算機科學中更是無處不在。常見的演算法問題例如：網路流問題（Network Flows）、圖論中的最短路徑問題（Shortest Paths）、以及圖形連通性問題（Connectivity in a Graph），都可以被包裝或轉化為線性規劃的形式來求解。希望透過接下來一系列的專欄，讓各位讀者對線性規劃有更完整的認識！