Введение 3
1. Цель работы 6
2. Постановка задачи 7
3. Методы решения 9
4. Описание работы проекта 16
5. Листинг 21
6 Эксперименты 29
Заключение 33
Литература 35
Приложение
Одной из известных задач комбинаторной оптимизации является задача о
назначениях - задача оптимального назначения работ исполнителям. Очень
часто в управлении производством приходится назначать исполнителей на
различные виды работ, что по сути и есть решение задачи о назначениях.
Примеров может быть очень много: распределение экипажей самолетов по
авиалиниям, машин такси по клиентам, назначение кандидатов на вакантные
должности и так далее.
Решение данной задачи интересовало людей всегда, что делает ее актуальной
во все времена. Если раньше матери в многодетных семьях вынуждены были
делить работу между своими детьми, то сегодня тем же самым занимается
руководство крупных и мелких предприятий, но только уже между своими
работниками. Важным условием является оптимальное распределение работы
между работниками, так как это помогает сэкономить время, нервы и другие
важные ресурсы.
Если формулировать задачу в наиболее общей форме, то это можно сделать
следующим образом:
Есть некоторое число работ и некоторое количество исполнителей этих работ.
Любой исполнитель может быть назначен на выполнение любой, но только
одной работы с неодинаковыми затратами. Необходимо распределить работы
так, чтобы они были выполнены с минимальными затратами.
Если число исполнителей и работ одинаково, то задача называется линейной
задачей о назначениях. Линейная задача о назначениях – это то же самое, что и
задача о назначениях без дополнительных условий.4
В случае единичных весов возникает задача о наибольшем паросочетании в
двудольном графе, что значит «назначить как можно больше задач».
Пример. Пусть логистическая компания использует двадцать машин, четыре из
которых свободны на данный момент (исполнители), и есть четыре клиента,
которым необходимо перевезти одинаковое количество плодородного грунта на
дачный участок в ближайшее время (работы). Логистическая компания
заботится о времени доставки машины к клиенту, поэтому для каждой машины
стоимость определяется временем, с какой машина доедет до места ожидания,
определѐнного клиентом. Итак, решение данной задачи о назначениях
заключается в том, чтобы распределить машины по клиентам так, что
суммарная стоимость (суммарное время ожидания) была бы минимальной.
При написании работы были запрограммированы два алгоритма решения
задачи о назначениях: с использованием метода расстановки пометок (МРП)
для решения задачи построения максимального потока минимальной
стоимости и Венгерский алгоритм.
Каждый алгоритм запрограммирован так, чтобы его возможно было
вызывать многократно, например, в виде функции. Также в интерфейсе
предусмотрена возможность решения как одного примера, используя ввод
данных с экрана, так и возможность решения большого количества примеров
любой заданной размерности, используя генерацию исходных данных с
записью результатов работы алгоритмов в текстовый файл.
Алгоритмы сравнивались по трудоемкости реализации для различных
размерностей. Для каждой группы экспериментов тестировалось по 100
примеров, по результатам которых были сделаны выводы.
Для каждой группы экспериментов вычислялись минимальные и максимальные
значения констант. Далее по значению констант формировались интервалы и
подсчитывалось, сколько примеров попадают в тот или иной интервал. Это
помогло мне сделать вывод о том, какой алгоритм лучше использовать при
конкретной размерности. Например, при размерностях матриц 10*10, 25*25,
30*30, 45*45 предпочтительнее использовать потоковый алгоритм с
использованием МРП.
Если рассматривать матрицы больших размерностей, к примеру, 100*100,
200*200, 300*300, 1000*1000, то Венгерский алгоритм отрабатывает намного
быстрее, чем потоковый с использованием МРП, и его трудоемкость
составляет O(n2), потоковый же алгоритм сохраняет свою трудоемкость,
равную O(n3).34
Результаты, получаемые с помощью вышеописанных методов являются
оптимальными. Разработанная программа может применяться для матриц как с
маленькими, так и с большими размерностями.
