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

Оглавление

• 1. Теоретическая часть
• 1.1 Теория математического программирования. Однокритериальная оптимизация. Необходимые и достаточные условия для локальных экстремумов гладких функций
• 1.2 Методы поиска глобального экстремума функции нескольких переменных. Условия Куна-Таккера. Условие Слейтера
• 1.3 Линейное программирование. Угловые точки допустимых множеств
• 1.4 Нелинейное программирование. Постановка общей задачи нелинейного программирования
• 2. Практическая часть
• 2.1 Метод Ньютона
• Список литературы
• 1. Теоретическая часть

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

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

.

1. Понятия локального и глобального экстремумов. Точка называется точкой локального минимума функции f(x), если , где - окрестность точки .

Точка называется точкой глобального минимума функции f(x), если .

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

. (1.1)

Теорема 1.1. (Необходимое условие 1 порядка). Пусть - точка минимума f(x), , и f(x) дифференцируема в , тогда выполняется условие стационарности (1.1).

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

Не всякая из точек, удовлетворяющих (1.1), является точкой минимума.

Теорема 1.2. (Достаточное условие 1-го порядка). Пусть f(x) - выпуклая функция, дифференцируемая в точке , и выполнено условие (1.1). Тогда - точка глобального минимума f (x) на.

Доказательство следует из

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

Тогда .

Теорема 1.4. (Достаточное условие 2-го порядка). Пусть в точке функция f(x) дважды дифференцируема, выполнено условие (1.1) и . Тогда точка - точка локального минимума.

Теорема 1.5. (Существование решения). Пусть f(x) непрерывна на и множество для некоторого A не пусто и ограниченно. Тогда существует точка глобального минимума на.

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

Теорема 1.7. Точка минимума сильно выпуклой функции существует и единственна.

Основные теоремы дифференциального исчисления: Теорема Ферма (необходимое условие экстремума для гладких функций)

Пусть f(x) функция, заданная на закрытом интервале [ a, b ], дифференцируемая на открытом (a, b) такая что в точке С выполнено: является точкой экстремума, т.е. точкой максимума или минимума. Тогда в точке С производная равна нулю.

Док-во: Пусть С -- точка максимума, т.е. аналогично С точка минимума, т.е. , тогда . Оценим при х > С и 0 при . Тогда, переходя к пределу, при х>С получим , а это возможно только если f''(C) = 0. Замечание: Теорему Ферма можно рассматривать как теорему о необходимых условиях экстремума функции на открытом интервале.

1.2 Методы поиска глобального экстремума функции нескольких переменных. Условия Куна-Таккера. Условие Слейтера

Метод множителей Лагранжа можно использовать при построении критериев оптимальности для задач с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств. Рассмотрим следующую общую задачу нелинейного программирования:

Минимизировать f(x) при ограничениях:

где x = x1,x2, x3,…, xn.

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

Кун и Таккер построили необходимые и достаточные условия оптимальности для задач нелинейного программирования, исходя из предположения о дифференцируемости функций f, gj, hk. Итак, задача Куна - Таккера состоит в том, чтобы найти векторы, удовлетворяющие следующим условиям:

Прежде всего, проиллюстрируем условия Куна-Таккера на примере.

Минимизировать при ограничениях:

Записав данную задачу в виде задачи линейного программирования, можно получить:

Уравнение (1), входящее в состав условий Куна-Таккерапринимает следующий вид:

откуда

Неравенства (2) и уравнения (3) задачи Куна-Таккера в данном случае записывается в виде:

Уравнения (4), известные как условие дополняющейнежесткости, принимают вид:

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

Условие регулярности Слейтера

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

Важнейшим из них является так называемое условие регулярности Слейтера:

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

,

т. е. является внутренней точкой относительно ограничения gi(x). Поэтому данное условие также называют условием телесности.

Вообще говоря, существуют разные варианты необходимого условия Куна--Таккера. Приведем один из них.

Если (D, f) является задачей выпуклого программирования с решением х, ее целевая функция f(x) и функции ограничений gi(x) -- дифференцируемы, нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор u ? 0, что (х,u) -- седловая точка функции Лагранжа Ф(х,u).

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

Определим F(x) как функцию, ставящую в соответствие каждому значению х минимальное значение функции Ф(х,u) по u:

и по аналогии

Рассмотрим задачу отыскания максимума функции F(x)

и задачу минимизации G(u)

Очевидно, что

Отсюда следует, что максимум F(x) находится в допустимой области D и совпадает с максимумом целевой функции f(x) задачи (1):

