Рефотека.ру / Математика

Курсовая работа: Сравнительный анализ методов оптимизации

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра САПР


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине "Теория принятия решений"

Тема: "Сравнительный анализ методов оптимизации"


Руководитель:

(подпись) (дата)

Студент:

(группа)

_____________________

(подпись) (дата)


Караганда 2009

Сравнительный анализ методов оптимизацииСодержание


Введение

1. Формулировка математической задачи оптимизации. Основные понятия

1.1 Формулировка математической задачи оптимизации

1.2 Минимум функции одной переменной

1.3 Минимум функции многих переменных

1.4 Унимодальные функции

1.5 Выпуклые функции

2. Прямые методы безусловной оптимизации

2.1 Прямые методы одномерной безусловной оптимизации

2.1.1 Метод деления отрезка пополам (дихотомии)

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

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

2.2 Методы безусловной минимизации функций многих переменных

2.2.1 Метод циклического покоординатного спуска

2.2.2 Алгоритм Хука-Дживса

2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации

2.2.4 Минимизация по правильному симплексу

2.2.5 Поиск точки минимума по деформируемому симплексу

2.2.6 Практическая реализация симплексных методов

3. Условная оптимизация

4. Линейное программирование

Заключение

Список использованной литературы

Введение


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

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

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


1. Формулировка математической задачи оптимизации. Основные понятия


1.1 Формулировка математической задачи оптимизации


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

Под минимизацией (максимизацией) функции n переменных f (x) = (x1,.., xn) на заданном множестве U n-мерного векторного пространства Еn понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:


f (x) ®min (max),

хО U


где f (x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные.

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

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

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


1.2 Минимум функции одной переменной


Пусть функция f (x) определена на множестве U вещественной оси R.

1. Число х* О U называется точкой глобального (абсолютного) минимума или просто точкой минимума функции f (x) на множестве U, если f (x*) Ј f (x) для всех хО U.

Значение f * = f (x*) = Сравнительный анализ методов оптимизации называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.

Множество всех точек минимума f (x) на U в дальнейшем будет обозначено через U*.

2. Число Сравнительный анализ методов оптимизации ОU называется точкой локального минимума функции f (x), если Сравнительный анализ методов оптимизациидля всех xОU, достаточно близких к Сравнительный анализ методов оптимизации, т.е. если существует e > 0 такое, что это неравенство выполняется для любогоСравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации.

Глобальный минимум f (x) является и локальным минимумом, а обратное неверно.


1.3 Минимум функции многих переменных


Будем рассматривать функции многих переменных f =f (x1, …, xn) как функции, заданные в точках х n-мерного евклидова пространства Еn: f =f (х).

1. Точка х*ОЕn, называется точкой глобального минимума функции f (х), если для всех х*ОЕn выполняется неравенство f (x*) Ј f (х). Значение f (x*) = =Сравнительный анализ методов оптимизации называется минимумом функции. Множество всех точек глобального минимума функции f (х) будем обозначать через U*.

2. Точка Сравнительный анализ методов оптимизации называется точкой локального минимума функции f (х), если существует e-окрестность точки Сравнительный анализ методов оптимизации: Un (Сравнительный анализ методов оптимизации) ={x | r (x, Сравнительный анализ методов оптимизации) < e} такая, что для всех х*ОUn (Сравнительный анализ методов оптимизации) выполняется неравенство f (Сравнительный анализ методов оптимизации) Ј f (х).

3. Если допустимое множество U в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством En, то говорят о задаче безусловной оптимизации

Сравнительный анализ методов оптимизации, x О En.


1.4 Унимодальные функции


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

Функция f (x) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа a и b, Сравнительный анализ методов оптимизации, такие, что:

1) если а < a, то на отрезке [a; a] функция f (x) монотонно убывает;

2) если b < b, то на отрезке [b; b] функция f (x) монотонно возрастает;

3) при х О [a; b] f (x) =f * = Сравнительный анализ методов оптимизации.

Множество унимодальных на отрезке [а; b] функций мы будем обозначать через Q [а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рисунке 1.


Сравнительный анализ методов оптимизации

Рисунок 1 - Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции


Основные свойства унимодальных функций:

1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].

