發佈時間:20261119

在前幾篇的線性規劃主題專欄裡,《線性規劃(1)》首先介紹線性規劃的概念,包含決策變數、限制條件與目標函數,讓各位讀者對於線性規劃問題有基礎了解。《線性規劃(2)》提到線性規劃的數學形式,包含一般形式與標準形式,並且定義可行解與最佳演算法,為接下來解決線性規劃的方法做鋪墊。而在《線性規劃(3)》,我們介紹了單體演算法,將將抽象的最佳化問題轉換成直觀的幾何圖形,並透過目標函數的等值線成功從可行區域當中找到最佳解。

透過先前的專欄,我們已經充分明白線性規劃的問題要怎麼從數學式去解決。然而,除了最一開始提到的競選問題,我們似乎並不清楚在實務上,究竟有哪些問題可以透過線性規劃來解決。因此,在了解了演算法與數學原理後,本篇專欄將帶大家回歸實務應用,探討如何「將問題建模為線性規劃」,並透過差分約束系統與圖論等經典問題,展現線性規劃強大的建模能力與應用價值。

線性規劃的應用
現實中的實用場景

線性規劃是作業研究(Operations Research)與計算科學中的核心工具,廣泛應用於商業決策、資源調度與工程優化,例如選舉場景就是一個典型的例子。以下是另外兩個例子:

航空公司希望排定機組人員的班表:美國聯邦航空管理局(FAA)提出了一些限制,例如限制每位機組人員可連續工作的小時數,並堅持特定機組人員在每個月份內只能操作一種機型。站在航空公司的立場,他們會希望在滿足所有限制的前提下,盡可能使用最少數量的機組人員來安排所有航班,以降低總人事成本。

石油公司希望決定在哪裡鑽探石油:石油公司在特定地點設置鑽井會產生相應的成本,而且根據地質調查,能夠預期在該鑽井獲得多少數量的桶裝石油。該公司在設置新鑽井方面預算有上限,並希望在此預算限制下,最大化其預期獲得的石油量。

以上這兩個例子,都能夠從問題描述當中看見線性規劃的影子。例如降低人事成本、最大化獲得石油量,都是最佳化問題的敘述方式。而機組人員的工作時數、每個月份能操作的機型數量,以及能夠設置鑽井的預算,都是在描述該問題的限制條件。接下來,我們將要從演算法常見的問題著手,說明如何在這些經典問題中透過線性規劃重新建構問題。

經典演算法場景

還記得我們在早期的專欄討論過差分約束系統(Difference Constraints System)與最短路徑問題嗎?題目會給予多個變數與他們所構成的不等式,而我們要將問題當中的每個變數轉換成圖形中的頂點,並將不等式轉換為圖形上的有向邊,最後再利用最短路徑演算法計算出每個變數的解,如下圖所示。

而當我們仔細去觀察這個問題的數學式,會發現它確實就是線性規劃問題的限制條件該有的模樣,因此我們便是在無形中利用線性規劃的特性去解決差分約束與最短路徑這個經典的大考題。

將問題當中的線性規劃特性找出來的好處在於,一旦你有辦法將問題轉化為多項式大小的線性規劃,就可以透過橢球演算法(Ellipsoid Algorithm)或內點法(Interior-Point Methods)在多項式時間內求解。換句話說,只要能辨識出這個問題可以用線性規劃建模,就可以直接套用常用的線性規劃演算法來求解。同樣的,線性規劃也可以對圖論(Graph)進行建模與求解。我們將透過單對最短路徑問題(Single-Pair Shortest-Path Problem)作為範例,將這個經典的圖論問題透過線性規劃來進行建模。

最短路徑 (Shortest Paths)
數學模型
在一個單對最短路徑問題當中,輸入會是一個加權有向圖,從節點 u 到節點 v 的邊權重記錄為 w(u,v)。我們要計算的目標為起始頂點 s 到目標頂點 t 的最短路徑權重 dt 為多少。而根據三角不等式(Triangle Inequality),我們可以得到對於所有邊 (u,v)∈E,皆滿足不等式:dv ≤ du + w(u,v)。而根據定義,通往起始節點 s 的最短路徑權重 ds 會設定為 0。因此我們可以寫出單對最短路徑問題的數學模型:
為什麼是「最大化」?
我相信各位讀者對於限制條件的寫法都不會有什麼疑問,只需要把所有點之間的三角不等式關係列出來,再加上限制起始頂點的最短路徑權重為0即可。然而,這個問題是「最短路徑」問題,為何我們的目標會是「最大化」目標頂點的最短路徑權重 dt 呢?
首先,讓我們先討論如果改成「最小化」目標頂點的最短路徑權重,會對整個線性規劃問題產生什麼樣的變化。既然所有邊都是非負的,而我們的目標又是最小化最短路徑權重,那有一組最佳解顯而易見,就是將所有頂點的最短路徑權重都設為 0,因為 0 ≤ 0 + w(u,v) 會完美符合所有限制條件。這樣雖然滿足限制,但求出的解答會變得毫無意義,根本沒有算出真正的最短路徑,因此最小化明顯不可行。
那最大化為什麼就可以呢?難道不會與題意不符或是讓最短路徑權重變得無限大嗎?這時候我們可以先觀察起始頂點 s,假設有一條邊從 s 到某個頂點 a,我們可以列出三角不等式:da ≤ ds + w(s,a),將 ds = 0 代入後可得 da ≤ w(s,a)。這代表什麼意思呢?意思是因為 ds 本身已經被死死固定在 0,因此 da 的大小就會被頂點 s 與頂點 a 之間的邊長權重給限制住,最大的極限就是 w(s,a),不可能再更大了。同理,若有另一條邊由頂點 a 通往頂點 b,則 db 的大小就會被限制在 w(s,a) 和 w(a,b) 兩者加總的數值內,並不可能超過。因此,這邊的最大化指的是,任意最短路徑權重 dv 都會從0開始,並且逐漸膨脹到貼合某一段連續邊長的總和,其值恰好就是這段最短路徑的權重總和。
那為什麼這樣可以計算出「最短」路徑權重呢?用最直白的方式來說,最短路徑當中的「最短」,會交給眾多的三角不等式來自然的交集出一個邊界。對於某個頂點 v 來說有些條件(路徑)會得到 dv ≤ 10,而有些會得到 dv ≤ 5。這時候我們對 dv 用最大化來計算時,它會從 0 開始不斷變大,並且先抵達 dv = 5 這個計算結果,此時兩個條件的限制都尚未被打破。但當 dv = 6 時,其中較小的條件 dv ≤ 5 並不能達成,因此透過最大化最短路徑權重 dv,我們反而可以順利得到最短路徑的答案,也就是 dv = 5。
總結
今天的專欄我們介紹了如何從問題當中去建模線性規劃,先透過現實生活的常見問題舉例,再討論到差分約束系統以及圖論問題。而在經典圖論問題單對最短路徑問題當中,我們找出本題的決策變數可以定義為最短路徑權重 dv,而限制條件可以透過三角不等式來列出。最後,我們聚焦在如何定義此最佳化問題,並點出一個常犯的錯誤:並不能因為是「最短」路徑問題,我們就輕易將最佳化問題定義為「最小化」。與之相反,本問題的決策變數與限制條件的選擇,反而會讓我們試圖將每一個決策變數給「最大化」,並透過限制條件的輔助,自然求得「最短」路徑的答案。
關鍵詞
線性規劃、差分約束系統、三角不等式
上一篇:線性規劃(3)
回首頁:資訊考點新
我要諮詢