О способе поиска минимального значения функции.

Параметры SOLVER-a

Диалоговое окно "Параметры поиска решения"

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

Максимальное время

Служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах) не превышающее 32767 (32767₁₀=77777₈), значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

Итерации

Служит для управления временем решения задачи, путем ограничения числа промежуточных вычислений. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

Точность

Служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать десятичную дробь от 0 (нуля) до 1. Чем больше десятичных знаков в задаваемом числе, тем выше точность — например, число 0,0001 представлено с более высокой точностью, чем 0,01.

Допустимое отклонение

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

Сходимость

Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков — например, 0,0001 соответствует меньшему относительному изменению по сравнению с 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения.

Линейная модель

Служит для ускорения поиска решения линейной задачи оптимизации.

Показывать результаты итераций

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

Автоматическое масштабирование

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

Значения не отрицательны

Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение.

Оценка

Служит для указания метода экстраполяции — линейная или квадратичная — используемого для получения исходных оценок значений переменных в каждом одномерном поиске.

Линейная. Служит для использования линейной экстраполяции вдоль касательного вектора.

Квадратичная. Служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач.

Производные (в программе - Разности)

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

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

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

Метод Служит для выбора алгоритма оптимизации — метод Ньютона или сопряженных градиентов — для указания направление поиска.

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

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

Загрузить модель

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

Сохранить модель

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

 

О способе поиска минимального значения функции.

Пусть задана функция двух переменных f(x, y). Пусть требуется найти её минимальное значение.

Вернёмся к подземной гидромеханике. Пусть задано распределение давления в пласте, в котором работает добывающая скважина, и дана карта изобар (см. рисунок 4). Допустим, мы находимся в какой-либо точке пласта, как попасть в точку, где давление минимально? Один из вариантов ответа – двигаться вместе с частицами потока. Куда направлен вектор скорости потока? По закону Дарси имеем:

,

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

Рисунок 4.

 

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

 

Как было указано в курсе «Подземной гидромеханики», вектор градиента выражается следующим образом: , в свою очередь,

.

Если функция двух переменных, то получаем:

, .

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

Рисунок 5.