МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ЗАДАЧА О НАЗНАЧЕНИЯХ С
ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ
Учебно-методическое пособие для вузов
Составители:
Медведева Ольга Александровна
Медведев Сергей Николаевич
Издательско-полиграфический центр
Воронежского государственного университета
2015
Стр.1
ВВЕДЕНИЕ
Задача о назначениях, её линейные, квадратичные и многоиндексные
разновидности привлекают внимание исследователей ввиду своей обширной
применимости в различных областях научной и практической деятельности.
Самой известной и изученной является линейная закрытая задача о
назначениях, которая относится к задачам дискретной оптимизации. Для неё
существуют точные методы решения, такие как венгерский алгоритм, метод
потенциалов, метод ветвей и границ. Однако дополнительные требования,
обусловленные практическими задачами, приводят к различным
модификациям математической модели, в частности к изменению
стандартных и/или добавлению новых ограничений. При этом также
необходимо внесение изменений в стандартные алгоритмы.
Авторы старались в данной работе привести помимо линейной задачи о
назначениях и венгерского метода её решения разнообразные модификации
данной задачи, требующие изменения математической модели и алгоритма
решения.
Методическая разработка состоит из 2-х параграфов. В 1-м
рассмотрена классическая задача о назначениях, а также венгерский метод
для её решения с подробным описанием этапов, во 2-м представлены
модификации задачи, связанные с внесением дополнительных требований в
формулировку, приведены их математические модели и алгоритмы решения.
Все методические рекомендации проиллюстрированы необходимым
количеством примеров.
3
Стр.3
матрица, у которой в каждой строке и в каждом столбце имеется ровно одна
единица, а остальные элементы являются нулями.
Заметим, что все задачи о назначениях размера n n имеют одно и то
же допустимое множество и отличаются друг от друга только
коэффициентами целевой функции, т.е. матрицей затрат
C c
{ } .
ij n n
1.2 Венгерский метод решения
Приведём формулировки нескольких теорем, на которых основан
венгерский метод:
Теорема 1. Если элементы матриц
равенствами ijd c α βj
ij
i
C { }ij n n
c
и D { }ij n n
d
связаны
, то задачи о назначениях с данными матрицами
эквивалентны, т.е. множества их решений (оптимальных точек) совпадают.
В дальнейшем преобразования вида ij
d c α βj
ij
i
(добавление ко
всем элементам любой строки или любого столбца одного и того же числа)
будем называть эквивалентными преобразованиями.
Следствие. Всегда можно считать, что все элементы матрицы C
неотрицательны, т.е.
i 0,
j
i 0).
j
i j , 1,n (c ji 0).
Теорема 2. Пусть все элементы матрицы C неотрицательны, т.е.
i j , 1,n (c Если в ней имеются n независимых нулевых элементов
с то их сумма является минимальной.
На основе представленных выше утверждений рассмотрим венгерский
метод решения задачи о назначениях. Данный алгоритм предназначен для
решения классической (закрытой) задачи о назначениях с заданной матрицей
C { }ij n n
c
(где сij – конечные числа). Общая схема метода имеет вид:
6
Стр.6
Начало
Исходные данные: матрица затрат
C { }ij n n
c
Этап 1. Приведение матрицы C
Этап 2. Вычисление максимального
Этап 4. Отыскание n
независимых нулей
числа k независимых нулей в матрице C
k
= n
< n
Конец
Остановимся подробнее на каждом из этапов.
Этап 1 (приведение матрицы)
Матрица C называется приведённой, если все её элементы
неотрицательны и, кроме того, в каждой строке и в каждом столбце имеются
нулевые элементы.
Таким образом, приведённая матрица C удовлетворяет двум условиям:
1.
2. j c i c 0).
Для приведения матрицы C с
i j , 1,n (c ji 0),
i
(
ij
0)
j
(
ij
элементами
с i 0j
нужно
воспользоваться эквивалентными преобразованиями. При этом сначала
осуществляется приведение матрицы по строкам, т.е. в каждой строке ищется
наименьший элемент ,iα i n и осуществляется переход к матрице C с
элементами с ijc α j 1, .n Если матрица C оказалась не приведённой
по столбцам, то в каждом столбце ищется наименьший элемент β j n и
осуществляется переход к матрице C , элементы которой вычисляются
7
1, ,
ij
i ,
j ,
1, ,
Этап 3. Получение
новых нулей
Стр.7
следующим образом: с ij
приведённой.
ij
c β i . Матрица по построению является
j ,
1,n
приведённой матрице
Этап 2 (вычисление максимального числа независимых нулей)
При вычислении максимального числа k независимых нулей в
необходимо
воспользоваться
следующим
утверждением:
Теорема 3 (теорема Кёнига). Максимальное число независимых нулей
равно минимальному суммарному числу горизонтальных и вертикальных
линий (строк и столбцов), которыми можно зачеркнуть все нулевые
элементы приведённой матрицы.
Отыскание независимых нулей осуществляется, вообще говоря,
полным перебором всех возможных вариантов.
Для практической реализации этапа 2 существуют разные подходы. Так
для задач небольшой размерности поиск можно организовать следующим
образом: каждый раз выбирается строка (столбец) с наименьшим
количеством нулей и вычёркиваются столбцы (строки), соответствующие
нулям. Однако такой способ вычёркивания является неточным и при
увеличении размерности матрицы может давать число линий больше
минимально возможного значения.
Существуют и другие подходы к реализации перебора. Далее
рассмотрим способ, который гарантированно находит как минимальное
число линий вычёркивания, так и сами независимые нули. Он основан на
интерпретации теоремы Кёнига в терминах теории графов.
Введём некоторые определения.
Граф
G ( , )V E
его вершин X и Y такие, что , X Y , X Y V , X Y и всякое
называется двудольным, если существуют множества
,
ребро графа G инцидентно некоторой вершине из X и некоторой вершине из
Y . Множества X и Y называются долями графа G.
8
Стр.8
Паросочетанием в графе G будем называть множество его рёбер,
попарно не имеющих общих вершин.
Теорема 4 (теорема Кёнига в терминах теории графов): число рёбер
в максимальном паросочетании двудольного графа равно мощности его
минимального вершинного покрытия.
Данная формулировка интерпретируется в матричном виде следующим
образом: строки приведённой матрицы назначений соответствуют вершинам
левой доли двудольного графа, а столбцы – вершинам правой доли. Нулям
матрицы отвечают рёбра в двудольном графе.
Таким образом, чтобы найти независимые нули в матрице назначений,
следует найти максимальное паросочетание
по теореме Кёнига
соответствующего двудольного графа.
Рассмотрим следующий
алгоритм поиска максимального
паросочетания в двудольном графе:
1. По заданной матрице затрат C построить двудольный граф по
правилу: дуга ( , )i j существует, если
c . Добавить в граф две
i 0j
вершины: источник s и сток t . Добавить дуги, идущие из источника
во все вершины левой доли графа, и дуги, идущие из всех вершин
правой доли графа в сток.
2. Найти путь из s в t . Все дуги, входящие в найденный путь,
поменять на обратные. Удалить дуги, выходящие из источника s и
входящие в сток t .
3. Прямые дуги найденного пути добавляются в решение, обратные
дуги из решения удалить. Если допустимые пути из s в t есть, то
переход к шагу 2, иначе переход к шагу 4.
4. Записать ответ. Дуги, попавшие в решение, соответствуют
независимым нулям в матрице C.
В результате работы алгоритма будут найдены независимые нули в
приведённой матрице затрат. Однако для дальнейшей работы венгерского
метода, а именно, для реализации этапа 3, необходимо знать не только
9
Стр.9
количество независимых нулей, но и горизонтальные и вертикальные линии,
которыми зачеркнуты все нулевые элементы приведённой матрицы. Для
этого воспользуемся следующим алгоритмом.
Алгоритм вычёркивания независимых нулей.
1. Найти строку без независимых нулей. Пометить её.
2. В найденной строке выбрать ноль. Пометить соответствующий
столбец.
3. В найденном столбце найти независимый ноль. Пометить
соответствующую строку и т.д.
По данное схеме перебираются все строки, не содержащие
независимых нулей. Помеченные на предыдущих этапах строки и столбцы не
учитываются при поиске. В искомое вычёркивание помещаются все
непомеченные строки и все помеченные столбцы.
Этап 3 (получение новых нулей)
Обозначим через ( )r
ij
r раз (r = 0,1,2) на этапе 2, и положим α min( )ijс 0
с элемент приведённой матрицы ,C зачёркнутый
, где минимум берётся по
всем i, j, т.е. ищется наименьший из незачеркнутых элементов матрицы .C
Построим матрицу ,C проведя пересчёт элементов матрицы C следующим
образом:
a)
b)
c)
( )ijс ,ij
2
c
( )ijс ,
1
0
α cij
( )ijс .
α cij
Такие преобразования являются следствием применения теоремы 1,
согласно которой задача с новой матрицей C оказывается эквивалентна
исходной и, кроме того, элементы этой новой матрицы неотрицательны.
Переход к этапу 2.
10
Стр.10