Сравнение методов численного решения задач оптимизации

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

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО

ОБРАЗОВАНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН

САМАРКАНДСИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ АЛИШЕРА НАВОИ

МЕХАНИКО - МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА «ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ»

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

для получения академической степени магистра

по специальности

«5А480101 -Вычислительная математика»

на тему:

СРАВНЕНИЕ МЕТОДОВ ЧИСЛЕННОГО РЕШЕНИЯ

ЗАДАЧ ОПТИМИЗАЦИИ

КОСИМОВА ДИЛМУРОДА НАСИМОВИЧА

Самарканд - 2012

РЕЦЕНЗИЯ

на магистерскую диссертацию Косимова Д. на тему

«Сравнение методов численного решения задач оптимизации»

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

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

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

Диссертационная работа удовлетворяет всем требованиям, предъявляемым к магистерским диссертационным работам и заслуживает оценке 18 баллов.

Зав. кафедрой «Информационной

технологии» СамИЭС доц. Аликулов А.И.

ОТЗЫВ

на магистерскую диссертацию Косимова Д. на тему «Сравнение методов численного решения задач оптимизации»

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

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

В период работы над диссертационной работой Косимов Д. проявлял способности к творческой деятельности. Результаты являются новыми и получены самостоятельно.

Работа удовлетворяет всем требованиям и её автор, в случае успешной защиты, заслуживает оценке 27 баллов.

Научный руководитель: доц. Маматов Ш.С

ANNOTATSIYA

1-bobda ekstremumni topisning algoritmlari quyidagi metodlar uchun keltirilgan:

- minimumni passiv qidiruv algoritmi;

- minimumni aktiv qidiruv algoritmi;

- tekis blokli qidiruv algoritmi;

- oraliqni teng 2ga bo'lish algoritmi;

- dixotomiya metodi algoritmi;

- oltin kesim metodi algoritmi;

- urinmalar metodi algoritmi;

2-bobda “Сравнение методов оптимизации” nomli umumiy dastur tuzilgan va dastur algoritmining ishlash qoidalari bayon qilingan. Dastur 4 ta metod uchun tuzilgan: teng 2 ga bo'lish, oltin kesim va parabolik approksimatsiyalah metodlari.

Dastur javobida kesmaning o'rtasi, optimallik mezoni va iteratsiyalar soni ko'rsatiladi.

Dastur Dellphi7 algoritmik tilida tuzildi.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. СРАВНЕНИЕ МЕТОДОВ ОДНОМЕРНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

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

1.2 Алгоритм пассивного поиска минимума

1.3 Алгоритм активного поиска минимума

1.4 Методы поиска, основанные на аппроксимации целевой функции

ГЛАВА 2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СРАВНЕНИЯ МЕТОДОВ ОПТИМИЗАЦИИ

2.1 Назначение и анализ использования разработки

2.2 Постановка задачи. Входная и выходная информация

2.3 Описание алгоритма

2.4 Описание процесса отладки программы

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ВВЕДЕНИЕ

оптимизация функция целевой аппроксимация

Методы оптимизации очень широко используются на практике [1,5,7,8,12].

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

1. По размерности решаемой задачи: одномерные и многомерные.

2. По способу формирования шага многомерные методы делятся на следующие виды:

2.1. Градиентные.

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

· по алгоритму коррекции шага;

· по алгоритму вычисления новой точки: одношаговые и многошаговые.

2.2. Безградиентные: с поочередным изменением переменных и с одновременным изменением переменных.

2.3. Случайного поиска: с чисто случайной стратегией и со смешанной стратегией.

3. По наличию активных ограничений.

3.1. Без ограничений (безусловные).

3.2. С ограничениями (условные):

· с ограничениями типа равенств;

· с ограничениями типа неравенств;

· смешанные.

