從你網購的包裹如何以最快速度送達，到航空公司如何規劃數千架飛機的航線以節省燃料，背后都有一個近 80 歲「高齡」的數學方法在默默工作。它被譽為優化領域的基石，高效又令人信賴。然而，一個奇怪的事實是：幾十年來，沒有人能從理論上完美解釋它為何如此高效。現在，這個謎題的最后一塊拼圖，終于被找到了。

1939 年，當時還是加州大學伯克利分校一年級研究生的喬治·丹齊格（George Dantzig）在一次統計學課上遲到了。他從黑板上抄下了兩個問題，以為是家庭作業。他后來回憶說，他發現這次的作業「比平時難得多」，并為自己多花了好幾天才完成而向教授道歉。

幾周后，他的教授告訴他，他成功解決了統計學領域兩個尚待解決的著名問題。

丹齊格的這項成果為他的博士論文奠定了基礎，并在幾十年后成為了電影《心靈捕手》的靈感來源。

喬治·丹齊格（George Dantzig，1914—2005），美國著名數學家，1947 年提出了單純形法，被稱為線性規劃之父。

丹齊格在 1946 年，也就是二戰剛結束后不久，獲得了博士學位，并很快成為了新成立的美國空軍的數學顧問。

與所有現代戰爭一樣，第二次世界大戰的勝負取決于對有限資源的審慎分配。但與以往的戰爭不同，這場沖突的規模是全球性的，其勝利在很大程度上是依靠純粹的工業實力取得的。當時，美國能夠生產比其敵人更多的坦克、航空母艦和轟炸機。

了解到這一點后，軍方對優化問題產生了濃厚興趣，即：在可能涉及成百上千個變量的情況下，如何戰略性地分配有限的資源？

美國空軍交給丹齊格的任務是，找出解決這類優化問題的新方法。作為回應，他發明了單純形法 (simplex method) ，這個算法借鑒了他在近十年前解決黑板問題時所發展出的一些數學技巧。

近 80 年后，當需要在復雜的約束條件下做出后勤或供應鏈決策時，單純形法仍然是使用最廣泛的工具之一。它高效且行之有效。法國國家科學研究中心 (CNRS) 的 Sophie Huiberts 說道：「它一直運行得很快，沒人見過它變慢過。」

與此同時，一個奇特的性質長期以來為丹齊格的方法蒙上了一層陰影。

1972 年，數學家們證明：該算法完成任務所需的時間可能會隨著約束條件的數量呈指數級增長。

因此，無論該方法在實踐中運行得多快，理論分析始終給出最壞情況下的場景，暗示它可能需要指數級更長的時間。對于單純形法，「我們研究算法的傳統工具并不奏效，」 Huiberts 說。

但在即將于 12 月在計算機科學基礎（Foundations of Computer Science）會議上發表的一篇新論文中，Huiberts 和慕尼黑工業大學的博士生 Eleon Bach 似乎已經克服了這個問題。

• 論文標題：Optimal Smoothed Analysis of the Simplex Method
• 論文地址：https://arxiv.org/abs/2504.04197

他們不僅使該算法變得更快，還從理論上解釋了這一現象：長期以來令人擔憂的指數級運行時間在實踐中并未出現。

這項成果建立在 Daniel Spielman 和滕尚華 (Shang-Hua Teng) 2001 年里程碑式成果《Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time》（arXiv:cs/0111050）之上。滕尚華表示，這項成果「卓越且優美」。

「這是一項非常了不起的技術工作，它巧妙地結合了以往研究中發展的許多思想，同時增加了一些非常好的新穎技術構想，」 波恩大學的數學家 László Végh 說道，他沒有參與這項研究。

從幾何角度來看，單純形算法的整個執行過程，就是尋找一條路徑（比方說，從底部頂點到最高點），并且這條路徑包含的步驟最少，或者說，經過的邊最少。總步數則與算法的運行時間（或「復雜度」）相關，目標是在最少的步數內解決問題。在這張圖中找出從底部到頂部的最短路線，就相當于找出了這類算法所能采取的最有效形式。

如果不是因為以下兩個問題，找到一條快速直接的路徑可能會很容易：

• 第一，原始形狀可能比我們的例子復雜得多，有更多的面、頂點和邊。
• 第二，沒有地圖可以引導你。你無法看到你試圖導航的整個物體。相反，你從一個頂點開始，選擇要先沿著哪條邊走。在下一個頂點你做同樣的事情，依此類推，并不確定你選擇的邊會將你帶到哪里。

