Оптимизация

 
Решение задач оптимизации

П1.1. Поиск экстремумов  и решение уравнений

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

    Найдем  с помощью «Поиска решения» минимум  функции

           .       (П1.1)

    На  рабочем листе в ячейках A1:B2 создадим таблицу, в которой хранятся значение аргумента и значение функции (рис. П1). Ячейка B2 содержит формулу (П1.1)

          «=2*A2^2-3*A2+1».

    После ввода формулы, которая является целевой функцией, выполняем команду «Поиск решения». В окне диалога «Поиск решения» указываем адрес целевой ячейки ($B$2), цель поиска (минимальное значение) и адрес изменяемой ячейки ($A$2). Так как наша исследуемая функция является нелинейной, то в параметрах «Поиска решения» нужно обязательно снять флажок «Линейная модель». Теперь можно дать команду «Выполнить», результатом которой будет окно, показанное на рис. П2. В окне «Результаты поиска решения» обязательно прочитайте сообщение о ходе выполнения команды. Найденные численные значения могут быть сохранены на рабочем листе в изменяемых ячейках, при необходимости можно восстановить исходные значения. Сохранив результаты поиска минимума, в ячейке $A$2 мы обнаружим значение 0,75, которое прекрасно совпадает с точным значением положения минимума x_min = 3/4.

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

    Проанализируем  более сложную мультиэкстремальную  функцию

     ,       (П1.2)

найдем  все ее максимумы и минимумы на отрезке –2 £ x £ 2. Прежде всего построим график функции (П1.2) и выясним, сколько и каких экстремумов имеет функция на заданном отрезке. Определим также примерное положение экстремумов. График функции (П1.2) показан на рис. П4, список экстремумов вводим в рабочий лист (рис. П5, ячейки D3:D8). В диапазон F3:F8 вводим формулы типа

    «=SIN(E3)*COS(2*E3)» (ячейка F3).

    В качестве начального приближения в  ячейках E3:E8 используем данные из столбца D3:D8. Для точного определения положения каждого локального экстремума мы должны использовать «Поиск решения» с соответствующим набором параметров (целевые ячейки находятся в диапазоне F3:F8, изменяемые ячейки – в диапазоне E3:E8; не забудьте указать цель поиска и ограничения на допустимые значения аргумента). Уточненные экстремальные значения функции и аргумента показаны на рис. П5.

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

Рис. П1. Поиск минимума функции (П1.1).

Рис. П2. Диалог «Результаты поиска решения».

Рис. П3. Результат поиска максимума функции (П1.1).

Рис. П4. График функции (П1.2).

Рис. П5. Приближенные и точные положения  локальных экстремумов функции (П1.2) на отрезке [2, 2] (включая крайние точки).

    Помимо задач оптимизации инструмент «Поиск решения» позволяет решать уравнения вида

     .        (П1.3)

    Найдем  точки пересечения функции (П1.2) с  осью абсцисс на отрезке [-2; 2]. Для  этого мы должны решить уравнение

     .        (П1.4)

    Из  графика функции (П1.2) видно, что на заданном отрезке имеется три  корня (рис. П1.4). Занесем приближенные значения корней в таблицу (рис. П6, ячейки A3:A5). В диапазон C3:C5 введем формулы

          «=SIN(A3)*COS(2*A3)» (ячейка C3),

    а в ячейки B3:B5 скопируем приближенные значения корней из диапазона A3:A5. Для отыскания каждого корня требуется запустить «Поиск решения» с соответствующим набором параметров. Например, при поиске первого корня  
