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

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

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

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

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

 (7)

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

Рисунок 15 - Пробные точки z¹,z²,z³,z⁴ для перехода к новому симплексу

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

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

1), то выбор точек z¹ и z² соответствует сжатию симплекса; b » 1, поэтому выбор точки z³ соответствует отражению, а g > 1 и выбор точки z⁴ приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве E_n для n £ 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х⁰ Î E_n, по формулам

, (8)

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

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

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

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

Шаг 2. Упорядочить вершины х⁰,..., xⁿ так, чтобы f (х⁰) £ … £ f (хⁿ).

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

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

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

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

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

 

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). Тогда целевая функция будет выглядеть как:

В начальной допустимой базисной точке, как известно, Y_S=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

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

Под симплекс-разностью понимаются элементы, стоящие в строке -f на пересечении с соответствующей переменной y_i. В данном случае наибольшую положительную симплекс-разность, равную 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

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

Заключение

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

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

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

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

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

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

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

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