Математическое моделирование и информатика

Лента достижимости J-сети, моделирующей применение алгоритма оптимизации последовательности отбора к одной задаче

А. П. Димитриев, Т. А. Лавина, Р. И. Баженов, Т. Н. Копышева

Чувашский государственный университет им. И. Н. Ульянова, г. Чебоксары

Аннотация: Распределение учебной нагрузки на кафедре ранее было формализовано как задача комбинаторной дискретной оптимизации, и для её решения эффективным является применение алгоритма оптимизации последовательности отбора. Этот алгоритм разработан авторами в более ранних работах и использует, в частности, принципы алгоритма имитации отжига. Разработана блок-схема для данного алгоритма с целью наглядного представления работы такого алгоритма, необходимого для дальнейшего понимания излагаемого материала. Для моделирования динамики алгоритма разработана математическая модель на основе одной из разновидностей цветных сетей Петри – J-сети. Детально описана логика работы этой модели. Построена лента достижимости J-сети, содержащая 269 маркировок, часть из которых, представляющая характерные особенности, приводится в статье. Для сокращения размера ленты достижимости приняты некоторые допущения. Отбраковка недостижимых маркировок производится путем дополнительного анализа наборов неравенств – результатов сравнения значений целевой функции. В связи со значительным количеством анализируемых неравенств разработано программное средство для решения систем неравенств, алгоритм работы которого обладает полиномиальной временной сложностью. Проведен анализ ленты достижимости, который показывает корректность работы алгоритма оптимизации. Научная новизна: впервые построена лента достижимости для J-сети.

Ключевые слова: лента достижимости, оптимизация последовательности отбора, дискретная оптимизация, учебная нагрузка, J-сеть, сеть Петри

УДК: 519.6

MSC: 90-10

Поступила в редакцию: 10.02.2025
Принята в печать: 26.11.2025

DOI: 10.15507/2079-6900.27.202504.517-538