Математические методы, которые использует Поиск решения (Solver) в Excel
Solver - важная надстройка в Excel, которая помогает решать экономические задачи продвинутого уровня (ранее такая функциональность была доступна только в специализированных компьютерных программах). Данный инструмент использует достижения такого раздела математики, как методы оптимизации (mathematical optimization), или по-другому, математическое программирование (Mathematical Programming, к обычному программированию компьютерных программ эта наука не имеет прямого отношения).
В экономике, как на уровне фирмы, так и на уровне государства, часто возникала проблема оптимального распределения ресурсов. Например, необходимо максимизировать прибыль, управляя ассортиментом выпускаемых изделий, при этом определенные ресурсы (количество имеющегося оборудования, сотрудников необходимой квалификации) зафиксированы. Или, к примеру, распределить доступный бюджет между различными видами рекламы, чтобы добиться максимального контакта с аудиторией. В математическую экономику такая задача вошла под названием задачи о размещении (распределении ресурсов) - также широко известно название Wyndor Glass Company problem.
Особенно ярко это проблема стояла перед социалистическими экономиками, где имелась возможность централизованно регулировать распределение ресурсов между отраслями. Поэтому неудивительно, что методы математического программирования были разработаны советским математиком Леонидом Канторовичем, который позднее получил за это Нобелевскую премию мира по экономике. И хотя в Советском Союзе они не помогли справиться с дефицитом и другими традиционными проблемами плановых экономик, на более низком уровне планирования разработанный математический аппарат оказался востребованным.
Основная задача математического программирования в общем виде
Основная задача математического программирования - максимизировать (или минимизировать) целевую функцию при условии выполнения определенных ограничений.
F(X1,X2,...,XN) -> max
при условии
f1(X1,X2,...,XN)
f1(X1,X2,...,XN)
...,
fM(X1,X2,...,XN)
Иными словами, нам необходимо подобрать X1,X2,...,XN таким образом, чтобы целевая функция F достигла своего максимального значения при условии выполнения всех ограничений. Размерность задачи определяется количеством варьируемых переменных Х, а не количеством ограничений. В одномерном виде - это по существу широко известная из курса математического анализа задача максимизации (минимизации) функции на определенном интервале:
Математическое программирование в одномерном пространстве
В данном примере необходимо найти такое значение функции, при котором она принимает наименьшее значение. Переменная только одна - Х (по горизонтальной оси), а в роли ограничений выступают условия X>0 и X<8. Далее рассмотрим аналогичную двумерную задачу.
Математическое программирование в двумерном пространстве
На данном примере рассмотрена задача из области так называемого линейного программирования - важнейшего раздела математического программирования. Этот раздел работает с функциями, которые имеют линейный характер (такими, как Х2=kX1+b). Графически линейные функции описываются прямыми линиями (в двумерном пространстве), плоскостью (в трехмерном пространстве) и гиперплоскостью (в N-мерном пространстве). Линейными в этом случае должны быть как целевая функция, так и все функции ограничений.
На графике три ограничения (описаны сиреневыми линиями) совместно с требованиями на неотрицательность изменяемых переменных образуют многоугольник (светло-розового цвета) - область возможных решений (feasible solution). Целевая функция (желтого цвета) - описывается множеством линий (которые расположены параллельно по отношению к друг другу), чем выше и правее находится линия, тем большему значению целевой функции она соответствует. По существу, задача линейного программирования - найти наивысшее значение целевой функции, которое удовлетворяет множеству доступных решений. В данном примере максимум достигается в точке (5,5) и соответствует значению целевой функции, равному 15.
Данную двумерную задачу оптимизации графически можно описать и в трехмерном пространстве (тогда не придется двигать целевую функцию), это вопрос только удобства представления. Графически это будет выглядеть аналогично тому, как выше представлен одномерный случай (на графике отображена двумерная нелинейная целевая функция, линейная была бы в виде плоскости):
Математическое программирование в двумерном пространстве
То есть, вместо отрезка множество доступных множеств будет выглядеть как многогранник (на графике представлен вырожденный случай - квадрат), а целевая функция станет трехмерной (где по оси аппликат будет отложено целевое значение функции, а по осям абсцисс и ординат - возможные значения изменяемых (оптимизируемых) переменных.
Настройка Поиска решения в Excel
Обратим внимание, что по умолчанию Поиск решения (Solver) не входит в базовую версию Excel. Это надстройка, которую необходимо включить, после этого она появится в разделе Данные (Data). Solver также не стоит путать с функцией Goal seak. Solver позволяет найти максимальное или минимальное решение (оптимизация), в то время как Goal Seek помогает найти такую переменную, при которой функция принимает конкретное значение (не обязательно оптимальное решение). Goal Seek позволяет изменять только одну переменную, в то время как Solver позволяет изменять сразу несколько переменных. Упрощая, Goal Seak лучше использовать, когда Вам необходимо решить какое-то уравнение, в то время как Solver в основном заточен на решение оптимизационных задач (поиска максимума и минимума), хотя решить уравнение с его помощью также можно.
Отметим также, что Goal Seak в некоторых случаях также можно использовать для оптимизации. В этом случае нужно быть уверенным, что оптимальное значение находится именно в том месте, где целевую функцию пересекает ограничительное условие. Чаще всего это бывает в тех случаях, где есть уверенность в постоянном непрерывном возрастании (или убывании) целевой функции на всем множестве ее значений. Обычно это условие выполнено для линейных и некоторых других функций. В этом случае Goal Seak по существу ищет точку пересечения ограничения и целевой функции. Если функция имеет локальные максимумы и минимумы, то в этом нельзя быть уверенным. В любом случае, обычно проще всего все же использовать Solver.
При работе с Solver необходимо соблюдать определенные правила оформления. Как правила, целевые функция, изменяемые переменные и ограничения необходимо отобразить на одном листе Excel. Даже если сам расчет идет на другом листе, на том листе, где планируется запускать Solver, необходимо сослаться на этот расчет. Изменяемые переменные также располагают рядом, чтобы они представляли собой единый массив ячеек.
Выбор метода оптимизации в Excel
Самый важный момент при работе с Solver - выбор метода оптимизации. Если задача линейная, то рекомендуется выбрать вариант linear programming (Simplex LP). Для поиска оптимального решения в этом случае будет использован симплекс-метод - наиболее известный способ решения задач линейного программирования. Это наиболее быстрый метод, который обеспечивает максимально точное решение. Важно понимать, что линейными должны быть все изменяемые переменные (как внутри целевой функции, так и в каждом ограничении). Если хотя бы где-то изменяемая переменная возводится в квадрат, оказывается в знаменателе, участвует в условии вида IF, встречается внутри функции VLOOKUP, возводится в степень, от нее берется логарифм и пр., то линейное программирование использовать нельзя. Условие линейности также нарушается, если необходимо получить только целые значения изменяемых переменных.
В нелинейных случаях нужно выбирать из двух оставшихся вариантов. Если функция отвечает условию гладкости, то можно использовать вариант GRG Nonlinear (Generalized Reduced Gradient). Гладкость функции (smoothness) - более строгое условие, нежели непрерывность функции. Любая гладкая функция непрерывна, но не любая непрерывная функция гладкая. Например, функция константы непрерывная, но не гладкая. Гладкость бывает разного порядка - зависит от того, производную какого порядка можно от этой функции взять. Например, линейная функция - гладкая первого порядка, т.к. от нее можно взять только первую производную. Квадратичная функция - гладкая второго порядка, т.к. от нее можно взять первую и вторую производную.
На практике Вам необходимо в первую очередь понимать, является ли целевая функция непрерывной (то есть нет ли у нее разрывов или скачков значений в определенном месте). Если это полином (парабола и выше), степенная функция, логарифм, тригонометрическая функция и пр., то условие непрерывности выполнено. Непрерывность обычно нарушается, когда на разных интервалах значений изменяемой переменной функция описывается разной формулой (например, при Х<8 функция линейная, а при X>8 - квадратичная). Обычно в файлах Excel непрерывность нарушается при использовании конструкций вида IF и VLOOKUP (важно, чтобы аргументом этих расчетов была изменяемая переменная, во всех остальных случаях такие конструкции в файле не являются проблемой). В этом случае функция не будет непрерывной (и, как следствие, гладкой). А это значит, что GRG Nonlinear использовать нельзя.
GRG - достаточно быстрый метод. В его основе лежит расчет градиента - градиент функции в данной точке показывает направление ее наибольшего роста (снижения) в этой точке. Главная проблема этого метода - он останавливается в тот момент, когда находит локальный минимум функции. Например, возможна такая ситуация:
Ложный (локальный) минимум при поиске решения методом GRG Nonlinear
При поиске минимума данной функции метод может ложно остановиться в точке А (локальном минимуме функции), в то время как настоящий (глобальный) минимум функции находится в точке С. Таким образом, результат функции очень сильно зависит от начальных значений изменяемых переменных, и при разных начальных условиях Excel будет возвращать разный результат (не всегда правильный). При этом локальные минимумы и максимумы могут возникать у многих видов функций, например, у полиномов разной степени (Х3,X4,X5 и пр.). Чтобы использовать данный метод, нужно быть уверенным в непрерывно возрастающем или убывающем характере функции.
Если линейное программирование и градиентный метод не подходят, то можно использовать вариант Evolutionary. Этот метод реализует сложный итерационный вариант перебора возможных значений.
Отметим также, что существует компромиссный вариант между GRG и Evolutionary. Выбрав вариант GRG Nonlinear, можно зайти на вкладку Option и там указать опцию "Use multistart". В этом случае GRG стартует с нескольких начальных точек (система сама генерирует выборку распределенных случайным образом стартовых значений), далее выполняя свою стандартную процедуру поиска оптимального решения. В этом случае нахождение глобального максимума не гарантировано, но вероятность, что программа вернет именно его, существенно повышается.
Почему одни страны, города или компании добиваются экономического успеха, а другие - вынуждены влачить жалкое существование? Почему экономический рост такой слабый, а неравенство доходов все выше? Как новые технологии могут изменить глобальный экономический ландшафт? Присоединяйтесь к нашей группе ВКонтакте, чтобы получать больше информации о долгосрочных трендах в экономике и бизнесе.
