« реализация многомерных задач оптимизации в excel»

Лазаренко Виктория Сергеевна студент 4 курса, Ставропольский государственный педагогический институт, РФ, г. Ставрополь Кузина Наталья николаевна научный руководитель, Старший преподаватель кафедры математики и информатики, Ставропольский государственный педагогический институт, РФ, г. Ставрополь

« РЕАЛИЗАЦИЯ МНОГОМЕРНЫХ ЗАДАЧ ОПТИМИЗАЦИИ В excel» Аннотация: В статье рассмотрены основные методы многомерной оптимизации, ПРИВЕДЁН ПРИМЕР РЕАЛИЗАЦИИ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ (МЕТОДА ПОКООРДИНАТНОГО СПУСКА) В среде Excel. КЛЮЧЕВЫЕ СЛОВА: многомерная оптимизация, условная оптимизация, БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.

Введение

Изучение задач многомерной оптимизации заключается в нахождении точек минимума функции почти всех переменных на всем промежутке  определенной размерности. 

Такая задача сложнее задачи минимизации функции одной переменной, в связи с тем, что с увеличением размерности места переменных, растёт размер вычислений и возникает трудность в построении алгоритмов, тем самым возникают трудности в изучении поведения мотивированной функции.

В данной статье мы рассмотрим численные методы оптимизации, т.е. способы построения алгоритмов нахождения оптимального (минимального или максимального) познания некой функции и для наглядности реализуем пример многомерной оптимизации в Excel. Ведь Excel – это одна из наиболее узнаваемых и известных программ, возможности которой разрешают стремительно отыскивать действенное решение, начиная с математических задач и заканчивая применением оптимизации в самых различных сферах работе человека.

Численные методы многомерной оптимизации

Существуют разные методы безусловной и условной оптимизации. К безусловной оптимизации относятся методы: покоординатного спуска, метод наискорейшего спуска и подпрограмма EXCEL “Поиск решения”. Линейное программирование, метод штрафных функций и подпрограмма EXCEL “Поиск решения” – это условная оптимизация.

Суть методов безусловной оптимизации состоит в поиске минимуму функции методом неоднократных вычислений, при разных значениях характеристик х = {x_k}, где k = 0, 1, 2, .... Методы условной оптимизации применяются при наличии ограничений. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x₁, …,x_n на каждой итерации.

Рассмотрим более подробно безусловную оптимизацию, её методы и реализацию примера в Excel.

Метод покоординатного спуска (метод прямого поиска), в котором используются лишь значения целевой функции. Чтобы воспользоваться этим методом, необходимо иметь такие исходные данные, как: формулу целевой функции, имеющую вид f(X₁,X₂, ... , Xn); Е - точность нахождения значений независимых переменных, при которых функция достигает минимума; начальные приближения X₁₀,X₂₀ ... , Xn₀.

Стоит отметить, что метод покоординатного спуска сводит многомерную задачу оптимизации к многократному решению одномерных задач по каждой независящей переменной.

Приведём пример, чтобы показать наглядно сущность метода и его разрешение.

Условие задачи: число независимых переменных равняется двум. Ограничения отсутствуют. Требуется найти минимум функции

u = (X₂-X₁²)² + (1-X₁)²

из начальной точки (0,5;0,5) c точностью 0,0001. Проанализировав функцию, заметим, что она будет иметь минимум, равный нулю. Для чего и первое, и второе слагаемое тоже должны быть равны нулю. Откуда координаты точки минимума (1;1).

Решим эту задачу на EXCEL. Откроем новый рабочий лист, где столбец А -значения X₁, столбец В - значения X₂, а столбец С - значения целевой функции и, наконец, столбец D - значения погрешности D.

Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.

Опишем первую итерацию, для этого скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X₁ выполним с помощью подпрограммы EXCEL «Поиск решения». Вызовем эту подпрограмму командой меню Сервис - Поиск решения.

Теперь скопируем содержимое ячейки А4 в ячейку А5. Сделаем текущей ячейку С5. Зададим команду меню Сервис - Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5. В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате X₂.

Вычислим погрешности решения на первом шаге, для этого внесём в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5). На этом заканчивается первая итерация.

Вторая и все последующие итерации проводятся аналогично, но с учетом соответствующих адресов ячеек.

Можно построить диаграмму изменения на каждой итерации, на которой видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.

Реализация метода покоординатного спуска представлена в Excel на рисунке 1.

Рисунок 1. Метод покоординатного спуска в Excel

Заключение

Можно сказать, что сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях[1], в связи с этим растёт необходимость развития математического аппарата оптимизации. Решение задач с помощью Excel, позволяем наглядно разобраться с задачей и решить её.

Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев.

Список литературы

1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. - М.: Высш. шк., 2007.

2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. - М.: Высш. шк., 2005.

3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. - Воронеж: Изд-во ВГУ, 1997.

4