線性規劃(Linear Programming)

線性規劃(Linear Programming)
臺北市立第一女子中學數學科蘇俊鴻老師

讓我們就從下面的例子說起，來介紹什麼是線性規劃：

為預防禽流感，營養師吩咐雞場主人每天必須從飼料中提供至少 84 單位的營養素 A 、
至少 72 單位的營養素 B 和至少 60 單位的營養素 C 給他的雞群。

這三種營養素可由兩種飼料中獲得，且知第一種飼料每公斤售價 5 元並含有 7 單位的營 養素 A ，3 單位的營養素 B 與 3 單位的營養素 C ；第二種飼料每公斤售價 4 元並含有 2 單位的營養素 A ， 6 單位的營養素 B 與 2 單位的營養素 C 。

若雞場主人每天使用 x 公斤的第一種飼料與 y 公斤的第二種飼料就能符合營養師吩咐，並且想以最少的飼料成本來達到雞群的營養要求，則x, y 的值為何？最少的飼料成本又是多少？

換言之，雞場主人想要以「最少」的飼料成本來達成雞群的營養要求，以達到預防禽流感的目的；將成本寫成算式，就稱為目標函數。

該如何配置這兩種飼料的使用？首先，我們當然要先了解各種條件的限制。若是依條件列出的算式，以及「目標函數」都是一次式，我們就將此類的問題稱為「線性規劃」。

以上述問題來看，設每天使用第一種飼料 \(x\) 公斤；第二種飼料 \(y\) 公斤，

將條件列出，可得二元一次聯立不等式 \(\left\{ \begin{array}{l} x \ge 0,y \ge 0\\ 7x + 2y \ge 84\\ x + 2y \ge 24\\ 3x + 2y \ge 60 \end{array} \right.\) 。

同時，目標函數(即飼料成本)為 \(5x+4y\) 。這個問題便是典型的線性規劃問題。

進而，我們將滿足聯立不等式的解區域畫出，稱為可行解區域，如圖一。

接著，畫出通過原點的直線 \(5x+4y=0\) ，讓其在可行解區域內移動。

不難發現形如 \(5x+4y=k\) 的一組平行線移動時，在點 \((18,3)\) 時會有最小值。

因此，當 \(x=18,y=3\) 時，最小值為 \(5\times 18+4\times 3=102\)

(關於可行解區域的繪製及目標函數最大、最小值的求法，請參閱〈二元一次不等式〉一文)。

此時，點 \((18,3)\) 就稱為最佳解，而上述利用平行直線來判定最佳解的方法，就稱為平行線法。

因此，依問題設定兩個變數 \(x,y\) ，列出不等式組及目標函數，

再依二元一次聯立不等式繪製圖形，找出可行解區域。

接著，在可行解區域內，找到點 \((x,y)\) 滿足目標函數的極值，

此時的點 \((x,y)\) 叫做問題的最佳解，這樣的程序正是高中課程中處理線性規劃的標準作法。

不過，當遇有整數解限制，而最佳解並非整數時，該如何處理？值得我們好好研究一下。

同樣地，還是用下面的例子來說明：

某貨運公司有載重4噸的小貨車7輛，載重5噸的大貨車4輛及9名司機，

現在受託每天至少要運送30噸的煤，且人、車每天只能出動一次。

若小貨車開一趟要500元，大貨車要800元，怎樣調度才能最省錢？

設派出小貨車 \(x\) 輛，大貨車 \(y\) 輛，且 \(x,y\) 為整數，

依題意可列式為 \(\left\{ \begin{array}{l} 0 \le x \le 7\\ 0 \le y \le 4\\ x + y \le 9\\ 4x + 5y \ge 30 \end{array} \right.\) ，此聯立不等式的解如圖二。

而所求為 \(500x+800y\) 的最小值，

即目標函數\(=500x+800y=100(5x+8y)\) 。

利用平行線法，不難發現最佳解為 \((7,\frac{2}{5})\) 。

然而，\((7,\frac{2}{5})\) 並非問題所求的整數解。

那麼，如何找到滿足目標函數的最小值之整數解？

以往的課本常交待就在 \((7,\frac{2}{5})\) 的附近找尋幾個整數解，再帶入判斷即可。

這樣的作法，並不能保證所找到的整數解必為最小值，而且該找尋幾個整數點代入才足夠呢？

以上述問題為例，在的附近的整數解有 \((7,1)\) 、\((6,2)\) 兩點，

不過，這兩個點都不是最佳整數解。

以下提供一個可以保證所求必為最佳整數解的作法(但不一定迅速)：

由於 \((7,\frac{2}{5})\) 代入，得 \(100(5 \times 7 + 8 \times \frac{2}{5}) = 3820\) ，

而 \((7,\frac{2}{5})\) 附近的 \((7,1)\) 代入，得 \(100(5\times 7+8\times 1)=4300\) 。

因此，只需依序考慮 \(5x+8y=39,5x+8y=40,5x+8y=41\)，

以及 \(5x+8y=42\) 等幾條直線在可行解區域中是否有整數解即可。

就此例而言，當 \(5x+8y=41\) 時，恰有點 \((5,2)\) 滿足，

因此，\(x=5,y=2\) 為最佳整數解，而最少運費為 \(4100\) 元。

倘若這幾條直線都沒能找到整數解，

那麼，一開始在 \((7,\frac{2}{5})\) 附近所找的 \((7,1)\) 就一定是最佳解了。

線性規劃在高中數學中一直佔有相當重要的地位，儘管受限於數學知識，高中課程只能介紹平面(二維)的狀況，算是線性規劃中的「淺薄特例」。但從數學建模的觀點，高中課程的線性規劃卻是一個讓人可以理解如何「利用數學解決實際問題」的極佳例子。