Таким образом, задача (2), в определенном смысле, равносильна (1). Аналогичные выводы могут быть получены и для (3). Задачи (2) и (3) образуют двойственную пару. Как нетрудно догадаться, данное отношение является обобщением отношения двойственности для задач линейного программирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых х?Х, u?0.



Условие (4) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений {х(q)} и {u(q)}, то с помощью неравенств вида

можно определить момент остановки вычислительной процедуры.

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

1.3 Линейное программирование. Угловые точки допустимых множеств.

Определение 1. Задача, в которой требуется минимизировать (или максимизировать) линейную форму

при условии, что , ,

или , , и , ,

называется задачей линейного программирования в произвольной форме записи.

Определение 2. Задача в матричной форме вида

(1)

называется симметричной формой записи задачи линейного программирования.

Определение 3. Задача линейного программирования вида

(2)

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

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

Если система ограничений задана в форме ,

то можно, введя дополнительные переменные, привести ее к виду

, , , где .

Если же ограничения в задаче заданы в форме ,то

, , .

Рассмотрим задачу с ограничениями . Эту систему ограничений можно представить в виде системы

.

Введем следующие обозначения:

,,…,, ,…,,

.

Тогда задачу линейного программирования можно записать в виде:

, .

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

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

Определение 4.Набор чисел , удовлетворяющий ограничениям задачи линейного программирования называется ее планом.

Определение 5. Решением задачи линейного программирования называется ее план, минимизирующий (или максимизирующий) линейную форму.

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

. (3)

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

Умножим (3) на слева

, (4)

и найдем отсюда :

. (5)

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

Если положить , то

. (6)

Решение (6) называют базисным решением системы из уравнений с неизвестными.

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

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

Если среди компонент нет нулевых, то базисное допустимое решение называется невырожденным.

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

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

Теорема 1: (основная теорема линейного программирования):

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

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

Доказательство: Доказательство теоремы основано на следующей лемме.

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

1)Пусть - некоторая внутренняя точка. Многогранник ограниченный замкнутый, имеет конечное число угловых точек. - допустимое множество.

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

, , .

Так как функция линейна, то

. (*)

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

.

Подставим данное значение функции в линейную форму (*) вместо и получим:

.

Так как - оптимальная точка, то получили противоречие: (!). Следовательно, , - угловая точка.

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

, и ,

то .

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

экстремум функция нелинейный программирование

1.4 Нелинейное программирование. Постановка общей задачи нелинейного программирования

Нелинейное программирование (NLP, англ. NonLinearProgramming) -- случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x1, х2,..., xn) на множестве D, определяемом системой ограничений

где хотя бы одна из функций f или gi является нелинейной.

По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f) и кратко может быть записана в следующем виде

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

Как и в ЗЛП, вектор х* = (x1*,x2*,...,xn*) D называется допустимым планом, а если для любого x D выполняется неравенство f(x*) ? f(x), то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.

С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а gi(х) ? 0 как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП (аiх - bi ? 0).

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

или запись условий дискретности множеств:

Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:

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

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

1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).

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

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

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

2. Практическая часть

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

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

Чтобы численно решить уравнение f(x)=0 методом простой итерации, его необходимо привести к следующей форме: , где -- сжимающее отображение.

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

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция определяется выражением:

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

По теореме Банаха последовательность приближений стремится к корню уравнения .

Рис. 2. - Иллюстрация метода Ньютона (синим изображена функция f(x), нуль которой необходимо найти, красным -- касательная в точке очередного приближения xn).

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

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

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

где -- угол наклона касательной в точке xn.

Следовательно искомое выражение для xn+1 имеет вид:

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

Алгоритм

Задается начальное приближение x0.

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

.

Задача: Методом Ньютона вычислить минимум функции двух переменных.

Алгоритм: Пусть (x0, y0) - начальное приближение для точки минимума. Очередное приближение вычисляется по формуле:

где ѓ'(x), ѓ'(y) - производные функции ѓ(x, y) по xи по y, а hi, j - элементы матрицы Гессе (матрицы вторых производных):

h1,1 = ѓxx h1,2 = h2,1 = ѓxy h2,2 = ѓyy

В покомпонентном виде приведенная выше формула имеет вид:

xk+1 = xk - (h2,2 * ѓ'(xk)- h1,2 * ѓ'(yk)) / det(h)

yk+1 = yk - (- h2,1 * ѓ'(xk) + h1,1 * ѓ'(yk)) / det(h)

где det(h) - определитель матрицы h.

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

Контрольный пример

Начальная точка (4, -1, 2).

