Факультативное занятие по реализации многомерных задач оптимизации в Excel

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

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

Введение

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

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

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

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

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

Существуют различные методы безусловной и условной оптимизации:

• Безусловная оптимизация: Метод покоординатного спуска;

• Безусловная оптимизация: метод наискорейшего спуска;

• Безусловная оптимизация: подпрограмма EXCEL “Поиск решения”;

• Условная оптимизация: метод штрафных функций;

• Условная оптимизация: подпрограмма EXCEL “Поиск решения”;

• Условная оптимизация: линейное программирование.

Рассмотрим наиболее подробно безусловную оптимизацию, её методы и реализацию примера в 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. На этом заканчивается подготовительный этап.

Опишем первую итерацию пошагово:

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

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

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

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

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

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

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

Заключение

Сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях техники [1]. К навыкам математического обоснования принятия решений относятся навыки математического моделирования оптимизационных задач, выбора адекватного математического обеспечения (метода, алгоритма, программной системы) с необходимым обоснованием.

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

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

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

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

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

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

5