Государственный комитет рсфср по делам науки и высшей школы

Ленинградский ордена Ленина и ордена Октябрьской Революции Электротехнический институт им. В. И. Ульянова (Ленина)

Методические указания

к лабораторным работам

по дисциплине

"ИССЛЕДОВАНИЕ АЛГОРИТМОВ

ОПТИМИЗАЦИИ"

Санкт-Петербург - 1991

Государственный комитет РСФСР по делам науки и высшей школы

------------------

Ленинградский ордена Ленина и ордена Октябрьской Революции электротехнический институт имени В.И.Ульянова (Ленина)

-----------------------------------------------------------

Методические указания к лабораторным работам

по дисциплине

"ИССЛЕДОВАНИЕ АЛГОРИТМОВ

ОПТИМИЗАЦИИ"

Санкт-Петербург-1991

УДК 681.3

Методические указания к лабораторным работам по дисциплине "Исследование алгоритмов оптимизации» /Сост.: Н. Е. Барабанов, В.Э. Балтрашевич, А.А. Первозванский; ЛЭТИ,- С.-Пб,. 1991.- 32 с.

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

Предназначены для студентов специальностей 22.04 и 01.02.

Утверждено

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

Введение

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

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

Методические указания ориентированы на студентов специальнос­тей 22.04 "Программное обеспечение вычислительной техники и авто­матизированных систем" и 01.02 "Прикладная математика", изучающих дисциплину "Методы оптимизации".

Лабораторная работа I одномерная оптимизация

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

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

Рассматривается задача поиска минимума непрерывной функции одного аргумента на заданном интервале [А, В]. Без ограничения общности далее считаем А=0, B=1. При этом предполагаем, что функ­ция ƒ имеет внутри интервала [А, В] не более одного строгого ми­нимума (т.е. она унимодальна). Если же функция ƒ обладает не­сколькими локальными минимумами на интервале [А, В], то описывае­мые ниже методы приводят к локализации одного из этих минимумов.

- 3 -

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

Вначале его длина равна 1. Пусть после проведения nиспыта-­ ний для функции ƒ длина интервала неопределенности равнаL_n(ƒ). Выбор метода минимизации (т.е. способа указания точек, в которых будут вычисляться значения функции ƒ) определяется требованием минимизацийL_n(ƒ) для "наихудшей" функции ƒ, т.е. минимизацииmax{L_n(ƒ):ƒ непрерывна на [0,1]}=L_n.

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