Рабочая программа по дисциплине "Методы оптимизации" для специальности 230105 "Программное обеспечение вычислительной техники и автоматизированных систем"

Вид материала

Рабочая программа

Содержание Цели и задачи дисциплины и ее место в учебном процессе 2. Содержание дисциплины 4. Учебно-методические материалы по дисциплине Соответствие между рейтингом и экзаменационной оценкой Правила оценивания контрольных работ.

Подобный материал:

• Рабочая программа по дисциплине Архитектура вычислительных систем Для специальности, 122.63kb.
• Рабочая программа по дисциплине "Вычислительная математика" для специальности 230105, 201.66kb.
• Рабочая программа по дисциплине «Информатика» для специальности 230105(220400)   «Программное, 259.13kb.
• Рабочая программа по дисциплине "Программирование на языке высокого уровня" для специальности, 137.39kb.
• Рабочая программа по дисциплине: «Программное обеспечение сетей эвм» Для специальности, 72.13kb.
• Рабочая программа по дисциплине: «обработка экспериментальных данных на эвм» Для специальности, 112.33kb.
• Рабочая программа по дисциплине: «Сети ЭВМ и телекоммуникации» Для специальности, 95.71kb.
• Методические указания для студентов специальности 230105 «Программное обеспечение вычислительной, 223.95kb.
• Рабочая программа по дисциплине Численные методы оптимизации для специальности 220400, 70kb.
• Рабочая программа для специальности: 220400 Программное обеспечение вычислительной, 133.96kb.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Государственное образовательное учреждение высшего

профессионального образования

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

радиоэлектроники (ТУСУР)

УТВЕРЖДАЮ Проректор по учебной работе ____________Л.А. Боков “____”_______________2011 г.

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


По дисциплине “Методы оптимизации" для специальности 230105 "Программное обеспечение вычислительной техники и автоматизированных систем"


Факультет систем управления

Профилирующая кафедра «Автоматизированных систем управления»


Учебный план набора 2006 года и последующих лет


курс четвертый


семестр восьмой


Распределение учебного времени


лекции 32 часа

практические занятия 32 часа

всего аудиторных занятий 64 часа

самостоятельная работа 62 часа

общая трудоемкость 126 часов


экзамен 8 семестр


2011


Рабочая программа по дисциплине «Компьютерная графика» составлена с учетом требований Государственного образовательного стандарта высшего и профессионального образования по специальности 220400, утвержденного 27.03.2000г.


Рабочая программа рассмотрена и утверждена на заседании кафедры АСУ.

Протокол № 9 от " 24 " марта 2011 г.


Разработчик

доцент кафедры АСУ А.А.Шелестов


Зав. обеспечивающей

каф. АСУ А.М.Кориков

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

Декан

факультета систем управления П.В.Сенченко

Зав. профилирующей кафедрой АСУ А.М.Кориков

1. ^ ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ И ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
   

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

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

Основными задачами дисциплины являются:

• изучение основных положений теории оптимизации;
  
• освоение конструктивных особенностей оптимизационных алгоритмов;
  
• изучение методов линейного и нелинейного программирования;
  
• формирование у студентов навыков, необходимых для построения мате- матической модели системы (процесса), выбора характеристического критерия, выбора и программной реализации соответствующего алго- ритма.
  

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

В результате изучения дисциплины студент должен:

• иметь представление об основных идеях и принципах теории оптимизации;
  
• знать основные теоремы и алгоритмы оптимизации;
  
• уметь самостоятельно разрабатывать модели и оптимизационные алгоритмы и программно реализовывать их на ЭВМ.
  

Весь материал дисциплины сформирован таким образом, что в первую очередь исследуется идейная сторона методов, связь их с другими методами. При необходимости доказываются основополагающие теоремы и лишь после этого рассматриваются конструктивные особенности алгоритмов. Большинство методов излагаются с учетом их последующей реализации на ЭВМ. При этом внимание уделяется практически важным вопросам: построение математической модели, ее реализации, подготовка к решению, выбор стратегии оптимизации и т.д.

Практические занятия призваны ознакомить студентов с основными методами и оптимизационными алгоритмами, прикладными пакетами, а также привить определенные навыки самостоятельного постановки задачи оптимизации, выбора эффективного алгоритма и его программной реализации.

