Нелинейные задачи оптимизации в экономике

Задача оптимизации

А.А. Макаркин

Саратовский государственный аграрный университет имени Н. И. Вавилова,

г. Саратов

Глобальный экстремум – минимум или максимум функции на всей области определения; локальный экстремум – в окрестности точки. Далее в тексте нас интересует точка, в которой находится экстремум, а не его значение. Например, квадратичная функция y=(x-a)2 имеет глобальный минимум в точке x=a. Существуют функции, которые имеют бесконечное множество точек глобальных экстремумов, например, y=sin (x). Большинство функций не имеют никаких экстремумов.

Лагранж Жозеф Луи (1736–1813 гг.) впервые сформулировал задачу об условном экстремуме. Непрерывная функция над ограниченной областью всегда имеет минимальное и максимальное значение. Назовем их «главные экстремумы». Чаще всего точки главных экстремумов находятся на границах области. Заданные ограничения образуются многочисленные локальные граничные экстремумы, например, дорога под уклон, упирающаяся в забор в форме подковы.

Задача оптимизации – поиск в ограниченной области точек (координат) главных экстремумов. Искать минимум функции все равно, что искать максимум этой же функции со знаком «минус». Далее везде, если специально не оговорено, будем искать минимум функции. Как иногда говорят, «будем спускаться к минимуму».

Канторович Леонид Витальевич (1912–1986 гг.) в 1939–1940 гг. положил начало задачам оптимизации в экономике, показал, как решать линейные задачи оптимизации (линейное программирование).

Целевая функция – это функция, у которой ищут условный экстремум. План – любая точка из области ограничений. Оптимальный план – точка, где целевая функция имеет главный экстремум.

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

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

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

Очень трудно решать нелинейные задачи оптимизации, когда целевая функция или ограничения являются нелинейными. Поэтому эти задачи редко решаются в экономике. Рассмотрим методы решения нелинейных задач.

Метод тотального перебора

Любая задача оптимизации может быть решена методом тотального перебора. Алгоритм решения:

·  область ограничений накрывается прямоугольной сеткой;

·  каждый узел сетки проверяется по системе ограничений;

·  если узел – план, для него рассчитывается значение целевой функции;

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

Недостатки метода

·  огромные временные затраты. Даже если необходимо иметь скромную точность 0,001 от ширины интервала ограничений, то для одной переменной надо 1000 раз проверить ограничения и 1000 раз рассчитать значение целевой функции, для двух переменных – 10002 раз, для 10 переменных – 100010 раз.

·  локальные экстремумы. При крупном шаге сетки можно попасть в локальный экстремум и быть далеко от главного экстремума. Этот недостаток устраняется при достаточно мелком шаге сетки. Но тогда еще больше становится первый недостаток.

Ускоренный метод тотального перебора. В методе тотального перебора ускорение может быть достигнуто за счет сгущения сетки вокруг предполагаемого решения:

·  на крупной сетке 1 ищется оптимальный узел 1;

·  вокруг оптимального узла 1 строится локальная сетка 2 с более мелким шагом и ищется оптимальный узел 2;

·  вокруг оптимального узла 2 строится локальная сетка 3 с более мелким шагом и ищется оптимальный узел 3. И так далее.

Сгущение останавливается, когда достигнут заданный шаг сетки.

Недостатки метода:

·  большие временные затраты. Но они существенно меньше, чем в методе тотального перебора;

·  локальные экстремумы. При крупном шаге сетки 1 можно зацепиться за локальный экстремум.

Представьте себе, что один узел сетки 1 попал близко от локального экстремума, а другой узел сетки 1 попал далеко от главного экстремума в области ограничений. Если значение целевой функции в первой точке окажется меньше, чем во второй, сетка будет сгущаться вокруг локального экстремума.

Такая ситуация случается достаточно редко, но о ней нужно помнить.

Метод спуска по сетке: Пусть целевая функция зависит от одной переменной y=f (x), и область ограничений – отрезок [a<x<b].

