Модели и методы конечномерной оптимизации

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

Содержание

1. Одномерная оптимизация. Метод «золотого сечения»

2. Условная нелинейная оптимизация. Применение теоремы Джона-Куна-Таккера

3. Линейное программирование. Симплекс-метод

4. Исследование множества на выпуклость

5. Исследование функции на выпуклость

6. Исследование функции на овражность

7. Безусловная оптимизация неквадратичной функции овражной структуры. Метод Дэвидона-Флетчера-Пауэлла

8. Сведение задачи условной оптимизации к безусловной задаче оптимизации

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

8.2 Метод возможных направлений Зойтендейка

9. Вывод

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

11. Приложения

1. Одномерная оптимизация. Метод «золотого сечения»

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

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

Теоретические сведения:

Определение 1.1

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

Определение 1.2

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

Здесь - норма вектора в конечном n-мерном евклидовом пространстве.

Теорема 1.1 (необходимые условия экстремума первого порядка)

Пусть есть точка локального минимума (максимума) функции на множестве и дифференцируема в точке . Тогда аргумент функции в точке равен нулю, т.е.



или

Теорема 1.2 (достаточные условия экстремума первого порядка)

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

и

, тогда точка есть точка локального минимума (максимума) функции на множестве .

Решение:

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

(1)

что соответствует формуле площади поверхности закрытого цилиндра с параметрами радиуса r и высоты h.

Т.к. в задаче указано, что у бака фиксированный объем, то можно записать уравнение связи между параметрами бака, т.е.:

(2)

Уравнение (2) дает возможность свести задачу минимизации целевой функции от двух параметров к одномерной минимизации целевой функции одного параметра, например:

(3)

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

(4)

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

С учетом уравнения связи (2) получаем решение:

(5)

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

(6)

Программная реализация данной задачи методом «золотого сечения» находится в приложении 11.1.

Метод «золотого сечения»:

«Золотым сечением» отрезка называется такое разбиение отрезка на две неравные части, что отношение длины всего отрезка к длине большей части равно отношению длины большей части к длине меньшей части отрезка.

«Золотое сечение» отрезка осуществляется каждой из двух симметрично расположенных относительно центра отрезка точек:

Алгоритм:

(шаг 1)Находим точки, осуществляющие «золотое сечение» отрезка из системы:

, где

(шаг 2) Сравниваем значения функций в точках «золотого сечения»

-Если

-Если

(шаг 3) Проверяем условие остановки алгоритма

, если не выполняется, переходим на (шаг 1),

иначе вычисляем точку минимума

2. Условная нелинейная оптимизация. Применение теоремы Джона-Куна-Таккера

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

Требуется решить задачу вида:

Теоретические сведения:

Определение 2.1

Обобщенной функцией Лагранжа называется функция вида:

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

Определение 2.2

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

Определение 2.3

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

Определение 2.4

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

Определение 2.5

Ограничение называется активным в точке , если . Если , то ограничение называется пассивным.

Определение 2.6

Градиенты ограничений являются линейно независимыми в точке , если равенство

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

Определение 2.7

Точка называется регулярной точкой минимума (максимума), если градиенты ограничений являются линейно независимыми (), иначе точка называется нерегулярной точкой минимума (максимума).

Теорема 2.1 (Джона-Куна-Таккера) (необходимые условия минимума (максимума) первого порядка)

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

а) Условие нетривиальности:

б) Условие стационарности обобщенной функции Лагранжа:

в) Условие допустимости решения:

г) Условие согласования знаков:

д) Условие дополняющей нежесткости:

Теорема 2.2(достаточные условия минимума (максимума) первого порядка)

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

Теорема 2.3(достаточное условие экстремума второго порядка)

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

Если в этой точке для всех ненулевых таких, что

То точка является точкой локального минимума (максимума) в данной задаче.

Замечание 2.1

Если функции выпуклые, то условия теоремы 2.1 являются одновременно и достаточными условиями глобального минимума

Определение 2.8

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

Решение:

Перепишем условие



(ШАГ 1)

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

(ШАГ 2)

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

а) Условие нетривиальности:

б) Условие стационарности обобщенной функции Лагранжа:

или

в) Условие допустимости решения:

г) Условие согласования знаков:

д) Условие дополняющей нежесткости:

(ШАГ 3)

Решаем систему

для двух случаев:

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

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

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

Из второго уравнения получаем, что , что не удовлетворяет условию нетривиальности решения.

Система перепишется как:

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

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



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

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

