Метод штрафных функций excel

Обновлено: 05.07.2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод покоординатного спуска (метод прямого поиска), в котором используются только значения целевой функции. Чтобы воспользоваться этим методом, необходимо иметь следующие исходные данные:

а) формулу целевой функции f(X₁,X₂, . , Xn),

б) Е - точность нахождения значений независимых переменных, при которых функция достигает минимума,

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

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

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

из начальной точки (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.

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

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

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

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

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

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

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

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

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

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

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

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

Опишем первую итерацию, для этого скопируем содержимое ячейки В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.

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

Читайте также: