線性規劃(Linear Programming) | 科學Online - 國立臺灣大學

讓我們就從下面的例子說起，來介紹什麼是線性規劃：. 為預防禽流感，營養師吩咐雞場主人每天必須從飼料中提供至少84 單位的營養素A 、 Saturday16thJuly2022 16-Jul-2022 人工智慧 化學 物理 數學 生命科學 生命科學文章 植物圖鑑 地球科學 環境能源 科學繪圖 高瞻專區 第一期高瞻計畫 第二期高瞻計畫 第三期高瞻計畫 綠色奇蹟－中等學校探究課程發展計畫 關於我們 網站主選單 線性規劃(LinearProgramming) 臺北市立第一女子中學數學科蘇俊鴻老師 讓我們就從下面的例子說起，來介紹什麼是線性規劃： 為預防禽流感，營養師吩咐雞場主人每天必須從飼料中提供至少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\ge0,y\ge0\\7x+2y\ge84\\x+2y\ge24\\3x+2y\ge60\end{array}\right.\) 。

同時，目標函數(即飼料成本)為\(5x+4y\) 。

這個問題便是典型的線性規劃問題。

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

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

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

因此，當\(x=18,y=3\) 時，最小值為\(5\times18+4\times3=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\lex\le7\\0\ley\le4\\x+y\le9\\4x+5y\ge30\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\times7+8\times\frac{2}{5})=3820\) ， 而\((7,\frac{2}{5})\)附近的\((7,1)\) 代入，得\(100(5\times7+8\times1)=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)\) 就一定是最佳解了。

線性規劃在高中數學中一直佔有相當重要的地位，儘管受限於數學知識，高中課程只能介紹平面(二維)的狀況，算是線性規劃中的「淺薄特例」。

但從數學建模的觀點，高中課程的線性規劃卻是一個讓人可以理解如何「利用數學解決實際問題」的極佳例子。

Tags:二元一次不等式,可行解區域,整數解,目標函數,線性規劃 前一篇文章下一篇文章 您或許對這些文章有興趣 海芭夏(HypatiaofAlexandria) 泰勒多項式(2)（TaylorPolynomials(2)） 惠更斯(ChristiaanHuygens)專題 發表迴響Cancelcommentreply 你的電子郵件位址並不會被公開。

必要欄位標記為*迴響名稱* 電子郵件* 個人網站 驗證問題* 1+2= 熱門文章 導出單位 細胞膜運輸物質的方式 綜合除法 比爾定律與吸收度 點到直線的距離公式 絕對壓力 白努利原理 醣類的組成與分類 棕色脂肪 穿透式電子顯微鏡 總點閱排行 點到直線的距離公式 細胞膜運輸物質的方式 比爾定律與吸收度 混成軌域 準確度和精確度 腎素-血管收縮素-醛固酮系統 穿透式電子顯微鏡 好站鏈接 科學online粉絲專頁 Insertmathas Block Inline Additionalsettings Formulacolor Textcolor #333333 FormulaID Formulaclasses TypemathusingLaTeX Preview \({}\) Nothingtopreview Insert