Методы одномерной оптимизации являются базой для некоторых «многомерных» методов [6, 9, 10, 13-16]. В многомерной градиентной оптимизации строится улучшающая последовательность в зависимости от скорости изменения критерия по различным направлениям. При этом под улучшающей последовательностью понимается такая последовательность х₀, х₁,... , х_i, ..., в каждой точке которой значение критерия оптимальности лучше, чем в предыдущей. В безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента).

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

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы [5, 8, 12, 23, 25]:

· Методы исследования функций классического анализа;

· Методы, основанные на использовании неопределенных множителей Лагранжа;

· вариационное исчисление;

· динамическое программирование;

· принцип максимума;

· линейное программирование;

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

Как правило, нельзя рекомендовать какой либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике. Одни методы в этом отношении являются более общими, другие менее общими. Наконец, цeлью группу методов (методы исследования функций классического анализа, метод множителей Лагранжа, методы нелинейного программирования) на определенных этапах решения оптимальной задачи можно применять в сочетании с другими, например динамическим программированием или принципом максимума [20-22, 26-29].

В данной магистерской диссертации рассматривается задачи сравнение методов одномерной оптимизации.

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

Цель и задачи работы. Целью настоящей работы является знакомство с оптимизационными задачами, изучение различных методов одномерной оптимизации, сравнение различных методов одномерной оптимизации и сравнение эффективности их решения для целевой функции R(x)=D sin(Ax^B + C) на интервале от [-1; 2] с погрешностью в 0.05.

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

1) метод сканирования,

2) метод деления пополам,

3) метод золотого сечения,

4) метод параболической аппроксимации.

В ответе должны выводиться: середина отрезка, критерий оптимальности и количество итераций.

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

Степень разработанности задачи. Создан программа «Сравнение методов оптимизации», предназначенная для решения задач оптимизации численными методами: метод сканирования; метод деления пополам; метод золотого сечения; метод параболической аппроксимации.

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

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

Методы исследования. Задача оптимизации решается следующими методами одномерной оптимизации:

1) метод сканирования,

2) метод деления пополам,

3) метод золотого сечения,

4) метод параболической аппроксимации.

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

Структура работа. Работа состоит из введения, двух глав, заключение и списка используемых литератур. Общий объём работы составляет 70 страниц.

ГЛАВА 1.

СРАВНЕНИЕ МЕТОДОВ ОДНОМЕРНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

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

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

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

Однако возьмем другой пример. Допустим, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где разместить остановки? И так далее.

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

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

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

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

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

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

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

Поиск экстремума функций одной переменной имеет самостоятельный интерес, так как является составной частью многих методов многомерной оптимизмации. От правильной организации одномерного поиска существенно зависит успех решения всей задачи. Кроме того, одномерная оптимизация, будучи простой по формулировке задачей, позволяет легко войти в общию проблематику оптимизационных задач [14-16].

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

=

где Х-множество допустимых точек, среди которых ищется точка .

Другая распространенная запись задачи минимизации.

Когда X = R, мы имеем дело с одномерной безусловной задачей минимизацииц, т.е. когда целевая функция имеет только один простой аргумент и область Х есть вся вещественная ось чисел.

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

Определение: Функция называется унимодальной на если существует такая точка Є,что

()>(),если <<,,Є,

()<(),если <<, ,Є,

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

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

Определение: ) называется выпуклой на Х=(a,b) если

(б +(1-б))?б()+(1- б) f() при любых ,Є, и всех б, 0?б<1.

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

1.2 Алгоритм пассивного поиска минимума

Отрезок ) исходный отрезок неопределенности. Пусть N-число точек, в которых необходимо провести вычисления целевой функции f(х), т.е. N экспериментов. Точки, в которых необходимо провести эксперименты, определяются следующим образом:

· Если_ - нечётное, то =а+; =1,2,3,…

· Если _-чётное, то =a+; =-; =1,2,…,k

Среди вычисленных значений {f(=)} (), ищется точка ,в которой достигаются минимум:

