Математическое и программное обеспечение вычислительных комплексов для решения задач анализа несовместных систем с массивно параллельной обработкой данных : диссертация на соискание ученой степени доктора физико-математических наук : 05.13.11 : 05.13.18

Оптимизация технологических процессов на производстве и в транспорте традиционно являются важнейшими областями применения математических методов, программного обеспечения и новейших достижений аппаратного обеспечения вычислительных средств. Современный этап развития теории и практики оптимизации технологических процессов на производстве и в транспорте характеризуется существенным ростом объемов обрабатываемых данных. Сегодня появились возможности фиксации большого числа параметров и условий, при которых осуществляются технологические процессы, практически для каждого отдельного изделия или оказываемого сервиса. В результате в системах хранения данных накапливаются и архивируются большие объемы исторических данных о реализованных технологических процессах. При этом важную роль начинают играть системы предиктивной аналитики, основанные на обработке больших объемов исторических данных, и системы оптимизации технологических процессов в качестве инструментов внедрения полученных прогнозных аналитик. В настоящей работе оптимизация технологических процессов занимает важную роль и реализуется при решении двух классов прикладных задач: оптимизация технологических процессов на металлургическом производстве и оптимизация технологических процессов при планировании и организации грузовых железнодорожных перевозок.
Оптимизация технологических процессов на металлургическом производстве является актуальной областью исследования, поскольку металлургия представляет собой одну из важнейших отраслей экономики с большим экспортным потенциалом. Оптимизация технологических процессов при планировании и организации грузовых железнодорожных перевозок, в свою очередь, играет важнейшую роль для обеспечения территориальной целостности страны, и также является важным интеграционным фактором, влияющим на развитие экономики. В обеих задачах очень важную роль играет инфраструктура, представляющая собой машины и металлургические агрегаты в первом случае, и инфраструктуру железнодорожной сети — во втором. Развитие инфраструктуры требует значительных капитальных вложений и является, вследствие этого, достаточно инерционным процессом. В
6
то же время потребности в росте качества производимой продукции, объемов (металлургического производства) и качества оказываемых сервисных услуг (транспорта) отличается значительно большей динамикой. Закономерным следствием этого является возрастающее влияние инфраструктурных ограничений в процессах оптимизации технологических процессов и появление конфликтов или противоречий в системах ограничений, то есть, другими словами, несовместных условий.
В связи с этим актуальным является систематическое изучение свойств несовместных систем условий с применением различных математических подходов, которые являются одним из основных объектов исследования в настоящей диссертации.
В настоящей работе предлагается разработка математических моделей и методов анализа различных классов несовместных систем условий, а также разработка численных методов и алгоритмов анализа несовместных систем условий на основе полученных математических результатов. На базе разработанных численных методов и алгоритмов разрабатывается математическое и программное обеспечение вычислительных комплексов, ориентированных на решение рассматриваемых в работе прикладных проблем, характеризующихся большими объемами исторических данных. Наконец, большое внимание в работе уделяется разработке методов параллельной обработки данных с использованием средств теории графов. Эти методы используются для создания управляющих программ вычислительных комплексов, организующих массивно параллельную обработку данных.
Таким образом, целью диссертационной работы является разработка математического и программного обеспечения вычислительного комплекса для решения задач анализа несовместных систем с использованием массивно параллельной обработки данных. Этот вычислительный комплекс предназначен для решения прикладных задач анализа несовместных систем, возникающих в условиях ограниченности инфраструктурных ресурсов таких, как железнодорожная транспортная сеть, или в условиях технологических процессов с большим числом ограничений таких, как металлургическое производство.
В работах [84, 85, 116–119] получены важные результаты в области разработки математического и программного обеспечения вычислительных

7
комплексов и автоматизированных систем различного назначения. В том числе в этих работах получены результаты в области разработки моделей и методов параллельной и распределенной обработки данных. В диссертационной работе разрабатывается вычислительный комплекс специального назначения — для решения задач анализа несовместных систем условий. Такие задачи, как уже было отмечено, часто возникают в производственной деятельности в условиях большого количества ограничений и характеризуются, как правило, большой размерностью и высокой комбинаторной сложностью. Этими обстоятельствами мотивирована разработка специального программного обеспечения, моделей и методов массивно параллельной обработки данных, а также управляющих программных средств для реализации этих методов.
В работах [21,137,153,154] разрабатываются модификации классических оптимизационных методов управления производственными процессами, таких как глубокое обучение, MES и ERP–технологии.
Значимые результаты в области разработки методов распознавания и классификации данных получены в работах [67, 76, 89, 90, 182]. Одним из эффективных методов решения задачи распознавания образов в геометрической постановке является комитетный метод. С практической точки зрения наибольший интерес представляют комитеты систем линейных неравенств, ввиду их широкого применения в области моделирования противоречивых задач. Систематическое исследование различных комитетных конструкций было начато в работах [105, 106] и трансформировалось в работах [104, 107–110] в самостоятельную область математических исследований. В этой связи разработка эффективных методов численного решения задач распознавания образов в геометрической постановке представляется актуальной, при этом эффективность понимается в контексте вычислительной сложности алгоритмов и практической значимости результатов. В частности, в диссертации разработан новый подход к решению задачи синтеза комитетов минимальной мощности, в основе которого лежит специальная математическая конструкция — альтернативные покрытия. В рамках этого подхода сформулирован дополнительный критерий оптимальности решения, а также разработаны эффективные алгоритмы разделения обучающей выборки.

8
Другая прикладная область, на исследование которой ориентирован вычислительный комплекс, — это задача управления транспортными процессами в условиях противоречивости.
Большой вклад в развитие математических методов решения задач организации перевозок на железнодорожном транспорте внесли авторы работ [97–99, 204, 220, 221]. В работах [146, 147] в контексте задач логистики исследуются вопросы планирования перевозок, необходимых к последующему исполнению. В диссертационной работе задача управления транспортными процессами на этапе планирования грузовых железнодорожных перевозок получила новую формулировку в терминах задачи поиска всех максимальных совместных подсистем (МСП) соответствующей несовместной системы условий. Условиями при этом являются потенциальные маршруты следования поездов, а МСП определяет набор допустимых, с точки зрения одновременного исполнения, маршрутов. Таким образом прикладная задача управления транспортными процессами в условиях противоречивости также может быть решена с помощью разрабатываемого вычислительного комплекса.
В области решения задачи управления транспортными процессами на этапе назначения локомотивов важные результаты получены в работах [91,120, 215, 216]. Этот этап, ввиду ряда естественных ограничений на доступность и использование локомотивов, характеризуется высокой комбинаторной сложностью. Назначение, оптимальное в части количества используемых ресурсов и равномерности их загрузки, требует разработки эффективных эвристических алгоритмов. Так, например, в работах [61, 62, 205, 217, 218] разрабатываются эффективные алгоритмы для решения различных оптимизационных задач, в том числе связанных с назначением заданного множества ресурсов. В диссертации предлагается новый подход для решения задачи о назначении локомотивов в вычислительном комплексе, ориентированный на снижение размерности без существенной потери качества приближенного решения.
В рамках разработки математического обеспечения вычислительного комплекса в диссертационной работе с различных позиций исследуются комбинаторные и структурные свойства несовместных систем. Для этих целей в рассмотрение вводится базовая математическая конструкция — абстрактный симплициальный комплекс — структурные и комбинаторные

