КАЛИНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


УЧЕБНАЯ ПРОГРАММА

по дисциплине "МЕТОДЫ ОПТИМИЗАЦИИ"

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

Факультет: фундаментальной подготовки
Кафедра: прикладной математики


КАЛИНИНГРАД
2004


1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ

1.1. Цель преподавания дисциплины.

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

1.2. Задачи изучения дисциплины.

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

2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ

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

3. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ


Виды учебной работы 5 семестр
Общая трудоемкость дисциплины 90
Аудиторные занятия 46
Лекции 30
Лабораторные занятия 16
Самостоятельная работа 44
Вид итогового контроля зачет

4. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

4.1. Разделы дисциплины и виды занятий

Раздел дисциплины Лекции ЛР
1 Классическая теория 8 6
2 Элементы вариационного анализа 6 4
3 Элементы выпуклого анализа Теорема Куна-Таккера 2 -
4 Методы линейного программирования 6 4
5 Оптимизация на графах 8 2

4.2. Содержание разделов дисциплины

Раздел 1. Классическая теория (8 часов).

Элементы нелинейного анализа. Сильная и слабая дифференцируемость, их связь (2 часа)
Множители Лагранжа. Теорема оптимизации со связями (2 часа)
Обзор существующих пакетов прикладных программ, примеры использования (2 часа)
Примеры численных алгоритмов, конструирование и анализ. Использование штрафов (2 часа)

Раздел 2. Элементы вариационного анализа (6 часов).

Дифференцирование функционалов. Вариации. Примеры (2 часа)
Уравнение Эйлера. Экстремали (2 часа)
Примеры классических вариационных задач. Понятие о дифференциальных ограничениях (управляемость) (2 часа)

Раздел 3. Элементы выпуклого анализа.

Теорема Куна-Таккера (2 часа).

Раздел 4. Методы линейного программирования (6 часов).

Постановка задач линейного программирования. Стандартная форма задачи. Симплекс-метод (2 часа).
Двойственность в оптимизации. Примеры в линейном программировании (2 часа).
Матричные игры. Оптимальные стратегии (2 часа).

Раздел 5. Оптимизация на графах (8 часов).

Задачи на графах. Оптимальный путь (2 часа).
Принцип Беллмана Примеры применения (2 часа).
Оптимизация потоков. Сетевые планы. (2 часа).
Понятие о дифференциальных играх (2 часа).

5. ЛАБОРАТОРНЫЕ ЗАНЯТИЯ.

Раздел 1. Классическая теория (6 часов).

Минимизация функций одной переменной. Использование пакета MathCad (2 часа).
Сравнение методов оптимизации функций многих переменных (2 часа).
Задачи с ограничениями. Множители Лагранжа (2 часа).

Раздел 2. Элементы вариационного анализа (4часа).

Наискорейший спуск. Решение уравнений Эйлера (2 часа).
Задача Дидоны. Непосредственная оптимизация (2 часа).
Множество всех подмножеств. Примеры отображений множеств. Сравнения множеств.

Раздел 4. Методы линейного программирования (4 часа).

Симплекс-задача. Двойственность. Индивидуальное задание (2 часа).
Матричная игра. Оптимальные стратегии (2 часа).

Раздел 5. Оптимизация на графах (включая принцип Беллмана) (2 часов).


6. ТЕМЫ ДЛЯ САМОСТОЯТЕЛЬНОГО ИЗУЧЕНИЯ

1. Теорема Тэйлора в R^n. Различные варианты теоремы Ферма (4 часа).
2. Необходимые условия экстремума на классах функционалов, сильная и слабая дифференцируемость (4 часа).
3. Случаи интегрируемости уравнений Эйлера. Возможность отсутствия экстремалей (2 часа).
4. Зачача Больца. Условия трансверсальности (4 часа).
5. Дифференциальные ограничения. Принцип оптимальности Понтрягина. Задачи оптимального управления (6 часов).
6. Выпуклые задачи. Субдифференциал (4 часа).
7. Двойственность в выпуклом программировании (2 часа).
8. Принцип оптимизации в форма Беллмана. Дискретизация (2 часа).
9. Выполнение индивидуальных заданий (10 часов).
10. Консультации (6 часов).
7. ЛИТЕРАТУРА

7.1. Основная литература:

1. Алексеев В.М., Тихомиров В.М.,Фомин СИ. Оптимальное управление. -М.: Наука, 1979.
2. Бахвалов Н.С. Методы вычислений, Т.1. -М.: Наука, 1975.
3. Васильев Ф.П. Лекции по методам решения экстремальных задач. -М.: МГУ, 1974.
4. Дегтярев Ю.И. Исследование операций. -М.: Высшая школа, 1986.
5. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. -М.: Высшая школа, 1979.

7.2. Дополнительная литература:

1. Айзеке Р. Дифференциальные игры. -М.: Мир, 1967.
2. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. -М.: Наука, 1984.
3. Беллман Р., Энджел Э. Динамическое программирование и уравнения в частных производных. -М.: Мир, 1974.
4. Колмогоров А.Н., Фомин СВ. Элементы теории функций и функционального анализа. -М.: Наука, 1981.
5. Красовский Н.Н. Теория управления движением. -М.: Наука, 1985.
6. Саульев В.К., Самойлов И.И. Приближенные методы оптимизации функций многих переменных. В кн.: "Математический анализ", Т. 11 (Итоги науки и техники), 1973. -С. 91-128.

8. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

Стандартные классные занятия. Для реализации некоторых алгоритмов полезно использование ПК со стандартным математическим обеспечением, включающим, например, MathCad версии не ниже 2000.

Учебная программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования подготовки дипломированного специалиста учебного плана КГТУ подготовки инженеров по указанным специальностям от 28.02.2001

Автор программы Пахнутов И.А., доцент кафедры прикладной математики КГТУ.

Программа рассмотрена и обсуждена на заседании кафедры 19.12.2003 г., протокол № 4.
Программа одобрена на заседании методической комиссии ФАПУ 10.02.2004 г., протокол № 9.