Найденная точка принимается за приближенное решение задачи =. Исходный отрезок неопределенности [a,b] после экспериментов [], в N точках сужается до [], длина которого

(,,…,)=

Точность найденного решения равно половине отрезка неопределенности, т.е.,где и - точное решение.

1.3 Алгоритм активного поиска минимума

В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учётом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начнем с методов блочного поиска, которое сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объедини в блоке, в каждом из которых проводится одновременно n, экспериментов, общее число экспериментов, будет N), т.е. блок-это совокупность из нескольких экспериментов, которые проводятся одновременного (пассивный поиск).

Результаты, полученные в ()-м блоке{j=1,2,…,} (последовательный поиск). Если размере блоков равны единице, т.е. то мы имеем обычный последовательный алгоритм поиска.

1.3.1 Алгоритм равномерного блочного поиска.

Схема алгоритма

Шаг 1.Задаются исходный отрезок неопределенности - точность приближенного решения число экспериментов

В блоке n - нечётное(). Проводим эксперимент в средине отрезка [а,b], т.е. вычисляем где

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

следовательно точное значение минимума содержится на отрезке [].

Шаг 3. Полагаем а = , b = +1, = =. Если b-а, то , = и поиск заканчивается. Иначе перeйти к шагу 2. Если заданная точностъ достигнута после m итераций, т.е. после экспериментов в m блоках, то длина отрезка неопределённоcти после всех n вычислений

(

будет:

Ln= и Ln

1.3.2 Алгоритм деления интервал пополам

Это вариант предыдущего алгоритма при

Схема алгоритма

Шаг 1. Задаются a,b,е. Производим эксперимент в точке x₂=(a+b)/2, т.е. вычисляем y_n = f(x_n).

Шаг 2. Производим эксперименты в остальных точках блока:

Находим x_j такую, что

=.

Тогда точное решение содержится на отрезке [x_j-1, x_j+1].

Предполагается x₀ = a, x₄ = b.

Шаг 3. Пологаем а=х_j-1, b= х_j+1, =Если

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

==,

где [z] - целая часть числa z .

Следовательно, достигнутая точность будет

|х*-x Ю |,

1.3.3 Метод дихотомии

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

Схема алгоритма

Шаг 1. Задаются а,b, и малое положительное число, значительно меньшее чем

Шаг 2. Определяется середина отрезка x=(a+b)/2. Производятся эксперименты в двух точках, близких к середине:

Шаг 3. Определяется следующей отрезок локализации, т.е. определяется какой из отрезков ] содержит точное решение Если , то это отрезок [ т.е выбранный отрезок локализации мы снова обозначили как [а,b].

Шаг 4. Если , то , ) и поиск заканчивается. Иначе перейти к шагу 2.

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

+

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

А теперь перейдём к рассмотрению чисто последовательных методов поиска.

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

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

В результате этих двух экспериментов отрезок неопределённости сузится до отрезка [] или []. Так как у нас нет никаких оснований предпочесть один из этих вариантов, то точки и должны быть симметричны относительно середины отрезка В этом случае длины отрезков [] и [].] будут равны. Таким образом, остаётся вопрос как выбрать точку (см. рис.1).

Рис.1

В методе золотого сечения точка x₁ выбирается из соображения, что должно выполняется соотношение:

==

т.е. делит отрезок по правилу и “золотого сечения ”, где есть “золотое отношение”. Точка x₂ определяется как точка симметричная к x₁ относительно середины отрезка.

В результате экспериментов у нас получается отрезок неопределённости , содержащий точку , или отрезок неопределённости,], содержащий точку .

1.4 Методы поиска, основанные на аппроксимации целевой функции

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

1.4.1 Метод касательных.

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

) + ()

в точке а и касательной () = f(+()( в точке

Полученная аппроксимирующая функция есть ломаная, состоящая из прямой () на [] и () на[], где с - точка пересечения касательных (см. рис 2). Легко заметить что при минимум аппроксимирующей функции достигается в точке с. Значение точки пересечения с можно определить по формуле

,

В точке производятся вычисления. Если = 0, то решением задачи будет = c. Если же > 0, то в качестве следующего отрезка неопределённости будет [a,c]. Если же < 0, то - отрезок Процесс повторяется до тех пор пока = 0, или отрезок не определенности не достигнет заданной точности.

Рис.2

Шаг 1. Заданы a,b,е вычислить=), =, =, =

Шаг 2. Заданы 2е, то получаем = , = (). Поиск окончен.

Если то вычислить с = , y=f(c), z=

Если z =0, то полагаем = с, = y и поиск окончен.

Если то ,

Повторить шаг 2.

1.4.2 Метод парабол

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

)

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

+

Причем Эта точка выбирается в качестве точки очередного вычисления значения функции (см. рис. 3 и 4).

Рис.3

Рис.4

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

x=

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

В силу унимодальности функции и зависимости от выполнения или невыполнение условий , , .

Это будут отрезки с точкой внутри

(смотри рис.4). Далее строится парабола, определяется ее минимум, и т.д, до тех пор пока длина отрезка неопределенности не удовлетворяет заданной точности. (см. рис.5)

Схема алгоритма.

Шаг 1. Задаются . Вычислить =,==

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

+

Шаг 3.

а) При

· Если , то ==.

· Если , то , =.

· Если , то , ,==

b) При

· Если , то , ==.

· Если , то =.

· Если , то =c, , ,==

Шаг 4. Если , то закончить поиск, положив = , = иначе перейти к шагу 2.

Рис.5

Все эти алгоритмы реализованы нижеприведенными программами [2-4].

ПРОГРАММЫ РЕАЛИЗАЦИИ РАСЧЕТОВ

1. Программа для метода золотого сечения

//Для n=2

#inclyde<iostream.>

#inclyde<math.h>

#inclyde<windows>

Void main()

{

Float a.b.t//пункт№1

Int h.N

Float E,xp,yp,x1,y1,x2,y2

a=0;

b=1

cout<<”N=”

cin>>N;

t=(1+sqrt(5))/2;

h=0

x1=a+(b-a)/pow(t,2);

y1=x1*x1*x1*x1-1.5*atan(x2);

h=h+2

do if(y1<y2){b=x2;x2=x1;y2=y1;x1=a+b-x2;

yl=x1*x1*x1*x1-1.5*atan(x1);h=h+1;

}

else{a=x1;x1=x2;y1=y2:

x2=a+b-x1;y2=x2*x2*x2*-1.5*atan(x2);h=h+1;

}

}

Wlhile(h<=N);// Пункт№7

{if(y1<y2)b=x2;

else a=x1

xp=(a+b)/2;

yp=xp*xp*xp*xp*-1.5*atan(xp);

E=(b-a)/2;

cout << “xp=”<<xp<<endl;

cout << “xp=”<<yp<<endl;

cout<<”E=”<<E<< endl;

system (“pause”);

2. Программа для метода Фибоначчи

#inclyde<iostream.>

#inclyde<math.h>

#inclyde<windows>

Void main()

{

float a,b,d,t*F,x1,x2,y1,y2 xp,yp;// пункт№1

int N,I;

float E;

a=0;

b=1;

cout<<”N=”

cin>>N;

t=(1+sqrt(5))/2;

F[0]=1;

F[1] =1;

For(i=2,i<=N;i++) F[i]=F[i-2];

D=(b-a)*(F[N-2]/F[N]);

y1=x1*x1*x1*x1-1.5*atan(x1);

x2=a+(b-a)*(F[N-1]/F[N];

y2=x2*x2*x2*x2*-1.5*atan(x2);

3. Программа для метода деления интервала пополам

#1)Для n=3

#include<iostream.h>

# include<math.h>

# include<windows.h>

Void main()

| Float a,b;//пупкт №1

Int I,h,N,n,f;

Float min .E,xp,yp.*x.*y;

a=0;

b=1:

cout<<”N=”>;

cin>>N;

n=3;

x=new float[n+2]

y= new float[n+2]

x[2]=[a+b]/2;

y[2]=x[2]*x[2] *x[2] *x[2]-1.5*atan(x[2]);

h=l;

do

|X[1]=(a+x[2])/2;

Y[1]=x[1]*x[1] *x[1] *x[1]-1.5*atan(x[1]);

X[3]=(x[2]+b)/2;

Y[3]=x[3]*x[3] *x[3] *x[3]-1.5*atan(x[3]);

H=h+2

X[0]=a;

X[n+1]=b

Min=y[1];

F=1;

For(i=1;i<=n;i++)

If(y[i]<min){min=y[i]; f=I;}

A=x[f-1];

Yp=xp *xp* xp* xp-1.5*atan(xp);

E=(b-a)/2

Cout<<”xp=”<<xp<<endl;

Cout<<”yp=”<<yp<<endl;

Cout<<”E=”<<E<<endl;

System(“pause”);

БЛОК СХЕМЫ

1. Пассивный метод

2. Алгоритм для блочного метода



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

4. Метод Фибоначчи

5. Метод деления интервала пополам

ГЛAВA 2.

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СРАВНЕНИЯ

МЕТОДОВ ОПТИМИЗАЦИИ

2.1 Назначение и анализ использования разработки

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

В данной программе решается уравнение вида R(x)=D sin(Ax^B + C) на интервале от [-1; 2] с погрешностью в 0.05

2.2 Постановка задачи. Входная и выходная информация

Рассмотрим методы решения одномерных задач оптимизации вида R(x) > max, где а ? х ? b, где х - скаляр, а и b - соответственно минимальное и максимальное возможные значения переменной х.

Будем рассматривать алгоритмы, связанные с построением улучшающей последовательности. Решением задачи называется х*, при котором R(x*) ? R(x) для любого значения а ? х ? b. При решении задач не будем различать два значения х_i , и х_i+1, если |х_i - х_i+1|? , где - задаваемая погрешность решения.

Метод сканирования. Заключается в последовательном переборе всех значений а ? х ? b c шагом (погрешность решения) с вычислением критерия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х*.

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

На практике можно реализовать одну из основных модификаций метода - последовательное уточнение решения, или сканирование с переменным шагом (см. рис. 1).

Рис. 1. Иллюстрация модифицированного метода сканирования: 1 - интервал, включающий в себя искомый максимум функции после первого этапа сканирования (исходный участок разбит на 5 участков); 2 - то же, после второго этапа.

На первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение R(x), разбивается на более мелкие отрезки, ищется, новый отрезок, внутри которого находится уточненное значение максимума.

Новый отрезок опять делится на более мелкие и т.д., до тех пор, пока величина отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого варианта метода - возможность пропуска «острого» глобального максимума R(x).

Метод деления пополам. Метод деления пополам основан на делении текущего отрезка [a, b], где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на /2, где - погрешность решения задачи оптимизации.

Если R(x + /2)>R(x - /2), то максимум располагается на правой половине текущего отрезка [a, b], в противном случае - на левой.

Процесс поиска завершается при достижении отрезком [a, b] величины заданной погрешности .

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

На рис. 2 приведены три этапа метода половинного деления. Сплошными вертикальными линиями отмечены середины отрезков, а пунктирными - вычисляемые значения критерия оптимальности слева и справа на /2 от середин.

Рис. 2. Иллюстрация метода половинного деления: 1 - интервал, включающий в себя искомый максимум функции после первого этапа (первого деления пополам); 2,3 - то же соответственно после второго.

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

После нахождения середины отрезка (например, точка с₁) в одной из половинок (допустим, в левой) находят среднюю точку (точка с₂) и, сравнивая значения функции в этих точках, определяют, в какой из половинок находится экстремум. Если R(c₁)<R(c₂), то в качестве следующего отрезка выбираем отрезок [а, c₁)], если же R(c₁)>R(c₂), то берут новую точку в середине правой половины (точка c₃) и в ней вычисляют функцию. В зависимости от сравнения значений функции в точках c₃ и c₁) выбирают новый отрезок [c₁, b] или [с₂, c₃] и т.д.

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

Метод золотого сечения. Рассмотрим метод золотого сечения:

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

ab/cb=cb/ac; ab/ad=ad/db;

Рис. 3. Иллюстрация метода - золотого сечения: 1 - интервал, включающий в себя искомый максимум функции после , первого (первого золотого сечения в точках с и d); 2 - то же, после второго этапа (новая точка е и старая точка d)

Путем сравнения R(c) и R(d) определяют следующий отрезок, где содержится максимум. Если R(d)>R(c), то в качестве следующего отрезка выбирается отрезок [c, b], в противном случае - отрезок [a, d].

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [a, b], т.е.

db/cd =cd/cb

Поэтому на каждой следующей итерации (кроме «запуска» метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.

Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение R(x):

Условие окончания поиска - величина отрезка, содержащего максимум, меньше заданной погрешности.

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

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

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

Метод параболической аппроксимации заключается в замене нелинейной функции R(x) квадратичной параболой R₂(х), построенной по трем точкам, принадлежащим R(x), с последующим нахождением max параболической функции, используя аналитические условия оптимальности:

dR/dx=0.

На первом этапе в качестве исходных трех точек используютcя x₁=a, x₂=b и x₃=(а+b)/2. В этих точках вычисляется R(x) и по полученным точкам R(x₁), R(x₂), R(x₃) строится парабола R₂=С₂х² +C₁х+С₀, коэффициенты которой находятся из решения соответствующей системы уравнений:

R₂(x₁)=R(х₁), R₂(х₂)=R(x₂), R₂(х₃)=R(x₃)

Условие оптимальности приводит к уравнению х₄ =-С₁/(2С₂), где х₄ - точка максимума параболы R₂(x). Далее выбирается новый отрезок, внутри которого находится точка х₄, и, используя х₃, х₄, строится новая парабола, по которой уточняется положение максимума R(x) и т.д. до тех пор, пока величина отрезка, внутри которого находится максимум, не будет меньше заданной погрешности . Таким образом, метод имеет итерационный характер. Можно строить параболу на каждом шаге и по трем последним точкам, но только в том случае, если точно известно, что функция гладкая и одно-экстремальная. В противном случае первый вариант даст лучший результат.

К достоинству метода относится высокая скорость сходимости к оптимуму, хотя метод может не всегда сходиться к нему.

На рис.4 приведены два случая применения метода параболической аппроксимации: а) рассмотрена ситуация, когда метод параболической аппроксимации сходится к решению, уже на третьем этапе парабола, построенная по точкам х₃, х₄, х₅, практически совпадает с исходной функцией; б) парабола не имеет максимума уже на втором этапе.