9
свойства которой связаны с аналогичными свойствами несовместных систем. Абстрактные симплициальные комплексы подробно рассматриваются, например, в работах [19, 128, 140, 241, 245]. В диссертации на основе этой базовой математической конструкции разрабатываются теоретико–графовые математические модели для решения задач анализа несовместных систем.
Из литературы по теории графов следует отметить фундаментальные работы [11,68,69,83,96,136,145,155,177]. Теоретико–графовой математической моделью для исследования структурных и комбинаторных свойств конечных несовместных систем линейных неравенств является граф максимальных совместных подсистем (граф МСП). Это понятие было впервые введено в работе [32] в результате обобщения конструкций, предложенных в работе [151]. В результате систематического исследования свойств графа МСП получены важные результаты, на основе которых разработаны эффективные вычислительные алгоритмы для решения задач анализа несовместных систем условий.
Другой подход к исследованию структурных и комбинаторных свойств несовместных систем линейных неравенств основан на методах комбинаторной геометрии. В этой связи особый интерес представляет исследование диагональной структуры выпуклых многогранников и адекватная их классификация по этому критерию. Так, например, в работах [209–211, 236] исследуются свойства диагоналей различных типов. В частности, в работе [167] было введено понятие A–диагонали, а в работе [183] — понятие F–диагонали. Однако, комбинаторные типы многогранников, определяемые семействами A– и F–диагоналей, не совпадают с комбинаторным типом, определяемым решеткой граней. В диссертационной работе в рассмотрение вводится новый тип диагоналей, названный G–диагональю, классификация по которому в точности совпадает с классической. Этот результат получил эффективное приложение в области разработки методов численного решения задач анализа несовместных систем. Установлено, что семейства всех МСП и МНП (минимальных несовместных подсистем) несовместной системы линейных неравенств однозначно соответствуют семействам G–диагоналей и граней соответствующего выпуклого многогранника. При этом сам многогранник может быть получен с помощью преобразования Гейла на множестве задающих векторов системы (подробнее о преобразованиях и диаграммах Гейла см.,

10
например, [60, 66, 68, 168, 230, 232], [231, §5.6], [246, Ch. 5], [253, §3.6]). Кроме того, из установленной взаимосвязи получены нижние оценки для числа МСП несовместной системы линейных неравенств.
В работах [175, 239, 240, 243] и [173, Ch. 2], [244, Ch. 1] исследуются комбинаторные свойства конечномерных пространств, при этом основным объектом исследования выступают положительные базисы. В диссертации эти объекты получили новое приложение в задачах анализа несовместных систем и были всесторонне исследованы как геометрические представления МНП систем линейных неравенств.
Обзор теории монотонных булевых функций (МБФ) и их разнообразных применений представлен, например, в работах [94, 103, 111, 122, 132, 174, 254]. Взаимосвязь задачи расшифровки МБФ и задачи выделения МСП несовместных систем линейных неравенств обоснована в основополагающей работе [76]. В рамках этой взаимосвязи в диссертации разрабатываются эффективные алгоритмы расшифровки МБФ и приводятся оценки вычислительных сложностей этих алгоритмов. При этом эффективность алгоритмов показана либо в терминах оптимальности по ряду критериев, либо в терминах абсолютного отклонения приближенного решения.
Как уже было отмечено, вычислительный комплекс для решения задач анализа несовместных систем условий предназначен для исследования таких предметных областей как управление технологическими маршрутами на дискретном производстве и транспортными процессами в условиях противоречивости (общая структурная схема вычислительного комплекса представлена на Рис. 1).
Компоненты, разработке которых посвящена диссертационная работа, — это математическое обеспечение (МО) и специальное программное обеспечение (ПО). В общем случае управляющие программы (см. Рис. 1) относят к блоку системных программ базового программного обеспечения. Как было отмечено ранее, прикладные задачи анализа несовместных систем возникают в условиях большой размерности и высокой комбинаторной сложности. В этой связи актуальной представляется разработка адекватных моделей и эффективных методов параллельной обработки данных в вычислительном комплексе, реализация которых определяет функционал управляющих программ специального программного обеспечения.

.
11
Рис. 1 Структурная схема вычислительного комплекса
В Главе 1 описываются основные математические модели несовместных систем, которые далее более детально исследуются в Главах 2 и 3. Вводится аксиоматическое определение несовместной системы условий в наиболее общем виде (в рамках настоящей работы) на языке отображений булевой решетки в множество подмножеств некоторого множества.
Далее описывается хорошо известное понятие комитета несовместной системы линейных неравенств и его применение в задаче распознавания образов в геометрической постановке. Данный класс несовместных систем условий играет очень большую роль в исследованиях, проводимых в последующих главах.
Другой моделью несовместных систем условий служат монотонные булевы функции (МБФ). Любой конечной монотонной несовместной системе условий может быть поставлена в соответствие некоторая МБФ от двоичных переменных, где — количество условий в исходной несовместной системе. При этом совместным подсистемам ставятся в соответствие нули МБФ, а несовместным подсистемам — единицы. При изучении комбинаторных свойств несовместных систем условий важнейшую роль играют семейства максимальных совместных подсистем (МСП) и семейства минимальных несовместных подсистем (МНП). В МБФ, поставленной в соответствие исходной монотонной системе несовместных условий, семейству МСП соответствует множество верхних нулей МБФ и семейству МНП — множество нижних

12
единиц МБФ. Таким образом, теория МБФ служит одним из инструментов анализа комбинаторных свойств несовместных систем условий. Практическое использование аппарата МБФ будет показано в Главе 4.
В качестве следующих базовых математических моделей для исследования задач анализа несовместных систем условий предлагаются абстрактные симплициальные комплексы и близкие к ним системы независимости. Каждой монотонной несовместной системе условий можно поставить в соответствие абстрактный симплициальный комплекс на множестве вершин, мощность которого равна числу условий в исходной системе. Тогда семейству МСП исходной системы будет поставлено в соответствие семейство гиперграней абстрактного симплициального комплекса.
На языке абстрактных симплициальных комплексов в Главе 1 выводится ряд общих свойств семейств совместных подсистем, такие как соотношение между семействами совместных подсистем различной мощности, а также утверждение о мощности наименьшей МНП и наибольшей МСП исходной системы. Заметим, что эти соотношения действуют в общем случае, независимо от природы самих условий, входящих в несовместную систему, и являются базовыми общими свойствами несовместных систем условий.
В Главе 2 разрабатываются теоретико–графовые методы математического моделирования несовместных систем условий. Предлагается подход, в рамках которого исследование сводится к рассмотрению структурных и комбинаторных свойств графов систем независимости. С помощью этой математической модели в Главе 4 будут разрабатываться методы численного решения задач подсчета и выделения всех МСП и МНП несовместных систем.
Методы теории графов предоставляют адекватный аппарат для исследования структурных свойств несовместных систем условий. В рассмотрение вводится специальная конструкция — граф системы независимости — и рассматриваются свойства такого графа для различных классов систем независимости.
Показано, что класс графов независимости достаточно широк: всякий конечный простой граф изоморфен некоторому графу системы независимости, и установлено соотношение между количеством элементов системы независимости и числом вершин и ребер соответствующего графа.

13
Самой общей моделью несовместной системы условий в настоящей работе является семейство упорядоченных пар множеств, каждая из которых является подмножеством некоторого топологического пространства .
Центральным результатом главы является утверждение о связности графа системы независимости, состоящей из семейства упорядоченных пар замкнутых подмножеств топологического пространства . Этот результат интересен тем, что связность графа системы независимости выводится из связности самого топологического пространства. На основе этого результата формулируются достаточные условия связности графа системы независимости, порождаемой несовместной системой неравенств, определяемых непрерывными вещественными функциями.
Отдельно рассматриваются несовместные системы нестрогих неравенств и несовместные системы строгих неравенств, определяемых непрерывными вещественными функциями, и получены достаточные условия связности порождаемых такими системами графов системы независимости.
Доказано, что граф системы независимости нестрогих неравенств, определяемых вещественными функциями над связным топологическим пространством, связен. Для аналогичного случая, но со строгими неравенствами, получены достаточные условия связности соответствующего графа системы независимости, состоящие в том, что объединение попарных пересечений нуль–множеств вещественных непрерывных функций, определяющих неравенства системы, не разделяет топологическое пространство . Этот результат имеет важные для исследований в настоящей работе следствия. Например, если вещественные непрерывные функции, определяющие неравенства в системе, являются попарно взаимно простыми полиномами, то соответствующий граф системы независимости связен.
Наибольший прикладной интерес представляет случай линейных функций над пространством R . В этом случае достаточное условие связности графа системы независимости формулируется как отсутствие противоположных векторов среди векторов, определяющих линейные неравенства. Тогда попарное пересечение их нуль–множеств имеет размерность − 2 и объединение конечного числа плоскостей размерности − 2 не разделяет связное пространство R . Это условие является общепринятым при рассмотрении несовместных систем однородных строгих линейных неравенств

14
в задачах распознавания образов в геометрической постановке. Важность последнего результата связана с тем, что граф системы независимости для несовместной системы линейных неравенств может быть эффективно использован в алгоритмах выделения МСП этой системы, что, в свою очередь, играет важную роль в задаче синтеза комитетов. Эти вопросы будут подробно обсуждаться при разработке численных методов и алгоритмов.
В связи с указанной практической значимостью несовместных систем линейных неравенств, далее в Главе 2 более подробно изучаются свойства графов систем независимости, порождаемых такими системами. Эти графы были названы в работе графами МСП несовместной системы линейных неравенств.
Как уже было сказано выше, важнейшим свойством графа МСП является то, что этот граф связен. Следующим, не менее важным свойством графа МСП является наличие в нем цикла нечетной длины. Это свойство в Главе 4 будет положено в основу приближенного алгоритма построения комитета и будут приведены оценки, подтверждающие его эффективность.
Для несовместных систем над пространством R2 приводится характеризация графов МСП: это будут простые циклы нечетной длины, большей или равной 3.
Далее в Главе 2 рассматриваются более сильные типы связности, присущие графам МСП. Во–первых, граф МСП не имеет мостов, то есть удаление любого ребра не нарушает связности этого графа. Во–вторых, если ранг каждой подсистемы из трех неравенств равен 3, то граф МСП является 2–связным, то есть удаление любой вершины графа МСП не нарушает его связность. Более сильный тип связности повышает надежность приближенных алгоритмов выделения МСП, о чем подробнее будет сказано в Главе 4.
Получено следующее локальное свойство графа МСП: если любая подсистема из + 1 неравенств совместна (1 − 1), то степень любой вершины графа МСП не меньше + 1. Это свойство также эффективно используется при построении численных методов в Главе 4.
Для графов МСП получены следующие оценки:
(1) граф МСП содержит простой цикл нечетной длины, не превосходящей числа неравенств в исходной системе,

15
(2) диаметр графа МСП не превосходит [︀ ]︀, где — число неравенств в 2
исходной системе неравенств.
В Главе 4 эти оценки также будут использоваться для разработки методов
численного решения задач анализа несовместных систем.
В Главе 3 несовместные системы линейных неравенств рассматриваются
с позиций комбинаторной геометрии. Установлена тесная взаимосвязь между комбинаторными свойствами систем линейных неравенств и аналогичными свойствами выпуклых многогранников.
В этой главе вводится важное новое понятие G–диагонали выпуклого многогранника. Введенное понятие соотносится с двумя другими понятиями A–диагоналей и F–диагоналей. Выводятся все попарные зависимости между шестью свойствами многогранников такими, как «быть циклическим», «иметь вершины в общем положении», «быть симплициальным» и три свойства попарных совпадений семйств A–, F– и G–диагоналей.
Говорят, что два многогранника имеют одинаковый комбинаторный тип, если их решетки граней изоморфны. Будем говорить, что два многогранника имеют одинаковые A–, F– или G–диагональные типы, если соответственно семейства A–, F– или G–диагоналей этих многогранников комбинаторно изоморфны. Отношение «иметь одинаковый диагональный комбинаторный тип» также является отношением эквивалентности и порождает комбинаторную классификацию на множестве многогранников. В настоящей работе показано, что определение G–диагоналей отличается от определений A– и F–диагоналей тем, что классификация многогранников по комбинаторному типу совпадает с классификацией по диагональному типу только для G–диагоналей. В связи с этим введение понятия G–диагоналей и изучение комбинаторных свойств G–диагоналей многогранников приобретает особый научный и практический интерес.
Положительный базис (ПБ) линейного пространства определяется как минимальное по включению подмножество линейного пространства, положительная оболочка которого совпадает со всем линейным пространством. Положительные базисы в R изучаются в Главе 3 с точки зрения комбинаторной структуры двух семейств подмножеств — так называемых минимальных подбазисов и максимальных односторонних подмножеств. Для максимального одностороннего подмножества ПБ ⊂ R рассматриваются

16
две характеристики: ( ) — мощность наибольшего максимального одностороннего подмножества, и ( ) — мощность наименьшего максимального одностороннего подмножества. Показано, что положительный базис ⊂ R является строго положительным (то есть пересечение положительных оболочек любых непересекающихся подмножеств состоит из единственного нулевого вектора) тогда и только тогда, когда
( ) = ( ) = .
В результате исследования свойств ПБ также получены оценки для характеристик ( ) и ( ) для положительных базисов ⊂ R .
Особый случай, интересный для рассмотрения в теории положительных базисов — это регулярные базисы. Положительный базис пространства R называется регулярным, если для некоторого его симплициального представления ( ′, ′′) выполняется включение:
⊂ conv ′ ,
где conv — выпуклая оболочка. В рамках исследования свойств ПБ в Главе 3 также были получены характеризации регулярных положительных базисов ⊂ R .
Неравенство, входящее в несовместную систему неравенств, называется существенным, если оно не входит хотя бы в одну МСП этой системы. Система неравенств называется несократимой, если все входящие в нее неравенства являются существенными. Доказывается, что несовместные системы линейных неравенств несократима тогда и только тогда, кода положительные оболочки векторов, определяющих неравенства системы, образует линейное пространство.
Центральным результатом Главы 3 является полученная двойственная связь между комбинаторной структурой несовместной системы линейных неравенств и комбинаторной структурой некоторого соответствующего выпуклого многогранника. Для построения указанной двойственности используются преобразования Гейла конечной последовательности точек
: = ( 1, 2,…, ) ⊆ R

такой, что
17
aff = R .
Основная в Главе 3 теорема устанавливает двойственную связь между любой несократимой несовместной системой линейных неравенств над пространством R и некоторым набором точек
= ( 1, 2,…, )
афинной размерности = − − 1. При этом набор определяющих векторов данной несовместной системы линейных неравенств является преобразованием Гейла набора точек с точностью до положительных множителей. Тогда справедливо следующее.
(1) Семейство МСП несовместной системы линейных неравенств комбинаторно изоморфно семейству дополнений диагоналей набора .
(2) Семейство МНП несовместной системы линейных неравенств комбинаторно изоморфно семейству дополнений гиперграней набора
.
Установленная двойственная связь играет важную роль при исследовании
комбинаторных свойств несовместных систем линейных неравенств в связи с тем, что результаты комбинаторной геометрии в области исследования выпуклых многогранников могут быть использованы для исследования свойств семейств МСП и МНП несовместных систем линейных неравенств. И, напротив, свойства семейств МСП и МНП несовместных систем линейных неравенств могут быть использованы для исследования свойств диагоналей и гиперграней конечных наборов точек.
В качестве примера использования полученной двойственности, в работе получена оценка снизу для максимального количества МСП несовместной системы линейных неравенств. Для этого используется циклический многогранник, представляющий собой выпуклую оболочку конечного числа точек параметрической кривой вида
(︀ 1, 2,…, )︀ ∈ R .
Циклический многогранник известен своими экстремальными свойствами. В работе получены оценки для числа диагоналей в циклическом многограннике.

