Статус дисциплины: по выбору, читается на программе бакалавров по направлению «Экономика» в третьем семестре. Для посещения курса необходимо успешное освоение курсов «Математический анализ-2» и «Линейная алгебра-2».

Тема 1. ВВЕДЕНИЕ

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

Тема 2. ГЕОМЕТРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Понятие отрезка в n-мерном пространстве. Понятие выпуклого множества. Выпуклость множества допустимых решений и множества оптимальных решений задачи линейного программирования. Теоремы о соответствии крайних точек и допустимых базисных решений, о существовании допустимого и оптимального базисного решения задачи линейного программирования. Многогранное множество, многогранник. Теорема о представлении многогранника. Представление допустимого и оптимального множеств задачи линейного программирования.

Тема 3. СИМПЛЕКСНЫЙ МЕТОД Алгебра симплексного метода.

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

Тема 4. ТЕОРИЯ ДВОЙСТВЕННОСТИ И АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

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

Тема 5. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Целочисленные задачи линейного программирования. Метод отсечений. Отсечение Данцига. Отсечение Гомори; правильность отсечения Гомори. Комбинаторные методы дискретного программирования. Метод ветвей и границ. Некоторые экономические задачи целочисленного программирования.

Тема 6. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Конечномерные гладкие задачи с ограничениями в виде равенств и неравенств. Необходимые и достаточные условия существования экстремума. Теоремы об отделимости. Задача выпуклого программирования. Теорема Куна-Таккера. Тема

7. ТРАНСПОРТНАЯ ЗАДАЧА Различные формы транспортной задачи. Структура допустимого множества замкнутой транспортной задачи. Нахождение исходного допустимого базисного решения методом северо-западного угла и методом минимального элемента. Понятие цикла. Метод потенциалов решения транспортной задачи. Вырожденность и неединственность в транспортной задаче. Транспортная задача с ограничениями на пропускную способность. Задача о назначениях. Составление расписания.

Тема 8. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ И ОПТИМИЗАЦИЯ НА СЕТЯХ

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

Тема 9. ЭЛЕМЕНТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Постановка задачи динамического программирования. Принцип оптимальности Беллмана для решения задач динамического программирования с конечным и бесконечным горизонтом. Лемма Блэквелла. Алгоритмы решения оптимизационных задач, основанные на принципе Беллмана.