Метод Зойтендейка

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

Приднестровский государственный университет им. Т.Г. Шевченко

Инженерно-технический институт

Кафедра информационных технологий и автоматизированного

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

Курсовая работа

по дисциплине «Методы оптимизации»

тема: «МЕТОД ЗОЙТЕНДЕЙКА»

Тирасполь, 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. МЕТОДЫ ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

2. МЕТОД ЗОЙТЕНДЕЙКА

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

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

2.3 Алгоритм

3. БЛОК СХЕМА АЛГОРИТМА МЕТОДА ЗОЙТЕНДНЙКА

4. КОНТРОЛЬНЫЙ ПРИМЕР

4.1 Аналитическое решение контрольного примера

4.2 Исследование поставленной задачи

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

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

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

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

1. углубление теоретических знаний по курсу «Методы оптимизации»;

2. развитие навыков самостоятельной творческой работы;

3. практическое использование методов оптимизации (метод Зойтендейка) для решения задачи минимума дважды непрерывно дифференцируемой функции ;

4. развитие навыков использования ЭВМ и языков программирования;

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

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

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

1. МЕТОДЫ ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

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

Прямые методы оперируют непосредственно с исходными задачами оптимизации и генерируют последовательности точек {x[k]}, таких, что f(х[k+1]) f(x[k]). В силу этого такие методы часто называют методами спуска. Математически переход на некотором k-м шаге (k. 0, 1, 2, ...) от точки х[k] к точке x[k+1] можно записать в следующем виде:

x[k+l] x[k] + akp[k],

где р[k] -- вектор, определяющий направление спуска; аk -- длина шага вдоль данного направления. При этом в одних алгоритмах прямых методов точки х[k] выбираются так, чтобы для них выполнялись все ограничения задачи, в других эти ограничения могут нарушаться на некоторых или всех итерациях. Таким образом, в прямых методах при выборе направления спуска ограничения, определяющие допустимую область G, учитываются в явном виде.

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

2. МЕТОД ЗОЙТЕНДЕЙКА

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

Найти минимум дважды непрерывно дифференцируемой функциипри условии, что вектор удовлетворяет ограничениям j=1,….,m, в которых функции x, т.е. такую точку , что

,

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

Стратегия решения методом Зойтендейка [Zoutendijk G.] состоит в построении последовательности допустимых точек {}, таких, что

Правило построения точек последовательности {}:

где точка - допустимая и такова, что

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

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

где величина определяется из условия а величина , удовлетворяет условиям:

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

Возможное направление спуска , удовлетворяет условиям, определяется из решения задачи линейного программирования

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

2.3 Алгоритм

Шаг 1. Задать , предельное число итераций M, допустимую начальную точку , в которой

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

Шаг 3. Проверить выполнения условия k?M:

а) если k=M, расчет закончен;

б) если k<M, перейти к шагу 4.

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

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

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

Шаг 6. Записать систему неравенств

Шаг 7. Сформировать задачу линейного программирования:

Шаг 8. Решить задачу линейного программирования, сформированную на шаге 7. В результате находится искомое возможное направление спуска -минимальное значение z.

Шаг 9. Вычислить шаг , решив задачу

для чего следует:

а) найти величину из условия

б) определить величину из условий

(если условие выполняется только при то не вычисляется). Если в точке ограничение с номером j активно и =0, то значение не вычисляется;

в) найти =

г) вычислить значение

Шаг 10. Найти точку .

Шаг 11. Вычислить величину

Шаг 12. Проверить условие окончания:

а) если , то расчет может быть либо закончен если точность удовлетворительна, либо продолжен при , . В первом случае - искомое приближенное решение задачи (10.14), во втором - следует перейти к шагу 3;

б) если , то положить k=k+1 и перейти к шагу 3.

программирование зойтендейк дифференцируемый функция

3. БЛОК СХЕМА АЛГОРИТМА МЕТОДА ЗОЙТЕНДЕЙКА

4. КОНТРОЛЬНЫЙ ПРИМЕР

4.1 Аналитическое решение контрольного примера

Задание: найти минимум в задаче

Решим задачу аналитически, задав при этом значения , . Полагаем что k=0, и проверяем условие

Итерация 0:

Вычислим . Подставим значения и получим:

Проверяем выполнение условия

Активным является ограничение

Записываем систему неравенств:

Имеем и

-8

Записываем задачу линейного программирования

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

.

Имеем

Решение задачи линейного программирования с использованием симплекс метода имеет вид

Поэтому

Вычислим шаг из условия. Имеем

а)

б)

поскольку второе ограничение активно и , величина не вычисляется;

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

в)

г)

Находим точку

.

Вычисляем

.

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

4.2 Исследование поставленной задачи

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

Оптимизация сводится к нахождению минимума указанной функции в сжатые сроки.

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. - М.: Высш. шк., 2002.

2. Амосов А.А. , Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров: Учеб. пособие. - М.: Высш. шк., 1994.

3. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. - М.: Изд-во МАИ, 1998.

4. Банди Б. Методы оптимизации. М.: Радио и связь. 1988.

5. Васильев Ф.П. Методы оптимизации - Издательство «Факториал Пресс», 2002.

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