18
С помощью установленной двойственности полученные оценки для числа диагоналей транслируются в оценку снизу для максимального числа МСП несовместной системы линейных неравенств.
В Главе 4 разрабатываются численные методы решения задач анализа несовместных систем условий, которые лежат в основе разработки математического обеспечения вычислительного комплекса.
На основе результатов, полученных в Главе 2, разрабатывается ряд алгоритмов выделения МСП несовместных систем линейных неравенств, построения их графов МСП и алгоритмов решения задачи построения минимального комитета несовместной системы линейных неравенств. Программная реализация этих алгоритмов является компонентой математического обеспечения вычислительного комплекса.
Базовый алгоритм КОМБ выделения МСП решает задачу выделения всех МСП несовместной системы, содержащих некоторую выделенную совместную подсистему . Алгоритм КОМБ основан на построении блокатора семейства дополнений уже найденных МСП до всей системы. В случае = ∅ алгоритм КОМБ будет находить все МСП несовместной системы.
Использование факта связности графа МСП несовместной системы линейных неравенств позволяет построить алгоритм ГРАФ–КОМБ путем сведения задачи выделения всех МСП системы к серии задач меньшей размерности. Каждая подзадача из этой серии состоит в поиске МСП, смежных с выделенной МСП в графе МСП исходной системы. Связность графа МСП гарантирует, что при таком подходе будут найдены все МСП исходной системы, содержащие выделенную совместную подсистему — дополнение выделенной МСП до всей системы всегда совместно.
В Разделе 4.1 Главы 4 рассматриваются варианты алгоритмов КОМБ и ГРАФ–КОМБ, обозначаемые как КОМБ( ) и ГРАФ–КОМБ( ). Отличия этих алгоритмов состоят в том, что при поиске МСП, содержащих выделенную подсистему, они останавливаются, если уже найдено таких МСП, или исчерпаны все элементы блокаторов. Следует отметить, что алгоритм ГРАФ–КОМБ( ) даже при очень малых значениях , скажем, близких к , находит, благодаря связности графа МСП, большое количество МСП. При этом вычислительные затраты на выделение очередной МСП растут тем медленнее, чем меньше значение .

19
Одним из центральных результатов Главы 4 является теорема о том, что если в последовательности МСП, образующей цикл нечетной длины в графе МСП, взять по одному решению для каждой МСП, то полученное множество векторов является комитетом исходной несовместной системы линейных неравенств. Данная теорема, в сочетании с утверждением из Главы 2 о существовании цикла нечетной длины в графе МСП, мотивировала разработку приближенного алгоритма построения комитета минимальной мощности несовместной системы линейных неравенств.
В Главе 4 впервые вводится понятие альтернативного покрытия и мощности альтернативного покрытия. Целью введения этого понятия явилась необходимость уточненной классификации комитетов несовместных систем линейных неравенств. На основе введенного понятия, вводится дополнительный критерий классификации комитетов. Содержательный смысл этого критерия состоит в том, что при равенстве числа членов двух комитетов, приоритетным считает тот из них, для которого мощность соответствующего альтернативного покрытия меньше. Для подтверждения работоспособности такого подхода в Главе 4 приводится пример, который показывает, что существуют два комитета с равным числом членов, но с различными мощностями соответствующих альтернативных покрытий.
Для построения альтернативных покрытий в диссертации разработан подход, связанный с построением логических решающих деревьев. На этом этапе важной стандартной задачей является построение решающей функции для узла дерева. С этой целью рассматривается задача оптимального разбиения множества классов и формализуется критерий качества разбиения для узла дерева. Разрабатываются приближенные алгоритмы решения задачи, а также приводятся результаты вычислительных экспериментов и оценки качества решений, доставляемых этими приближенными алгоритмами. Близость решений для двух различных разбиений оценивается по расстоянию Хэмминга между двоичными кодами, представляющими эти разбиения. В частности, в серии из 100 экспериментов со случайными выборками, результаты демонстрируют в среднем близость в 89,4% между разбиениями, полученными полным перебором (со сложностью ( · 2 )) и приближенным алгоритмом (со сложностью (︀ · 2)︀). Это означает, что в среднем приближенный алгоритм

20
получает решение весьма близкое к оптимальному при существенно меньшей сложности вычислений.
Как уже было ранее отмечено, в терминах МБФ мультииндексы МСП и МНП соответствуют верхним нулям и нижним единицам некоторой МБФ, связанной с системой. В Главе 4 рассматривается взаимосвязь задач поиска максимальных совместных подсистем с задачей расшифровки монотонных булевых функций. Классическая задача расшифровки МБФ подразумевает использование оракула, который по предъявленному двоичному набору возвращает значение МБФ на этом наборе. В качестве критерия оптимальности алгоритма расшифровки традиционно принимается число обращений этого алгоритма к оракулу, то есть говорят о минимизации этого числа. При этом значения МБФ на остальных наборах (для которых обращения к оракулу не происходило) должны однозначно восстанавливаться, исходя из свойств монотонности. Так, например, классический минимаксный критерий Шеннона требует от оптимального алгоритма в худшем случае минимального числа обращений к оракулу среди всех алгоритмов расшифровки. Оптимальный по этому критерию алгоритм был построен в работе [8], где была также получена точная оценка для алгоритма расшифровки МБФ переменных вида:
(︀ )︀+(︀ )︀. ⌊ /2⌋ ⌊ /2⌋+1
Поскольку значения МБФ для верхних нулей и нижних единиц не могут быть восстановлены по принципу монотонности, исходя из значений МБФ в других точках, то число обращений к оракулу не может быть меньше, чем сумма числа верхних нулей — P, и числа нижних единиц — Q. Исходя из этого в диссертации вводится новый нормированный критерий оптимальности алгоритма расшифровки МБФ, в котором число обращений к оракулу нормируется на сумму P + Q, то есть на общее количество верхних нулей и нижних единиц МБФ. Этот критерий, таким образом, учитывает объективную сложность расшифровки конкретной МБФ. В области исследования свойств нового критерия в работе получены оценки сверху и снизу, а также разработаны приближенные алгоритмы расшифровки МБФ, доставляющие минимальное (как можно меньшее) значение этого критерия. Для известного тестового примера приводится сравнение приближенного алгоритма с алгоритмами, оптимальными по критерию Шеннона и разработанными в работах [8] и [139].

