组合优化若干经典问题新进展分析

摘 要：采用计算机科学和运筹学交叉的学科研究的方法，是组合优化对经典问题进行研究的方式。组合优化，就是对于离散结构的问题进行性质的求解，将不同离散问题进行结构差异的分析，采用不同的技巧和研究手段，针对经典问题进行计算和理论的研究。

关键词：组合优化；经典问题；进展分析

中图分类号：O224 文献标志码：A 文章编号：2095-2945（2018）13-0057-02

Abstract： Using the method of interdisciplinary research of computer science and operational research is the way of combinatorial optimization to study classical problems. Combinatorial optimization is to solve the problem of discrete structure， to analyze the structural differences of different discrete problems， to use different techniques and research methods， and calculate and study the classical problems.

Keywords： combinatorial optimization； classical problems； progress analysis

组合优化是采用离散结构的性质的求解的方式，摆图论和拟阵以及多面体进行性质和求解的方法，采用计算复杂性和几何计算结合的方式，运用计算机科学和运筹学的交叉，将关键的研究课题进行关注，经过组合和优化，得到了关于基础理论和方法的有效计算结果。随着网络技术和信息科学的发展，当前运用互联网进行人类生活方式的改变，例如物联网的创新发展，带来了组合优化的研究方法，包含计算复杂性理论、算法设计和分析应用的研究内容，经过设计和分析，最终在应用领域利用算法进行了成果的展示和问题的解决。

1 装箱问题

装箱问题是经典组合优化的问题，该问题经过研究后，得到了在线算法和近似算法，经典装箱问题是经过论证的，简单叙述为：给定若干尺寸进行物品的装箱，每个箱子装的物品的尺寸不能超过1，划分问题和装箱问题密切关联，根據假设，最终的问题的算法和求解值经过比率的划分，得到了结果是大于等于1，装箱问题有若干变形。将装箱装入单位的容量的箱子中，物品是通过一个一个的形式出现的。一些物品假设物品为边长不超过1的矩形，集中类型的箱子经过选择，箱子为单位正方形，可行的装箱不允许出现变尺寸装箱[1]。在物品之间以及物品的边界有任何的重叠，人们对于装箱问题的在线模式的探讨，经过同一个箱子的向量和分量的计算，可以得到结果，对于装箱的算法进行了重新的界定。在线环境下，在不知道任何后续物品的信息的前提下，必须经过装箱，并作出决定不得更改。采用这一在线算法的决策，使得物品信息在不全的情况下，是由于信息的缺失导致的算法的效果。

2 旅行商问题

TSP（旅行商）问题是组合优化的基本问题，给定的网络中一系列的点经过两两之间的距离，得到了路径是最短的。这条路径恰好经过了每个点，最后回到出发点。作为实际的问题，有徐哲对于TSP中的NP难的问题进行了验证，发现TSP问题不存在近似比，常数为多项式时间算法。通常考虑度量空间下的TSP，一般值得是点与点之间的距离，必须满足三个条件：点到自身的距离，对称性，三角不等式。在度量空间中，TSP可以找到近似比，常数为多项式时间算法。度量空间下的TSP不存在多项式时间，近似方案是一种特殊的近似算法，在多项式中可以达到近似值[2]。

3 斯坦纳树问题

网络设计中，该问题属于基础性问题，在大规模的集成电路的设计中，斯坦纳树问题在给定的赋权联通图中，对于指定的顶点进行连续的子图的求解，经过一般假设连通的费用较小，指定的点为终端，其他顶点为斯坦纳点。不同的度量空间下有不同的变形，在直线距离下给定点集的最短连通网络。

4 设施选址问题

对于供应链管理和仓库选择，该问题是组合优化领域中的热点问题，研究具有很强的应用价值。在给定的若干位置中，选择已经建立的设施，使得顾客的需求得到满足。连接的费用如果是非负的可以确定简单的结构，给定设施的地址的集合，给定的顾客地址的集合以及顾客到开设设施的服务费用，在不同地址进行费用的开设，非度量的无容量限制，确定的地质用于开设设施，则对称的度量可以无容量地限制而不能直接应用于实际，设施的选址问题，最终顾客的开设的费用和连接的费用的和最小尽管无容量设施选址问题需要经过算法设计，但是在解决实际问题上，其理论依据和算法思想等，是无容量限制的。而且，设施选址的领域还牵扯到带容量限制的设施选址，和带惩罚的设施选址问题等均为无容量限制的[3]。

