Начало: Математика для чайников. Глава 1. Что такое математическая абстракция.
Предыдущая глава: Математика для чайников. Глава 17. Численные методы
В прошлой главе мы говорили о численных методах. Тогда я вскользь упомянул, что эти методы можно применять в задачах математической оптимизации. А сегодня мы рассмотрим методы оптимизации более подробно. Для начала, давайте разберемся, а что вообще такое оптимизация? Часто некоторые деятели (всякие там «эффективные» менеджеры) занимаются имитацией бурной деятельности, а потом гордо говорят, что они что-то там «оптимизируют». Но если рассмотреть оптимизацию с точки зрения математики, то таких «деятелей» легко вывести на чистую воду. Потому что в математике есть строгое, четкое и однозначное определение оптимизации.
И так, оптимизация – это нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств. И это касается любой оптимизации. Так что если кто-то гордо говорит, что он занимается «оптимизацией», но его действия не подходят под это определение, он нагло врет.
Рассмотрим определение оптимизации на конкретном примере. Допустим, некий «эффективный менеджер» занимается оптимизацией производственных затрат. Что это значит? Это значит, что он минимизирует функцию затрат. Почему затраты – это функция? Потому что она зависит от различных факторов, которые можно выразить числами. Более того, производственные затраты можно вычислить: сложить затраты на покупку материалов, на зарплату рабочих, на электричество и другие затраты. Но, надо понимать, что зависимость является функцией только в том случае, если эта зависимость однозначная. То есть, если при одних и тех же параметрах: количество и ценах закупленных материалов, суммы косвенных затрат и так далее результат одинаков.
Но тут возникает очень интересный нюанс. Лучший способ минимизировать затраты – вообще остановить производство, всех уволить и закрыть предприятие. Тогда затраты будут нулевые, то есть, самые минимальные, что и требовалось по условиям задачи, что вряд ли устроит собственника. Как можно выйти из этой ситуации? Очень просто. Добавить в условия задачи ограничение: прибыль (или доход) не должна уменьшиться меньше, чем определенное значение. Хотя… можно вообще поставить задачу по-другому: максимизировать прибыль.
В вышеописанной задачи могут быть и другие ограничения, например, производственные мощности и емкость рынка сбыта: невозможно произвести и продать бесконечное количество продукции.
А теперь давайте подумаем, а как «эффективный менеджер» будет выполнять поставленную задачу по оптимизации. У него должны быть полномочия что-то менять, например, увеличить выпуск одного вида продукции и уменьшить выпуск другого. От его решения зависит оптимизируемая величина (целевая функция). А вот параметры, которые он волен менять и от которых зависит целевая функция называются параметры оптимизации.
А теперь разберем математическую формулировку задачи оптимизации. Как правило, она выглядит так:
Здесь f – целевая функция, x со стрелочкой - это вектор (набор из нескольких чисел). Иначе можно записать:
где n – количество параметров оптимизации. Здесь мы поставили цель минимизации целевой функции. Чаще всего именно такая цель и ставиться при оптимизации. Если надо функцию максимизировать, мы можем просто взять ее со знаком минус, иным словами:
Это то же самое, что:
Тоже касается и неравенств, чтобы заменить «меньше или равно» на «больше или равно» нам надо перед функцией в правой части поставить знак минус. Почему я обращаю на это внимание? Потому что зачастую разные алгоритмы оптимизации предполагают именно минимизацию, или именно условия «больше или равно». А реально может быть по-разному. Но, зная этот лайфхак, можно легко преобразовать формулы.
Теперь поговорим о том, как решают задачи оптимизации. Если у нас задача задана аналитически в виде формулы, и ограничения не заданы, то мы можем просто найти точки перегиба функции методом производной. Например:
Определим ее производную:
Если забыли, что такое производная, то можете заглянуть сюда:
· Математика для чайников. Глава 9. Основы матанализа | Александр Шуравин. | Яндекс Дзен (yandex.ru)
· Математика для чайников. Глава 14. Производная | Александр Шуравин. | Яндекс Дзен (yandex.ru)
Идем дальше. Решаем уравнение:
Проверим, построив график функции:
Как видим, без условий все просто. А если добавить условия? Только не говорите что тоже просто, тут есть хитрый подвох. Нельзя, например, просто так взять и исключить из рассмотрения точки перегиба, которые не удовлетворяют условиям. Давайте проверим.
Пусть у нас задача оптимизации поставлена вот так:
Наша единственная точка перегиба вылетает. И… означает ли это, что задача не имеет решения? Вовсе нет. Просто в этом случае минимум будет в точке x=1. Действительно, слева от этой точки – запретная зона, а справа функция идет вверх. У нас только одна эта точка (x=1) и остается.
Но тут мы просто догадались. Правда, в математике нет такого метода решения, как «догадались». Как мы будем действовать в общем случае? В этом случае нужно свести задачу к задаче безусловной оптимизации. Например, можно использовать метод штрафных функций. Под штрафной функцией понимают некоторое слагаемое, которое прибавляется к целевой функции:
Важно, чтобы с этим слагаемым целевая функция имела те же самые экстремумы.
В общем, идея состоит в том, что мы ограничения заменяем штрафной функцией. В данном случае мы можем применить вот такую штрафную функцию:
Ее производная определена только на участке x>1 и равна нулю. Таким образом, нам надо рассмотреть точку x=1 и корни уравнения:
При x>1
Но при заданных условиях корней нет. У нас остается только точка x=1. Докажем, что
При x>1.
Пусть:
Тогда
Вычалим f(1):
Таким образом:
Что и требовалось доказать.
Итак, мы узнали, что такое оптимизация, как задачу оптимизации сформулировать строго математически и как вывести на чистую воду «эффективных» менеджеров, занимающихся имитацией бурной деятельности, прикрываясь громким словом «оптимизация». Еще мы разобрали конкретный пример решения задачи оптимизации.
Теперь поговорим об оптимизации в более широком смысле. В самом общем случае, под оптимизацией понимается нахождение наилучшего решения. Таким образом, оптимизационные задачи приходиться решать в самых разных областях человеческой деятельности. Но все они, так или иначе, сводятся к математике. Почему? Потому что для решения любой оптимизационной задачи необходимо построить математическую модель исследуемого объекта и провести вычислительный эксперимент. Иначе никак.
Основу вычислительного эксперимента при решении оптимизационной задачи составляет триада «модель-алгоритм-программа». Иными словами, оптимизационная задача решается, главным образом, на компьютере, именно поэтому материал данной статьи очень важен для будущих айтишников.
В общем случае задача оптимизации решается в три этапа. На первом этапе строиться математическая модель исследуемого объекта, которая отражает самые важные свойства объекта (в математической форме, естественно). Второй этап – разрабатывается алгоритм для обсчета этой модели на компьютере. Таким образом, модель должна быть представлена в такой форме, чтобы было удобно применять численные методы (см. Математика для чайников. Глава 17. Численные методы | Александр Шуравин. | Дзен (dzen.ru)). Ну и третий этап – на основании разработанных алгоритмов написать компьютерную программу, которая и произведет необходимые вычисления.
Существует даже целая научная дисциплина о том, как решать оптимизационные задачи. И называется эта дисциплина теория оптимизации. Ценность теории оптимизации состоит в том, что она универсальная по отношению к различным задачам, в частности:
- в математической экономике;
- в IT-науках: оптимальное управление, робототехника, машинное обучение;
- в технике: оптимальное планирование информационных и компьютерных сетей, оптимальная структура технических систем;
- в численном анализе: аппроксимация, регрессия, решение линейных и нелинейных систем управления и т. д.
Теория оптимизация, как вы поняли, изучает задачи оптимизации и как их решать. А с чего начать изучения задач оптимизации? Разумеется, с их классификации. Почему? Если мы знаем, к какому классу отнести наша задачу, то мы можем применить к ней тот метод решения, который применяется для задач данного класса.
Задачи оптимизации классифицируются по:
- типу параметров оптимизации (непрерывные, дискретные и целочисленные);
- по размерности (одномерные и многомерные, иногда отдельно выделают двумерные). Под мерностью понимают количество неизвестных, например, если неизвестное одно, чаще всего оно обозначается как x – то это одномерная задача, если неизвестных две (например, x и y), то двумерная, если это многомерная задача. В многомерной задаче неизвестные принято обозначать x1,x2,…xn;
- по наличию ограничений (безусловная оптимизация, где ограничений нет и условная, где они есть);
- по характеру значений задачи оптимизации подразделяются на детерминированные, где все значения строго определены и на стохастические, где есть случайные величины;
- по виду целевой функции и ограничений задачи оптимизации делятся на линейные и нелинейные.
И так, подытожим. Если нам надо что-то оптимизировать, мы строит математическую модель, формулируем задачу оптимизации, и решаем ее. Для того, чтобы решить, мы определяем, к какому классу задач относится эта задача и берет метод, предназначенный для решения именно этого класса задач. О самих методах я расскажу в будущих статьях, ибо впихнуть все это в одну статью нереально, так как там «много букв (и цифр, и формул)».
Продолжение: