Условия существования, алгоритмы построения и оценки комитетов для несовместных систем ограничений

• Автор: Рыбин, Алексей Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Екатеринбург
• Количество страниц: 103 с.

Содержание
Введение
1 Определения и предварительные результаты
1 Основные понятия и определения
2 Теоремы существования
3 Уточнение оценок числа членов минимального комитета для
систем линейных неравенств
2 Некоторые достаточные условия существования комитета
1 Системы включений, порожденных множествами над Яп
2 Системы включений, порожденных множествами в плоскости
3 Комитет системы включений, образованных выпуклыми многогранными множествами над В2
3 Задача о минимальном комитете
1 Постановка задачи
2 Общие свойства
3 Случай квадратной матрицы
4 Алгоритм поиска минимального комитета
Заключение
Введение
Метод комитетов определяет одно из важных направлений исследований задач оптимизации и классификации. Сфера применения комитетных конструкций определяется широтой их интерпретации. В общем случае они могут интерпретироваться как стохастические, размытые решения задач исследования операций, компромиссные решения в задачах с многокритериальностью и несовместностью ограничений, ’’смешанные стратегии“ использования решений совместных подсистем несовместных систем ограничений, решающие правила в задачах принятия решения и т.д. [21, 56].
Возникновению понятия комитета предшествовали эксперименты с ассоциативными машинами типа перцептрона [5, 12]. Понятие комитета (’’committee solution“) было введено C.M.Ablow и D.J.Kaylor [1, 3] для системы однородных строгих линейных неравенств над Rn. Комитетом системы
(яу х) > 0, j £ Njni
где aj,x е Rn ими было названо конечное множество К С Rn, такое что в полупространстве решений каждого неравенства лежит более половины элементов К.
Пусть задана произвольная система включений
xeDj С X, j е Nm.
Комитетом этой системы называется конечная последовательность
Q = {хЪХ2,.. ,хк)
элементов X, такая что в каждом множестве Dj находится более половины членов Q. Другими словами, для каждого j £ Nm выполнено неравенство
Минимальным комитетом указанной системы называют последовательность (5 с наименьшим возможным числом членов.
Исследование комитетов и комитетных конструкций в ИММ УрО РАН было инициировано С.Б.Стечкиным в начале 60-х годов. С тех пор систематические исследования в этом направлении проводятся под руководством Вл.Д.Мазурова, в работах которого [35]—[40], [42]—[53]
-доказано необходимое и достаточное условие существование комитета строгих однородных линейных неравенств, дана оценка числа членов минимального комитета;
-доказаны теоремы существования комитета для более общих классов систем неравенств (неоднородных линейных, нелинейных, над произвольным вещественным линейным пространством, неравенств сопряженного вида);
-введены определения и доказаны соответствующие теоремы существования для других комитетных конструкций: разделяющего комитета функционалов, комитета системы множеств, 2—решения, р—комитета, коллективного решения;
-разработаны и обоснованы методы и вычислительные схемы для построенных комитетных конструкций, в том числе минимальных комитетов;
-даны направления приложений комитетных конструкций в распознавании образов, вычислительной математике, теории оптимизации и в принятии решений.
Комитетным конструкциям посвящены исследования ряда других Екатеринбургских математиков. В работах А.И.Кривоногова [31]—[34] получены некоторые условия конечности алгоритма построения комитета типа линейной коррекции, обоснована эффективная схема построения комитета системы линейных неравенств с дообучением, исследованы методы проектирования в задаче построения комитета. В работах В.А.Новокшенова, Д.Н.Гайнанова, Л.И.Тягунова [64, 15, 16, 17, 78] исследованы структура максимальных совместных подсистем несовместных систем линейных неравенств и свойства порождаемых ими графов. В работах Н.Г.Белецкого [14] изучены разделяющие свойства комитетов. В исследованиях М.Ю.Хачая [79, 80, 81], на основе введенного им понятия гиперграфа максимальных совместных подсистем, предложена комбинаторная схема классификации минимальных комитетов,

тем не менее, комитетом не обладает, поскольку множества ее составляющие попарно не пересекаются, и, таким образом, не выполнены необходимые условия существования комитета (см. рис. 2.3).
Рис. 2.3: Комитета системы х € ш 1К(В), ] € N3 не существует.
Обобщением теоремы 2.1.2 является
Теорема 2.1.3. Пусть заданы множества С 1Д, у Е Ат, нгогда для
существования комитета системы (2.1) достаточно существования комитета системы
У игЬК(0,и), j Е 1Ут. (2.3)
Доказательство. Пусть = (ж*, Х2, , жД является комитетом системы (2.3). Рассмотрим произвольный номер г' Е Щ. Предположим, для некоторого Д Е Мт выполнено включение
€ и «).