跳到主要內容

OR人物

線性規畫之父 丹齊格

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)、馮•紐曼這樣的大人物,也有許多剛開始從事學術研究的年輕人,他們後來也都相當知名。霍特林以身材胖大、養尊處優著稱,人們開玩笑說,如果他跳進大西洋游泳,海平面會升高幾公分。丹齊格第一次向這樣一批有許多著名學者在內的聽眾演講關於線性規劃的概念、模型和演算法,心情相當緊張。事實上,那時候丹齊格完全是個無名小輩。
丹齊格講完以後,會議主席照例請大家進行討論。在冷場幾分鐘以後,著名經濟學家霍特林舉手發言。他站起來,帶著人們熟悉的微笑,毫不客氣地說:
“但是,我們大家都知道,世界是非線性的。”
講完,就莊嚴地坐了下來。
丹齊格本來心情就緊張,聽到幾乎是從哲學層面發出的根本性抨擊,難免一時慌張。正在他不知道怎樣回答大人物霍特林的質疑的關口,馮•紐曼舉起了手。他說:
“主席先生,如果演講人不介意的話,我將樂於代他回答這個問題。”
丹齊格當然同意。馮•紐曼對大家說:
“報告人把他的題目叫做線性規劃,非常認真地敍述了他的公理。如果你有什麼應用問題是滿足這些公理的,你可以採用他的方法。如果你沒有這樣的應用問題,那當然不必勉強。”
這是一個富有科學哲學意味的答辯。從根本上說,霍特林的看法完全正確,世界確實是非線性的,而且是高度非線性的。但是,即使是完全正確的看法,也不應當捆住人類解決面臨問題的手腳。可幸的是,線性系統(線性不等式組或線性方程組)還是可以用於近似地解決人們在實際規劃問題中遇到的絕大部分非線性關係,而且解決得十分成功。就經濟效益而言,人類迄今沒有別的方法能夠像線性規劃的單體方法那麼成功。
(原載《經濟學家茶座》第十一輯)
張貼留言

這個網誌中的熱門文章

轉載《再別康橋》 賞析

《再別康橋》賞析
作者: 徐志摩


輕輕的我走了,
正如我輕輕的來;
我輕輕的招手,
作別西天的雲彩。

那河畔的金柳,
是夕陽中的新娘;
波光裡的豔影,
在我的心頭蕩漾。

軟泥上的青荇,
油油的在水底招搖;
在康河的柔波裡,
我甘心做一條水草!

那榆蔭下的一潭,
不是清泉,
是天上虹;

陳琳 古詩《飲馬長城窟行》漫談

飲馬長城窟,水寒傷馬骨。
往謂長城吏,慎莫稽留太原卒﹗
官作自有程,舉筑諧汝聲﹗
男兒寧當格鬥死,何能怫郁(ㄈㄨˊ ㄩˋ)筑長城。

長城何連連,連連三千里。
邊城多健少,內舍多寡婦。

作書與內舍,便嫁莫留住。
善待新姑嫜,時時念我故夫子﹗

報書往邊地,君今出語一何鄙﹖
身在禍難中,何為稽留他家子﹖
生男慎莫舉,生女哺用脯。
君獨不見長城下,死人骸骨相撐拄。
結髮行事君,慊慊心意關。
明知邊地苦,賤妾何能久自全﹖

語譯
  第一層(1—8句),寫築城役卒與長城吏的對話:
  讓馬飲水,只得到那長城下山石間的泉眼,那裡的水是那麼的冰冷,都冷傷透及馬骨頭裡。
  一位築城役卒跑去對監修長城的官吏懇求說:你們千萬不要長時間的滯留我們這些來自太原的役卒啊!

白居易的《花非花》究竟是什麽意思

花非花,霧非霧。夜半來,天明去。來如春夢不多時,去似朝雲無覓處。這首唐代著名詩人白居易的《花非花》在五十多年前我讀書的時候就已經於音樂課中學過,至今還沒忘記它的旋律。不過對於詞句的意思卻是不甚了了。最近我著迷台詩宋詞的學習,上網查這首詩的翻譯,發現有多家不同的解讀,詩人的《花非花》到底想說什麼呢?感到十分有趣,特將結果整理與同好分享。
白居易詩不僅以語言淺近著稱,其意境亦多顯露,但這首《花非花》卻句式奇特,且通篇取譬,十分含蓄,甚至迷離,堪稱是中國文學史上最早的朦朧詩的代表,在白詩中確乎是一個特例。因此對於這首詩到底想表達甚麼,充滿好奇。詩取前三字爲題,近乎“無題”。首二句應讀作“花——非花,霧——非霧”,先就給人一種捉摸不定的感覺。“非花”、“非霧”均系否定,卻包含一個不言而喻的前提:似花、似霧。因此可以說,這是兩個靈巧的比喻。語意雙關,富有朦朧美是這首小詞的最大特點。霧、春夢、朝雲,這幾個意象都是朦朧、飄渺的,意象之間又故意省略了銜接,顯出較大的跳躍性,文字空靈,精煉,使人咀嚼不盡,顯示了詩人不凡的藝術功力。但是,從“夜半來,天明去”的敘寫,可知這裏取喻於花與霧,在於比方所詠之物的短暫易逝,難持長久。如果單看“夜半來,天明去”,頗使讀者疑心是在說夢。但從下句“來如春夢”四字,可見又不然了。“夢”原來也是一比。這裏“來”、“去”二字,在音情上有承上啓下作用,由此生發出兩個新鮮比喻。“夜半來”者春夢也,春夢雖美卻短暫,於是引出一問:“來如春夢幾多時?”“天明”見者朝霞也,雲霞雖美卻易幻滅,於是引出一歎:“去似朝雲無覓處”。
  有人主張這首詞通篇都是隱語,主題當是詠官妓。當時各級官府都有一定數目的官妓,供那些官僚們驅使。首句“花非花”是說官妓的容顏如花,但又並非真花。次句“霧非霧”中“霧”字是雙關。借“霧”為“婺”。“婺女”即女宿星。因官妓女性,上應女宿,但又並非雲霧之霧。
“夜半來,天明去”既是詠星,也是說人。語意雙關,而主要是說人。唐宋時代旅客招妓女伴宿,都是夜半才來,黎明即去。因此,她來的時間不多,旅客宛如做了一個春夢。她去了之後,就像清晨的雲,消散得無影無蹤。官妓不同于一般的妓女,更不同于正式的妻子,她們與官僚之間互為依存,但關係又不便十分密切,只能以夜來明去為限,可謂會短別長。元稹有一首詩《夢昔時》,記他在夢中重會一個女子,有句云:“夜半初得處,天明臨去時。”…