Теория расписаний, целочисленная оптимизация, методы агрегирования и декомпозиции

Тема 1. Постановка задач теории расписаний. Критерии оценки расписаний.

Проблемы упорядочения работ. Основные понятия и определения. Постановка задач теории расписаний. Исходные данные для построения расписаний. Искомые величины при составлении расписаний. Критерии оптимальности расписаний. Формы представления расписаний. Упорядочение конечного числа работ для одной машины. Переналадки оборудования. Задача коммивояжера.

Тема 2. Задача Джонсона. Условия оптимальности для задачи Джонсона.

Постановка задачи Джонсона. Условия оптимальности для задачи Джонсона. Доказательство теоремы Джонсона. Алгоритм ее решения на основе условий оптимальности Джонсона и алгоритм Беллмана. Задача Джексона. Алгоритм ее решения.

Тема 3. Общая задача построения расписаний.

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

Тема 4. Задачи многокритериальной оптимизации.

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

Тема 5. Задачи целочисленного и смешанного линейного программирования.

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

Тема 6. Алгоритмы отсекающей плоскости для задач целочисленного и смешанного линейного программирования.

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

Тема 7. Метод ветвей и границ.

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

Тема 8. Метод динамического программирования.

Принцип оптимальности Беллмана. Основное уравнение динамического программирования. Использование динамического программирования для решения задачи коммивояжера. Использование метода динамического программирования для решения задачи о походном ранце. Использование метода динамического программирования для решения задач дискретного программирования. Достоинства и недостатки метода динамического программирования. Сравнение с методом ветвей и границ.

Тема 9. Методы декомпозиции в задачах линейного программирования.

Методы декомпозиции. Сущность методов. Метод декомпозиции Данцига-Вулфа. Схема декомпозиции Корнаи-Липтака. Схема метода распределенного моделирования.

Тема 10. Методы агрегирования.

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

Тема 11. Задачи управления дискретными процессами.

Основные постановки задач управления дискретными процессами. Условия оптимальности для задач управления дискретными процессами. Основные методы решения задач управления дискретными процессами.

Тема 12. Математические методы моделирования сложных систем.

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