ВВЕДЕНИЕ 2
1. ИЗВЕСТНЫЕ МЕТОДЫ ОТСЕЧЕНИЙ 4
2. ИССЛЕДУЕМЫЙ МЕТОД ОТСЕЧЕНИЙ С ОБНОВЛЕНИЕМ
АППРОКСИМИРУЮЩИХ МНОЖЕСТВ 6
3. ПОСТАНОВКА ЗАДАЧИ И АЛГОРИТМ ЕЕ РЕШЕНИЯ 7
3.1. Постановка задачи 7
3.2. Метод отсечений 7
4. РАБОТА С ПРОГРАММОЙ 9
4.1. Описание работы с программой 10
4.2. Подтверждение работоспособности программы на тестовых примерах. . 12
4.3. Результаты численных экспериментов 15
5. РЕШЕНИЕ ИССЛЕДУЕМЫМ МЕТОДОМ ОПТИМИЗАЦИОННОЙ
ЭКОНОМИЧЕСКОЙ ЗАДАЧИ 26
6. ЗАКЛЮЧЕНИЕ 33
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА 34
ПРИЛОЖЕНИЕ
Дипломная работа посвящена численному исследованию одного из методов выпуклого программирования. Методы решения задач математического программирования востребованы и довольно часто используются на практике. Поэтому создание новых и численное исследование старых остается актуальным и в наше время.
Один из известных классов методов решения задач математического программирования образуют так называемые методы отсечений (см. например, [1-9]).
Класс методов отсечений достаточно широк. Условно можно разделить их на три группы. В методах первой группы при построении приближений используется аппроксимация области ограничений исходной задачи. Методы такого типа удобны в том случае, когда целевая функция является линейной или выпуклой квадратичной.
В методах второй группы аппроксимируется надграфик функции цели многогранными множествами. Такие методы удобны, соответственно, тогда, когда линейными функциями задана допустимая область.
Самая малочисленная - третья группа, которую образуют те, в которых используется аппроксимация как надграфика, так и области ограничений. В методах такого типа для построения приближений решаются вспомогательные задачи линейного программирования, несмотря на то, что нелинейны и целевая функция, и функции, задающие ограничения.
Дипломная работа посвящена численному исследованию одного из методов третьей группы [9].Данный метод включает аппроксимацию и области ограничений, и надграфика целевой функции. Отсечения итерационных точек осуществляется плоскостями, которые строятся в методе с помощью субградиентов функций цели и ограничений. Каждая такая итерационная точка отыскивается путем решения задачи линейного программирования. Во время решения задачи происходит накопление отсекающих плоскостей, что делает задачу трудоемкой, необходимо достаточно большое количество времени для ее решения. Поэтому в данном методе, в отличие от большинства известных методов отсечений, реализована процедура обновления аппроксимирующих множеств.
Для исследования упомянутого метода отсечений в дипломной работе программно реализован данный метод на языках С++, С#. С помощью этой программы проведена серия экспериментов с использованием тестовых примеров различной размерности. На основе экспериментов сделаны выводы по выбору некоторых параметров метода, а также по способам обновления аппроксимирующих множеств. Проверена работоспособность исследуемого метода на оптимизационной экономической задаче.
Были сделаны следующие выводы:
1. Были изучены известные методы отсечений.
2. Был изучен новый метод отсечений с аппроксимацией области ограничений и надграфика целевой функции, допускающий периодические обновления аппроксимирующих множеств за счет отбрасывания секущих плоскостей.
3. Данный метод был программно реализован на языках C++, С#.
4. Было протестировано некоторое количество примеров различных размерностей, результаты были занесены в Таблицы («Таблица 1», «Таблица 2»).
5. На основе проведенных экспериментов можно дать следующие
рекомендации:
5.1. Не рекомендуется использовать полное обновление
аппроксимирующих множеств.
5.2. При обновлении аппроксимирующих множеств рекомендуется оставлять только «активные» плоскости.
5.3. Рекомендуется применять описанный в работе адаптивный способ изменения параметров sk и akj влияющих на моменты обновления аппроксимирующих множеств.
5.4. Чем выше скорость убывания значений параметров sk и ak, тем эффективнее метод.
6. Работоспособность исследуемого метода подтверждена решением одной прикладной оптимизационной задачи.
