作者 | 吳昊 & 編輯 | 羅數君
文 1967字 閱讀時間約 5分鐘
導語：
你是否有過這樣的經歷，在琳琅滿目的商品前無法抉擇，希望在預算內買到最有價值的東西？其實無論在個人的日常生活還是工作中，懂得線性規劃的數學知識都將使你事半功倍。想了解這個數學知識嗎？請讀者們看今天的文章吧！
假如給你100塊錢，你會做什麼？學生們可能會買一本日趨昂貴的教材，家長們可能會給孩子買一套網絡課程，加班族們可能會買一張咖啡店的會員卡……哪個選擇最優呢？這就要看每個人心中，每件東西的價值了。
博深購物城最近舉辦了這樣一場活動：每一個到店中的顧客都會領到100塊錢的代金券，可以在購物城中任意挑選商品消費。皮卡丘轉了一圈，列了一個他看中的物品清單：
皮卡丘的目的，就是在不超過100塊錢的前提下，最大化他的皮卡皮卡！可是由於他的手力量有限，只能拿總共不超過30克的物品。轉化成數學的語言，這就是說：
給定兩個條件15m + 20f + 12s ≤100，以及5m + 5f + 7s ≤ 30，最大化25m + 35f + 40s。當然，由於物品的數量只能是非負數，所以我們規定m, f, s ≥0。同時，由於以上物品都可以按重量賣，而重量可以是小數，所以我們不規定這三個變量是整數。
圖片來源：zh.fanpop.com/
這種生活中十分常見的最大化問題叫作線性規劃（linear programming）問題。它的嚴格定義是：已知x1, x2, x3 … ≥ 0，並給定一些線性的條件a1x1+a2x2+a3x3 …≤ c，最大化線性函數d1x1 + d2x2 + d3x3 …的取值。
我們來舉幾個最簡單的例子：x + y ≤ 3，-2x + 5y ≤ 3，x + 2y ≤ 2，x和y都非負，要最大化的線性函數 f = 6x + y。這該怎麼解決呢？我們可以畫一張圖：
這張圖裡的橫軸為x，縱軸為y，三條線對應的不等式已在圖中標出，而同時符合三個不等式，並滿足兩個變量均非負的可行域（可取值範圍）就是藍色的這片區域。在這片區域上，我們畫出 6x + y 的等值線（比如6x + y = 1，6x + y=2，6x + y = 3等），發現其中函數6x + y 在(2, 0)這一點的取值最大。因此，我們就可以得到所求的最大值為12。
注釋：等值線是製圖對象某一數量指標值相等的各點連成的平滑曲線。
圖片來源：deansforimpact.org/content-of-thinking/
二元線性函數的等值線很容易找到：固定函數的值，只需解一個二元一次方程即可， 比如6x + y = 1。多元線性函數稍複雜一點，因為我們要找到的不再是等值線，而是使函數值相等的高維平面，比如三維平面6x + 3y + 7z = 5。
那麼問題來了：在高維空間中，就算我們能找出所有等值面，那如何看出哪個與可行域相交的等值面取值是最大的呢？畫出來是不太可能了，那該如何計算呢？
我們先來證明一個引理：使線性函數 f 取值最大的點一定是不等式對應的平面的交點，也就是可行域的頂點，而不會是可行域內部的點。
注釋：引理是數學中為了取得某個更好的結論而作為步驟被證明的命題，其意義並不在於自身被證明，而在於為達成最終目的作出貢獻。
圖片來源：tenor.com/view/garfield-thinking-think-get-to-work-gif-12041090
這個看似很複雜的定理證明卻十分簡潔明了：任意一個多維的多面體裡，任取一個點v，它對應的函數值 f(v) = r。如果它不是頂點，那麼經過v的任何平面（多面體本身的表面除外）都會把多面體切成至少兩塊（如果是凹多面體的話可能多於兩塊），v 所在的等值面 f = r 也不例外。它也會把可行域這個多面體切成至少兩塊，也就是說，等值面的兩邊都有可行域。又因為我們的函數 f 是線性的，所以兩邊中一定會有一邊取值大於 r，所以 v 取得的值 r 一定不是最大值。
那麼，如果等值面恰好就是多面體本身的一個表面呢？那麼這個表面也一定會經過至少一個頂點，引理證明完畢。
圖片來源：giphy.com/gifs/cheer-cheering
知道了這個性質之後，我們就可以用一個最基礎的方法——枚舉法：把多面體的每個頂點代入函數進行計算，最大的值就是我們想要的結果。
那麼，皮卡丘最多能得到多少皮卡皮卡呢？我們一共有5個不等式（包括3個非負變量）。每3個平面都會產生0個，1個，或無窮個交點。在本題目中，每三個不等式都會產生1個交點，但有些交點並不在可行域內。根據排列組合的知識，我們一共可以得到10個交點。但是事實上，在10個可能的交點裡，只有6個滿足所有的不等式，而這六個交點裡，皮卡丘能獲得皮卡皮卡的最大值是198.75。此時，m = 0, f = 4.25, s = 1.25。也就是說，皮卡丘要拿4.25單位的番茄醬，1.25單位的飼料以最大化他的皮卡皮卡。
圖片來源：stockphoto.com/illustrations/aha
在現實問題中，我們通常會有很多個變量和條件，這時枚舉法就太耗時間了。線性規劃最常用的幾個方法包括單純形法、橢球算法、內點法等，比枚舉法快得多。有興趣的讀者們可以深入探索一番哦！
假如給你一百塊錢，你會怎麼花呢？下一次，不妨建個模最大化你的皮卡皮卡~
喜歡這篇文章嗎？歡迎給我們留言，探討有趣的數學問題，如果你還想看其他的相關內容，也可以向我們提出來哦！