21
Результаты этого сравнения показали, что разработанный в диссертации приближенный алгоритм потребовал не более 71 обращения к оракулу, в то время, как вышеупомянутые алгоритмы потребовали 252 обращения.
Интересный результат с использованием введенного критерия оптимальности был получен в работе для МБФ, порожденной несовместной системой линейных неравенств. В рассмотрение был введен модернизированный оракул. Для заданного двоичного набора новый оракул должен выдать значение МБФ. В случае, если значение функции равно 1, то оракул должен вернуть дополнительно любую нижнюю единицу, двоичный набор для которой меньше или равен двоичного набора, предложенного оракулу. Для такой постановки в диссертации разработан алгоритм, который требует не более P + Q обращений к оракулу. Исходя из того, что никакой другой алгоритм не может иметь менее P + Q обращений, получаем, что предложенный алгоритм является оптимальным по введенному критерию (значение критерия для этого алгоритма равно 1).
Следующий класс МБФ, рассматриваемый в работе, составляют МБФ, порожденные неориентированными графами. Такая МБФ на некотором двоичном наборе принимает значение 0, если подмножество вершин графа, состоящее из вершин, номера которых соответствуют единичным компонентам этого набора, не содержит ребер. Для расшифровки этой МБФ могут быть использованы как известные, так и разработанные в диссертации алгоритмы. Для практических целей особый интерес представляют максимальные верхние нули МБФ или, в терминах теории графов, наибольшее независимое множество вершин (Maximum Indepentend Set — MIS) в неориентированном графе, порождающем МБФ. В Главе 4 разработан эвристический алгоритм поиска максимального независимого множества с абсолютной оценкой отклонения приближенного решения от оптимального.
С этой целью вводится понятие ( , )–вершины в графе, где — количество вершин в окрестности вершины в графе, а — количество ребер, недостающих в окрестности вершины до полного порожденного подграфа. Доказано, что если в графе существует ( ,0)–вершина, то она входит в некоторое наибольшее независимое множество. Если же параметр вершины не равен 0, то эта вершина входит в некоторое независимое множество и при этом число вершин в этом множестве отличается от числа вершин в

22
наибольшем независимом множестве не более, чем на вершин. На основе этих свойств разработан алгоритм последовательного выбора ( , )–вершин в серии подграфов исходного графа. В результате формируется независимое множество и абсолютная оценка отклонения приближенного решения от оптимального — количество вершин в приближенном решении меньше, чем количество вершин в оптимальном решении, не более, чем на . Здесь — это сумма значений параметров всех вершин в последовательности отобранных ( , )– вершин. В случае если все вершины в отобранной последовательности являются ( ,0)–вершинами, то полученное решение будет точным. Например, это имеет место для дерева. Для дополнительных графов тестовой библиотеки DIMACS в работе приводятся результаты вычислительных экспериментов с использованием разработанного эвристического алгоритма. При этом алгоритм демонстрирует высокую эффективность. Полученные приближенные решения либо совпадают с наилучшими, известными на сегодняшний день, либо очень близки к ним. Следует отметить также высокую эффективность алгоритма в части сложности вычислений, которая подтверждается той же серией экспериментов.
В Главе 4 также разработан общий подход к реализации массивно параллельной обработки данных с графовой структурой. В основе этого подхода лежит идея декомпозиции набора ориентированных путей на множестве сильно связных подграфов ориентированного графа. Разработанный метод параллельной обработки данных положен в основу одной из компонент программного обеспечения вычислительного комплекса — управляющей программы для реализации метода параллельной обработки данных с графовой структурой. Эта управляющая программа используется в приложении вычислительного комплекса для решения задачи управления транспортными процессами в условиях противоречивости (в частности, на этапе организации грузовых железнодорожных перевозок).
Математическая постановка задачи параллельной обработки данных с графовой структурой состоит в следующем. Задан ориентированный граф, набор ориентированных путей этого графа и набор сильно связных подграфов, объединение которых полностью покрывает исходный граф. Необходимо декомпозировать набор ориентированных путей на множество подпутей таким образом, чтобы каждый подпуть целиком лежал в некотором сильно связном

23
подграфе. При этом декомпозиция оценивается по трем критериям: сложность декомпозиции (количество полученных подпутей), баланс декомпозиции (общее количество пар взаимно обратных подпутей в полученном множестве подпутей) и равномерность декомпозиции (показатель распределения подпутей по сильно связным подграфам). Для решения этой многокритериальной задачи, и, как следствие, для реализации метода параллельной обработки данных с графовой структурой, в диссертации разработан эвристический алгоритм, основанный на идее быстрой сортировки строк специальным образом построенной таблицы. В работе также приводятся результаты в области сравнения по сложности разработанного эвристического алгоритма с алгоритмом полного перебора.
В Главе 5 исследуются классы прикладных задач, для решения которых могут быть использованы методы анализа несовместных систем условий. Другими словами, задачи этих классов могут быть эффективно решены с помощью вычислительного комплекса для решения задач анализа несовместных систем с массивно параллельной обработкой данных.
Первой рассматривается задача управления транспортными процессами в условиях противоречивости. В частности, рассматривается задача организации грузовых железнодорожных перевозок, которая включает два этапа: этап планирования перевозок и этап назначения локомотивов для исполнения заданного плана перевозок. В задаче планирования основным объектом рассмотрения являются нормативные нитки графика движения поездов. Нормативные нитки определяются как ориентированные пути в графе сети. При этом для каждой дуги заданы путь, по которому осуществляется движение на соответствующем перегоне. Кроме того, для каждой вершины в пути заданы время прибытия и время отправления из соответствующей станции. Элементы инфраструктуры сети такие, как пути на перегонах, приемо– отправочные пути, являются основными ресурсами, которые используют вышеупомянутые нормативные нитки графика. В работе формализовано понятие конфликтности двух любых нормативных ниток. На основе этого понятия вводится определение графа конфликтов, вершинами которого служит множество нормативных ниток, а ребрами связана такие пары вершин, для которых соответствующие нормативные нитки конфликтны. В этих терминах независимые системы вершин графа конфликтов определяют бесконфликтные наборы нормативных ниток. Таким образом, бесконфликтный

24
набор нормативных ниток может служить допустимым расписанием для осуществления перевозок. При этом с практической точки зрения интересны максимальные бесконфликтные наборы. Следовательно, задача планирования грузовых железнодорожных перевозок сводится в рамках разработанной теоретико–графовой модели к задаче поиска максимального независимого множества вершин в неориентированном графе конфликтов. В Главе 4 для решения этой задачи разработан эвристический алгоритм с абсолютной оценкой отклонения приближенного решения от оптимального.
В Разделе 5.1 Главы 5 рассматривается задача о назначении и перемещении локомотивов с целью исполнения некоторого бесконфликтного набора нормативных ниток. Отметим, что набор, подлежащий исполнению, формируется на этапе планирования грузовых железнодорожных перевозок, и считается заданным на этом этапе. При этом предполагается заданной также информация о доступных локомотивах с их локализацией и временем готовности к перевозкам. В бесконфликтном наборе нормативных ниток выделяется некоторое подмножество, которое реализует заданные размеры движения или, другими словами, план перевозок. Такой набор бесконфликтных ниток называется вариантным графиком движения поездов. В диссертации исследуется задача о назначении и перемещении локомотивов, суть которой состоит в том, чтобы для каждой нормативной нитки из вариантного графика, был назначен локомотив, с учетом условий доступности локомотивов. При этом один локомотив может выполнить последовательно несколько нормативных ниток графика. Таким образом, задача состоит в том, чтобы выполнить весь объем перевозок, используя минимальное количество локомотивов. Данная задача переформулирована в работе на языке теории графов. С этой целью вводится в рассмотрение ориентированный граф зависимостей нормативных ниток из вариантного графика. Вершинами этого графа являются нормативные нитки, и дуга следует из одной вершины в другую, если соответствующие нормативные нитки могут быть исполнены последовательно одним и тем же локомотивом. Тогда задача оптимального назначения и перемещения локомотивов сводится к задаче поиска минимального числа ориентированных путей графа зависимостей нормативных ниток таких, что их объединение полностью покрывает все его вершины. При этом пути могут иметь пересечения. Тогда следующая модификация задачи