2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] Сравнительный анализ методов оптимизации [а; b].

3. Пусть f (x) Сравнительный анализ методов оптимизацииQ [а; b] и Сравнительный анализ методов оптимизации. Тогда:


если Сравнительный анализ методов оптимизации, то x* Сравнительный анализ методов оптимизации [a; x2] ;

если Сравнительный анализ методов оптимизации, то x* Сравнительный анализ методов оптимизации [x1; b],


где х* - одна из точек минимума f (x) на отрезке [a; b].


1.5 Выпуклые функции


Функция f (x), заданная на отрезке [a; b], называется выпуклой на этом отрезке, если для всех х', х" Сравнительный анализ методов оптимизации [а; b] и произвольного числа Сравнительный анализ методов оптимизации [0; 1] выполняется неравенство


f [ax'+ (1- a) x"] Ј af (x') + (l - a) f (x"). (1)


Перечислим основные свойства выпуклых функций.

Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"] М [a; b] ее график расположен не выше хорды, проведенной через точки графика с абсциссами х' и х" (рисунок 2).


Сравнительный анализ методов оптимизации

Рисунок 2 - Взаимное расположение Сравнительный анализ методов оптимизации


Пусть х' и х" - произвольные точки отрезка [a; b], причем х' < х". Легко проверить, что при любом a О [0; 1] точка xa = ax’ + (1-a) x" лежит на отрезке [x’; х"] и при непрерывном изменении a от 0 до 1 пробегает этот отрезок от точки х" (при a = 0) до точки x' (при a = 1).

Рассмотрим хорду графика f (x), проходящую через точки (х',f (х')) и (х",f (х")). Ордината ya точки этой хорды, соответствующая абсциссе c, равна. Поэтому неравенство (1) графика выпуклой функции и хорды означает, что f (xa) Ј ya, т.е. при любом расположении xa, на отрезке [х'; х"] точка графика функции f (x) лежит не выше соответствующей точки хорды.

2. Из курса математического анализа известны следующие условия выпуклости функции:

а) для того чтобы дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы производная f ' (x) не убывала на [а; b] ;

б) для того чтобы дважды дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы при всех хО [а; b] выполнялось неравенство f " (x) і 0.

3 Условие выпуклости для дифференцируемой на отрезке [а; b] функции f (x) означает, что на этом отрезке любая касательная к графику f (x) лежит не выше этого графика (рисунок 3).


Сравнительный анализ методов оптимизации

Рисунок 3 - условие выпуклости


Уравнение касательной к графику f (х) в точке (x0, f (x0)), x0 О [а; b] имеет вид: у (х) =f (x0) +f ’ (x0) (x-x0). По формуле конечных приращений для любого хО [а; b] имеем: f (х) =f (x0) +f ’ (x) (x-x0), где точка x лежит между x и x0. Поэтому


f (х) - у (х) = [f ’ (x) - f ’ (x0)] (x-x0), хО [а; b],


откуда с учетом того, что производная f ’ (x) выпуклой функции не убывает, получаем:


f (x) -y (x) і 0 (2)


для всех хО [а; b].

4. Если f (x) - выпуклая дифференцируемая на отрезке [а; b] функция и в точке х* О [а; b] выполняется равенство


f ’ (x*) = 0 (3)


то х* является точкой глобального минимума f (х) на [а; b].

С учетом (3) уравнение касательной у (х) =f (х0) +f ’ (х0) (х-х0) к графику f (x) для точки x0 =х* принимает вид у (х) =f (x*). Поэтому из (2) следует, что f (x) Сравнительный анализ методов оптимизацииf (x*) для всех хО [а; b], т.е. х* - точка глобального минимума f (x).

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

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

5. Можно показать, что всякая выпуклая непрерывная на отрезке [а; b] функция является и унимодальной на этом отрезке. Обратное, вообще говоря, неверно (рисунок 4).


Сравнительный анализ методов оптимизации

Рисунок 4 - график унимодальной, но не выпуклой функции


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

2. Прямые методы безусловной оптимизации


Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции f (х) и ее производных в некоторых точках отрезка [а; b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].

Рассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х) ® min, xО En, которые опираются только на вычисление значений функции f (х), т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишь иметь возможность вычислять или измерять значения f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.