Рис. 4. Иллюстрация метода параболической аппроксимации: а - решение найти можно; б - решение найти нельзя; 1 - функция, экстремум которой ищется; 2 - аппроксимирующая парабола первого этапа, построенная по точкам х₁, х₂, х₃; 3 - аппроксимирующая парабола второго этапа, построенная по точкам х₂, х₃, х₄; х₃;- середина исходного интервала; х₂, х₄ - точка максимума первой параболы; х₅ - точка максимума второй параболы.

2.3 Описание алгоритма

Интерфейс созданной программы (рис. 5)- «Сравнение методов оптимизации» - состоит :

1) из семи полей ввода (вводятся значения A, B, C, D, погрешность и интервал (min и max));

2) из четырех переключателей ( * Метод сканирования, * Метод деления пополам, * Метод золотого сечения, * Метод параболической аппроксимации);

3) кнопки Вычислить;

4) поля, в котором будет выводиться ответ;

5) кнопки Выход, а так же главного меню;

6)

Рис 5. Интерфейс программы «Сравнение методов оптимизации»

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

Описание алгоритма при выборе переключателя «Метод сканирования»:

1) первым делом обнулим счетчик, который считает количество итераций (it:=0);

2) оформим цикл типа repeat - until (до тех пор пока):

· потом разбиваем отрезок на четыре части (Int:=(max-min)/4) и присваиваем некоторой переменной значение минимума (PER:=min);