25
состоит в том, чтобы общее количество вершин во всех найденных путях было минимальным.
В реальных системах организации грузовых железнодорожных перевозок есть существенная особенность. Она состоит в том, что все локомотивы «приписаны» к некоторому множеству депо (так называемое депо приписки). При этом локомотивы могут перемещаться только в некоторой ограниченной подсети всей железной дороги, определяемой для каждого депо приписки. Таким образом, ориентированный граф сети может быть представлен как объединение сильно связных подграфов, каждый из которых определяет некоторое депо приписки. Таким образом, для каждого сильно связного подграфа будет задан ресурс — те локомотивы (и их условия доступности), которые приписаны к соответствующему депо. При этом сильно связные подграфы имеют пересечения. В связи с этим возникает задача декомпозиции вариантного графика на поднитки, каждая из которых будет целиком расположена в области обслуживания локомотивов некоторого депо. Другими словами, пути ориентированного графа необходимо декомпозировать так, чтобы каждый подпуть целиком лежал в некотором сильно связном подграфе.
В Главе 4 был разработан эффективный метод параллельной обработки данных такого типа. Таким образом, эта задача может быть решена с помощью разработанного ранее алгоритма декомпозиции множества ориентированных путей на множестве сильно связных подграфов. Этот алгоритм был использован для решения тестовой задачи, имеющей прикладное происхождение (реальные данные). Вариантный график размерности 1215 (количество нормативных ниток) был декомпозирован на множестве сильно связных подграфов размерности 16 (количество локомотивных депо на Московской железной дороге). В результате для каждого сильно связного подграфа был сформирован набор подпутей. При этом максимальная размерность набора для отдельно взятого сильно связного подграфа составила 197 подпутей, а минимальная — 12 подпутей. Таким образом, в результате использования разработанного метода параллельной обработки данных с графовой структурой размерность подзадач, подлежащих решению, снижается почти на порядок по сравнению с размерностью исходной задачи.
В Разделе 5.2 Главы 5 рассматривается задача управления технологическими маршрутами на дискретном производстве. Не уменьшая

26
общности, задача исследуется на примере металлургического производства. В частности, в диссертации исследуется задача оптимального назначения технологических маршрутов в процессе изготовления продукции.
Идея оптимального назначения основана на возможности сбора и архивирования больших объемов исторических данных о реализации технологических процессов. Возможность дальнейшего использования этих данных мотивирует исследование задач прогнозирования и распознавания качества конечной продукции с целью выбора оптимального маршрута для продолжения технологического процесса. Конечной целью такого выбора является исключение брака производства или повышение объемов выпуска товарной продукции на единицу затрат. Заметим, что накапливаемая информация имеет все признаки больших данных, а именно:
– имеют значительные объемы, измеряемые многими терабайтами информации,
– накопление информации происходит в потоковом режиме с большой скоростью,
– накапливаемая информация характеризуется большим разнообразием и содержит значения тысяч и даже десятков тысяч параметров.
В работе вводится в рассмотрение инфраструктурный граф, вершины которого соответствуют технологическим агрегатам производства. Из одной вершины выходит дуга в другую вершину, если единица продукции после обработки на первом агрегате может проследовать в этом направлении на обработку на втором агрегате. Вершиной–развилкой инфраструктурного графа называется вершина, из которой выходит более одной дуги. В таких и только таких вершинах может приниматься решение о переназначении технологического маршрута. Любой исполненный технологический маршрут представляет собой ориентированный путь инфраструктурного графа. Каждой вершине в этом пути присваивается набор параметров, характеризующих конкретную реализацию технологического маршрута для данного исполненного технологического маршрута. При этом исполненный технологический маршрут является продуктовым, если он завершается выпуском товарной продукции. Для каждого продуктового исполненного технологического маршрута определяется параметр принадлежности продукции к некоторому классу эффективности. В частности, могут рассматриваться два класса: годные и

27
бракованные изделия. Тогда рассматриваемая задача состоит в снижении брака производства путем оптимального назначения технологических маршрутов в ходе их исполнения.
Таким образом, в результате накопления технологической информации возникает большая база данных с продуктовыми исполненными технологическими маршрутами (ИТМ) с маркерами классов эффективности. Все продуктовые ИТМ могут быть разбиты на классы по принципу принадлежности к одному и тому же ориентированному пути в инфраструктурном графе. На каждом таком пути может располагаться одна и более вершин–развилок. Для каждого такого класса и каждой такой вершины–развилки может быть поставлена задача прогнозирования или, другими словами, задача распознавания класса эффективности, которому будет принадлежать готовое изделие, если технологический маршрут данного класса будет продолжен далее при достижении данной вершины–развилки. Обучающая выборка для такой задачи будет состоять из подвекторов продуктовых исполненных технологических маршрутов, ограниченных начальным участком ориентированного пути инфраструктурного графа от начальной вершины до рассматриваемой вершины–развилки. Каждый такой подвектор будет снабжен маркером принадлежности некоторому классу эффективности. Таким образом, возникает целая серия задач распознавания образов в геометрической постановке, каждая из которых состоит из большого числа конечномерных векторов, снабженных маркером принадлежности к одному из классов эффективности. Для этих векторов необходимо построить решающее правило для отнесения нового такого вектора к одному из классов эффективности.
Численные методы решения таких задач подробно рассматриваются в Главе 4 диссертации.
Полный цикл работ показан на примере задачи прогнозирования и снижения брака на производстве. Предположим, что рассматривается всего два класса эффективности: годное и бракованное изделие. Предположим также, что для всех указанных выше задач распознавания построены решающие правила. Рассмотрим механизм использования полученной сети решающих правил для снижения брака производства. Пусть выбран для реализации некоторый технологический маршрут, который связан с

28
некоторым ориентированным путей в инфраструктурном графе. Пусть исполняемый технологический маршрут достиг первой вершины–развилки на рассматриваемом маршруте. Следовательно, получен конечномерный вектор параметров для начального участка до этой вершины–развилки. Используя построенное ранее решающее правило, можно определить, какой будет результат при продолжении технологического маршрута дальше. Если прогнозируется годное изделие, то технологический маршрут продолжается по плану. Если же прогнозируется брак, то следует испытать все другие маршруты, имеющие такой же начальный участок до рассматриваемой вершины–развилки. Для всех этих случаев, используя соответствующие найденные ранее решающие правила, будет получен прогноз о качестве конечной продукции. Если найдутся маршруты с прогнозом годного изделия, то следует выбрать один из них для дальнейшего продолжения. Если же для всех технологических маршрутов прогнозируется брак, то текущий технологический процесс следует прекратить, а единицу продукции отправить на переработку.
В Главе 5 также разработан метод параллельной обработки данных, возникающих в процессе управления технологическими маршрутами. Рассматривается вся сеть задач распознавания образов, каждая из которых определяется выделенными начальными участками исполненных технологических маршрутов до некоторой вершины–развилки. Суть метода состоит в том, чтобы запускать процесс дообучения системы по мере поступления новых данных в приоритетном порядке независимо для каждого класса исполненных технологических маршрутов. Этот метод реализован в управляющей программе вычислительного комплекса, которая функционирует согласно принятому в вычислительном комплексе механизму передачи данных на параллельную обработку.
В Главе 6 приводится описание вычислительного комплекса для решения задач анализа несовместных систем с массивно параллельной обработкой данных в приложении к решению задач, исследуемых в Главе 5.
Математическое обеспечение вычислительного комплекса представляет собой программную реализацию алгоритмов численного решения задач анализа несовместных систем, разработанных в Главе 4. Программное обеспечение, в свою очередь, состоит из двух управляющих программ для реализации

