автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы коррекции данных несовместных линейных систем комбинаторного типа

На правах рукописи

КЛИМЕНКО Оксана Александровна

МЕТОДЫ КОРРЕКЦИИ ДАННЫХ НЕСОВМЕСТНЫХ ЛИНЕЙНЫХ СИСТЕМ КОМБИНАТОРНОГО ТИПА

05.13.17-теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва -2010

- 2 ДЕК 2010

004615048

Работа выполнена на кафедре теоретической информатики и дискретной математики математического факультета Московского педагогического государственного университета.

Научный руководитель:

доктор физико-математических наук, профессор

ГОРЕЛИК Виктор Александрович.

Официальные оппоненты:

доктор физико-математических наук, профессор

САМЫЛОВСКИЙ Александр Иванович.

кандидат физико-математических наук, старший научный сотрудник БРИТКОВ Владимир Борисович.

Ведущая организация: Московский городской педагогический

университет.

Защита состоится «6» декабря 2010 г. в 16 : 00 часов на заседании диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогического государственного университета: 119992, Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан ч.З » 1

Ученый секретарь

диссертационного совета мУРавьева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Как известно, моделирование сложных процессов и явлений - многошаговая процедура. Первоначальное описание информационной модели, имеющее вид системы уравнений или неравенств, связывающих параметры или характеристики объекта, может быть противоречивым, т.е. соответствующая система может не иметь решения, быть несовместной. Эта противоречивость может быть вызвана неточностью или неопределенностью исходных данных, чрезмерным упрощением действительных связей, абсолютизацией некоторых требований и т.д. Противоречивость можно считать одним из факторов плохой формализуемости, которая является частым атрибутом реальных задач, В современной математике уже не ставится под сомнение содержательность проблемы коррекции несовместных моделей. Несовместная модель может быть показателем сложности информационных процессов, а способы ее корректирования - отражением действительных процедур разрешения реальных проблем. Виды и способы коррекции могут быть различными и определяться внешними причинами, к которым, прежде всего, относятся содержательные особенности решаемой прикладной задачи.

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

В последние годы исследования в области методов коррекции несовместных СЛАУ ведутся весьма интенсивно. При этом особое внимание уделяется задачам структурной коррекции, которые, с одной стороны, в наибольшей степени отвечают потребностям практики, а с другой стороны, представляют наиболее сложный математический объект, трудно поддающийся аналитическому исследованию.

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

и предложен метод коррекции с использованием штрафных функций норм векторов невязок. Для плохо обусловленных систем со структурой Вандер-монда сформулирован регуляризованный критерий коррекции, разработан численный алгоритм, реализующий поиск оптимального решения в различных нормах. В.Л. Матросов, В.А. Горелик, С.А. Жданов, О.В. Муравьева применили методы коррекции к задачам распознавания. В.А. Горелик, И.А. Золтоева и Р.В. Печенкин рассмотрели проблему оптимальной коррекции несовместной системы с матрицами разреженной структуры и ее применение к задачам многокритериальной оптимизации. Естественным требованием для таких систем является сохранение разреженной структуры, что вносит ограничение на структуру матрицы коррекции, но с другой стороны уменьшает размерность задачи, что приводит к построению более эффективных алгоритмов.

В качестве одной из разновидностей структурных ограничений можно рассматривать матрицы комбинаторного типа, в строках которых элементы записаны так, что представляют подмножества данного множества или сочетания из всех его элементов.

В последние десятилетия изменилось соотношение дискретной и классической математики. Изменилась и роль комбинаторики - с помощью современных мощных компьютеров стало возможным делать переборы, ранее требовавшие сотни лет. Широкое распространение получили комбинаторные методы и комбинаторные устройства, связь, управление и функционирование которых основаны на комбинировании сигналов по принципу перестановок, размещений и сочетаний. Математические модели процессов и явлений, функционирующих на комбинаторных принципах, как правило, содержат много переменных величин и поэтому описываются системами с большим числом уравнений и неравенств. Кроме того матрицы этих систем содержат значительное количество нулей, т.е. являются разреженными. Очевидно, что такая особенность структуры матриц комбинаторного типа должна учитываться при подборе методов решения соответствующих задач. Любой канал связи содержит шумы, приводящие к неточности информационных сигналов, получаемых на выходе. Устройства и системы, работающие на комбинаторных принципах, не являются исключением. Поэтому системы уравнений и неравенств, описывающие работу таких устройств могут оказаться несовместными. Как правило, исследование структур, функционирующих по законам комбинаторики, осуществляется с помощью графов. В данной работе предлагается использовать системы уравнений и неравенств комбинаторного типа, позволяющие получить сведения не только о результатах работы таких структур, но и факторах существенно на нее влияющих, определять границы устойчивости и т.п. Ранее задачи коррекции исходных данных несовместных систем комбинаторного типа не рассматривались.

Проблема заключается в разработке математического аппарата исследования структурных задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа и построении устойчивых и эффективных численных методов решения таких задач.

Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений и неравенств.

Предмет исследования составляют вопросы структурной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа с матричными и векторными нормами в качестве критерия минимальности коррекции.

Основная цель - развитие подхода структурной коррекции к несовместным системам линейных алгебраических уравнений и неравенств с матрицами комбинаторного типа и разработка методов их оптимальной коррекции (по квадратичному и минимаксному критерию).

В основу исследования была положена гипотеза о том, что несовместная система Лх&Ь является результатом неточно заданных или противоречивых исходных данных: вектора а, от которого параметрически зависит матрица комбинаторного типа А, и что задачу коррекции можно свести к задаче оптимизации и получить такие оптимальные решения, чтобы гарантировать совместность и структурный вид скорректированной системы, при условии, что поправка минимальна.

Для достижения поставленной цели и проверки гипотезы решались следующие задачи:

1. Определение понятия матрицы комбинаторного типа и исследование особенностей ее структуры и свойств.

2. Исследование вопроса совместности системы линейных неравенств с матрицами комбинаторного типа.

3. Постановка и решение проблемы коррекции систем уравнений и неравенств с матрицами комбинаторного типа.

4. Разработка вычислительных алгоритмов для поиска оптимального решения задач коррекции несовместных систем линейных уравнений и неравенств с матрицами комбинаторного типа.

5. Применение методов коррекции систем комбинаторного типа к задачам принятия решений и распознавания.

Методологическую основу работы составляют современные методы линейной алгебры, математического анализа, теории оптимизации, анализа и обработки данных.

Научная новизна

• введено понятие матрицы комбинаторного типа и исследованы свойства комбинаторных систем линейных уравнений и неравенств;

• предложен метод решения задачи оптимальной коррекции несовместных систем комбинаторного типа с использованием квадратичного и минимаксного критериев;

• предложен метод коррекции кооперативных игр с пустым ядром на основе нового понятия Ср-ядра;

• рассмотрено приложение матриц и систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации.

Практическая значимость. Предложенные в работе методы исследования и коррекции несовместных систем линейных алгебраических уравнений

и неравенств комбинаторного типа могут быть использованы для разработки и анализа моделей информационных процессов и структур и решения на их основе многих прикладных задач в сфере планирования и управления. В работе эти методы использованы для коррекции пустых ядер отношений предпочтения в задачах принятия решений и построения разделяющих гиперплоскостей пересекающихся классов в различных подпространствах признакового пространства.

Вычислительные эксперименты показали работоспособность предлагаемых методов и алгоритмов.

Основные положения, выносимые на защиту:

• формализация задач оптимальной коррекции структурных систем линейных алгебраических уравнений и неравенств с матрицами комбинаторного типа при наличии ошибок данных в обеих частях системы;

• модификация алгоритма обобщенной наименьшей нормы (ТЬЫ) для решения задач коррекции обеих частей и при наличии ошибок только в левой части и комбинация его с методом штрафных функций;

• конкретизация методов исследования и коррекции несовместных СЛАУ и систем неравенств комбинаторного типа для решения несобственных задач принятия решений и распознавания.

Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях:

1. на X Международной научно-практической конференции «Информационные и коммуникационные технологии в образовании» Борисоглебск, 2009 г.,

2. на Всероссийской научно-практической конференции «Математика, информатика, естествознание в экономике и в обществе» Москва, 2009 г.,

3. на XVII Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2010» Москва, 2010 г.,

4. на VI Московской международной конференции по Исследованию Операций (01Ш2010), Москва, 2010,

а также на научно-методических семинарах кафедры информатики СевероВосточного государственного университета (г. Магадан) и кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета (г. Москва).

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Диссертация состоит из введения, трех глав, заключения и списка литературы. Во введении обосновывается актуальность темы исследования, определяется цель работы, формулируются задачи, которые необходимо было решить для достижения поставленной цели, указывается методологическая основа исследования, раскрывается научная новизна и практическая значимость диссертационной работы, выдвигаются основные положения, выносимые на защиту, представлено основное содержание работы.

