Метод множителей Лагранжа

Размещено на http://www.allbest.ru/

1. Классификация задач нелинейного программирования и методы их решения

1.1 Постановка задач нелинейного программирования

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

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

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

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

.

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

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

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

где х -- произвольная точка из допустимого множества задачи.

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

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

Разницу между глобальным и локальным максимумами легко видеть на следующем рисунке.

Рисунок 1.1 Разница между глобальным и локальным максимумами

Точки А и В являются точками локального максимума, точка С является точкой глобального максимума.



1.2 Выпуклые и вогнутые функции

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

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

Графический пример выпуклой функции изображен на следующем рисунке.

Рисунок 1.2 Графический пример выпуклой функции

Функция называется вогнутой на некотором выпуклом множестве S", если для любых двух точек и соотношение выполняется для всех : .

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



Рисунок 1.3 Графический пример вогнутой функции

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

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

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

Далее я рассмотрю критерии выпуклости и вогнутости функций. Введу некоторые дополнительные определения.

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

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

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

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

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

Для случая функции одной переменной приведенные теоремы принимают следующий вид:

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

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



1.3 Методы решения задач нелинейного программирования

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

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

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

Рассмотрим задачу нелинейного программирования, содержащую только две переменные, записанную в виде

.

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

Множество точек, удовлетворяющих ограничениям задачи, называется допустимым множеством задачи.

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

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

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

1. На плоскости наносятся геометрические места точек, соответствующих каждому уравнению из ограничений задачи , . Строится допустимое множество задачи. Если допустимое множество задачи пусто, то задача не имеет решения.

2. Строятся линии уровня целевой функции при различных значениях параметра .

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

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

5. Для найденной точки определяют ее координаты и значение целевой функции в данной точке .



1.3.2 Градиентные методы

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

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

max (min) ,

.

Общая схема метода состоит в построении последовательности приближений , исходя из соотношения

где направление убывания функции вдоль.

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

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

. Для коэффициента проверяется выполнение условия

Если оно выполнено, то полагается . Если нет, то производится дробление шага, т.е. принимается и вновь проверяется выполнение условия (1.3.4). Процесс дробления, т.е. умножения текущего значения на , продолжается до тех пор, пока условие (1.3.4) не окажется выполненным. Этот процесс не может быть бесконечным, поскольку -- направление убывания. Первое , при котором условие выполнено и принимается за [4]

1.3.3 Метод кусочно-линейной аппроксимации

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

при условиях

Чтобы найти решение задачи (1.3.5)(1.3.7) функции и заменяют кусочно-линейными функциями и и переходят к задаче

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

Тогда функции и можно записать в виде

где

Причем

Подставляя теперь в (1.3.8), (1.3.9) выражения функции и в соответствии с формулой (1.3.11), приходят к задаче линейного программирования:

[2]

1.3.4 Метод множителей Лагранжа

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

где функции и , непрерывны, и непрерывны их частные производные по .

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

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

Рисунок 1.4 Касание в точке, являющейся оптимальным решением

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

Из условия пропорциональности в точке имеем

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

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

Введем новую функцию

.

Тогда последняя система перепишется в виде:

Функцию F называют функцией Лагранжа. [4]

Необходимые условия условного экстремума.

Если - точка экстремума функции F по условиям связи

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

Достаточные условия условного экстремума.

Пусть для и выполняются условия (1.3.30), то есть является стационарной точкой функции Лагранжа , если . Тогда:

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

b) является точкой условного минимума функции F по условию (1.3.29), если для произвольных значений , которые все одновременно не равняются нулю и связанны между собой условиями (1.3.31);

c) не является точкой условного экстремума функции F по условию (1.3.29), если может принимать как положительные, так и отрицательные значения зависимо от значений , связанных между собой условиями (1.3.31);

d) вопрос про наличие условного экстремума в точке остается открытым, если не выполняются условия ни одного с предыдущих пунктов a)-c). [1]

Алгоритм метода множителей Лагранжа решения задач нелинейного программирования.

1. Составляют функцию Лагранжа

2. Находят частные производные функции Лагранжа по и , и приравнивают их к нулю

3. Решают систему (1.3.33) и определяют точки, в которых функция может иметь экстремум.

4. Проверяют полученные на этапе 3 точки на экстремум и определяют экстремальное значение функции найденной точки. [4]



2. Реализация метода множителей Лагранжа

