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

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

Рубрика Математика
Вид курсовая работа
Язык русский
Дата добавления 12.07.2012
Размер файла 716,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

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

Введение

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

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

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

Задание на курсовую работу:

Найти минимум целевой функции f(x)

-методом равномерного симплекса;

-методом Хука-Дживса;

-методом сопряжённых направлений Пауэлла;

-методом Коши;

-методом Ньютона;

-методом сопряжённых градиентов;

-квазиньютоновским методом;

-имея ограничения на решение, методом штрафных функций.

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

Исходные данные для решения:

1. Вид целевой функции

;

2. Начальная точка поиска х(0) = [-9;-10]Т и величина шагов;

3. Вид ограничений задачи.

4. Окончание поиска:

- в методе равномерного симплекса после завершения одного оборота симплекса в области расположения стационарной точки;

- в методе Хука-Дживса после первого сокращения шага поиска;

- в методе Коши после выполнения четырёх итераций;

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

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

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

1. Нахождение стационарной точки

Целевая функция:

Частные производные по и :

Приравняв полученные выражения к нулю, получим систему уравнений:

Решение системы уравнений даёт результат:

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

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

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

Рис 1. Линии уровня функции и стационарная точка

Метод равномерного симплекса

Описание алгоритма

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

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

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

Некоторые правила:

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

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

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

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

Приращения и определяется по формулам:

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

Вычисление центра тяжести:

Если - точка, подлежащая отражению, то координаты центра тяжести определяются по формуле:

Координаты новой вершины удовлетворяют уравнению:

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

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

Нахождение минимума целевой функции методом равномерного симплекса

Исходные данные:

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

- масштабный множитель

Минимизируем целевую функцию до первого уменьшения размера симплекса

Пусть масштабный множитель -

1-я итерация:

- максимально, следовательно, заменяем

2-я итерация:

- максимально, следовательно, заменяем

3-я итерация:

- максимально, следовательно, заменяем

4-я итерация:

- максимально следовательн,о заменяем

5-я итерация:

- максимально, следовательно, заменяем

6-я итерация:

- максимально, следовательно, заменяем

7-я итерация:

- максимально, следовательно, заменяем

8-я итерация:

- максимально, следовательно, заменяем

9-я итерация:

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

10-я итерация:

Координаты точки, полученные на 10-й итерации, совпадают с координатами, полученными на 4-й итерации. Симплекс накрыл точку минимума. Далее следует уменьшить масштабный множитель (например, в 2 раза) и построить новый исходный симплекс, взяв в качестве исходной точку

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

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

Метод Хука-Дживса

Описание алгоритма

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

Исследующий поиск:

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

Поиск по образцу:

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

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

Шаг 1. Задать:

1. Начальную точку ;

2. Приращение ,;

3. Коэффициент уменьшения шага ;

4. Параметр окончания поиска .

Шаг 2. Произвести исследующий поиск.

Шаг 3. Поиск удачный:

Да:

перейти к шагу 5;

Нет:

продолжить.

Шаг 4. Проверка на окончание поиска: ?

Да:

прекратить поиск;

Нет:

уменьшить приращение по формуле: ,;

Перейти к шагу 2.

Шаг 5. Провести поиск по образцу:

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

Шаг 7. Выполняется ли условие ?

Да:

продолжить ; ;

перейти к шагу 5;

Нет:

перейти к шагу 4.

Нахождение минимума целевой функции методом Хука-Дживса.

Исходные данные:

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

- векторная величина приращения;

- коэффициент уменьшения шага.

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

Исследующий поиск вокруг базовой точки х(0):

фиксируя х2, даём приращение переменной х1:

х2=-10; х1=-9+1=-8 f =190<359удача

фиксируя х1, даём приращение переменной х2:

х1=-8; х2=-10+1=-9 f = 183<190удача

х(1) = [-8;-9]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp(2) = 2*х(1) - х(0);

хp (2) = [-7;-8]T f =147

Исследующий поиск вокруг точки хp (2):

фиксируя х2, даём приращение переменной х1:

х2=-8; х1=-7+1=-6 f = 120<147удача

