Решение задач безусловной оптимизации

Решение задач безусловной оптимизации

Оглавление

Введение

Теоретическая часть

Аналитический способ

Численные методы

Решение поставленной задачи в МCAD

Решение задачи с помощью табличного редактора Ms Excel

Решение задачи с помощью языка С++

Заключение

Введение

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

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

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

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

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

Цель курсовой работы:

·        изучить необходимые программные конструкции языка программирования;

·        освоить стандартные алгоритмы безусловной оптимизации;

·        реализовать их средствами языка программирования С++;

·        научиться использовать программы MCAD и MS Excel для решения поставленных задач и сверить полученные результаты.

Задачи данной курсовой работы:

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

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

Теоретическая часть

Для оптимизационного решения задачи требуется:

. Сформулировать задачу;

. Построить математическую модель (определить множество переменных);

. Определить ограничения на возможные решения;

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

способа:

·        Аналитический

·        Численный

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

Аналитический способ

1.       Для одной переменной

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

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

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

Пусть функция y=f(x) :

1.       непрерывна в точке ;

2.       дифференцируема в этой точке ;

3.       - точка возможного экстремума;

.        при переходе через точку  производная  меняет знак.

Тогда, если  меняет знак с плюса на минус, то  - точка максимума, а если с минуса на плюс, то  - точка минимума.

) Найти производную функции .

) Найти стационарные точки (точки, подозрительные на экстремум), решив уравнение .

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

) Найти значение функции в точках минимума (максимума).

. Для двух переменных

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

Если - точка экстремума функции f, то

и или

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

Обозначим

Если D > 0, A > 0, то - точка минимума.

Если D > 0, A < 0, то - точка максимума.

Если D < 0, экстремума в точке нет.

Если D = 0, необходимы дополнительные исследования.

Численные методы

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

Метод "золотого сечения" почти столь же эффективен, как и метод Фибоначчи, однако при этом не требуется знать n - количество вычислений функции, определяемое вначале. После того как выполнено j вычислений, записываем

L_j-1=L_j+L_j+1

Однако если n не известно, то мы не можем использовать условие L_n-1 =L_n - е. Если отношение последующих интервалов будет постоянным, т.е.

то

т. е. τ=1+1/ τ.

Таким образом, τ²-τ-1=0, откуда . Тогда

 и т.д.

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

, т.е. .

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

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

Таким образом, если ищется интервал (х0, х3) и имеются два значения функции f1 и f2 в точках x1 и x2, то следует рассмотреть два случая (рис. 1).

Рисунок 1

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

Рисунок 2. Схема алгоритма метода «золотого сечения»

Здесь С - константа,

1 (поиск минимума функции F(x)),

С=

-1 (поиск минимума функции F(x)),

При выводе x - координата точки, в которой функция F(x) имеет минимум (или максимум), FM - значение функции F(x) в этой точке.

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

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

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

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

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

Стратегия решения задачи состоит в построении последовательности точек {x^k}, k=0,1,…, таких, что . Точки последовательности {x^k} вычисляются по правилу

,

где точка x⁰ задается пользователем;  - градиент функции f(x), вычисленный в точке x^k; величина шага t_k задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия

 или  

Построение последовательности {x^k} заканчивается в точке x^k, для которой

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

где  - малое положительное число. Вопрос о том, может ли точка x^k рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования.

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

Геометрическая интерпретация метода для функции двух переменных f(x₁,x₂):

Алгоритм

Шаг 1. Задать  - предельное число итераций. Найти градиент функции в произвольной точке

Шаг 2. Положить k=0.

Шаг 3. Вычислить .

Шаг 4. Проверить выполнение критерия окончания :

·             если критерий выполнен, расчет закончен: ;

·        если критерий не выполнен, то перейти к шагу 5.

Шаг 5. Проверить выполнение неравенства :

·             если неравенство выполнено, то расчет окончен: ;

·        если нет, то перейти к шагу 6.

Шаг 6. Задать величину шага t_k.

Шаг 7. Вычислить .

Шаг 8. Проверить выполнение условия

 (или ):

·    если условие выполнено, то перейти к шагу 9;

·        если условие не выполнено, положить  и перейти к шагу 7.

Шаг 9. Проверить выполнение условий

·    если оба условия выполнены при текущем значении k и k=k-1, то расчет окончен,

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

Процедура решения задачи

1.       Используя алгоритм градиентного спуска с постоянным шагом, найти точку x^k, в которой выполнен по крайней мере один из критериев окончания расчетов.

2.       Провести анализ точки x^k с целью установить, является ли точка x^k найденным приближением решения задачи. Процедура анализа определяется наличием у функции f(x) непрерывных вторых производных. Если , то следует провести проверку выполнения достаточных условий минимума: . Если , то точка  есть найденное приближение искомой точки . Если , то следует провести проверку функции f(x) на выпуклость в Q-окрестности точки , используя критерий выпуклости для функций : функция f(x) выпукла (строго выпукла) в том и только в том случае, если . Если функция f(x) выпукла (строго выпукла), то  есть найденное приближение точки .

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

Схема алгоритма метода градиентного спуска

Решение поставленной задачи в МCAD

задача

Минимизация функции с одной переменной.

способ

способ

задача

Определение какого рода функция и нахождение минимума(максимума) этой функции.

способ

способ

Вывод

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

