ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.04.2024
Просмотров: 227
Скачиваний: 0
37
задачи.
Рассмотрим алгоритм решения таких задач на примере.
Пусть для выполнения пяти различных работ имеется пять человек. Из отчетных данных известно, какое время требуется каждому из них для выполнения каждой работы. Эти данные приведены в таблице.
Исполнители |
|
|
Работы |
|
|
Наличие |
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
3 |
4 |
5 |
|
|
|
|
|
|
|
|
|
1 |
2 |
9 |
|
2 |
7 |
1 |
1 |
|
|
|
|
|
|
|
|
2 |
6 |
8 |
|
7 |
6 |
1 |
1 |
|
|
|
|
|
|
|
|
3 |
4 |
6 |
|
5 |
3 |
1 |
1 |
|
|
|
|
|
|
|
|
4 |
4 |
2 |
|
7 |
3 |
1 |
1 |
|
|
|
|
|
|
|
|
5 |
5 |
3 |
|
9 |
5 |
1 |
1 |
|
|
|
|
|
|
|
|
Потребности |
1 |
1 |
|
1 |
1 |
1 |
5 |
|
|
|
|
|
|
|
|
В данном случае величины Cij представляют собой затраты времени
каждого работника на выполнение каждой из работ, а величины xij равны 1
или 0, причем xij =1, если работник i назначен на работу j, и 0 во всех
остальных случаях.
1, если i работникназначенна j работу, |
|
xij = |
0, востальныхслучаях. |
|
|
Таким образом, задача сводится к минимизации функции
n n
Z = ∑∑Cijxij i=1 j=1
при следующих ограничениях:
n
∑xij =1, j =1,n;
i=1
n
∑xij =1, i =1,n;
j=1
38
xij = 0 или1 ( xij = xij2 ).
Ясно, что если отбросить последнее условие и заменить его условием xij ≥ 0 , то получается транспортная задача, в которой все потребности и все ресурсы равны 1.
Метод решения задачи о назначении основан на двух теоремах. Первая из них утверждает, что решение не изменится, если прибавить к любому столбцу или строке матрицы (Cij ) некоторую константу или вычесть ее из них.
Теорема 1.
|
|
|
|
n n |
|
|
|
|||
Если xij = Xij минимизирует |
Z = ∑∑Cijxij |
по всем xij , |
таким, что |
|||||||
|
|
|
|
i=1 j=1 |
|
|
|
|||
|
n |
n |
|
|
|
|
|
|
|
|
xij ≥ 0 |
и ∑xij |
= ∑xij =1, то xij = Xij |
минимизирует |
также |
функционал |
|||||
|
i=1 |
j=1 |
|
|
|
|
|
|
|
|
n |
n |
|
|
|
|
|
|
|
|
|
Z' = ∑∑C'ijxij , где C'ij = Cij − ui − vj |
i, j = |
1,n. |
|
|
|
|
||||
i=1 j=1 |
|
|
|
|
|
|
|
|
|
|
Доказательство: |
|
|
|
|
|
|
|
|
||
Для доказательства первой теоремы заметим, что |
|
|
||||||||
n |
n |
n n |
|
n |
n |
n |
n |
|
||
Z' = ∑∑C'ijxij = ∑∑(Cij − ui − v j )xij = ∑∑Cijxij − ∑ui |
∑xij − |
|
||||||||
i=1 j=1 |
i=1 j=1 |
|
i=1 j=1 |
i=1 |
j=1 |
|
||||
n |
n |
n |
n |
|
|
|
|
|
|
|
− ∑v j ∑xij = Z |
− ∑ui − |
∑vj . |
|
|
|
|
|
|
|
|
j=1 i=1 |
i=1 |
j=1 |
|
|
|
|
|
|
|
|
Вследствие того, что величины, вычитаемые из Z с целью получения |
||||||||||
Z' , не зависят от xij , Z' |
достигает минимума всегда, когда минимизируется |
|||||||||
Z, и наоборот. ■ |
|
|
|
|
|
|
|
|
||
Теорема 2. |
|
|
|
|
|
|
|
|
||
Если все |
Cij ≥ 0 |
и можно |
отыскать набор xij = Xij |
такой, что |
||||||
n n |
|
|
|
|
|
|
|
|
|
|
∑∑Cijxij = 0 , то это решение оптимально. |
|
|
|
|||||||
i=1 j=1
Вторая теорема очевидна.
39
Метод решения сводится к прибавлению констант к строкам и столбцам и вычитанию их из строк и столбцов до тех пор, пока достаточное число величин Cij не обращается в нуль, что дает решение, равное нулю.
Отыскание решения начинают, вычитая наименьший элемент из каждой строки исходной матрицы. Результат вычитания приведен в таблице (справа указано сколько единиц вычитали из каждой строки).
|
1 |
2 |
3 |
|
4 |
5 |
Вычитается |
|
|
|
|
|
|
|
|
1 |
|
1 |
8 |
1 |
6 |
0 |
1 |
2 |
|
5 |
7 |
6 |
5 |
0 |
1 |
3 |
|
3 |
5 |
4 |
2 |
0 |
1 |
4 |
|
3 |
1 |
6 |
2 |
0 |
1 |
5 |
|
4 |
2 |
8 |
4 |
0 |
1 |
|
|
|
|
|
|
|
|
Затем, вычитаем минимальный элемент из каждого столбца. Составляем следующую таблицу (в нижней строке указано сколько единиц вычитали из каждого столбца).
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
0 |
7 |
0 |
4 |
0 |
|
|
|
2 |
|
4 |
6 |
5 |
3 |
0 |
|
|
3 |
|
2 |
4 |
3 |
0 |
0 |
|
|
4 |
|
|
|
|
|
|
|
|
|
2 |
0 |
5 |
0 |
0 |
|
|
|
5 |
|
3 |
1 |
7 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вычитается |
1 |
1 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Из столбцов и строк было вычтено всего 10 единиц. Поэтому для правильной оценки любого решения необходимо прибавить к результату 10 единиц.
Прежде всего стремятся отыскать решение, включающее лишь те
40
клетки, в которые стоят нулевые элементы, так как, такое решение, если его удается найти, будет наилучшим из всех возможных. Попробуем найти такое решение среди полученных нулей, помня, что в каждой строке и каждом столбце может быть только одно назначение. Получим допустимое решение. Оно помечено в таблице круглыми скобками (в этом случае не удалось отыскать решение среди одних нулей).
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
1 |
0 |
7 |
(0) |
4 |
0 |
2 |
(4) |
6 |
5 |
3 |
0 |
3 |
2 |
4 |
3 |
(0) |
0 |
4 |
2 |
(0) |
5 |
0 |
0 |
5 |
3 |
1 |
7 |
2 |
(0) |
|
|
|
|
|
|
Итак, получено решение: x13=1, x21=1, x34=1, x42=1, x55=1. Суммарные затраты времени на выполнение всех работ равны 14. Это число получим, если сложим затраты времени каждого работника, назначенного на выполнение одной из работ, взятые в исходной таблице.
2.3.1. Алгоритм решения задачи о назначении
Для того, чтобы определить, возможно ли улучшение решения, применяется следующий алгоритм.
Шаг 1. Провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули (можно показать, что во всех матрицах n ×n все нули можно пересечь меньшим числом линий, чем n, тогда и только тогда, когда среди этих нулей решение не содержится).
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
41
1 |
0 |
7 |
0 |
4 |
0 |
2 |
4 |
6 |
5 |
3 |
0 |
3 |
2 |
4 |
3 |
0 |
0 |
4 |
2 |
0 |
5 |
0 |
0 |
5 |
3 |
1 |
7 |
2 |
0 |
|
|
|
|
|
|
Использованы только 4 линии, а порядок матрицы пятый, следовательно, нулевые клетки не содержат оптимального решения.
Шаг 2. Выбрать наименьший элемент, через который не проведена линия (в нашем случае – это 1 в клетке (5,2)).
Шаг 3. Вычесть это число из всех элементов, через которые не проведена ни одна линия, и прибавить его ко всем элементам, через которые проведены 2 линии. Другие элементы оставить без изменений.
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
1 |
0 |
7 |
0 |
4 |
1 |
|
2 |
3 |
5 |
4 |
2 |
0 |
|
3 |
2 |
4 |
3 |
0 |
1 |
|
4 |
2 |
0 |
5 |
0 |
1 |
|
5 |
2 |
0 |
6 |
1 |
0 |
|
|
|
|
|
|
|
|
Этот шаг должен приводить к появлению нуля в клетке, где его ранее не было. В нашем случае – в клетке (5,2).
Шаг 4. Определить, имеется ли решение среди нового набора нулей. (В нашем случае оно отсутствует) Если решение не обнаруживается, то вернуться к шагу 1 и выполнять алгоритм до тех пор, пока не будет найдено решение.
Теперь наименьшее незачеркнутое число 2. Вычтем его из всех элементов, через которые не проведена ни одна линия и прибавим его ко всем элементам, зачеркнутым дважды. Получим три новых нуля в клетках (3,1), (4,1), (5,1). Среди нового набора нулей пытаемся отыскать решение.