Михалевич В.С., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов

М.: Наука, 1983. — 208 с. — (Экономико-математическая библиотека).Посвящена актуальным приложениям численных методов решения дискретных задач оптимизации. Последовательно изложены современные методы решения дискретных задач оптимизации распределения ресурсов на сетях, основанные на идее последовательной оптимизации, и проанализирована эффективность таких методов. Для специалистов в области прикладной математики и кибернетики, а также специалистов в области экономики, применяющих в своей работе математические методы.Предисловие.
Дискретные сетевые задачи оптимального распределения ресурсов.
Элементы языка сетевых моделей.
Сетевое планирование с ограниченными ресурсами.
Программно целевой метод управления и сетевые задачи распределения ресурсов.
Детерминированные задачи оптимального планирования в параллельных вычислительных системах.
Библиографический комментарий.
Теория сложности экстремальных комбинаторных задач и сетевые задачи распределения ресурсов и составления расписаний.
Элементы прикладной теории сложности.
Простейшая модель вычислений: машины Тьюринга.
Классы Р и NP, языки и задачи.
NР-полнота задачи выполнимости булевой формулы.
NР-полнота простейших сетевых задач теории расписаний.
NР-полнота задач с несколькими разнородными процессорами и независимыми цепями операций.
Сложность обобщенной задачи составления расписания с векторными потребностями в ресурсах.
Библиографический Комментарий.
Вариации длительности кратчайших расписаний. Приближенные алгоритмы с оценкой погрешности.
Алгоритмы с оценками.
Вариации длительности приоритетных расписаний.
Один класс приближенных асимптотических оптимальных алгоритмов в задачах типа «станки—детали».
Библиографический комментарий.
Динамическое программирование.
Алгоритм динамического программирования.
О сложности алгоритмов динамического программирования.
Библиографический комментарий.
Последовательный анализ вариантов.
Задача с независимыми операциями.
Метод последовательного анализа вариантов (общее описание).
Алгоритм последовательного анализа вариантов в задаче с независимыми операциями.
Оценки трудоемкости в среднем алгоритма последовательного анализа вариантов.
Библиографический комментарий.
Метод ветвей и границ.
Основные понятия и структура алгоритмов.
Методы теории двойственности для решения оценочных задач.
Двойственные оценки в задачах на ациклических сетях операций.
Специальные методы решения оценочных задач.
Практические алгоритмы ветвей и границ.
Библиографический комментарий.
Литература.
Предметный указатель.