誤打誤撞破解兩道難題的「線性規劃之父」丹錫

誤打誤撞破解兩道難題的「線性規劃之父」丹錫
Image Credit: INFORMS影片截圖
我們想讓你知道的是

丹錫因為一次上課時遲到,誤打誤撞下竟解決了兩道當時未有答案的難題。

丹錫(George Dantzig)的父母在巴黎大學讀書時認識,其後移民至美國定居。在1914年11月8日出生的丹錫,高中時期已對數學有興趣,特別是幾何學——他的父親(Tobias Dantzig)是一名數學家,提出複雜的問題讓他挑戰。

其後丹錫進了馬里蘭大學,取得數學及物理學位,並於密芝根大學取得數學碩士學位。他喜歡統計學,卻對其他抽象數學興趣不大,於是離開學界到美國勞工統計局工作。兩年後他獲加州大學柏克萊分校取錄,攻讀博士學位,師承統計學家內曼(Jerzy Neyman)。

二戰爆發後,丹錫暫停學業加入美國空軍負責統計工作,戰後才完成博士學位。雖然獲邀留在大學任教,但他決定回到空軍成為數學顧問。1952年,他加入蘭德公司(RAND Corporation)的數學分部,1960年回到加州大學柏克萊分校的工業工程學系擔任教授。

丹錫最著名的數學貢獻是發現了「單純形法」(simplex method),有效快速解決一些規劃問題,例如以最符合成本效益的方式分配工作、製造產品等。他更因這個發現開拓了線性規劃(linear programming)的領域,在經濟學、運籌學(operation research)等學科有廣泛應用,丹錫亦因此被視為線性規劃之父。[1]

據丹錫所說,這個發現亦跟他在讀博士期間,內曼在課上的兩道著名「習題」有關。

在他讀博士的第一年,丹錫上內曼其中一堂課時遲到,進課室時已開始上課。他看到黑板上有兩道習題,於是抄在筆記上回家解決。這兩條問題比平時困難,數日後他把功課交給內曼,並為自己花了那麼長時間完成道歉。內曼只叫他把答案放到其辦公桌上。

vlcsnap-2018-11-08-13h01m54s497
Image Credit: INFORMS影片截圖

丹錫起初有點猶豫——內曼桌上有太多東西,他擔心功課會被淹沒、不見天日。大約6星期後,內曼在某個星期日早上8時敲門,興奮地告訴他︰「我剛寫完你其中一篇論文的介紹,快點讀完,好讓我寄出去發表。」

原來在那一堂課開始時,內曼向班上提到兩個統計學上未解決的難題——但丹錫遲到,錯過了這一部份,更誤會兩條問題是功課習題。在內曼協助下,第一道難題的答案在1940年發表。

一年後,丹錫為未想到博士論文題目感到擔憂,內曼知道後告訴他,只要把兩條問題的解答合起來,就會接納作為其博士論文。[2]

他第二道「習題」的答案未有立即發表在期刊上,直到1950年,數學家華特(Abraham Wald)打算把新發現投稿到期刊,卻被告知結果跟丹錫的發現類似,於是寫信給丹錫,雙方同意下論文聯名發表。

自1966年起,丹錫在史丹福大學擔任運籌學及電腦科學教授,後來成為同一大學的運輸科學教授,達退休年齡繼續教學、做研究。2005年5月13日,丹錫在加州史丹福逝世,終年90歲。

相關文章︰

註︰

  1. 蘇聯經濟學家簡托羅維奇(Leonid Kantorovich)在1939年的發現亦令他被視為線性規劃之父,1975年跟荷蘭經濟學家高普曼斯(Tjalling Koopmans)同獲瑞典中央銀行紀念阿爾弗雷德·諾貝爾經濟學獎(通稱諾貝爾經濟學獎)。
  2. 想了解兩條題目的話,可以參考他的博士論文題目︰I. Complete Form Neyman-Pearson Fundamental Lemma. II. On the Non-Existence of Tests of Student's Hypothesis Having Power Functions Independent of Sigma.,相應兩篇期刊論文分別可在以下連結讀到︰

參考資料︰

核稿編輯:王陽翎

或許你會想看
更多『評論』文章 更多『科學』文章 更多『Kayue』文章
Loader