★加星zzllrr小樂公眾號(hào)數(shù)學(xué)科普不迷路！

目前主流的單純形法——一種廣泛應(yīng)用于平衡復(fù)雜物流約束的技術(shù)——已然達(dá)到極致。

圖源：Nash Weerasekera / Quanta Magazine

作者：Steve Nadis（量子雜志特約撰稿人）2025-10-13

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號(hào)）2025-10-14

1939年，加州大學(xué)伯克利分校一年級(jí)研究生喬治·丹齊格（George Dantzig）上統(tǒng)計(jì)學(xué)課遲到了，他從黑板上抄了兩道題，以為是家庭作業(yè)。他后來回憶說，這道作業(yè)“比平時(shí)難做”，于是向教授道歉，因?yàn)樗嗷藥滋鞎r(shí)間才完成。幾周后，教授告訴他，他解決了統(tǒng)計(jì)學(xué)中兩個(gè)著名的開放性問題。丹齊格的研究成果為他的博士論文奠定了基礎(chǔ)，幾十年后，更是為電影 《心靈捕手》

Good Will Hunting

丹齊格于1946年二戰(zhàn)剛結(jié)束后獲得博士學(xué)位，并很快成為新成立的美國空軍的數(shù)學(xué)顧問。與所有現(xiàn)代戰(zhàn)爭一樣，二戰(zhàn)的勝負(fù)取決于有限資源的審慎分配。但與以往的戰(zhàn)爭不同，這場戰(zhàn)爭真正具有全球性，其勝利很大程度上得益于強(qiáng)大的工業(yè)實(shí)力。美國可以比敵人生產(chǎn)更多的坦克、航空母艦和轟炸機(jī)。鑒于此，軍方對最優(yōu)化問題產(chǎn)生了濃厚的興趣——即如何在可能涉及數(shù)百甚至數(shù)千個(gè)變量的情況下，戰(zhàn)略性地分配有限的資源。

空軍委托丹齊格尋找解決此類最優(yōu)化問題的新方法。為此，他發(fā)明了單純形法（simplex method），這種算法借鑒了近十年前他在解決黑板問題時(shí)開發(fā)的一些數(shù)學(xué)技巧。

近80年后，單純形法仍然是在復(fù)雜約束條件下進(jìn)行物流或供應(yīng)鏈決策時(shí)最廣泛使用的工具之一。它高效可行?！八恢边\(yùn)行得很快，而且從未有人見過它不快，”法國國家科學(xué)研究中心（CNRS）的索菲·惠伯茨（Sophie Huiberts）說道。

與此同時(shí)，丹齊格方法的一個(gè)奇特特性長期以來一直蒙上陰影。1972年，數(shù)學(xué)家證明，完成一項(xiàng)任務(wù)所需的時(shí)間可能會(huì)隨著約束數(shù)量的增加而呈指數(shù)增長。因此，無論該方法在實(shí)踐中有多快，理論分析總是會(huì)給出最壞的情況，這意味著它可能需要更長的時(shí)間。對于單純形法，“我們研究算法的傳統(tǒng)工具不起作用，”惠伯茨說。

然而，在一篇將于12月在計(jì)算機(jī)科學(xué)基礎(chǔ)大會(huì)上發(fā)表的新論文中 https://arxiv.org/abs/2504.04197 ，惠伯茨和慕尼黑工業(yè)大學(xué)的博士生Eleon Bach（埃利昂·巴赫）似乎已經(jīng)克服了這個(gè)問題。他們提高了算法的速度，并提供了理論依據(jù)，解釋了為什么長期以來人們擔(dān)心的指數(shù)級(jí)運(yùn)行時(shí)間在實(shí)踐中不會(huì)出現(xiàn)。這項(xiàng)工作建立在丹尼爾·斯皮爾曼（Daniel Spielman）和滕尚華于2001年取得的一項(xiàng)里程碑式成果 https://arxiv.org/abs/cs/0111050 的基礎(chǔ)上，滕尚華表示，這項(xiàng)工作“非常出色，且精彩”。