Рис. 2. - График функции

Табл. 1. - Значения x, yи z, а также числителей и детерминанта для вычисления этих значений

X	y	z	h33 * dx	h22 * dy	h11 * dz	det(h)
4	-1	2	48	-16	112	32
2,5	-0,5	-1,5	24	-14	56
1,75	-0,0625	-3,25	12	-12,25	28
1,375	0,320313	-4,125	6	-10,7188	14
1,1875	0,655273	-4,5625	3	-9,37891	7
1,09375	0,948364	-4,78125	1,5	-8,20654	3,5
1,046875	1,204819	-4,89063	0,75	-7,18073	1,75
1,023438	1,429216	-4,94531	0,375	-6,28313	0,875
1,011719	1,625564	-4,97266	0,1875	-5,49774	0,4375
1,005859	1,797369	-4,98633	0,09375	-4,81052	0,21875
1,00293	1,947698	-4,99316	0,046875	-4,20921	0,109375
1,001465	2,079235	-4,99658	0,023438	-3,68306	0,054688
1,000732	2,194331	-4,99829	0,011719	-3,22268	0,027344
1,000366	2,29504	-4,99915	0,005859	-2,81984	0,013672
1,000183	2,38316	-4,99957	0,00293	-2,46736	0,006836
1,000092	2,460265	-4,99979	0,001465	-2,15894	0,003418
1,000046	2,527732	-4,99989	0,000732	-1,88907	0,001709
1,000023	2,586765	-4,99995	0,000366	-1,65294	0,000854
1,000011	2,63842	-4,99997	0,000183	-1,44632	0,000427
1,000006	2,683617	-4,99999	9,16E-05	-1,26553	0,000214
1,000003	2,723165	-4,99999	4,58E-05	-1,10734	0,000107
1,000001	2,757769	-5	2,29E-05	-0,96892	5,34E-05
1,000001	2,788048	-5	1,14E-05	-0,84781	2,67E-05

Рис. 3. - График сходимости при начальной точке (4, -1, 2)



Рис. 4. - График сходимости при начальной точке (0, 2, -4)

Рис. 5. - График сходимости при точности 0.1

Рис. 6. - График сходимости при точности 0.01

Функция для исследования:

Рис. 7. - График функции

Табл. 2. - Значения x, yи z, а также производных и детерминанта для вычисления этих значений

x	Y	h11	h12	h22	f(x,y)dx	f(x,y)dy	det(h)
5	-1	30,45623	-12,1825	24,36499	48,72998	-24,365	593,6526
3,5	-0,75	11,59912	-4,31595	11,50921	17,44364	-8,6319	114,8692
2,076577	-0,53378	4,491822	-1,50761	5,648757	6,159265	-3,01521	23,10033
0,767226	-0,34946	1,793873	-0,51285	2,935155	2,120168	-1,0257	5,002276
-0,37165	-0,19899	0,761482	-0,16525	1,660835	0,692546	-0,3305	1,237389
-1,25706	-0,08809	0,366789	-0,04699	1,066751	0,200203	-0,09398	0,389065
-1,79463	-0,02368	0,224818	-0,00965	0,815325	0,041975	-0,01931	0,183207
-1,98041	-0,0022	0,187569	-0,00082	0,742999	0,003639	-0,00163	0,139363
-1,99981	-2,1E-05	0,183976	-7,8E-06	0,735831	3,58E-05	-1,6E-05	0,135375
-2	-2,1E-09	0,18394	-7,6E-10	0,735759	3,57E-09	-1,5E-09	0,135335
-2	-2E-17	0,18394	-7,4E-18	0,735759	0	-1,5E-17	0,135335
-2	0	0,18394	0	0,735759	0	0	0,135335

Список литературы

1) Монографии, изданные в издательстве Российской Академии Естествознания [Электронный ресурс]. Режим доступа: http://www.rae.ru/monographs/57-2327

2) Планирование решений в экономике. Условие регулярности Слейтера[Электронный ресурс]. Режим доступа: http://ecosyn.ru/page0130.html

3) Бельков В.Н., Ланшаков В.Л. Автоматизированное проектирование технических систем: Учебное пособие-Москва: Академия Естествознания, 2009.

4) Акулич И. Л. Математическое программирование в примерах и задачах: Учеб.пособие для студентов эконом. спец. вузов. -- М.: Высш. шк., 1986.http://cyberfac.ru/publ/matematicheskie_metody_v_ehkonomike/kanonicheskaja_postanovka_zadachi_linejnogo_programmirovanija/45-1-0-1431

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