组合优化（Ⅱ）——对称差分解法的又一应用

本文先讨论函数的增量与微分对于连续型最优化问题的作用，析出有益的启发。用之于组合优化，得到了求解问题的一个方法——对称差（的）分解法。文献［２］对它作了讨论并得到不少应用。本文提出两个赋权凸锥独立集合问题。它们是典型的组合优化问题，分别与线性规划中两个互为对偶模型等价；用对称差分解法进行求解。

算法的发现（Ⅱ）──对称差（的）分解法及其应用

本文摹仿古典数学的导数、差分概念，在组合优化中建立枚举章法下的一个方法一一对弥差分解法，给出一个求解某些问题的一般模式。用它统一地讨论组合最优化的六个基本图论问题：最短路问题，最小生成树问题，匹配问题，巡迥商问题，中国邮路问题和最大流问题。讨论表明，Ｂｅｌｌｍａｎ最优性原理，交错链，增值路等概念都是对称差分解法在具体问题中的自然结果。还表明，涉及上述大个问题的２０多个著名定理都是定理４的具体推论。