📄Работа №44001
Тема: Сравнение алгоритмов решения задачи о назначениях
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
40 листов
Год:
2018
Просмотров:
227
4750
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
1. Цель работы 6
2. Постановка задачи 7
3. Методы решения 9
4. Описание работы проекта 16
5. Листинг 21
6 Эксперименты 29
Заключение 33
Литература 35
Приложение
1. Цель работы 6
2. Постановка задачи 7
3. Методы решения 9
4. Описание работы проекта 16
5. Листинг 21
6 Эксперименты 29
Заключение 33
Литература 35
Приложение
📖 Введение
Одной из известных задач комбинаторной оптимизации является задача о
назначениях - задача оптимального назначения работ исполнителям. Очень
часто в управлении производством приходится назначать исполнителей на
различные виды работ, что по сути и есть решение задачи о назначениях.
Примеров может быть очень много: распределение экипажей самолетов по
авиалиниям, машин такси по клиентам, назначение кандидатов на вакантные
должности и так далее.
Решение данной задачи интересовало людей всегда, что делает ее актуальной
во все времена. Если раньше матери в многодетных семьях вынуждены были
делить работу между своими детьми, то сегодня тем же самым занимается
руководство крупных и мелких предприятий, но только уже между своими
работниками. Важным условием является оптимальное распределение работы
между работниками, так как это помогает сэкономить время, нервы и другие
важные ресурсы.
Если формулировать задачу в наиболее общей форме, то это можно сделать
следующим образом:
Есть некоторое число работ и некоторое количество исполнителей этих работ.
Любой исполнитель может быть назначен на выполнение любой, но только
одной работы с неодинаковыми затратами. Необходимо распределить работы
так, чтобы они были выполнены с минимальными затратами.
Если число исполнителей и работ одинаково, то задача называется линейной
задачей о назначениях. Линейная задача о назначениях – это то же самое, что и
задача о назначениях без дополнительных условий.4
В случае единичных весов возникает задача о наибольшем паросочетании в
двудольном графе, что значит «назначить как можно больше задач».
Пример. Пусть логистическая компания использует двадцать машин, четыре из
которых свободны на данный момент (исполнители), и есть четыре клиента,
которым необходимо перевезти одинаковое количество плодородного грунта на
дачный участок в ближайшее время (работы). Логистическая компания
заботится о времени доставки машины к клиенту, поэтому для каждой машины
стоимость определяется временем, с какой машина доедет до места ожидания,
определѐнного клиентом. Итак, решение данной задачи о назначениях
заключается в том, чтобы распределить машины по клиентам так, что
суммарная стоимость (суммарное время ожидания) была бы минимальной.
назначениях - задача оптимального назначения работ исполнителям. Очень
часто в управлении производством приходится назначать исполнителей на
различные виды работ, что по сути и есть решение задачи о назначениях.
Примеров может быть очень много: распределение экипажей самолетов по
авиалиниям, машин такси по клиентам, назначение кандидатов на вакантные
должности и так далее.
Решение данной задачи интересовало людей всегда, что делает ее актуальной
во все времена. Если раньше матери в многодетных семьях вынуждены были
делить работу между своими детьми, то сегодня тем же самым занимается
руководство крупных и мелких предприятий, но только уже между своими
работниками. Важным условием является оптимальное распределение работы
между работниками, так как это помогает сэкономить время, нервы и другие
важные ресурсы.
Если формулировать задачу в наиболее общей форме, то это можно сделать
следующим образом:
Есть некоторое число работ и некоторое количество исполнителей этих работ.
Любой исполнитель может быть назначен на выполнение любой, но только
одной работы с неодинаковыми затратами. Необходимо распределить работы
так, чтобы они были выполнены с минимальными затратами.
Если число исполнителей и работ одинаково, то задача называется линейной
задачей о назначениях. Линейная задача о назначениях – это то же самое, что и
задача о назначениях без дополнительных условий.4
В случае единичных весов возникает задача о наибольшем паросочетании в
двудольном графе, что значит «назначить как можно больше задач».
Пример. Пусть логистическая компания использует двадцать машин, четыре из
которых свободны на данный момент (исполнители), и есть четыре клиента,
которым необходимо перевезти одинаковое количество плодородного грунта на
дачный участок в ближайшее время (работы). Логистическая компания
заботится о времени доставки машины к клиенту, поэтому для каждой машины
стоимость определяется временем, с какой машина доедет до места ожидания,
определѐнного клиентом. Итак, решение данной задачи о назначениях
заключается в том, чтобы распределить машины по клиентам так, что
суммарная стоимость (суммарное время ожидания) была бы минимальной.
✅ Заключение
При написании работы были запрограммированы два алгоритма решения
задачи о назначениях: с использованием метода расстановки пометок (МРП)
для решения задачи построения максимального потока минимальной
стоимости и Венгерский алгоритм.
Каждый алгоритм запрограммирован так, чтобы его возможно было
вызывать многократно, например, в виде функции. Также в интерфейсе
предусмотрена возможность решения как одного примера, используя ввод
данных с экрана, так и возможность решения большого количества примеров
любой заданной размерности, используя генерацию исходных данных с
записью результатов работы алгоритмов в текстовый файл.
Алгоритмы сравнивались по трудоемкости реализации для различных
размерностей. Для каждой группы экспериментов тестировалось по 100
примеров, по результатам которых были сделаны выводы.
Для каждой группы экспериментов вычислялись минимальные и максимальные
значения констант. Далее по значению констант формировались интервалы и
подсчитывалось, сколько примеров попадают в тот или иной интервал. Это
помогло мне сделать вывод о том, какой алгоритм лучше использовать при
конкретной размерности. Например, при размерностях матриц 10*10, 25*25,
30*30, 45*45 предпочтительнее использовать потоковый алгоритм с
использованием МРП.
Если рассматривать матрицы больших размерностей, к примеру, 100*100,
200*200, 300*300, 1000*1000, то Венгерский алгоритм отрабатывает намного
быстрее, чем потоковый с использованием МРП, и его трудоемкость
составляет O(n2), потоковый же алгоритм сохраняет свою трудоемкость,
равную O(n3).34
Результаты, получаемые с помощью вышеописанных методов являются
оптимальными. Разработанная программа может применяться для матриц как с
маленькими, так и с большими размерностями.
задачи о назначениях: с использованием метода расстановки пометок (МРП)
для решения задачи построения максимального потока минимальной
стоимости и Венгерский алгоритм.
Каждый алгоритм запрограммирован так, чтобы его возможно было
вызывать многократно, например, в виде функции. Также в интерфейсе
предусмотрена возможность решения как одного примера, используя ввод
данных с экрана, так и возможность решения большого количества примеров
любой заданной размерности, используя генерацию исходных данных с
записью результатов работы алгоритмов в текстовый файл.
Алгоритмы сравнивались по трудоемкости реализации для различных
размерностей. Для каждой группы экспериментов тестировалось по 100
примеров, по результатам которых были сделаны выводы.
Для каждой группы экспериментов вычислялись минимальные и максимальные
значения констант. Далее по значению констант формировались интервалы и
подсчитывалось, сколько примеров попадают в тот или иной интервал. Это
помогло мне сделать вывод о том, какой алгоритм лучше использовать при
конкретной размерности. Например, при размерностях матриц 10*10, 25*25,
30*30, 45*45 предпочтительнее использовать потоковый алгоритм с
использованием МРП.
Если рассматривать матрицы больших размерностей, к примеру, 100*100,
200*200, 300*300, 1000*1000, то Венгерский алгоритм отрабатывает намного
быстрее, чем потоковый с использованием МРП, и его трудоемкость
составляет O(n2), потоковый же алгоритм сохраняет свою трудоемкость,
равную O(n3).34
Результаты, получаемые с помощью вышеописанных методов являются
оптимальными. Разработанная программа может применяться для матриц как с
маленькими, так и с большими размерностями.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.