29
методов параллельной обработки данных, и двух комплексов проблемно– ориентированных прикладных программ. Отметим, что вышеупомянутые методы параллельной обработки данных были также разработаны в Главах 4 и 5 диссертации.
Вычислительный комплекс состоит из нескольких компонент: сервер сбора данных, сервер хранения данных, сервер математических моделей, сервер управляющих программ, сервер планирования и сервер принятия решений. В каждом из этих серверов функционируют специализированные программы. При этом сервер сбора данных и сервер принятия решений оснащены также каналами связи с внешними системами и уровнем пользователей соответственно.
Математическое обеспечение вычислительного комплекса располагается на сервере математических моделей и взаимодействует с сервером планирования и сервером управляющих программ. В рамках взаимодействия сервера математических моделей с сервером управляющих программ в вычислительном комплексе реализованы такие методы параллельной обработки данных, как декомпозиция множества путей ориентированного графа на множестве сильно связных подграфов, а также параллельная обработка на сети задач распознавания (прогнозной аналитики).
В Главе 6 также разрабатываются комплексы проблемно– ориентированных программ для решения исследуемых задач управления технологическими маршрутами на дискретном производстве и транспортными процессами в условиях противоречивости.
Комплекс программ «Управление технологическими маршрутами» состоит из двух программных компонент: программа «DATA TRACK» и программа «EXPERT BASE». В рамках архитектуры вычислительного комплекса программа «DATA TRACK» располагается на серверах сбора и хранения данных. Таким образом, программа «DATA TRACK» взаимодействует в вычислительном комплексе с внешними системами и с сервером управляющих программ. Основным функционалом этой программы является сбор, архивирование и первичная обработка данных о завершившихся и действующих технологических процессах. Аналогично, будучи расположенной на серверах планирования и принятия решений, программа «EXPERT BASE» взаимодействует в вычислительном комплексе

30
с сервером управляющих программ, сервером математических моделей и с уровнем пользователей. Основной задачей этой программной компоненты является непосредственно формирование решающих правил о продолжении или переназначении действующих технологических маршрутов, а также подготовка и представление на уровень пользователей информации рекомендательного характера.
Комплекс программ «Управление транспортными процессами» также состоит из двух компонент: программа «Регистратор прохождения транспорта» и программа «PLAMER». Обе эти программные компоненты в рамках архитектуры вычислительного комплекса располагаются на сервере сбора данных и взаимодействуют с внешними системами и сервером хранения данных. Программа «Регистратор прохождения транспорта» предназначена для сбора данных о доступных ресурсах локомотивного и вагонного парка, а также для формирования отчетности о локализации задействованных ресурсов в режиме реального времени. В свою очередь, программа «PLAMER» предназначена для планирования местной работы. Обработка информации, предоставляемой программой «PLAMER», является неотъемлемой составляющей этапа формирования размеров движения.
Таким образом, в диссертатации получены следующие новые результаты.
1. Предложены новые методы разработки прикладного программного обеспечения, основанные на анализе несовместных систем и моделях массивно параллельной обработки данных, позволяющие разработать математическое и программное обеспечение вычислительных комплексов для решения задач в таких важных предметных областях как управление технологическими маршрутами на дискретном производстве и управление транспортными процессами в условиях противоречивости. Разработана общая архитектура вычислительного комплекса и функционал составляющих элементов.
2. Разработаны новые методы математического моделирования и анализа несовместных систем условий с позиций теории графов и комбинаторной оптимизации (графы систем независимости), комбинаторной геометрии (свойства семейств диагоналей и граней выпуклых многогранников) и теории булевых функций (максимальные верхние нули монотонных булевых функций).

31
3. Всесторонне рассмотрены свойства графов систем независимости для различных классов. Для ряда классов систем независимости, представляющих прикладной интерес, доказана связность графа системы независимости, вытекающая из связности соответствующего топологического пространства и являющаяся важнейшим свойством графа системы независимости, эффективно использующимся при построении алгоритмов выделения их экстремальных подсистем.
4. Получены новые результаты для класса систем независимости, порождаемых несовместными системами линейных неравенств, доказаны связность графа максимальных совместных подсистем (графа МСП) и достаточные условия более сильного типа связности графа МСП, а также получены оценки степеней вершин и диаметра графа МСП. Полученные результаты имеют важное значение при построении алгоритмов выделения максимальных совместных подсистем (МСП) несовместной системы линейных неравенств. Доказана теорема о существовании цикла нечетной длины в графе МСП, на базе которой предложен новый приближенный алгоритм построения минимального комитета несовместной системы линейных неравенств и получена оценка его эффективности в сравнении с известными алгоритмами. Впервые введено понятие альтернативного покрытия, на основе которого разработан новый критерий классификации классических инструментов обработки данных таких как комитеты и решающие деревья.
5. Введено понятие G–диагонали выпуклого многогранника и получены новые результаты о взаимосвязи между семействами МСП и МНП (минимальных несовместных подсистем) несовместной системы линейных неравенств и семействами диагоналей и граней соответствующего выпуклого многогранника, что позволило применить глубоко разработанный арсенал методов и средств комбинаторной геометрии для анализа несовместных систем линейных неравенств и получить оценки снизу для максимального числа МСП и новые результаты о комбинаторных свойствах выпуклых многогранников, которые описываются в терминах графов систем независимости двойственных конструкций. Показано, что классификация многогранников по комбинаторному типу совпадает с классификацией многогранников по типам G–диагоналей. Исследованы комбинаторные свойства положительных базисов конечномерных евклидовых пространств,

32
представляющих все многообразие элементов семейства МНП несовместных систем линейных неравенств.
6. Построены новые полиномиальные эвристические алгоритмы дихотомии для решения многоклассовой задачи распознавания образов в геометрической постановке на этапе разделения обучающей выборки. Эффективность разработанных алгоритмов показана в сравнении с алгоритмами полного перебора всех возможных решений и подтверждается результатами вычислительных экспериментов для большой выборки из случайных наборов векторов.
7. Разработаны новые точные и приближенные комбинаторные и комбинаторно-графовые алгоритмы выделения всех МСП несовместных систем линейных неравенств. Актуальность приближенных алгоритмов связана с тем, что, с практической точки зрения оказывается достаточным выделение некоторого связного подграфа графа МСП, содержащего цикл нечетной длины.
8. Введен новый естественный критерий оптимальности алгоритма расшифровки монотонной булевой функции (МБФ), нормированный на общее число верхних нулей и нижних единиц МБФ и учитывающий объективную сложность задачи. Для МБФ, порождаемых несовместными системами линейных неравенств, построен оптимальный алгоритм по этому критерию.
9. Разработан новый полиномиальный эвристический алгоритм расшифровки МБФ, порождаемых неориентированными графами, с абсолютной оценкой точности приближенного решения. Показана взаимосвязь задачи расшифровки МБФ и классической задачи комбинаторной оптимизации о наибольшем независимом множестве. Проведены вычислительные эксперименты на известных примерах графов из библиотеки DIMACS, для которых показана эффективность разработанного алгоритма в сравнении с известными быстрыми алгоритмами.
10. Разработан новый подход к оптимизации управления технологическими маршрутами на дискретном производстве, состоящий в формировании сети задач распознавания образов, решаемых с помощью разработанных в работе методов анализа несовместных систем. Разработана модель параллельной обработки данных для решения задач в такой сети.
11. Разработана новая математическая модель управления транспортными процессами в условиях противоречивости на примере задачи