Решение задачи с помощью табличного редактора Ms Excel

задача:

Ход решения в Ms Excel

Итак, вначале в соответствии с поставленной задачей протабулируем функцию (найти минимум при х>0). Затем по полученным данным построим график, по которому находим примерное приближение значений минимума. Записываем приближенное значение в отдельную ячейку, в соседнюю ячейку записываем формулу зависящую от приближенного значения и воспользуемся инструментом «Поиск решения». В качестве целевой ячейки указываем функцию, ставим галочку «Минимальное значение», в поле «Изменяя ячейки» ставим ячейку с приближение. Жмем «Выполнить» и получаем искомое значение минимума.

2 задача:

Ход решения в Ms Excel

Табулируем функцию. По полученным данным построим график поверхности, по которому видим, что нужно найти минимум этой функции. С помощью встроенной функции МИН() найдем наименьшее приближенное значение функции. Далее в отдельную ячейку скопируем значения х, у и z для полученного максимума, и воспользуемся инструментом «Поиск решения». В качестве целевой ячейки указываем скопированное выше значение z, ставим галочку «Минимальное значение», в поле «Изменяя ячейки» ставим ячейку со значением х и у. Жмем «Выполнить» и получаем искомое значение максимума.

Решение задачи с помощью языка С++

численный экстремум безусловный оптимизация

1 задача:

#include <iostream>

#include <math.h>

#include <stdio.h>

#include <conio.h>

#include <windows.h>namespace std;double epsilon = 0.001;//точностьfun(double x)

{pow(x,4)/4-pow(x,3)/3-7*pow(x,2)+4*x+1;//заданная функция

}

//Метод золотого сеченияGoldenSection(double a, double b)

{x1,x2;//объявляемy1, y2;//переменные= a + 0.382*(b-a);//два отрезка на которые= a + 0.618*(b-a);//делится промежуток= fun(x1);//вычисляется значение функции в точке х1= fun(x2);//вычисляется значение функции в точке х2((b-a) > epsilon)

{(y1 >= y2)

{= x1;//к началу отрезка присваевается значение первого отрезка= x2;//= fun(x1);//вычисляется значение функции в точке х1= a + 0.618*(b-a);= fun(x2);//вычисляется значение функции в точке х2

}

{= x2;//к концу отрезка присваивается значение х2= x1;= fun(x2);//вычисляется значение функции в х2= a + 0.382*(b-a);= fun(x1);//вычисляется значение функции в х1

}

}(a+b)/2;//отрезок делится на две части

}main()

{(LC_CTYPE, "Russian");a, b, min, max;//объявление переменных<< "\t Вычисление минимума функции F(x) = x^4/4-x^3/3-7*x^2)+4*x+1 \n\t метадом золотого сечения " << endl << endl;<< "Входной интервал для поиска экстремальных функций (например 0 15):\n";>> a;//Ввод начала отрезка>> b;//ввод конца отрезка= GoldenSection(a, b);//Значение минимума в золотом сечении("\n Значение точки минимум MIN=%3.3f",min);//Вывод минимума("\n значение функции F(min)=%3.3f",fun(min));//Вывод функции от точки минимума

_getch();0;

}

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

2 Задача:

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include<iostream>

#define N 2// количество переменныхx_k[N];//неизвестныеx_k_1[N];//значение последвательного приближенияlambda_k;//шагy(double *x, int n)

{(2*pow(x[0],2) -3*x[1]*x[0] + 5*x[1]*x[1]-3*x[0]); //функция

}dy_dx0(double *x, int n) // первая частная производная по Х

{(4*x[0]-3*x[1]-3);

}dy_dx1(double *x, int n) // первая частная производная по Y

{(-3*x[0]+10*x[1]);

}dy2_dx0(double *x, int n)// 2-я частная производная по X

{(4);

}dy2_dx1(double *x, int n)// 2-я частная производная по Y

{(10);

}main(void)

{ setlocale(LC_CTYPE, "Russian");_k = 0.001;//шаг_k[0] = 0;//начальное_k[1] = 5;//приближение(1)//будет длится до конца интервала

{_k_1[0] = x_k[0]- lambda_k*dy_dx0(x_k, N) ;//последвательное_k_1[1] = x_k[1] - lambda_k*dy_dx1(x_k, N);//приближение(fabs(dy_dx0(x_k_1, N))<lambda_k && fabs(dy_dx1(x_k_1, N))<lambda_k) break;//условие при котором меняются значения меняется начальное и конечное значение промежутка_k[0] = x_k_1[0];//присвоение начальному значению_k[1] = x_k_1[1];//значение приближения

}_k[0] = x_k_1[0];_k[1] = x_k_1[1];("\tГрадиентный метод:\n");("\tМинимум найден на x1 =%.3lf, x2 =%.3lf, Y(X1,X2) =%3.3f\n", x_k[0], x_k[1], y(x_k, N));//Вывод минимальных точек и значения функции в этой точке();0;

}

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

Заключение

Путем сложных вычислений курсовая работа выполнена в математическом редакторе Mathcad, табличном редакторе Excel и языке программирования С++. Все ответы сходятся, для проверки построены графики, на которых видна приблизительная цель вычислений. Всё выполнено согласно правилам. Таким образом, можно сделать вывод, что данная курсовая работа по теме «Решение задач безусловной оптимизации» выполнена.