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

↑

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

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

1. Найти с помощью алгоритма Басакера-Гоуэна и алгоритма Клейна поток величины m = 4 с минимальной стоимостью.

[1] 2

a

t

s

b)

[2] 3

a

t

4. ЗАДАЧИ О НАЗНАЧЕНИЯХ

4.1. Классическая задача о назначениях

Задано n работ и n исполнителей, причем каждую из работ может выполнять любой из исполнителей. Стоимость выполнения i-ой работы j-ым исполнителем определяется величиной c_ij ≥ 0. Требуется распределить исполнителей на выполнение работ так, чтобы все работы были выполнены, каждый исполнитель выполнял только одну работу, и стоимость выполнения всех работ была бы минимальной.

Построим математическую модель для данной задачи. Пусть

Тогда задача может быть сформулирована в виде следующей задачи булевого программирования:

Можно привести еще одну интерпритацию постановки задачи. Построим полный двудольный граф G=(V₁UV₂ , E), вершины первой доли которого соответсвуют исполнителям, второй – работам. Припишем ребру (v_i , u_j), v_i V₁ , u_j V₂ , вес c_ij . Тогда задача заключается в поиске совершенного (покрывающего все вершины графа) паросочетания с минимальным весом.

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

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

Легко показать, что решения задач для исходной и для приведенной матриц совпадают.

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

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

Шаг 1. Для приведенной матрицы строим сеть с (2n + 2)-мя вершинами: источником s, множеством вершин S = {s₁ , … , s_n},  соответсвующими строкам матрицы стоимостей,  множеством  вершин T = {t₁ , …, t_n}, соответсвующими столбцам матрицы стоимостей, и стоком t . Источник s соединяем дугой с каждой вершиной s_i , каждую вершину t_j соединяем дугой со стоком t . Добовляем дугу   (s_i, t_j ) тогда и только тогда, когда . Пропускные способности всех дуг полагаем равными 1.

Шаг 2. Находим максимальный поток в сети из s в t. Если величина найденного потока равна n, то решение задачи получено. В оптимальном назначении x_ij = 1 огда и только тогда, когда дуга (s_i, t_j ) существует и поток по ней равен 1.

Если максимальный поток меньше n, то переходим на шаг 3.

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

Пусть при нахождении максимального потока на последнем шаге алгоритма вершины множества  оказались помеченными, а вершины множества  – непомеченными. Пусть S^”  ( T^” ) номера вершин, входящих в S^’ ( T^’ ). Находим .

Шаг 4. Вычитаем элемент  из всех элементов в строках, соответсвующих вершинам из S' и добавляем к элементам столбцов соответсвующих вершинам из T\T'.

Шаг 5.  Переходим к шагу 1 с матрицей, полученной на шаге 4.

В результате работы алгоритма в матрице стоимостей на каждой итерации появляется хотя бы один новый ноль (на месте элементов равных ), т. е. в сети появляется хотя бы одна новая дуга.

Пример.Решить задачу о назначении со следующей матрицей стоимостей:  

.

Начальный шаг. Приводим матрицу С сначала по строкам, затем − по столбцам. Приведенная матрица C^’ имеет вид

.

Итерация 1. Строим для приведенной матрицы C^’ сеть

Пропускные способности всех дуг полагаем равными 1. Находим максимальный поток в полученной сети. На последней итерации алгоритма Форда-Фалкерсона получим:

s

s₁

s₂

s₃

s₄

t₁

t₂

t₃

t₄

t

v

(-,∞)

(t₄^-,1)

(s⁺,1)

(s⁺,1)

(s₃⁺,1)

Значение максимального потока v = 2. Это меньше 4, поэтому необходимо преобразовать сеть. Имеем: S ^“ = {1, 3, 4}, T ^“= {1, 2, 3}. Находим  = 1. Преобразуем приведенную матрицу, вычитая элемент  из всех элементов в строках с номерами из S^” и добавляя к элементам столбцов с номерами, не вошедшими в T^”. Матрица C ^’ примет вид

.

Итерация 2. Получим следующую сеть:

Находим максимальный поток в сети. На последней итерации алгоритма Форда-Фалкерсона получим:

s

s₁

s₂

s₃

s₄

t₁

t₂

t₃

t₄

t

v

(-,∞)

(t₄^-,1)

(s⁺,1)

(s₃⁺,1)

Имеем: v = 3 < 4, S ^” = {1,3}, T^”= {1,2,3}. Находим . После преобразования получим матрицу

.

Итерация 3. Строим сеть. Максимальный поток в сети равен 4. Следовательно, решение получено. На сети соответствующие дуги с единичным потоком выделены. Получаем назначение: x₁₂ = 1, x₂₃ = 1, x₃₄ = 1, x₄₁ = 1. Значение целевой функции равно 13.

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

2. В некоторых случаях задачу о назначении необходимо решать на максимум. Тогда поступают следующим образом: находят ; переходят к матрице с элементами  ; решают для этой матрицы задачу минимизации.

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



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США