研究所考試
在前幾篇的線性規劃主題專欄裡,《線性規劃(1)》首先介紹線性規劃的概念,包含決策變數、限制條件與目標函數,讓各位讀者對於線性規劃問題有基礎了解。《線性規劃(2)》提到線性規劃的數學形式,包含一般形式與標準形式,並且定義可行解與最佳演算法,為接下來解決線性規劃的方法做鋪墊。而在《線性規劃(3)》,我們介紹了單體演算法,將將抽象的最佳化問題轉換成直觀的幾何圖形,並透過目標函數的等值線成功從可行區域當中找到最佳解。
透過先前的專欄,我們已經充分明白線性規劃的問題要怎麼從數學式去解決。然而,除了最一開始提到的競選問題,我們似乎並不清楚在實務上,究竟有哪些問題可以透過線性規劃來解決。因此,在了解了演算法與數學原理後,本篇專欄將帶大家回歸實務應用,探討如何「將問題建模為線性規劃」,並透過差分約束系統與圖論等經典問題,展現線性規劃強大的建模能力與應用價值。
線性規劃是作業研究(Operations Research)與計算科學中的核心工具,廣泛應用於商業決策、資源調度與工程優化,例如選舉場景就是一個典型的例子。以下是另外兩個例子:
航空公司希望排定機組人員的班表:美國聯邦航空管理局(FAA)提出了一些限制,例如限制每位機組人員可連續工作的小時數,並堅持特定機組人員在每個月份內只能操作一種機型。站在航空公司的立場,他們會希望在滿足所有限制的前提下,盡可能使用最少數量的機組人員來安排所有航班,以降低總人事成本。
石油公司希望決定在哪裡鑽探石油:石油公司在特定地點設置鑽井會產生相應的成本,而且根據地質調查,能夠預期在該鑽井獲得多少數量的桶裝石油。該公司在設置新鑽井方面預算有上限,並希望在此預算限制下,最大化其預期獲得的石油量。
以上這兩個例子,都能夠從問題描述當中看見線性規劃的影子。例如降低人事成本、最大化獲得石油量,都是最佳化問題的敘述方式。而機組人員的工作時數、每個月份能操作的機型數量,以及能夠設置鑽井的預算,都是在描述該問題的限制條件。接下來,我們將要從演算法常見的問題著手,說明如何在這些經典問題中透過線性規劃重新建構問題。
經典演算法場景還記得我們在早期的專欄討論過差分約束系統(Difference Constraints System)與最短路徑問題嗎?題目會給予多個變數與他們所構成的不等式,而我們要將問題當中的每個變數轉換成圖形中的頂點,並將不等式轉換為圖形上的有向邊,最後再利用最短路徑演算法計算出每個變數的解,如下圖所示。

而當我們仔細去觀察這個問題的數學式,會發現它確實就是線性規劃問題的限制條件該有的模樣,因此我們便是在無形中利用線性規劃的特性去解決差分約束與最短路徑這個經典的大考題。
將問題當中的線性規劃特性找出來的好處在於,一旦你有辦法將問題轉化為多項式大小的線性規劃,就可以透過橢球演算法(Ellipsoid Algorithm)或內點法(Interior-Point Methods)在多項式時間內求解。換句話說,只要能辨識出這個問題可以用線性規劃建模,就可以直接套用常用的線性規劃演算法來求解。同樣的,線性規劃也可以對圖論(Graph)進行建模與求解。我們將透過單對最短路徑問題(Single-Pair Shortest-Path Problem)作為範例,將這個經典的圖論問題透過線性規劃來進行建模。
,從節點 u 到節點 v 的邊權重記錄為 w(u,v)。我們要計算的目標為起始頂點 s 到目標頂點 t 的最短路徑權重 dt 為多少。而根據三角不等式(Triangle Inequality),我們可以得到對於所有邊 (u,v)∈E,皆滿足不等式:dv ≤ du + w(u,v)。而根據定義,通往起始節點 s 的最短路徑權重 ds 會設定為 0。因此我們可以寫出單對最短路徑問題的數學模型:
