- •Государственный комитет рсфср по делам науки и высшей школы
- •Введение
- •Лабораторная работа I одномерная оптимизация
- •Постановка задачи
- •Краткие общие сведения Метод Пассивного поиска
- •Метод Фибоначчи
- •Метод золотого сечения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 3 симплексный метод
- •Постановка задачи
- •Краткие общие сидения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 4 решение прямой и двойственной задач
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Тексты исходных задач Вариант I
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Лабораторная работа 5 транспортная задача
- •Постановка задачи
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Лабораторная работа 6 задача 0 коммивояжере
- •Постановка задачи
- •Краткие общие сведения
- •Порядок проведения лабораторной работы
- •Требования к отчету
- •Контрольные вопросы
- •Содержание
- •197376, Санкт-Петербург, ул. Проф. Попова, 5
Государственный комитет рсфср по делам науки и высшей школы
Ленинградский ордена Ленина и ордена Октябрьской Революции Электротехнический институт им. В. И. Ульянова (Ленина)
Методические указания
к лабораторным работам
по дисциплине
"ИССЛЕДОВАНИЕ АЛГОРИТМОВ
ОПТИМИЗАЦИИ"
Санкт-Петербург - 1991
Государственный комитет РСФСР по делам науки и высшей школы
------------------
Ленинградский ордена Ленина и ордена Октябрьской Революции электротехнический институт имени В.И.Ульянова (Ленина)
-----------------------------------------------------------
Методические указания к лабораторным работам
по дисциплине
"ИССЛЕДОВАНИЕ АЛГОРИТМОВ
ОПТИМИЗАЦИИ"
Санкт-Петербург-1991
УДК 681.3
Методические указания к лабораторным работам по дисциплине "Исследование алгоритмов оптимизации» /Сост.: Н. Е. Барабанов, В.Э. Балтрашевич, А.А. Первозванский; ЛЭТИ,- С.-Пб,. 1991.- 32 с.
Рассматриваются вопросы использования различных методов минимизации функций.
Предназначены для студентов специальностей 22.04 и 01.02.
Утверждено
редакционно-издательским советом института в качестве методических указаний
Введение
"Методы оптимизации" - это раздел вычислительной математики, объединяющий методы и алгоритмы решения задач оптимизации функций, а также обосновывающие применение этих методов теоретические результаты. Особенностью этого раздела является огромное многообразие рассматриваемых в нем постановок задач и методов их решения: в диапазоне от классической теоремы Ферма, дающей критерий минимума функции одной переменной, до современных методов решения больших прикладных задач, требующих перебора гигантского числа вариантов и, соответственно, применения вычислительной техники.
Отражением этого факта является состав предлагаемых методических указаний, охватывающий такие различные методы оптимизации, как математическое программирование, линейное программирование и метод ветвей и границ.
Методические указания ориентированы на студентов специальностей 22.04 "Программное обеспечение вычислительной техники и автоматизированных систем" и 01.02 "Прикладная математика", изучающих дисциплину "Методы оптимизации".
Лабораторная работа I одномерная оптимизация
Цель работы. Исследование некоторых процедур минимизации функций одной переменной.
Постановка задачи
Рассматривается задача поиска минимума непрерывной функции одного аргумента на заданном интервале [А, В]. Без ограничения общности далее считаем А=0, B=1. При этом предполагаем, что функция ƒ имеет внутри интервала [А, В] не более одного строгого минимума (т.е. она унимодальна). Если же функция ƒ обладает несколькими локальными минимумами на интервале [А, В], то описываемые ниже методы приводят к локализации одного из этих минимумов.
- 3 -
В распоряжении исследователя имеется возможность вычислить значения функции в nточках (т.е. провестиnиспытаний). Посколь-ку в общем случае точно точку минимума найти таким путем невозможно, ставится задача отыскания интервала наименьшей длины, внутри которого гарантированно находится точка минимума.
Вначале его длина равна 1. Пусть после проведения nиспыта- ний для функции ƒ длина интервала неопределенности равнаLn(ƒ). Выбор метода минимизации (т.е. способа указания точек, в которых будут вычисляться значения функции ƒ) определяется требованием минимизацийLn(ƒ) для "наихудшей" функции ƒ, т.е. минимизацииmax{Ln(ƒ):ƒ непрерывна на [0,1]}=Ln.
Методы минимизации делятся на две группы в зависимости от того, можно ли при назначении следующей точки вычисления функции ƒ использовать информацию об уже вычисленных значениях функции ƒ. Методы, использующие эту информацию, называются методами активного поиска, не использующие - методами пассивного поиска. Ясно, что разумные методы активного поиска приводят к лучшему в указанном выше смысле результату, чем наилучшие метода пассивного поиска.