Математическое программирование Оглавление (стр. 7 )

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

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

Работа с учебной литературой. Студент обязан изучать литературу. Однако на основе всего изученного материала студенты должны выработать и своё собственное видение изучаемой проблемы. Общая учебная литература указана отдельным списком, дополнительная литература даётся к каждому занятию, кроме того, студент может использовать любую другую доступную ему литературу.

Домашние работы и индивидуальные задания.

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

Примерное содержание практических (лабораторных) занятий курса

Тема  занятия №1. Предмет математического программирования.

О моделях. Вопросы классификации и специфики. Примеры математических моделей. Основные обозначения. Задачи оптимального проектирования. Задачи оптимального планирования.

       Тема занятия №2.  Элементы выпуклого анализа.

Евклидово пространство. Выпуклые множества. Проекция точки на множество. Теоремы отделимости. Угловые точки. Теорема о представлении. Теорема Фаркаша. Конус. Теорема о замкнутости конуса. Выпуклые и вогнутые функции. Дифференцируемость по направлению. Выпуклые дифференцируемые функции. Некоторые экстремальные свойства функций на выпуклых множествах. Сильная выпуклость функций.

       Тема занятия №3.  Основы выпуклого программирования.

Основная задача выпуклого программирования. Условие регулярности. Функция Лагранжа. Условия оптимальности. Теорема Куна-Таккера. Задача с линейными ограничениями.

       Тема занятия №4. Теория линейного программирования. 

Основная задача. Двойственность. Примеры. Геометрическая интерпретация  основной задачи линейного программирования. Основные теоремы. Алгебраическая характеристика угловой точки. Двойственные задачи со смешанными ограничениями. Каноническая задача линейного программирования.

       Тема занятия  №5. Конечные методы решения задач линейного программирования.

Симплекс-метод. Поиск начальной угловой точки. Вырожденность. Модифицированный симплекс-метод. Двойственный симплекс-метод.

       Тема  занятия №6. Метод штрафных функций. Вопросы устойчивости в математическом программировании.

Описание метода. Теоремы о сходимости. Применение метода штрафных функций в линейном программировании. Корректные и некорректные задачи. Метод регуляризации.

       Тема занятия №7. Методы одномерной минимизации.

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

       Тема занятия №8. Вычислительные методы нелинейного программирования.

Методы безусловной минимизации. Градиентные методы. Метод Ньютона. Метод сопряженных градиентов. Методы условной минимизации. Метод условного градиента. Метод возможных направлений. Обзор других методов (покоординатный поиск, циклический покоординатный поиск, случайный поиск). О сходимости релаксационных методов для невыпуклых задач.

       Тема занятия №9. Вариационное исчисление.

Основные определения. Основные леммы вариационного исчисления. Простейшая задача вариационного исчисления. Функционалы от нескольких функций. Функционалы с производными высшего порядка. Функционалы от функций многих переменных. Канонический вид уравнения Эйлера.

Примерная тематика лабораторных работ

       Лабораторная работа № 1. Экстремум функции одного переменного.

       Лабораторная работа № 2. Условный функции нескольких переменного.

       Лабораторная работа № 3. Численные методы поиска экстремума функции одного переменного. 

       Лабораторная работа № 4. Симплекс-метод.

       Лабораторная работа № 5. Транспортные задачи.

       Лабораторная работа № 6. Определение экстремума функционала для простейшей задачи вариационного исчисления.

Примерная тематика контрольных работ

       Контрольная работа №1. Аналитические методы решения задач поиска экстремума функций при наличии смешанных ограничений.

       Контрольная работа №2. Принцип максимума Понтрягина. Методы решения задач оптимального управления.

Cловарь терминов

А

Аксиома – это суждение, которое в рамках некоторой науки или теории принимается истинным без доказательств

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

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

Аналогия-это умозаключение, в котором на основании сходства двух объектов в некоторых признаках и при наличии дополнительного  признака у одного из них делается вывод о наличии такого же  признака у  другого  объекта.

В

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

Выполнимая формула. Формула называется выполнимой, если она общезначимая или нейтральная.

Высказывание – неопределяемое понятие. Под высказыванием понимают повествовательное предложение, которое объективно является истинным или ложным.

Г

Гипотеза – это предложение о свойствах, причинах, структуре, связях изучаемых объектов или явлений. 

       Д

       Дедуктивное умозаключении. Дедуктивным называется умозаключение, в котором  посыпки и заключение находятся в отношении логического следования.

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

Допустимые значения предиката - это значения, при которых предикат имеет смысл.

З

Заключение - это высказывание, содержащее новое знание, полученные  из исходного.

И

Интерпретацией формулы А называется всякий набор истинностных значений атомов, входящих в эту формулу.

Истинностная функция. Функция вида называется n-местной истинностной функцией или функцией алгебры высказывания.

Истинностной таблицей формулы называется таблица, содержащая всевозможные интерпретации формулы и соответствующие этим интерпретациям значения формулы.

Н

Невыполнимая формула. Формула называется невыполнимой (тождественно ложной, противоречием), если во всех своих интерпретациях она принимает значение Л.

Нейтральная формула. Формула называется нейтральной, если во всех своих интерпретациях она принимает значение так И, как и Л.

Необщезначимая формула. Формула называется необщезначимой, если она невыполнимая или нейтральная.

Неполная индукция - это умозаключение, в котором на основании того, что некоторые объекты класса обладают определенным свойством, делается вывод о том, что этим свойством обладают все объекты данного класса.

О

Областью истинности предиката называется множество значений, при которых предикат обращается в истинное высказывание.

Областью определения предиката называется множество допустимых значений переменных

К

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

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

Квантор существования – специальный указатель на то, что некоторое P имеет место (или истинно) при некоторых переменных, перечисленных в этом указателе, причем конкретные значения, обеспечивающие это, не указываются, а фиксируется лишь то, что они существуют. Переменные, перечисленные в указателе, называются связанными.

Л

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