фиксируя х1, даём приращение переменной х2:

х1=-6; х2=-8+1=-7 f = 115<120удача

х(2) = [-6;-7]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (3) = 2*х(2) - х(1);

хp (3) = [-4;-5]T f =63

Исследующий поиск вокруг точки хp (3):

фиксируя х2, даём приращение переменной х1:

х2=-5; х1=-4+1=-3 f = 45<63удача

фиксируя х1, даём приращение переменной х2:

х1=-3; х2=-5+1=-4 f = 43<45удача

х(3) = [-3;-4]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (4) = 2*х(3) - х(2);

хp (4) = [0;-1]T f =7

Исследующий поиск вокруг точки хp (4):

фиксируя х2, даём приращение переменной х1:

х2=-1; х1=0+1=1 f = 15>7неудача

фиксируя х1, даём приращение переменной х2:

х1=1; х2=-1+1=0 f =9<15удача

х(4) = [1;0]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (5) = 2*х(4) - х(3);

хp (5) = [5;4]T f =27.

5. Исследующий поиск вокруг точки хp (5):

фиксируя х2, даём приращение переменной х1:

х2=4; х1=5+1=6 f = 36>27неудача

фиксируя х1, даём приращение переменной х2:

х1=6; х2=4+1=5 f =43>27неудача

х2=4-1=3 f =29<27удача

х(5) = [6;3]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (6) = 2*х(5) - х(4);

хp (6) = [11;6]T f =70.

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

б = 1/2=0.5;

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

х (5) = [6][3], используя новое значение приращения б =0.5;

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

Т.о. мы получили точку х = [6;3]Т, значение функции в которой

f(x) = 36. Это значение значительно приближено к значению функции в стационарной точке (1), однако дальнейший ход решения укажет на улучшение результата.

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

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

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

Рис 3. Графическое пояснение метода Хука-Дживса

Метод сопряжённых направлений Пауэлла

Описание алгоритма

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

приводится к виду сумма полных квадратов

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

В методе Пауэлла поиск реализуется в виде:

вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.

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

Шаг 1. Задать исходные точки , и направление . В частности, направление может совпадать с направлением координатной оси;

Шаг 2. Произвести одномерный поиск из точки в направлении получить точку , являющуюся точкой экстремума на заданном направлении;

Шаг 3. Произвести одномерный поиск из точки в направлении получить точку ;

Шаг 4. Вычислить направление ;

Шаг 5. Провести одномерный поиск из точки (либо ) в направлении c выводом в точку .

Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.

Решение:

Целевая функция:

Начальная точка:

Значение целевой функции в этой точке:

Шаг 1. Зададим исходные точки S(1) и S(2):

S(1) = [1;0] S(2) = [0;1]

Шаг 2. Найдем значение , при [Х(0)+2S(2)]. Произвольная точка на луче из точки Х(0) в направлении S(2) определяется как

Х = Х(0) + S(2) = [-9;-10] + [0;1]

откуда X1 = -9 X2 = - 10

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

(Х) =

Дифференцируем это выражение по и приравниваем нулю:

'(X) = 2 - 31

2 - 31 = 0

Отсюда находим :

= 15.5

X(1) = [-9;-10] + 15.5[0;1] = [-9;5.5]

[X(1)] = 99

Аналогично найдем значение , при [Х(1)+S(1)].

Х = Х(1) + S(1) = [-9;5.5] + [1;0]

откуда X1 = -9 X2 =5.5

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

(Х) =

Дифференцируем это выражение по и приравниваем нулю:

'(X) = 2 - 29

2 - 29 = 0

Отсюда находим :

= 14.5

X(2) = [-9;5.5] + 10.5[1;0] = [0.5;5.5]

[X(2)] = 21

Также найдем значение , при [Х(2)+2S(2)].

Х = Х(2) + S(2) = [0.5;5.5] + [0;1]

откуда X1 = 3 X2 = 5.5+

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

(Х) =

Дифференцируем это выражение по и приравниваем нулю:

'(X) = 2+12

12 + 2 = 0

Отсюда находим :

= -6

X(3) = [0.5;5.5] -6 [0;1] = [1.5;-0.5]

[X(3)] = -3

Шаг 3. Положим

S(3) = X(3) - X(1) = [12;-6]

Направление S(3) оказывается сопряженным с направлением S(2). Поскольку N = 2, то оптимизация вдоль направления S(3) дает искомый результат. Шаг 4. Найдем такое значение , при [X(3) + S(3)]

X = X(3) + [12;-6]= [1.5;-0.5] + [12;-6]

X1 = 3+ 12 X2 = -0.5 -6

'(X) = 216-6

Отсюда

= 0.0278

Тогда

Х(4) = [3;-0.5] +0.0278*[12;-6] = [3.3336;-0.6668]

Таким образом, получили точку х= [3.3336;-0.6668-]T, значение функции в которой f(x) = -3,778, совпадает со стационарной точкой.

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

Графическое пояснение метода сопряженных направлений Пауэлла:

Рис.

Методы прямого поиска являются удобными при простых целевых функциях, или когда необходимо найти оптимум с невысокой степенью точности. Но требуют больших затрат времени и вычислительных ресурсов, из-за большого числа проводимых итераций: метод поиска по симплексу - 15 итераций, метод Хука-Дживса - 5 итераций, метод сопряженных направлений Пауэлла - 4 итерации.

Метод Коши

Описание алгоритма

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

- градиент функции

Алгоритм метода выглядит следующим образом:

, где - градиент.

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

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

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

Нахождение минимума целевой функции методом Коши.

Исходные данные:

- начальная точка (начальное приближение)

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

Начальное приближение

1. Новое приближение определим по формуле:

Выбираем такое, чтобы минимизировать функцию

2. Далее найдем точку:

f (x(1) ) =[-0,778;0,866]T

3. Далее найдем точку:

После 4 итераций найдено достаточно точное значение минимума, при котором значение целевой функции в точке , .

Рис 5. Графическое пояснение метода Коши

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

Описание алгоритма

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

, где:

- гессиан (матрица Гессе)

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

Нахождение минимума целевой функции методом Ньютона.

Исходные данные:

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

;

Таким образом, точка минимума , значение функции в которой найдена за одну итерацию.

Рис 6. Графическое пояснение метода Ньютона

Метод сопряженных градиентов

Описание алгоритма

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

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

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

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

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

Используемые в методе формулы:

Изменение градиента при переходе от точки к точке :

Изменения аргумента:

Направление поиска:

, , .

(рекуррентная формула Флетчера-Ривса).

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

Исходные данные:

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

Шаг 1.

Шаг 2.

Поиск вдоль прямой:

Шаг 3.

Определим направление :

//х1 в производную

Шаг 4.

Поиск вдоль прямой:

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

Рис 7. Графическое пояснение метода сопряженных градиентов

Квазиньютоновский метод

Описание алгоритма

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

Направление поиска определяется выражением:

, где - матрица порядка (метрика).

Матрица - вычисляется по формуле.

, где:

(1)

Где изменение градиента на предыдущем шаге.

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

Нахождение минимума целевой функции квазиньютоновским методом:

Исходные данные:

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

Шаг 1.

Положим

Шаг 2.

Поиск вдоль прямой:

Шаг 3.

Шаг 4.

Поиск вдоль прямой:

Таким образом, точка минимума , значение функции в которой найдена за одну итерацию.

Рис 8. Графическое пояснение квазиньютоновского метода

Градиентные методы поиска экстремума функции

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

Метод простейших градиентов

Решение:

f(x1,x2)= (х1 - 3)2 + (х2 - 1)2 +х1*х2

?f/?x1=2*x1 + x2 - 6 ?f/?x2=x1 + 2*x2 -2

1. Шаг: Задаем начальные данные:

х(0) = [-9;-10]Т; б =0,3;

2. Шаг:

1 итерация: х(1) = х(0) - б *f (x(0) ).

f (x(0) ) = [-34;-30]T; х(1) = [-9;-10]Т -0,3[-34;-30]T=[1,2;-1]T;

2 итерация: х(2) = х(1) - б *f (x(1) ).

