📄Работа №115183
Тема: Реализация алгоритма декомпозиции задач линейного программирования больших размерностей
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
48 листов
Год:
2018
Просмотров:
264
4265
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 5
ГЛАВА 1 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СИМПЛЕКС-МЕТОДА 7
1.1. Основные понятия симплекс-метода 7
1.2. Алгоритмическая реализация симплекс-метода 14
ГЛАВА 2. МЕТОД ДЕКОМПОЗИЦИИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 19
2.1 Теоретические основы метода декомпозиции 19
2.2. Признак оптимальности промежуточного дезагрегированного решения 22
ГЛАВА 3 РЕАЛИЗАЦИЯ АЛГОРИТМА ДЕКОМПОЗИЦИИ 24
3.1. Разработка алгоритма декомпозиции 24
3.2. Реализация алгоритма декомпозиции 25
ЗАКЛЮЧЕНИЕ 39
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
ГЛАВА 1 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СИМПЛЕКС-МЕТОДА 7
1.1. Основные понятия симплекс-метода 7
1.2. Алгоритмическая реализация симплекс-метода 14
ГЛАВА 2. МЕТОД ДЕКОМПОЗИЦИИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 19
2.1 Теоретические основы метода декомпозиции 19
2.2. Признак оптимальности промежуточного дезагрегированного решения 22
ГЛАВА 3 РЕАЛИЗАЦИЯ АЛГОРИТМА ДЕКОМПОЗИЦИИ 24
3.1. Разработка алгоритма декомпозиции 24
3.2. Реализация алгоритма декомпозиции 25
ЗАКЛЮЧЕНИЕ 39
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
📖 Введение
Большая размерность является исключительным свойством большинства практических задач линейного программирования. Например, решение задач оптимизированного проектирования на уровне страны матрицы ограничений достигают размерности m=104, n=106. При такой размерности классические методы линейного программирования, такие как симплекс-метод, двойственный симплекс -метод и др., оказываются малоэффективными. Таким образом, это было связано с необходимостью разработки специальных методов как приближенных, так и точных, предназначенных для решения задач высокой размерности.
Большинство этих методов используют принцип декомпозиции (принцип децентрализации). Его идея состоит в том, что большая задача разбивается на ряд задач меньшего размера, нахождении независимых оптимумов для каждой из них, а затем связывают эти частные решения в общее решение исходной задачи.
Методы блочного программирования могут быть использованы для построения эффективных алгоритмов решения специальных задач линейного программирования.
Актуальность данной работы математическая модель реальных задач сводящийся к задачам линейным программирования которые характеризуются большим числом переменных.
Объектом является математическая модель задачи линейного программирования.
Предметом является математическая модель задачи линейного программирования с большим числом переменных.
Целью является разработать и реализовать алгоритм декомпозиции для задачи линейного программирования.
Для реализации цели сформируем задачи:
1. Проанализировать теоретические основы симплекс -метода
2. Исследовать сущность декомпозиции для задачи линейного программирования.
3. Реализовать декомпозицию для задачи линейного программирования.
Большинство этих методов используют принцип декомпозиции (принцип децентрализации). Его идея состоит в том, что большая задача разбивается на ряд задач меньшего размера, нахождении независимых оптимумов для каждой из них, а затем связывают эти частные решения в общее решение исходной задачи.
Методы блочного программирования могут быть использованы для построения эффективных алгоритмов решения специальных задач линейного программирования.
Актуальность данной работы математическая модель реальных задач сводящийся к задачам линейным программирования которые характеризуются большим числом переменных.
Объектом является математическая модель задачи линейного программирования.
Предметом является математическая модель задачи линейного программирования с большим числом переменных.
Целью является разработать и реализовать алгоритм декомпозиции для задачи линейного программирования.
Для реализации цели сформируем задачи:
1. Проанализировать теоретические основы симплекс -метода
2. Исследовать сущность декомпозиции для задачи линейного программирования.
3. Реализовать декомпозицию для задачи линейного программирования.
✅ Заключение
Целью данной дипломной работы являлось разработать и реализовать алгоритм декомпозиции. Поставленные задачи были выполнены:
1. Проанализировать теоретические основы симплекс -метода
2. Исследовать сущность декомпозиции для задачи линейного программирования.
3. Реализовать декомпозицию для задачи линейного программирования.
В ходе изучения теоретических основ симплекс -метода было выявлено, что он малоэффективен в задачах большой размерности, так как увеличивается число переменных, и тем самым возникают сложности при минимизации (максимизации) целевой функции.
По этой причине была изучена сущность декомпозиции для задач линейного программирования, и как оказалось в сравнении с симплекс - методом, он неограничен в количестве переменных и разбиваясь на подзадачи упрощает ход решения.
Хоть в качестве алгоритма для решения задач больших размерностей выбран алгоритм декомпозиции, это не исключает факт непосредственного использования симплекс -метода. В численном примере было видно, что разбив задачу на блоки, каждый блок решается графическим способом, но для того чтобы еще более упростить нахождения значений, был использован симплекс-метод.
Таким образом, в завершении данной выпускной квалификационной работы был реализован алгоритм декомпозиции. Который как было выяснено в ходе работы высокоэффективен и очень удобен при решении задач больших размерностей. Одним из главных достоинств этого метода является то, что не требуются громоздкие вычисления, и не возникает трудностей решить задачу, так как благодаря разбиению задач на блоки, каждую блочную задачу очень легко решить.
Благодаря этому методу сокращается количество вычислений, а также существует выигрыш во времени, что еще более убеждает в том, что метод на самом деле является эффективным.
1. Проанализировать теоретические основы симплекс -метода
2. Исследовать сущность декомпозиции для задачи линейного программирования.
3. Реализовать декомпозицию для задачи линейного программирования.
В ходе изучения теоретических основ симплекс -метода было выявлено, что он малоэффективен в задачах большой размерности, так как увеличивается число переменных, и тем самым возникают сложности при минимизации (максимизации) целевой функции.
По этой причине была изучена сущность декомпозиции для задач линейного программирования, и как оказалось в сравнении с симплекс - методом, он неограничен в количестве переменных и разбиваясь на подзадачи упрощает ход решения.
Хоть в качестве алгоритма для решения задач больших размерностей выбран алгоритм декомпозиции, это не исключает факт непосредственного использования симплекс -метода. В численном примере было видно, что разбив задачу на блоки, каждый блок решается графическим способом, но для того чтобы еще более упростить нахождения значений, был использован симплекс-метод.
Таким образом, в завершении данной выпускной квалификационной работы был реализован алгоритм декомпозиции. Который как было выяснено в ходе работы высокоэффективен и очень удобен при решении задач больших размерностей. Одним из главных достоинств этого метода является то, что не требуются громоздкие вычисления, и не возникает трудностей решить задачу, так как благодаря разбиению задач на блоки, каждую блочную задачу очень легко решить.
Благодаря этому методу сокращается количество вычислений, а также существует выигрыш во времени, что еще более убеждает в том, что метод на самом деле является эффективным.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.