Некоторые нелинейные методы решения оптимизационных задач

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

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

Введение

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

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

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

Однако возьмем другой пример. Допусти, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где разместить остановки? И так далее.

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

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

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

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

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

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

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

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

1. Некоторые нелинейные методы решения оптимизационных задач

1.1 Общая характеристика нелинейных методов оптимизации

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

а) классический метод оптимизации, типа метода множителей Лагранжа;

б) выпуклое программирование;

в) динамическое программирование и др.

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

В общем случае нелинейная экономико-математическая модель может быть рассмотрена как задача нелинейного программирования (НП) в виде:

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

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

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

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

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

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

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

а) прямые методы, состоящие в нахождении оптимального решения в направлении наиболее быстрого его достижения, которые относятся к группе градиентных методов (например, метод наискорейшего спуска);

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

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

Рассмотрим принципиальную суть некоторых нелинейных методов оптимизации.

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

дифференциальный экстремум лагранж множитель

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

Идея метода состоит в сведении поиска условного экстремума целевой функции задачи нелинейного программирования:

при ограничениях-равенствах на переменные

к задаче безусловной оптимизации более сложной функции (функции Лагранжа), но без ограничений, которая представляется в виде:

,

где , - дифференцируемые функции; - неопределенные пока еще множители Лагранжа.

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

После чего формируется нелинейная система уравнений:

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

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

Пример. Спрос на продукцию, которая изготавливается на двух видах оборудования, составляет 120 единиц. Себестоимость (д.е.) производства единицы продукции на оборудовании каждой группы зависит от объема производства - соответственно и - и представляется в виде: для первой группы - для второй группы .

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

Решение.

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

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

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

Из решения системы находим:

Таким образом, по первой группе оборудования необходимо выпустить 66,5, а по второй - 53,5 единиц продукции. При этом минимальные затраты составят:

д.е.

1.3 Выпуклое программирование

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

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

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

Рис. 1. Пример выпуклой функции

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

(*)

для любых и любого действующего числа (рис.1).

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

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

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

при наличии ограничений на переменные:

и условий неотрицательности переменных:

.

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

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

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

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

Рассмотрим решения некоторых типовых задач выпуклого программирования.

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

- минимизировать функцию

(1.1)

- при ограничениях

(1.2)

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

Решение.

Первый шаг. 1. Определение направления спуска . Для отыскания направления спуска решаем следующую задачу линейного программирования:

- минимизировать функцию при ограничениях (1.2).

Решив эту задачу, получим , так что .

2. Определение величины шага . Двигаясь вдоль луча ; , находим минимум функции .

Получаем , так что .

3. Определение новой точки. Новое приближение определяется по формуле .

Второй шаг:

Третий шаг:

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

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

Решение.

Определим область допустимых решений задачи:

а) первое ограничение соответствует окружности с допустимыми решениями внутри и на самой окружности (штриховка на рис. 2);



Рис. 2. Графическое решение задачи выпуклого программирования

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

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

Построим линию уровня, соответствующую целевой функции, и определим направление ее убывания.

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

2. Формулировка задач нелинейного программирования и их классификация

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

Классификация задач проводится по различным признакам.

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

2. Непрерывность функций и их производных (условия гладкости).

3. Наличие локальных экстремумов (многоэкстремальность).

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

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

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

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

В самом общем виде классификация представлена в таблице.

Табл. 1

Вид	Вид функции ограничений	Число переменных	Название задачи
Нелинейная	Отсутствуют	1	Безусловная однопараметрическая оптимизация
Нелинейная	Отсутствуют	Более 1	Безусловная многопараметрическая оптимизация
Нелинейная или линейная	Нелинейные или линейные	Более 1	Условная нелинейная оптимизация

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

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

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

Общая формулировка нелинейных задач:

Найти переменные , удовлетворяющие системе уравнений:

(2.1)

и обращающие в максимум (минимум) целевую функцию:

(2.2)

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

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

Объем производства (выраженный в натуральных или стоимостных единицах) являются функцией затрат производства . Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов ( и ) и от цен этих факторов ( и ). Совокупные издержки выражаются формулой . Требуется при данных издержках определить такое количество факторов производства, которое максимизирует объем продукции .

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

(2.3)

(2.4)

при которых функция:

(2.5)

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

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

Если для всех точек этой окрестности или , то говорят, что функция имеет экстремум в (соответственно максимум или минимум).

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

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

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

.

Следовательно, точки экстремума функции удовлетворяет системе уравнений:

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

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

Двух переменных:

если и , то в точке функция имеет максимум;