f (x(1) ) = [-4,6;-2,8]T; х(2) = [1,2;-1]T -0,3[-4,6;-2,8]T =[2,58;0,16]T;

3 итерация: х(3) = х(2) - б *f (x(2) ).

f (x(2) ) = [-0,68;0,9]T; х(3) = [2,58;0,16]T -0,3[-0,68;0,9]T =[2,784;0,11]T;

4 итерация: х(4) = х(3) - б *f (x(3) ).

f (x(3) ) = [-0,322;1,004]T; х(4) = [2,784;0,11]T -0,3[-0,322;1,004]T =[2,881; -0,191]T;

5 итерация: х(5) = х(4) - б *f (x(4) ).

f (x(4) ) = [-0,429;0,499]T; х(5) = [2,881; -0,191]T -0,3[-0,429;0,499]T =[3,0097; -0,341]T;

6 итерация: х(6) = х(5) - б *f (x(5) ).

f (x(5) ) = [-0,322;0,328]T; х(6) =[3,0097; -0,341]T -0,3[-0,322;0,328]T =[3,106; -0,439]T;

7 итерация: х(7) = х(6) - б *f (x(6) ).

f (x(6) ) = [-0,227; 0,228]T; х(7) =[3,106; -0,439]T -0,3[-0,227; 0,228]T =[3,1741; -0,5074]T;

8 итерация: х(8) = х(7) - б *f (x(7) ).

f (x(7) ) = [-0,159; 0,159]T; х(8) =[3,1741; -0,5074]T -0,3[-0,159; 0,159]T =[3,333; -0,667]T;

После выполнения 8 итераций получено решение х* = х(7), при котором значение целевой функции f*=-0,3778.

Графическое пояснение метода простейших градиентов

Рис.

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

Нахождение условного экстремума. Метод штрафных функций

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

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

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

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

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

Виды штрафов:

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

Логарифмический штраф.

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

Штраф, заданный обратной функцией.

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

Штраф типа квадрата срезки.

, где

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

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

Шаг 1. Задать начальные данные:

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

- начальное значение штраф параметра

- параметр окончания работы алгоритма

Шаг 2. Построить штрафную функцию:

Шаг 3. Находим , доставляющее экстремум , методом Ньютона.

Шаг 4. Выполняется ли условие:

Да: , процесс решения закончен.

Нет: перейти к шагу 5.

Шаг 5.

, перейти к шагу 2.

Нахождение минимума целевой функции :

Исходные данные:

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

Ограничение на решение:

Преобразуем целевую функцию введением в неё заданного квадратичного штрафа:

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

Совместное решение даёт:

Устремляя к нулю, получаем

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

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

1.

2.

3.

4.

Таблица. Сведем все данные в таблицу:

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

Рис 9. Графическое пояснение метода штрафных функций

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

Рис.10 Интерфейс программы.

Библиографический список

1.Микрюкова В.И. Методы оптимизации. - методические указания по выполнению курсовой работы. - Киров ВятГу,2004. - 41.

2.Конспекты лекций.

3.Карманов В.Г. Математическое программирование. - М: Наука. Главная редакция физико-математической литературы, 1986

4.Коршунов Ю.М. Математические основы кибернетики. - М: Энергия, 1980.

5.В. И. Методы оптимизации. Методические указания по выполнению курсовой работы. Киров, 2010.

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

Приложение

Листинг программы.

//---------------------------------------------------------------------------

#include <vcl.h>

#include <math.h>

#include <fstream.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

double a[6] = {1,1,1,1,1,1}, nx[2] = {-10,-9}, E=1E-5;

//---------------------------------------------------------------------------

double f(double x[2])

{

return a[0]*x[0]*x[0]+a[1]*x[1]*x[1]+a[2]*x[0]*x[1]+a[3]*x[0]+a[4]*x[1]+a[5];

}

//---------------------------------------------------------------------------

double get_f_opt(double cur_x[2], double&df, double x[2])

{

double temp;

temp = a[2]*a[2]-4*a[1]*a[0];

x[0] = (-a[2]*a[4]+2*a[3]*a[1])/temp;

x[1] = (-a[2]*a[3]+2*a[4]*a[0])/temp;

df = 1/2.*sqrt(pow(x[0]-cur_x[0],2)+pow(x[1]-cur_x[1],2));

df = ceil(df);

return f(x);

}

