Рассматривается задача построения систем динамической оптимизации в условиях, характерных для АСУ ТП. Система предназначена для оптимизации текущего экономического критерия (например, минимизации текущей себестоимости продукции) при наличии инерционности и стохастических возмущений в технологическом процессе и асимметрия функции потерь относительно ее экстремального значения. В работе предложен и исследован новый класс алгоритмов субоптимального замкнутого стохаотического управления, сконструированных с учетом специфических условий, характерных для рассматриваемого класса прикладных задач.

Работа посвящена теории матроидов и ее связи с теорией комбинаторных экстремальных задач. Главы I и II представляют посуществу введение в теорию матроидов в задачах. В главе III рассматриваются задачи построения экстремальных в том или ином смысле независимых множеств матроида. Важное понятие суммы матроидов обсуждается в главе IV. Здесь, в частности, вводится понятие увеличивающего пути в матроидах, с помощью которого дается конструктивное описание цикла суммы матроидов и алгоритмическое доказательство основных теорем о сумме матроидов. С помощью понятия увеличивающего пути строится также полиномиальный (по числу обращений к оракулу независимости) алгоритм отыскания базы суммы матроидов. Применение результатов о сумме матроидов к задачам упаковки, покрытия и пересечения в матроидах даны в главе V. В главе VI обсуждается связь иежду матрсидами и субмодулярными функциями. Здесь, в частности, устанавливаются свойства так называемых циклических множеств матроида в терминах порождающей его субмодулярной функции. На основе этих свойств строится конструктивное доказательство обобщения теоремы о ранге суммы матроидов. Наконец, в главе VII прослеживается связь между теорией матроидов и теорией трансверсалей. В частности, показано, как с помощью теорем о сумме матроидов получить основные факты теории трансверсалей.