Задача о назначениях
Приводится пример решения задачи о назначении.Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й задачи на j-м машине. Задачи решаются одновременно с некоторого момента t0. Найти такое распределение задач по вычислительным машинам, чтобы общее время решения всех задач было бы минимальным при условии что на одной машине может решаться только одна задача.
Решение находим с помощью калькулятора.
Исходная матрица имеет вид:
| 5 | 5 | M | 2 | 2 |
| 7 | 4 | 2 | 3 | 1 |
| 9 | 3 | 5 | M | 2 |
| 7 | 2 | 6 | 7 | 8 |
Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| 3 | 3 | M | 0 | 0 | 2 |
| 6 | 3 | 1 | 2 | 0 | 1 |
| 7 | 1 | 3 | M | 0 | 2 |
| 5 | 0 | 4 | 5 | 6 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
| 3 | 3 | M | 0 | 0 |
| 6 | 3 | 1 | 2 | 0 |
| 7 | 1 | 3 | M | 0 |
| 5 | 0 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
| 3 | 3 | M | [0] | [-0-] |
| 6 | 3 | 1 | 2 | [-0-] |
| 7 | 1 | 3 | M | [-0-] |
| 5 | [0] | 4 | 5 | 6 |
| [-0-] | [-0-] | [-0-] | [-0-] | [0] |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 5, строку 1, столбец 2.
Получаем сокращенную матрицу (элементы выделены):
| 3 | 3 | M | 0 | 0 |
| 6 | 3 | 1 | 2 | 0 |
| 7 | 1 | 3 | M | 0 |
| 5 | 0 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 |
Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:
| 3 | 3 | M | 0 | 0 |
| 5 | 3 | 0 | 1 | 0 |
| 6 | 1 | 2 | M | 0 |
| 4 | 0 | 3 | 4 | 6 |
| 0 | 0 | 0 | 0 | 0 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
| 3 | 4 | M | 0 | 1 |
| 5 | 3 | 0 | 1 | 0 |
| 6 | 1 | 2 | M | 0 |
| 4 | 0 | 3 | 4 | 6 |
| 0 | 1 | 0 | 0 | 1 |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| 3 | 4 | M | 0 | 1 | 0 |
| 5 | 3 | 0 | 1 | 0 | 0 |
| 6 | 1 | 2 | M | 0 | 0 |
| 4 | 0 | 3 | 4 | 6 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
| 3 | 4 | M | 0 | 1 |
| 5 | 3 | 0 | 1 | 0 |
| 6 | 1 | 2 | M | 0 |
| 4 | 0 | 3 | 4 | 6 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
| 3 | 4 | M | [0] | 1 |
| 5 | 3 | [0] | 1 | [-0-] |
| 6 | 1 | 2 | M | [0] |
| 4 | [0] | 3 | 4 | 6 |
| [0] | 1 | [-0-] | [-0-] | 1 |
В результате получаем эквивалентную матрицу Сэ:
| 3 | 4 | M | 0 | 1 |
| 5 | 3 | 0 | 1 | 0 |
| 6 | 1 | 2 | M | 0 |
| 4 | 0 | 3 | 4 | 6 |
| 0 | 1 | 0 | 0 | 1 |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
| 3 | 4 | M | [0] | 1 |
| 5 | 3 | [0] | 1 | [-0-] |
| 6 | 1 | 2 | M | [0] |
| 4 | [0] | 3 | 4 | 6 |
| [0] | 1 | [-0-] | [-0-] | 1 |
Cmin = 2 + 2 + 2 + 2 + 0 = 8