//---------------------------------------------------------------------------

void paint_line(TChart*& Chart, int count, int ie)

{

double x[2],x0_min,x0_max,dx0,temp,f,f_opt,df;

int i, j;

f_opt=get_f_opt(nx,df,x);

Chart->Series[2]->AddXY(x[0],x[1],"x*");

for(i=0,f=ceil(f_opt+df);i<ie;f+=df,i++)

{

temp = a[3]*a[3]*a[1]*a[1]-a[3]*a[1]*a[2]*a[4]+a[1]*a[0]*a[4]*a[4]+

4*a[1]*a[1]*a[0]*f-4*a[1]*a[1]*a[0]*a[5]-a[2]*a[2]*a[1]*f+

a[2]*a[2]*a[1]*a[5];

if(temp<0) {continue;i--;}

temp = pow(temp,0.5);

x0_min=(1/(2*(4*a[1]*a[0]-a[2]*a[2])))*(-4*a[3]*a[1]+2*a[2]*a[4]-4*temp);

x0_max=(1/(2*(4*a[1]*a[0]-a[2]*a[2])))*(-4*a[3]*a[1]+2*a[2]*a[4]+4*temp);

dx0 = (x0_max-x0_min)/count; x0_min-=dx0; x0_max+=dx0;

for(x[0]=x0_min;x[0]<x0_max;x[0]+=dx0)

{

temp = a[4]*a[4]+2*a[4]*a[2]*x[0]+a[2]*a[2]*x[0]*x[0]-

4*a[1]*a[0]*x[0]*x[0]-4*a[1]*a[5]+4*a[1]*f-

4*a[1]*a[3]*x[0];

if(temp<0) temp=0; else temp = pow(temp,0.5);

for(j=-1;j<=1;j+=2)

{

x[1]=1/(2*a[1])*(-a[4]-a[2]*x[0]+j*temp);

Chart->Series[0]->AddXY(x[0],x[1]);

}

}

x[0] = x0_min+random(count)*dx0;

temp = a[4]*a[4]+2*a[4]*a[2]*x[0]+a[2]*a[2]*x[0]*x[0]-

4*a[1]*a[0]*x[0]*x[0]-4*a[1]*a[5]+4*a[1]*f-

4*a[1]*a[3]*x[0];

if(temp<0) temp=0; else temp = pow(temp,0.5);

x[1]=1/(2*a[1])*(-a[4]-a[2]*x[0]+(random(2)*2-1)*temp);

}

}

//---------------------------------------------------------------------------

void grad(double x[2], double gr[2])

{

gr[0] = 2*a[0]*x[0]+a[2]*x[1]+a[3];

gr[1] = 2*a[1]*x[1]+a[2]*x[0]+a[4];

}

//---------------------------------------------------------------------------

void gess(double x[2], double ge[2][2])

{

ge[0][0]=2*a[0]; ge[0][1]=ge[1][0]=a[2]; ge[1][1]=2*a[1];

}

//---------------------------------------------------------------------------

double get_alpha(double x[2], double s[2])

{

double t[2];

t[0] = 2*a[0]*s[0]*x[0]+ 2*a[1]*s[1]*x[1]+

a[2]*s[0]*x[1]+ a[2]*s[1]*x[0]+

a[3]*s[0] + a[4]*s[1];

t[1] = a[0]*s[0]*s[0]+ a[1]*s[1]*s[1]+

a[2]*s[0]*s[1];

if(fabs(t[0])<E) return 0;

return -0.5*t[0]/t[1];

}

//---------------------------------------------------------------------------

int TForm1::Calc(double E1, double E2, double count, int n)