· оформляем цикл для нахождения массива чисел (x[i]) на заданном интервале;

· на каждом интервале находим значение функции;

· находим максимальное значение;

· находим индекс максимального значения;

· некоторой новой переменной присваиваем значение x[k];

· вычисляем новые значения минимума и максимума;

· считаем количество итераций (it:=it+1);

3) на экран выводится ответ (рис. 6 ).

Рис 6. Приведены вычисления контрольной задачи «Методом сканирования

Приведем пример: дана функция R(x)=D sin(Ax^B+C), где коэффициенты имеют следующие значения: А=1,0, В=1,0, С=1,0, D=1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: =0,05.

Результаты расчетов. Разобьем весь интервал на четыре подинтервала (крупный шаг), координаты х будут следующими:

x₁=-0,25, x₂=0,5, x₃=1,25.

Соответственно значения критерия равны:

R₁=0,68163, R₂=0,9974, R₃=0,77807.

Следовательно, в качестве нового отрезка выбираем отрезок [-0,25; 1,25], так как внутри него находится максимальное значение:

x₀=0,5, R₀=0,99749499,

0 - номер итерации (после первого этапа). Разбиваем его снова на четыре части, имеем значения:

х₁=0,125, х₂=0,5, x₃=0,875.

Вычислив R(x) в этих точках, получим, что новый интервал, внутри которого лежит экстремум, равен [0,125ж 0,875].

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

Табл. №1 (Расчеты данных по этапам методом сканирования)

№	X	R
1	0,50000000	0,99749499
2	0,50000000	0,99749499
3	0,59375000	0,99973658
4	0,57031250	0,99999988
6	0,59375000	0,99973658

Всего проведено 6 · 3 = 18 вычислений критерия оптимальности.

Описание алгоритма при выборе переключателя «Метод деления пополам»:

1) обнулим счетчик который считает количество итераций (it:=0);

2) оформим цикл типа repeat - until (до тех пор пока):

· вычислим середину отрезка (ser) и точки стоящие от середины отрезка на еp/2 (G и H);

· далее вычисляем критерий оптимальности в этих точках (ser, H, G);

· проверяем условие, если критерии оптимальности от точки G больше критерия оптимальности чем от точки H (R1>R2), то минимальное значение равно середине отрезка (min:=ser);

· проверяем второе условие, если критерии оптимальности от точки G меньше критерия оптимальности чем от точки H (R1<R2), то максимальное значение равно середине отрезка (max:=ser);

· считаем количество итераций (it:=it+1);

· проверяем условие окончания вычислений - разница между максимумом и минимумом должна быть меньше заданной погрешности (until (max-min)<ep);

3) на экран выводится ответ (рис. 7).

Рис 7. Приведены вычисления контрольной задачи

«Методом деления пополам»

Приведем пример: дана функция R(x)=D sin(Ax^B+C), где коэффициенты имеют следующие значения: А=1,0, В=1,0, С=1,0, D=1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: =0,05.

Результаты расчетов. Середина отрезка x₀ =0,5000, значение критерия R₀=0,9975, значение

R(0,5 - /2) =R(0,475)=0,97922273, значение R(0,5+/2)=R(0,525)=0,9989513.

Следовательно, искомый максимум лежит в правой половине отрезка, т.е. теперь отрезком является [0,5; 2].

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

x1=1,25000000 R1=0,77807320 левый

