资源预览内容
第1页 / 共3页
第2页 / 共3页
第3页 / 共3页
亲,该文档总共3页全部预览完了,如果喜欢就下载吧!
资源描述
科學月刊【生活與學習】專百科學月刊【生活與學習】專百 6 月月 高中學課程的線性規劃高中學課程的線性規劃 單維彰單維彰100 5 月月 16 日日 所謂線性規劃 (Linear Programming) 在其(經過整的)學形式上,是求 n m 元一次目標函在滿足個一次等式 之限制條件下的最小值。 (我們可以只討的情況。) 1 122nnPc xc xc x11 112211nna xa xa xb 21 122222nna xa xa xb 1 122mmmnna xaxaxb m mn 就像許多學概一樣,線性規劃的初步想法可以追溯到早以前,但是我 們今天認它的方式乃至於稱呼它的名字,乃是具體地誕生於西元 1948 。名字之中的線性(linear) 表現它在學技術上的特徵:求最小值的目標函 以及設定條件的等式 , 都是一次式 , 也就是線性的 。 而 規劃 (programming) 其實是軍事用語,意指一套兵派遣、火部署和補給作業的規劃;這個字表現 這套學想要解決的典型問題。 但是者該將線性字面地解為直線的 。這是一部份高中學生具 有的迷思:因為二元一次方程式 axbyc 的圖形是平面上的直線,就自然 地以為三元一次方程式 axbyczd 的圖形是空間中的直線是的,它 是空間中的平面。一般而言,n元一次方程式1 122nna xa xa xb的圖形是n空間,少一個維 (也就是n-1 維) 的 平面 ,稱為超平面 (hyperplane)。 而滿足n元一次等式1 122a xa x的解 , 就是被超平面分割的個 半空間之一。 nna xb線性規劃在 1960 代因為美國報紙的宣揚而成為家喻戶曉的學明星。做 為明星所達到的最高峰,或許是 1975 的貝爾經濟獎,受獎者是位線性規 劃的先學者,得獎的原因是他們在資源最佳分配上的貢獻 。而線性規 劃的基本性質,和它的基本解法單形法(Simplex Method),都在 1950 代的 前期就確。 1966 前後 , 為東華書局根據民國 53 版之課程標準編撰當新民教授在 高中學教科書時,很有創意地將線性規劃的淺薄特 :2n 的情況,寫進 教科書。將一個還在尖端研究域的學課題寫進高中學教材,應當是一件 人歡欣鼓舞的事,很有趣也很有啟發性。教授後成為中央大學校(成為 大學)後的首任校長。 上,排除一些無聊的情況之後,滿足限制條件的點,是n維空間中被m 個超平面圍成的區域;稱為多胞形 (polytope);這個看起很時尚的名字,其實 在二維(平面上)就是多邊形(如三角形、四邊形等) ,在三維(空間中)就是多面體(如四面體、方體、角錐體等) 。學定保證上述多胞形必然 是凸的 ,所以如果目標函在限制條件之下有最小值,則最小值一定發生在 此多胞體的某一個頂點上。 (也就是n個超平面交於一點) 。這是這是一個美好的定,但是實上頗為困難。首先,求取頂點坐標等於要算 一個n元一次方程式的解,在高中學習高斯消去法求解三元一次式,我們可以推廣此算法解n元一次式,但是其複雜的程是n:3,而是3n:27。 者只要代入n=10 試試看,就可以想像其複雜的程;而n=10 是實際應用時常 的未知個。其次,頂點的個非常多,而且容判斷。在m個條件中 任選n個,就能計算一個交點高中生可以解, 一個組合問題,限制條件形成的凸多胞體可能有m nC個交點。者只要試試 看15 10C就能感受交點有多麼大!而m=15 在實際應用時還算太多。但是這些 交點卻一定是多胞體的頂點(稍後在平面上再解釋) ,我們還須要一些並容 的步驟判斷哪些交點是頂點? 因此,應用學家(和經濟學者)並直接使用上述美好的定,設計求解 線性規劃問題的演算法(否則,那個貝爾獎是是得太輕一點?) 。單 形法是最早發明的算法,雖然這個方法在上如後發明的種算法,但是 實務經驗上卻相當可靠,所以至今仍是最普遍被採用的算法。單形法的重點在於 效,它使得我們必嘗試目標函在每一個頂點的值,就能找到發生極小值的 那個頂點。 當2n ,也就是目標函與限制條件都只有個變,我們可以限制在平 面上探討它。此時我們習慣將1x寫成x,2x寫成y,而限制條件就是由m條直線kkka xb yc,1k , 2, , m圍成的凸多邊形。事實上,每條直線就有一個交 點,如五個條件對應的五條直線一共(最多)有5 210C 個交點,須要求解二 元一次方程組10遍(通常包含0x 和0y 個條件,所以有條直線就是x 軸和y軸,簡化問題) 。但是我們可以在平面上看到這m條直線,很容 假思地新民校於民看到頂點的大位置,只要算出形成頂點的交點即可,而必經 過計算交點然後判斷是否為頂點的步驟。 長國57版的東華版學課本引進2n 之線性規劃淺薄特 時,只有一個題。其設計目標看只想要結二元一次等式的解區域 (平面上的多邊形) ,並順點到為止地介紹一項學新知(線性規劃) 。用今天 的法,就是在教材添加一點花絮或欣賞 。當時,他並未明求解的 方法及由,只是 (解法)一般將至為繁複,但由線性規劃之,960-2x-y之極大或極小值,將在五邊形之頂點出現 。然後就是頂點表法。習題之中, 題是解條二元一次等式的操作習,題習畫解區域,一題習由 解區域找等式,只有一個文字應用題。 如果將民國5361間的學教材當作台灣現代學課程的第一代, 則6272間的第二代四種版本的學課本中,仍然只有校長的東華版在第 冊第四章總複習的4-4等式與極值問題,放一個線性函的極限題(8) ,內容就是線性規劃。這第二代的教材採用平直線系 (xyk)解釋xy的最大值發生在一個四邊形區域的某頂點。這份教材 沒有提到頂點法 ,甚至沒有設計似的習題;整個教材中,僅此一個題。 平的章等式的 2-空間中 (也就是維) 討線性規劃在第三代學課程(民國7287,全國統一使用的部編版)忽然變成一個重要課題 , 在第一冊第三章 直線方程式與二元一次等式 的 3-4 二元一次等式與線性規劃,正式躍上標題。這一冊課本平均每節只 有10.6頁,而3-4佔19頁,可是一個重點章節 。3-4的內容完整地從 直線系發展到頂點法,並介紹頂點坐標是整的題型。 第四代學課本又回到一綱多本的局面 , 共同的依據是民國8410月公布 高級中學學科課程標準 。這一代的課本保存部編版的線性規劃,但是 移到高中三級選修的學甲或,各版本都為線性規劃獨設 一節。當時認為學甲適合準備進入、工、醫、農、商學域的高中生,而 學乙則是為文、法、教育、藝術域的學生設計的。 第四代課本中的南一版最接近前代部編版的內容,放在第二 3線性規劃 ,佔18頁,課後設計7道習題,外加2個綜合習題。相 對於部編版,只在格子點問題上做簡化。除康熙版只用13頁,各版本都 盡情發揮這個課題,三民版用20頁,翰版24頁,正中版30頁,騰版甚 至還框一個線性規劃基本定! 即使2n , 目標函( , )zf x yaxby仍然應該在1n 。高中生已經知道zaxby亦即0axbyz是空間中的平面,稱它為。 當( , )x y在限制條件圍成的凸多邊形區域內,相當於( , , )x y z形成上的一個凸多邊形。想像我們把一張紙平鋪在桌面上畫一個凸多邊形,然後隨意拎起這張 紙,讓它斜在空中(得卷曲) ,則紙上多邊形的最高點,當然發生在某個頂 點或某個頂點所的整條邊!大一微積分的學生將會知道,目標函( , )f x y的法。頂點 法的思過去 半個一點。可次偏導恆為,所以在區域的內部沒有界點,因此它的極值必定發生 在邊界上。同討邊界上的函,也同樣沒有界點,所以極值必定發生在頂2的線性規劃問題,其實還有也許自然的 自從獨佔教科書市場15的部編版課本之後,線性規劃就在高中學課程 站穩腳跟。然而,與國際學教材相比,線性規劃仍是本國之獨有特色之一。 以二元一次等式找到凸多邊形之可解區域 , 然後以平直線系推導 維過程,失為一本線性規劃教科書的絕妙入門教材;作為學應用之通 或欣賞,也失為高中教材的好範。但是,將它作為一個課程主題處 ,稍嫌孤於核心知之外,又未能掌握一般性問題的關鍵,則可以考n 看世紀的教材發展程,在整個高中學教育的原則之下,重新思考其適 當性。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号