Методы оптимизации

Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА дисциплины МЕТОДЫ ОПТИМИЗАЦИИ Для подготовки бакалавров по направлению 552800-“ Информатика и вычислительная техника ”.

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

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

“УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. “_____”_______________2001 г.

РАБОЧАЯ ПРОГРАММА дисциплины МЕТОДЫ ОПТИМИМЗАЦИИ Для

подготовки бакалавров по направлению 552800-“ Информатика и вычислительная техника ”.

Факультет ФКТИ Кафедра Математического обеспечения и применения ЭВМ Курс – 3 Семестр(ы) – 5 Лекции

32 ч.

Практические занятия

16 ч.

Лабораторные занятия

16 ч.

Аудиторные занятия Самостоятельные занятия Всего часов

64 ч. 62 ч. 126 ч.

2001

2

Экзамен

5 семестр

Зачет

5 семестр

Рабочая программа обсуждена на заседании кафедры Математического обеспечения и применения ЭВМ “____”_______________2001 г., протокол №______. Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению 552800–”Информатика и вычислительная техника" Рабочая программа согласована с рабочими программами изученных ранее дисциплин: 1) Математический анализ, 2) Программирование Рабочая программа одобрена методической комиссией факультета ФКТИ “____”_____________2001г.

3

Цели и задачи дисциплины 1. Изучение математической базы решения оптимизационных задач. 2. Формирование навыков экспериментальных исследований при выборе метода оптимизации. Требования к уровню освоения дисциплины В результате изучения дисциплины студенты должны: 1. Знать основные понятия и постановки задач теории минимизации гладких функций, выпуклого и линейного программирования, переборных задач. Вариационного исчисления, методы решения типовых задач из указанных областей. 2. Уметь решать вручную и с помощью ЭВМ типовые задачи небольшой размерности. 3. Иметь представление о разнообразных постановках оптимизационных задач, а также о стандартных программных средствах решения типовых оптимизационных задач.

Содержание рабочей программы Тема 1. Вводная. Краткая характеристика дисциплины. Ее цели и задачи, порядок изучения материала, связь с другими дисциплинами учебного плана и место в подготовке инженера по специальности 2204. Формы контроля самостоятельной работы. Краткая характеристика учебной литературы. Основные понятия. Классификация допустимых множеств. Соответствие методов и допустимых множеств. Тема 2. Безусловная оптимизация. Постановка задачи. Общая схема безусловной оптимизации. Методы первого порядка. Градиентный метод с постоянным шагом. Теорема о сходимости градиентного метода. Выпуклые функции и множества. Свойства выпуклых функций. Теорема о скорости сходимости градиентного метода. Градиентный метод с дроблением шага. Метод наискорейшего спуска. Масштабирование. Метод Ньютона. Теорема о скорости сходимости метода Ньютона. Сравнение градиентных методов. Понятие о числе обусловленности локального минимума. Многошаговые (двухшаговые) методы. Метод тяжелого шарика. Метод сопряженных градиентов. Метод Полака-Ривьера. Квазиньютоновские методы. Метод Давидона-Флетчера_Пауэлла. Метод БройденаФлетчера-Шенно. Методы нулевого порядка. Методы аппроксимации. Метод покоординатного спуска. Метод симплексов (Нелдера-Мида). Метод Пауэлла. Методы прямого поиска в задачах одномерной оптимизации. Метод квадратичной интерполяции. Метод дихотомии (половинного деления). Метод «золотого сечения». Метод Фибоначчи. Тема 3. Условная оптимизация. Постановка задачи нелинейного программирования. Ограничения типа равенств. Ограничения типа неравенств. Лемма Фаркаша. Теорема Каруша-Джона. 4

Задача выпуклого программирования. Функция Лагранжа. Теорема о седловой точке. Теорема Куна-Таккера. Методы условной минимизации. Метод проекции градиента. Метод условного градиента. Метод модифицированной функции Лагранжа. Метод штрафных функций. Двойственность задачи выпуклого программирования. Теорема двойственности. Двойственность задачи линейного программирования. Тема 4. Линейное программирование. Основные понятия. Теорема о представлении и о существовании оптимальной точки. Геометрическая интерпретация задачи линейного программирования. Условие оптимальности для задачи линейного программирования. Теорема об угловой точке. Базис и базисное решение. Теорема о допустимом решении задачи линейного программирования. Симплекс-метод решения задачи линейного программирования. Транспортная задача. Построение первоначального опорного плана. Построение оптимального плана методом потенциалов. Теорема о потенциалах. Алгоритм метода потенциалов. Представление транспортной задачи с помощью графов. Тема 5. Решение переборных задач. Метод ветвей и границ. Задача о коммивояжере. Динамическое программирование. Вывод уравнения Беллмана. Примеры задач динамического программирования. Задача о ранце. Задача о распределении ресурсов. Тема 6. Вариационное исчисление. Постановка задачи. Уравнение Эйлера-Лагранжа. Частные случаи уравнения ЭйлераЛагранжа. Задача о брахистохроне. Вариационные задачи на условный экстремум. Принцип максимума Понтрягина. Принцип максимума в задаче о предельном быстродействии. Тема 7. Заключительная. Программная реализация системы оптимизации. Основные тенденции развития методов оптимизации и краткая характеристика программных средств решения оптимизационных задач. Интеллектуальные системы решения оптимизационных задач. Генетические алгоритмы. Оптимизация на нечетких множествах. Перечень лабораторных работ № 1 2 3 4 5 6 7

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

5

Номер темы 2 3 4 4 4 5 5

Перечень практических занятий №

Наименование темы занятия

Номер темы программы 1 2 3 4

Дифференцирование сложных функций многих переменных. Методы безусловной оптимизации. Методы условной оптимизации. Задача линейного программирования. Табличный метод решения задачи линейного программирования. Геометрическая интерпретация задачи линейного программирования. Метод ветвей и границ. Задача коммивояжера. Динамическое программирование. Задача о ранце. Задача о распределении ресурсов. Вариационное исчисление. Уравнение Эйлера-Лагранжа.

1 2 3 4

5 6 7

5 5 6

Распределение учебных часов по темам и видам занятий № темы

Название разделов и тем

Лекции

Объем учебных часов

1

Введение

1

2

Безусловная оптимизация

8

3

Условная оптимизация

4

Практ. занятия

Аудит. занятия

Самост. работа

Всего

Семест р

2

3

4

7

5

4

3

15

10

25

5

6

4

2

12

10

22

5

Линейное программирование

7

4

4

15

10

25

5

5

Решение переборных задач

4

4

3

11

10

21

5

6

Вариационное исчисление

4

2

6

10

16

5

7

Заключительная

2

2

8

10

5

64

62

126

ИТОГО:

Лабор. занятия

32

16

6

16

ЛИТЕРАТУРА Основная

№ 1 2

3 4 5 6

Название, библиографическое описание

Л

Балтрашевич В. Э., Барабанов Н. Е. Методы оптимизации: Учеб. пособие. СПб.: Изд-во СПбГЭТУ “ЛЭТИ”, 2001. 80 с. Методические указания к лабораторным работам по дисциплине «Исследование алгоритмов оптимизации»/Сост.: Барабанов Н.Е., Балтрашевич В.Э., Первозванский А.А.;ЛЭТИ. –С_Пб.,1991. Поляк В.Т. Введение в оптимизацию. Учебник – М.: Наука, 1983. Карманов В.Г. Математическое программирование. Учебник – М.:Наука, 1986. Банди Б. Методы оптимизации. Вводный курс. – М.:Радио и связь, 1988 Банди Б. Основы линейного программирования. Учебник – М.: Наука, 1983.

6

6

Лр

6

Пз (С)

6

К-во экз. в библ. (на каф.)

80

6

6

Уч 16 Ф4

6

6

10

6

9

6

6

6

Уч 7 Ф5

6

6

6

Уч 1 Ф3

Гриф

Мин. образ. РФ ГК СССР по нар.обр.

МВ и ССО СССР МВ и ССО СССР МВ и ССО СССР МВ и ССО СССР

Дополнительная №

Название, библиографическое описание

1

Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978. Кузин Л.Г. Основы кибернетики. Т.1 – М.: Энергия, 1973. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965. Кузнецов Ю.И., Кузубов В.И., Волощенко А.Б. Математическое программирование. Учебник -–М. Высшая школа, 1980

2 3 4

7

К-во экз. в библ. (на каф.)

0 33 0 0

Автор: к.т.н., доцент

Балтрашевич В.Э.

Рецензент д.т.н., профессор

Постников Е.В.

Зав. Кафедрой МО ЭВМ д.т.н., профессор

Лисс А.Р.

Декан факультета ФКТИ д.т.н., профессор

Герасимов И.В.

Программа согласована: Зав. отделом учебной литературы (для технических дисциплин) Председатель методической комиссии факультета ФКТИ к.т.н., доцент Руководитель методического отдела к.т.н., доцент

Смирнова О.Н. Чугунов Л.А.

Марасина Л.А.

8