1939 年，加州大學伯克利分校的一年級研究生喬治·丹齊格 (George Dantzig) 遲到了，他從黑板上抄了兩道題，以為這是作業。他後來回憶道，他發現作業“比平時難”，並為多花了幾天時間來完成作業而向教授道歉。幾週後，他的教授告訴他，他已經解決了統計學中兩個著名的開放性問題。丹齊格的工作為他的博士論文奠定了基礎，並在幾十年後為這部電影提供了靈感 善意釣魚。
丹齊格於 1946 年二戰結束後獲得博士學位，並很快成為新成立的美國空軍的體育顧問。與所有現代戰爭一樣，第二次世界大戰的結果取決於對有限資源的明智分配。但與以往的戰爭不同的是，這場衝突的範圍確實是全球性的，並且很大程度上是通過純粹的工業力量取得勝利的。美國可以生產比敵人更多的坦克、航空母艦和轟炸機。認識到這一點，陸軍一直對優化問題非常感興趣，即如何在可能涉及數百或數千個變量的情況下戰略性地分配有限的資源。
空軍責成 Dantzig 發現解決此類優化問題的新方法。作為回應，他發明了一種簡單的方法，一種基於他大約十年前在解決黑板問題時開發的一些數學技術的算法。
近 80 年後，當需要在復雜的約束下做出物流或供應鏈決策時，簡單的方法仍然是使用最廣泛的工具之一。它很有效並且有效。 “它總是很快，沒有人發現它不快，”他說。 索菲·惠伯特 法國國家科學研究中心（CNRS）。
與此同時，有一種奇怪的品質早已給丹齊格的方法蒙上了陰影。 1972 年，數學家證明，隨著約束數量的增加，完成任務所需的時間會急劇增加。因此，無論這種方法在實踐中看起來有多快，理論分析始終呈現出最壞的情況，這意味著它可能需要更長的時間。 “對於簡單的方法來說，我們用於研究算法的傳統工具不起作用，”惠伯特說。
但以一種新的方式 紙 將於 12 月在計算機科學基礎會議、Huiberts 和 埃隆·巴赫慕尼黑工業大學的一名博士生似乎已經克服了這個問題。他們使算法變得更快，並且還提供了為什麼長期以來人們擔心的指數運行時間在實踐中未能實現的理論原因。建立在 歷史成績 從 2001 年起 丹尼爾·斯皮爾曼 和 滕尚華“輝煌（而且）美麗，”滕說。
他說：“這是一件非常令人印象深刻的藝術作品，巧妙地將以前研究中開發的許多想法結合在一起，（同時添加）一些非常酷的新技術想法。” 拉斯洛·無花果波恩大學的數學家並未參與這項工作。
優化工程
這個簡單的方法旨在解決這樣一類問題：假設一家家具公司生產梳妝台、床和椅子。巧合的是，每個梳妝台的利潤是每張椅子的三倍，而每張床的利潤是每張床的兩倍。如果我們想把它寫成一個表達式，使用 一個, 為了， 和 C 為了表示家具的生產數量，我們可以說總利潤與 3 成正比一個 + 2為了 + C。
為了實現利潤最大化，公司每種產品應該生產多少產品？答案取決於它面臨的限制。假設該公司每月最多可以生產 50 件商品，因此 一個 + 為了 + C 小於或等於50個。輪子很難製造——最多不能生產20個——所以 一個 小於或等於20。椅子需要特殊木材，供應有限，所以 C 必須小於 24。
這種簡單的方法將這種情況（儘管它們通常涉及許多變量）轉變為工程問題。想像一下我們的約束圖 一個, 為了 和 C 在三個維度上。如果 一個 小於或等於 20，我們可以想像 3D 圖上的水平垂直於 一個 軸，然後將其切入 一個 = 20。我們將規定解必須位於該水平或低於該水平的某個位置。同樣，我們可以創建與其他約束相關聯的限制。這些邊界結合起來可以將空間劃分為複雜的三維形狀，稱為多面體。
