Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Программа'
Создание условий для повышения качества общего образования, которые предполагают проведение оптимизации учебной психологической и физической нагрузки ...полностью>>
'Документ'
4. Ангелы и духи, то есть люди после смерти, могут встречать всех, кого они любили, и с кем были знакомы в этом мире, или о ком они слышали. Они могут...полностью>>
'Документ'
по факсу (485 ) 7 -54-7 Справки по тел. (485 ) 7 -55-05 Елена Николаева, Ол...полностью>>
'Урок'
/Это единство живой и неживой природы, в котором сообщество живых организмов разных профессий способно совместными усилиями поддерживать круговорот ве...полностью>>

Главная > Рабочая программа

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

МИНОБРНАУКИ

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

ФАКУЛЬТЕТ ИНФОРМАТИКИ

УТВЕРЖДАЮ

Декан факультета

С.П. Сущенко

« » 2010 г.

ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

(ОПД.Ф.8 )

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

трудоемкость дисциплины 7 зачетных единицы

НАПРАВЛЕНИЕ 080800 – ПРИКЛАДНАЯ ИНФОРМАТИКА

Томск

2010

УТВЕРЖДЕНО

кафедрой прикладной информатики.

Протокол №50 от 01.12.2010 г.

Зав. кафедрой, профессор

С.П.Сущенко

СОСТАВИТЕЛЬ

к. ф.-м. н, профессор кафедры прикладной информатики

Б. А. Гладких

I.Организационно-методический раздел

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

Дисциплины-предшественники: 1) математический анализ, 2) алгебра и геометрия.

Требования к уровню освоения дисциплины – умение применять методы оптимизации к решению реальных задач на компьютере.

II.Содержание дисциплины

II.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. Задача оптимального распределения ресурсов

II.2.Лабораторный практикум (Семинарские занятия)

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

1) Редактор матриц и преобразование Жордана.

2) Симплексный метод с искусственным базисом.

3) Метод потенциалов для решения транспортной задачи.

4) Венгерский метод для решения задачи о назначениях.

5) Метод дискретного линейного программирования (метод Гомори или метод ветвей и границ для решения задачи о ранце - по выбору).

6) Метод нелинейного программирования (по выбору).

7) Метод динамического программирования (задача по выбору).

III.Распределение часов курса по темам и видам работ

№№ пп

Наименование тем

Всего часов

Аудиторные занятия (час),

в том числе

Самостоятельная

работа

лекции

семинары

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

1

Задача линейного программирования

8

2

6

2

Жордановы исключения и другие вопросы линейной алгебры

20

4

6

10

3

Симплексный метод

24

6

6

12

4

Теория двойственности

16

6

10

5

Транспортная задача

24

6

6

12

6

Задача о назначениях

20

4

6

10

7

Дискретное линейное программирование

20

4

8

8

8

Теория выпуклого программирования

16

6

10

9

Одномерная оптимизация

4

4

10

Оптимизация функций без ограничений

22

8

14

11

Оптимизация функций с ограничениями

18

6

12

12

Динамическое программирование

28

8

6

14

ИТОГО

220

64

0

38

118

IV. Учебно-методическое обеспечение курса

  1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Физматллит, 2005. – 368 с.

  2. Пантелеев А.П., Летова Т. А. Методы оптимизации в примерах и задачах. – М.: Высшая школа, 2008. – 544 с.

  3. Сторонгин Р. Г. Исследование операций. Модели экономического поведения. – М.: Бином. Лаборатория знаний, 2007. – 208 с.



Похожие документы:

  1. Рабочая программа трудоемкость дисциплины 4 зачетные единицы направление 080800 прикладная информатика

    Рабочая программа
    ... .09) РАБОЧАЯ ПРОГРАММА трудоемкость дисциплины 4 зачетные единицы НАПРАВЛЕНИЕ 080800ПРИКЛАДНАЯ ИНФОРМАТИКА Томск 2010 УТВЕРЖДЕНО кафедрой прикладной информатики. Протокол ... наук, доцент кафедры прикладной информатики Л.Д. Шапиро Организационно- ...

Другие похожие документы..