Тип работы:
Предмет:
Язык работы:


Исследование алгоритма решения задачи минимизации суммарного штрафа

Работа №61288

Тип работы

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

Предмет

информатика

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

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


Введение 3
1. Цель работы 5
2. Приближенный алгоритм 6
3. Точный алгоритм 10
4. Генератор исходных данных для задачи 11
5. Экспериментальное исследование 13
6. Описание работы приложения 19
7. Выбор языка программирования 20
Заключение 21
Список литературы 22
Приложение


Сегодня мир развивается с огромной скоростью. Постоянно расширяются масштабы современного производства, усложняются и делегируются процессы, возникает необходимость в координации работы различных отраслей. Людям приходиться принимать решения, зачастую связанные с большими затратами и сложными условиями. Принимаемые решения направлены на достижение определённых целей и имеют систему ограничений. Эти цели могут быть реализованы разным способом, с различными затратами и временем. Успешное решение невозможно без повышения качества управления производственными процессами и технологическими объектами. Для этого необходимо применение научных методов моделирования и оптимизации производственно-экономических и технологических ситуаций. Немаловажную роль в достижении этой цели играет последовательность выполнения поступающих задач. Выбрать верно данную последовательность помогает теория расписаний.
Введение в теорию расписаний
Задачи теории расписаний - задачи оптимизации процесса обслуживания конечного множества требований в системе, содержащей конечное множество приборов.
Нужно обслужить на одном приборе n требований с момента времени t. Пронумеруем их:
1,...,n
Обслуживание элементов множества N:
N = { 1,...,n }
Запрещены искусственные простои прибора, прерывание в обслуживании требований и одновременное обслуживание требований. 
Для каждого требования заданы параметры V j £ N: ij - момент поступления требования j на обслуживание.
Pj > 0 - длительность обслуживания требования j.
dj - директивный срок момента времени, к которому желательно завершить. Wj - вес, приоритет, значимость требования.
GN - граф, отношения предшественников задаются ориентированным графом без контуров.

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!


В результате выполнения дипломной работы был исследован приближенный алгоритм решения задачи минимизации суммарного штрафа с применением метода решения задачи о назначениях.
В работе реализовано сведение задачи минимизации суммарного штрафа с одинаковыми продолжительностями обслуживания к задаче о назначениях, а также запрограммирован алгоритм решения задачи о назначениях. В качестве точного метода был выбран метод перебора.
Алгоритмы были реализованы на языке программирования Python в среде PyCharm 3.6.
Было сгенерировано пять тысяч примеров с различными
продолжительностями и различным количеством требований, были
получены решения этих примеров приближенным алгоритмом и проведено исследование приближенного алгоритма. В ходе этого исследования было выявлено, что приближенный алгоритм дает 100% совпадение с точным при количестве требований равным одному, но чем больше количество требований, тем менее точно работает приближенный алгоритм. При количестве требований равном 10 количество совпадений приближенного алгоритма с точным алгоритм становится равным нулю.
Реализованный алгоритм имеет простой и удобный интерфейс и может быть использован в дальнейшем для расчетов.



1. Афанасьев, М.Ю. Исследование операций в экономике: модели, задачи, решения /М.Ю. Афанасьев, Б.П. Суворов.- М.: Инфра-М, 2003.- 444с.
2. Лутц, М. Learning Python / М. Лутц.- М: Символ-Плюс, 2011.- 1280 с.
3. Теория расписаний. Задачи и алгоритмы [Текст]: учеб. пособие для студ. вузов/А.А. Лазарев, Е.Р. Гафаров; под ред. академика РАН С.Н. Васильева. -М.: Москва, 2011.- 222с.
4. Основы Python — кратко. Часть 6. Расширенное определение функций [Электронный ресурс]. - Режим доступа: https://habrahabr.ru/post/50381/. Дата обращения: 20.05.17.
5. Python-3. Почему программисты используют Python [Электронный ресурс]. - Режим доступа: http://python-3.ru/page/pochemu-programmisty- ispolzujut-python#comment-499. Дата обращения: 01.06.17.
6. Ranum, D.L. Problem Solving with Algorithms and Data Structures Using Python / D.L. Ranum, B.N. Miller.- М.: Franklin, Beedle & Associates Inc, 2011.438 с.


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



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


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