2.1 Прямые методы одномерной безусловной оптимизации


Методы исключения отрезков

Пусть а < x1<х2<b. Сравнив значения f (x) в точках x1 и х2 (пробных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х2], если Сравнительный анализ методов оптимизации или к отрезку m [x1; b] если Сравнительный анализ методов оптимизации (рисунок 5). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку минимума. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить Сравнительный анализ методов оптимизации, где Сравнительный анализ методов оптимизации - одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков.

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


Сравнительный анализ методов оптимизации

Рисунок 5 - Уменьшение отрезка поиска точки минимума методами исключения отрезков


2.1.1 Метод деления отрезка пополам (дихотомии)

Суть метода заключается в том, что заданный отрезок [а; b] делится пополам:


Сравнительный анализ методов оптимизации.


Затем в каждой из половин отрезка [а; с] и [с; b] выбираются по одной точке x1 и х2, в них вычисляются значения функций, производится сравнение полученных значений, и в результате сравнения устанавливается отрезок, в котором минимума быть не может. Откинув его, продолжаем ту же процедуру с полученным отрезком до тех пор, пока вновь полученный отрезок не станет меньше по длине некоторой наперед заданной величины:


Сравнительный анализ методов оптимизации.


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


Сравнительный анализ методов оптимизации (4)


где d > 0 - малое число.

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство Сравнительный анализ методов оптимизации.

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить середину отрезка и значения x1 и х2 по формулам (4). Вычислить f (x1) и f (x2).

Шаг 2. Сравнить f (x1) и f (x2). Если Сравнительный анализ методов оптимизации, то перейти к отрезку [а; x2], положив b = x2, иначе - к отрезку [x1; b], положив а = x1.

Шаг 3. Найти достигнутую точность Сравнительный анализ методов оптимизации. Если Сравнительный анализ методов оптимизации то перейти к следующей итерации, вернувшись к шагу 1. Если Сравнительный анализ методов оптимизации, то завершить поиск х*, перейдя к шагу 4.

Шаг 4. Положить


Сравнительный анализ методов оптимизации.


Замечания:

1. Число d из (4) выбирают на интервале (0; 2e) с учетом следующих соображений:

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

б) при чрезмерно малом d сравнение значений f (x) в точках x1 и х2, отличающихся на величину d, становится затруднительным. Поэтому выбор d должен быть согласован с точностью определения f (x) и с количеством верных десятичных знаков при задании аргумента х.

Пусть Сравнительный анализ методов оптимизации - погрешность счета. Тогда следует учитывать следующее условие:


Сравнительный анализ методов оптимизации.


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

Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и х2, обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1-t (рисунок 6).


Сравнительный анализ методов оптимизации

Рисунок 6 - Определение пробных точек в методе золотого сечения


Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2ў = 1-t нового отрезка [0; t]. Чтобы точки х2 = t, и х2ў = 1-t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство Сравнительный анализ методов оптимизации или Сравнительный анализ методов оптимизации, откуда находим положительное значение


Сравнительный анализ методов оптимизации


Таким образом,


х1 = 1-t = Сравнительный анализ методов оптимизации, Сравнительный анализ методов оптимизации.


Для произвольного отрезка [а; b] выражения для пробных точек примут вид


Сравнительный анализ методов оптимизации; Сравнительный анализ методов оптимизации. (5)


Замечания:

1. Точки x1 и х2 из (5) обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (5) одна из них Сравнительный анализ методов оптимизации переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х2], то на него переходит пробная точка Сравнительный анализ методов оптимизации исходного отрезка, становясь его второй пробной точкой (х2’= х1) (рисунок 6). В случае перехода к отрезку [х1; b] пробная точка Сравнительный анализ методов оптимизации исходного отрезка становится первой пробной точкой отрезка [х1; b].

3. Легко проверить, что х1=а+b-х2, и x2=а+b-х1. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (5).

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


Сравнительный анализ методов оптимизации.


Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х1 и х2 по формулам (5). Вычислить f (x1) и f (x2).

Шаг 2. Определить Сравнительный анализ методов оптимизации. Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) Ј f (x2) то положить b=x2, x2=x1, f (x2) Ј f (x1), x1=b-t (b-a) и вычислить f (x1), иначе - положить a=x1, x1= x2, f (x1) = f (x2), x2=b+t (b-a) и вычислить f (x2). Перейти к шагу 2.