5 计算复杂性理论

对于问题进行资源的定量分析，包括时间空间等，在算法复杂度的相互关系和基本性质的问题上，经过计算复杂性的分析，得到了关于计算机科学和应用数学相关领域的重大深远的影响意义。

计算复杂性理论的历史回溯，是在上世纪60年代提出的，具有空间的复杂性和时间性。经过层级定理的证明，运行时间将多项式进行了规模性的输入，得到的算法是有效的。包括中药的组合优化，有效的多项式时间算法，最大权匹配等等，计算复杂性理论的基础被用来表示非确定型和确定型图灵机模型，奠定了计算复杂性理论的基础，用来表示时间的可解的问题。上世纪70年代进行可满足性问题的组合优化问题的判定，在NP问题上，归类到完备类。NP中的任何问题在多项式内，都进行了等价的时间可解。除了个别的案例之外，每个组合优化的问题都被多项式的时间设定为完备的NP，使得PSHIFOU DENGYU泥皮这一难题受到瞩目。

6 多面体组合

采用线性代数和多面体以及方法进行组合优化的问题，是复杂性和组合优化算法结合的有力的工具。运用高效的多项式时间算法，最大关系是组合的原始对偶的最小最大定理。组合的技术不仅被用来证明是组合优化问题的多项式时间的可解性，经过多方面的紧密交织和多面体的性质加以导出，在算法上利用不等式解决了相应的组合优化的问题，还可以对多面体的线性不等式系统进行刻画，最终形成了多面体的组合研究的特征[4]。

对多面体进行匹配，也被用来为不少NP难的组合优化的问题进行设计算法的验证，例如履旅行商、设施选址问题等等。

例如在覆盖类型和装填的问题上。一个基本的框架就是逆阻和阻断的多面体理论的讨论，典型运用和研究较为广泛，在多面体组合中发挥核心作用的对偶理论，采用不等式样系统进行表达，包含了迭代建立定义多面体侧面的不等式系统，得到了逆阻的多面体的性质，对于定理和算法能够导出，能够对多面体的特征使得多面体完整的线性刻画经过证明是最小、最大关系的验证途径，建立多面体侧面和顶点的极性、相应线性的对偶整数型，多面体组合的中心任务，为分离问题涉及算法的识别性的可行解的系统，非可行解和多面体的超平面系统。

7 拟阵

随着拟阵分解定理的运用和建立，在发展促进中形成算法设计。这是一个基于某个有限集合的，满足特定公例的独立集系统，能够被贪婪算法解决，形成组合优化问题的结构特征，广泛的拟阵的应用，混合矩阵论、网络编码等，次模型和拟阵被优化界设定为重要课题，成为了次模优化的重要基石。经过定理分析和识别，产生了多项式时间算法，对于组合优化等学科领域产生了深远的影响。

8 结束语

组合优化在信息科学技术的基础上，通过数学理论和方法，与网络互联，逐步地将简单的P和NP-难进行了两级的划分，最终回到了代价和算法的精度的平衡问题上。通过对精确算法的实用性的研究，保证了算法的精确度，降低了指数的复杂性，促使人们能够对问题的计算的有效性进行深入的探讨，使得多面体理论、复杂性思想和统计方法显现出较大的作用。

参考文献：

[1]陳兆盟，吴文祥，刘小明，等.车道拥挤收费与信号控制组合优化模型研究[J].交通运输系统工程与信息，2017（5）：29-35.

[2]吴晓进.函数最优极值问题的组合优化求解[J].内蒙古师范大学学报（自然科学汉文版），2017（6）：800-802，806.

[3]朱学谦.海外石油项目多目标组合优化研究[J].河南科学，2017（12）：2041-2047.

[4]杨丽丽，袁浩浩.基于组合优化理论的协同过滤推荐算法[J].现代电子技术，2018（1）：139-142.