对有序组合树法的改进

为了提高有序组合树法的运算效率，必须充分利用约束条件中的有关信息．通过深入分析，提出了极差、必选变量、不可选变量等概念，将多个约束条件联系成为一个整体．提出了用检验约束条件的相容性，并以相容性为判据进行截枝的新办法．证明了如果必选变量全部取值为1是可行解，则必是最优解。给出了改进后的有序组合树法的计算步骤流程．

Improvement to the Sequential Combination Tree Algorithm

To increase the efficiency of sequential combination tree method, it is necessary to make full use of information in the constraint conditions. Based on a thorough analysis of the method, the concepts such as ultimate difference, necessary variables, and ineligible variables were proposed to combine constraints as a whole. A new algorithm was presented, in which the compatibility of constraints are determined and taken as a criterion to cut branches. It was proved that if all the necessary variables taking 1 is a feasible solution, it is the optimum solution. The flow chart of the new algorithm was presented.