Шаг 4. Окончание поиска: положить


Сравнительный анализ методов оптимизации, Сравнительный анализ методов оптимизации.


Сравнение методов исключения отрезков. При сравнении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.

Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e (N) нахождения точки х*, которую они обеспечивают в результате определения N значений f (x). Метод золотого сечения считают более точным, чем метод дихотомии, однако разница в точности в данном случае незначительна.

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

Пусть заданы следующие параметры:


Сравнительный анализ методов оптимизации


Примем Сравнительный анализ методов оптимизации и Сравнительный анализ методов оптимизации. Тогда Сравнительный анализ методов оптимизации (рисунок 7).


Сравнительный анализ методов оптимизации

Рисунок 7 - Поведение исходной функции на заданном отрезке


Проведем несколько итерации методом дихотомии:


Сравнительный анализ методов оптимизации


Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:


Сравнительный анализ методов оптимизации


Так как f (x1) > f (x2), то a: =x1, b оставляем прежним. Тогда на третьем шаге:


Сравнительный анализ методов оптимизации


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


Сравнительный анализ методов оптимизации

Рисунок 8 - Получение решения методом дихотомии


Для метода золотого сечения:


Сравнительный анализ методов оптимизации


Так как f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:


Сравнительный анализ методов оптимизации


Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда на третьем шаге:


Сравнительный анализ методов оптимизации


И так далее до тех пор, пока не достигнем указанной точности. Полный расчет представлен на рисунке 9. Листинг программы представлен в приложении А.


Сравнительный анализ методов оптимизации

Рисунок 9 - Получение решения методом золотого сечения

2.2 Методы безусловной минимизации функций многих переменных


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


2.2.1 Метод циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениям x1 и x2.


Сравнительный анализ методов оптимизации

Рисунок 10 - Циклический покоординатный спуск.


Опишем этот алгоритм.

Шаг 0. Выбрать х О En, критерий достижения точности e и шаг Сравнительный анализ методов оптимизации. Найти f (x1 (0),x2 (0)).

Шаг 1. Принять x1 (1) = x1 (0) +Сравнительный анализ методов оптимизации. Определить f (x1 (1),x2 (0)). Сравнить полученное значение с значением начальной функции. Если f (x1 (1),x2 (0)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (1),x2 (0)) > f (x1 (0),x2 (0)), то перейти к шагу 2.

Шаг 2. Принять x1 (1) = x1 (0) - Сравнительный анализ методов оптимизации. Определить f (x1 (1),x2 (0)). Сравнить полученное значение с значением начальной функции. Если f (x1 (1),x2 (0)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (1),x2 (0)) > f (x1 (0),x2 (0)), то перейти к шагу 3.

Шаг 3. Принять x2 (1) = x2 (0) +Сравнительный анализ методов оптимизации. Определить f (x1 (0),x2 (1)). Сравнить полученное значение с значением начальной функции. Если f (x1 (0),x2 (1)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (0),x2 (1)) > f (x1 (0),x2 (0)), то перейти к шагу 4.

Шаг 4. Принять x2 (1) = x2 (0) - Сравнительный анализ методов оптимизации. Определить f (x1 (0),x2 (1)). Сравнить полученное значение с значением начальной функции. Если f (x1 (0),x2 (1)) < f (x1 (0),x2 (0)), то перейти к шагу 4, если же f (x1 (0),x2 (1)) > f (x1 (0),x2 (0)), то принять исходную точку за минимум.

Шаг 5. Проверить условие достижения точности Сравнительный анализ методов оптимизации.

Если в процессе решения с шагом Сравнительный анализ методов оптимизации не получено решения, то принять Сравнительный анализ методов оптимизации


2.2.2 Алгоритм Хука-Дживса

Этот алгоритм содержит две основные процедуры:

а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);

б) перемещение в направлении убывания.


Сравнительный анализ методов оптимизации

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


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

Опишем один из алгоритмов данного метода.

Шаг 1. Выбираем начальную точку и находим в ней значение функции.

Шаг 2. Обозначим координаты начального вектора: Сравнительный анализ методов оптимизации.

