Решение уравнений и задач оптимизации

Решение уравнений и задач оптимизации

3. Решение уравнений и задач оптимизации

Для решения задач оптимизации широкое променение находят различные средства Excel:

· Подбор параметров для нахождения значения, приводящего к требуемому результату.

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

· Диспетчер сценариев для создания и оценки наборов сценариев «что – если» с несколькими вариантами исходных данных.

3.1 Подбор параметров

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

Если команда Подбор параметра отсутствует в меню Сервис, выполните команду Сервис/Надстройка и установите флажок Пакет анализа в окне диалога Надстройка

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

· формула для расчета;

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

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

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

Такой процесс называется итерацией, и продолжается он до тех пор, пока редактор не выполнит 100 попыток или не найдет решения, лежащее в пределах точности 0,001 от точного значения (настройка этих параметров осуществляется с помощью команды Сервис/Параметры, вкладка Вычисления)

Оптимизация с помощью команды Подбор параметров выполняется так:

1. Создайте лист, например, с формулой =B1*B2 в ячейке B3, пустой (переменной) ячейкой (B2) и другими данными (B1), которые могут понадобиться при вычислениях. Например, необходимо определить количество книг по цене 23,75 грн., которые необходимо продать, чтобы объем продаж составил 10000,00 грн.

2. Выделите ячейку листа (B3), в которой содержится формула (эта ячейка появится в поле «Установить в ячейке» в окне диалога Подбор параметра). Выполните команду Сервис/Подбор параметра. Открывается окно диалога Подбор параметра.

3. Введите в текстовое поле Значение число, соответствующее объему продаж — 10000. Переместите курсор в текстовом поле Изменяя значения ячейки. Выделите ту ячейку, в которой должен содержаться ответ (переменная ячейка). Ее содержимое будет подобрано и подставлено в формулу командой Подбор параметра. Выделенная ячейка (B2) выделяется на листе рамкой. Нажмите кнопку ОК, чтобы найти решение.

После завершения итерационного цикла в окне диалога Результат подбора параметра появляется сообщение, а результат заносится в ячейку листа. Решение показывает, что для достижения объема продаж 10000 грн. необходимо продать 421 книгу по цене 23,75 грн. Для закрытия окна диалога Результат подбора параметра щелкните на кнопке ОК.

3.2 Команда «Поиск решения»

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

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

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

Общие свойства, которые характерны для задач, решаемых с помощью надстройки Поиск решения:

· Существует единственная целевая ячейка, содержащая формулу, значение которой должно быть сделано максимальным, минимальным или же равным, какому-то конкретному значению.

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

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

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

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

После того, как задача оптимизации будет подготовлена на листе, можно приступать к работе.

1. Выделите на листе целевую ячейку, в которую введена формула.

2. Выполните команду Сервис/Поиск решения. Открывается окно диалога Поиск решения. Поскольку была выделена ячейка, в текстовом поле «Установить целевую ячейку» появится правильная ссылка на ячейку. В группе «Равной» переключатель по умолчанию устанавливается в положение «Максимальному значению».

3. Перейдите к полю «Изменяя ячейки» и введите переменные ячейки листа

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

5. Когда оптимизационная задача будет готова к выполнению, можно нажать кнопку Выполнить для получения ответа. Появится окно диалога с описанием результатов процесса оптимизации.

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

3.3 Диспетчер сценариев «что–если»

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

Чтобы устранить эти ограничения, разработчики Excel создали Диспетчер сценариев, помогающий работать с несколькими моделями «что – если». Командой Сервис/Сценарии можно создавать новые и просматривать существующие сценарии для решения задач, и отображать консолидированные отчеты.

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

Создание сценариев происходит следующим образом:

· Выполните команду Сервис/Сценарии. Открывается изображение окна диалога Диспетчер сценариев.

· Нажмите кнопку Добавить, чтобы создать первый сценарий. Откроется окно диалога Добавление сценария.

· Введите Лучший вариант (или любое другое имя) в поле Название сценария, затем с помощью окон диалога введите изменяемые ячейки. Когда этот сценарий будет готов, введите следующий.

