Файл: Практикум Челябинск 2019.pdf

56
Практическая работа 4. ЗАДАЧА О НАЗНАЧЕНИЯХ
КРАТКАЯ СПРАВКА
Задача о назначениях – частный случай транспортной задачи.
Такая задача решается

при определении маршрута передвижения людей, автомашин;

при распределении людей на работы, должности;

при распределении групп по аудиториям и т.д.
Общая постановка задачи. Требуется распределить n работ между n потенциальными кандидатами так, чтобы затраты на выполнение всех работ были минимальными или общая эффективность выполнения всех работ была максимальной. При этом каждого кандидата можно назначить на выполнение только одной работы, а каждая работа, в свою очередь, должна выполняться только одним кандидатом.
Математическая модель задачи о назначениях в случае минимизации затрат:




n
i
n
j
ij
ij
min
x
c
1 1
при ограничениях
 





















n
,
j
,
n
,
i
,
,
x
,
n
,
i
,
x
,
n
,
j
,
x
ij
n
j
ij
n
i
ij
1 1
1 0
1 1
1 1
1 1
, где с
ij
– затраты на выполнение i-м рабочим j-ой работы;
x
ij
– переменная модели:
x
ij
= 1, если i-й рабочий назначен на работу j,
x
ij
= 0, если i-й рабочий не назначен на работу j.
В случае максимизации эффективности выполнения всех работ за с ij обозначают коэффициент, показывающий эффективность выполнения i-м рабочим j-й работы, и задача решается на максимизацию целевой функции.
Если количество потенциальных кандидатов не равно количеству работ, задача является открытой или несбалансированной и требует приведения к замкнутому виду путем введения недостающих кандидатов или работ в необходимом количестве, для которых все с
ij
= 0.
4.1. Решение задачи о назначении с помощью программы Microsoft
Office Excel
Пример 4.1. Необходимо распределить четырех рабочих по четырем видам работ. Различная квалификация рабочих обуславливает различную

57 стоимость выполнения работ. Стоимость работ
с
ij
(усл. ден. ед.) приведена в таблице 4.1. Как распределить работы между рабочими, чтобы общая стоимость всех видов работ была минимальной?
Таблица 4.1
Рабочие
Виды работ
1
2
3
4
Р
1
50 50 120 20
Р
2
70 40 20 30
Р
3
90 30 50 140
Р
4
70 20 60 70
Решение
1. Составим математическую модель задачи.
Переменные:


4 1
4 1
1 0
,
j
;
,
i
j
работу
на
назначен
i
работник
если
,
j;
работу
на
назначен
не
i
работник
если
,
x
ij






Целевая функция – общая стоимость всех видов работ, которую необходимо минимизировать:
 
min
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
X
F


















44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 70 60 20 70 140 50 30 90 30 20 40 70 20 120 50 50
Ограничения:

по работам























;
x
x
x
x
,
x
x
x
x
,
x
x
x
x
,
x
x
x
x
1 1
1 1
44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11

по работникам























;
x
x
x
x
,
x
x
x
x
,
x
x
x
x
,
x
x
x
x
1 1
1 1
44 34 24 14 43 33 23 13 42 32 22 12 41 31 21 11

.
x
ij
0

2. Введем исходные данные.
Экранные формы, задание переменных, целевой функции и ограничений представлены на рисунках 4.1

4.5.

58
Рис. 4.1. Исходные данные для решения задачи о назначениях
Рис. 4.2. Исходные данные для решения задачи о назначениях (режим
Формулы / Показать формулы)

59
Рис. 4.3. Формулы для вычисления ограничений по работам
Рис. 4.4. Формулы для вычисления ограничений по работникам
Рис. 4.5. Формула для вычисления значения целевой функции
3. Решим задачу, используя надстройку Поиск решения (Данные/ Поиск
решения).
Общий вид диалогового окна Поиск решения приведен на рисунке 4.6.
Рис. 4.6. Заполненное диалоговое окно Поиск решения

60
В группе Ограничения: заданы, кроме остальных, ограничения на
двоичность переменных (первая запись (см. рис. 4.6)), означающие, что x
ij
должны быть 0 или 1 (рис. 4.7).
Рис. 4.7. Введение ограничения на двоичность переменной
Ответ. Проведенные расчеты (рис. 4.8) показывают, что минимальная общая стоимость всех видов работ составляет 140 усл. ден. ед. При этом работника Р
1
необходимо назначить на работу 4; работника Р
2