Eleon Bach（埃利昂·巴赫）是這項(xiàng)新成果的共同作者之一。

圖源：Eleon Bach

“這是一項(xiàng)非常令人印象深刻的技術(shù)工作，它巧妙地結(jié)合了之前研究中開發(fā)的許多想法，[同時(shí)添加]了一些真正好的新技術(shù)理念，”波恩大學(xué)數(shù)學(xué)家拉斯洛·維格 (László Végh) 說，他沒有參與這項(xiàng)工作。

最優(yōu)化幾何

單純形法旨在解決如下一類問題：假設(shè)一家家具公司生產(chǎn)衣櫥、床和椅子。碰巧的是，每個(gè)衣櫥的利潤是每把椅子的三倍，而每張床的利潤是每把椅子的兩倍。如果我們用 a 、 b 和 c 分別表示每種家具產(chǎn)量，將其寫成一個(gè)表達(dá)式，那么總利潤與 3a + 2b + c 成正比。

為了實(shí)現(xiàn)利潤最大化，公司應(yīng)該生產(chǎn)每種產(chǎn)品多少？答案取決于公司面臨的約束條件。假設(shè)公司每月最多生產(chǎn) 50 件產(chǎn)品，那么 a + b + c 小于或等于 50。衣櫥的生產(chǎn)難度更大——最多只能生產(chǎn) 20 個(gè)——所以 a 小于或等于 20。椅子需要特殊的木材，而且供應(yīng)有限，所以 c 必須小于 24。

單純形法將類似情況（盡管通常涉及更多變量）轉(zhuǎn)化為幾何問題。想象一下，在三維空間中繪制 a 、 b 和 c 的約束圖形。如果 a 小于或等于 20，我們可以想象在三維圖形上有一個(gè)垂直于 a 軸的平面，并在 a = 20 處與其相交。我們規(guī)定解必須位于該平面上方或下方的某個(gè)位置。同樣，我們可以創(chuàng)建與其他約束相關(guān)的邊界。這些邊界結(jié)合起來，可以將空間劃分成一個(gè)復(fù)雜的三維形狀，稱為多面體（polyhedron）。

索菲·惠伯茨（Sophie Huiberts）持有一個(gè)最優(yōu)化問題的幾何模型。

圖源：Sophie Huiberts

單純形算法從頭到尾的執(zhí)行過程，用幾何學(xué)的表達(dá)方式來說，就是尋找一條路徑——比如從最底下的頂點(diǎn)到最上面的頂點(diǎn)——它需要的步驟最少，或者說，追蹤的邊數(shù)最少?？偛襟E數(shù)又與算法的運(yùn)行時(shí)間（或“復(fù)雜度”）相關(guān)，目標(biāo)是用最少的步驟解決問題。在這張圖中，找出從底部到頂部的最短路徑，就等于找出這種算法可以采用的最高效形式。

找到一條快速直接的路徑或許很容易，但往往因?yàn)橐韵聝牲c(diǎn)并不容易：首先，原始形狀可能比我們的例子復(fù)雜得多，包含更多的面、頂點(diǎn)和邊。其次，沒有地圖指引你。你無法看到你試圖導(dǎo)航的整個(gè)對象。相反，你從一個(gè)頂點(diǎn)開始，選擇先走哪條邊。在下一個(gè)頂點(diǎn)，你又重復(fù)同樣的步驟，以此類推，你并不確定你選擇的這條邊會(huì)把你帶到哪里。

如果你運(yùn)氣極差，可能會(huì)在每個(gè)頂點(diǎn)都走錯(cuò)，然后被困在迷宮里。“你可能會(huì)走從 A 到 B最長的路，”巴赫說，“因?yàn)樵诿總€(gè)拐角處，都會(huì)有人告訴你可能走錯(cuò)方向。”這種情況可能會(huì)導(dǎo)致最糟糕的結(jié)果，需要花費(fèi)指數(shù)級(jí)的時(shí)間才能完成。

