喬治·丹齊格:從誤解的難題到線性規劃(一)

唐宋韻在他前幾天的一篇文章裏介紹了電影《心靈捕手》(Good Will Hunting)。電影裏麵的主角是一個麻省理工學院的清潔工,把黑板上一個數學問題誤以為是作業,當即在黑板上便把它解決了。但實際上這個問題是一個未解的數學難題,自然引起人們的注意。。。

學數學的大概都知道,解題這個情節是以數學家喬治·丹齊格(George Dantzig)的真實故事為藍本的。當然電影裏麵的人物的其它故事和丹齊格完全沒有關係。因為我對優化這個領域曾經比較熟悉,按唐兄建議,分享一下丹齊格的原版故事。也順便介紹一點和丹齊格最重要的工作相關的線性規劃問題。線性規劃現在幾乎是所有理工科學生都會學一點的。它不僅有很廣泛的應用,也有很多優雅的審美性質。

導師傑裏·紐曼

丹齊格和他的導師傑裏·紐曼(Jerzy Neyman)師生倆都是20世紀泰鬥級的數學家,在各自領域中都是大家繞不過去的豐碑。他們的工作不僅給成千上萬的數學後輩提供了飯碗,還因為兩人做的都是應用數學,也深入影響到現代社會每一個人的日常工作和生活。

傑裏·紐曼Jerzy Neyman

傑裏·紐曼是波蘭出生的數學家,在華沙大學取得博士學位。前半生在波蘭的各個研究院和英國倫敦大學學院,後半生在加州大學伯克利分校。紐曼引入了統計假設檢驗(Statistical Hypothesis Testing)中的“置信區間”(confidence interval)概念,並與埃貢·皮爾遜(Egon Pearson)合作提出了“紐曼-皮爾遜引理”,引入了統計假設檢驗的零假設,奠定了現代統計推斷理論的基礎。這些概念和工具現在廣泛應用在醫學、經濟學和社會科學等領域的各種統計分析中。對於現在學習統計學的本科和研究生學生而言,零假設、置信區間、類型一錯誤和類型二錯誤等,都是學習中的重點。

紐曼不僅在學術上成就斐然,還培養了近40個博士生,很多在統計學和其他領域取得了重大突破。丹齊格就是其中之一。而電影中的做題故事,就發生在他手下。

黑板上的”作業“

丹齊格是美國人,父親也是一位數學家。1939年,丹齊格是加州大學伯克利分校的一名研究生,修著紐曼教的統計學課。一天,丹齊格遲到了。走進教室後,發現黑板上有兩個數學問題。他以為是布置的作業,便把它們抄下來帶回家努力解答。幾天後,他把解答交給了紐曼,還以為已經錯過了”作業“的上交日期。幾周後,紐曼告訴他,這兩道題並不是作業,而是當時統計學中著名的未解是否有解答的難題(open problem)。一年後,丹齊格和紐曼討論自己的博士論文選題時,紐曼不當回事地說,把那兩個問題的解答放到一個文件夾裏交上來,就足夠作為丹齊格的博士學位論文了。

喬治·丹齊格George Dantzig

丹齊格的博士論文最終隻用了其中的一個問題。另外一個問題因為沒有發表,多年後被另一個數學家亞伯拉罕·沃爾德 ( Abraham Wald ) 又重複解決了。沃爾德準備發表他的工作時,才得知丹齊格當年已經解決了這個問題。結果最後這個問題的解答以他們二人的名義發表了。而丹齊格包含在他的博士論文裏的那個問題,後來幫助他發現了線性規劃問題最有名且最有用的單純性算法。後麵我們再更仔細聊這一點。

丹齊格的這個故事當然很少見,不然不會成為傳奇。丹齊格後來自己也說過,如果當初知道那是未知解答的難題,他那時候也許就不會那麽積極努力地去解決它們。畢竟這種問題已經被很多人嚐試過且未能成功。但是把未知是否有解答的問題放進博士生資格考試裏的事,還真有學校幹過。我讀書的時候,我前一屆的師兄們的資格考試裏就有這種不知是否可解的題。但我還沒有聽說過誰當場解決過這種題。放這種問題到博士生的資格考試裏也可以是有理的:看看你對相關領域是否很了解,還有你做研究的能力——雖然不知道有沒有解答,但是你可以說說你對這個問題的看法和可能去研究它的角度和途徑。當然,在考試中遇上這種問題是很煩人的。因為你如果不知道它是未解的問題,你就可能在它上麵浪費很多時間,影響你解答其他有解的問題。

請您先登陸,再發跟帖!