В первой главе вводится понятие матрицы комбинаторного типа:

Определение 1.1. Матрицей комбинаторного типа назовем матрицу А={ау\сцГ0, (/,/) € К0, К0 сК},К = Ш) | / - 1,..., т;у = 1, .... п), К0 = № где К\ = {(»',/) | а,у е (М(п) = 2")}, М(п) - множество всех подмножеств множества, состоящего из п элементов.

Вообще говоря, можно различными способами записать матрицу такого типа. В данной работе рассматривается матрица комбинаторного типа, элементы которой упорядочены лексикографически:

"м 0 0 0 0 0 0 '

0 ап 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

°п*П а„+|2 0 0 0 0 0

°»+21 0 0 0 0 0

".1 а„1 "т) й™-2

где т = (2" - 1), первые п строк матрицы содержат по 1 ненулевому элементу и представляют сочетание из п элементов по 1 или, что то же самое, подмножества множества {1, ..., п) состоящие из одного элемента, следующие р = СЦ строк содержат по 2 элемента и являются подмножествами множества {1, ..., п), состоящими из двух элементов и т.д. Последняя строка содержит все п элементов. Очевидно, рд = С', где ц - число элементов в подмножестве. Таким образом, строки матрицы представляют наборы лексикографически упорядоченных подмножеств множества {1, ..., и}. В общем случае число ненулевых элементов матрицы А равно к = 2п-п 12 = 1"А • п, нулевых кй=2" -п- 2""' • и - и = (2"~' - 1)и.

Множество матриц комбинаторного типа обозначим Кп„. Исследована структура и свойства такой матрицы. На основе понятия матрицы комбинаторного типа вводится понятие системы линейных уравнений и системы линейных неравенств комбинаторного типа, записываемых в виде Ах = Ь,А е К„,„ и АхйЬ,А е КМ|„ соответственно. Рассматриваемые системы являются примером переопределенных систем, поэтому могут оказаться несовместными. Для получения качественной информации об информационном процессе, описываемом такой системой, целесообразно провести коррекцию исходных данных, которая для конкретной информационной модели реального процесса может быть интерпретирована по-разному.

Простейшим случаем коррекции для несовместной системы уравнений с матрицей комбинаторного типа является задача коррекции правой части, т.е. нахождения вектора А такого, что система

Ах = Ь + 1г

имеет решение и = пип|й|^.

Для р - 2 получаем хорошо исследованную задачу метода наименьших квадратов

т

Y/z,2 -»min

tr '

Ax-b + h.

Матрица А е К„,я в общем случае является прямоугольной, поэтому решение данной задачи следует искать либо используя понятие псевдообратной матрицы, либо сингулярного разложения (особенно полезно при анализе влияния ошибок входной информации на решение задачи МНК), либо QR-алгоритма.

Для р- оо получаем задачу линейного программирования:

w-> min

x,u,h

u>h, uk-hi Ax=b+h

Для систем неравенств с матрицами комбинаторного типа при р = 2 получим ту же задачу МНК, но с ограничениями в виде неравенств, для которой также предложены эффективные алгоритмы. Случай р = со аналогично сводится к задаче линейного программирования.

Гораздо больший интерес вызывают задачи коррекции левой части и обеих частей несовместной системы линейных уравнений и неравенств с матрицами комбинаторного типа. Такая коррекция позволяет более тонко исследовать и учитывать важные факторы и построить информационную модель, максимально соответствующую практическим нуждам. Поэтому в данной главе особое внимание уделено формулировке задач коррекции несовместных систем линейных уравнений и неравенств, когда ошибки присутствуют в левой и обеих частях системы и разработке методов их решения с использованием в качестве критерия коррекции нормы Гельдера с показателем р = 2, 00.

Задача 1.1. Дана несовместная система линейных уравнений Ах = Ъ, А е Кт „. При этом в общем случае 6*0. Требуется найти матрицу Я е Кт„, и вектор h е R™ такие, что система (А + Н)х = 6 + h совместна и выполнено условие

Задача 1.2. Дана несовместная система линейных уравнений Ax = b,A е Кт,„. При этом в общем случае 6*0. Требуется найти матрицу Я е Кт„ такую, что система (А + Н)х = Ь совместна и выполнено условие

\Ml=™iHl

Задача 1.3. Дана несовместная система линейных неравенств Ах й Ь, А е Ктп. При этом в общем случае 6*0. Требуется найти матрицу Я е Кт,„, и вектор

he Rm такие, что система (А + Н)х <b + h совместна и выполнено условие

\lHh}\p=nAfHh]\p

Задача 1.4. Дана несовместная система линейных неравенств Ах <, Ь, А е Ктп. При этом в общем случае Ъ ф 0. Требуется найти матрицу Н е К„,л такую, что система (А + Н)х < Ь совместна и выполнено условие

1Н=<™1 к

Для решения этих задач прежде всего рассмотрена процедура параметризации матрицы комбинаторного типа.

Структура матрицы комбинаторного типа такова, что по полученному в результате параметризации вектору а размерности к она может быть однозначно восстановлена. Зная размеры шхи и вектор а, можно однозначно построить матрицу Н(а) (элементы в строках матрицы упорядочены лексикографически).

|а„,если ¡ = аи } = М„

I />> 1 J 41

Нч=\

[0 в противном случае

гяер = 1, ...,к, q = l,...,C'„, 1= 1, ..., t= 1, ..., п, Мщ sM(t), M(t) - множество всех подмножеств индексов J, состоящих из t элементов, упорядоченное в лексикографическом порядке.

Данный факт позволяет в сформулированных задачах заменять понятие малости нормы матрицы на эквивалентное понятие - малость нормы вектора, что в свою очередь дает возможность свести рассматриваемые задачи к задачам безусловной оптимизации.

В работе построены матрично-векторные преобразования, позволяющие линеаризовать исследуемые задачи. Так для задачи 1.1 имеем: вектору х поставим в соответствие m х к матрицу Х(х) следующим образом: , если г = /,, s = /,!</ <k,i, е IA, j, eJA

х„ = <

[0 в остальных случаях 1А = {г.«,ЛеК\Ко} = {1!\М,...,к} ¿А = {}:0,ЛеК\Ко} = и1\1=\,...,к} Параметрическая матрица Х{х) позволяет получить тождество, связывающее дг, а, Ща) и Х(х): Лемма 1.1.

Ща)х=Х(х)а.

Алгоритм решения задач 1.1 и 1.2 основан на алгоритме обобщенной наименьшей нормы. При этом линеаризованная задача 1.1 имеет вид

¡/■(а,*)!

->Ш1П,

а

» п;

где г(а, х) = Ь-(А+Н(а))х и представляет вектор невязок исследуемой системы.

Для решения задачи 1.2 предлагается использовать механизм штрафования функции нормы вектора невязки для того, чтобы обеспечить равенство нулю вектора поправок правой части корректируемой системы. При этом линеаризованная задача 1.2 представима в виде

10

И +C||r(a,x)|

—> mm

a,x

где С - коэффициент штрафа, С —> со.

Для систем неравенств комбинаторного типа сформулирован и доказан критерий совместности.

Теорема 1.2. Достаточным условием совместности системы линейных неравенств комбинаторного типа вида Ах й Ь при аи * 0, / = 1 ,...,п является вы-

полнение условия

sign

\

/=1

2и+1+2/

яАГК+(-1)2"+ЧГК

k=l* J

<=1

Предложен метод коррекции несовместной системы линейных неравенств с матрицами комбинаторного типа. Рассмотрены модификации базового алгоритма для различных ситуаций помех в значениях исходных данных.

После приведения системы линейных неравенств комбинаторного типа к системе уравнений с помощью стандартного перехода задачу 1.3 можно сформулировать как задачу условной минимизации вида

||r(a,x,>>)|

-> min

СС аЛ.У^О

II II р