·  выберем шаг сетки h;

·  в области ограничений зададимся начальным приближением, точкой старта x=x0, и вычислим
f (x0)4

·  проверим точки x0–h, x0, x0+h. Если точка выходит за пределы области ограничений, значение целевой функции в этой точке делаем большим числом. Если точка не выходит за пределы области ограничений, вычислим в этой точке значение целевой функции;

·  сравним значения целевой функции в соседних точках x0–h, x0, x0+h;

·  если f (x0) оказалось самым маленьким, найден оптимальный план x0 с точность
h шага сетки;

·  конец спуска;

·  если нет, сдвигаем x0 в левую или правую точку, где целевая функция оказалась меньше;

·  повторяем вычисления до тех пор, пока не найдем оптимальный план (пункт 4), или пока не упремся в границу области. Тогда оптимальный план будет найден в последней точке x0.

Недостатки метода:

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

·  Зависимость от начального приближения. Будет найден тот экстремум, в окрестности которого находится начальная точка x0. Это может быть главный экстремум, локальный экстремум, или локальный граничный экстремум.

Метод градиентного спуска. В методе спуска по сетке чтобы перейти из начальной точки в соседнюю точку нужно проанализировать для одной переменной – 3 соседних точки, для двух переменных – 32=9 точек, для 10 переменных – 310 точек. То есть очень много вычислений на каждое перемещение. При этом траектория представляет собой ломаную линию, которая вьется вокруг направления наибыстрейшего спуска.

Как известно, направление наибыстрейшего спуска из точки x0 противоположно направлению вектора-градиента в этой точке.

Пусть целевая функция зависит от n параметров y=f (x1, x2,…xn). Тогда:

Здесь частные производные, проекции вектора-градиента на оси координат, вычисляются в точке .

В задаче на условный экстремум задана только целевая функция. Частные производные в точке x0 вычисляются численно, например, как приращения значений целевой функции на малых перемещениях.

Если по переменной xk мы уперлись в границу области, то частная производная по этой координате будет равна 0, нельзя двигаться через границу. Вектор-градиент развернется вдоль границы.

Из точки x0 по направлению против вектора-градиента продвигаемся на шаг h. Новая точка x0 будет иметь координаты:

Как далеко можно продвинуться, какой взять шаг h? При малом шаге возрастает время счета. При большом шаге есть опасность проскочить экстремум. Главный критерий выбора шага h: в новой точке x0 целевая функция должна стать меньше, чем в предыдущей.

В новой точке x0 заново вычисляем вектор-градиент и сдвигаемся на шаг h в противоположном направлении в следующую точку x0.

Критерий останова. В очередной точке
x0 значение целевой функции больше, чем в предыдущей точке.

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

Недостатки метода:

·  временные затраты. Это может быть в случае малого шага спуска по градиенту. Но они существенно меньше, чем в методе спуска по сетке.

·  зависимость от начального приближения. Будет найден тот экстремум, в окрестности которого находится начальная точка x0. Это может быть главный экстремум, локальный экстремум, или локальный граничный экстремум.

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

Для борьбы с локальными экстремумами предложен метод тяжелого шарика. В общих чертах суть метода в следующем. Когда тяжелый шарик скатывается по сложной поверхности, набранная скорость позволяет ему проскакивать локальные ямки. Но эта скорость не должна быть слишком большой. Тогда шарик проскочит главную ямку, остановится на противоположном скате в главную ямку и начнет двигаться обратно. Для реализации этой идеи нужно управлять шагом h.

Программа MS Excel «Поиск решения». В табличном процессоре MS Excel задачи оптимизации решаются в программе «Поиск решения». Если в дополнительном окне «Параметры» установлен флажок «Линейная модель», то тип модели будет «Линейная оптимизация», и для решения используется симплекс-метод. Если к тому же хотя бы для одной их переменных установлено ограничение «цел», то тип модели будет «Целочисленная линейная оптимизация». Тогда для ее решения используется метод ветвей и границ.

