Информация о работе
Подробнее о работе
Исследование алгоритмов решения целочисленных и частично целочисленных задач линейного программирования
- 102 страниц
- 2021 год
- 3 просмотра
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Линейное программирование (ЛП) посвящено методам решения экстремальных задач. Данные задачи основаны на нахождении минимального и максимального значений функции на множествах -мерного векторного пространства.
Актуальность. Задачи целочисленного и частично целочисленного линейного программирования на сегодняшнее время применяются в различных сферах, таких как производственное планирование, телекоммуникационные сети, сотовая сеть.
Введение 4
1 Обзор существующих методов решения задачи линейного программирования 5
1.1 Общая характеристика задачи целочисленного и частично целочисленного линейного программирования 5
1.1.1 Математическая модель задачи целочисленного и частично целочисленного линейного программирования 5
1.2 Методы решения задачи целочисленного и частично целочисленного линейного программирования 6
1.2.1 Метод ветвей и границ 7
1.2.2 Метод Гомори 15
2 Реализация алгоритмов для решения целочисленных и частично- целочисленных задач линейного программирования 25
2.1 Структура реализованной программы 25
2.2 Реализация метода ветвей и границ 26
2.3 Пользовательский графический интерфейс приложения 36
3 Сравнительный анализ реализаций 42
3.1 Технические данные для сравнительного анализа 42
3.2 Метод ветвей и границ 42
3.3 Сравнение графиков однопоточной и параллельной реализации алгоритма ветвей и границ 45
3.4 Метод Гомори 47
3.5 Сравнение графиков однопоточной и параллельной реализации алгоритма Гомори 50
3.6 Сравнение параллельной реализации алгоритма ветвей и границ и алгоритма Гомори 52
4 Моделирование данных 54
4.1 Описание математической модели 54
4.2 Применение алгоритма ветвей и границ полученной модели 65
4.3 Применение алгоритма Гомори полученной модели 66
4.4 Сравнительный анализ алгоритмов 67
Заключение 69
Список используемой литературы и используемых источников 70
Приложение А Листинг программы 73
Приложение Б Листинг пользовательского интерфейса 96
Объект исследования – задачи целочисленного и частично целочисленного линейного программирования.
Предмет исследования – методы решения задач целочисленного и частично целочисленного линейного программирования.
Цель исследования – анализ методов решения задач целочисленного и частично целочисленного линейного программирования и реализация рассмотренных алгоритмов и их модификаций.
1. Богданова Е.Л. Оптимизация в проектном менеджменте: линейное программирование: учебное пособие / Е.Л. Богданова, К.А. Соловейчик, К.Г. Аркина. – СПб.: Университет ИТМО, 2017. – 165 с.
2. Метод ветвей и границ [Электронный ресурс:] – Режим доступа: http://www.math.nsc.ru/AP/benchmarks/UFLP/uflp_bb.html
3. Решение задачи целочисленного программирования графическим методом и методом Гомори [Электронный ресурс:] – Режим доступа: https://www.matburo.ru/Examples/Files/LP_Num7.pdf
4. Решение задачи целочисленного программирования методом ветвей и границ [Электронный ресурс:] – Режим доступа: https://www.matburo.ru
/Examples/Files/LP_Num5.pdf
5. Сизова С.А. Линейное программирование как область математического программирования при решении экономических задач / С.А. Сизова, В.Ю. Мурдугова, С.В. Мелешко // Старвопольский Государственный аграрный университет, статья в журнале – научная статья, №6(2), 2013, 16-20 с.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
