ГРАФЫ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ И ИХ ПРИЛОЖЕНИЕ К ЗАДАЧАМ ОПТИМИЗАЦИИ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ
Определены два типа ограничений на достижимость вершин графа (возможность соединить одну вершину графа с другой путем): вершинная смешанная и вершинная барьерная. В случае вершинной смешанной достижимости на графе выделено подмножество вершин, по которым путь не может проходить подряд более определенного количества раз. Барьерная достижимость предполагает, что на графе выделены два подмножества вершин. Вершины первого подмножества увеличивают энергетический показатель движущегося по пути объекта, а вершины второго подмножества могут быть пройдены только при условии, что энергетический показатель достиг определенного уровня. Показано, как эти виды ограничений на достижимость, определенные в терминах вершин графа, свести к соответствующим типам ограничений на дугах графа. Рассмотрена задача нахождения оптимального пути выполнения технологического процесса при наличии ограничений на последовательность выполнения отдельных операций.