高中数学课程里的线性规划.pdfVIP

科學月刊【數‧生活與學習】專欄‧百年 6月 高中數學課程裡的線性規劃 單維彰‧ 100 年5月 16日 所謂線性規劃 (Linear Programming) 在其（經過整理的）數學形式上，是求n 元一次目標函數P c x c x c x 在滿足m 個一次不等式 1 1 2 2 n n a x a x a x b 11 1 12 2 1n n 1 a x a x a x b 21 1 22 2 2n n 2 … a x a x a x b m1 1 m 2 2 mn n m 之限制條件下的最小值。（我們可以只討論m n 的情況。） 就像許多數學概念一樣，線性規劃的初步想法可以追溯到更早以前，但是我 們今天認識它的方式乃至於稱呼它的名字，乃是具體地誕生於西元 1948 年。名 字之中的「線性」(linear) 表現了它在數學技術上的特徵：求最小值的「目標函 數」以及設定條件的不等式，都是一次式，也就是線性的。而「規劃」(programming) 其實是軍事用語，意指一套兵力派遣、火力部署和補給作業的規劃；這個字表現 了這套數學想要解決的典型問題。 但是讀者不該將「線性」字面地理解為「直線的」。這是一部份高中學生具 有的迷思：因為二元一次方程式 ax by c 的圖形是平面上的直線，就「自然 地」以為三元一次方程式 ax by cz d 的圖形是空間中的直線—不是的，它 是空間中的平面。一般而言，n 元一次方程式a x a x a x b 的圖形是n 1 1 2 2 n n 度空間裡，少了一個維度（也就是n-1 維）的「平面」，稱為超平面 (hyperplane) 。 而滿足n 元一次不等式a x a x a x b 的解，就是被超平面分割的兩個「半 1 1 2 2 n n 空間」之一。 線性規劃在 1960 年代因為美國報紙的宣揚而成為家喻戶曉的數學明星。做 為明星所達到的最高峰，或許是 1975 年的諾貝爾經濟獎，受獎者是兩位線性規 劃的先行學者，得獎的原因是他們「在資源最佳分配理論上的貢獻」。而線性規 劃的基本性質，和它的基本解法「單形法」(Simplex Method) ，都在1950 年代的 前期就確立了。 當李新民教授在1966 年前後，為東華書局根據民國53 年版之課程標準編撰 高中數學教科書時，很有創意地將線性規劃的「淺薄特例」：n 2 的情況，寫進 了教科書。將一個還在尖端研究領域的數學課題寫進高中數學教材，應當是一件 令人歡欣鼓舞的事，很有趣也很有啟發性。李教授後來成為中央大學復校（成為 大學）後的首任校長。 理論上，排除一些無聊的情況之後，滿足限制條件的點，是n 維空間中被m 個超平面圍成的區域；稱為多胞形 (polytope) ；這個看起來很時尚的名字，其實 在二維（平面上）就是多邊形（例如三角形、四邊形等），在三維（空間中）就 是多面體（例如四面體、立方體、角錐體等）。數學定理保證了上述多胞形必然 是「凸的」，所以如果目標函數在限制條件之下有最小值，則最小值一定發生在 此多胞體的某一個頂點上 。 這是一個美好的定理 ，但是實行上頗為困難。首先，求取頂點坐標等於要算 一個n 元一次聯立方程式的解，在高中學習了高斯消去法求解三元一次聯立式， 我們可以推廣此算法解n 元一次式，但是其複雜的程度不是n:3 ，而是n3 :27 。讀 者只要代入n=10 試試看，就可以想像其複雜的程度；而n=10 是實際應用時常 見的未知數個數。其次，頂點的個數非常多，而且不容易判斷。在m 個條件中 任選n 個，就能計算一個交點（也就是n 個超平面交於一點）。高中生可以了解， 這是一個組合問題，限制條件形成的凸多胞體可能有Cm 個交點。讀者只要