组合最优化

来自中文百科专业版
跳转至: 导航搜索

  组合最优化汉语拼音:Zuhe Zuiyouhua;英语:Combinatorial optimization),在给定有限集的所有具备某些条件的子集中,按某种目标找出一个最优子集的一类数学规划。又称组合规划。从最广泛的意义上说,组合规划与整数规划这两者的领域是一致的,都是指在有限个可供选择的方案的组成集合中,选择使目标函数达到极值的最优子集。

  组合最优化发展的初期,研究一些比较实用的基本上属于网络极值方面的问题,如广播网的设计、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后,对拟阵中的一些理论问题的研究成为组合规划研究的新课题,并得到应用。现在应用的主要方面仍是网络上的最优化问题,如最短路问题、最大(小)支撑树问题、最优边无关集问题、最小截集问题、推销员问题等。