Из первых двух уравнений получаем:

Полученную точку следует проверить на выполнение условий, записанных на (шаге 2).

Условия выполняются. Активное ограничение: . Пассивное ограничение: .

Из системы получаем:



Полученные точки проверяем на выполнение условий, записанных на (шаге 2).

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

Из системы получаем:

Для полученного множителя Лагранжа находим точку:

Проверяем необходимые условия минимума на (шаге 2).

Условия не выполняются, т.к. , что удовлетворяет точке условного максимума. Активное ограничение: . Пассивное ограничение: .

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

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

(ШАГ 4)

Для получено на (шаге 3) точки проверяем достаточные условия минимума первого порядка теорема 2.2.

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

теорема 2.3.

Запишем второй дифференциал обобщенной функции Лагранжа с учетом :

или

Видно, что второй дифференциал функции Лагранжа положителен, т.е.:

По теореме 2.4 заключаем, что точка есть точка условного локального минимума.

Докажем выпуклость функции :

Построим график целевой функции с помощью среды MathCAD 14.

И его линии уровня:



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

(ШАГ 5)

Перепишем целевую функцию:

Ее значение в точке - глобального минимума есть

3. Линейное программирование. Симплекс-метод

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

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

Теоретические сведения:

Стандартный симплекс-метод:

Целевая функция и ее ограничения имеют вид:

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

Определение 3.1

Частное решение соответствующее нулевым свободным (небазисным) переменным, т.е. , называется базисным решением и записывается как:

Определение 3.2

Если все - то решение допустимое базисное

Определение 3.3

Решение задачи представимо в виде , где

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

1) Если , то - оптимальное решение

2) Если , то задача не имеет решения

3) Если , то

Шаги симплекс-метода:

1) Проверка на оптимальность и разрешимость

2) Выбор ведущего столбца (для задачи на минимум)

3) Выбор ведущей строки по симплексному отношению , где r-ведущая строка,

s- ведущий столбец.

4) Построение более предпочтительного вида (переход к другому базису): -

-Удаляем переменную из других ограничений, используя метод Жордана-Гаусса, и пере ходим к 1)

Двухэтапный симплекс-метод:

Искусственные переменные вводятся как:

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

Этапы:

1) Нахождение вспомогательного решения

2)Нахождение основного решения

Решение:

Этап 1:

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

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



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

Составляем таблицу и выбираем ведущий столбец и строку по и минимальному симплексному отношению :

БП	x1	x2	x3	x4	x5	x6	x7	x8	ПЧ	СО
x5	-1	3	1	10	1	0	0	0	25	5/2
x8	2	1	1	<5>	0	1	0	1	10	2
x7	10	2	2	-5	0	0	1	0	26	-26/5
	2	1	1	5	0	1	0	0	10	-

Обнуляем все элементы столбца, кроме разрешающего коэффициента:

БП	x1	x2	x3	x4	x5	x6	x7	x8	ПЧ	СО
x5	-5	1	-1	0	1	-2	0	-2	5	-
x4	2/5	1/5	1/5	1	0	1/5	0	1/5	2	-
x7	12	3	3	0	0	1	1	1	36	-
	0	0	0	0	0	0	0	-1	0	-

Полагаем, что свободные переменные равны нулю, тогда решение:

Сделаем проверку:



Подставим точку в ограничения.

Ограничения выполняются:

Этап 2:

Решаем основную задачу:

Выделим базисные переменные и уберем их из целевой функции:

Тогда целевая функция примет вид:

Записываем симплекс-таблицу и повторяем тот же алгоритм:

БП	x1	x2	x3	x4	x5	x6	x7	ПЧ	СО
x5	-5	1	-1	0	1	-2	0	5	-1
x4	2/5	1/5	1/5	1	0	1/5	0	2	5
x7	12	3	3	0	0	1	1	36	3
	2	-1	-8	0	0	-3	0	-30	-

БП	x1	x2	x3	x4	x5	x6	x7	ПЧ	СО
x5	0	9/4	1/4	0	1	-19/12	5/12	20	-
x4	0	1/10	1/10	1	0	1/6	-1/30	4/5	-
x1	1	1/4	1/4	0	0	1/12	1/12	3	-
	0	-3/2	-17/2	0	0	-19/6	-1/6	-36	-

Получаем решение:

Сделаем проверку:

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



Т.о. найдено допустимое базисное решение исходной задачи.

4. Исследование множества на выпуклость

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

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

Теоретические сведения:

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

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

Графически это выглядит так:

Математически данное свойство выражается, как:

Данных сведений достаточно, что бы решить поставленную задачу.

Решение:

Пусть произвольная системы линейных уравнений и неравенств имеет вид:



Это ее матричная запись., которая является более удобной.

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

Тогда два решения этой системы можно записать так:

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

Объединяя две системы, получим:

В силу дистрибутивности свойств умножения матриц уравнение переписывается в виде:

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

Отсюда следует выпуклость множества Х - решений произвольной системы линейных уравнений и неравенств.

5. Исследование функции на выпуклость

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

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

Теоретические сведения:

Определение 5.1

Функция где - выпуклое множество, называется выпуклой функцией на этом множестве, если

Теорема 5.1

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

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

не убывает на множестве .

Теорема 5.2

Пусть функция дифференцируема на интервале и , при всех .

Тогда возрастает на . Если же при всех , то не убывает на .

Аналогично, если , при всех , то убывает на , а если , при всех , то не возрастает на .

Теорема 5.3

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

Замечание 5.1

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

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

Теорема 5.4

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

Решение:

Согласно теореме 5.4, если функция выпуклая и имеет вторую производную,то: при всех .

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



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

Тогда их произведение будет положительно :

Производная произведения не убывает :

6. Исследование функции на овражность

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

Требуется исследовать на овражность функцию :

Теоретические сведения:

Определение 6.1

Матрицей Гессе дважды дифференцируемой в точке функции называется матрица частных

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

Определение 6.2

Собственные значения матрицы размера находятся как корни характеристического уравнения (алгебраического уравнения n-й степени):

Определение 6.3

Пусть ограниченная снизу функция:

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

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

В этом случае поверхности уровня имеют структуру, сильно отличающуюся от сферической.

Такие функции называются овражными.

Определение 6.4

Степень овражности характеризуется числом:

Обычно при k>10 функция приобретает овражную структуру.

Определение 6.5

Если собственные значения матрицы Гессе удовлетворяют неравенствам:

а отношение:

невелико ,то число называется размерностью оврага.

Решение:

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

Найдем собственные значения матрицы Гессе:

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

График функции и линии уровней построим в среде MathCAD 14

Линии уровней:

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

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

Метод Дэвидона-Флетчера-Пауэлла

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

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

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

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

Метод Давидона - Флетчера - Пауэла.

Первоначально метод был предложен Дэвидоном (Davidon [1959] ), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963] ). Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj f(y). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj , где Dj - положительно определенная симметрическая матрица порядка n х n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

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

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

1) Ввод начальных данных с клавиатуры:

2) Проверка условия:

А) Если утверждение верно, то 5);

Б) Если утверждение ложно, то 3).

3) Нахождение значения :

Где

4) Переопределение значений:

Увеличиваем счетчик итераций и переходим к Шаг2);

5) Минимум найден:

Решение задачи

График и линии уровня заданной функции представлены на рисунках:

Рис.7.1

Функция определена при:

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

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

Результат работы программы:

Рис. 4.3

- начальная точка

Программа нашла минимум исходной функции за 2 итерации.

Значение функции 1.90263 1.903.

Выполним проверку при помощи пакета Mathcad 14:

8. Сведение задачи условной оптимизации к безусловной задаче оптимизации.

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

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

Требуется найти решение задачи:

Теоретические сведения:

Задача условной оптимизации:

Этот метод основан на сведении к последовательности задач, минимизации дополнительной функции:

- штрафная функция, зависящая от двух параметров,

- параметр штрафа.

С ростом номера k , штраф за невыполнение ограничений увеличивается



Штрафная функция записывается в виде:

- квадрат срезки (для ограничений типа неравенств).

- квадратичная функция.

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

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

Теорема 8.2.1 (о сходимости метода штрафных функций)

Пусть - точка локального минимума задачи условной минимизации

- непрерывные, дифференцируемые функции в окрестности точки .

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

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

Шаг№1

Задается начальное приближение , начальный штраф , его обычно берут равным {0,01;0,1;1}.

Задается некоторая константа для увеличения .

Задается точность .

Шаг№2

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

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

Шаг№3

Проверка условия окончания поиска:

а) если ,то в качестве оптимальной точки выбираем .

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

, k=k+1 => Шаг№1.

Результат работы программы:

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

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



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



8.2 Метод возможных направлений Зойтендейка

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

Требуется найти решение задачи:

В общем виде она выглядит так:

Стратегия поиска:

Метод основан на построении последовательности точек , таких, что .

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