如果你運氣特別差，你可能會在每個頂點都走錯方向，最終陷入迷宮。「你可能會走上從 A 點到 B 點的最長路徑，」 Bach 說，「因為在每個拐角處，都有人告訴你該走向錯誤的方向。」 正是這種情況可能導致需要指數級時間才能完成的最壞情況。

2001 年，Spielman 和滕尚華證明：引入一點點隨機性可以幫助避免這樣的結果。

滕尚華（左）和 Daniel Spielman 在他們 2001 年的里程碑式成果中運用了隨機性。

回到前面的例子（注意這里極大地簡化了 Spielman 和滕尚華的論證），讓我們假設你到達的每個拐角處都有六個選擇。如果總是有人告訴你走最差的方向，你就會陷入困境。然而，如果你依靠擲骰子來決定，你將有六分之五的機會避開最差的選擇，從而可能避免災難。在過程中注入隨機性和不確定性的元素是合理的，因為在現實世界中，測量永遠不是精確的。

當然，Spielman 和滕尚華引入隨機性的方式完全不同，但他們證明：運行時間絕不會比約束數量的某個固定次冪更差（例如 n2 ）—— 這就是所謂的多項式時間 (polynomial time)。這比指數時間（例如 2? 的形式）要好得多。

最優幾何

單純形法旨在解決這樣一類問題：假設一家家具公司生產衣柜、床和椅子。巧合的是，每個衣柜的利潤是椅子的三倍，而每張床的利潤是椅子的兩倍。如果我們想把這寫成一個表達式，用 a、b 和 c 分別代表生產的家具數量，那么總利潤將與 3a+2b+c 成正比。

為了實現利潤最大化，公司應該各種物品各生產多少件呢？

答案取決于它面臨的約束條件。比方說，該公司每月最多能生產 50 件產品，因此 a+b+c≤50。衣柜的制造難度更大 —— 假設產量不能超過 20 個，所以 a≤20；椅子需要特殊的木材，而且供應有限，所以 c 必須小于 24。

單純形法可將這類情況（通常涉及更多變量）轉化為一個幾何問題。

想象一下在一個三維圖表中繪制我們對 a、b 和 c 的約束條件。如果 a≤20，我們可以想象在三維圖上有一個垂直于 a 軸的平面，在 a=20 的位置將其切開。我們會規定，我們的解必須位于該平面上或其下方的某個位置。同樣，我們可以為其他約束條件創建邊界。這些邊界組合起來可以將空間分割成一個復雜的三維形狀，稱為多面體 (polyhedron)。

Sophie Huiberts 手持一個優化問題的幾何模型。

然而，這并沒有完全解決問題。

Huiberts 指出，他們的多項式時間值仍然相當高，其中包含一個 30 次冪的項，對于指數來說，這是一個相當大的數字。

因此，在過去二十年里，研究人員一直在逐步降低這個數值。

在 Bach 和 Huiberts 的新論文中，他們在算法中應用了更多的隨機性，以證明運行時間可以保證遠低于先前確立的水平。他們還證明：基于 Spielman 和滕尚華所建立方法的算法，其運行速度無法超越他們獲得的值。Huiberts 說，這告訴我們，「我們完全理解了單純形法的這個模型。」

研究主要結果

盡管如此，Huiberts 并不認為這是終點。

從 2001 年 Spielman 和滕尚華開始的方法展示了如何將運行時間從指數級降低到多項式級。下一個合理的目標是發明一種能夠與約束數量成線性關系擴展的方法。「這是所有這項研究的北極星 (North Star)，」她說。但這需要一種全新的策略。「我們短期內還不大可能實現它。」

雖然 Bach 和 Huiberts 的努力對他們領域的同行具有理論意義，但這項工作尚未產生任何直接的實際應用。

Eleon Bach 是這項新成果的作者之一。

盡管如此，它可能會平息一些人對于依賴當今基于單純形法的軟件可能產生的擔憂。愛丁堡大學數學講師、線性規劃軟件設計師 Julian Hall 表示：「雖然實踐實驗表明這些問題總是在多項式時間內解決」，但 Bach 和 Huiberts 的研究為這一直覺提供了更強的數學支持。「因此，現在更容易說服那些擔心指數級復雜度的人了。」