Помощь студентам в учебе
Масштабируемый алгоритм решения задачи линейного программирования с изменяющимися исходными данными
|
ОГЛАВЛЕНИЕ 6
ВВЕДЕНИЕ 8
1 ОБЗОР ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ 10
Выводы по разделу один 10
2 ТЕОРИЯ НАХОЖДЕНИЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ
НЕРАВЕНСТВ 11
Выводы по разделу два 16
3 ПОНЯТИЕ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ 17
Выводы по разделу три 18
4 ОСНОВЫ ТЕОРИИ ЛИНЕЙНОЕО ПРОЕРАММИРОВАНИЯ 19
Выводы по разделу четыре 25
5 АЛЕОРИТМ NON-STATIONARY LINEAR PROGRAMMING 26
5Л Фаза Quest 27
5.2 Фаза Targeting 31
Выводы по разделу пять 38
6 РЕАЛИЗАЦИЯ АЛЕОРИТМА NON-STATIONARY LINEAR
PROGRAMMING 39
Выводы по разделу шесть 44
7 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ 45
7.1 Исследование стационарного варианта фазы Quest 45
7.2 Исследование нестационарного варианта фазы Quest 49
7.3 Исследование стационарного варианта алгоритма NSLP 53
7.4 Исследование нестационарного варианта алгоритма NSLP 56
7.4.1 Исследование зависимости сходимости от количества ячеек
следящей области по одному измерению 56
7.4.2 Исследование зависимости сходимости от модуля вектора
параллельного переноса многогранника 58
7.4.3 Исследование по поиску значения масштабирующего коэффициента
следящей области 59
7.4.4 Исследование зависимости сходимости от модуля вектора параллельного переноса многогранника (со скорректированным масштабом изменения координат) 60
Выводы по разделу семь 63
ЗАКЛЮЧЕНИЕ 64
БИБЛИОЕРАФИЧЕСКИЙ СПИСОК 66
ПРИЛОЖЕНИЯ 70
Приложение 1 70
Приложение 2 74
Приложение 3 78
Приложение 4 82
Приложение 5 91
Приложение 6 93
Приложение 7 95
Приложение 8 97
Приложение 9 99
Приложение 10 101
Приложение 11 102
ВВЕДЕНИЕ 8
1 ОБЗОР ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ 10
Выводы по разделу один 10
2 ТЕОРИЯ НАХОЖДЕНИЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ
НЕРАВЕНСТВ 11
Выводы по разделу два 16
3 ПОНЯТИЕ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ 17
Выводы по разделу три 18
4 ОСНОВЫ ТЕОРИИ ЛИНЕЙНОЕО ПРОЕРАММИРОВАНИЯ 19
Выводы по разделу четыре 25
5 АЛЕОРИТМ NON-STATIONARY LINEAR PROGRAMMING 26
5Л Фаза Quest 27
5.2 Фаза Targeting 31
Выводы по разделу пять 38
6 РЕАЛИЗАЦИЯ АЛЕОРИТМА NON-STATIONARY LINEAR
PROGRAMMING 39
Выводы по разделу шесть 44
7 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ 45
7.1 Исследование стационарного варианта фазы Quest 45
7.2 Исследование нестационарного варианта фазы Quest 49
7.3 Исследование стационарного варианта алгоритма NSLP 53
7.4 Исследование нестационарного варианта алгоритма NSLP 56
7.4.1 Исследование зависимости сходимости от количества ячеек
следящей области по одному измерению 56
7.4.2 Исследование зависимости сходимости от модуля вектора
параллельного переноса многогранника 58
7.4.3 Исследование по поиску значения масштабирующего коэффициента
следящей области 59
7.4.4 Исследование зависимости сходимости от модуля вектора параллельного переноса многогранника (со скорректированным масштабом изменения координат) 60
Выводы по разделу семь 63
ЗАКЛЮЧЕНИЕ 64
БИБЛИОЕРАФИЧЕСКИЙ СПИСОК 66
ПРИЛОЖЕНИЯ 70
Приложение 1 70
Приложение 2 74
Приложение 3 78
Приложение 4 82
Приложение 5 91
Приложение 6 93
Приложение 7 95
Приложение 8 97
Приложение 9 99
Приложение 10 101
Приложение 11 102
Целью выпускной квалификационной работы является исследование масштабируемого алгоритма решения задачи линейного программирования с изменяющимися входными данными Non-Stationary Linear Programming (NSLP).
Для достижения поставленной задачи необходимо, прежде всего, произвести обзор литературных источников, связанных с теоретической базой алгоритма: работ по теории нахождения решений систем линейных неравенств, фейеровским методам в оптимизации, основам линейного программирования.
Также необходимо проанализировать состояние и статус проблемы путём обзора научных публикаций в области разработки методов решения нестационарных задач линейного программирования. Кроме того, необходимо выявить основные особенности таких задач и сложности, возникающие при попытке применения классических методов при их решении. Помимо прочего, в перечень подлежащих разработке вопросов входит проведение анализа основной идеи, лежащей в основе алгоритма NSLP, а также описание его основных фаз. Фаза Quest (поиск) предназначена для поиска решения системы неравенств, задающей ограничения нестационарной задачи, а фаза Targeting (позиционирование) - для формирования следящей области, позволяющей с заданной точностью определить решение.
После этого необходимо написать программу, реализующую алгоритм NSLP, протестировать её на примере модельной задачи различных размерностей (смоделировав нестационарность исходных данных) и провести ряд вычислительных экспериментов по исследованию сходимости алгоритма в зависимости от параметров алгоритма и интенсивности изменения исходных данных.
Таким образом, предметом исследования является предлагающийся в качестве алгоритма решения нестационарных задач алгоритм NSLP. В силу того, что классические методы решения задач линейного программирования при нестационарном характере входных данных не дают оптимального решения, имеет место необходимость разработки и реализации альтернативных алгоритмов. Следовательно, исследование рассматриваемого в выпускной квалификационной работе алгоритма NSLP является актуальным направлением научной деятельности.
В качестве метода исследования используется метод решения нестационарных задач линейного программирования, основанный на применении фейеровских отображений.
Для достижения поставленной задачи необходимо, прежде всего, произвести обзор литературных источников, связанных с теоретической базой алгоритма: работ по теории нахождения решений систем линейных неравенств, фейеровским методам в оптимизации, основам линейного программирования.
Также необходимо проанализировать состояние и статус проблемы путём обзора научных публикаций в области разработки методов решения нестационарных задач линейного программирования. Кроме того, необходимо выявить основные особенности таких задач и сложности, возникающие при попытке применения классических методов при их решении. Помимо прочего, в перечень подлежащих разработке вопросов входит проведение анализа основной идеи, лежащей в основе алгоритма NSLP, а также описание его основных фаз. Фаза Quest (поиск) предназначена для поиска решения системы неравенств, задающей ограничения нестационарной задачи, а фаза Targeting (позиционирование) - для формирования следящей области, позволяющей с заданной точностью определить решение.
После этого необходимо написать программу, реализующую алгоритм NSLP, протестировать её на примере модельной задачи различных размерностей (смоделировав нестационарность исходных данных) и провести ряд вычислительных экспериментов по исследованию сходимости алгоритма в зависимости от параметров алгоритма и интенсивности изменения исходных данных.
Таким образом, предметом исследования является предлагающийся в качестве алгоритма решения нестационарных задач алгоритм NSLP. В силу того, что классические методы решения задач линейного программирования при нестационарном характере входных данных не дают оптимального решения, имеет место необходимость разработки и реализации альтернативных алгоритмов. Следовательно, исследование рассматриваемого в выпускной квалификационной работе алгоритма NSLP является актуальным направлением научной деятельности.
В качестве метода исследования используется метод решения нестационарных задач линейного программирования, основанный на применении фейеровских отображений.
В рамках выполнения выпускной квалификационной работы был исследован масштабируемый алгоритм решения задачи линейного программирования с изменяющимися исходными данными Non-Stationary Linear Programming (NSLP).
В основе исследования лежит осуществлённый в рамках работы анализ предметной области. Он подразумевает под собой, прежде всего, обзор теоретической базы предложенного алгоритма Non-Stationary Linear Programming, включающей в себя: теорию нахождения решения систем линейных неравенств (второй раздел), теорию фейеровских методов оптимизации (третий раздел) и основ линейного программирования (четвёртый раздел).
Был произведён анализ последних достижений в разработке методов решения нестационарных задач линейного программирования посредством обзора научных публикаций в данной области. После выявления практической ценности разработки алгоритма NSLP, было произведено подробное описание работы его основных фаз (Quest и Targeting) и особенностей его применения (пятый раздел).
После анализа литературных источников и теоретической базы алгоритм NSLP был реализован в виде программы на языке Python. Вкратце описаны архитектура разработанной программы, особенности и инструменты реализации и ограничения её применения (шестой раздел).
Затем с программно реализованным алгоритмом был проведён ряд вычислительных экспериментов, в которых исследовалось влияние различных параметров алгоритма на его работу (седьмой раздел). Из наиболее значимых результатов исследований алгоритма можно выделить следующие:
1) Наиболее быстрая сходимость фейеровского процесса на фазе Quest достигается при относительно больших значениях значении коэффициента релаксации (в наших исследованиях таким значением было Я = 10);
2) Наиболее быстрая сходимость алгоритма NSLP (в сущности, фазы Targeting) достигается при относительно небольшом количестве ячеек следящей области (в наших исследованиях таким значением было К = 11 (число ячеек по одному измерению) при начальной длине ребра ячейки s = 0.01). Такой вывод справедлив как для стационарных, так и для нестационарных задач; замечено при этом, что при сравнении отработки алгоритма при решении нестационарной и стационарных задач при одном и том же значении К, соответствующая нестационарная задачи сходится существенно быстрее;
3) Величина модуля вектора d, на который происходит параллельный перенос многогранника М, не оказывает существенного влияния на скорость сходимости ни фазы Quest, ни всего алгоритма целиком. Однако при этом следует отметить, что при достижении определённого значения модуля dалгоритм NSLP перестаёт сходиться и «застревает» в бесконечном итерационном процессе на фазе Targeting (в наших исследованиях такая ситуация наступала при координатах вектора d, равных двести каждая и периоде изменения исходных данных, равном полутора секундам). Дополнительные исследования показали, что увеличение значения параметра w(коэффициента масштабирования следящей области в случае отсутствия пересечений её ячеек с многогранником) вплоть до 64 всё равно не обеспечивает сходимость алгоритма при больших значениях вектора d.
Направление дальнейших исследований может быть связано с расширением функциональности алгоритма: например, разработка метода, обеспечивающего нахождение решения нестационарных задач линейного программирования, нестационарность которых имеет более сложный вид, чем параллельный перенос многогранника на фиксированный вектор с постоянной частотой. Кроме того, существующая версия алгоритма реализует решение только модельных задач; соответственно, в будущих исследованиях необходимо провести работу по совершенствованию алгоритма для обеспечения решения более широкого класса задач.
В основе исследования лежит осуществлённый в рамках работы анализ предметной области. Он подразумевает под собой, прежде всего, обзор теоретической базы предложенного алгоритма Non-Stationary Linear Programming, включающей в себя: теорию нахождения решения систем линейных неравенств (второй раздел), теорию фейеровских методов оптимизации (третий раздел) и основ линейного программирования (четвёртый раздел).
Был произведён анализ последних достижений в разработке методов решения нестационарных задач линейного программирования посредством обзора научных публикаций в данной области. После выявления практической ценности разработки алгоритма NSLP, было произведено подробное описание работы его основных фаз (Quest и Targeting) и особенностей его применения (пятый раздел).
После анализа литературных источников и теоретической базы алгоритм NSLP был реализован в виде программы на языке Python. Вкратце описаны архитектура разработанной программы, особенности и инструменты реализации и ограничения её применения (шестой раздел).
Затем с программно реализованным алгоритмом был проведён ряд вычислительных экспериментов, в которых исследовалось влияние различных параметров алгоритма на его работу (седьмой раздел). Из наиболее значимых результатов исследований алгоритма можно выделить следующие:
1) Наиболее быстрая сходимость фейеровского процесса на фазе Quest достигается при относительно больших значениях значении коэффициента релаксации (в наших исследованиях таким значением было Я = 10);
2) Наиболее быстрая сходимость алгоритма NSLP (в сущности, фазы Targeting) достигается при относительно небольшом количестве ячеек следящей области (в наших исследованиях таким значением было К = 11 (число ячеек по одному измерению) при начальной длине ребра ячейки s = 0.01). Такой вывод справедлив как для стационарных, так и для нестационарных задач; замечено при этом, что при сравнении отработки алгоритма при решении нестационарной и стационарных задач при одном и том же значении К, соответствующая нестационарная задачи сходится существенно быстрее;
3) Величина модуля вектора d, на который происходит параллельный перенос многогранника М, не оказывает существенного влияния на скорость сходимости ни фазы Quest, ни всего алгоритма целиком. Однако при этом следует отметить, что при достижении определённого значения модуля dалгоритм NSLP перестаёт сходиться и «застревает» в бесконечном итерационном процессе на фазе Targeting (в наших исследованиях такая ситуация наступала при координатах вектора d, равных двести каждая и периоде изменения исходных данных, равном полутора секундам). Дополнительные исследования показали, что увеличение значения параметра w(коэффициента масштабирования следящей области в случае отсутствия пересечений её ячеек с многогранником) вплоть до 64 всё равно не обеспечивает сходимость алгоритма при больших значениях вектора d.
Направление дальнейших исследований может быть связано с расширением функциональности алгоритма: например, разработка метода, обеспечивающего нахождение решения нестационарных задач линейного программирования, нестационарность которых имеет более сложный вид, чем параллельный перенос многогранника на фиксированный вектор с постоянной частотой. Кроме того, существующая версия алгоритма реализует решение только модельных задач; соответственно, в будущих исследованиях необходимо провести работу по совершенствованию алгоритма для обеспечения решения более широкого класса задач.