- Выбор направления осуществляется следующим образом:

1)

2)

А) Вектор направляется внутрь области

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

Определим множество индексов:

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

-Шаг определяется как:

Алгоритм:

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

2) Определяем элементы множеств ,

3) Если ,

иначе:

4) Если , то завершаем, иначе 5)

5) Определяем шаг и находим следующую точку

Решение:

Итерация 0:

1) Выбираем точку ,которая принадлежит допустимому множеству

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

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

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

4) Теперь определяем шаг:



Находим градиенты ограничений:

Так как , то

Получаем, что до следующей точки равен

5) Получаем следующую точку:

Итерация 1:



Вычислим градиент в этой точке:

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

2) Для нахождения возможного направления составляем экстремальную задачу:

Преобразуем задачу к необходимому виду:

Решаем задачу симплекс-методом:

Выбираем максимальную положительную оценку и минимальное неотрицательное симплексное отношение:

				u1	u2	ПЧ
2	-2	3	-3	1	0	0
1	1	1	1	0	1	1
2/7	-2/7	1	-1	0	0	0
				u1	u2	ПЧ
2/3	-2/3	1	-1	1/3	0	0
1/3	5/3	0	2	-1/3	1	1
-8/21	8/21	0	0	-1/3	0	0
				u1	u2	ПЧ
4/5	0	1	-1/5	1/5	2/5	2/5
1/5	1	0	6/5	-1/5	3/5	3/5
-48/105	0	0	-16/35	-9/35	-8/35	-8/35

Получаем направление:

3) Теперь найдем шаг:



Получаем, что шаг:

4) Получаем следующую точку:

Итерация 2:

1) Выбираем начальной точкой точку:



Вычисляем градиент:

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

3) Находим направление :

Составляем экстремальную задачу.

Преобразуем к виду:

Решим симплекс-методом. Составляем таблицу

				u1	u2	ПЧ
2	-2	3	-3	1	0	0
1	1	1	1	0	1	1
2	-2	1	-1	0	0	0
				u1	u2	ПЧ
1	-1	3/2	-3/2	1/2	0	0
0	2	-1/2	5/2	-1/2	1	1
0	0	-2	2	-1	0	0
				u1	u2	ПЧ
1	1/5	6/5	0	1/5	3/5	3/5
0	4/5	-1/5	1	-1/5	2/5	2/5
0	-8/5	-8/5	0	-3/5	-4/5	-4/5

Получаем направление:

4) Находим шаг:



Получаем шаг:

5) Следующая точка:

Итерация 3:

1) Берем точку с прошлой итерации:

Вычисляем градиент:



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

3) Находим направление:

Составляем таблицу

				u1	u2	ПЧ
2	-2	3	-3	1	0	0
1	1	1	1	0	1	1
2/3	-2/3	1	-1	0	0	0
				u1	u2	ПЧ
2/3	-2/3	1	-1	1/3	0	0
1/3	5/3	0	2	-1/3	1	1
0	0	0	0	-1/3	0	0

Получаем, что следовательно, т.к. свободные переменные, равные нулю, то направление:

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

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

9. Вывод

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

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

- Условной и безусловной оптимизации:

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

Задачи условной минимизации решались:

1) С применением теоремы Джона-Куна-Таккера

2) Методом возможных направлений Зойтендейка

3) Методом внешних штрафных функций (программная реализация; использовался метод Дэвидона-Флетчера-Пауэлла)

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

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

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

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

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

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

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

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

оптимизация нелинейный функция

1.Пантилеев А.В., Летова Т.А., «Методы оптимизации в примерах и задачах», «Высшая школа», 2002 г.

2.Лутманов С.В., «Курс лекций по методам оптимизации», 2001

3.Ларичев О.И., Горвиц Г.Г., «Методы поиска локального экстремума овражных функций», «Наука», 1990

4.Амосов А.А., Дубинский Ю.А., Копченова Н.В., «Вычислительные методы для инженеров», «Высшая школа», 1994

5.Бушуев А.Ю., Кутыркин В.А., Мозжорина Т.Ю., Тимофеев В.Н., «Введение в оптимизацию» «МГТУ им. Н.Э.Баумана», 2008

11.Приложения

Одномерный поиск. Метод «золотого сечения».

Описание программы:

Задача состоит в минимизации затрат на производство закрытого цилиндрического бака, при заданном объеме V;

-В программе производится минимизация функции одного аргумента S(R)=2*PI*r^2+2*V/r;

-При выполнении программы вводится значение объема V;

