Построение мультипликаторов и их применение при матричных операциях.
Постановка задачи математического программирования. Выпуклое программирование.
Задача линейного программирования и различные формы ее записи. Приведение общей задачи ЛП к симметричной форме записи.
Приведение общей задачи ЛП к каноническому виду.
Условие оптимальности базисного плана канонической задачи ЛП.
Симплекс-метод и его сходимость
Теорема о существовании решения задачи ЛП.
Формулы пересчета при симплекс-методе.
Построение начального базисного плана с помощью искусственных переменных.
Борьба с зацикливанием симплекс-метода. Правило Блэнда.
Двойственность для задач линейного программирования в симметричной форме записи. Критерии оптимальности.
Запись двойственной задачи и условий дополнительности для задачи ЛП общего вида.
Матричные игры в чистых стратегиях.
Матричные игры в смешанных стратегиях. Теорема фон Неймана.
Матричные игры. Критерий седловой точки для игры в смешанных стратегиях.
Необходимые условия минимума для задачи математического программирования с ограничениями-неравенствами.
Теорема о седловой точке как достаточное условие минимума.
Теорема Куна-Таккера для выпуклой задачи
Двойственность в выпуклом программировании.
Критерий оптимальности для задачи выпуклого программирования с линейными ограничениями.
Обзор методов нелинейной оптимизации. Метод возможных направлений.
Градиентные методы нелинейной оптимизации.
Методы штрафных функций и функций Лагранжа для нелинейной оптимизации.
Транспортная задача в матричной постановке. Существование решения.
Критерий оптимальности для транспортной задачи. Метод потенциалов. Связь с симплекс-методом.
Транспортная задача в сетевой постановке. Роль матрицы инциденций.
Задача о максимальном потоке и двойственная к ней. Теорема о максимальном потоке и минимальном разрезе.
Алгоритм Форда-Фалкерсона для максимального потока.
Построение увеличивающей цепи с точки зрения остаточной сети потока.
Задача о потоке минимальной стоимости. Основная теорема. Алгоритм Клейна. Решение транспортной задачи с ограничениями на пропускные способности.
Динамическое программирование. Принцип оптимальности Беллмана. Функциональное уравнение динамического программирования на примерах. Особенности применения динамического программирования.
Целочисленное линейное программирование. Общие замечания. Схема метода ветвей и границ для дискретных задач оптимизации.
Метод Лэнд и Дойг для задач целочисленного линейного программирования.
Геометрическая иллюстрация. Применение к задаче о ранце.