组合最优化中的布尔方法

本文旨在从NP-完全性理论的角度,以拟布尔函数最优化为典型实例介绍组合最优化问题的一些研究方法和取得的主要进展。并且也提出了一些有待解决的问题和可能的研究途径。

组合最优化中的布尔方法(续二)

§13 天篷取优 为了计算最好的天篷,我们研究在SAM-图S_f上的最大W-对集问题(WM)。

组合最优化中的布尔方法(续一)

§7 对偶性 我们还是先从如下的一般拟布尔最优化问题——称之为原问题——开始: (7.1) 任一线性拟布尔函数t(x)=α_0+α_1x_1+…+α_nx_n,如果对于任何x∈B^n均有t(x)≥f(x),则称t(x)为f(x)的一个上平面。若用t(x)代替(7.1),则得 (7.2)称这个问题为(7.1)的线性松驰。当然,(7.2)的最优值提供了(7.1)的一个上界。 令J为f(x)的所有上平面组成的集合。我们的兴趣在于找f(x)的这样的一个上平面t_0(x)使得(7.2)的最优值与(7.1)的最优值最接近。