2.1 Решение задач нелинейного программирования методом Лагранжа

Найти максимальное(минимальное) значение функции:

При ограничениях:

Математическая постановка задачи состоит в определении минимального(максимального) значения функции (2.1.1) при условиях (2.1.2).

Решим задачу, используя метод множителей Лагранжа. Для этого составим функцию Лагранжа:

Вычислим частные производные функции Лагранжа по всем переменным:

Составим систему уравнений для нахождения стационарных точек на основании необходимых условий условного экстремума (1.3.30):

Имеем линейную систему пяти уравнений с пятью неизвестными. Для ее решения применим метод Гаусса.

Расширенная матрица системы:

Приведем к верхнему треугольному виду:

Отсюда получим:

Следовательно, функция Лагранжа имеет одну стационарную точку при

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

тогда второй дифференциал функции Лагранжа:

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

Если

точка условного максимума.

.

Ответ:

2.2 Реализация задач нелинейного программирования в Mathcad

нелинейный программирование лагранж mathcad

1. Запускаем Mathcad. Открывается пустое окно для ввода задачи и решения. Обозначим специально для удобства решения задачи в программном пакете Mathcad переменные таким образом:

2. Записываем условие задачи. Функцию от переменных x, y, z и ограничения p и q от этих же переменных. Само значение функции и ограничения записывается после знака присваивания, который устанавливается с помощью окна в Mathcad “Вычисление” и выглядит таким образом . Степень аргумента устанавливается с помощью этой кнопки , которая находится в окне Mathcad “Матрица”. Ограничения нужно записывать предварительно перенеся с правой части в левую результирующее значение.

3. Далее приравниваем к нулю переменные p и q от аргументов x, y, z, относящиеся к соответствующим ограничениям. Для приравнивания нужно использовать знак, который устанавливается с помощью комбинации клавиш Ctrl + =.

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

5. После мы должны найти вектор частных производных функции Лагранжа, что является градиентом Функции Лагранжа. Определяем переменную G от аргументов x, y, z, , и присваиваем ей оператор градиента с помощью комбинации клавиш Ctrl+Shift+G и заполняю нижний прямоугольник аргументами x, y, z, , , а в прямоугольник по середине записываю обращение к Функции Лагранжа с ее аргументами. В конце ставлю знак следствия , который находится в окне Mathcad “Вычисление”. После чего у нас появится система.

6. Дальше ищем нули частных производных, т.е. точки, которые подозрительны на экстремум. Для этого открываем окно Mathcad “Символьные” и выбираем данную функцию . В треугольник слева выписываем новую переменную O, после которое через оператор присваивания присваиваем значение переменной G с ее аргументами x, y, z, , . В правой части от ставим запятую и далее через запятую перечисляем все аргументы x, y, z, , и в конце устанавливаем знак следствия из окна “Вычисление”. После чего нужно подождать некоторое время. В итоге строка выделится красным цветом, т.к. возвращенный символьный результат слишком велик для отображения, но его можно использовать в последующих вычислениях, что мы и сделаем.

7. Ниже выписываем ранее определенную переменную O и ставим знак равенства из окна Mathcad “Вычисление”. После установки знака равенства, программа производит вычисление и выписывает матрицу.

Замечание: знак равенства устанавливать обязательно нужно из указанного окна Mathcad, а не с клавиатуры.

8. Далее определяем аргументам соответствующие матрицы подозрительных точек. Для этого обозначаем новую переменную X (обязательно большая буква), которой будет соответствовать матрицы точек для аргумента x. После определения переменной X через оператор присваивания присваиваем ей значение переменной O с индексом 0 значения столбца матрицы с помощью кнопки в окне Mathcad “Матрица”. Точно также делаем для остальных четырех аргументов, меняя лишь имя переменных и значения столбца матрицы.

9. Наконец получаем значения функции в найденных точках. Определяем новую переменную ff, которой присваиваем через оператор присваивания вектор кнопкой , которая находится в окне Mathcad “Матрица”, функции от трех первых аргументов, найденных в предыдущем пункте. В результате получаем матрицу значений.

10. Теперь с помощью определенной выше переменной ff и функций min и max находим максимальное и минимальное значение. Определяем новые переменные MinF и MaxF, которым присваиваем соответственные значения функции min от переменной ff и функции max от переменной ff, где в конце устанавливаем знак равенства и получаем результат.

Размещено на Allbest.ru

...