Тогда, соответственно, угол направления движения


Сравнительный анализ методов оптимизации.


Рассчитываем координаты 4-х точек в окрестности начальной по следующим формулам:


Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации


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

Шаг 3. Сравниваем полученные значения с f (x1 (0),x2 (0)). Если какое-нибудь из них оказалось меньше значения функции в 0-й точке точке, то принимаем его за исходное и переходим к шагу 5.

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

Шаг 5. Проверить условие достижения точности


Сравнительный анализ методов оптимизации.


Если данное условие не выполнено, возвращаемся к шагу 2.

2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации

Пусть заданы следующие условия:


Сравнительный анализ методов оптимизации


Тогда по методу циклического покоординатного спуска будет выполнен счет следующего вида:


Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации


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


Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации,


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


Сравнительный анализ методов оптимизации


Результаты работы данного алгоритма представлены на рисунке 12. Листинг программы приведен в приложении Б.


Сравнительный анализ методов оптимизации

Рисунок 12 - Решение поставленной задачи методом спуска


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

Тогда, соответственно, угол направления движения


Сравнительный анализ методов оптимизации.


Найдем значения функции 4-х точек в окрестности начальной:


Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации


Минимальное значение функция принимает в точке2, поэтому движемся в заданном направлении 2 пока идет уменьшение функции до достижения указанной точности, в противном случае уменьшаем шаг


(Сравнительный анализ методов оптимизации):

Сравнительный анализ методов оптимизации


Конечный результат получен на ЭВМ за 36 итераций. Результат представлен на рисунке 13. Листинг программы приведен в приложении Б.


Сравнительный анализ методов оптимизации

Рисунок 12 - Решение поставленной задачи методом спуска


2.2.4 Минимизация по правильному симплексу

Правильным симплексом в пространстве En называется множество из n + 1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.

В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 - правильного тетраэдра.

Если х0 - одна из вершин правильного симплекса в En то координаты остальных п вершин х1,. ., хn можно найти, например, по формулам:


Сравнительный анализ методов оптимизации (6), где

d1 Сравнительный анализ методов оптимизации, d2 Сравнительный анализ методов оптимизации,


a- длина ребра. Вершину х0 симплекса, построенного по формулам (6), будем называть бaзовой. В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой-либо вершины, например, хk симметрично относительно центра тяжести хc остальных вершин симплекса. Новая и старая вершины Сравнительный анализ методов оптимизациии хk связаны соотношением:


Сравнительный анализ методов оптимизации, где xcСравнительный анализ методов оптимизации.


В результате получается новый правильный симплекс с тем же ребром и вершинами Сравнительный анализ методов оптимизации=2xc - хk, хi, i= 0,. ., n, i№ k. Таким образом, происходит перемещение симплекса в пространстве Еn. На рисунке 13 представлена иллюстрация этого свойства симплекса в пространстве Е2.

Сравнительный анализ методов оптимизации

Рисунок 13 - Построение нового симплексa в E2 отрaжением точки х: a - нaчaльный симплекс х0, х1, Сравнительный анализ методов оптимизации; б - новый симплекс х0, х1, Сравнительный анализ методов оптимизации; центр отрaжения - точкa xc = (х0+ х1) /2


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

Шаг 0. Выбрать параметр точности e, базовую точку х0, ребро Сравнительный анализ методов оптимизации и построить начальный симплекс по формулам:


Сравнительный анализ методов оптимизации


Вычислить f (х1 (0),x2 (0)).

Шаг 1. Вычислить значения f (х) в вершинах симплекса х1,. ., xn.

Шаг 2. Упорядочить вершины симплекса х0,. ., хn так, что бы f (х1 (0),x2


(0)) Ј …Ј Јf (х1) Ј f (хn-1) Ј f (хn).


Шаг 3. Найти среднее значение функции:


Сравнительный анализ методов оптимизации.


Проверить условие Сравнительный анализ методов оптимизации из учета того, что:


Сравнительный анализ методов оптимизации (3.38)


Если оно выполнено, то вычисления прекратить, полагая х* » х0, f * » f (x0). В противном случае перейти к шагу 4.

Шаг 4. Найти


Сравнительный анализ методов оптимизации


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


Сравнительный анализ методов оптимизации.