· Нажмите кнопку Добавить, чтобы создать второй сценарий. Введите название Худший вариант. После завершения создания двух сценарием можно приступить к просмотру результатов.

· Закройте окно диалога Диспетчер сценариев кнопкой Закрыть.

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

· Выполните команду Сервис/Сценарии. Открывается окно диалога:

· Выберите из списка сценарий для просмотра.

· Нажмите кнопку Вывести. Excel заменяет содержимое ячеек листа значениями из сценария и отображает результаты на листе.

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

Создание отчетов по сценарию

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

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

Создание отчета по сценарию происходит следующим образом:

· Выполните команду Сервис/Сценарии. Откроется окно диалога Диспетчер сценариев.

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

Системы уравнений и задачи оптимизации

Разложение на множители алгебраического многочлена степени n

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

Методы решения квадратных уравнений

Квадратное уравнение – это алгебраическое уравнение второй степени (также его называют квадратным трёхчленом), которое можно записать в следующем виде:

Безусловная оптимизация. Метод Ньютона

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

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

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

где — матрица Гессе, которая представляет собой симметричную квадратную матрицу вторых частных производных целевой функции в точке

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

Продифференцируем функцию, разложенную в ряд Тейлора, по компоненте

Таким образом, целевая функция имеет экстремум функции при следующем значении ее аргумента:

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

— вектор столбец управляемых параметров, которые определяются в задаче оптимизации (размерность: 1xn)

— квадратная матрица вторых частных производных (размерность: nxn)

— вектор столбец градиента целевой функции по управляемым параметрам (размерность: 1xn).

Итерационный процесс расчета продолжается до тех пор, пока не будут выполнены некоторые критерии останова:

— траектория поиска остается в малой окрестности текущей точки поиска:

— приращение целевой функции не меняется:

— градиент целевой функции в точке локального минимума обращается в нуль:

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

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

Рис.1. Поиск минимума квадратичной функции по методу Ньютона

При увеличении количества переменных и усложнением функции возникают сложности с вычислением матрицы Гессе, поэтому в настоящее время разработаны квазиньютоновские алгоритмы, основанные на приближённых выражениях для матрицы Гессе. Тем не менее, многие компьютерные программы, решающие задачу оптимизации, построены на основе метода Ньютона. Роль метода Ньютона велика: большинство наиболее эффективных методов в линейном и нелинейном программировании строятся на его основе.

Методика расчета

• 1 шаг: Определяем аналитические выражения (в символьном виде) для вычисления градиента рассматриваемой функции и квадратной матрицы Гессе:

градиент рассматриваемой функции:

квадратная матрица Гессе:

• 2 шаг: Задаем начальное приближение

Далее выполняется итерационный процесс.

• 3 шаг: Определяем новые значения аргументов функции после выполнения k-го шага расчета методом по следующей формуле:

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

Оптимизационные задачи. Общие сведения

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

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

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

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

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

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

Приращение вектора управляемых параметров в большинстве случаях вычисляется по формуле:

В данном выражении — значение вектора управляемых параметров на k-ом шаге, — шаг расчета, а — направление поиска экстремума функции.

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

Шаг расчета

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

Другими словами, величина шага расчета вычисляется при решении следующего выражения:

В результате решения данного уравнение мы получим, что шаг расчета в символьном виде определяется следующим образом:

где — значение аргумента функции на k-ом шаге итерации;

n – количество неизвестных переменных, которые определяются в ходе решения задачи;

L – некоторая константа, которая определяется из определителя следующей матрицы:

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

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

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

Рис.1. Критерий выбора шага расчета по правилу Армихо

Методика определения шага расчета оптимизационной задачи в соответствии с правилом Армихо заключается в следующем:

1.Задать коэффициент в диапазоне от 0 до 1.

2.Задать начальное значение шага .

Процедура поиска (проверка выполнения условия по правилу Армихо)

3. В случае если условие по правилу Армихо не выполняется, тогда необходимо скорректировать шаг расчета , где переменная может принимать любое значение от 0 до 1, по умолчанию примем, что переменная , а — текущий шаг поиска.

