Рабочая программа специальность 351500 математическое обеспечение и администрирование информационных систем статус дисциплины

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

Утверждаю

Декан факультета информатики

С.П. Сущенко

« » 2010 г.

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

РАБОЧАЯ ПРОГРАММА

Специальность 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ

Статус дисциплины:

региональный компонент специальности

Томск - 2010 г.

ОДОБРЕНО кафедрой прикладной информатики
Протокол №50 от 01.12.2010
Зав. кафедрой, профессор _________________С.П.Сущенко

РЕКОМЕНДОВАНО методической комиссией факультета информатики

Председатель комиссии, профессор _____________________ Б.А.Гладких

“___”_____________2010 г.

Рабочая программа по курсу “Методы оптимизации” составлена на основе требований Государственного образовательного стандарта высшего профессионального образования по специальности 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ, утвержденного 10 марта 2000 г. Общий объем курса 204 часа. Из них: лекции – 64 часа, лабораторные занятия – 32 часа, самостоятельная работа студентов – 108 часов. Экзамен в шестом семестре. Общая трудоемкость курса 5.3 зач. ед.

СОСТАВИТЕЛЬ:

Гладких Борис Афанасьевич – кандидат технических наук, профессор кафедры прикладной информатики

Цели и задачи дисциплины, ее место в учебном процессе

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

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

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

Студент должен владеть математическими методами оптимизации, знать и уметь использовать численные методы оптимизации.

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

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

2. Содержание дисциплины
2.1. Теоретическая часть

Введение
Часть 1. Линейное программирование
1. Задача линейного программирования
1.1. Примеры задач линейного программирования. Задача о производственном плане. Задача о диете.
1.2. Каноническая форма. Приведение задачи линейного программирования к канонической форме. Развернутая, матричная и векторная запись задачи.
2. Повторение линейной алгебры
2.1. Метод Жордана–Гаусса. Равносильные преобразования систем линейных уравнений. Преобразования Жордана, правило прямоугольника. Применение метода Жордана–Гаусса для решения квадратной системы линейных уравнений, обращения матрицы, вычисления определителя, вычисления ранга матрицы, проверки разрешимости системы уравнений общего вида.
2.2. Системы уравнений общего вида. Частные решения. Базисные решения.
2.3. Линейное пространство и линейная независимость векторов. Аксиомы линейного пространства. Линейная зависимость векторов. Базис. Разложение векторов по базису. Преобразование базиса в общем случае и при замещении одного вектора.
2.4. Решение линейных уравнений методом Жордана–Гаусса как процесс замещения векторов в базисе.
2.5. Выпуклые множества в линейном пространстве. Определение выпуклого множества. Крайние точки. Теорема о представлении. Теорема о разделяющей гиперплоскости.
3. Симплексный метод
3.1. Геометрическая интерпретация задачи линейного программирования.
3.2. Свойства планов задачи линейного программирования. Выпуклость. Нахождение решения в крайней точке. Эквивалентность крайних точек и опорных планов.
3.3. Теория симплексного метода. Общая схема решения экстремальных задач и ее реализация в симплексном методе. Ограничение перебора. Целенаправленность перебора. Критерий оптимальности.
3.4. Практический алгоритм симплексного метода.
3.5. Метод искусственного базиса.
4. Теория двойственности
4.1. Симметричные двойственные задачи. Двойственная пара задач линейного программирования в развернутой и матричной форме. Двойственные условия.
4.2. Несимметричные двойственные задачи.
4.3. Первая теорема двойственности.
4.4. Вторая теорема двойственности.
4.5. Экономическая интерпретация двойственных задач
Выяснение экономического смысла двойственных переменных в задаче о производственном плане методом анализа размерности. Объективно - обусловленные оценки (ООО) и их роль в истории экономико - математических учений. Экономическая интерпретация теорем двойственности.
5. Транспортная задача
5.1. Постановка и формы записи транспортной задачи.
5.2. Свойства транспортной задачи. Разрешимость. Размерность. Целочисленность.
5.3. Построение исходных опорных планов. Метод северо-западного угла. Метод минимального элемента.
5.4. Критерий оптимальности в транспортной задаче. Задача, двойственная транспортной. Потенциалы и матрица невязок.
5.5. Переход к новому опорному плану.
5.6. Практический алгоритм метода потенциалов.
6. Задача о назначении
6.1. Постановка и формализация.
6.2. Свойства задачи о назначениях Эквивалентные преобразования матрицы стоимостей. Независимые нули, критерий оптимальности.
6.3. Независимые нули и паросочетания. Метод чередующихся цепей.
6.4. Практический алгоритм венгерского метода.
7. Дискретное линейное программирование
7.1. Классификация задач и методов дискретного программирования.
7.2. Методы отсечения. Алгоритм Гомори Идея метода отсечений. Правильные отсечения. Реализация правильного отсечения в алгоритме Гомори.
7.2. Метод ветвей и границ. Булево программирование на примере задачи о ранце. Реализация метода ветвей и границ.
Часть 2. Нелинейное программирование
8. Теория выпуклого программирования
8.1. Трудности, порождаемы нелинейностью. Задача выпуклого программирования.
8.2. Выпуклые функции и их свойства.
8.3. Классические задачи оптимизации. Функция Лагранжа.
8.4. Теорема Куна–Таккера.
8.5. Дифференциальные условия Куна–Таккера и их геометрическая интерпретация.
8.6. Частные случаи. Неограниченность переменных по знаку. Ограничения в виде равенства. Линейное программирование как частный случай выпуклого.
8.7. Применение теоремы Куна–Таккера к квадратичному программированию. Метод Вулфа.
9. Одномерная оптимизация
9.1. Постановка задачи и классификация методов. Предварительная локализация экстремума.
9.2. Минимизация унимодальных функций. Методы дихотомии и золотого сечения.
9.3. Минимизация выпуклых функций. Метод парабол.
9.4. Метод касательных.
9.5. Метод Ньютона.
10. Оптимизация функций без ограничений
10.1. Общая схема и классификация релаксационных методов.
10.2. Методы нулевого порядка. Метод Гаусса–Зайделя. Овражный метод. Метод Пауэлла.
10.3. Методы первого порядка (градиентные). Метод скорейшего спуска и его недостатки. Метод Флетчера - Ривса.
10.4. Методы второго порядка. Метод Ньютона–Рафсона. Метод Дэвидона–Флетчера–Пауэлла (ДФП).
10.5. О минимизации невыпуклых функций. Классификация методов. Методы сглаживания, тяжелого шарика. Методы случайного поиска (без обучения и с обучением).
11. Оптимизация функций с ограничениями
11.1. Классификация и обзор методов.
11.2. Методы штрафных функций. Внешние штрафные функции. Внутренние штрафные функции.
11.3. Метод поиска седловой точки функции Лагранжа.
11.4. Метод линейной аппроксимации для решения задач сепарабельного программирования.
11.5. Метод секущих плоскостей (метод Кэлли).
11.6. Методы возможных направлений. Схема методов по Зойтендейку. Нормализации.
12. Динамическое программирование
12.1. Основные принципы
История динамического программирования. Демонстрация основных принципов динамического программирования на примере задачи о кратчайшем пути. Принцип многошаговости. Принцип погружения. Принцип оптимальности. Функция Беллмана и уравнение Беллмана.
12.2. Задача оптимального распределения ресурсов

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

