运筹学中若干难题

形成一个公认的科学难题的过程本身就是科学研究的一个结果,同时也是开启新的、未知大门的敲门砖。在许多科学家看来,科学难题是科学进步的阶梯。随着一个又一个科学难题的解决,科学技术不断登上新的台阶,人类文明上升到一个新的高度。

上个世纪伊始,著名数学家希尔伯特在国际数学家大会上提出了23 个数学难题。在过去的100 年里,这些问题激发了众多数学家的热情,引导了数学研究的方向,对现代数学的发展产生了难以估量的巨大影响。在运筹学发展的60 多年里,几代运筹学工作者在运筹学的各个方向取得了许许多多的成果,应用数学的理论和方法奠定了运筹学的基础,也对数学的发展做出了贡献。

著名数学科普作家卡斯蒂在总结上个世纪意义的重大数学成果时,从众多的数学定理中遴选出了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-分布的最小表示。

显然,运筹学未解的难题远不止上述这些。特别是,这些问题在运筹学的各个分支之间的分布不平衡,个别方向甚至未能得到反映;它们对运筹学的理论及应用的意义和重要性各不相同,难易程度也有千差万别。有兴趣的读者可以在此基础上开展研究,也可以提出和研究其他有意义的问题。毕竟发现问题、提出问题、分析问题和解决问题的过程构成了运筹学的发展进程。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: