🔍 Поиск готовых работ

🔍 Поиск работ

Сравнение алгоритмов решения задачи о назначениях

Работа №44001

Тип работы

Бакалаврская работа

Предмет

информатика

Объем работы40
Год сдачи2018
Стоимость4750 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
216
Не подходит работа?

Узнай цену на написание


Введение 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
Результаты, получаемые с помощью вышеописанных методов являются
оптимальными. Разработанная программа может применяться для матриц как с
маленькими, так и с большими размерностями.


Заботин И.Я.,Фазылов В.Р.,Шульгина О.Н., Алгоритмы решения
оптимизационных задач на графах// Учебное пособие, Казань: Казанский
государственный университет, 2006.
2. Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. - М.: Мир, 1966.
3. Вагнер Г. Приложение 1.2 Решение задачи о назначениях // Основы
исследования операций. Пер. с англ. — М.: Издательство «Мир», 1972. —
Т. 1.
4. Краснов М.,Киселев А.,Макаренко Г.,Шикин Е., Заляпин В.,Эвнин А.,Том 7
Вся высшая математика — М.: Издательство «КомКнига», 2006.
5. Акоф Р., Сасиени М.,. Глава 5 Распределительные задачи: назначение и
размещение ресурсов //Основы исследования операций. — М.: Издательство
«Мир», 1971.
6. Хемди А. Таха. гл 5.4 Задача о назначениях. // Введение в исследование
операций. 7-е издание. Пер. с англ. — М.: Издательский дом «Вильямс»,
2005.
7. Стивен Прата Язык программирования С++.Лекции и упражнения 6-е
издание.Пер.с англ. — М.: Издательский дом «Вильямс», 2017.
8. Bjarne Stroustrup Programming: Principles and Practice Using C++ 2nd edition,
Addison-Wesley Professional, May 2014.
9. Афанасьев М.Ю.,Суворов Б.П. Исследование операций в экономике: модели,
задачи, решения — М.: ИНФРА-М, 2003.
II. Интернет-ресурсы:
1. http://cppstudio.com/cat/274/ - учебник «Язык программирования С++»
2. https://code-live.ru/tag/cpp-manual/ - учебник «С++ с нуля»
3. ru.stackoverflow.com– форум вопросов и ответов для программистов

Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ
.