По курсу не предусмотрены практические занятия

2.3. Лабораторные работы

Цель лабораторных работ – написать приложения (с использованием любой технологии программирования), реализующие основные методы линейного и нелинейного программирования.

1) Редактор матриц и преобразование Жордана.
2) Симплексный метод с искусственным базисом.
3) Метод потенциалов для решения транспортной задачи.
4) Венгерский метод для решения задачи о назначениях.
5) Метод дискретного линейного программирования (метод Гомори или метод ветвей и границ для решения задачи о ранце - по выбору).
6) Метод нелинейного программирования (по выбору).
7) Метод динамического программирования (задача по выбору).

2.4. Курсовой проект

Курсовой проект не предусмотрен.

3. Учебно-методические материалы по дисциплине
3.1. Основная литература
1. Гасс С. Линейное программирование. – М.: Физматгиз, 1961. – 303с.
2. Юдин. Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения . – М.: Наука, 1969. – 424 с.
3. Банди Б. Основы линейного программирования. – М.: Радио и связь, 1989. – 174 с.
4. Карманов В.Г. Математическое программирование. – М.: Наука, 1960. – 256 с.
5. Мину М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990. – 488 с.
6. Аоки М. Введение в методы оптимизации: Основы и приложения нелинейного программирования. – М.: Наука, 1977. – 343 с.
7. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. – М.: Наука, 1969. – 368 с.

3.2. Дополнительная литература не требуется.

3.3. Наглядных пособий и технических средств обучения при чтении данного курса не предусмотрено.