Задача о наименьшем покрытии

Постановка задачи

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

Алгоритм решения задачи

Задача о покрытии является достаточно сложной комбинаторной задачей, и на ЭВМ она чаще всего решается в два этапа. На предварительном этапе выясняется, имеет ли вообще исходная задача решение, и если оно существует, то определяется приближенное решение. Здесь же могут быть найдены элементы покрывающего множества (столбцы), включаемые в оптимальное решение, что позволяет упростить исходную задачу. На общем этапе на основе приближенного определяется оптимальное решение.

Нахождение приближенного решения

Задача о покрытии имеет решение, если в исходной матрице нет нулевых строк. Приближенным решением задачи о покрытии является подматрица матрицы A без нулевых строк с числом столбцов, близким к минимально возможному. Для нахождения приближенного решения, как правило, используется градиентный метод, который состоит в пошаговом выделении столбцов (включении в приближенное решение) результирующей матрицы:

• — на первом шаге выделяется столбец, содержащий наибольшее число единиц (если таких несколько, то берется любой из них), и в матрице вычеркиваются (считаются покрытыми) все строки, содержащие единицу в выделенном столбце;
• — на k-м шаге выполняются те же действия над матрицей, полученной (в результате вычеркивания строк) на предыдущем шаге.

Этот процесс заканчивается, если на очередном шаге все строки рассматриваемой матрицы оказались вычеркнутыми. Подматрица, составленная из тех столбцов исходной матрицы A, которые выделялись в процессе выполнения алгоритма, и является искомой подматрицей.

После получения приближенного решения выясняется, можно ли некоторые из столбцов включить в оптимальное решение. Это осуществляется по следующему правилу: если в какой-либо строке имеется всего один единичный элемент, то содержащий его столбец должен быть включен в оптимальное решение. При этом из подматрицы, передаваемой на оптимизацию, вычеркиваются эти столбцы и покрываемые ими элементы.

Oпределение оптимального решения Полученное на предыдущем этапе приближенное решение передается алгоритму минимизации. Целью этого этапа является дальнейшее уменьшение (если это возможно) числа столбцов подматрицы.

Для определения оптимального решения, как правило, используется метод ветвей и границ.

Метод ветвей и границ при решении задачи о наименьшем покрытии

Исходными данными для применения алгоритма является матрица, представляющая собой приближенное решение задачи о наименьшем покрытии с вычеркнутыми столбцами, включенными в оптимальное решение, и строками, которые они покрывают.

Нахождение оптимального решения задачи о наименьшем покрытии в табличной форме состоит из двух основных повторяющихся этапов.

На первом этапе находят одно из допустимых решений, а на втором оно проверяется на оптимальность. Если текущее решение не оптимально, то возвращаются на первый этап, где формируют новое допустимое решение, иначе алгоритм заканчивает работу (рис. 3.5).

Рис. 3.5.

В ходе выполнения первого этапа над столбцами, включенными в решение, ставят индексы, а снизу эти столбцы помечают знаком *.

Строки, содержащие единицу в столбцах, имеющих индекс и метку, считаются покрытыми.

В процессе проверки текущего решения на оптимальность индексы и метки со столбцов снимаются, после чего соответствующие строки считаются непокрытыми. Текущее решение является оптимальным, если число столбцов, входящих в него, меньше числа столбцов, включенных в предыдущее решение.

Алгоритм ветвей и границ для решения задачи о наименьшем покрытии в табличной форме состоит из следующих шагов.

• 1. Среди столбцов, не имеющих индекса, находится столбец, обладающий максимальной мощностью (мощностью столбца называют число единиц в нем, расположенных в непокрытых строках). Над ним указывается индекс, значение которого равно, например, числу обращений к п. 1, а снизу он помечается знаком *. Покрываемые им строки отмечаются справа знаком +.
• 2. Находится оценка нижней границы количества столбцов L1 текущего решения как сумма числа столбцов, имеющих метку *, и числа столбцов, необходимых для покрытия непокрытых строк. Последнее определяется как минимальное число столбцов, не имеющих индекса, суммарная мощность которых больше или равна числу непокрытых строк (если мощность оказывается меньшей, то оценка нижней границы считается равной общему числу столбцов матрицы покрытий).
• 3. Проверяется, если число столбцов L1 текущего решения больше или равно числу столбцов L0 предыдущего решения, то переходят к п. 4, иначе, если не все строки покрыты, возвращаются к п. 1. (Первоначально L0 приравнивают к числу столбцов в матрице покрытий.) Если же L1
• 4. Проверяется, помечен ли столбец, включенный в решение последним. Если помечен, то метка с него снимается (соответствующие строки считаются непокрытыми), и переходят к п. 2. Если же столбец, включенный в решение последним, не помечен, то с него снимается индекс.
• 5. Проверяется наличие столбцов с индексами. Если таких нет, то исследуемое решение оптимально, иначе возвращаются на п. 4.

Решение задачи о наименьшем покрытии на основе линейного программирования

Пусть x_j=1, если S_j — покрывающее множество войдет в покрытие и равно 0 — в противном случае. Тогда задача сводится к задаче целочисленного программирования:

минимизировать Z=.

при ограничениях.

1, где i=1,2,N.

Решение задачи оптимизации системы методом линейного программирования может быть осуществлено с помощью пакета MS EXCEL.