2001年，斯皮爾曼和滕尚華證明了哪怕是最微小的隨機(jī)性也能幫助避免這種結(jié)果?；氐角懊娴睦印M管這可能大大簡化了斯皮爾曼和滕尚華的論證——假設(shè)你遇到的每個(gè)角落都有六個(gè)選擇。如果你總是被告知最壞的方向，你就會(huì)陷入困境。然而，如果你依靠擲骰子，你就有六分之五的機(jī)會(huì)避免最糟糕的選擇，從而可能避免災(zāi)難。考慮到現(xiàn)實(shí)世界中的測量從來都不精確，在過程中注入隨機(jī)性和不確定性元素是合理的。斯皮爾曼和滕尚華以完全不同的方式引入了隨機(jī)性，但他們證明了運(yùn)行時(shí)間永遠(yuǎn)不會(huì)比約束數(shù)量的某個(gè)固定冪（例如 n2 ） 更差，這就是所謂的多項(xiàng)式時(shí)間的一個(gè)例子。這比指數(shù)時(shí)間要好得多，指數(shù)時(shí)間的形式是 2? 。

滕尚華（上）和丹尼爾·斯皮爾曼（下）在2001年取得的里程碑式成果中使用了隨機(jī)性。

圖源：Emilio Flores / Quanta Magazine ；Brandon Schulman

然而，這并沒有完全解決問題。Huiberts指出，他們的多項(xiàng)式時(shí)間值仍然相當(dāng)高——它們包含一個(gè)30次方的項(xiàng)，這對于指數(shù)來說是一個(gè)相當(dāng)大的數(shù)字。因此，在過去的二十年里，研究人員一直在逐步降低這個(gè)值。

在新論文中，Bach 和 Huiberts 在算法中引入了更多隨機(jī)性，證明了運(yùn)行時(shí)間肯定比之前建立的運(yùn)行時(shí)間要短得多。他們還證明，基于斯皮爾曼和滕尚華建立的方法的算法不可能比他們得到的值更快。Huiberts 表示，這說明“我們完全理解了單純形法的這個(gè)模型”。

波恩大學(xué)計(jì)算機(jī)科學(xué)家 Heiko R?glin 表示：“這標(biāo)志著我們對單純形算法的理解取得了重大進(jìn)展，首次為該方法的實(shí)際效率提供了真正令人信服的解釋。”

盡管如此，Huiberts 并不認(rèn)為這是研究的終點(diǎn)。斯皮爾曼和滕尚華于2001年開創(chuàng)的方法展示了如何將運(yùn)行時(shí)間從指數(shù)級(jí)縮短到多項(xiàng)式級(jí)。下一步合乎邏輯的做法是發(fā)明一種能夠隨著約束數(shù)量線性擴(kuò)展的方法。“這是所有這些研究的北極星，”她說。但這需要一個(gè)全新的策略?！拔覀兌唐趦?nèi)還無法實(shí)現(xiàn)這一目標(biāo)?！?/p>

雖然 Bach 和 Huiberts 的努力引起了同行們的理論興趣，但這項(xiàng)工作尚未產(chǎn)生任何直接的實(shí)際應(yīng)用。然而，它或許可以緩解人們對依賴目前基于單純形法的軟件的一些擔(dān)憂?！半m然實(shí)際實(shí)驗(yàn)表明這些問題總是可以在多項(xiàng)式時(shí)間內(nèi)解決，”設(shè)計(jì)線性規(guī)劃軟件的愛丁堡大學(xué)數(shù)學(xué)講師 Julian Hall 說道，但 Bach 和 Huiberts 的研究為這一直覺提供了更有力的數(shù)學(xué)支持?！耙虼?，現(xiàn)在更容易說服那些害怕指數(shù)級(jí)復(fù)雜性的人了?！?/p>

參考資料

https://www.quantamagazine.org/researchers-discover-the-optimal-way-to-optimize-20251013/

https://arxiv.org/abs/2504.04197

https://arxiv.org/abs/cs/0111050

小樂數(shù)學(xué)科普近期文章

出版社和作家自薦通道

小樂數(shù)學(xué)科普薦書

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點(diǎn)贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號(hào)主頁

加星★

數(shù)學(xué)科普不迷路！