線性規畫之父 丹齊格
1947年，美國數學家丹齊格(George B.Danzig)提出了線性規劃問題的一般模型和求解線性規劃問題的單體演算法。從此，線性規劃理論和應用得到了廣泛發展。
原來，在第二次世界大戰期間，丹齊格就在美國空軍的一個小組從事資源分配和計畫編制的工作。大戰以後，他回到伯克利加州大學，並取得了博士學位。這時，他成為美國空軍審計長的數學顧問，從事計畫工作機械化的研究。
作為一個數學家，首先要把問題表達清楚，這就是所謂建立模型的工作。1940年代，美國勞工統計局的里昂惕夫(W. Leontief) 所做投入—產出模型（input-output model）使丹齊格受到很大啟發。里昂惕夫是十月革命後移居美國的俄裔經濟學家，他的投入—產出模型是矩陣結構的一種線性模型，在概念上非常簡單同時又足夠精細，對實際制訂計畫很有幫助。當時，經濟學家們已經形成了他們的線性規劃模式，並且已經有了一些求解的方法。現在看來，當時這些方法都很原始。
1947年初，丹齊格拜訪了經濟學家柯普曼斯(T．J．Koopmans)，從他那裏知道線性規劃問題還沒有一種有效的、通用的演算法。這年夏天，丹齊格就研究從“線性規劃問題可行區域凸多面體”的一個頂點出發，沿著凸多面體的棱，走向目標函數值更優的下一個頂點的方法。凸多面體“單純分割”為一個個“單體”以後，屬於同一單體的兩個頂點稱為相鄰的頂點。丹齊格的單體演算法，通過一種矩陣表格的運算，提供了從一個頂點走向相鄰頂點中目標函數值最優的頂點的方法。
翻開任何一本介紹單體演算法的教科書，並且花一點耐性把它讀下去，你就知道學會單體演算法的操作並不是一件困難的事。不過，這需要列出許多表格，佔用許多篇幅，所以我們現在只好割愛，而代之以上面這樣比較籠統的介紹。
幸遇霍特林和馮•紐曼
提出單體演算法以後，丹齊格有兩個不放心。首先，線性規劃的一般理論當時還不完備。為此，他到普林斯頓高等研究院，向偉大的數學家馮•紐曼(J．von Neumann)請教。原來，當時馮•紐曼剛剛和摩根斯坦寫完《博弈論和經濟行為》這本數理經濟學的劃時代的巨著。這本巨著以稍許不同的方式，已經為線性規劃理論奠定了堅實的基礎。關於線性不等式的理論，關於凸多面體的理論，就是關於線性規劃的理論。
另一方面，丹齊格擔心單體演算法在實際計算時是不是有效，會不會算得很慢。大約一年以後，在1948年6月，空軍小組的成員告訴丹齊格，單體演算法對於所有試驗過的問題，都非常有效，算得很快。這真出乎演算法發明者本人的預料。變數數目稱為線性規劃問題的維數，約束方程和不等式的數目稱為線性規劃問題的階數。40年以後，丹齊格這樣回顧自己當時的感受：
解一個階數為m的線性規劃問題，大體上只需要2m到3m次迭代。這種情況實在令人吃驚。我確實未曾預料到結果會這麼了不起。我當時還沒有解高維問題的經驗，我不能依賴自己的幾何直覺。例如，我的直覺告訴我，從一個頂點或許需要經過很多步才能移動到相鄰的下一個頂點，而實際上卻只需要幾步。簡單地說，在高維空間，人們的直覺可能一文不值。
線性規劃問題的理論價值和經濟價值，使它在經濟學研究方面也佔有重要的地位。自從1969年頒發經濟學諾貝爾獎以來，上面提到的康托洛維奇、柯普曼和斯蒂格勒都曾因為包括與線性規劃問題有關的其他一些工作而獲獎，里昂惕夫則因為發展了投入一產出分析方法而獲獎。馮•紐曼健在的時候，還沒有諾貝爾經濟學獎，不然的話，他更是當之無愧。
40年代末期，線性規劃可說是理論上完備，方法上可靠。這裏所講的方法，就是丹齊格提出的實際使用效果很好的單體演算法。在向馮•紐曼請教以後不久，丹齊格參加了美國計量經濟學會在威斯康辛舉行的一次學術會議。會議的參加者中有霍特林(H．Hotelling)、柯普曼斯(T．J．Koopmans)、馮•紐曼這樣的大人物，也有許多剛開始從事學術研究的年輕人，他們後來也都相當知名。霍特林以身材胖大、養尊處優著稱，人們開玩笑說，如果他跳進大西洋游泳，海平面會升高幾公分。丹齊格第一次向這樣一批有許多著名學者在內的聽眾演講關於線性規劃的概念、模型和演算法，心情相當緊張。事實上，那時候丹齊格完全是個無名小輩。
丹齊格講完以後，會議主席照例請大家進行討論。在冷場幾分鐘以後，著名經濟學家霍特林舉手發言。他站起來，帶著人們熟悉的微笑，毫不客氣地說：
“但是，我們大家都知道，世界是非線性的。”
講完，就莊嚴地坐了下來。
丹齊格本來心情就緊張，聽到幾乎是從哲學層面發出的根本性抨擊，難免一時慌張。正在他不知道怎樣回答大人物霍特林的質疑的關口，馮•紐曼舉起了手。他說：
“主席先生，如果演講人不介意的話，我將樂於代他回答這個問題。”
丹齊格當然同意。馮•紐曼對大家說：
“報告人把他的題目叫做線性規劃，非常認真地敍述了他的公理。如果你有什麼應用問題是滿足這些公理的，你可以採用他的方法。如果你沒有這樣的應用問題，那當然不必勉強。”
這是一個富有科學哲學意味的答辯。從根本上說，霍特林的看法完全正確，世界確實是非線性的，而且是高度非線性的。但是，即使是完全正確的看法，也不應當捆住人類解決面臨問題的手腳。可幸的是，線性系統(線性不等式組或線性方程組)還是可以用於近似地解決人們在實際規劃問題中遇到的絕大部分非線性關係，而且解決得十分成功。就經濟效益而言，人類迄今沒有別的方法能夠像線性規劃的單體方法那麼成功。
（原載《經濟學家茶座》第十一輯）
1947年，美國數學家丹齊格(George B.Danzig)提出了線性規劃問題的一般模型和求解線性規劃問題的單體演算法。從此，線性規劃理論和應用得到了廣泛發展。
原來，在第二次世界大戰期間，丹齊格就在美國空軍的一個小組從事資源分配和計畫編制的工作。大戰以後，他回到伯克利加州大學，並取得了博士學位。這時，他成為美國空軍審計長的數學顧問，從事計畫工作機械化的研究。
作為一個數學家，首先要把問題表達清楚，這就是所謂建立模型的工作。1940年代，美國勞工統計局的里昂惕夫(W. Leontief) 所做投入—產出模型（input-output model）使丹齊格受到很大啟發。里昂惕夫是十月革命後移居美國的俄裔經濟學家，他的投入—產出模型是矩陣結構的一種線性模型，在概念上非常簡單同時又足夠精細，對實際制訂計畫很有幫助。當時，經濟學家們已經形成了他們的線性規劃模式，並且已經有了一些求解的方法。現在看來，當時這些方法都很原始。
1947年初，丹齊格拜訪了經濟學家柯普曼斯(T．J．Koopmans)，從他那裏知道線性規劃問題還沒有一種有效的、通用的演算法。這年夏天，丹齊格就研究從“線性規劃問題可行區域凸多面體”的一個頂點出發，沿著凸多面體的棱，走向目標函數值更優的下一個頂點的方法。凸多面體“單純分割”為一個個“單體”以後，屬於同一單體的兩個頂點稱為相鄰的頂點。丹齊格的單體演算法，通過一種矩陣表格的運算，提供了從一個頂點走向相鄰頂點中目標函數值最優的頂點的方法。
翻開任何一本介紹單體演算法的教科書，並且花一點耐性把它讀下去，你就知道學會單體演算法的操作並不是一件困難的事。不過，這需要列出許多表格，佔用許多篇幅，所以我們現在只好割愛，而代之以上面這樣比較籠統的介紹。
幸遇霍特林和馮•紐曼
提出單體演算法以後，丹齊格有兩個不放心。首先，線性規劃的一般理論當時還不完備。為此，他到普林斯頓高等研究院，向偉大的數學家馮•紐曼(J．von Neumann)請教。原來，當時馮•紐曼剛剛和摩根斯坦寫完《博弈論和經濟行為》這本數理經濟學的劃時代的巨著。這本巨著以稍許不同的方式，已經為線性規劃理論奠定了堅實的基礎。關於線性不等式的理論，關於凸多面體的理論，就是關於線性規劃的理論。
另一方面，丹齊格擔心單體演算法在實際計算時是不是有效，會不會算得很慢。大約一年以後，在1948年6月，空軍小組的成員告訴丹齊格，單體演算法對於所有試驗過的問題，都非常有效，算得很快。這真出乎演算法發明者本人的預料。變數數目稱為線性規劃問題的維數，約束方程和不等式的數目稱為線性規劃問題的階數。40年以後，丹齊格這樣回顧自己當時的感受：
解一個階數為m的線性規劃問題，大體上只需要2m到3m次迭代。這種情況實在令人吃驚。我確實未曾預料到結果會這麼了不起。我當時還沒有解高維問題的經驗，我不能依賴自己的幾何直覺。例如，我的直覺告訴我，從一個頂點或許需要經過很多步才能移動到相鄰的下一個頂點，而實際上卻只需要幾步。簡單地說，在高維空間，人們的直覺可能一文不值。
線性規劃問題的理論價值和經濟價值，使它在經濟學研究方面也佔有重要的地位。自從1969年頒發經濟學諾貝爾獎以來，上面提到的康托洛維奇、柯普曼和斯蒂格勒都曾因為包括與線性規劃問題有關的其他一些工作而獲獎，里昂惕夫則因為發展了投入一產出分析方法而獲獎。馮•紐曼健在的時候，還沒有諾貝爾經濟學獎，不然的話，他更是當之無愧。
40年代末期，線性規劃可說是理論上完備，方法上可靠。這裏所講的方法，就是丹齊格提出的實際使用效果很好的單體演算法。在向馮•紐曼請教以後不久，丹齊格參加了美國計量經濟學會在威斯康辛舉行的一次學術會議。會議的參加者中有霍特林(H．Hotelling)、柯普曼斯(T．J．Koopmans)、馮•紐曼這樣的大人物，也有許多剛開始從事學術研究的年輕人，他們後來也都相當知名。霍特林以身材胖大、養尊處優著稱，人們開玩笑說，如果他跳進大西洋游泳，海平面會升高幾公分。丹齊格第一次向這樣一批有許多著名學者在內的聽眾演講關於線性規劃的概念、模型和演算法，心情相當緊張。事實上，那時候丹齊格完全是個無名小輩。
丹齊格講完以後，會議主席照例請大家進行討論。在冷場幾分鐘以後，著名經濟學家霍特林舉手發言。他站起來，帶著人們熟悉的微笑，毫不客氣地說：
“但是，我們大家都知道，世界是非線性的。”
講完，就莊嚴地坐了下來。
丹齊格本來心情就緊張，聽到幾乎是從哲學層面發出的根本性抨擊，難免一時慌張。正在他不知道怎樣回答大人物霍特林的質疑的關口，馮•紐曼舉起了手。他說：
“主席先生，如果演講人不介意的話，我將樂於代他回答這個問題。”
丹齊格當然同意。馮•紐曼對大家說：
“報告人把他的題目叫做線性規劃，非常認真地敍述了他的公理。如果你有什麼應用問題是滿足這些公理的，你可以採用他的方法。如果你沒有這樣的應用問題，那當然不必勉強。”
這是一個富有科學哲學意味的答辯。從根本上說，霍特林的看法完全正確，世界確實是非線性的，而且是高度非線性的。但是，即使是完全正確的看法，也不應當捆住人類解決面臨問題的手腳。可幸的是，線性系統(線性不等式組或線性方程組)還是可以用於近似地解決人們在實際規劃問題中遇到的絕大部分非線性關係，而且解決得十分成功。就經濟效益而言，人類迄今沒有別的方法能夠像線性規劃的單體方法那麼成功。
（原載《經濟學家茶座》第十一輯）
留言