КОМБИНАТОРНЫЕ ОПТИМИЗАЦИЯ И НАДЕЖНОСТЬ

Abstract

В монографии воедино связаны важные идеи комбинаторной оптимизации и теории комбинаторной надежности гиперграфов, ранее освещаемых в литературе изолированно. Объединяющим лейтмотивом служат линейная оптимизация, теория графов и алгоритмическая сложность перечислительных задач. Рассматриваются алгоритмы решения задач линейной оптимизации; оптимизационные задачи на графах и матроидах; обобщенная сетевая потоковая модель; основы дискретного программирования. Излагаются методы полиномиальной сводимости перечисленных задач и алгоритмические проблемы точного и приближенного вычисления полиномов комбинаторной надежности; теория доминирования сетевых гиперграфов; двойственные задачи надежности графоид- ных гиперграфов; оптимизационная и потоковые модели надежности. Адресуется ученым и аспирантам, магистрантам и студентам, интересующимся дискретной оптимизацией, теорией графов и гиперграфов, комбинаторной надежностью. Может быть использована в преподавании дискретной математики, теории сложности вычислений, математического программирования, исследования операций, для чтения спецкурсов и проведения факультативов, в работе студенческих научных кружков, а также при подготовке курсовых и дипломных работ.