x_п = -0,9 в качестве целевой ячейки указывается ячейка C3, в качестве изменяемой – ячейка B3. Цель поиска во всех случаях одна – сделать значение целевой ячейки равной нулю. Результаты решения уравнения (П1.4) представлены в таблице на рис. П6.

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

     .        (П1.5)

    Очевидно, что решениями системы (П1.5) являются точки пересечения окружности с радиусом 1 и кубической параболы 3/5(x³-1) (рис. П7). На рабочем листе создадим таблицы и введем формулы, как показано на рис. П8. Ячейки A3 и B3 содержат текущие значения переменных x и y и являются изменяемыми ячейками для «Поиска решения». Левые части уравнений (П1.5) запрограммированы в ячейках E2 и E3

    «=A3^2+B3^2» (ячейка E2),

    «=3*A3^3-5*B3» (ячейка E3),

значения  правых частей внесены в ячейки F2 и F3. Из графиков системы (П1.5) предварительно определяем приближенные значения корней и вводим пару значений в ячейки A3 и B3. Затем открываем окно «Поиск решения» и указываем параметры поиска (рис. П9). В качестве целевой ячейки выбрана ячейка E2, в которой требуется установить значение 1, изменяемые ячейки - A3 и B3. Чтобы решение удовлетворяло второму уравнению системы, добавим ограничение $E$3 = $F$3. Выполняя поиск, находим две пары решений системы (П1.5) и копируем их в таблицу «Решения» (рис. П8).

Рис.П6. Приближенные и точные решения уравнения (П1.4) на отрезке  
xÎ[-2; 2].

Рис. П7. Графическое решение системы (П1.5).

Рис. П8. Численное решение системы (П1.5).

Рис. П9. Параметры «Поиска решения» для  решения системы (П1.5).

П1.2. «Поиск решения» и  регрессионный анализ

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

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

           .       (П1.6)

    Здесь V – объем продаж, t – время, A, B, C и D – параметры модели. Выбранная функция обеспечивает моделирование регулярных колебаний с амплитудой A и частотой B, параметр C отвечает за синхронность изменений V(t) с исходными данными, параметр D задает средний уровень объема продаж, относительно которого происходят колебания. Значения параметров A, B, C и D неизвестны и наша задача заключается в их определении. Будем подбирать параметры модели так, чтобы сумма квадратов разностей между наблюдаемыми (W) и теоретическими (V) значениями была минимальной

           .       (П1.7)

Суммирование  в (П1.7) производится по всему набору наблюдаемых величин.

    Поставленная  задача легко решается с помощью инструмента «Поиск решения». Заполним исходными данными диапазоны A2:A37 (номер месяца) и B2:B37 (наблюдаемые величины W). В ячейки C2:C37 введем формулы модели (П1.6)

    «=$E$3*SIN($F$3*A2+$G$3)+$H$3» (ячейка C2),

в которых  содержатся абсолютные ссылки на таблицу «Параметры модели». Целевая функция (П1.7) вычисляется в ячейке E7 с помощью функции СУММКВРАЗН

    «=СУММКВРАЗН(B2:B37;C2:C37)».

    Для корректного решения задачи оптимизации  необходимо задать «хорошие» начальные значения для параметров модели. Из графика П10 видно, что амплитуда колебаний A » 10, средний уровень объема продаж D » 30, частота колебаний B » 2p/12 » 0,52, начальный сдвиг фазы колебаний  
C » -p/2 » -1,57. Вносим эти значения в ячейки E3:H3 и выполняем «Поиск решения», где в качестве целевой ячейки указан адрес E7 и в качестве изменяемых ячеек указан диапазон E3:H3 (ограничения отсутствуют). Результат оптимизации показан на рис. П11. Используя найденные значения параметров, по формуле (П1.6) можно определить объем продаж в произвольный момент времени. Достоверность модели можно оценить, вычислив коэффициент корреляции и другие статистические параметры (такие функции имеются в MS Excel). Однако и без дополнительных вычислений из рис. П10 наглядно видно, что модель адекватно описывает наблюдаемую зависимость.

Рис. П10. Объемы продаж (символы) и результаты модели (П1.6).

Рис. П11. Рабочий лист регрессионной модели (П1.6).

Задачи.

    1. Найдите экстремумы функций.

 

    2. Решите уравнения и системы  уравнений