-Решением задачи является пара чисел (Rmin;Hmin);

-Высота H находится по формуле H=V/(PI*r^2);

-Используется метод «золотого сечения» .

Программа написана в среде Microsoft Visual Studio 2010.

Листинг

#include <iostream>;

#include <math.h>;

using namespace std;

void main()

{

//Повторить программу или нет

char chose[4]="no";

//Включаем вывод русских символов в консоль;

setlocale(LC_ALL,"Russian");

//Число PI;

const double pi=3.1416;

//Инициализация границ отрезка локализации минимума, т.е. два значения радиуса [R1;R2] в милиметрах;

double R1=0, R2=100000;

//Константы золотого сечения;

double const1=0.381966, const2=0.618033;

//Точки, осуществляющие золотое сечение;

double alfa=0, bett=0;

//Значения функции для двух точек золотого сечения(нужны для сравнения);

double S1=0,S2=0;

//Точность,объем, минимальный радиус и соответствующая ему высота;

double eps=0,V=0,Rmin=0,Hmin=0;

{

cout<<"В программе производится минимизация функции одного аргумента:"<<endl;

cout<<"S(r)=2*PI*r^2+2V/r;"<<endl;

cout<<"При выполнении программы вводится значение объема V;"<<endl;

cout<<"Решением задачи является пара чисел (r*;H*);"<<endl<<endl; loop:

cout<<"Введите объем V:\t";

cin>>V;

cout<<"Задайте точность eps:\t";

cin>>eps;

cout<<endl;

}

//Вычисляем начальные точки золотого сечения;

{

alfa=R1+const1*(R2-R1);

bett=R1+const2*(R2-R1);

}

//Далее следует реализация метода;

while(const2*(R2-R1)>=eps) {

S1=2*(pi*pow(alfa,2)+V/alfa);

S2=2*(pi*pow(bett,2)+V/bett);

//Т.к. функция унитарна, изменяем границы отрезка локализации минимума;

if (S1>S2){

R1=alfa;

alfa=bett;

bett=R1+const2*(R2-R1);

}

else {

R2=bett;

bett=alfa;

alfa=R1+const1*(R2-R1);

}

};

//Обработка конечных данных;

{

//Далее сравниваются два значения S1 S2;

S1=2*(pi*pow(R1,2)+V/R1);

S2=2*(pi*pow(R2,2)+V/R2);

if (S1>S2)

Rmin=alfa;

else

Rmin=bett;

//Минимальная высота: H=V/(pi*R^2);

Hmin=V/(pi*pow(Rmin,2));

}

//Вывод ответа;

cout<<"Решением задачи в виде (Rmin;Hmin): ("<<Rmin<<";"<<Hmin<<")"<<endl<<endl;

//Закольцовка

{

cout<<"Запустить заново?"<<endl;

cout<<"1. yes"<<endl;

cout<<"2. no"<<endl;

cout<<"Выбор:\t";

cin>>chose;

cout<<endl<<endl;

if (chose[0]=='y'&&chose[1]=='e'&&chose[2]=='s') {goto loop;}

}

}

Многомерный поиск минимума функций и добавленный метод внешних штрафных функций. Метод Дэвидона-Флетчера-Пауэлла.

Описание программы:

Программа реализует метод Дэвидона-Флетчера-Пауэлла. Находится минимум функций двух переменных.

В меню программы можно выбрать ход программы, а именно:

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

2. Запуск поиска минимума неквадратичной функции овражной структуры, овражность которой усиливается при увеличении значений переменных . (См. раздел 7)

3. Запуск поиска минимума задачи на условный минимум квадратичной функции. Реализуется метод внешних штрафов с применение метода многомерного поиска минимума Дэвидона-Флетчера-Пауэлла.

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

Программа написана в среде Microsoft Visual Studio 2010.

Листинг:

#include <iostream>;

#include <math.h>;

using namespace std;

//размерность Евклидова пространства

const int n=2;

//создание нестандартных наименований типов

typedef int counters;

typedef int number_of_iteration;

typedef double step;

typedef double fine;

typedef double accuracy;

typedef double norm_gradient;

typedef double point [n];

typedef double difference_of_points [n];

typedef double gradient [n];

typedef double difference_of_grad [n];

typedef double direction [n];

typedef double matrix [n][n];

typedef double Hessian_matrix [n][n];

typedef double Determ_Hess_matr;

double phi(fine p,point x)