если и , то в точке минимум (в этих случаях );

если , то экстремума нет;

если , то вопрос об экстремуме остается открытым.

2.1 Основные понятия и определения

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

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

Определение 2. Линия уровня функции - спроецированная на плоскость переменных сечение графика функции плоскостью .

Рис. 3

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

Пример 1. Построить линию уровня функции , проходящую через точку .

Последовательность действий:

1. Вычислим значение функции в точке .

2. запишем уравнение линии уровня: - это уравнение окружности с центром в точке и радиусом .

3. Построим чертеж линии уровня.

Рис. 4

Определение 3. Градиентом функции многих переменных называется вектор, составленный из первых частных производных функции по всем переменным:

Градиент - это вектор - столбец размерности , где - число переменных функции.

Свойства градиента:

(1) Градиент функции перпендикулярен касательной к линии уровня функции ;

(2) Направление градиента есть направление наиболее быстрого роста функции.

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

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

;

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

;

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

Пример 2. Построить градиент функции в точке .

Последовательность действий:

1. Построим линию уровня функции в точке . Получим , значит, уравнение линии уровня: - это уравнение эллипса с центром в точке .

2. Составим градиент функции.

Получим , следовательно .

3. Вычислим значение частных производных функции в точке :

Следовательно .

4. Построим полученный вектор на координатной плоскости из точки и затем перенесем его в заданную точку .

Рис. 5

Определение 4. Матрицей Гессе называется квадратная матрица, составленная из вторых частных производных функции по всем переменным, матрица имеет размерность , где - число переменных функции:

Определение 5. Собственные числа матриц - это корни характеристического уравнения вида:

Табл. 2. Определение 6

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

Критерий Сильвеста (критерий знакоопределенности матрицы).

Матрица является положительной, если все ее диагональные миноры положительны: отрицательно определенной, если они чередуют знак, начиная с «-».

Здесь диагональные миноры:

Квадратичная функция двух переменных.

Квадратичная функция 2-х переменных имеет вид:

Уравнение линии уровня квадратичной функции имеет вид:

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

- определяющий

2.2 Постановка задачи оптимизации

Постановка задачи оптимизации подразумевает:

1. Формулировку цели, ради которой ставится задача.

2. Определение критерия отбора путей достижения цели.

3. Задание множества путей достижения цели: множества допустимых решений (МДР).

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

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

Цель: Рассчитываемый контейнер должен обладать наибольшим (максимальным) объемом.

Критерий: , где и - неизвестны и должны быть определены.

МДР:, где - известная заданная величина.

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

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

1. Задается целевая функция многих переменных , , определенная на -мерном евклидовом пространстве .

2. Определяется критерий: найти минимальное значение функции, максимальное значение функции, найти значение переменных, при котором функция примет конкретное значение и т.д.

3. Задается МДР: , среди элементов которого осуществляется поиск решения.

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

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

при при .

Определение 2. Точка называется точкой глобального минимума (глобального максимума) на , если:



Рис. 6

На рисунке точки и являются точками локальных минимумов; точка локальный максимум. кроме того, точка является также и глобальным минимумом.

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

Множество точек экстремума может содержать конечное число точек (в том числе и одну), бесконечное число точек или быть пустым.

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

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

.

2.3. Задачи поиска безусловного экстремума ФМП

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

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

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

Теорема о необходимых условиях экстремума 2-го порядка (НУ 2-го порядка). Если точка является точкой безусловного локального минимума (максимума) , и функция дважды непрерывно дифференцируема в ней, то

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

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

Табл. 3

Необходимые условия экстремума	1. Записать градиент функции : 2. Записать необходимые условия безусловного экстремума - составить систему алгебраических уравнений вид: . 3. Найти стационарные точки функции , решив полученную систему. 4. Составить матрицу Гессе . 5. Вычислить матрицу Гессе в точках . 6. Проверить знакоопределенность матрицы для каждой точки: · - - локальный минимум функции (ДУ) · -- локальный максимум функции (ДУ) · - требуется дополнительная проверка на локальный минимум функции (НУ 2-го порядка) · - требуется дополнительная проверка на локальный максимум функции (НУ 2-го порядка) · -в точке нет экстремума.
Достаточные условия экстремума и необходимые условия 2-го порядка

Исследование знакоопределенности матрицы :

· - либо по критерию Сильвестра, либо на основании определения ( все )

· - либо по критерию Сильвестра, либо на основании определения (все )

· - на основании определения (все ), либо из условия, что все главные миноры матрицы неотрицательны.

· - на основании определения (все ),либо из условия, что все главные миноры матрицы неположительны.

