考虑冗余的极小碰集问题研究

针对海上采油平台可燃气体探测器布设优化问题,首先建立了一个精确理论模型;通过对精确理论模型进行降维、简化和数字化处理,得到一个近似应用模型,该模型可视为极小碰集问题的一个变体,即考虑冗余的极小碰集问题。证明了冗余度大于或等于2的极小碰集问题都是NP-完备的。结合探测器布设的应用背景,针对冗余度为2的问题设计了一个启发式算法,旨在保证冗余度的前提下,极小化所需探测器的数目。仿真结果表明,该算法可以在不显著增加或减少探测器安装数目的情况下,使得任何一个拟泄漏点在任何风向下发生泄漏,都可以至少被两个探测器探测到,从而大大提高平台的安全性。