Дисциплина читается в течение одного семестра. Изучение завершается сдачей экзамена.


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

2.1 Наименование тем, объем в часах, содержание.

Тема 1. Введение.

Лекции - 2 час, самостоятельная работа - 2 час.


Методологические основы оптимизации. Применение методов оптимизации в инженерной практике. Связь с теорией автоматического управления. Исторический путь становления различных методов оптимизации. Цель, задачи и содержание курса.


Тема 2. Постановка и классификация задач.

Лекции - 2 час, самостоятельная работа - 4 час.


Содержательные и формализованные постановки задач оптимизации. Критерии качества и ограничения. Классификация задач оптимизации по виду целевой функции, критерию и типу ограничений. Задачи математического программирования и управления.


Тема 3. Анализ экстремальных задач (минимизация функций). Лекции-4 час, самостоятельная работа - 10 час.

Необходимые и достаточные условия существования экстремума функций без ограничений (скалярный и векторный случаи). Необходимые и достаточные условия существования условного экстремума в задачах с ограничениями. Теорема Сильвестра. Квадратичные формы. Функция Лагранжа. Условия оптимальности в терминах седловых точек функции Лагранжа. Теорема Куна - Таккера. Принцип двойственности в задачах математического программирования.


Тема 4. Методы минимизации функций. Лекции - 8 час, самостоятельная работа - 16 час.


4.1. Методы одномерного поиска

Математическая постановка задачи. Унимодальность и основные свойства унимодальных функций. Глобальная и ассимптотическая сходимость. Методы исключения интервалов: равномерного поиска, дихотомии, Фибоначчи, золотого сечения, метод ломанных. Полиномиальная аппроксимация и методы точечного оценивания. Методы оптимизации с использованием производных. Сравнительные оценки методов.


4.2. Методы поиска экстремума функций многих переменных.

Методы покоординатного спуска, метод Хука-Дживса, метод сопряженных направлений Пауэлла. Градиентные методы: метод Коши, метод Ньютона, метод Флетчера-Ривза. Алгоритмы с самонастройкой параметра длины рабочего шага. Проблемы вычисления элементов матрицы Гессе. Квазиньютоновские методы, методы с переменной метрикой. Алгоритмы Дэвидона-Флетчера-Пауэлла, Поллака-Рибьера, Бройдена-Флетчера-Шенно. Сравнение методов и результатов вычислительных экспериментов.


Тема 5. Модели и методы линейного программирования. Лекции - 6 час, самостоятельная работа - 12 час.


Математическая постановка и особенности задач ЛП. Основные формы записи задач ЛП. Приведение задач ЛП к стандартной и канонической форме. Графический метод решения задач ЛП, характеристика экстремальных точек. Симплекс-метод. Оптимальные планы и их определение. Симплекс-таблица. Критерий оптимальности симплекс - таблицы и процедура улучшения плана. Метод искусственного базиса. Двойственная задача ЛП, двойственный симплекс-метод. Анализ чувствительности в линейном программировании. Задачи целочисленного ЛП. Метод Гомори. Метод ветвей и границ. Способы построения дополнительных ограничений. Рекомендации составления моделей и решения задач ЛП.


Тема 6. Методы нелинейного программирования для задач с ограничениями. Лекции - 8 час, самостоятельная работа - 14 час.


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


Тема 7. Стратегии оптимизационного исследования. Лекции - 2 час, самостоятельная работа - 4 час.


Построение модели, реализация модели, оценка решения. Примеры экономических и технических приложений. Пакеты прикладных программ для решения оптимизационных задач.


2.2. Практические занятия. Наименование тем и их объемы.


2.2.1. Численные методы минимизации функций одной переменой - 4 час.

2.2.2. Безусловная минимизация функций многих переменных - 8 час.

2.2.3. Решение задач линейного программирования - 4 час.

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

ограничениями - 12 час.

2.2.5. Дискретное динамическое программирование - 2 час.

2.2.6. Задачи вариационного исчисления - 2 час.


3.Формы самостоятельной работы