на работу
3; работника Р
3

на работу 2, а работника Р
4

на работу 1.
Рис. 4.8. Результат решения задачи о назначении

61
Пример 4.2. Пусть в задаче из примера 4.1 можно ввести нового
(пятого) рабочего, способного выполнить любой вид работ со стоимостью соответственно 60, 45, 30 и 80 усл. ден. ед. Определить, каким образом данная мера повлияет на назначение рабочих и минимизацию общей стоимости работ.
Решение
Для того, чтобы ответить на этот вопрос, необходимо добавить ограничение по пятому работнику и в ограничениях по работам знак = заменить на знак

(рис. 4.9, 4.10).
Рис. 4.9. Исходные данные для решения задачи о назначениях (режим
Формулы / Показать формулы) для пяти работников
Рис. 4.10. Заполненное диалоговое окно Поиск решения для пяти работников

62
Результат решения задачи представлен на рисунке 4.11.
Рис. 4.11. Результат решения задачи для пяти работников
Выводы
Общая стоимость всех видов работ составляет 120 усл. ден. ед., т.е. при вводе пятого работника общая стоимость работ уменьшается на 20 усл. ден. ед.
Прием на работу работника Р
5
приведет к изменению назначений работников на работы, но при этом работник Р
3
должен быть уволен или отправлен в отпуск (см. рис. 4 11) .
Пример 4.3. Пусть в задаче из примера 4.1 необходимо ввести новый вид работ, который может выполнить любой из четырех рабочих, со стоимостью соответственно 20, 10, 20 и 80 усл. ден. ед. Будет ли новая работа более выгодной по сравнению с имеющимися?
Решение
Для того, чтобы ответить на этот вопрос, необходимо добавить ограничение по пятой работе и в ограничениях по работникам знак = заменить на знак

(рис. 4.12, 4.13).

63
Рис. 4.12. Исходные данные для решения задачи о назначениях (режим
Формулы / Показать формулы) для пяти работ
Рис. 4.13. Заполненное диалоговое окно Поиск решения для пяти работ
Результат решения задачи представлен на рисунке 4.14.

64
Рис. 4.14. Результат решения задачи для пяти работников
Выводы
Общая стоимость всех видов работ составляет 80 усл. ден. ед., т.е. новая работа более выгодная по сравнению с первой (см. рис. 4 14).
4.2. Решение задачи о назначении с помощью венгерского метода
КРАТКАЯ СПРАВКА
Венгерский метод
1 этап. Получение нулей в каждой строке
В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки
2 этап. Получение нулей в каждом столбце
В преобразованной матрице в каждом столбце определяют минимальный элемент и вычитают его из всех элементов данного столбца.
3 этап. Поиск оптимального решения
Найти строку, содержащую наименьшее число нулей.
Отмечаем один из нулей, например подчеркиванием или обведением.

65
Зачеркиваем оставшиеся нули этой строки и столбца, в котором находится
отмеченный нуль. (Так как одной работе должен соответствовать один
человек). Аналогичная операция проводится для всех строк, пока это возможно.
Если число отмеченных нулей совпадает с количеством строк, т.е. в каждой строке есть отмеченный нуль, то получено оптимальное решение.
В противном случае переход к этапу 4.
4 этап. (Если оптимальное решение не получено)
1. Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в матрице.
2. Найти наименьший из элементов, через которые не проходит ни одна прямая.
3. Вычесть его из всех элементов, через которые не проходят прямые.
4. Прибавить его ко всем элементам, лежащим на пересечении прямых.
5. Элементы, через которые проходит только одна прямая, оставить неизменными.
В результате в таблице появится как минимум одно новое нулевое значение.
Вернуться к этапу 3.
5 этап. Запись результата
Записать матрицу назначений и найти значение целевой функции.
Пример 4.4. Решить пример 4.1, используя венгерский метод.
Решение
1 этап: Получение нулей в каждой строке
В каждой строке таблицы найдем наименьший элемент и вычтем его из всех элементов данной строки (рис. 4.15, 4.16).
Рис. 4.15. 1 этап венгерского метода