Тогда отраженная вершина будет иметь вид:


Сравнительный анализ методов оптимизации.


Если f (Е) <f (xn), то перейти к построению нового симплекса, иначе - перейти к шагу 5.

Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром (редуцирование), считая базовой вершиной х0. Остальные n вершин симплекса найти по формуле хi = (хi + х0) /2, i=1,. ., n. Перейти к шагу 1.

Геометрическая иллюстрация работы алгоритма в пространстве показана на рисунке 14, где точки х0, х1, х2 - вершины начального симплекса, а пунктиром указаны процедуры отражения.


Сравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации

Рисунок 14 - Поиск точки минимума функции Сравнительный анализ методов оптимизациис помощью правильных симплексов в пространстве Сравнительный анализ методов оптимизации


Замечания:

1. Следует иметь в виду, что если функция f (х) многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума f (х).

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

2.2.5 Поиск точки минимума по деформируемому симплексу

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


Сравнительный анализ методов оптимизации (7)


Геометрическая иллюстрация этих процедур для пространства E2 приведена на рисунках 15 и 16.


Сравнительный анализ методов оптимизации

Рисунок 15 - Пробные точки z1,z2,z3,z4 для перехода к новому симплексу


Сравнительный анализ методов оптимизации

Рисунок 16 - Новые симлексы, полученные в результате процедур сжатия (а, б); отражения (в); растяжения (г).


Так как величина a О (0;

1), то выбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве En для n Ј 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х0 О En, по формулам


Сравнительный анализ методов оптимизации, (8)


где e i - i-й базисный вектор; a- параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi в формулах (9): a = 1/2, b = 1 и g =2.

Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовую точку х0, параметр a и построить начальный симплекс. Вычислить f (х0).

Шаг 1. Вычислить значения функции в вершинах симплекса х1,..., xn.

Шаг 2. Упорядочить вершины х0,..., xn так, чтобы f (х0) Ј … Ј f (хn).

Шаг 3. Проверить достижение заданной точности. Если оно выполняется, то вычисления завершить, полагая х * » х0, f * » f (х0). Иначе - перейти к шагу 4.

Шаг 4. Найти Сравнительный анализ методов оптимизациии пробные точки zk, k=1, …, 4 пo формулам (9). Найти f (z*) = min f (zk). Если f (z*) < f (zn). то положить xn=z* и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Уменьшить симплекс, полагая хi = (хi + х0) /2, i = 1,. ., n и перейти к шагу 1.

Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки х0 снова строят симплекс, полагая а = ||x0-xn||.

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


2.2.6 Практическая реализация симплексных методов

Пусть заданы следующие условия:


Сравнительный анализ методов оптимизации


Для первой вершины:


Сравнительный анализ методов оптимизации


Для второй вершины:


Сравнительный анализ методов оптимизации


Для третьей вершины:


Сравнительный анализ методов оптимизации


Наибольшее значение функция принимает в точке2, ее и будем отражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:


Сравнительный анализ методов оптимизации


Рассмотрим метод симплекса.

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


Сравнительный анализ методов оптимизации


Т. к. Сравнительный анализ методов оптимизации, то строим новый симплекс на вершинах Е,1 и 3 и повторяем эту операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса.

Результат рабочей программы представлен на рисунке 17. Листинг приведен в приложении В.


Сравнительный анализ методов оптимизации

Рисунок 17 - Практическая реализация симплекс-метода


Перейдем к методу деформируемого симплекса.

Введем коэффициенты уменьшения и увеличения: Сравнительный анализ методов оптимизации.

Найдем значения функции 4-х точек в окрестности начальной:


Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации


Минимальное значение функция принимает в точке1, поэтому строим новый симплекс на вершинах Е,1 и 3 и повторяем выше указанную операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса. Результат рабочей программы представлен на рисунке 18. Листинг приведен в приложении В.


Сравнительный анализ методов оптимизации

Рисунок 18 - Практическая реализация метода деформируемого симплекса


3. Условная оптимизация


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

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


Сравнительный анализ методов оптимизации


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

Рассмотрим 2 метода решения задачи условной оптимизации:

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

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

Например:


Сравнительный анализ методов оптимизации


где R - параметр штрафа (некое число).

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


