整數解

線性規劃(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\) 。這個問題便是典型的線性規劃問題。

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