№ п/п	Наименование работы	Кол-во час.	Форма контроля
1	Проработка лекционного материала	14	Экзамен
2	Подготовка к практическим занятиям	10	Опрос на занятиях. Проверка домашних работ.
3	Подготовка и проработка теоретического материала для выполнения контрольных работ	16	Оценка выполненных контрольных работ на основе собеседования.
4	Изучение тем теоретической и практических частей, отводимых на самостоятельную проработку	22	Опрос. Оценка качества выполненных работ.

Всего часов самостоятельной работы - 62

по дисциплине


^ 4. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ

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

1. Мицель А.А., Шелестов А.А. Методы оптимизации: Учеб. пособие – Томск: Изд-во ТУСУРа, 2005. – 256 с.

2. Методы оптимизации. Лабораторный практикум: Учеб. пособие / Мицель А.А., Шелестов А.А., Романенко В.В., Клыков В.В. – Томск: Изд-во Томск. гос. ун-та систем управления и радиоэлектроники, 2004. – 80 с.

3. Рубан А.И. Оптимизация систем. Учебное пособие.-Томск: Изд-во Томск. ун-та, 1984.

4. Сборник задач по математике для втузов. Ч.4. Методы оптимизации. /Вуколов и др.; под ред. А.В.Ефимова. - М.: Наука, 1990.


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

1. Реклейтис Г., Рейвиндран А., Рэгсдел К.Оптимизация в технике: В 2-х кн. Пер. с англ.- М.: Мир, 1986.

2. Габбасов Р., Кириллова Ф.М. Методы оптимизации. - Минск: Изд-во БГУ, 1988.

3. Карманов В.Г. Математическое программирование: Учебное пособие. - М.: Наука, 1989.

4. Химмельблау Д. Прикладное нелинейное программирование.- М.: Мир, 1991.

5. Аоки М. Введение в методы оптимизации. - М.: Наука, 1988.

6. Гилл Ф. и др. Практическая оптимизация. - м.: Мир, 1992.

7. Боглаев Ю.П. Вычислительная математика и программирование: Учебное пособие для студентов втузов. - М.: Наука, 1989.

8. Мину М. Математическое программирование. Теория и алгоритмы. - М.: Наука, 1990.


ПРИЛОЖЕНИЕ

Применение рейтинговой системы


Курс 4, семестр 8


Контроль обучения – экзамен.

Максимальный семестровый рейтинг 120 баллов.


^ Соответствие между рейтингом и экзаменационной оценкой


Менее 60 баллов – не допускается к экзаменам.

Рейтингу 60-79 соответствует оценка «удовлетворительно».

Рейтингу 80-99 баллов соответствует оценка «хорошо».

Рейтингу 100-120 баллов соответствует оценка «отлично».


В течение семестра необходимо выполнить 4 контрольные работы.

Максимум за своевременную выполненную контрольную работу и их защиту начисляется 80 баллов (4 работы  20 баллов = 80 баллов). Если работы не выполняются в срок, то их выполнение остается необходимым для получения зачета, но баллы за них не начисляются.

^ Правила оценивания контрольных работ. Отчёт о контрольной работе должен быть своевременно сдан преподавателю и защищён на следующем занятии. Величина снижения оценки определяется преподавателем индивидуально. Мотивы снижения оценки и соответствующие максимальные значения s:

• задание выполнено частично 10;
  
• неполный отчёт 5;
  
• неуверенная защита 10.
  

Если отчёт не сдан в срок по неуважительной причине, то контрольная работа считается не выполненной. Для допуска к экзамену она должна быть выполнена, но баллы за неё не начисляются.


Посещение лекций по лямбда–исчислению (16 лекций) = 20 баллов


Баллы дополнительно начисляются:

– посещение лекций: 0,5 балла за каждую лекцию. Итого: до 12 баллов.

– творческие моменты при решении контрольных заданий: 10% от рейтинга работы. Итого: до 8 баллов.


Баллы снимаются:

– отсутствие на лекции без уважительной причины: минус 1 балл за каждую лекцию. Итого: до 20 баллов.

– при защите контрольных работ студент не может объяснить ход выполнения работы и суть используемых алгоритмов.


До первой контрольной точки студент должен набрать не менее 30 баллов.