{

double g1=0,g2=0;

g1=2*x[0]+3*x[1]-6;

g2=2*x[0]+x[1]-4;

return (p*0.125)*( (abs(g1)+g1)*(abs(g1)+g1)+(abs(g2)+g2)*(abs(g2)+g2) );

}

double f(char var,fine p,point &x)

{

if (var=='1') return x[0]*x[0]-3*x[0]*x[1]+10*x[1]*x[1]+5*x[0]-3*x[1];

if (var=='2') return sqrt(1+2*x[0]+x[1]*x[1])+exp(x[0]*x[0]+2*x[1]*x[1])-x[0]-x[1];

if (var=='3') return x[0]*x[0]-2*x[0]-x[1]+phi(p,x);

}

double psy(char var,fine p,step s,point &x, direction &d)

{

double sum1=0,sum2=0,sum3=0;

double g1=0,g2=0;

if (var=='1')

{

sum1=d[0]*d[0]-3*d[0]*d[1]+10*d[1]*d[1];

sum2=2*x[0]*d[0]-3*x[1]*d[0]-3*x[0]*d[1]+20*x[1]*d[1]+5*d[0]-3*d[1];

sum3=x[0]*x[0]-3*x[0]*x[1]+10*x[1]*x[1]+5*x[0]-3*x[1];

return s*s*sum1+s*sum2+sum3;

}

if (var=='2')

{

sum1=sqrt( (1+2*x[0]+x[1]*x[1]) + 2*s*(d[0]+x[1]*d[1]) + s*s*(d[1]*d[1]) );

sum2=exp( (x[0]*x[0]+2*x[1]*x[1])+2*s*(x[0]*d[0]+2*x[1]*d[1])+s*s*(d[0]*d[0]+2*d[1]*d[1]) );

sum3=x[0]+x[1]+s*(d[0]+d[1]);

return sum1+sum2-sum3;

}

if (var=='3')

{

g1=2*x[0]+3*x[1]+s*(2*d[0]+3*d[1])-6;

g2=2*x[0]+x[1]+s*(2*d[0]+d[1])-4;

sum1=2*x[0]*d[0]-2*d[0]-d[1];

sum2=x[0]*x[0]-2*x[0]-x[1];

sum3=(p*0.125)*( (abs(g1)+g1)*(abs(g1)+g1)+(abs(g2)+g2)*(abs(g2)+g2) );

return ( s*s*d[0]*d[0]+s*sum1+sum2+sum3 );

}

}

double diff(char &var,fine p,counters i,counters j, point &x)

{

accuracy h=0.000000001;

point dx;

for(j=0;j<n;j++) {dx[j]=x[j];}

dx[i]=dx[i]+h;

return ((f(var,p,dx)-f(var,p,x))/h);

}

double d_diff(char &var,fine p,counters i,point &x)

{

accuracy h=0.00001;

double result=0;

double f1=0,f2=0,f3=0;

double dx[n];

counters j=0;

for(j=0;j<n;j++){dx[j]=x[j];}

dx[i]=x[i]+h; f1=f(var,p,dx);

f2=f(var,p,x);

dx[i]=x[i]-h; f3=f(var,p,dx);

result=(f1-2*f2+f3)/(h*h);

if (abs(result)<0.001) result=0;

return result;

}

double mixdiff(char &var,fine p,counters i,counters j,point &x)

{

accuracy h=0.00001;

double result=0;

double f1=0,f2=0,f3=0,f4=0;

double dx[n];

counters k=0;

for(k=0;k<n;k++) {dx[k]=x[k];}

f1=f(var,p,x);

dx[i]=dx[i]-h; f2=f(var,p,dx);

dx[j]=dx[j]-h; f4=f(var,p,dx);

dx[i]=dx[i]+h; f3=f(var,p,dx);

result=(f1-f2-f3+f4)/(h*h);

if (abs(result)<0.001) result=0;

return result;

}

void Hessian(char &var,fine p,point &x,Hessian_matrix &H,Determ_Hess_matr &dH)

{

counters i=0,j=0;

dH=0;

cout<<endl<<"Матрица Гесса: "<<endl;

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

H[i][j]=mixdiff(var,p,i,j,x);

H[i][i]=d_diff(var,p,i,x);

cout<<" "<<H[i][j];

}

cout<<endl;

}

dH=H[0][0]*H[1][1]-H[0][1]*H[1][0];

cout<<"Определитель матрицы Гесса: "<<dH<<endl;

}

void step_0(char &var,counters i, counters j, accuracy &eps, point &x, matrix &D)