66
Рис. 4.16. 1 этап венгерского метода (режим Формулы / Показать
формулы)
2 этап. Получение нулей в каждом столбце
В преобразованной матрице в каждом столбце определяем минимальный элемент и вычитаем его из всех элементов данного столбца
(рис. 4.17, 4.18).
Рис. 4.17. 2 этап венгерского метода

67
Рис. 4.18. 2 этап венгерского метода (режим Формулы / Показать
формулы)
3 этап. Поиск оптимального решения
Выберем строку, содержащую наименьшее число нулей (например, строка 38).
Отмечаем один из нулей обведением (например, ячейка E38).
Зачеркиваем оставшиеся нули этой строки и столбца, в котором находится отмеченный нуль. (Так как одной работе должен соответствовать один человек). Аналогичная операция проводится для всех строк, пока это возможно (рис. 4.19):

выбираем ноль в ячейке D39, зачеркиваем ноль в ячейке D40;

выбираем ноль в ячейке F37, зачеркиваем ноль в ячейке C37.
Рис. 4.19. 3 этап венгерского метода
Число отмеченных нулей не совпадает с количеством строк, т.е. оптимальное решение не получено.

68
4 этап. (Если оптимальное решение не получено)
Проведем минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в матрице (на рис. 4.20 отмечены серым цветом).
Рис. 4.20. 4 этап венгерского метода
Находим наименьший из элементов, через которые не проходит ни одна прямая: =МИН(C47:C49;F47:F49).
Вычитаем его из всех элементов, через которые не проходят прямые.
Прибавляем его ко всем элементам, лежащим на пересечении прямых.
Элементы, через которые проходит только одна прямая, оставляем неизменными.
В результате в таблице появилось новое нулевое значение: ячейка F56
(рис. 4.21).
Рис. 4.21. 4 этап венгерского метода. Появление нового нулевого решения
Возвращаемся к этапу поиска оптимального решения.

69
Выберем строку, содержащую наименьшее число нулей (например, строка 56).
Отмечаем один из нулей обведением (например, ячейка E56).
Зачеркиваем оставшиеся нули этой строки и столбца, в котором находится отмеченный нуль (ячейка F56). (Так как одной работе должен соответствовать один человек). Аналогичная операция проводится для всех строк, пока это возможно (рис. 4.22):

выбираем ноль в ячейке D57, зачеркиваем ноль в ячейке D58;

выбираем ноль в ячейке C55, зачеркиваем ноль в ячейке F55.
Рис. 4.22. Новый поиск оптимального решения
Число отмеченных нулей не совпадает с количеством строк, т.е. оптимальное решение не получено.
Проведем минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в матрице (на рисунке 4.23 отмечены серым цветом).
Рис. 4.23. Минимальное количество прямых, проведенные через все нули
Находим наименьший из элементов, через которые не проходит ни одна прямая: =МИН(C65:C66;E65:F66).
Вычитаем его из всех элементов, через которые не проходят прямые.
Прибавляем его ко всем элементам, лежащим на пересечении прямых.
Элементы, через которые проходит только одна прямая, оставляем неизменными.
В результате в таблице появилось новое нулевое значение: ячейка С75
(рис. 4.24).

70
Рис. 4.24. Появление нового нулевого решения
Выберем строку, содержащую наименьшее число нулей (например, строка 74).
Отмечаем один из нулей обведением (например, ячейка D74).
Зачеркиваем оставшиеся нули этой строки и столбца, в котором находится отмеченный нуль (ячейка D75). (Так как одной работе должен соответствовать один человек). Аналогичная операция проводится для всех строк, пока это возможно (см. рис. 4.24):

выбираем ноль в ячейке C75, зачеркиваем ноль в ячейке С72;

выбираем ноль в ячейке F72, зачеркиваем ноль в ячейке F73;

выбираем ноль в ячейке E73.
Число отмеченных нулей совпадает с количеством строк, т.е. оптимальное решение получено.
5 этап. Запись результата
Матрица назначений и найденное значение целевой функции 140 усл.
ден. ед (=F6+E7+D8+C9) представлены на рисунке 4.25.