ВВЕДЕНИЕ 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
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
Большая размерность является исключительным свойством большинства практических задач линейного программирования. Например, решение задач оптимизированного проектирования на уровне страны матрицы ограничений достигают размерности m=104, n=106. При такой размерности классические методы линейного программирования, такие как симплекс-метод, двойственный симплекс -метод и др., оказываются малоэффективными. Таким образом, это было связано с необходимостью разработки специальных методов как приближенных, так и точных, предназначенных для решения задач высокой размерности.
Большинство этих методов используют принцип декомпозиции (принцип децентрализации). Его идея состоит в том, что большая задача разбивается на ряд задач меньшего размера, нахождении независимых оптимумов для каждой из них, а затем связывают эти частные решения в общее решение исходной задачи.
Методы блочного программирования могут быть использованы для построения эффективных алгоритмов решения специальных задач линейного программирования.
Актуальность данной работы математическая модель реальных задач сводящийся к задачам линейным программирования которые характеризуются большим числом переменных.
Объектом является математическая модель задачи линейного программирования.
Предметом является математическая модель задачи линейного программирования с большим числом переменных.
Целью является разработать и реализовать алгоритм декомпозиции для задачи линейного программирования.
Для реализации цели сформируем задачи:
1. Проанализировать теоретические основы симплекс -метода
2. Исследовать сущность декомпозиции для задачи линейного программирования.
3. Реализовать декомпозицию для задачи линейного программирования.
Целью данной дипломной работы являлось разработать и реализовать алгоритм декомпозиции. Поставленные задачи были выполнены:
1. Проанализировать теоретические основы симплекс -метода
2. Исследовать сущность декомпозиции для задачи линейного программирования.
3. Реализовать декомпозицию для задачи линейного программирования.
В ходе изучения теоретических основ симплекс -метода было выявлено, что он малоэффективен в задачах большой размерности, так как увеличивается число переменных, и тем самым возникают сложности при минимизации (максимизации) целевой функции.
По этой причине была изучена сущность декомпозиции для задач линейного программирования, и как оказалось в сравнении с симплекс - методом, он неограничен в количестве переменных и разбиваясь на подзадачи упрощает ход решения.
Хоть в качестве алгоритма для решения задач больших размерностей выбран алгоритм декомпозиции, это не исключает факт непосредственного использования симплекс -метода. В численном примере было видно, что разбив задачу на блоки, каждый блок решается графическим способом, но для того чтобы еще более упростить нахождения значений, был использован симплекс-метод.
Таким образом, в завершении данной выпускной квалификационной работы был реализован алгоритм декомпозиции. Который как было выяснено в ходе работы высокоэффективен и очень удобен при решении задач больших размерностей. Одним из главных достоинств этого метода является то, что не требуются громоздкие вычисления, и не возникает трудностей решить задачу, так как благодаря разбиению задач на блоки, каждую блочную задачу очень легко решить.
Благодаря этому методу сокращается количество вычислений, а также существует выигрыш во времени, что еще более убеждает в том, что метод на самом деле является эффективным.