· - на основании определения ( разных знаков).

Пример 1.

Дано:

Решение:

1.

2.

3. Решаем систему:

Таким образом получены 2 стационарные точки функции:

4.

5.

6. Исследуем знакоопределенность матриц по критерию Сильвестра:

В точке значит следовательно, - локальный минимум.

В точке значит не выполняются достаточные условия экстремума.

Проверим необходимые условия экстремума 2-го порядка, вычислив собственные числа:

Значит матрица , следовательно, в экстремума нет.

2.4 Прямые методы поиска безусловного экстремума ФМП

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

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

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

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

Определение 2. Последовательность называется сходящейся к точке минимума, если .

Все прямые методы имеют один и тот же алгоритм: , где

· - текущая точка последовательности, причем - задается из физического содержания задачи или произвольно;

· - последующая точка последовательности;

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

· - шаг (число ).

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

Все прямые методы отличаются друг от друга способом задания и выбором .

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

1. Методы первого порядка, использующие информацию о 1-х производных функции .

2. Методы второго порядка, использующие для своей реализации информацию о 1-х и 2-х производных функции .

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

Методы первого порядка

Метод градиентного спуска

Алгоритм метода:

здесь:

· - направление антиградиента функции;

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

Геометрическая интерпретация метода:

Рис. 7

Основной критерий окончания метода:

Построение последовательности заканчивается в точке, для которой:

е, где е- заданное малое положительное число.

Дополнительные критерии окончания метода:

· при выполнении предельного числа итераций:

· при однократном или двукратном одновременном выполнении двух условий: , где - малое положительное число.

Метод градиентного наискорейшего спуска.

Алгоритм метода:

здесь:

· - направление антиградиента функции;

· - шаг вычисляется из условия наибольшего убывания функции в точках последовательности, построенной по закону (2.1):

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

Рис. 8

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



Критерии окончания метода такие же, как и в методе градиентного спуска.

Вычисление шага может быть выполнено тремя способами:

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

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

Способ С. предполагает численное решение задачи методом дихотомии на отрезке с заданной точностью.

Метод покоординатного спуска.

Алгоритм метода:

здесь:

· - проекция на ось антиградиента функции;

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

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



Рис. 9

Критерии окончания метода такие же, как и в методе градиентного спуска.

Метод Гаусса-Зейделя (наискорейшего покоординатного спуска)

Алгоритм метода: .

здесь:

· - проекция на ось антиградиента функции;

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

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



Рис. 10

Критерии окончания метода такие же, как и в методе градиента спуска.

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

Сходимость метода градиентного спуска (градиентного наискорейшего спуска, покоординатного спуска и метода Гаусса-Зейделя) регламентируется теоремой.

Теорема. Если функция ограничена снизу, а ее градиент удовлетворяет условию Липшица:

то метод градиентного спуска гарантирует при .

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

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

Метод сопряженных градиентов (Флетчера - Ривса).

Алгоритм метода:

здесь:

·

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

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

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



Рис. 11

Критерии окончания метода такие же, как и в методе градиентного спуска.

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

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

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

Пример 1.

Дано:

Сделать 2 итерации методом градиентного спуска из начальной точки

Решение:

Найдем градиент функции

Итерация 0 алгоритм (соответствует начальной точке)



Итерация 1 алгоритм

Зададим шаг , тогда:

Вычислим значение функции в точке

Т.к. шаг выбран удачно

Итерация 2 алгоритм

Зададим шаг , тогда:

Вычислим значение функции в точке



Т.к. шаг выбран удачно

Пример 2.

Дано:

Сделать 1 итерацию методом наискорейшего градиентного спуска из начальной точки

Решение:

Итерация 0 алгоритм (соответствует начальной точке) - см. пример 1.

Итерация 1 алгоритма

Способ А вычисления шага .

Вычислим значение функции в точке :

Как видно функция в точке зависит от величины шага , следовательно, можно записать:

Найдем минимум функции :

 - значение шага

- значит, функция принимает минимальное значение.

Окончательно:

;

Способ В вычисления шага :

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

Воспользуемся условием

Окончательно:



Пример 3.

Дано:

Сделать 2 итерации методом покоординатного спуска из начальной точки

Решение:

Итерация 0 алгоритм (соответствует начальной точке) -см. пример 1.

Итерация 1 алгоритма

Для проекции градиента выберем направление оси . Зададим шаг , тогда:

Вычислим значение функции в точке

Т.к. шаг выбран удачно

Итерация 2 алгоритма



Для проекции градиента выберем направление оси . Зададим шаг , тогда:

