Методы нахождения безусловного и условного экстремума
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
Методы нахождения безусловного и условного экстремума
Введение
С развитием производственных отношений в стране перед наукой встаёт серьёзная и очень важная проблема оптимизации рыночных отношений, внедрения компьютерной обработки данных в экономику. Значительное число нерешённых задач стоит перед человечеством накануне второго тысячелетия. Во времена, когда борьба уже идёт не за минуты и секунды, а за микросекунды, не за метры и сантиметры, а за миллиметры и доли миллиметров, когда возможность учесть, а главное исследовать влияние косвенных факторов на жизненноважные области деятельности человека, становится невторостепенной, оптимизационные методы минимизации и максимизации приобретают всё большую ценность и востребованность.
Развитие численных линейных методов решения задач линейного программирования очень важно в нынешнее время, поскольку сложность решаемых задач взваливает всю работу на современные ЭВМ, работающие с единичками и ноликами, и неподозревающих о существовании производных, первообразных, интегралов и пр. И нахождение оптимального решения сводится к представлению его в виде численных методов.
Применение оптимизационных задач имеет особый успех при проектировании и анализе больших технических систем. Кроме того, интенсивное развитие средств вычислительной техники стимулирует ускорение темпов внедрения теоретических разработок в инженерную практику. В настоящее время для инженера знание методов оптимизации столь же необходимо, как знание основ математического анализа, физики, радиоэлектроники и других дисциплин.
Задание на курсовую работу:
Найти минимум целевой функции f(x)
методом равномерного симплекса;
методом Хука-Дживса;
методом сопряжённых направлений Пауэлла;
методом Коши;
методом Ньютона;
методом сопряжённых градиентов;
квазиньютоновским методом;
имея ограничения на решение, методом штрафных функций.
Предварительно необходимо найти стационарную точку х и определить характер экстремума из необходимых и достаточных условий.
Исходные данные для решения:
1.Вид целевой функции
;
. Начальная точка поиска х(0) = [-9;-10]Т и величина шагов;
. Вид ограничений задачи.
. Окончание поиска:
в методе равномерного симплекса после завершения одного оборота симплекса в области расположения стационарной точки;
в методе Хука-Дживса после первого сокращения шага поиска;
в методе Коши после выполнения четырёх итераций;
в методе штрафных функций после выполнения расчётов для четырёх последовательных значений штрафного параметра.
В остальных методах экстремум определяется точно и за конечное число шагов.. Нахождение безусловного экстремума
. Нахождение стационарной точки
Целевая функция:
Частные производные по и :
Приравняв полученные выражения к нулю, получим систему уравнений:
Решение системы уравнений даёт результат:
Таким образом, экстремум целевой функции является точка с координатами , значение целевой функции, в которой: .
Для определения характера стационарной точки составим Гессиан функцию (определитель, составленный из вторых производных исходной целевой функции).
Так как гессиан функция - положительно определенная матрица (выполняются условия Сильвестра: все диагональные элементы матрицы Гесса - положительные величины, все ведущие главные определители положительные величины), стационарная точка является точкой минимума.
Рис 1. Линии уровня функции и стационарная точка
Метод равномерного симплекса
Описание алгоритма
Суть метода заключается в исследовании целевой функции в вершинах некого "образца", построенного в пространстве вокруг "базовой" точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве - тетраэдр.
Работа алгоритма начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой точке. Затем определяется вершина с максимальным значением целевой функции и проектируется через центр тяжести оставшихся вершин в новую точку.
Процедура продолжается до тех пор, пока не будет накрыта точка минимума.
Некоторые правила:
. Если вершина с максимальным значением целевой функции построена на предыдущем шаге, то отбрасывается вершина со следующим по величине значением целевой функции.
. Если вокруг одной из вершин начинается циклическое движение, то необходимо уменьшить размеры симплекса.
Поиск заканчивается тогда, когда размеры симплекса или разность значений целевой функции становятся достаточно малыми.
При заданной начальной точке и масштабном множителе , координаты остальных вершин симплекса в - мерном пространстве вычисляются по формуле:
Приращения и определяется по формулам:
Величин