Постановка задачи. В матричной форме задача о покрытии формулируется следующим образом

В матричной форме задача о покрытии формулируется следующим образом. Дана матрица A(N,M) с элементами из множества {0,1}. При этом считают, что номера строк образуют покрываемое множество, а номера столбцов - покрывающее. Требуется найти подматрицу матрицы A, которая содержит N строк (среди которых нет нулевых) и состоит из минимально возможного числа столбцов. К подобной формулировке могут быть сведены многие оптимизационные задачи управления.