Вычислим значение функции в точке

Т.к. шаг выбран удачно

Пример 4.

Дано:

Сделать 1 итерацию методом Гаусса - Зейделя из начальной точки

Решение:

Итерация 0 алгоритма (соответствующей начальной точке) - см. пример1.

Итерация 1 алгоритма

Для проекции градиента выбирается направление оси .

Используем способ А. вычисления шага :

Вычислим значение функции в точке:

Как видно функция в точке зависит только от величины шага , следовательно, можно записать:

.

Найдем минимум функции :

- значение шага

-значит, функция принимает минимальное значение

Окончательно:

.

Пример 5.

Дано:

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

Решение:

Итерация 0 алгоритма (соответствует начальной точке) - см. пример 1.

Итерация 1 алгоритма

Результаты итерации совпадают с 1-й итерацией метода наискорейшего градиентного спуска - см. пример 2.

Итерация 2 алгоритма

Используем способ А вычисления шага :

Вычислим значение функции в точке :

Найдем минимум функции :

- значение шага

- значит, функция принимает минимальное значение

Окончательно:

Очевидно, что на 2-й итерации найдены координаты стационарной точки с точностью .

Методы второго порядка

Метод Ньютона

Алгоритм метода:

здесь:

- направление спуска

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

Геометрическая итерация метода для квадратичной функции:



Рис. 12

Критерии окончания метода такие же, как и в методе градиентного спуска.

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

Пример 6

Дано:

Сделать 1 итерацию методом Ньютона из начальной точки

Решение:

Итерация 0 алгоритма (соответствует начальной точке)

Итерация 1 алгоритма

Очевидно, что 1-й итерации найдены координаты стационарной точки.

Задачи нелинейного программирования при ограничениях типа равенств.

Постановка задачи:

Решается задача:

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

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

Пример 1.



Рис. 13

Здесь точка - условный максимум,

точка - условный минимум

Пример 2.



Рис. 14

Здесь точка - условный минимум.

Как видно из чертежа, точки касания обладают следующими свойствами:

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

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

Последовательность графического решения задачи:

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

2. Вычислить точку касания, пользуясь условиями касания.

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

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

Метод исключений.

Допустим, что система ограничений может быть разрешена относительно некоторых переменных:

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

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

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

Алгоритм решения задачи методом исключений:

1. Разрешить систему ограничений относительно любых переменных.

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

3. Решить полученную задачу безусловной оптимизации - найти стационарные точки и проверить достаточные условия .

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

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

Метод множителей Лагранжа (аппарат необходимых и достаточных условий).

Определение 1.

Функция называется классической функцией Лагранжа.

Функция зависит от переменных: штук и штук - называемых множителями Лагранжа.

Определение 2.

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

Определение 3.

Первым дифференциалом ограничения называется функция:

Теорема 1. (о необходимых условиях экстремума). Пусть есть точка локального условного экстремума в задаче (*), и при этом , являются линейно-независимыми, то найдутся такие , что:

· , (условие стационарности функции Лагранжа по )

· , (условие допустимости решения)

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

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

1. Записать классическую функцию Лагранжа:

2. Записать необходимые условия экстремума ФМП при ограничениях типа равенств:

,

3. Решить полученную систему. Решение системы - условно-стационарные точки .

4. Проверить достаточные условия экстремума в каждой точке , для этого

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

Записать дифференциалы ограничений:

В каждой точке

4.1. Вычислить второй дифференциал .

4.2. Записать условия равенства дифференциалов ограничений в каждой точке :

,

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

Определить знак :

· если при , то точка - точка условного локального минимума в задаче;

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

Метод штрафных функции.

Метод штрафных функции относится к численным методам решения задач (*).

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

,

здесь - штрафная функция

- штраф

- штрафной параметр, при решении каждой задачи (3.1) фиксируется.

Функция штрафа конструируется из условия:

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

Обычно, в качестве штрафа используют функцию вида:

.

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

Доказано, что при , последовательность получаемых точек стремится к :

Существует связь между значением параметра штрафа и множителями Лагранжа:

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

Алгоритм аналитического решения задачи методом штрафной функции:

1. Записать штрафную функцию:

2. Записать необходимые условия экстремума для штрафной функции:



3. Найти решение полученной системы: . Решение системы зависит от параметра .

4. Найти условно-стационарную точку в задаче:

.

5. Составить матрицу Гессе для штрафной функции:

6. Исследовать знакоопределенность матрицы при по критерию Сильвестра.

7. Записать оценку множителей Лагранжа:

Рассмотрим решение Примера 2 различными методами:

Дано:

Найдем решение задачи методом исключений:

Решение:

1. Выразим одну из переменных из ограничения:

2. Подставим полученное выражение в функцию:



3. Найдем экстремум полученной функции:

4. Найдем значение оставшейся переменной:

Ответ: получена точка - условный локальный минимум.

Найдем решение задачи методом множителей Лагранжа:

Решение:

1. Запишем функцию Лагранжа:

2. Запишем необходимые условия экстремума

3. Найдем координаты условно-стационарных точек

Получена условно-стационарная точка

4. Установим тип полученной точки с помощью достаточных условий экстремума.

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

Составляем дифференциал ограничения:

В точке имеем: при условии . Значит , тогда получим при , следовательно точка - условный локальный минимум.

Ответ: получена точка - условный локальный минимум.

Найдем решение задачи методом штрафной функции:

Решение:

1. Запишем штрафную функцию:

2. Запишем необходимые условия экстремума

3. Найдем координаты стационарных точек штрафной функции:



Получена условно-стационарная точка

4. Найдем координаты условно-стационарных точек.

,

следовательно получена условно-стационарная точка

5. Составим матрицу Гессе для штрафной функции:

6. По критерию Сильвестра: при

при

значит матрица и точка - условный минимум.

7. Запишем оценку множителя Лагранжа:

Ответ: получена точка - условного локальный минимум.

Методические указания решения задач нелинейного программирования.

Этап №1 Методы безусловной минимизации функции многих переменных

Дано:

Решение:

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

Запишем градиент функции:

Запишем необходимые условия экстремума и вычислим координаты стационарных точек:

Получена стационарная точка функции

Составим матрицу Гессе:

Вычислим матрицу Гессе в полученной стационарной точке:

Определим характер полученной стационарной точки, используя критерий Сильвестра:

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

б) Сделать три итерации методом градиентного спуска из начальной точки в направлении экстремума.

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

Итерация 0

Итерация 1

Вычислим точку по формуле: . Зададим шаг



,

следовательно, шаг выбран удачно

Итерация 2

Вычислим точку по формуле: . Зададим шаг

, следовательно, шаг выбран удачно.

Итерация 3

Вычислим точку по формуле: . Зададим шаг

, следовательно, шаг выбран удачно.

Приведенные вычисления представим в виде таблицы

Табл. 4

№						f
0	0	0	-	20	10	10	22.3607
1	-2	-1	0.1	10	2	-26	10.198
3	-3	-1.2	0.1	5.6	-0.8	-33.92	5.6569
4	-3.56	-1.12	0.1	3.52	-1.6	-36.5696	3.8666

в) Сделать одну итерацию методом наискорейшего спуска из начальной точки в направлении экстремума

Итерация 0. Итерация 0 совпадает с 0-ой итерацией метода градиентного спуска.

Итерация 1.

Вычислим точку по формуле:

.

Вычислим шаг :

Приведённые вычисления представим в виде таблицы

Табл. 5

№						f
0	0	0	-	20	10	10	22.3607
1	-3.5714	-1.7857	0.17857	2.1429	-4.2857	-34.6429	4.7916

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

Итерация 0. Итерация 0 совпадает с 0-ой итерацией метода градиентного спуска.

Итерация 1. Итерация 1 совпадает с 1-й итерацией метода наискорейшего спуска.

Итерация 2.

Вычислим точку по формулам:

Вычислим шаг :

Т.к. в точке градиент функции , то - стационарная точка функции.

Приведенные вычисления представим в виде таблицы

Табл. 6

№						f
0	0	0	-	20	10	10	22.3607
			-	-20	-10
1						f
	-3.5714	-1.7857	0.17857	2.1429	-4.2857	-34.6429	4.7916
			0.04592	-3.0612	3.8265
2						f
	-5	0	0.46666	0	0	-40	0

д) Сделать одну итерацию методом Ньютона из начальной точки в направлении экстремума

Итерация 0. Итерация 0 совпадает с 0-ой итерацией метода градиентного спуска.

Итерация 1.

Вычислим точку по формуле:

Вычислим матрицу обратную к матрице Гессе, вычисленной в точке

Тогда



Т.к. в точке градиент функции , то - стационарная точка функции!

Приведенные вычисления представим в виде таблицы

Табл. 7

№					f
0	0	0	20	10	10	22.3607
1	-5	0	0	0	-40	0

Этап №2 Методы решения ЗНП при ограничениях типа равенства

Дано:

Решение:

Преобразуем ограничение к виду;

а) Решить задачу графически.

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

· точка касания принадлежит ограничен...