Так как (А + #(a)) х = b -у + h, то -h = r(a, х, у), а \\Н(а)\\р = ||а||р. Подвергнув векторы х, у и а линейным приращениям Ах, Ду и А а, с учетом Н(Аа)х=Х(х)Аа и отбрасывая слагаемое Н(Аа)Ах как величину второго порядка малости, получим:

г{а + А а, х + Ах, у + Ау) = г(а, х, у) -Х(х)А а - (А+Н (а))Ах - Ау тогда линеаризованная задача 1.3 формулируется

Х(х) А + Н [а) 1т

0

0

Да Ах Ау

-г а

> min

Дог.Дх.Ау,

Рассуждая аналогично можно прийти к решению задачи 1.4 с использованием механизма штрафования.

• mm ,

а,хДу, у'гО

где С - коэффициент штрафа, С —»со.

Рассмотрены различные варианты систем линейных уравнений и неравенств комбинаторного типа, предполагающие сведение к рассмотренным. Описаны изменения, которые необходимо внести в базовый алгоритм для решения задачи коррекции в случае противоречивости таких систем. Рассмотрены следующие частные случаи систем: с фиксированными (не подлежащими коррекции) строками, с отсутствующими строками и с повторяющимися по определенному принципу строками. Для указанных систем пред-

ложены схемы сведения к рассмотренным ранее системам для использования полученных для их решения алгоритмов.

Все предложенные алгоритмы протестированы на модельных примерах, приведены графические результаты анализа сходимости по аргументу и по значению целевой функции для предлагаемых алгоритмов.

Во второй главе рассмотрено приложение комбинаторных систем и методов коррекции несовместных систем такого типа для аппроксимации ядер отношений предпочтения на примере коррекции характеристической функции кооперативной игры. В частности, исследовано С-ядро кооперативной игры как пример системы комбинаторного типа вида

Y,x,ïv(S) VSczN,

¡eS i-i

Ненулевые элементы матрицы данной системы равны единице.

Пустота С-ядра рассмотрена как проблема противоречивости модели. Сформулированы задачи коррекции характеристической функции игры с пустым С-ядром.

Для устранения проблемы противоречивости модели кооперативной игры предлагается ввести новый принцип решения - С^-ядро, представляющее собой непустое множество вида

Ср =j*eX(v): \\А\\р -unin.gjr, £ v(S)-Av(S) VS cwj,

где X(v) - множество дележей, || • - норма Гельдера, А - вектор с компонентами Ду(л> В работе рассматривается норма Гельдера с показателем р = 2 и р- оо. Очевидно, если С-ядро игры существует, то С ¡г С.

Данный принцип решения кооперативной игры представляет коррекцию правой части несовместной системы комбинаторного типа. При этом можно рассматривать следующие условия на коррекцию:

1) Av(s)=£, VS Ф0, {/'}, ЛГ;

2)AvW>0, VS *0,ЛГ;

3) Av(iy=fo(S), VS *0, N, к< 1;

4) ДцугМЯ VS*0, N, к< 1.

5) AV(S) = max(0,e(S,x)), e(S,x) = v(S) - , S*0, N;

ieS

6)

7) EAKS)=-Ar(JV)-

S*0

Sc.V

Отдельным условием на коррекцию может выступать требование сохранения супераддитивности характеристической функции кооперативной игры, которое для условий 2,4, 6, 7 в общем случае не сохраняется.

В работе рассмотрено применение перечисленных условий на коррекцию, приведены их содержательные практические трактовки. Для каждого

случая рассмотрены варианты сводимости поставленной задачи коррекции к задаче линейного программирования (для р = от) и к задаче квадратичного программирования (для р = 2).

В вопросе о существовании С-ядра одной из основных является теорема Бондаревой о сбалансированных покрытиях, согласно которой С-ядро непусто тогда и только тогда, когда

^еЛ, Л = 1а:£А5 =1, VI е ЛГ, А5 £ О V.? * Лг[.

БсЯ I ЯП ]

Этот результат может быть получен из решения задачи линейного программирования:

£шах, £А5 = 1, Ау > 0, /еЛГ.

УсЛ' ¡3!

Эти условия в случае пустоты С-ядра позволяют использовать методы коррекции левой части несовместной системы неравенств комбинаторного типа, соответствующих приведенным покрытиям, для которых неравенства нарушены, т.е. получаем задачу

min

hl,

