Задачи для самостоятельного решения

↑

⇐ ПредыдущаяСтр 9 из 11Следующая ⇒

В следующих задачах найти оптимальное назначение, соответствующее минимальному значению целевой функции.

1.                                        2.

3.                                           4.

5.                                     6.

7.                                         8.

9.                                         10.

В следующих задачах найти оптимальное назначение, соответствующее максимальному значению целевой функции

1.                                        2.

3.                                            4.

                                   4.2. Задача о назначениях на узкие места

Имеется n лиц и n работ. Заданы эффективности  исполнения каждым лицом каждой работы. Каждый исполнитель должен назначаться на выполнение только одной работы и все работы должны быть выполнены. Требуется найти такое назначение исполнителей на работы, при котором наименьшая эффективность выполнения работ максимальна.

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

То назначение исполнителя на работу, на котором реализуется минимальная эффективность, называют узким местом в назначении.

Нетрудно видеть, что каждое назначение задается взаимно однозначным отображением множества {1,2,…,n} на себя, т. е. образует подстановку

,

где  указывает номер назначаемой i-у исполнителю работы. Количество всевозможных назначений работников на работы равно n!

Рассмотрим алгоритм Гросса для решения задачи.

Начальный шаг. Фиксируем любое назначение P₀ , что соответсвует выбору в строках и столбцах матрицы эффективностей  ровно по одному элементу. При этом назначении вычисляется значение целевой функции, т. е. вычисляется величина . Обозначим эту величину через s.

Шаг 1. Строим двудольный граф G = (V₁UV₂ , E), вершины первой доли которого соответсвуют исполнителям, второй – работам. Ребро (v_i,u_j) E тогда и только тогда, когда a_ij > s .

Шаг 2. Ищем максимальное (по числу ребер) паросочетание в графе G = (V₁UV₂ , E).

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

Если же число ребер в паросочетании окажется меньше n, то имеющееся назначение оптимально.

Пример.Пусть задана матрица эффективностей:

Возьмем назначение . Имеем F(P₀) = 3. Строим двудольный граф:

Количество ребер в максимальном паросочетании равно 6, поэтому находим новую подстановку . Для этой подстановки имеем F(P₁) = 4. Двудольный граф имеет максимальное паросочетание с 4 ребрами. Следовательно, назначение P₁ оптимально.

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

Приведем алгоритм Кенига-Эгервари, построения максимального паросочетания в двудольном графе. Пусть G = (V₁UV₂, E) двудольный граф с |V₁| = n, |V₂| = m.

Начальный шаг. Строим таблицу размером nxm , строки которой соответсвуют вершинам первой, а столбцы – вершинам второй долей. В клетку (i, j ) ставим символ * и называем ее недопустимой, если в графе нет ребра (v_i, u_j ) для вершин v_i V₁, u_j V₂ . Если (v_i, u_j ) E, то клетку оставляем свободной и называем допустимой. Множество допустимых клеток называем независимым, если среди них нет двух, стоящих в одной строке или одном столбце. Очевидно, что между множествами независимых допустимых клеток построенной таблицы и паросочетаниями исходного двудольного графа существует взаимно однозначное соответсвие. И максимальным паросочетаниям будет соответсвовать множества независимых допустимых клеток с максимальным числом клеток.

Шаг 1. Строим произвольное множество независимых допустимых клеток, помещая в вошедшие в него клетки символ «1». Например, просмотром в порядке возрастания номеров строк слева направо и фиксацией «1» в первой по ходу просмотра допустимой клетке, которая является независимой по отношению к допустимым клеткам, отмеченных ранее.

Если окажется, что во всей таблице все клетки недопустимы, то это означает, что в графе нет ребер.

Шаг 2. Находим в таблице строки без символа «1» и помечаем их символом «-» и переходим к следующему шагу. Если в каждой строке таблицы окажется символ «1», то ребра соответсвующего паросочетания составляют наибольшее паросочетание, и действия окончены.

Шаг 3. Просмотрим все получившие пометки строки в порядке возрастании их номеров. Просмотр очередной строки состоит в следующем: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются меткой (+p), где p - номером просматриваемой строки. При этом соблюдается принцип: если пометка уже стоит, то на ее место вторая не ставится.

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

Шаг 4. Просмотрим помеченные на шаге 3 столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскивается символ «1» и строка, в которой он расположен, помечается меткой (-h), где h - номер просматриваемого столбца. При этом соблюдается прежний принцип: если столбец уже помечен, то метка не изменяется.

Если возникает ситуация, когда в просматриваемом столбце нет символа «1», то действия на данном шаге прерываются, и осуществляется переход к следующему шагу 5. 

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

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

Шаг 5. Производим изменение множества независимых допустимых клеток в таблице. Рассматриваем столбец, имеющий пометку и не содержащий символа «1». В нем ставим символ «1» в строку, номером которой помечен этот столбец. Затем в этой строке ищем «старый» символ «1» и перемещаем его по столбцу в строку, номер которой равен пометке при этом столбце. Далее в строке, куда попал последний символ «1» ищем «старый» символ «1» и с ним проделываем то же самое. В конце концов очередной перемещаемый «старый» символ «1» окажется в строке, где больше символов «1» нет, то есть в строке, помеченную символом «-». Возник новый набор независимых допустимых клеток, в котором элементов на один больше, чем в прежнем. Все метки уничтожаются и осуществляется переход на шаг 2.

Пример.Найти максимальное паросочетание для следующего двудольного графа:

v₁         v₂  v₃  v₄  v₅  v₆  v₇  v₈  v₉

u₁   u₂ u₃ u₄ u₅ u₆ u₇ u₈ u₉

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

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Первая итерация выполнения шагов 2 – 4 даст таблицу с метками:

*

*

*

*

*

*

-2

*

*

*

*

*

*

-1

*

*

*

*

*

*

-4

*

*

-3

*

*

*

*

*

*

-6

*

*

*

*

*

*

-8

*

*

*

*

*

*

*

*

*

-

*

*

*

*

*

*

-

+9

+8

+2

+8

+4

+8

+9

+4

Выполнение шага 5 увеличивает количество независимых допустимых клеток до 8.  

Выполнение второй итерации приведет к следующей таблице с метками:

*

*

*

*

*

*

-2

*

*

*

*

*

*

*

*

*

*

*

*

-4

*

*

*

*

*

*

*

*

-6

*

*

*

*

*

*

-8

*

*

*

*

*

*

*

*

*

-

*

*

*

*

*

*

+8

+8

+8

+1

Поскольку больше меток установить нельзя и столбец без символа «1» не помечен, то алгоритм завершает работу.

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров