Содержание
Введение 2
1 Определения и предварительные результаты 9
1 Основные понятия и определения ............................... 9
2 Теоремы существования.......................................13
3 Уточнение оценок числа членов минимального комитета для
систем линейных неравенств..................................19
2 Некоторые достаточные условия существования комитета 28
1 Системы включений, порожденных множествами над Яп .... 29
2 Системы включений, порожденных множествами в плоскости . 42
3 Комитет системы включений, образованных выпуклыми многогранными множествами над Я2 44
3 Задача о минимальном комитете 50
1 Постановка задачи...........................................51
2 Общие свойства..............................................57
3 Случай квадратной матрицы...................................66
4 Алгоритм поиска минимального комитета.......................84
Заключение 94
Введение
Метод комитетов определяет одно из важных направлений исследований задач оптимизации и классификации. Сфера применения комитетных конструкций определяется широтой их интерпретации. В общем случае они могут интерпретироваться как стохастические, размытые решения задач исследования операций, компромиссные решения в задачах с многокритериальностью и несовместностью ограничений, ’’смешанные стратегии“ использования решений совместных подсистем несовместных систем ограничений, решающие правила в задачах принятия решения и т.д. [21, 56].
Возникновению понятия комитета предшествовали эксперименты с ассоциативными машинами типа перцептрона [5, 12]. Понятие комитета (’’committee solution“) было введено C.M.Ablow и D.J.Kaylor [1, 3] для системы однородных строгих линейных неравенств над Яп. Комитетом системы
(dj,ж) > 0, j € Nm,
где (ij, х £ Я" ими было названо конечное множество К С Яп, такое что в полупространстве решений каждого неравенства лежит более половины элементов К.
Пусть задана произвольная система включений
х £ Dj С X, j £ Nm.
Комитетом этой системы называется конечная последовательность
Q = (х 1, • • • j .Tfc)
элементов X, такая что в каждом множестве Dj находится более половины членов Q. Другими словами, для каждого j £ Nm выполнено неравенство
|{t € Nk : х{ € Dj}| >
Минимальным комитетом указанной системы называют последовательность С} с наименьшим возможным числом членов.
Исследование комитетов и комитетных конструкций в ИММ УрО РАН было инициировано С.Б.Стечкиным в начале 60-х годов. С тех пор систематические исследования в этом направлении проводятся под руководством Вл. Д. Мазурова, в работах которого [35]—[40| ,|42]—[53]
-доказано необходимое и достаточное условие существование комитета строгих однородных линейных неравенств, дана оценка числа членов минимального комитета;
-доказаны теоремы существования комитета для более общих классов систем неравенств (неоднородных линейных, нелинейных, над произвольным вещественным линейным пространством, неравенств сопряженного вида);
-введены определения и доказаны соответствующие теоремы существования для других комитетных конструкций: разделяющего комитета функционалов, комитета системы множеств, 2—решения, р— комитета, коллективного решения;
-разработаны и обоснованы методы и вычислительные схемы для построенных комитетных конструкций, в том числе минимальных комитетов;
-даны направления приложений комитетных конструкций в распознавании образов, вычислительной математике, теории оптимизации и в принятии решений.
Комитетным конструкциям посвящены исследования ряда, других Екатеринбургских математиков. В работах А.И.Кривоногова [31]-[34] получены некоторые условия конечности алгоритма построения комитета типа линейной коррекции, обоснована эффективная схема построения комитета системы линейных неравенств с дообучением, исследованы методы проектирования в задаче построения комитета. В работах В.А.Новокшенова, Д.Н.Гайианова, Л.И.Тягунова [64, 15, 16, 17, 78] исследованы структура максимальных совместных подсистем несовместных систем линейных неравенств и свойства порождаемых ими графов. В работах Н.Г.Белецкого [ 14] изучены разделяющие свойства комитетов. В исследованиях М.Ю.Хачая [79, 80, 81], на основе введенного им понятия гиперграфа максимальных совместных подсистем, предложена комбинаторная схема классификации минимальных комитетов,
-3-
сформулирован и доказан критерий существования комитета с заданным наперед числом членов, получены новые оценки числа членов минимального комитета для систем линейных неравенств. Им также показано, что задача построения минимального комитета в общем случае Л^Р-трудна [83]. Теоретические и алгоритмические разработки в области комитетных конструкций были реализованы в пакетах распознавания образов "КВАЗАР* [55] и ЖВА-ЗАР-г1 [68]. успешно применяемых для задач классификации, диагностики, прогнозирования в медицине и моделировании технико-экономических систем.
Ю.И.Журавлевым предложен подход к исследованию методов распознавания образов с точки зрения алгебраической теории алгоритмов, в рамках которого им проанализированы стандартные классы алгоритмов распознавания и, в частности, классы комитетных алгоритмов [23]—[26]. Исследованию свойств комитетов, комитетных алгоритмов классификации и таксономии посвящены работы [27, 28, 29, 66, 67, 75, 76].
Комитетные конструкции представляют собой удобный инструмент при анализе противоречивых моделей. Возникновение противоречий в моделировании сложных систем вполне закономерно и обусловлено целым рядом объективных причин [21]. Одним из способов разрешения противоречий является включение в модель блока распознавания образов — дискриминантного анализа или таксономии [19. 20, 21]. [43]—[46], [48, 50. 53, 58]. [59, 60. 61]. Пусть заданы множества А, В С ЯЛ, известны их конечные подмножества А' С А, В' С В и определен класс функций Я С {Яп —> Я}. Назовем
[58] задачей дискриминантного анализа задачу нахождения такой функции / € Я, что
Предположим, что класс Я некоторым образом параметризован, так что Я = {/(с, •) | с 6 С}. Тогда поставленная задача преобразуется в задачу решения
-4-
системы неравенств
(7(с,а)>0, а € Л',
\f(c,b)<0, ЬеВ'
относительно неизвестного параметра с € С. В ряде случаев эта система может оказаться несовместной. Тогда, в зависимости от ситуации, можно использовать то или иное подходящее обобщение понятия решения, например, дискретную аппроксимацию в форме комитета.
Пусть определена конечная последовательность
<2 = (Л, Л,, Л) = (/(о. ■)- /(<*, •),•••, /(<*, •))
элементов ^ и для произвольного х € Яп
У>(х) = {г е ЛГ* : /<(*) > 0} С ЛГ*.
Г%) = {* € Мк : /,(*) < 0} С Л^.
Если для всех а € Л', 6 € В' выполнены неравенства
|У>(а)|>*/2, \УЦЪ)\>к/2,
то называется разделяющим комитетом множеств А' и В'. В этом случае полагаем
А = {х € Дг< : \\г>{х)\ > /с/2} , Б = {х £ Яп : \У~(х)\ > к/2} .
То. что <5 является разделяющим комитетом множеств А' и В' эквивалентно тому, что последовательность К — (сьсг,... ,с*) является комитетом системы (1): для всякого а* £ А' и большинства членов К выполнено неравенство /(с£,а*) > 0, а для любого Ь* € В' и большинства членов К следует
/М*)<0.
В настоящее время наиболее изученным в теории комитетов является круг проблем, связанных с комитетной разрешимостью систем линейных неравенств. Широта сферы приложения комитетных конструкций, определенная универсальность комитетного подхода в задачах с противоречивыми условиями делают актуальным вопрос о существовании комитетных конструкций для других классов систем ограничений. Так, например, к проблеме построения
- 5 -
комитета несовместной системы ограничений, порожденной множествами над Яп (в частности, выпуклыми многогранными), приводит применение метода комитетов к несобственным задачам оптимизации при наличии директивных ограничений [21] определенного характера.
В ряде работ (см., например, [34]) отмечена важность задачи построения минимального комитета. Среди прочих критериев оптимальности, критерий минимальности суммы весов членов комитета во многих случаях наилучшим образом согласуется с содержательной стороной изучаемой проблемы. Комитет как дискретная аппроксимация [19, 20, 21, 22] собственного решения несовместной системы порождает и задачу наилучшей аппроксимации, то есть задачу построения минимального комитета. Оценки числа членов минимального комитета важны для итерационных процедур построения комитета системы линейных неравенств. Малое число членов комитета свидетельствует об устойчивости комитетного решающего правила, об определенных закономерностях в исследуемых объектах и т.д. В связи с трудностью задачи о минимальном комитете представляется актуальным поиск и изучение полиномиально разрешимых классов задач, исследование возможности оценки числа членов минимального комитета и построение эффективных приближенных алгоритмов для решения задачи о минимальном комитете.
Целью представленной диссертации является определение условий существования комитета для несовместных систем включений, образованных произвольными множествами над Яп, вычисление оценок числа членов минимального комитета произвольных несовместных систем включений, поиск полиномиально разрешимых подклассов для задачи о минимальном комитете, построение приближенных алгоритмов для ее решения.
В диссертации используется методика теории комитетов, дискретной оптимизации, выпуклого анализа, теории линейных неравенств и линейного программирования.
Представленная диссертация состоит из трех глав. Глава 1 является вводной. В ней даются необходимые определения и понятия теории комитетов. Далее в ней приводятся и обосновываются новые оценки числа членов минимального комитета для несовместных систем линейных неравенств, связанные со свойством совместности или разрешимости комитетом всевозможных
-6-
подсистем данной системы определенного ранга. Таким образом, в частности, дан ответ на вопрос, поставленный в 1981 году Вл.Д.Мазуровым [57): что можно сказать о числе членов минимального комитета системы линейных неравенств, если нет противоречий к-го рода, но есть противоречия к + 1-го рода?
В главе 2 получены достаточные условия существования комитетного решения для несовместной системы включений, порожденных произвольными множествами над Яп. Показано, что для существования комитета такой системы достаточно существования комитета для некоторой системы включений, образованной конусами, в частности, многогранными, если исходная система была образована выпуклыми многогранными множествами. Также в главе 2 указываются достаточные условии существования комитета большинства для несовместных систем включений, образованных многогранными, не обязательно выпуклыми, конусами и многогранными выпуклыми множествами над В2. Показано, что для рассматриваемых классов включений может быть построен комитет, не превосходящий по числу членов чиста включений в системе. Доказывается, что в случае когда система включений образована выпуклыми многогранными множествами и, в частности, выпуклыми многогранными конусами над Я2, задача построения комитета сводится к комитет-ному решению системы линейных однородных неравенств.
В главе 3 рассмотрена задача целочисленного линейного программирования, возникающая в связи с проблемой поиска комитета с наименьшим возможным числом членов — минимального комитета — для произвольной несовместной системы включений. В предположении, что множество решений тех максимальных совместных подсистем, на основе которых строится минимальный комитет, известно (при этом ни одно из них нельзя исключить), указываются нижние и верхние оценки числа членов минимального комитета (оптимума соответствующей задачи целочисленного линейного программирования). Для более узкого случая, когда число решений максимальных совместных подсистем, необходимых для построения минимального комитета, совпадает с числом включений, исследованы некоторые, возникающие в связи с этим, свойства матриц ограничений. Получены двусторонние оценки числа членов минимального комитета, являющиеся одновременно точными
-7-
- Київ+380960830922