【學界】21世紀運籌學相關的12個未解難題

04-05

作者：藍色的信封
『運籌OR帷幄』責任編輯： @文雨之（東北大學系統工程博士生）
本篇文章是由以上作者在博客上的優秀文章（原文鏈接: 運籌學的若干難題），通過『運籌OR帷幄』責任編輯整理修改而成的。

歡迎原鏈接轉發，付費轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。
敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：
『運籌OR帷幄』大數據人工智慧時代的運籌學

0.從希爾伯特的23個數學難題開始

形成一個公認的科學難題的過程本身就是科學研究的一個結果，同時也是開啟新的、未知大門的敲門磚。在許多科學家看來，科學難題是科學進步的階梯。隨著一個又一個科學難題的解決，科學技術不斷登上新的台階，人類文明上升到一個新的高度。上個世紀伊始，著名數學家希爾伯特在國際數學家大會上提出了23 個數學難題。在過去的100 年裡，這些問題激發了眾多數學家的熱情，引導了數學研究的方向，對現代數學的發展產生了難以估量的巨大影響。在運籌學發展的60 多年裡，幾代運籌學工作者在運籌學的各個方向取得了許許多多的成果，應用數學的理論和方法奠定了運籌學的基礎，也對數學的發展做出了貢獻。

1.運籌學相關的12未解難題

著名數學科普作家卡斯蒂在總結上個世紀意義的重大數學成果時，從眾多的數學定理中遴選出了5 個，其中4 個都與運籌學有非常緊密的關係，它們是：極小極大定理（博弈論），單純形法（線性規劃），停機定理（計算的理論），布勞威爾不動點定理（博弈論的基礎工具）。

著名數學家波利亞曾經說過：「數學就是解決問題的藝術」。隨著一個又一個運籌學難題的解決，新的難題不斷地從新的土壤里破土而出。其中一些不僅僅是運籌學的相關研究方向的重大問題，也是數學及相關學科的一些核心問題。在著名數學家斯米爾給出的本世紀18個數學難題中，其中以下4個就與運籌學相關：

（1）「P是否等於NP」，也被列為本世紀的7個數學難題之一；

（2）單變數多項式整解的個數；

（3）可描述價格調整的一般均衡理論的數學模型；

（4）實係數線性規劃是否多項式時間可解。

以下12 個問題是運籌學相關方向具有一定代表性的未解難題：

（1）凸多面體的d-步猜想；

（2）有限多個二次函數最大值的極小化問題；

（3）推廣的Lax 猜想；

（4）DFP 擬牛頓法的收斂性；

（5）最小阻力凸體問題；

（6）是否存在求解性線性規劃的強多項式時間演算法？

（7）組合優化反問題的計算複雜性；

（8）求解旅行商問題的更好的近似演算法；

（9）k-伺服器猜想；

（10）裝箱問題是否存在絕對近似演算法；

（11）隨機排隊網路的遍歷性；

（12）PH-分布的最小表示。

2.總結

顯然，運籌學未解的難題遠不止上述這些。特別是，這些問題在運籌學的各個分支之間的分布不平衡，個別方向甚至未能得到反映；它們對運籌學的理論及應用的意義和重要性各不相同，難易程度也有千差萬別。有興趣的讀者可以在此基礎上開展研究，也可以提出和研究其他有意義的問題。畢竟發現問題、提出問題、分析問題和解決問題的過程構成了運籌學的發展進程。

以上『運籌OR帷幄』專欄所有文章都會同步發送至留德華叫獸的頭條主頁，以及同名微信公眾號，目前預計受眾10w +

如果你是運籌學/人工智慧碩博或在讀，請在下圖的公眾號後台留言：「加微信群」。系統會自動辨認你的關鍵字，並提示您進一步的加群要求和步驟，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

運籌學|控制論|優化理論愛好者，歡迎加qq群：686387574

人工智慧愛好者，歡迎加qq群： 685839321

數據科學|分析愛好者，歡迎加qq群：130414574

最後敬請關注和擴散本專欄及同名公眾號，會陸續發布運籌學、人工智慧中優化理論相關乾貨及行業動態：『運籌OR帷幄』大數據和人工智慧時代下的運籌學 - 知乎專欄