Сравнительный анализ методов оптимизации


В данном курсовом проекте необходимо было максимизировать объемное тело, представленное на рисунке 19.


Сравнительный анализ методов оптимизации

Рисунок 19 - Объем, который необходимо максимизировать


Указанное тело состоит из цилиндра и стоящего на нем сегмента сферы. Определим изменяемые параметры для данного случая (рисунок 20): r - радиус цилиндра (равен радиусу сферы), h - высота сегмента сферы и h2 - высота цилиндра.


Сравнительный анализ методов оптимизации

Рисунок 20 - Изменяемые параметры


Для цилиндра: Сравнительный анализ методов оптимизации.

Для сегмента: Сравнительный анализ методов оптимизации

Тогда для всей фигуры: Сравнительный анализ методов оптимизации

Пусть площадь всего объема равна 200: Сравнительный анализ методов оптимизации


Выразим из формулы общей площади параметр h2:


Сравнительный анализ методов оптимизации.


Подставим полученное выражение в формулу объема, получим:


Сравнительный анализ методов оптимизации


Обозначим r=3 и h=1. Затем следует провести двумерную оптимизацию. Ниже на рисунке 21 приведена рабочая форма программы, реализующая двумерную оптимизацию для первого случая и трехмерную - для штрафных функций по методу координатного спуска.

Для указанного случая V=260.799603505204 при r*=4.06250000000002 и h*=0.975.

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


Сравнительный анализ методов оптимизации


где с -площадь.

Таким образом, следует провести трехмерную оптимизацию для следующей функции:


Сравнительный анализ методов оптимизации


Изменяемыми параметрами в данном случае являлись r - радиус цилиндра и сферы, h - высота сегмента и h2 - высота цилиндра.

Для второго случая V=260.778443852174 при r*=4.44999999999999, h*=1.025 и h2*=4.05.

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


Сравнительный анализ методов оптимизации

Рисунок 21 - Условная оптимизация


4. Линейное программирование


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


Сравнительный анализ методов оптимизации


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

Они широко распространены, поэтому будут подробно рассматриваться в рамках данного курсового проекта.

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


Сравнительный анализ методов оптимизации


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

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


Сравнительный анализ методов оптимизации


Система уравнений является базисной, то есть ранг матрицы равняется L-числу строк. Понятно, что L <N, где N - число переменных. Если же L =N, то при условии базисности допустимая область превращается в точку.

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

Рассмотрим ограничения:


Сравнительный анализ методов оптимизации.


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

Запишем базисную систему в виде:


Сравнительный анализ методов оптимизации


Поскольку Rang (AБ) = L, то можно сказать, что матрица Сравнительный анализ методов оптимизации существует.

Тогда


Сравнительный анализ методов оптимизации, а Сравнительный анализ методов оптимизации


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

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

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

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

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

Оно не превышает


Сравнительный анализ методов оптимизации.


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

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

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

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

Если в задаче N переменных и L ограничений (Сравнительный анализ методов оптимизации), то целевая функция имеет вид:


Сравнительный анализ методов оптимизации


Разделим Г на 2 части: Г (ГБГS). Тогда целевая функция будет выглядеть как:


Сравнительный анализ методов оптимизации


В начальной допустимой базисной точке, как известно, YS=0. Следовательно,


Сравнительный анализ методов оптимизации


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


Сравнительный анализ методов оптимизации.


Метод выбора столбца, вводимого в базис и выбора строки переменной, выводимой из базиса, сведем в так называемую симплекс-таблицу.

Рассмотрим следующую задачу:


Сравнительный анализ методов оптимизации


Параметр k в этом случае - подбираемый коэффициент, величина которого оказалась: k=7.

Рассмотрим геометрический способ решения задачи линейного программирования. Запишем для данного случая:


Сравнительный анализ методов оптимизации


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


Сравнительный анализ методов оптимизации


Оптимальное решение соответствует прямой, параллельной fнач. и проходящей через самую дальнюю от fнач. точку допустимого множества. Из графика видно, что оптимальная точка x* (1.8, 1.14375) находится на пересечении g1 (x1) и g2 (x2). Значение функции в этой точке: f (x*) =15.375.

Для решения данной задачи с помощью симплекс-таблиц перепишем исходную систему в следующем виде:


Сравнительный анализ методов оптимизации


Тогда симплекс-таблица на 0-й итерации примет вид:


Значение y1 y2 y3 y4 y5
y3 8 1 4 1 0 0
y4

12

6

1 0 1 0
y5 7 2 3 0 0 1
-f 0 6 4 0 0 0

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

Под симплекс-разностью понимаются элементы, стоящие в строке -f на пересечении с соответствующей переменной yi. В данном случае наибольшую положительную симплекс-разность, равную 6, имеет переменная y1.

Далее выбираем ту переменную, которая выводится из базиса. Выбирается та переменная из базиса, у которой элемент на пересечении строки базисной переменной или столбца вводимой в базис переменной (y1) положителен.

Для данного случая это переменные y3,y4,y5.

Проведем сравнение отношений элемента столбца y1 к соответствующему элементу столбца значений: Сравнительный анализ методов оптимизации - наибольшее отношение.

Следовательно, из базиса выводится переменная y4.

Перейдем к первой итерации. Элемент, стоящий на пересечении выводимой строки и столбца вводимой переменной, называется ведущим элементом.

На месте ведущего элемента на текущей итерации запишем 1, а все остальные элементы равны 0:


Значение y1 y2 y3 y4 y5
y3
0.0000



y1
1.0000



y5
0.0000



-f
0.0000




Заполним строку y1. Для этого строку y4 0-й итерации разделим на 6:


Значение y1 y2 y3 y4 y5
y3
0.0000



y1 2.0000 1.0000 0.1667 0.0000 0.1667 0.0000
y5
0.0000



-f
0.0000




Для того, чтобы заполнить строки итерации 1, используем строку y1 итерации 1 и соответствующие строки итерации 0.

Таким образом, симплекс-таблица на первой итерации будет иметь вид:


Значение y1 y2 y3 y4 y5
y3 6.0000 0.0000 3.8333 1.0000 -0.1667 0.0000
y1 2.0000 1.0000 0.1667 0.0000 0.1667 0.0000
y5 3.0000 0.0000 2.6667 0.0000 -0.3333 1.0000
-f -12.0000 0.0000 3.0000 0.0000 -1.0000 0.0000

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


Значение y1 y2 y3 y4 y5
y3 1.6875 0.0000 0.0000 1.0000 0.3125 -1.4375
y1 1.8125 1.0000 0.0000 0.0000 0.1875 -0.0625
y2

1.1250

0.0000

1.0000

0.0000

-0.1250

0.3750

-f

-15.3750

0.0000 0.0000 0.0000 -0.6250 -1.1250

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

Заключение


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

На основе данных нашего исследования были разработаны программы для применения соответствующих методов.

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

Список использованной литературы


Турчак Л.И. Основы численных методов: Учеб. пособие. - М.: Наука, Гл. ред. физ. - мат. лит., 1978. - 320 с.

Щетинин Е.Ю. Математические методы оптимизации. Конспект лекций

Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М.: Мир, 1985 -509с.

Дегтярев Ю.И., "Исследование операций", Москва 1986.

Похожие работы:

  1. • Сравнительный анализ методов оптимизации
  2. • Сравнительный анализ методов оптимизации
  3. • Линейное и нелинейное программирование
  4. • Продвижение программного продукта на рынке
  5. • Вопросы выбора асcортимента товара для универмагов и торговых ...
  6. • Анализ и оценка эффективности производства
  7. • Управление процессами обслуживания на предприятиях питания
  8. • Внутренний финансовый контроль отраслей, предприятий ...
  9. • Производственно-экономическая деятельность ...
  10. • Учет и анализ денежных средств на примере ...
  11. • Государственное управление в современной России
  12. • Анализ и оценка процесса управления денежными ...
  13. • Анализ и оценка предпринимательской деятельности ...
  14. • Экзаменационные билеты по методам оптимизации за весенний ...
  15. • Методология сравнительного правоведения
  16. • Методы сравнительного анализа деятельности посреднических ...
  17. • Сравнительный анализ численных методов
  18. • Сравнительное правоведение: общая характеристика
  19. • Сравнительный исторический метод в языкознании
Смотреть все похожие работы
Рефетека ру refoteka@gmail.com