{

int i,j,k; bool l;

double gr[2], //градиент

s[2], //направление

x[2][2]={{nx[0],nx[1]}}, //точки

alpha; //коэффициент поиска вдоль прямой

paint_line(Chart1,count,n);

Series3->AddXY(x[0][0],x[0][1],"f(x[0])="+FloatToStrF(f(x[0]),ffGeneral,5,0));

StringGrid1->Cells[0][1] = 1;

StringGrid1->Cells[1][1] = x[0][0];

StringGrid1->Cells[2][1] = x[0][1];

StringGrid1->Cells[3][1] = f(x[0]);

StringGrid1->RowCount = 2;

for(k=0;1;k++)

{

grad(x[k],gr);

if(sqrt(pow(gr[0],2)+

pow(gr[1],2))<E1) break;

for(i=0;i<2;i++) s[i] = -gr[i];

alpha = get_alpha(x[k],s);

for(i=0;i<2;i++) x[1][i] = x[0][i]+alpha*s[i];

Series3->AddXY(x[1][0],x[1][1],"f(x["+IntToStr(k+1)+"])="+

FloatToStrF(f(x[1]),ffGeneral,5,0));

StringGrid1->Cells[0][k+2] = k+2;

StringGrid1->Cells[1][k+2] = x[1][0];

StringGrid1->Cells[2][k+2] = x[1][1];

StringGrid1->Cells[3][k+2] = f(x[1]);

StringGrid1->RowCount = k+3;

Series2->AddArrow(x[0][0],x[0][1],x[1][0],x[1][1]);

if(sqrt(pow(x[1][0]-x[k][0],2)+

pow(x[1][1]-x[k][1],2))<E2) break;

for(i=0;i<2;i++) x[0][i]=x[1][i];

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

a[0] = StrToFloatDef(LabeledEdit1->Text,1);

a[1] = StrToFloatDef(LabeledEdit2->Text,1);

a[2] = StrToFloatDef(LabeledEdit3->Text,1);

a[3] = StrToFloatDef(LabeledEdit4->Text,1);

a[4] = StrToFloatDef(LabeledEdit5->Text,1);

a[5] = StrToFloatDef(LabeledEdit6->Text,1);

nx[0] = StrToFloatDef(LabeledEdit7->Text,1);

nx[1] = StrToFloatDef(LabeledEdit8->Text,1);

double E1,E2;

E1 = StrToFloatDef(LabeledEdit9->Text,1);

E2 = StrToFloatDef(LabeledEdit10->Text,1);

Calc(E1,E2,1E3,5);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FormCreate(TObject *Sender)

{

StringGrid1->Cells[0][0] = "i";

StringGrid1->Cells[1][0] = "x[i][0]";

StringGrid1->Cells[2][0] = "x[i][1]";

StringGrid1->Cells[3][0] = "f(x[i])";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{

if(SaveDialog1->Execute())

Chart1->SaveToMetafile(ChangeFileExt(SaveDialog1->FileName,".wmf"));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button3Click(TObject *Sender)

{

if(SaveDialog1->Execute())

{

ofstream out(ChangeFileExt(SaveDialog1->FileName,".txt").c_str());

for(int i=0;i<StringGrid1->RowCount;i++)

{

for(int j=0;j<StringGrid1->ColCount;j++)

{

out.width(20);

out<<StringGrid1->Cells[j][i].c_str();

}

out<<endl;

}

out.close();

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button4Click(TObject *Sender)

{

Form1->Close();

}

//---------------------------------------------------------------------------

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


Подобные документы

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

    курсовая работа [517,9 K], добавлен 30.04.2011

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

    курсовая работа [65,3 K], добавлен 30.11.2010

  • Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.

    курсовая работа [219,4 K], добавлен 17.04.2013

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

    задача [394,9 K], добавлен 21.08.2010

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

    курсовая работа [37,2 K], добавлен 01.05.2011

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

    контрольная работа [1,4 M], добавлен 16.08.2010

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

    реферат [162,8 K], добавлен 20.05.2019

  • Теория математического программирования. Методы поиска глобального экстремума функции нескольких переменных. Угловые точки допустимых множеств. Постановка общей задачи нелинейного программирования. Решения уравнения f(x)=0 методом простой итерации.

    контрольная работа [775,4 K], добавлен 05.01.2013

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

    курсовая работа [197,1 K], добавлен 09.04.2013

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

    курсовая работа [2,2 M], добавлен 11.12.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.