{

cout<<endl<<"Список: "<<endl<<endl;

cout<<"1.Тестовая функция "<<endl;

cout<<"2.Неквадратичная (основная) функция "<<endl;

cout<<"3.Условная минимизация.Метод внешних штрафных функций"<<endl;

repeat:

cout<<endl<<"Пункт: ";

cin>>var;

if ((var=='1')||(var=='2')||(var=='3')) {;}

else {cout<<endl<<"Выберете пункт из списка!"<<endl; goto repeat;}

cout<<endl<<"Задайте точность:\t";

cin>>eps;

cout<<endl<<"Ввод начальной точки Х в "<<n<<"-мерном Евклидовом";

cout<<endl<<"пространстве, при k=0(можно в строчку, разделяя пробелами)";

cout<<endl;

for (i=0;i<n;i++) { cin>>x[i]; if (i==n-1) {break;} }

//присвоение вида D=Е (при k=0)

for (i=0;i<n;i++) {for (j=0;j<n;j++) {D[i][j]=0; D[i][i]=1;}}

}

void step_1(counters i, counters j, gradient &g, direction &d, matrix &D)

{

for(i=0;i<n;i++){d[i]=0;}

for(i=0;i<n;i++){ for(j=0;j<n;j++){ d[i]=d[i]+D[i][j]*g[j]; } }

for(i=0;i<n;i++){ d[i]=-d[i]; }

cout<<"Направление{ d(x)=-D*f'(x) }: "<<endl;

for(i=0;i<n;i++){cout<<d[i]<<endl;}

}

void step_2(char &var,fine p,step &s,point &x,direction &d)

{

double a=-1000, b=1000;

double const1=0.381966, const2=0.618033;

double alfa=0, bett=0;

double F1=0,F2=0;

double eps=0.000000001;

alfa=a+const1*(b-a);

bett=a+const2*(b-a);

while(const2*(b-a)>=eps)

{

F1=psy(var,p,alfa,x,d);

F2=psy(var,p,bett,x,d);

if (F1>F2)

{

a=alfa;

alfa=bett;

bett=a+const2*(b-a);

}

else

{

b=bett;

bett=alfa;

alfa=a+const1*(b-a);

}

};

F1=psy(var,p,alfa,x,d);

F2=psy(var,p,bett,x,d);

if (F1>F2) s=bett;

else s=alfa;

cout<<"Шаг S: "<<s<<""<<endl;

}

void step_3(char &var,fine p,difference_of_points &U,difference_of_grad &V,step s,point &x,direction &d)

{

counters i=0,j=0,k=1;

gradient g;

for(i=0;i<n;i++) {U[i]=-x[i];}

for (i=0;i<n;i++){g[i]=diff(var,p,i,j,x); if (abs(g[i])<0.0001) g[i]=0;}

for(i=0;i<n;i++) {V[i]=-g[i];}

for(i=0;i<n;i++) {x[i]=x[i]+s*d[i];}

for(i=0;i<n;i++) {U[i]=U[i]+x[i];}

for (i=0;i<n;i++){g[i]=diff(var,p,i,j,x); if (abs(g[i])<0.0001) g[i]=0;}

for(i=0;i<n;i++) {V[i]=V[i]+g[i];}

for(i=0;i<n;i++) {cout<<x[i]<<endl;}

cout<<endl<<"Разность точек U: "<<endl;

for(i=0;i<n;i++) {cout<<U[i]<<endl;}

cout<<endl<<"Разность градиентов V: "<<endl;

for(i=0;i<n;i++) {cout<<V[i]<<endl;}k++;

}

void step_4(counters i,norm_gradient &norm,gradient &g)

{

norm=0;

for (i=0;i<n;i++) {norm=norm+g[i]*g[i];}

norm=sqrt(norm);

}

void step_5(difference_of_points U,difference_of_grad V,matrix &D)

