Введение
Глава 1. Описание различных методов отсечений 5
1.1 Постановка задачи 5
1.2 Описание некоторых известных методов отсечений 5
1.3 Метод отсечений с аппроксимацией надграфика целевой функции без
обновления аппроксимирующих множеств 6
1.4 Метод отсечений с аппроксимацией надграфика целевой функции с
обновлением аппроксимирующих множеств 7
1.5 Сравнение методов отсечений с аппроксимацией надграфика целевой
функции 8
Глава 2. Описание работы приложения 9
2.1 Основные методы, реализованные в приложении 9
2.2 Описание работы приложения 10
2.2.1 Работа с данными, введенными пользователем вручную 11
2.2.2 Работа с данными, считанными из текстового файла 15
2.3 Окно «Справка» 19
2.4 Обработка возникающих ошибок 23
Глава 3. Численные эксперименты 28
Глава 4. Применение реализованного приложения для решения некоторых
экономических задач 31
Заключение 37
Список литературы 38
Приложение 40
Код окна «Метод отсечений» реализованного приложения 40
Код окна «Справка» реализованного приложения 66
Многие прикладные задачи ставятся в виде задач математического программирования. Существует большое количество методов решения задач математического программирования. Однако далеко не все из них удобны для практической реализации. Поэтому исследования, связанные с разработкой легко реализуемых методов решения задач математического программирования (в частности, выпуклого программирования), продолжают оставаться актуальными.
Существуют задачи выпуклого программирования, в которых целевая функция не является линейной. Для решения таких задач можно применять методы, относящиеся к классу методов отсечений [1-3]. К данным методам относится, в частности, метод отсечений с погружением в многогранные множества надграфика целевой функции. Главным недостатком данного метода отсечений является то, что на каждой итерации увеличивается количество формирующих погружающее множество отсекающих плоскостей. Таким образом, с ростом количества итераций увеличивается трудоемкость решения задач нахождения итерационных точек. Следовательно, время решения вспомогательной задачи увеличивается.
В одной из статей научного руководителя и его аспиранта был предложен вариант метода отсечений с аппроксимацией надграфика целевой функции, в котором заложена возможность периодического обновления аппроксимирующих множеств за счет отбрасывания любого количества любых отсекающих плоскостей [4, с.48-54].
Для численного исследования и сравнения данного метода с классическим было создано приложение, реализующее работу упомянутых выше методов. Была проведена серия экспериментов, в которых обоими методами были решены одни и те же задачи с одинаковой точностью и одинаковыми начальными погружающими множествами. По результатам экспериментов было выявлено, какой из методов предпочтительней при решении задач минимизации выпуклых дифференцируемых функций на множествах, заданных линейными ограничениями.
Также было проведено сравнение нескольких способов отбрасывания ограничений и найден оптимальный из них.
Цель работы. Численное исследование метода отсечений с обновлением аппроксимирующих множеств и сравнение его с классическим методом.
В выпускной работе проведено численное сравнение двух методов решения задачи выпуклого программирования, относящихся к классу методов отсечений, а именно, классического метода с аппроксимацией надграфика целевой функции и метода отсечений с обновлением аппроксимирующих множеств, предложенного ранее в статье научного руководителя и его аспиранта.
Для численного сравнения между собой названных методов составлены и отлажены программы, реализующие эти методы для задач минимизации выпуклых дифференцируемых функций на множествах, заданных линейными ограничениями.
С использованием этих программ проведена серия экспериментов на задачах различной размерности. Каждый тестовый пример решался обоими методами с одинаковой точностью и одинаковыми начальными аппроксимирующими множествами. Эксперименты показали, что практически во всех тестовых примерах заданная точность решения достигалась существенно быстрее методом отсечений с обновлением аппроксимирующих множеств.
Таким образом, получен следующий вывод: для указанных выше задач выпуклого программирования метод отсечений с обновлением аппроксимирующих множеств предпочтительнее классического метода отсечений без отбрасывания секущих плоскостей.
Кроме того, отметим, что работоспособность исследованного метода с обновлением аппроксимирующих множеств подтверждена в выпускной работе решением некоторых оптимизационных экономических задач.