х2=0,87500000 R2=0,95408578 левый

х3=0,68750000 R3=0,99319785 левый

x4=0,59375000 R4=0,99973658 левый

x5=0,54687500 R5=0,99971390

|x4 -х5|<, поэтому в качестве решения можно принять любое из этих значений или середину между ними.

Всего восемь раз (4 · 2 = 8) вычислялся критерий оптимальности (не считая вычислений непосредственно в середине отрезка, которые не используются в алгоритме метода).

Описание алгоритма при выборе переключателя «Метод золотого сечения»:

1) обнулим счетчик который считает количество итераций (it:=0);

2) оформим цикл типа repeat - until (до тех пор пока):

· некоторому числу m приравнивается минимум, а n - максимум;

· делим отрезок на неравные части по правилу золотого сечения (находим точки Lev и Prav);

· вычисляем критерий оптимальности в точках Lev и Prav;

· проверяем условие, при котором минимум отрезка принимает значение Prav - если критерий оптимальности от точки Lev больше критерия оптимальности от точки Prav;

· выводим на экран получившийся критерий оптимальности;

· проверяем второе условие, при котором максимум отрезка принимает значение Lev - если критерий оптимальности от точки Lev меньше критерия оптимальности от точки Prav;

· выводим на экран получившийся критерий оптимальности;

· считаем количество итераций (it:=it+1);

· проверяем условие окончания вычислений - разница между максимумом и минимумом должна быть меньше заданной погрешности (until (max-min)<ep);

4) на экран выводится ответ (рис. 8).

Рис 8. Приведены вычисления контрольной задачи «Методом золотого сечения»

Приведем пример: дана функция R(x)=D sin(Ax^B+C), где коэффициенты имеют следующие значения: А=1,0, В=1,0, С=1,0, D=1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: =0,05.

Результаты расчетов. Для «запуска» метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]:

х1 =0,145898, х2 =0,85410197.

Значения критериев в этих точках соответственно R(x1)=0,911080, R(x2)=0,960136. Следовательно, новым отрезком является [0,145898;2], внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрезка будет х3=0,58359214, a R(x3)=0,99991813.

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

х3=0,58359214 R3=0,99991813

х4=0,58359214 R4=0,99991813

x5=0,58359214 R5=0,99991813

x6=0,58359214 R6=0,99991813

х7=0,58359214 R7=0,99991813

x8=0,55920028 R8=0,99993277

x9=0,55920028 R9=0,99993277

Всего было проведено 10 вычислений критерия оптимальности.

Описание алгоритма при выборе переключателя «Метод параболической аппроксимации»:

1) обнулим счетчик который считает количество итераций (it:=0);

2) обнулим счетчик который считает сколько раз вычисляются коэффициенты параболы (i:=0);

3) рассчитываем середину отрезка (ser:=(max-min)/2+min);

4) оформим цикл типа repeat - until (до тех пор пока):

· вычисляем критерий оптимальности в точке min, max и ser (минимум, максимум и середина);

· находим общий делитель (dtl) - необходим чтобы использовать метод Крамера;

· методом Крамера находим коэффициенты X, Y, Z;

· находим коэффициенты параболы C0, C1, C2;

· считаем i:=i+1;

· приравниваем значению минимума значение середины (min:=ser);

· находим значение при котором парабола имеет максимум (Parab[i]:=-C1/(2*C2));

· считаем количество итераций (it:=it+1);

· проверяем условие окончания вычислений (until abs(Parab[i]-Parab[i-1])<ep) - разница между последним и предпоследним значениями должна быть меньше заданной погрешности;

5) выводится ответ (рис. 9).

Рис 9. Приведены вычисления контрольной задачи методом «параболической аппроксимации»

Приведем пример: дана функция R(x)=D sin(Ax^B+C), где коэффициенты имеют следующие значения: А=1,0, В=1,0, С=1,0, D=1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: =0,05.

...