0—1规划的切割压缩寻优法

1 引言0—1规划是管理决策中经常遇到的一类重要数学模型，但至今没有象求解线性规划单纯形法那样有比较成熟的一般寻优方法。目前尚有隐枚举法、极点排序法、有序组合树法及群论法等优化方法，各种方法又各具特色。考虑到0—1规划以致于整数规划都只是线性规划的特殊情形，故本文在线性规划单纯形法基础上提出0—1规划的切割压缩寻优法。这里的切割是指将可行域中多余部分首先切掉，所谓压缩就是让目标函数超平面沿法线方向不断向原点平移，直到与单位超正方体的某极点相交，得0—1规划的最优解。该方法不仅直观易懂，而且通过算例证明简便易行。