Если в дополнительном окне «Параметры» не установлен флажок «Линейная модель», то тип модели будет «Нелинейная оптимизация». Для ее решения всегда используется градиентный метод.

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

Нелинейная оптимизация очень редко используется в экономическом моделировании из-за сложности решения. Главная беда метода градиентного спуска – локальные и локальные граничные экстремумы целевой функции. То есть найденное решение зависит от начального значения, от точки старта. Это мы сейчас покажем на тестовом примере.

Тестирование программы. Для тестирования программы «Поиск решения» была использована нелинейная задача оптимизации с невыпуклыми ограничениями (рис. 1).

Рис. 1. Нелинейная невыпуклая задача оптимизации

Над плоскостью переменных (x1;x2) задана целевая функция – параболоид, который имеет глобальный минимум в точке (3,5; 3,5). Область ограничений – квадрат (0£x1£ 4, 0£x2£ 4), в который вставлена парабола  Неравенство выделяет часть плоскости (x1;x2) ниже параболы. На целевой поверхности парабола разбивается на участки: A®B – убывание; B®C – подъем; C®D – убывание; D®E – подъем. Это образует локальный граничный минимум в точке B. В точке D нет локального граничного минимума, из точки D есть спуск к глобальному минимуму.

Метод тестирования. На рабочем листе записывается задача оптимизации и выполняется в пошаговом режиме. Для этого в окне «Параметры поиска решения» нужно установить флажок «Показывать результаты итераций». После каждого шага изменяются значения решения. Для следующего шага нужно нажать кнопку «Продолжить» в окне «Текущее состояние поиска решения».

Приведем качественное описание тестирования. Из всех начальных точек программа стартовала по отрицательному градиенту, по направлению наибыстрейшего спуска к глобальному минимуму (3,5; 3,5). В описании мы объединили точки, которые ведут себя одинаково.

Там, где начальное направление градиента не пересекает ограничения, точки (3,0; 0,0), (2,0; 0,0), программа «Поиск решения» за один шаг докатилась до минимума (3,5; 3,5). На самом деле был не один шаг, но направление не менялось, поэтому показана одна точка.

Из точек (1,5; 0,0), (1,0; 0,0), (0,5; 0,0) направления по градиенту упираются в ограничение, убывающую ветку C®D. Программа вывела эти решения на границу и продвинула по убывающей ветке к точке D. На участке D®E граница снова начинает возрастать. Для всех трех точек старта программа около точки D нашла оптимальную точку отрыва и по прямой за один шаг докатилась до минимума (3,5; 3,5).

Из точек (0,0; 0,0), (0,0; 1,0), (0,0; 2,0) направления по градиенту упираются в ограничение, возрастающую ветку B®C. Программа вывела эти решения на границу и скатила вниз в точку B. На участке A®B граница убывающая, а в точке B градиент наибыстрейшего спуска выходит из области. Поэтому решения из всех начальных точек остановлены в точке B, точке локального граничного минимума.

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

Подведем итоги тестирования.

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

От локальных экстремумов лучше всего предохраняет удачный выбор начального приближения в окрестности главного экстремума.

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

Для реализации двухшагового тотального перебора удобно написать макрос в Excel на языке VBA. В этот макрос передается целевая функция и все ограничения. Этот макрос найдет начальное приближение и запустит макрос «Поиск решения», который в VBA называется Solver (Решатель).

Похожие статьи:

1. Оценка ситуации неопределенного поведения графических разрезов целевой функции в задачах нелинейной оптимизации затраты – выпуск
2. Контрольные работы и задачи с решением
3. Конформные отображения как важнейшие в прикладной математике
4. Построение нечетких прогностических моделей в экономике
5. ИСПОЛЬЗОВАНИЕ ГРАФОВ И СЕТЕЙ В ЭКОНОМИКЕ