4. В случае если условие по правилу Армихо выполняется, тогда в качестве шага расчета можно принять , а процедура поиска завершается.

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

• Второе условие (Правило Вольфе-Пауэлла — Wolfe. P) является модифицированным критерием, позволяет выбрать шаг расчета в случае выполнения двух условий:

— функция не должна превышать значения некоторой убывающей линейной функции, равной в нуле:

— величина скорости изменения функция в заданном направлении была в раз больше, чем скорость изменения функции в первоначальной точке

Рис.2. Критерий выбора шага расчета по правилу Вольфе-Пауэлла

Методика определения шага расчета оптимизационной задачи в соответствии с правилом Вольфе-Пауэлла заключается в следующем:

1. Задать коэффициент и в диапазоне от 0 до 1 .

2. Задать начальное значение шага , принять коэффициент и

Процедура поиска (проверка выполнения условия по правилу Вольфе-Пауэлла)

3. В случае если первое условие по правилу Вольфе-Пауэлла не выполняется, тогда принять коэффициент . Перейти к пункту №5.

4. В случае если второе условие по правилу Вольфе-Пауэлла не выполняется, тогда принять коэффициент :

— в случае если , то перейти к пункту №5;

— в случае если выполнить экстраполяцию, положив , где r – коэффициент экстраполяции . Перейти к пункту №3.

5. Выполнить текущий расчет шага по формуле

где — коэффициент интерполяции, который определяется в следующем диапазоне

Перейти к пункту №3.

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

• Третье условие (правило Голдстейна-Армийо) позволяет выбрать шаг расчета, рассматривая следующее неравенство:

Методика определения шага расчета оптимизационной задачи в соответствии с правилом Голдстейна-Армийо заключается в следующем:

1.Задать коэффициент и в диапазоне от 0 до 1 .

2. Задать начальное значение шага

3. В случае если условие по правилу Голдстейна-Армийоне выполняется, тогда необходимо скорректировать шаг расчета , где переменная может принимать любое значение от 0 до 1, по умолчанию примем, что переменная , а — текущий шаг поиска.

4. В случае если условие по правилу Голдстейна-Армийо выполняется , тогда в качестве шага расчета можно принять , а процедура поиска завершается.

Критерии останова оптимизационного процесса

Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета выполняется один (или несколько) критериев:

— траектория поиска остается в малой окрестности текущей точки поиска:

— приращение целевой функции не меняется:

— градиент целевой функции в точке локального минимума обращается в нуль:

Классификация методов оптимизации.

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

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

Методы безусловной оптимизации

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

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

Рис.3. Задача безусловной оптимизации для функции двух переменных

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

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

Наиболее популярными (с точки зрения обучения в высшей школе) являются следующие методы решения оптимизационных задач нулевого порядка:

Методы одномерного поиска:

— Метод дихотомического деления и метод золотого сечения – это методы одномерной оптимизации, основанные на делении отрезка, на котором ищется экстремум, пополам или в пропорциях золотого сечения (0,382 / 0,618), соответственно.

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

Методы многомерного поиска:

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

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

— Симплексный метод (метод деформируемого многогранника или метод Нелдера-Мида) – это метод безусловной оптимизации нулевого порядка, основанный на многократно повторяемых операциях построения многогранника с (n+1) вершинами, где n — размерность пространства управляемых параметров, и перемещения наихудшей вершины (с наихудшим значением целевой функции) в направлении центра тяжести многогранника.

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

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

Наиболее популярными (с точки зрения обучения в высшей школе) являются следующие методы решения оптимизационных задач первого порядка:

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

— Метод наискорейшего спуска – это метод нахождения локального минимума (максимума) функции при движении вдоль градиента с оптимальным шагом. Шаг расчета выбирается минимума целевой (минимизируемой) функции в направлении спуска.

— Метод сопряженных градиентов (метод Флетчера-Ривса) – это метод безусловной оптимизации первого порядка, в котором направление поиска на очередном шаге есть градиентное направление, скорректированное с учетом направления поиска на предыдущем шаге.