max(£As(v(S)-ÄvJ<v(jV)

которая может быть переформулирована следующим образом:

ЦдЦ^гпт

* 1>5У(5)-Г(Л0 УХеЛ-,

ЯсЛГ

где Л" с Л, А" = | А: £ А^(5) > у(Л01, Д„и£0.

max(XA5(v(S)-Av(J<vW

Теорема 2.3. Задача min

v N,

быть сведена к задаче линейного программирования

и —> min,

и > Аv(s)

при р - со может

ЕЛА

StzS

iS) ■■

Дц5)>0

Кроме того, в данной главе предлагается к рассмотрению новая информационная модель кооперативного взаимодействия, содержательно отличная от классического понятия - обобщенная кооперативная игра в форме характеристической функции. Данная модель основана на предположении, что каждый из участников кооперативного взаимодействия имеет заранее определенные предпочтения выигрыша аре-, и текущих вложений х1 в проект. Предполагается, что значение величины а,- для каждого участника индивидуально.

Определение 2.11. Обобщенной кооперативной игрой п лиц в форме характеристической функции будем называть объект <ЛГ, у(5), а>, где а = (а/,..., а„), функция удовлетворяет условиям:

1)у(0)=О;

2) v(5U2)>v(5)+v(7), если SnT=0 для любых коалиций S и Т.

Определение 2.12. Дележом для обобщенной кооперативной игры в форме характеристической функции называется вектор q = (q\, ..., q„), q¡ = a¡x¡, удовлетворяющий условиям коллективной

«i

и индивидуальной

ajx¡ >v¡V i е N

рациональности.

Определение 2.13. Дележ р предпочтительнее (доминирует) q по коалиции S, если p¡ > q¡, V i е S и < v(S).

ieS

Определение 2.14. Ядром обобщенной кооперативной игры называется множество всех ее недоминируемых дележей.

Теорема 2.4. Ядро обобщенной кооперативной игры описывается системой

^a¡X¡>v(S)\/S(zN

itS

ы

где x¡ -текущие вложения в проект, a¡x¡ - предпочтения выигрыша i'-го игрока.

Таким образом, получен новый объект кооперативной игры, позволяющий получить ответ на вопрос о достижимости и возможности увеличения выигрыша в результате объединения с другими участниками, содержательно иначе описывающий ситуацию кооперативного взаимодействия и основанный на понятии дележа - ядро СА:

СА =|*15>лМ5),£аЛ = v(N) VS с N j.

I IeS /=1 J

С^-ядро представляет систему линейных неравенств комбинаторного типа к которой в случае несовместности можно применить методы коррекции, рассмотренные в первой главе. Исследованы вопросы непустоты Сл-ядра обобщенной кооперативной игры как системы линейных уравнений и неравенств комбинаторного типа. Сформулирована задача коррекции несовместной модели обобщенной кооперативной игры для случая полной коррекции:

U* = v(i\0

и для коррекции только левой части системы, описывающей ядро

j(A¡ + H)x>v¡

U* = v(i\T) '

где элементы строк матрицы А\ представляют лексикографически упорядоченные подмножества (коалиции) множества всех игроков, элементы матрицы А2 - максимальное подмножество.

Сформулирована проблема совместности различных понятий решения кооперативной игры и ее разрешимости на основе методов коррекции. Определена связь нового объекта Ср-ядра с уже существующими принципами решения - С-ядром, Л^-ядром и вектором Шепли. Сформулированы и доказаны теоремы о совпадении или включении соответствующих множеств векторов. Теорема 2.5. Л^-ядро принадлежит С^-ядру при р = °о.

Теорема 2.6. Для того чтобы вектор Шепли принадлежал непустому С-ядру, необходимо и достаточно выполнение условия:

й-^у-й)

¿ты ЛП!

Гс/Мэ/

В частности, рассмотрена задача перемещения вектора Шепли в С-ядро, где принадлежность вектора Шепли С-ядру рассматривается как условие на коррекцию характеристической функции кооперативной игры. Все рассматриваемые в данной главе задачи решаются с использованием методов коррекции и на основе алгоритмов, представленных в первой главе.

Приведены численные примеры получения решений для кооперативных игр с использованием различных условий на коррекцию и норм в качестве критерия малости коррекции.

В третьей главе рассмотрено приложение систем комбинаторного типа к проблемам распознавания (на примере задачи кластеризации).

Опыт решения задач распознавания свидетельствует о том, что часто основная информация заключена не в отдельных признаках, а в их сочетаниях. К тому же не всегда известно сочетание каких именно признаков информативно, а каких нет. Кроме того, на практике всегда имеются ограничения по ресурсам, на создание средств измерения признаков или ситуации отсутствия данных по некоторым из них. В связи с указанной проблемой рассматривается задача построения решающего правила для разделения пересекающихся классов, работающего как для всего признакового пространства, так и для отдельных его подпространств (которые, по сути, представляют собой наборы сочетаний признаков).

Пусть имеется выборка из к + / точек, заданных в пространстве И", относящихся соответственно к двум различным классам К\ и Кг. Требуется поп

строить гиперплоскость вида .Р(х) = -Ь, разделяющую два данных

¿=1

множества с учетом возможного отсутствия некоторых значений параметров в задании объектов при минимальной коррекции координат в полном признаковом пространстве.

Предположим, что при отсутствии измерений некоторых признаков, их значения полагаются равными нулю, что идентично операции проектирования на соответствующее подпространство. Вследствие возмущений в измеряемом признаке выборки могут быть неразделимы гиперплоскостью, кроме

того, в случае разделимости во всем пространстве при отсутствии значений некоторых признаков соответствующие объекты (их проекции) могут не разделяться в некоторых подпространствах. Будем формулировать задачу кластеризации таким образом, чтобы одно решающее правило работало во всех подпространствах признакового пространства, включая его самого.

Рассмотрим первый объект, относящийся к классу К\, во всевозможных подпространствах »-мерного пространства (всего их 2" - 1). Для отделения объекта необходимо решить относительно вектора а и числа Ь систему вида:

«Л ^ъ

£7,Х, £ Ь

+ а2х]2 > Ь

а,х,, + а3х,3 > Ъ

- + ^ь

Построив для каждого объекта из представленной выборки такую систему, получим:

(Ха>Ь IУа<Ь '

, X/ - матрицы комбинаторного типа, содержащие ко-

ординаты /-го 0 = 1,..., к) объекта первого класса, - аналогичные матрицы для второго класса (/' = 1, ..., /). Необходимо найти коэффициенты а е ГГ и Ь е И такие, что указанная система является совместной.

Всего в системе будет содержаться (& + 1)(2" - 1) неравенств. Другими словами, имеем переопределенную систему линейных неравенств комбинаторного типа. Для случая несовместности такой системы была сформулирована задача коррекции.

Задача 3.1. Пусть дана несовместная система вида

-Ь + Уай О Я

X

г2

где Х = 2 , у=

Л.

Необходимо найти матрицу Я =

Нг

размера (к + 1)\2" - 1) х (и + 1),

а: п

У.

, Я* 6 К„, „, Н] е Кп„ такие, что система

16

(Нх-Х)а + Ь<, О (Нг+У)а-Ьй О совместна и выполнено условие

¡14 = ™«,-

В данной задаче имеем дополнительные ограничения на коррекцию: система состоит из к + / блоков по 2" - 1 строк. В каждом блоке имеем матрицу комбинаторного типа, в столбцах которой находятся равные значения коэффициентов. Этому ограничению есть очевидное геометрическое объяснение: объекты выборки - суть точки «-мерного пространства, параметры (признаки) Хд - координаты, очевидно, что каждая координата объекта определяется однозначно. Следовательно, в результате коррекции должны получить матрицу с теми же свойствами (т.е. и матрица коррекции Н должна соответствовать указанным ограничениям, которые примем как условия на коррекцию).

Для решения задачи 3.1 необходимо провести процедуру параметризации матрицы комбинаторного типа Н, Вектор, параметризующий матрицу Я(а) будет иметь размерность 2"~*-п(к + I), а = [а\ а2, ..., с/+']т, где «"векторы, параметризующие соответственно матрицы Н*, Н*, ¿=1 ,...,к, У = 1,...,/. Однако с учетом ограничений, связанных с особенностями рассматриваемой задачи (каждая матрица Х1 содержит к ненулевых элементов, п из которых различны), данное число можно значительно уменьшить: ...../

|Л«0«>если(г,5)еК \К0, (г + 5) еК\К0,1 = 1 ,...,т

Л"= л

[О, в противном случае

Вектор а в таком случае может состоять из п-лу ненулевых элементов. Формирование индексов происходит по следующему принципу: ар, если / = <7 и у' = и у = р

'' [0 в противном случае

где/) = 1, ..., п-(к +1),д = 1.....С'„, V = 1, ..., Г, I = 1, ..., п, е М(1), М(1) -

множество всех подмножеств индексовсостоящих из I элементов, упорядоченное в лексикографическом порядке.

Вектору а поставим в соответствие ту. к матрицу А (а) следующим образом: [аА, если г = /„, = V, 1 < V £ /„ е 1Х, у, е Зх

а- =„

[О в остальных случаях 1х = {/: (/,/) е К\К0} = {/, | V = 1,..., к}, Зх = {/: (¿.Л е К\- {/, IV = 1.....к)

После проведенных преобразований можно применить алгоритм коррекции левой части несовместной системы линейных неравенств комбинаторного типа, представленный в первой главе.

Предлагаемый алгоритм протестирован на модельных примерах.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Исследована структура и свойства матриц комбинаторного типа. Для систем неравенств с такими матрицами доказан критерий совместности.

2. Для задачи коррекции систем линейных уравнений с матрицами комбинаторного типа рассмотрены различные случаи коррекции: коррекция левой части и коррекция обеих частей системы. В качестве критерия минимальности коррекции использовались два критерия - квадратичный и минимаксный критерии. Для обоих критериев разработаны алгоритмы коррекции с учетом структуры задачи.

3. Рассмотрена особенность применения алгоритма обобщенной наименьшей нормы для решения задач коррекции несовместных систем линейных неравенств с матрицами комбинаторного типа. Разработаны модификации указанного алгоритма на случай коррекции только левой и обеих частей системы.

4. Рассмотрены приложения систем линейных уравнений и неравенств с матрицами комбинаторного типа, связанные с понятием ядра отношения предпочтения. Исследованы случаи несовместности систем, описывающих ядра этих отношений. Сформулированы новые принципы решения задач с пустыми ядрами (на примере кооперативных игр), основанные на методах коррекции.

5. Рассмотрено приложение систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации. Предложен метод построения линейного разделяющего правила, отделяющей объекты классов как во всем признаковом пространстве, так и в его подпространствах.

Вычислительные эксперименты показали, что задачи коррекции систем комбинаторного типа можно свести к соответствующим задачам оптимизации, а приведенные в работе алгоритмы позволяют с достаточно высокой точностью находить решение таких задач коррекции.

Полученные результаты могут использоваться в тех областях науки и техники, где требуется моделирование систем, основанных на противоречивой информации, имеющей комбинаторную структуру, где требуется определять параметры систем, основываясь на недостаточном количестве экспериментальных данных. При этом коррекция будет учитывать не только факт несовместности системы, но и структуру, которой эта система обладает.

Основное содержание диссертационной работы отражено в следующих

публикациях:

1. Клименко O.A. Применение методов коррекции несовместных линейных систем уравнений и неравенств комбинаторного типа в задачах принятия решений // Экономика, статистика и информатика. Вестник УМО. - 2010. -№ 4. - С. 132-136. - 0,6 п.л.

2. Клименко O.A. Оптимальная коррекция модели распределения средств в условиях кооперативного взаимодействия // Качество. Инновации. Образование. - 2010. - №9. - С. 69-75 - 0,6 п.л.

3. Горелик В.А., Клименко O.A. Методы коррекции несовместных линейных систем уравнений и неравенств комбинаторного типа и их применение к задачам классификации [Электронный ресурс] // Наука и образование: электронное научно-техническое издание / Моск. гос. техн. ун-т им. Н.Э. Баумана. - Режим доступа: http://www.technomag.edu.ru/doc/147195.html - 0,56 п.л. (авторский вклад 50%).

4. Клименко O.A. Задача коррекции для С-ядра кооперативных игр // Математика, информатика, физика и их преподавание: сборник трудов. - М.: МПГУ, 2009. С. 160-162. - 0,2 п.л.

5. Клименко O.A. Аппарат теории кооперативных игр в моделировании социально-экономических процессов // Молодой ученый. - 2010. - № 3. -С. 53-55-0,25 п.л.

6. Клименко O.A. Использование матриц комбинаторного типа для построения разделяющей гиперплоскости в задачах кластеризации // Молодой ученый. - 2010. - № 9. - С. 62 - 68 - 0,32 п.л.

7. Клименко O.A. Проблема устойчивости дележей в кооперативных играх в форме характеристической функции II Труды международной научно-практической конференции «Математика, информатика, естествознание в экономике и в обществе». Том 2. - М.: МФЮА, 2009. - С. 32-35 - 0,2 п.л.

8. Клименко O.A. Коррекция в кооперативных играх с пустым С-ядром // Сборник материалов X Международной науч.-практ. конф. «Информационные и коммуникационные технологии в образовании». - Борисог-лебск: БГПИ, 2009. - С. 196 - 198. - 0,2 п.л.

9. Клименко O.A. Получение «справедливых» устойчивых дележей в задачах кооперативных игр // Сб. тезисов ХУЛ Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов 2010». -М.: Издат. отдел фак-та ВМиК МГУ, 2010. - С. 33. - 0,06 п.л.

10. Горелик В.А., Клименко O.A. Методы коррекции в кооперативных играх с пустым ядром // Труды VI Московской международной конференции по исследованию операций (ORM2010) / Отв. ред. П.С. Краснощекой A.A. Васин. - М.: МАКС Пресс, 2010. - С. 336-338. - 0,11 п.л. (авторсю

вклад 50 %).

Подписано в печать: 02.11.10

Объем: 1 усл.п.л. Тираж: 100 экз. Заказ № 345 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского,39 (495) 363-78-90; www.reglet.ru

/

Введение.

Глава 1. Методы коррекции несовместных систем линейных уравнений и неравенств комбинаторного типа.

1.1. Понятие системы комбинаторного типа и постановки задач коррекции несовместных систем комбинаторного типа.

1.2. Решение задач коррекции системы линейных уравнений комбинаторного типа с использованием алгоритма ТЦЧ и его модификаций.

1.3. Критерий совместности системы неравенств комбинаторного типа и решение задач коррекции в случае их несовместности.

1.4. Смешанные системы комбинаторного типа.

1.5. Вычислительные эксперименты.

Глава 2. Применение методов коррекции систем комбинаторного типа к отношениям предпочтения с пустыми ядрами (на примере кооперативной игры).

2.1. Основные определения. Постановка проблемы.

2.2. Проблема пустоты ядра и возможные пути ее решения.

2.2.1. Понятие Ср-ядра.

2.2.2. Методы нахождения С^-ядра. Использование сбалансированных покрытий.

2.3. Сл-ядро отношения предпочтения в обобщенной кооперативной игре.

2.4. Проблема совместности различных понятий решения кооперативной игры и ее разрешения на основе методов коррекции.

2.5. Вычислительные эксперименты.

Глава 3. Применение методов коррекции систем комбинаторного типа в проблемах распознавания (на примере задачи кластеризации).

3.1. Постановка задачи кластеризации.

3.2. Подход к построению линейного решающего правила (разделяющей гиперплоскости) на основе минимальной коррекции

3.3. Разделяющая гиперплоскость в пространстве и подпространствах признаков (использование систем неравенств комбинаторного типа).

3.4. Вычислительные эксперименты.

Актуальность темы. Большинство экономических, социальных, биологических и технических процессов уже давно исследуются посредством» моделирования. Модель можно рассматривать как специальную форму кодирования информации. В отличие от обычного кодирования, когда известна вся исходная информация, и мы лишь переводим ее на другой язык, модель, какой бы язык она не использовала, кодирует и ту информацию, которую люди раньше не знали. Модель содержит в себе потенциальное знание, которое человек, исследуя ее, может приобрести, сделать наглядным и использовать в своих практических жизненных нуждах. Для этих целей в рамках самих наук развиты специальные методы анализа.

Как правило, для создания модели того или иного процесса или явления одного уравнения недостаточно — используется система уравнений или неравенств, представляющая собой совокупность элементов, находящихся в структурной взаимосвязи друг с другом и образующих определенную целостность. Принцип системности, пришедший из философии и естествознания и выросший в конечном итоге в теорию систем, показывает, что большая часть процессов и объектов окружающего мира могут быть описаны в виде системы. Широко используемой основой для моделирования многих дескриптивных и оптимизационных прикладных задач являются системы линейных алгебраических уравнений и неравенств. Такого рода системы встречаются в различных областях, причем они могут рассматриваться как самостоятельные объекты (например, если описывают линейные процессы или линейные регрессионные модели) или как вспомогательные (например, в случае линеаризации нелинейных моделей или дискретизации*непрерывных процессов).

Моделирование предполагает разделение входных параметров по степени важности влияния' их изменений на выходные. Чаще всего невозможно и не нужно учитывать все факторы, которые могут повлиять на значения интересующих величин. Таким образом, происходит огрубление модели, что может стать источником противоречивости (несовместности) системы, описывающей явление. Кроме того, несовместность модели может возникнуть и в силу иных причин, например, неточности измерений входных параметров: Очевидно, что такая модель не дает содержательной информации об исследуемом объекте. В данных условиях естественной видится коррекция противоречивой модели, которая позволит получить информацию как о процессе, так и о факторах, влияющих на его стабильность.

В некотором смысле противоречивые модели обладают большей способностью адаптации к реальным условиям.

Период начала систематизированных и интенсивных исследований задач многопараметрической коррекции несовместных систем линейных алгебраических уравнений пришелся на 80-е годы прошлого века. При этом в России (СССР) и за рубежом примерно в одно и то же время были независимо получены с использованием разного математического аппарата близкие результаты.

Прикладные задачи, вызвавшие обозначенные исследования, были различными. В зарубежных исследованиях указанное направление развивалось в связи с задачей обработки экспериментальных данных с помощью так называемого обобщенного метода наименьших квадратов — Total Least Squares (TLS), который является обобщением классического метода наименьших квадратов (МНК) на случай, когда шум присутствует в наблюдениях как зависимых, так и независимых переменных. Предполагая, что погрешности всех переменных подчиняются нормальному закону распределения с одними и теми же средним и дисперсией, было получено статистическое обоснование' TLS как метода, дающего оценки неизвестных параметров линейной модели, гарантирующего максимум функции правдоподобия. Как правило, системы линейных алгебраических уравнений, обрабатываемые с помощью TLS, это переопределенные системы полного ранга. Для сравнения - системы, возникающие при коррекции несобственных задач линейного программирования в канонической форме — как правило, являются недоопределенными. Главная задача TLS - определить квазирешение исследуемой линейной системы. В то же время, можно показать, что указанное квазирешение — это точное решение модифицированной системы, подвергшейся матричной коррекции по минимуму евклидовой нормы. Интенсивные исследования метода и его активное использование при решении прикладных задач начались в конце 80-х годов после появления работ бельгийского математика S. Van Huffei [96,97]. В 1993 году появилась публикация американского математика, профессора Дж.Б. Розена (J.B. Rosen) с учениками [94], послужившая началом развития нового научного направления - Structured Total Least Norm Approach. В этой работе была впервые поставлена и решена задача структурной коррекции переопределенной системы. Рассматривалась СЛАУ вида Ах = Ь, в которой вектор правой части b содержит неточные данные (ошибки измерения), левая часть системы - матрица А задана неточно в силу недостаточной априорной информации, кроме этого матрица А обладает определенной структурой.

Изучение проблемы несобственных (не имеющих решения в классическом смысле) задач математического программирования в нашей стране проводились научной школой Института математики и механики УрО РАН под руководством академика РАН И.И. Еремина [15, 16], [37, 38]. В частности, A.A. Ватолиным рассматривалась задача, которая заключалась в оптимальной многопараметрической коррекции несобственных задач линейного программирования в различных нормах. В его исследованиях задача оптимальной матричной коррекции несовместной системы линейных алгебраических уравнений по минимуму евклидовой нормы возникала в качестве вспомогательной задачи- при исследовании несобственных задач линейного программирования, записанных в канонической форме. Наиболее детально A.A. Ватолиным было выполнено исследование задач коррекции расширенной матрицы коэффициентов системы уравнений по минимуму евклидовой нормы и систем с фиксированными (не подверженными коррекции) строками и столбцами в расширенной матрице системы.

В конце 90-х годов в Москве (ВЦ. РАН и- МШ У) появился другой« центр исследования несовместных систем линейных алгебраических уравнений^ и несобственных задач линейного программирования под руководством! профессора В.А. Горелика (В.И. Ерохин, В.А. Кондратьева, О.В. Муравьева, P.P. Ибатуллин, Р.В. Печенкин, И.А. Золтоева и др.) [22], [24] - [26], [29, 30], [39], [42, 43], [53], [66], [72].

В монографии В.А. Горелика и В.И. Ерохина [24] приведено систематизированное описание методов решения задач оптимальной многопараметрической (матричной) коррекции несовместных систем линейных алгебраических уравнений с критериями оптимальности, построенными с использованием евклидовой нормы. Исследованы задачи коррекции, в которых часть элементов матрицы коэффициентов системы или часть элементов расширенной матрицы зафиксированы (задачи с фиксированными строками, задачи с фиксированными столбцами и задачи с совокупностью фиксированных строк и столбцов). Предложены модификации для критерия оптимальности коррекции с помощью взвешивания элементов матрицы коррекции как посредством ее левого и правого умножения на невырожденные весовые матрицы, так и с использованием индивидуальных неотрицательных весов для каждого элемента. Анализируются необходимые и достаточные условия существования решения задач матричной коррекции, вид оптимальных матриц коррекции и вид множеств решений скорректированных систем. Сформулированы возможные обобщения и модификации» постановок задач матричной коррекции, а также способы их регуляризации.

Муравьевой. О.В. [66] исследованы вопросы существования * и единственности решения в задаче матричной коррекции несовместной системы уравнений по критериям евклидовой и спектральной норм матрицы, свойства задачи аппроксимации несовместной системы линейных уравнений с коррекцией всех данных, получены аналитические выражения для. решения несобственной задачи линейного программирования первого рода, формализованной заданием порогового значения целевой функции и введением ее в качестве директивного ограничения при коррекции- для случаев с произвольным допустимым планом и с условием неотрицательности, сформулирована и решена задача линейной аппроксимации дискретно заданной функции по критерию, отличному от используемого в методе наименьших квадратов.

Ибатуллиным P.P. [43] рассмотрена задача коррекции всех данных для несовместных систем линейных уравнений с минимаксным критерием.

В последние годы исследования методов коррекции несовместных СЛАУ и их приложений в различных областях ведутся весьма интенсивно [42], [54], [63]. При этом особое внимание уделяется задачам структурной коррекции, которые, с одной стороны, в наибольшей степени отвечают потребностям практики, а с другой стороны, представляют наиболее сложный математический объект, трудно поддающийся аналитическому исследованию.

В работах В.А. Горелика, В.И. Ерохина и Р.В. Печенкина [25], [72] осуществлено развитие подхода структурной коррекции к несовместным СЛАУ с матрицами специального вида (блочной, матрицами Теплица и Вандермонда) и методов их оптимальной коррекции по квадратичному и минимаксному критериям. Получен метод решения- задачи оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений, обладающих блочной структурой; с использованием квадратичного и минимаксного критериев. Сформулирован критерий^ оптимальной коррекции несовместной системы с матрицей Теплица? и-Вандермонда при. наличии ошибок* только в левой, части и предложен метод коррекции с использованием штрафных функций норм векторов невязок. Для плохо обусловленных систем со структурой Вандермонда. сформулирован регуляризованный критерий коррекции, разработан численный алгоритм, реализующий поиск оптимального решения в различных нормах.

В.Л. Матросов, В.А. Горелик, С.А. Жданов, О.В. Муравьева применили методы коррекции к задачам распознавания [63]. В частности, ими« было рассмотрено применение обобщенного метода наименьших квадратов к задаче построения разделяющей гиперплоскости в пространстве признаков для двух классов объектов.

В.А. Горелик, И.А. Золтоева и Р.В. Печенкин [26], [42] рассмотрели проблему оптимальной коррекции несовместной системы с матрицами разреженной структуры и ее применение к задачам многокритериальной оптимизации. Естественным требованием для таких систем является сохранение разреженной структуры, что вносит ограничение на структуру матрицы коррекции, но с другой стороны уменьшает размерность задачи, что приводит к построению более эффективных алгоритмов.

В качестве одной из разновидностей структурных ограничений можно рассматривать матрицы комбинаторного типа, в строках которых ненулевые элементы записаны так, что представляют подмножества данного множества или сочетания из всех его элементов.

В последние десятилетия изменилось соотношение дискретной и классической математики. Изменилась и роль комбинаторики - с помощью современных мощных компьютеров стало возможным делать переборы, ранее требовавшие сотни лет. Широкое распространение получили комбинаторные методы и комбинаторные устройства, связь, управление и функционирование которых основаны на комбинировании сигналов по принципу перестановок, размещений и сочетаний. Комбинаторные методы используются для решения транспортных задач, в частности, задач по составлению расписания, выбора оптимальных маршрутов перевозок; для составления планов производства и реализации продукции, для оптимального распределения плановых заданий между предприятиями [56]. Кроме того, методы комбинаторики нашли применение в системах преобразования информации для передачи сигналов по каналам связи, например, при кодировании и декодировании, решении проблем синтеза, информационных систем. Машинный метод проектирования радиоэлектронной аппаратуры, решение задач компоновки и трассировки печатных проводников монтажных плат с помощью применения электронных вычислительных машин, разработка алгоритмов и языков программирования основаны также на комбинаторных принципах.

Математические модели процессов и явлений, функционирующих на комбинаторных принципах, как правило, содержат много переменных величин и поэтому описываются системами с большим числом уравнений и неравенств. Кроме того матрицы этих систем содержат значительное количество нулей, т.е. являются разреженными. Очевидно, что такая особенность структуры матриц комбинаторного типа должна учитываться при подборе методов решения соответствующих задач.

Как известно, любой канал связи содержит шумы, приводящие к неточности информационных сигналов, получаемых на выходе. Устройства и системы, работающие на комбинаторных принципах, не являются исключением. Поэтому системы уравнений и неравенств, описывающие работу таких устройств могут оказаться несовместными. Как правило, исследование структур, функционирующих по законам комбинаторики, исследуются с помощью графов. В данной работе предлагается для получения полной информационной картины действия» таких структур использовать системы уравнений и неравенств, комбинаторного типа, позволяющие получить сведения не только о результатах работы, но и факторах существенно на нее влияющих, определять границы устойчивости и т.п.

Проблема заключается в разработке математического аппарата исследования структурных задач оптимальной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа и построении устойчивых и эффективных численных методов решения таких задач.

Объектом исследования является теория коррекции несовместных систем линейных алгебраических уравнений и неравенств.

Предмет исследования составляют вопросы структурной матричной коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа с матричными и векторными нормами в качестве критерия минимальности коррекции.

Основная цель - развитие подхода структурной коррекции к несовместным системам линейных алгебраических уравнений и неравенств с матрицами комбинаторного типа и методов их оптимальной коррекции (по квадратичному и минимаксному критерию).

В основу исследования была положена гипотеза о том, что несовместная система Ах ~ Ь является результатом неточно заданных исходных данных: вектора а, от которого параметрически зависит матрица комбинаторного типа А, и что задачу коррекции можно свести к задаче оптимизации и получить такие оптимальные решения, чтобы гарантировать совместность и структурный вид скорректированной системы, при условии, что поправка минимальна.

Для достижения поставленной цели и проверки гипотезы решались следующие задачи:

1. Определение понятия матрицы комбинаторного типа и исследование особенностей ее структуры и свойств.

2. Исследование вопроса совместности системы линейных неравенств с матрицами комбинаторного типа.

3. Постановка и решение проблемы коррекции систем уравнений и неравенств е матрицами комбинаторного типа.

4. Разработка вычислительных алгоритмов для поиска оптимального решения задач коррекции несовместных систем линейных уравнений и неравенств с матрицами комбинаторного типа.

5. Применение методов коррекции систем комбинаторного типа- к задачам принятия решений и распознавания.

Методологическую основу работы составляют современные методы1 линейной алгебры, математического анализа, теории оптимизации; анализа и обработки данных.

Научная новизна

• введено понятие матрицы комбинаторного типа и исследованы свойства комбинаторных систем линейных уравнений и неравенств;

• предложен метод решения задачи оптимальной коррекции несовместных систем комбинаторного типа с использованием квадратичного и минимаксного критериев;

• предложен метод коррекции кооперативных игр с пустым ядром на основе нового понятия Ср-ядра;

• рассмотрено приложение матриц и систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации. Практическая значимость. Предложенные в работе методы исследования и коррекции несовместных систем линейных алгебраических уравнений и неравенств комбинаторного типа могут быть использованы для разработки и анализа моделей информационных процессов и структур и решения на их основе многих прикладных задач в сфере планирования и управления. В работе эти методы использованы для коррекции пустых ядер отношений предпочтения в задачах принятия решений и построения разделяющих гиперплоскостей пересекающихся: классов в различных подпространствах признакового пространства.

Проведенные вычислительные эксперименты показывают работоспособность предлагаемых методов и алгоритмов.

Основные положения, выносимые на защиту:

• формализация задач оптимальной коррекции структурных систем линейных алгебраических уравнений и неравенств с матрицами комбинаторного типа при наличии ошибок данных в обеих частях системы;

• модификация алгоритма обобщенной наименьшей нормы (ТЫЧ) для решения задач коррекции обеих частей и при наличии ошибок только в левой части и комбинация его с методом штрафных функций;

• конкретизация методов исследования и коррекции несовместных СЛАУ и систем неравенств комбинаторного типа для решения несобственных задач принятия решений и распознавания.

Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на следующих конференциях:

1. на X Международной научно-практической конференции «Информационные и коммуникационные технологии в образовании» Борисоглебск, 2009 г.,

2. на Всероссийской научно-практической конференции «Математика, информатика, естествознание в экономике и в обществе» Москва, 2009 г.,

3. на XVII Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2010» Москва, 2010 г.,

4. на VI Московской международной конференции по Исследованию Операций (01Ш2010), Москва, 2010, а также на научно-методических семинарах кафедры информатики СевероВосточного государственного университета (г. Магадан) и кафедры теоретической информатики и дискретной математики Московского педагогического государственного университета (г. Москва). Содержание и структура работы.

Диссертация состоит из введения, трех глав, заключения и списка литературы.

Заключение

В работе рассмотрены задачи матричной коррекции несовместных систем линейных уравнений и неравенств комбинаторного типа, которые помимо несовместности обладают дополнительным- свойством — определенной структурой, связанной с природой проблемы. Для такого рода задач предложены методы коррекции матрицы (расширенной матрицы) системы с ограничением на матрицу коррекции. Ограничение является структурным: скорректированная матрица должна также являться матрицей комбинаторного типа.

Рассмотрены применения предлагаемых методов к разным классам задач: решению систем линейных уравнений комбинаторного типа, систем неравенств, систем с фиксированными строками и столбцами. Рассмотрено применение коррекции к практическим задачам: нахождения непустого ядра игры и построение разделяющей гиперплоскости.

Получены следующие результаты:

1. Исследована структура и свойства матриц комбинаторного типа. Для систем неравенств с такими матрицами доказан критерий совместности.

2. Для задачи коррекции систем линейных уравнений с матрицами комбинаторного типа рассмотрены различные случаи коррекции: коррекция левой части и коррекция обеих частей системы. В качестве критерия минимальности коррекции использовались два критерия — квадратичный и минимаксный критерии. Для обоих критериев разработаны алгоритмы коррекции с учетом структуры задачи.

3. Рассмотрена особенность применения алгоритма обобщенной наименьшей нормы для решения задач коррекции несовместных систем линейных неравенств с матрицами, комбинаторного типа. Разработаны модификации указанного алгоритма на случай коррекции только левой и обеих частей системы.

4. Рассмотрены приложения систем линейных уравнений и неравенств с матрицами комбинаторного типа, связанные с понятием отношения предпочтения. Исследованы случаи несовместности систем, описывающих ядра этих отношений. Сформулированы новые принципы решения задач с пустыми ядрами (на примере кооперативных игр), основанные на методах коррекции.

5. Рассмотрено приложение систем комбинаторного типа и их коррекции в задачах распознавания на примере задачи кластеризации. Предложен метод построения линейного решающего правила, отделяющего объекты классов как во всем признаковом пространстве, так и в его подпространствах при минимальной коррекции их координат (значений признаков).

Вычислительные эксперименты, проведенные для рассмотренных задач коррекции, подтвердили гипотезу о том, что причиной несовместности системы являются противоречивые или неточные исходные данные, т.е. их коррекция приводит к совместным системам, а задачи коррекции систем комбинаторного типа можно свести к соответствующим задачам оптимизации. Приведенные в работе алгоритмы позволяют с достаточно высокой точностью находить решение таких задач коррекции.

Полученные результаты могут использоваться в тех областях науки и техники, где требуется моделирование систем, основанных на противоречивой информации, имеющей комбинаторную структуру, где требуется определять параметры систем, основываясь на недостаточном количестве экспериментальных данных. При этом коррекция будет учитывать не только факт несовместности системы, но и структуру, которой эта система обладает.

104

1. Акимов В.П. Теория кооперативных игр и моделирование распределения политического влияния: Дисс. . д-ра физ.-мат. наук: 05.13.18.-М., 2002.

2. Алгоритмы и программы восстановления зависимостей / В. Н. Вапник и др.; ред. В. Н. Вапника. М. : Наука, главная редакция физико-математической литературы, 1984. — 816 с.

3. Алипрантис К., Браун Д., Беркеншо О. Существование и оптимальность конкурентного равновесия : Пер. с англ. М. : Мир, 1995. - 384 с.

4. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. - 448 с.

5. Ашманов С.А. Линейное программирование. М. : Наука, 1981. — 304 с.

6. Бондарева О.Н. Теория ядра в кооперативной игре п лиц: Дисс. . канд. физ.- мат. наук: 01.01.09. Ленинград, 1962.

7. Бондарева О.Н. Методы решения кооперативных игр и их применение: Дисс. . д-ра физ.-мат. наук: 01.01.09. Ленинград, 1982

8. Бондарева О.Н. Некоторые применения методов линейного программирования к теории кооперативных игр. // Проблемы кибернетики. 1963, вып. 10.-с. 119-140.

9. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.-449 с.

10. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Статистические проблемы обучения. М. : Наука, 1974. - 415 с.

11. Васильев Ф.П. Численные методы решения экстремальных задач. — М. : Наука, 1988. 552 с.

12. Васильев В.А. Кооперативные принципы оптимальности в математической экономике: Дисс. . д-ра физ.-мат. наук: 01.01.09. — Новосибирск, 1988.

13. Васин А.А., Морозов В.В. введение в теорию игр с приложениями кэкономике. М., 2003. - 278 с.

14. Ватель И. А., Ерешко Ф.И. Математика конфликта и сотрудничества. —1 j1. М.: Знание, 1973. 64 с.

15. Ватолин A.A. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы // Ж. вычисл. матем. и матем. физ., 1984. Т. 24. - № 12. - С. 1907-1908.

16. Ватолин A.A. Несобственные задачи математического программирования и методы их коррекции: Дисс. . д-ра физ.-мат. наук: 01.01.09. Екатеринбург, 1992.

17. Воробьев H.H. Теория игр для экономистов-кибернетиков. М.: Наука, 1985.-272 с.

18. Гайнанов Д.Н. О комбинаторных свойствах несовместных систем линейных неравенств и многогранников // Математические заметки. 1985. -Т. 38. -№3. С. 463-474.

19. Гантмахер Ф.Р. Теория матриц. — Издание 5-е. — М.: Физматлит, 2006. 560 с.

20. Голуб Дж., Ван Лоун Ч. Матричные вычисления : Пер. с англ. М. : Мир, 1999.-548 с.

21. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высш. шк., 2004.-261 с.

22. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений. // Журн. вычисл. матем. и матем. физ. 2001. - Т. 41. -№ 11. - С. 1697-1705.

23. Горелик В.А. Элементы теории игр / В.А. Горелик, Т.П. Фомина. — Липецк, 1999. 128 с.

24. Горелик В.А., Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. М. : ВЦ РАН, 2004. - 196 с.

25. Горелик В.А., Ерохин В.И., Печенкин Р.В. Численные методы коррекции несобственных задач линейного программирования иструктурных систем уравнений. — М. : ВЦ РАН, 2006. 152 с.

26. Горелик В.А., Золтрева И.А., Печенкин Р.В. Методы коррекции несовместных линейных систем с разреженными матрицами. // Дискрет, анализ и исслед. операций. Сер. 2. 2007. - Т. 14. — № 2. - С. 62-75.

27. Горелик В.А. Клименко O.A., Методы коррекции- несовместных линейных систем уравнений и неравенств комбинаторного типа и их применение к задачам классификации // Наука и образование: электронное научно-техническое издание. 2010. - № 7.

28. Горелик В.А., Клименко O.A. Методы коррекции в кооперативных играх с пустым ядром // Труды VI Московской международной конференции по исследованию операций (ORM2010) / Отв. ред. П.С. Краснощекое, A.A. Васин. М.: МАКС Пресс, 2010. - С. 336-338.

29. Горелик В.А., Муравьева О.В. Матричная коррекция данных в задачах оптимизации и классификации. // Моделирование, декомпозиция и оптимизация сложных динамических процессов. М.: ВЦ РАН, 2004. -С. 94 - 120.

30. Горелик В.А., Муравьева О.В. методы коррекции данных в задаче распознавания образов // Тезисы докладов 2-й Московской конференции «Декомпозиционные методы в математическом моделировании и информатике». М.: ВЦ РАН, 2004. - С.39.

31. Гренандер У. Лекции по теории образов. Синтез образов: Пер. с англ. -Т.1. — М.: Мир, 1979.-384 с.

32. Гренандер У. Лекции по теории образов. Анализ образов: Пер. с англ. — Т.2. — М.: Мир, 1981. -446 с.

33. Гренандер У. Лекции по теории образов. Регулярные структуры: Пер. с англ. Т.З. -М.: Мир, 1983.-432 с.

34. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — М.: Наука, 1972.-368 с.

35. Дородницын A.A. Проблемы математического моделирования в описательных науках // Кибернетика. 1983. - № 4. - С. 6-10.1.107

36. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр. М.: Наука, 1981. -336 с.

37. Еремин И.И. Противоречивые модели оптимального планирования. -М. : Наука, 1988. 160 с.

38. Еремин И.И., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. — М.: Наука. Физматлит, 1983.-336 с.

39. Ерохин В.И. Свойства оптимальной одноранговой коррекции матриц коэффициентов несовместных неоднородных линейных моделей // Дискрет, анализ и исслед. операций. Сер. 2. 2002. — Т. 9. - № 1. - С. 33-60.

40. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. // Проблемы кибернетики. — М.: Наука, 1978.-Вып. 33.

41. Журавлев Ю.И. Избранные научные труды. — М.: Магистр, 1998. -420 с.

42. Золтоева И.А. Методы коррекции данных для формализации и решения задач многокритериальной оптимизации: Дисс. . канд. физ.-мат. наук: 05.13.17.-М., 2007.

43. Ибатуллин P.P. Методы коррекции и аппроксимации несобственных задач оптимизации и управления с минимаксным критерием: Дисс. . канд. физ.-мат. наук: 05.13.17. М., 2002.

44. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964. - 834 с.

45. Клименко O.A. Получение «справедливых» устойчивых дележей в задачах кооперативных игр // Сб. тезисов XVII Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов 2010». М.: Издат. отдел фак-та ВМиК МГУ, 2010. - С. 33.

46. Клименко O.A. Задача коррекции для С-ядра кооперативных игр // Научные труды МГТГУ. Серия: Математика; информатика, физика и их преподавание. М.: МЖУ, 2009. - С. 160-162.

47. Клименко O.A. Аппарат теории кооперативных игр в моделировании социально-экономических процессов // Молодой ученый. 2010. — № 3. — С. 53-55.

48. Клименко O.A. Коррекция в кооперативных играх с пустым С-ядром // Информационные и коммуникационные технологии в образовании. Сб. материалов X Международной науч.-практ. конф. Борисоглебск: ГОУ ВПО «БГПИ», 2009. - С. 196 - 198.

49. Клименко O.A. Использование матриц комбинаторного типа для построения разделяющей гиперплоскости в задачах кластеризации // Молодой ученый. 2010. - № 9. - С. 63-68.

50. Клименко O.A. Применение методов коррекции несовместных линейных систем уравнений и неравенств комбинаторного типа в задачах принятия решений // Экономика, статистика и информатика. Вестник УМО. -2010.-№4.-С. 77-87.

51. Клименко O.A. Оптимальная коррекция модели распределения средств в условиях кооперативного взаимодействия // Качество. Инновации. Образование.-2010. -№9.-С. 18-27.

52. Кондратьева В:А. Несобственные задачи линейной оптимизации и параметрическое программирование: Дисс. . канд. физ.-мат. наук: 05.13:17. -М., 2000.

53. Красников A.C. Матричная коррекция противоречивых данных в линейных оптимизационных моделях: Дисс. . канд: физ.-мат. наук: 05.13.17.-М., 2010.

54. Краснощеков П.С., Петров A.A. Принципы построения моделей. — М.: Изд-во МГУ, 1983. 264 с.

55. Кувырков П. П., Темников Ф. Е. Комбинаторные системы. М.: «Энергия», 1975. - 152 с.

56. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988.-200 с.

57. Лоусон Е., Хенсон Р. Численное решение задач метода наименьших квадратов / Чарльз Лоусон, Ричард Хенсон; пер с англ. М.: Наука. Гл. ред. физ.-мат. лит., 1986. - 232 с.

58. Льюс Р.Д. Райфа X. Игры и решения. Пер. с англ. М.: Изд-во ин. литры, 1961.-644 с.

59. Магарил-Ильяев Г. Г., Тихомиров В. М. Выпуклый анализ и его приложения. М.: Едиториал УРСС, 2003. - 176 с.

60. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. - 248 с.

61. Мандель И. Д. Кластерный анализ. М.: Финансы и Статистика, 1988. - 345 с.

62. Мулен Э. Кооперативное принятие решений: Аксиомы и модели; пер. с англ. М.: Мир, 1991. - 464 с.

63. Мулен Э. Теория игр с примерами из математической экономики: Пер. с франц. М.: Мир, 1985. - 200 с.

64. Муравьева О.В. Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации: Дисс. . канд. физ.-мат. наук: 05.13.17. -М., 2002.

65. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. Пер. с англ. М.: Наука, 1970. - 708 с.

66. Нуреев P.M. Курс микроэкономики: Учебник для вузов. М.: Издательство НОРМА, 2008. - 576 с.

67. Оуэн Г. Теория игр: Пер. с англ. М.: Мир, 1971. - 232 с.

68. Пападимитриу Х.Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. -М.: Мир, 1984. 512 с.

69. Петросян JI.A. Теория игр: Учеб. пособие для ун-тов / JI.A. Петросян, Н. А. Зенкевич, Е. А. Семина. М.: Высш. шк., Книжный дом «Университет», 1998. - 304 с.

70. Печенкин Р.В. Методы коррекции несовместных систем со структурными ограничениями: Дисс. . канд. физ.-мат. наук: 05.13.17. М., 2006.

71. Печерский C.JL, Беляева A.A. Теория игр для экономистов. Вводный курс: Учебное пособие. СПб.: Изд-во Европ. Ун-та в С.-Петербурге, 2001. - 342 с.

72. Плотинский Ю.М. Модели социальных процессов: Учебное пособие для высших учебных заведений. Изд. 2-е, перераб. и доп. - М.: Логос, 2001.-296 с.

73. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. - 470 с.

74. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: Пер. с англ. В 2 кн. Кн. 1. М.: Мир, 1986. - 350 с.

75. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: Пер. с англ. В 2-х кн. Кн. 2. М.: Мир, 1986. - 320 с.

76. Риордан Дж. Введение в комбинаторный анализ: Пер. с англ. М.: Изд-во иностр. литературы, 1963. - 288 с.

77. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации: Учеб. пособие. 2-е изд. - М.: ФИЗМАТЛИТ, 2005. - 368 с.

78. Теоретические основы информатики: учеб. пособие / В.Л. Матросов и др.. М.: Академия, 2009. - 352 с.

79. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1986.-288 с.

80. Ту Дж. Гонсалес Р. Принципы распознавания образов: Пер. с англ. М.: Мир, 1978.-412 с.83. .Управление большими системами / Сборник трудов. — Выпуск 26.1. — М.: ЖГУ РАН, 2009. 408 с.

81. Цурков В.И. Декомпозиция в задачах' большой размерности. — Ml: Наука, 1981.-352 с.

82. Чаки Ф. Современная теория управления. Нелинейные, оптимальные и адаптивные системы: Пер. с англ. — М.: Мир, 1975. 424 с.

83. Черников С.Н. Линейные неравенства. М.: Наука, 1968. — 488 с.

84. Beck A. The Matrix-Restricted Total Least Squares Problem

85. Combinatorial optimization: algorithms and complexity / Christos H. Papadimitriou, Kenneth Steiglitz. Englewood Cliffs, N.J.: Prentice Hall, 1982

86. Gilles D.B. Solutions to general non-zero-sum games. Contributions to the theory of games. IV (Kuhn H.W., Tucker A.W. eds.). Ann. Math. Studies, 40, -Princeton: Princeton Univ. Press, 1959, p. 47-86.

87. Golub G.H., Van Loan C.F. An analysis of the total least squares problem //SIAM Journal on Numerical Analysis, 1980, Vol. 17, No 3, pp. 883-893.

88. Korte B. Vygen J. Combinatorial Optimization. Theory and Algorithms.

89. Lemmerling P., Mastronardi N., S. Van Huffel. Fast structured total least squares algorithm for solving the basic deconvolution problem. SIAM J. Matrix Anal. Appl., 2000

90. Rosen J.B., Park H., Glick J. Structured nonlinear total least norm problems // UMSI reserch report. Minniapolis (Mn): Univ. of Minnesota. Supercomput. inst., 1995, 95/152, 11 p.

91. Rosen J.B. Park H. Glick J. Total least norm problems: formulation and solution // illUMSI reserch report. Minniapolis (Mn): Univ. of Minnesota. Supercomput. inst., 1993, 93/223. 18p.

92. Shapley L.S. A value for n-person games. Contributions to the theory of games. II (Kuhn H.W., Tucker A.W. eds.). Ann. Math. Studies, № 28, -Princeton: Princeton Univ. Press, 1953, p. 307-317.

93. Van Huffel S. Analysis of the total least squares problem and its use in parameter estimation // PhD thesis, Dept. of Electr. Eng., K.U.Leuven Belgium, June 1987.

94. Van Huffel S., Vandewale J. The Total Least Squares problems: Computational Aspects and Analysis. Philadelphia PA: SLAM Publishing, Vol. 35, №4, 1993. p. 660-662.