33
управления грузовыми железнодорожными перевозками и показано, что эта задача может быть решена методами анализа несовместных систем с помощью разрабатываемого в работе вычислительного комплекса. Показано, что формирование множества бесконфликтных наборов нормативных ниток (потенциальных расписаний, допустимых для совместного исполнения) может быть сведено к расшифровке МБФ, порожденной неориентированным графом.
12. Разработан новый общий подход к декомпозиции набора ориентированных путей в графе на множестве сильно связных подграфов этого графа. На основе этого подхода разработана модель параллельной обработки данных для задачи назначения локомотивов на исполнение ниток графика плана перевозок, имеющей высокую комбинаторную сложность. Важным преимуществом разработанной модели параллельной обработки является существенное снижение размерности задачи, что приобретает особую актуальность в условиях оперативной организации транспортных процессов.
13. Разработана управляющая программа для организации параллельной обработки данных в задаче управления технологическими маршрутами на дискретном производстве. Разработан комплекс проблемно–ориентированных прикладных программ для решения задач управления технологическими маршрутами на дискретном производстве, а также принципы его взаимодействия с другими компонентами вычислительного комплекса.
14. Разработана управляющая программа для организации параллельной обработки данных в задаче управления транспортными процессами в условиях противоречивости. Разработан комплекс проблемно–ориентированных прикладных программ для решения задачи управления транспортными процессами в условиях противоречивости, а также принципы взаимодействия его с другими компонентами вычислительного комплекса.
Таким образом, на защиту выносятся следующие положения.
1. Методы разработки программного обеспечения вычислительного комплекса, основанные на анализе несовместных систем и моделях массивно параллельной обработки данных. Общая архитектура вычислительного комплекса и функционал составляющих элементов.
2. Формализация задачи управления технологическими маршрутами на дискретном производстве как задачи распознавания образов в геометрической постановке. Новый эффективный метод параллельной обработки данных

34
на сети задач распознавания образов: кластеризация векторов обучающей выборки каждой задачи сети по мере накопления данных.
3. Формализация задачи управления транспортными процессами в условиях противоречивости как задачи расшифровки монотонной булевой функции (МБФ). Для решения этой задачи предложен новый полиномиальный алгоритм расшифровки МБФ, порождаемых неориентированными графами, с абсолютной оценкой точности приближенного решения. Проведены вычислительные эксперименты на известных примерах графов из библиотеки DIMACS, для которых показана эффективность разработанного подхода в сравнении с известными быстрыми алгоритмами.
4. Новые теоретико–графовые методы математического моделирования несовместных систем. Теоремы о связности графов для широкого класса систем независимости. Для класса несовместных систем линейных неравенств доказана теорема о существовании цикла нечетной длины в графе максимальных совместных подсистем (граф МСП) и впервые установлена взаимосвязь таких циклов с комитетами исходной системы. На основе полученных результатов разработаны эффективные алгоритмы построения графа МСП с последующим синтезом комитетов с числом членов, близким к минимальному.
5. Эффективные полиномиальные алгоритмы дихотомии с линейными разделяющими функциями в многоклассовой задаче распознавания образов для этапа разделения обучающей выборки. Метод альтернативных покрытий для повышения эффективности комитетных конструкций.
6. Новые комбинаторно–геометрические методы математического моделирования несовместных систем. Введено новое для комбинаторной геометрии понятие G–диагонали выпуклого многогранника и впервые несовместной системе линейных неравенств поставлен в соответствие (по определенному правилу) выпуклый многогранник таким образом, что семейства МСП (максимальных совместных подсистем) и МНП (минимальных несовместных подсистем) системы неравенств комбинаторно изоморфны семействам дополнений G–диагоналей и дополнений гиперграней многогранника. Исследованы комбинаторные свойства положительных базисов конечномерных евклидовых пространств, представляющих все многообразие элементов семейства МНП несовместных систем линейных неравенств.

35
7. Новый подход к оптимальной расшифровке МБФ: введен новый для теории булевых функций критерий оптимальной расшифровки, нормированный по числу обращений к оракулу и учитывающий объективную сложность МБФ. В рамках этого подхода разработан алгоритм расшифровки МБФ, оптимальный по введенному нормированному критерию для несовместных систем линейных неравенств.
8. Новый общий подход к параллельной обработке данных путем декомпозиции набора ориентированных путей в графе на множестве сильно связных подграфов этого графа. На основе этого подхода разработана модель параллельной обработки данных для задачи назначения локомотивов на исполнение ниток графика плана перевозок, имеющей высокую комбинаторную сложность. Важным преимуществом разработанной модели параллельной обработки данных является существенное снижение размерности задачи.
9. Управляющая программа для организации параллельной обработки данных в задаче управления технологическими маршрутами на дискретном производстве. Комплекс проблемно-ориентированных программ для решения задач управления технологическими маршрутами на дискретном производстве.
10. Управляющая программа для организации параллельной обработки данных в задаче управления транспортными процессами в условиях противоречивости. Комплекс проблемно-ориентированных прикладных программ для решения задачи управления транспортными процессами в условиях противоречивости.
Все результаты диссертационной работы получены лично автором в ходе научно–исследовательской деятельности. Из результатов, опубликованных в соавторстве, в диссертационную работу включен только принадлежащий автору материал.
Основные результаты диссертации изложены в 56 научных работах, включая 2 монографии, 25 статей в рецензируемых научных журналах, из которых 23 журнала входят в международные базы цитирования Scopus или Web of Science, и 13 журналов входят в перечень ВАК, а также 4 свидетельства о государственной регистрации программ для ЭВМ и 4 патента на изобретения.
Основные результаты диссертации докладывались на всероссийских и международных научных конференциях и семинарах.

36
1. Научно–техническая конференция «Методы математического программирования и их программное обеспечение» (Свердловск, 1981).
2. 1-я конференция по комбинаторной геометрии и ее приложениям (Батуми, 1985).
3. 23–24 международные научные конференции «Microwave and Telecom- munication Technology (CRIMICO)» (Севастополь, 2013–2014).
4. XLII–XLIII международные научные конференции «Гагаринские чтения» (Москва, 2016–2017).
5. XXI–XXII международные научные конференции «Системный анализ, управление и навигация» (Евпатория, 2016–2017).
6. Всероссийская научная конференция «Управление большими системами» (Самара, 2016).
7. Международная научная конференция «Математика, информатика и физика и их приложения в науке и образовании» (Москва, 2016).
8. Международная научно–практическая конференция «Big Data and Ad- vanced Analytics» (Минск, 2017).
9. Международная научная конференция «Big Data Conference (BDC)» (Москва, 2017).
10. Международная научная конференция «OPTIMA» (Petrovac, 2017).
11. Семинар отдела «Математическое программирование» ИММ им. Н. Н. Красовского УрО РАН (Екатеринбург, 2017–2018).
12. Семинар отдела «Дискретная оптимизация» Омского филиала ИМ им. С. Л. Соболева СО РАН (Омск, 2017).
13. Общероссийский семинар «Информатика, управление и системный анализ» факультета «Вычислительная математика и кибернетика» МГУ им. М. В. Ломоносова (Москва, 2017).
14. Семинар отдела «Теории расписаний и дискретной оптимизации» ИПУ им. В. А. Трапезникова РАН (Москва, 2018)
14. Семинар лаборатории «Дискретная оптимизация в исследовании операций» ИМ им. С. Л. Соболева СО РАН (Новосибирск, 2018).
15. Семинар лаборатории «Анализ данных» ИМ им. С. Л. Соболева СО РАН (Новосибирск, 2018).
Результаты диссертации были использованы в научно–исследовательских работах по гранту 218–03–167 в соответствии с договором No 02.G25.31.0055

37
c Министерством образования и науки России от 12 февраля 2013 года в рамках проекта «Разработка автоматизированной системы слежения, контроля, моделирования, анализа и оптимизации полного цикла выпуска металлургической продукции на основе создания и интеграции математических моделей технологических, логистических и бизнес–процессов предприятия».
Автор является лауреатом премии им. Е. А. и М. Е. Черепановых по направлению научно–технической деятельности (2000 г.) и премии Правительства России в области науки и техники (2004 г.).