{ counters i=0, j=0;

point l,m;

double A1=0,B1=0;

matrix A, B;

for(i=0;i<n;i++) { m[i]=0; l[i]=0; }

for(i=0;i<n;i++) { A1=A1+U[i]*V[i]; }

for(i=0;i<n;i++) { for(j=0;j<n;j++) { A[i][j]=(U[i]*U[j])/A1; } }

for(i=0;i<n;i++) { for(j=0;j<n;j++) { m[i]=m[i]+D[i][j]*V[j]; } }

for(i=0;i<n;i++) { B1=B1+V[i]*m[i]; }

for(i=0;i<n;i++) { for(j=0;j<n;j++) { l[i]=l[i]+V[j]*D[j][i]; } }

for(i=0;i<n;i++) { for(j=0;j<n;j++) { B[i][j]=((-1)*(m[i]*l[j]))/B1; } }

for(i=0;i<n;i++) { for(j=0;j<n;j++) { D[i][j]=D[i][j]+A[i][j]+B[i][j]; } }

cout<<endl<<"Матрица A: "<<endl;

for(i=0;i<n;i++)

{for(j=0;j<n;j++){cout<<" "<<A[i][j]<<" ";}cout<<endl;}

cout<<endl<<"Матрица В: "<<endl;

for(i=0;i<n;i++)

{for(j=0;j<n;j++){cout<<" "<<B[i][j]<<" ";}cout<<endl;}

cout<<endl<<"Матрица D (k=k+1): "<<endl;

for(i=0;i<n;i++)

{for(j=0;j<n;j++){cout<<" "<<D[i][j]<<" ";}cout<<endl;}

}

void main()

{

//Включаем вывод русских символов в консоль

setlocale(LC_ALL,"Russian");

char var;

counters i=0, j=0;

number_of_iteration k=0;

double c=5;

step s=0;

fine p=0.1;

accuracy eps=0;

accuracy fine_eps;

norm_gradient norm=0;

point x;

difference_of_points U;

gradient g;

difference_of_grad V;

direction d;

matrix D;

Hessian_matrix H;

Determ_Hess_matr dH;

step_0(var,i,j,eps,x,D);

if (var=='3')

{

cout<<endl<<"Точность метода штрафных функций: ";

cin>>fine_eps;

}

cout<<endl;

Hessian(var,p,x,H,dH);

if (dH<=0)

{

cout<<endl<<”Функций в данной области не имеет минимума: ”<<endl;

goto end;

}

cout<<endl<<"Градиент при k="<<k<<": "<<endl;

for (i=0;i<n;i++)

{

g[i]=diff(var,p,i,j,x);

if (abs(g[i])<0.0001) g[i]=0;

cout<<g[i]<<endl;

}

step_4(i,norm,g);

cout<<endl<<"Норма градиента при k="<<k<<": "<<norm<<endl;

//Реализация метода внешних штрафных функций(3 пункт)

switch (var)

{case '3': while (phi(p,x)>=fine_eps)

{

do

{

cout<<endl; for (i=0;i<20;i++) cout<<"|||";

cout<<endl<<"Итерация: "<<k<<endl<<endl;

step_1(i,j,g,d,D);

step_2(var,p,s,x,d);

cout<<endl<<"Следующая точка при k="<<k+1<<": "<<endl;

step_3(var,p,U,V,s,x,d);

cout<<endl<<"Градиент: "<<endl;

for (i=0;i<n;i++)

{

g[i]=diff(var,p,i,j,x);

if (abs(g[i])<0.0001) g[i]=0;

cout<<g[i]<<endl;

}

step_4(i,norm,g);

cout<<endl<<"Норма градиента: "<<norm<<endl;

step_5(U,V,D);

k++;

}

while (norm>eps);

p=c*p;

for (i=0;i<n;i++)

{

g[i]=diff(var,p,i,j,x);

if (abs(g[i])<0.0001) g[i]=0;

}

step_4(i,norm,g);

} break;

default: while (norm>eps)

{

cout<<endl; for (i=0;i<20;i++) cout<<"|||";

cout<<endl<<"Итерация: "<<k<<endl<<endl;

step_1(i,j,g,d,D);

step_2(var,p,s,x,d);

cout<<endl<<"Следующая точка при k="<<k+1<<": "<<endl;

step_3(var,p,U,V,s,x,d);

cout<<endl<<"Градиент: "<<endl;

for (i=0;i<n;i++)

{

g[i]=diff(var,p,i,j,x);

if (abs(g[i])<0.0001) g[i]=0;

cout<<g[i]<<endl;

}

step_4(i,norm,g);

cout<<endl<<"Норма градиента: "<<norm<<endl;

step_5(U,V,D);

k++;

}break;

}

cout<<endl; for (i=0;i<20;i++) cout<<"|||";

cout<<endl<<endl<<"Конец вычислений: "<<endl;

cout<<endl<<"Точка минимума при k="<<k<<": "<<endl;

for(i=0;i<n;i++) {cout<<x[i]<<endl;}

cout<<endl<<"Значение функции k="<<k<<": "<<endl;

cout<<f(var,p,x)<<endl;

end:;

}

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