Скачать 490.86 Kb.
|
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А.Н. ТУПОЛЕВА УТВЕРЖДАЮ: Проректор по учебной и методической работе _________________ И.К. Насыров «_____» _______________ 2007 г. ПРОГРАММА ДИСЦИПЛИНЫЕН.Ф.01.7 "МЕТОДЫ ОПТИМИЗАЦИИ"Рекомендуется УМЦ КГТУ им. А.Н. Туполева для направлений (специальностей) направления: 230100 « Информатика и вычислительная техника » специальности: 230105 « Программное обеспечение вычислительной техники и автоматизированных систем » формы обучения: очная
Дисциплина “Методы оптимизации” является математической основой решения различных проблем выбора одного из возможных образов действий, возникающих в любой области человеческой деятельности. Знания и навыки, приобретенные при изучении данной дисциплины, необходимы современному специалисту в области промышленной разработки программных продуктов и средств информационных технологий. В результате изучения дисциплины “Метода оптимизации” студенты должны приобрести знания основ современной технологии разработки математических моделей поиска оптимальных решений, выработать умение эффективно применять методы решения прикладных задач оптимизации, владение навыками алгоритмического мышления, необходимыми современным программистам, системным аналитикам, исследователям информационных технологий. Для изучения дисциплины “Методы оптимизации” необходимо усвоение студентами разделов “Математического анализа”: числовые множества и последовательности, дифференциальное и интегральное исчисление, линейная алгебра. 2. Требования к уровню освоения содержания дисциплины. В результате изучения дисциплины студенты должны: Знать - основы современной технологии разработки математической модели поиска оптимальных решений; -классификацию экстремальных задач и методов их решения; -основные аналитические и численные методы безусловной минимизации функций одной и нескольких переменных; -основные методы решения задач нелинейного программирования; -основные алгоритмы решения задачи линейного программирования; - типовые задачи оптимизации на графах; -простейшую задачу вариационного исчисления и метод ее решения. Уметь -формулировать основные математические задачи оптимизации, в зависимости от типа критерия качества и наличия ограничений; -решать классическим методом задачи безусловной минимизации функций одной и нескольких переменных; -решать симплекс-методом задачу линейного программирования; -применять практически основные численные методы решения задач нелинейного программирования; - решать задачу о максимальном потоке в среде MS Excel 2003. Иметь опыт -использования методов оптимизации на ПК в операционной системе Microsoft Windows. Иметь представление -об использовании методов оптимизации в последующих учебных дисциплинах, а также при выполнении курсового и дипломного проектирования; -о современной технологии постановки и практического решения типовых задач оптимизации в среде MS Excel. 3. Объем дисциплины и виды учебной работы
4. Содержание дисциплины 4.1. Тематический план
4.2. Содержание тем Введение 1. Предмет и задачи дисциплины (1/1) Экстремальные проблемы в технике и экономике, их возникновение и развитие. Признаки классификации экстремальных задач. Задачи математического программирования и их классификация. 2. Математическое моделирование в оптимизации (1/1) . Объект оптимизации. Выбор управляемых переменных и числового критерия оптимизации. Формулировка математической задачи оптимизации. Примеры формализации задач на экстремум. Задачи классического вариационного исчисления и оптимального управления. Методы одномерной оптимизации 3. Математическая модель одномерной оптимизации (1/2). Минимум функции одной переменной. Ее точки минимума и точная нижняя грань. Унимодальные функции и их свойства. Гладкие и выпуклые функции, их свойства. 4. Классический метод одномерной оптимизации (1/2) Необходимые и достаточные условия экстремума функции одной переменной. Алгоритмы реализации классического метода. Примеры. 5. Прямые методы одномерного поиска (7/1) Приближённые методы решения задачи одномерной оптимизации. Их классификация. Метод равномерного перебора. Метод поразрядного поиска. Методы исключения отрезков. Метод дихотомии. Метод золотого сечения. Методы безусловной минимизации функций многих переменных 6. Математическая модель многомерной оптимизации (2/2 ) Постановка задачи безусловной минимизации функций многих переменных. Минимум функции многих переменных. Дифференцируемые функции многих переменных. Необходимые и достаточные условия экстремума дифференцируемой функции. Алгоритм классического метода. Примеры. 7. Прямые методы безусловной оптимизации (1/2) Минимизация по правильному симплексу. Метод деформируемого многогранника. Методы покоординатного спуска. 8. Методы безусловной оптимизации, использующие производные (4/2) Понятия итерационной процедуры, минимизирующей последовательности, скорости сходимости, направления убывания функции, исчерпывающего спуска, градиента и антиградиента функции. Метод градиентного спуска. Метод наискорейшего спуска. Минимизация овражных функций. Метод быстрых и медленных переменных. Метод Гельфанда. 9. Градиентные методы второго порядка (2/2) Понятие дважды дифференцируемой функции многих переменных. Квадратичная аппроксимация. Матрица Гессе. Метод Ньютона. Обобщенный метод Ньютона. Примеры. Методы оптимизации при наличии ограничений 10. Математическая модель конечномерной оптимизации при наличии ограничений (1/2) Общая постановка и классификация задач математического программирования. Задача на условный экстремум. Функция Лагранжа. Правило множителей Лагранжа. Примеры. 11. Постановка задачи линейного программирования ( 3/1) Общая постановка ЗЛП. Каноническая форма ЗЛП. Приведение общей ЗЛП к канонической форме. Множество планов ЗЛП и его свойства. Угловые точки. Опорные планы вырожденные и невырожденные. Свойства решений ЗЛП. 12. Графический метод решения ЗЛП (1/2) Графическая интерпретация ЗЛП. Гиперплоскость линейной формы. Опорная гиперплоскость множества планов ЗЛП. Алгоритм графического метода решения ЗЛП. Примеры. 13. Метод последовательного улучшения плана (4/2) Основная идея метода последовательного улучшения планов. Переход от одного опорного плана к другому. Признак оптимальности опорного плана. Рекуррентные соотношения для параметров соседних опорных планов. Первый алгоритм симплекс-метода. Способы построения начального опорного плана. 14. Методы последовательной безусловной оптимизации (4/1) Метод штрафных функций. Последовательность штрафных функций. Метод барьерных функций. Последовательность барьерных функций. Комбинированный метод штрафных функций. Особенности алгоритмической реализации методов последовательной безусловной оптимизации. 15. Метод случайного поиска (4/1) Случаи предпочтительного выбора метода случайного поиска (МСП). Правило построения минимизирующей последовательности в МСП. Особенности алгоритмической реализации МСП. Понятие неудачного шага в МСП. Критерий прекращения поиска. Алгоритмы МСП с обучением и без обучения. Поиск с возвратом при неудачном шаге.Алгоритм наилучшей пробы. Алгоритм статистического градиента. 16. Постановка задачи выпуклого программирования (1/2) Выпуклые множества и их свойства. Выпуклые функции и их экстремальные свойства. Постановка ЗВП. Выпуклость допустимой области ЗВП. 17. Метод возможных направлений решения ЗВП (3/2) Понятие возможного и подходящего направлений. Основная идея метода возможных направлений. Алгоритм выбора начальной точки. Определение активных ограничений. Выбор наилучшего подходящего направления. Алгоритм вычисления длины шага в выбранном направлении. Оценка погрешности приближенного решения ЗВП. Оптимизация на графах 18. Типовые задачи оптимизации на графах и их решение в среде MS Excel 2003(2/2) Типовые задачи оптимизации на графах. Задача о максимальном потоке. Общая математическая постановка задач оптимизации на графах. Математическая модель задачи о максимальном потоке. Компонент офисного пакета MS System Office – MS Excel. Решение задачи о максимальном потоке в среде – MS Excel 2003. Оптимизация в функциональных пространствах 18. Простейшая задача вариационного исчисления (2/2) Основные понятия вариационного исчисления. Минимум функционала на заданном классе функций. Вариации функции и ее производных. Кривые сравнения нулевого и первого порядка близости. Лемма Лагранжа. Простейшая вариационная задача с фиксированными границами. 19. Аналитический метод решения вариационной задачи (2/2) Построение функций сравнения в задаче с фиксированными границами. Вывод необходимого условия экстремума функционала на классе гладких функций. Уравнение Эйлера. Примеры. 4.3. Лабораторный практикум
|
Рабочая программа дисциплины экономика направление подготовки: 230100.... Программа предназначена для бакалавров по направлениям 230100. 62 информатика и вычислительная техника; все неэкономические направления,... | Программа разработана в соответствии с: Федеральному Государственному... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов для направления 230100. 68... | ||
Программа дисциплины «Методы планирования производственных процессов»... Программа дисциплины «Методы планирования производственных процессов» для направления 230100 – «Информатика и вычислительная техника»... | Программа дисциплины «философия» по направлениям подготовки 230100... Программа предназначена для преподавателей, ведущих данную дисциплину, ассистентов и студентов направлений 230100 «Информатика и... | ||
Программа дисциплины «Социальная философия» по направлениям подготовки... Программа предназначена для преподавателей, ведущих данную дисциплину, ассистентов и студентов направлений 230100 «Информатика и... | Учебная Фгос по профессии 230103. 03 Наладчик компьютерных сетей, входящей в состав укрупненной группы направлений подготовки и специальностей... | ||
Программа дисциплины «Системы управления, ориентации и навигации»... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки специальности... | Программа дисциплины «Лазерная гироскопия» для специальности 230100.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки специальности... | ||
Программа дисциплины «Навигационные системы» для специальности... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки специальности... | Программа дисциплины «История России» для направления 230100. 62... Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки «Информатика и вычислительная... | ||
Программа дисциплины «История России» для направления 230100. 62... Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки «Информатика и вычислительная... | Учебная Программирование в компьютерных системах (базовой и углубленной подготовки), входящей в укрупненную группу направлений подготовки... | ||
Программа дисциплины «История России» для направления 230100. 62... Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки «Информатика и вычислительная... | Рабочая программа дисциплины системы и сети пакетной коммутации (сспк)... Рабочая программа предназначена для преподавания дисциплины «Системы и сети пакетной коммутации» студентам заочной сокращенной формы... | ||
Рабочая программа учебной дисциплины Основы алгоритмизации и программирования... Фгос нпо, входящей в состав укрупненной группы профессий 230000 Информатика и вычислительная техника, по направлению подготовки 230100... | Программа по формированию навыков безопасного поведения на дорогах... Для направления 230100 «Информатика и вычислительная техника» специальности 230100. 68 «Системы автоматизированного проектирования»... |