【逸聞舊事】喬治·丹齊格：從誤解的難題到線性規劃（一）

來源: cw 於 2024-07-07 23:00:52 [檔案] [博客] [舊帖] [給我悄悄話] 本文已被閱讀：次 (5431 bytes)

本文內容已被 [ cw ] 在 2024-07-08 07:25:39 編輯過。如有問題，請報告版主或論壇管理刪除.

唐宋韻在他前幾天的一篇文章裏介紹了電影《心靈捕手》（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 ) 又重複解決了。沃爾德準備發表他的工作時，才得知丹齊格當年已經解決了這個問題。結果最後這個問題的解答以他們二人的名義發表了。而丹齊格包含在他的博士論文裏的那個問題，後來幫助他發現了線性規劃問題最有名且最有用的單純性算法。後麵我們再更仔細聊這一點。

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