— Метод переменной метрики (метод Девидона-Флетчера-Пауэлла) – это метод безусловной оптимизации, в котором за основу взято решение системы уравнений, выражающих необходимые условия экстремума.

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

Наиболее популярными (с точки зрения обучения в высшей школе) являются следующие методы решения оптимизационных задач второго порядка:

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

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

Методы условной оптимизации

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

при заданных условиях (равенствами и/или неравенствами), при этом число ограничений m может быть как больше, так и меньше числа переменных n.

, j=1,2,…,m.

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

Рис.4. Задача условной оптимизации для функции двух переменных

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

• Методы сведения задачи к безусловной оптимизации — это задача условной оптимизации, основанная на преобразование задачи нелинейного программирования в последовательность задач безусловной оптимизации путем построения вспомогательных функций

Наиболее популярными (с точки зрения обучения в высшей школе) являются следующие методы решения оптимизационных задач условной оптимизации:

— Метод неопределенных множителей Лагранжа – это метод условной оптимизации, ориентированный на поиск экстремума целевой функции при наличии ограничений типа равенств.

— Условия Куна-Таккера – это метод решения оптимизационной задачи математического программирования с заданными ограничениями. Метод является обобщением метода множителей Лагранжа на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств.

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

• Методы непосредственного решения задачи условной оптимизации – это задача условной оптимизации, основанная на движении из одной допустимой точки, где выполнены все ограничения, к другой допустимой точке с лучшим значением целевой функции.

Наиболее популярными (с точки зрения обучения в высшей школе) являются следующие методы решения оптимизационных задач условной оптимизации:

— Метод приведенного градиента – это метод условной оптимизации, ориентированный на решение задач с ограничениями типа равенств. Направление движение в данном методе определяет приведенный градиент функции.

— Метод возможных направлений (метод Зойтендейка) — этот метод решения задач математического программирования основан на движении из одной допустимой точки к другой с лучшим значением целевой функции.

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

Безусловная оптимизация. Метод градиентного спуска (метод градиента).

Метод градиентного спуска (метод градиента) (в англ. литературе «gradient-search method») – это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:

— это значения аргумента функции (управляемые параметры) на вещественной области.

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

где i, j, n — единичные векторы, параллельные координатным осям.

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

Рис.1. Градиент к поверхности функции

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

Модуль градиента определяется в соответствии со следующей формулы:

Углы наклона этого вектора к направлению координатных осей х, у, z определяются исходя из соотношений в прямоугольном треугольнике (косинус угла):

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

«+» используется, когда ищется максимум функции;

«-» используется, когда ищется минимум функции.

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

Рис.2. Геометрическая интерпретация градиентного метода

Величина рабочего шага в направлении градиента зависит от величины градиента и от коэффициента пропорциональности шага. Величина шага расчета сильно влияет на эффективность метода расчета. В данном методе шаг расчета выбирается двумя способами:

— постоянный шаг расчета;

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

Нормированная запись уравнения

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

где — единичный вектор направления, который определяется по формуле:

— модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента:

– константа, определяющая размеры шага и одинаковая для всех i-х направлений.

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

— если угол наклона градиента меньше 30 градусов, то шаг расчета увеличить на некоторое число ;

— если угол наклона градиента находится в диапазоне от 30 до 60 градусов, то шаг расчета не изменяется ;

— если угол наклона градиента больше 60 градусов, то шаг расчета делится на некоторое число .

Итерационный процесс расчета продолжается до тех пор, пока не будут выполнены некоторые критерии останова:

— траектория поиска остается в малой окрестности текущей точки поиска:

— приращение целевой функции не меняется:

— градиент целевой функции в точке локального минимума обращается в нуль:

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

Методика расчета.

• • 1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции f(x), длины вектора градиента функции |f(x)| и единичного вектора t(V)

градиент рассматриваемой функции:

единичный вектор направления:

• 2 шаг: Задаем начальное приближение

Далее выполняется итерационный процесс.

• 3 шаг: Вычисление координат единичного вектора по формуле, полученной на шаге 1, и определение координат новой точки при движении по направлению единичного вектора как функция от шага расчета.

