算法的发现(IV)——论组合优化的特性清单

组合优化问题的定义［１］是定义１问题ＸＹＺ是指：对于每一个π（１）－集合Ｓ，从其诸π（２）－子集合中找出π（３）－（优）集合Ｓ＊．本文直接从它出发，§§２－５讨论诸π（ｉ）－集合（ｉ＝１，２，３）的某基本特性（ｐｒｏｐｅｒｔｙ），公理（ｐｏｓ－ｔｕｌａｔｅ），或者特殊情形（ｐａｒｔｉｃｕｌａｒｃａｓｅ）．列出了一个清单ＰＰＰ，叫做特性清单．它远非完善，但已经可以用来讨论不少问题．§６起简单地讨论若干个子清单，所对应的问题类，并讨论求解它们的一些方法．     

算法的发现（Ⅲ）——非负独立集合问题与线性规划

本文讨论最大权非负独立集合问题（ξ，１）。它与等式型线性规划问题等价，因此后者在组合优化中有着明显的“合法”地位，沿着文（１，２）的思路，前者得到建党妆始基可行解的生成算法（ξ，３），它与后者的Ｍ法和二步法迥然不同。用对称差分解法自然得到一个算法（ξ，４），相当于改进单纯形算法，最后，还作了几点评证（ξ５）。