Теория графов

Должно выполняться дополнительное условие: на каждую работу назначается только один работник и все работы должны быть выполнены.

3.7.2 Венгерский метод решения задачи о назначениях в матричной форме

Метод был предложен венгерским математиком Эгервари. Прежде чем перейти к рассмотрению венгерского метода, условимся элементы матрицы, образующие некоторое множество, называть независимыми, если никакие два элемента этого множества не лежат на одной и той же линии (строке, столбце). Так, например, элементы вида a_jj (j=1,N) независимы. Задача фактически сводится к определению N независимых элементов матрицы {a_ij} так, чтобы сумма этих элементов была максимальной. В процессе решения задачи приходится выделять отдельные линии матрицы (строки или столбцы). Выделенные линии отмечаются знаком +. Элементы, находящиеся в выделенных строках или столбцах, называются выделенными, а остальные - невыделенными. Алгоритм состоит из подготовительного этапа и ряда последовательно выполняемых итераций.

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

Итак, подготовительный этап заканчивается выделением звездочками независимых нулей.

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

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

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

Этап 3. Среди элементов, находящихся в невыделенных линиях, выбирается минимальный, который прибавляется к элементам выделенных столбцов и вычитается из элементов не выделенных строк. В результате этих операций появляются невыделенные нули.

3.7.3 Решение задачи о назначениях на основе линейного программирования

Пусть x_ij=1, если i-й работник выполненяет j-ю работу и равно 0-в противном случае. Тогда задача сводится к задаче целочисленного программирования:

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

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

=1,

=1 , где - целые числа .

3.7.4 Модификации задачи о назначениях

1. В ряде случаев представляется целесообразным решать задачу о назначениях не на максимум суммы n независимых элементов, а на ее минимум. В этом случае алгоритм венгерского метода отличается только подготовительным этапом. Для решения задачи на минимум достаточно в квадратной матрице производительностей A = {d_ij} заменить у элементов d_ij знаки на обратные, т.е. матрица будет иметь вид A = {-d_ij}. В остальном алгоритм остается без изменения. Поэтому от задачи максимизации всегда можно перейти к задаче минимизации.

2. Иногда в задаче о назначении матрица эффективностей не является квадратной: число исполнителей m не равно числу работ n. Допустим, mn. Построим тогда квадратную матрицу эффективностей введением (m-n) фиктивных работ, которые выполняются всеми лицами с одинаковой эффективностью, равной нулю. Решение видоизмененной задачи дает некоторое решение исходной задачи. Лицо, назначенное на фиктивную работу, остается без назначения.

В случае mn достраиваем матрицу эффективностей до квадратной введением (n-m) фиктивных исполнителей, имеющих нулевую эффективность на всех работах. Матрица эффективностей становится квадратной.

3. В ряде случаев допускается, чтобы i-исполнитель (например, узел связи c_i) мог выполнять две работы (например, обслуживать два населенных пункта из множества населенных пунктов B_i, i = 1,n). Для решения этой задачи условно представим i-исполнитель в виде двух самостоятельных исполнителей А_i' и A_i^”. Исходные данные для исполнителей А_i' и A_i^” должны быть одинаковы с данными для исполнителей A_i. В этом случае формально происходит увеличение числа исполнителей и может потребоваться увеличение числа фиктивных работ. Изложенный подход позволяет существенно расширять возможности практического использования задачи о назначениях.

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

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

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

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

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

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

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

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

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

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

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

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

Oпределение оптимального решения

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

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

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

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

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

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

Рис. 3.5

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

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

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

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

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

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

3. Проверяется, если число столбцов L1 текущего решения больше или равно числу столбцов L0 предыдущего решения, то переходят к п. 4, иначе, если не все строки покрыты, возвращаются к п.1. (Первоначально L0 приравнивают к числу столбцов в матрице покрытий.) Если же L1<L0 и все строки покрыты, то формирование очередного допустимого решения закончено. В этом случае запоминают номера и число помеченных столбцов и переходят к проверке решения на оптимальность.

4. Проверяется, помечен ли столбец, включенный в решение последним. Если помечен, то метка с него снимается (соответствующие строки считаются непокрытыми), и переходят к п. 2. Если же столбец, включенный в решение последним, не помечен, то с него снимается индекс.

5. Проверяется наличие столбцов с индексами. Если таких нет, то исследуемое решение оптимально, иначе возвращаются на п.4.

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

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

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

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

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

1. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000. 304 c.

2. Математика. Общий курс. СПб.: Изд-во ”Лань”, 2002. 960 c.

3. Кузнецов О.П., Адельсон-Вельский Г.И. Дискретная математика

для инженера. М.: Энергоатомиздат, 1997. 344 c.

4. Кабанов А.Н. Математические модели и алгоритмы оптимизации дискретных систем: Учеб. пособие./ Рязан.радиотехн.ин-т. Рязань, 1987. 64 c.

5. Емеличев В.А., Мельников О.И. Лекции по теории графов. М.: Наука, 1990. 384 с.

Размещено на Allbest.ru