4 шаг: Определяем шаг расчета: постоянный или дробный шаг расчета.

5 шаг: Определяем новые значения аргументов функции после выполнения k-го шага расчета методом градиентного спуска:

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

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

На этой странице вы найдете примеры решений различных оптимизационных задач с использованием пакета электронных таблиц MS Excel (используется как надстройка Поиск решения, так и ручные вычисления).

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

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

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

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

Алгоритм решения с помощью надстройки «Поиск решения» следующий:

• составить математическую модель задачи: выделить и обозначить переменные, ограничения на них в виде равенств и неравенств (естественные, например, неотрицательность количества, и дополнительные, например, «запасов железной руды не более 10 т»), целевую функцию (то, что нужно оптимизировать) выразить через переменные.
• выделить место под переменные задачи; внести ограничения (левые части — в виде формул от переменных, правые — в виде констант) в файл электронной таблицы Excel,
• внести в ячейку формулу для целевой функции,
• запустить надстройку Поиск решения,
• установить нужные параметры решения (ограничения в листе, ограничения неотрицательности, условие линейности при необходимости и т.п.) и запустить выполнение.

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

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

Задачи оптимизации: примеры в Excel

Задача 1. Намечается крупномасштабное производство легковых автомобилей. Имеются четыре варианта проекта автомобиля $R_j$. Определена экономическая эффективность $К$ — каждого проекта в зависимости от рентабельности производства. По истечении трех сроков $S_i$ рассматриваются как некоторые состояния среды (природы). Значения экономической эффективности для различных проектов и состояний природы приведены в следующей таблице (д. е.):

Выберите оптимальное решение в соответствии с критериями Лапласа, Вальда, Сэвиджа и Гурвица (при $а = 0,5$).

Задача 2. Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода каждого вида сырья на изготовление единицы продукции данного вида в таблице 6. В ней же указаны прибыль от реализации единицы изделия каждого вида и общее количество сырья данного, которое может быть использовано предприятием.
Требуется такой составить такой план производства изделий А и В, при котором прибыль от реализации будет максимальной?

Задача 3. Фирма N, имеющая филиалы (k), производит продукцию. Каждый филиал фирмы выпускает четыре вида продукции из пяти (i=1-5). Данные, характеризующие производство филиалов $b_$, приведены в табл.1.
Филиалы фирмы закупают сырье, из которого производят продукцию, у семи АО (j =1-7). Выход готового продукта из 1 тонны сырья $a_$ показан в табл.2.
Прибыль филиалов фирмы при закупке 1тн сырья у разных АО, $С_$ , показана в табл.3.
В разделе 1 работы требуется:
1.1.Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, ($x_j$), максимизируя прибыль филиала. Далее, студент формулирует экономико-математическую модель общей задачи линейного программирования (ОЗЛП).
1.2.С помощью полученных в результате реализации модели отчетов сделать рекомендации филиалу фирмы по расширению программы выпуска ассортимента продукции.

Задача 4. Для изготовления одного пирожка требуется 0,8 ед. начинки и 4 ед. теста, одного пирожного 4 ед. начинки и 0,5 ед. теста, одного рулета 2 ед. начинки и 2,5 ед. теста. Сколько пирожков, пирожных и рулетов нужно сделать кондитерской, если в наличии имеется 120 ед. теста и 300 ед. начинки?
Определите доход от реализации кондитерских изделий, если доход от продажи одного пирожка составляет 3 рубля, одного пирожного 2 рубля, одного рулета 1,5.
Для решения задачи используется ППП Excel.

Задача 5. Менеджер проекта по строительству нового торгового гипермаркета компании Наше дело надеется завершить проект за пару недель до Рождества.
После обзора оценок времени выполнения отдельных стадий выяснилось, что потребуются дополнительные инвестиции, чтобы сократить длительность проекта так, чтобы он действительно завершился вовремя. В таблице приведены оценки длительностей стадий и стоимость их сокращения на 1 и на 2 недели.
a. Нарисуйте сетевую диаграмму проекта и найдите критический путь.
b. Определите минимальную стоимость сокращения проекта на 5 недель.