Содержание к диссертации
Введение
ГЛАВА 1. Основы математического моделирования сложных систем на базе теории гиперграфов 24
1.1. Учет неопределенности параметров в математическом моделировании 24
1.2. Гиперграфы. Некоторые определения и свойства 28
1.3. Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах 34
1.4. Постановка задач и построение математических моделей на гиперграфах 38
1.4.1. Двукритериальная задача кадрового менеджмента 38
1.4.2. Математическая модель задачи управления космическим командно-измерительным комплексом 42
1.4.3. Математическая модель обучения сотрудников организации 48
1.4.4. Математическая модель назначения учителей в классы с учетом технологий обучения 52
1.5. Выводы по первой главе 60
ГЛАВА 2. Алгоритмы нахождения всех совершенных сочетаний и покрытий звездами много дольных однородных гиперграфов 61
2.1. Оценки числа ребер в -дольных -однородных гиперграфах 61
2.2. Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе 63
2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами 69
2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе 75
2.5. Алгоритм выделения совершенных сочетаний в многодольном гиперграфе 88
2.6. Алгоритм нахождения множества допустимых решений задачи покрытия -дольного -однородного гиперграфа звездами 91
2.7. Выводы по второй главе 101
ГЛАВА 3. Алгоритмические проблемы нахождения множества альтернатив для задачи о совершенном сочетании в много дольном гиперграфе в условиях неопределенности 103
3.1. Проблема неопределенности в математическом моделировании 103
3.2. Двухуровневый подход в математическом моделировании 108
3.2.1. Моделирование на нижнем уровне 109
3.2.2. Моделирование на верхнем уровне 121
3.3. Интервальные модели и многокритериальность 126
3.3.1. Общая постановка интервальных оптимизационных задач на гиперграфах 127
3.3.2. Сведение интервальной задачи к 2-критериальной 130
3.3.3. О разрешимости задач многокритериальной оптимизации с помощью алгоритмов линейной свертки критериев 132
3.3.4. Исследование разрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о сочетаниях с критериями вида MAXSUM на 3-дольном гиперграфе 133
3.4. Выводы по третьей главе 138
Заключение 139
Литература 141
- Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах
- Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе
- Алгоритм нахождения множества допустимых решений задачи покрытия -дольного -однородного гиперграфа звездами
- Общая постановка интервальных оптимизационных задач на гиперграфах
Введение к работе
Актуальность проблемы. Диссертационная работа посвящена разработке методов математического моделирования дискретных слабо структурированных процессов, для которых характерны множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных. Как часть этой проблемы в настоящей работе рассматриваются различные постановки дискретных задач управления: задача обучения сотрудников организации [20], задача назначения учителей в классы с учетом технологий обучения [77], задача управления космическим командно-измерительным комплексом [7], задача выбора стратегии ведения строительства строительной компанией [34]. Классические подходы моделирования таких задач оказываются недостаточными по той причине, что представление параметров и структуры этих задач с помощью инструментария классической теории графов [53] оказывается в принципе неадекватным в силу невозможности отразить в системном единстве сложную организацию их внутренних взаимосвязей, ограничиваясь только понятиями и обозначениями этой теории.
Для математического моделирования значительного количества дискретных систем оказывается вполне достаточным использование аппарата теории графов. Однако, не редки случаи, когда не удается достичь требуемой адекватности с его помощью, в силу чего возникает необходимость использования аппарата теории гиперграфов. Обычно попытка представить гиперграф в виде соответствующего графа приводит к появлению ложных «допустимых» решений. Например, на 4-вершинном множестве V = {1,2,3,4}
определен гиперграф с множеством ребер Е = {el,e2,e3}, ех =(1,2,3), е2= (1,3,4), еъ =(1,2,4), изображенный на рис.1. Попытка представить эти ребра треугольниками, построенными из ребер графа на рис.2, составляющих множество {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)), приводит к тому, что в
5 результате получается «ложный» треугольник, состоящий из ребер (2,3), (2,4), (3,4), приводящий к появлению несуществующего элемента в исходных
данных гиперграфовой задачи.
Рис. 1. 4-вершинный гиперграф G = (V,E), Е = {ех, е2, е3}, е, = (1,2,3), е2 =(1,3,4), ег =(1,2,4)
Рис.2. Представление ребер гиперграфа на рис.1 треугольниками, состоящими из гоа&овых оебеи
В качестве еще одной причины, по которой невозможно представить
гиперграфовую задачу в виде теоретико-графовой, можно назвать реально
существующее свойство неаддитивности функций, задающих веса ребер
гиперграфов. Суть этого свойства заключается в том, что на практике
оказывается нереальным определить правило или алгоритм, который
представлял бы вес ребра гиперграфа в виде суммы весов вершин этого ребра
или графовых ребер, определенных на множестве этих вершин.
Автором предлагается концепция двухуровневого моделирования рассматриваемых дискретных задач управления в условиях неопределенности. На нижнем уровне осуществляется моделирование исходных численных данных на базе экспертного оценивания [90]. Математическое моделирование верхнего уровня приводит к математическим постановкам многокритериальных задач на взвешенных гиперграфах. Весами ребер этих гиперграфов могут быть как действительные числа, так и интервалы или нечеткие множества. При этом заслуживают внимание следующие факты. Во-первых, к настоящему времени практически отсутствуют математические модели, сформулированные на базе теории гиперграфов, и тем более, отсутствуют алгоритмы (точные или приближенные) для экстремальных задач на гиперграфах. Известен лишь весьма ограниченный перечень задач на гиперграфах, относительно которых можно утверждать, что они являются NP-трудными [101]. Это утверждение в полной мере относится и к рассмотренной в диссертационной работе задаче о совершенных сочетаниях на многодольном гиперграфе и задаче покрытия много дольного однородного гиперграфа простыми звездами. Поэтому актуальной является разработка как точных переборных, так и приближенных малотрудоемких (полиномиальных) алгоритмов для решения этих задач. Наряду с этим актуальными также являются методы структурирования содержательных описаний дискретных задач управления в условиях неопределенности, для которых их данные в математической постановке заданы экспертными оценками.
Цель и задачи диссертационного исследования. Основной целью настоящей работы является разработка (на содержательном примере задачи обучения сотрудников организации, задачи назначения учителей в классы с учетом используемых технологий обучения, задачи управления космическим командно-измерительным комплексом, задачи выбора стратегии ведения строительства строительной компанией) двухуровневого подхода к математическому моделированию дискретных задач со сложной внутренней
7 структурой в условиях неопределенности. Поставленная цель требует решения следующих задач:
разработка в качестве основной составляющей модели нижнего уровня новых методов структурирования данных на базе идеи метода аналитической иерархии [81];
разработка на базе конкретных слабоструктурированных задач методов построения гиперграфовых моделей верхнего уровня;
исследование структурной сложности гиперграфовых моделей, а также вычислительной сложности (на базе обоснования свойства полноты) алгоритмов распознавания и нахождения допустимых решений задач о совершенных сочетаниях и покрытии гиперграфа звездами;
- разработка алгоритмов распознавания и алгоритмов нахождения
допустимых решений задачи о совершенных сочетаниях на гиперграфе и
задачи покрытия гиперграфа звездами.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории алгоритмов с оценками, теории графов и гиперграфов, многокритериальной оптимизации, комбинаторного анализа и математического программирования, теории экспертных систем, теории нечетких множеств и интервального исчисления,
Научная новизна. Научную новизну диссертационного исследования содержат следующие положения:
Построены на базе аппарата теории гиперграфов математические модели многокритериальных задач обучения сотрудников организации, назначения учителей в классы с учетом используемых технологий обучения, управления космическим командно-измерительным комплексом, выбора стратегии ведения строительства строительной компанией.
Достижимые верхние оценки количества ребер в полном многодольном однородном гиперграфе, а также максимальной мощности множества
8 совершенных сочетаний и множества покрытий звездами многодольных гиперграфов.
Обоснование свойства полноты задачи о совершенных сочетаниях и о покрытии звездами многодольного гиперграфа, а также обоснование труднорешаемости этих задач в многокритериальной постановке.
Полиномиальное сведение задачи о совершенных сочетаниях на многодольном гиперграфе к задаче о максимальной клике на специальном графе.
Полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в много дольном гиперграфе.
Алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе.
Полиномиальный алгоритм сведения задачи покрытия многодольного однородного гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе.
Обоснование неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании с векторной целевой функцией, состоящей из критериев весового вида.
Практическая ценность полученных результатов и их реализация. Практическая значимость результатов исследования заключается в том, что полученные в работе результаты могут быть использованы при формировании систем поддержки принятия решений в процессе математического моделирования задач управления сложными системами в условиях неопределенности, в том числе задачи обучения сотрудников организации [68], задачи назначения учителей в классы с учетом технологий обучения [70], задачи управления космическим командно-измерительным комплексом [41, 42] и задачи выбора стратегии ведения строительства строительной компанией. Идеи обоснования неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенном сочетании на гиперграфе, обоснование представленных
9 алгоритмов могут быть использованы в дальнейших исследованиях в области дискретной многокритериальной оптимизации.
На защиту выносятся следующие основные положения:
Обоснованное свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами.
Вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов, на которых базируются рассматриваемые в диссертации математические модели: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами.
Обоснование труднорешаемости задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке.
Полиномиальный алгоритм проверки выполнения необходимых условий существования в многодольном однородном гиперграфе совершенного сочетания.
Алгоритм выделения всех совершенных сочетаний в много дольном однородном гиперграфе, включая вывод оценки вычислительной сложности этого алгоритма.
Полиномиальный алгоритм сведения задачи о покрытии ^-дольного -однородного гиперграфа звездами к задаче о совершенном сочетании.
Структурирование задачи управления в условиях неопределенности данных сложной системы методом двухуровневого моделирования. Алгоритм реализации метода аналитической иерархии для слабоструктурированной задачи выбора стратегии ведения строительства строительной компанией.
10 8. Доказательство неразрешимости с помощью алгоритмов линейной
свертки критериев интервальной задачи о совершенном сочетании на
гиперграфе с целевой функцией весового вида.
Апробация работы. Результаты исследования и основные его положения докладывались и обсуждались на заседаниях научно-методического семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2002-2004 гг.) и получили положительную оценку на следующих конференциях и симпозиумах, проводимых различными академическими учреждениями и высшими учебными заведениями России:
- на VIII Международном семинаре «Дискретная математика и ее
приложения» (МГУ, 2004);
- на IV Международной конференции «Новые технологии в управлении,
бизнесе и праве» (Невинномысск, 2004);
- на VIII Международной конференции «Образование. Экология. Экономика.
Информатика» (Астрахань, 2003);
- на IV Международной конференции молодых ученых и студентов (Самара,
2003);
- на Международной научно-практической конференции «Наука и практика.
Диалоги нового века» (Набережные Челны, 2003);
- на III Международной конференции «Новые технологии в управлении,
бизнесе и праве) (Невинномысск, 2003);
- на III Международной конференции молодых ученых и студентов (Самара,
2002);
- на Международной школе-семинаре по геометрии и анализу памяти Н.В.
Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета
«Лиманчик», 2002);
- на 11-ой Всероссийской конференции молодых ученых «Математическое
моделирование в естественных науках» (Пермь, ПГТУ, 2002);
- на Дальневосточной конференции студентов, аспирантов и молодых
ученых по математическому моделированию (Владивосток, 2002);
11 - на V Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2002);
- на X Международной конференции «Математика. Экономика.
Образование». II Международный симпозиум «Ряды Фурье и их
приложения» (Ростов-на-Дону, 2002);
- на IV научно-практической конференции «Решение научно-технических и
социально-экономических проблем современности» (Черкесск, 2002);
А также на научно-исследовательских семинарах по графам и гипергафам под руководством проф. А.А.Зыкова (Одесса, 2002, 2003) [71].
Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00-01-00652 «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», НИР Министерства Обороны РФ (в/ч 32103) «Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами» [42] и «Исследование путей и способов повышения эффективности управления орбитальными группировками на основе адаптации системы управления КА к изменяющимся условиям космической обстановки» [41]. В результате внедрения разработанного научно-методического аппарата повышена оперативность решения задач управления космическими средствами на 20-25% при возможности сокращения на 7-12% трудозатрат, а использование разработанных в диссертации полиномиального алгоритма и алгоритма выделения всех совершенных сочетаний позволило на 53% повысить оперативность формирования исходных данных в системе поддержки принятия решений.
Материалы диссертации опубликованы в 13 научных статьях и в 14 тезисах докладов.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 101 наименование, а также приложений, включающих в себя программу реализации алгоритма
12 проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе, описания нечеткой экспертной системы диагностики факторов выполнения работы, а также актов внедрения результатов диссертационной работы.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы диссертационного исследования, сформулирована его цель, описана структура и дан краткий обзор работы, изложены основные научные результаты, выносимые на защиту, раскрыта научная новизна и практическая значимость полученных результатов.
В главе 1 дан краткий анализ видов неопределенности информации, характерных для экономических, социальных и других систем, связанных с участием человека [10, 21, 51]. Для математического моделирования дискретных слабо структурированных процессов и систем, в которых присутствуют множественность критериев, стохастичность, интервальность или нечеткость значений исходных данных [5, 47, 49] , одним из наиболее подходящих математических инструментариев структурирования объектов моделирования является инструментарий теории гиперграфов. Математическое моделирование на гиперграфах позволяет отразить в системном единстве взаимосвязь и взаимодействие основных факторов, составляющих содержание исследуемой задачи.
В главе 1 приведены основные понятия теории гиперграфов [28, 32], которые используются в работе, поскольку, в отличие от графов, в научной и учебной литературе на русском языке практически отсутствуют доступные публикации. Пусть V - конечное непустое множество, а Е = {е} - некоторое семейство непустых подмножеств eczV, тогда пара (V,E) называется гиперграфом G = (V, Е) с множеством вершин V = {v} и множеством ребер Е = {е}. Гиперграф G = (V, Е) называется -дольным, если его множество вершин разбито на доли (подмножества) Vs, s = 1,2,..і, так, что: 1) всякая
13 пара вершин из одной доли является не смежной; 2) у всякого ребра ее Е каждая пара вершин v',v"ee принадлежат различным долям. Если в гиперграфе G нет кратных ребер и степень всякого ребра еєЕ равна (\е\ = ), то такой гиперграф называют -однородным. Гиперграф G называется 3-дольным 3-однородным, если множество вершин V разбито на три подмножества Vs, s = l,3 так, что в каждом ребре е = (v,,v2,v3) є Е его вершины принадлежат различным долям, т.е. vseVs, s = 1,3. В этом случае гиперграф G будем обозначать через G = (Vl,V2,Vi,E). Гиперграф G' = (V',E') называется частью гиперграфа G = (V,E), если ГсКиЯ'сЯ. Часть G' = (V',E') гиперграфа G = (V,E) называется его подгиперграфом, если он образуется из исходного гиперграфа G путем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть G' = (V,E') гиперграфа G = (V, Е) назовем реберным подгиперграфом, если из G удаляются только ребра.
Если в -однородном гиперграфе G = (V,E) число вершин п = \У\
кратно , то совершенным сочетанием ( -сочетанием) называется такой его реберный подгиперграф х = (V,Ex), в котором каждая компонента связности представляет некоторое ребро ее Е. Из этого следует, что мощность
\Е,\ = — = т.
В гиперграфе G = (Уг,У2,У3,Е) простой звездой называется такая его часть z = (Угг, V* Уъг ,Е2), ^'сК„ s = 1,3, в которой всякая пара ребер є', є" є Ег пересекается только в одной вершине veVxz. Степенью звезды r(v) называют число ребер в ней. Допустимым покрытием гиперграфа звездами x = (Vx,Ex), FcF, ЕхсЕ называем подгиперграф G' = (V',E') гиперграфа G = (V, Е), каждая компонента связности которого является простой звездой степени r(v) с центром в некоторой вершине V є V1, и
14 каждая вершина v є V3 инцидентна только одному ребру некоторой звезды с
центром v є Vx.
Ребро еєЕ гиперграфа G называется N-взвешенным, если ему поставлена в соответствие последовательность неотрицательных чисел wv(e)>0,v = l,2,...,N. Гиперграф называется N -взвешенным, если каждое его ребро является N -взвешенным.
Если задача формулируется на гиперграфе G = (V,E), то ее допустимое
решение определяется в виде реберного подгиперграфа x = (Vx,Ex), Vx с V,
Ех с Е, который может представлять собой совершенное сочетание
(покрытие гиперграфа звездами); X = X(G) = {х} - множество всех
допустимых решений (МДР) задачи на G. Математическое моделирование
реальных задач приводит зачастую к многокритериальным постановкам, для
которых «оптимальное решение» отсутствует. В условиях
многокритериальное возникает необходимость вместо оптимума искать
множество альтернатив [79, 83]. Качество допустимых решений хеХ
оценивается векторной целевой функцией (ВЦФ)
F(x) = (F:(x),F2(x),...,FN(x)), первые Nl критериев которой имеют вид
MAXSUM Fv(jc)=^wv(e)-^max,v = l,iV1, NX
ееЯЛ
критериев имеют вид МАХМШ (оценка по наихудшему)
F (х) = min wv(є) -> max,v = N^,N . В определении этих критериев
еєЕх
используются веса wv(e),v = 1,2,...,N, приписанные ребрам еєЕ . ВЦФ F(x)
определяет собой в МДР X паретовское множество ІсІ. В качестве искомого решения принимается полное множество альтернатив (ПМА), обозначаемое через Х. Подмножество JcX называется ПМА, если оно имеет минимальную мощность Х , и при этом выполняется равенство
F(X) = F(X), где F(X*) = {F(x) :хеГ} VJ*cJ. Принято говорить, что задача с ВЦФ F(x) обладает свойством полноты, если для всякого ее МДР
15 найдутся такие параметры ВЦФ, при которых выполняются равенства
Х =Х = Х [26].
Теорема 1.1. Всякая векторная задача о совершенных сочетаниях на і -дольных гиперграфах является полной, если ее ВЦФ содержит не менее двух весовых критериев вида MAXSUM и MAXMIN, и все ее допустимые решения х = (V,Ex) состоят из одного и того же количества ребер \ЕХ\, хєХ.
Теорема 1.2. Всякая векторная задача о покрытии ^-дольного -однородного гиперграфа звездами является полной, если ее ВЦФ содержит не менее двух весовых критериев вида MAXSUM и MAXMIN, и все ее допустимые решения х-(у,Ех) состоят из одного и того же количества
ребер \Ех\, хєХ.
В заключительной части главы 1 осуществляется постановка и построение математических моделей на гиперграфах: двукритериальной задачи кадрового менеджмента [68], задачи управления космическим командно-измерительным комплексом [41, 42], математической модели обучения сотрудников организации, математической модели назначения учителей в классы с учетом технологий обучения [70].
Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах
Специалисты часто сталкиваются с необходимостью расчетов при наличии нечетко заданных параметров или неточной информации. Такого рода ситуации могут возникать как вследствие недостаточной изученности объектов, так и из-за участия в управлении человека или группы лиц. Особенность подобных систем состоит в том, что значительная часть информации, необходимой для их математического описания, существует в форме представлений или пожеланий экспертов. Но в языке традиционной математики нет объектов, с помощью которых можно было бы достаточно точно отразить нечеткость представлений экспертов. В связи с тем, что при построении формальных моделей чаще всего пользуются детерминированными методами, то тем самым вносят определенность в те ситуации, где ее в действительности не существует. Таким образом, точный количественный анализ подобных систем по своей сути мало пригоден и неэффективен, а в реальных экономических, социальных и других системах, связанных с участием человека, не имеет требуемого практического значения. Он не в состоянии охватить нечеткость человеческого мышления. Мир руководителя - нечеткий. Это утверждение наводит на мысль о том, что для моделей процессов управления больше подошли бы нечеткие математические методы, нежели классические.
Значительное продвижение в этом направлении сделал Лотфи Заде в 1965 году. Предложенная им теория нечетких (размытых) множеств предназначалась для преодоления трудностей представления неточных понятий, анализа и моделирования систем, в которых участвует человек. Л.Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 либо 1. Такие множества были названы им нечеткими (fuzzy). Л.Заде определил также ряд операций над нечеткими множествами и предложил обобщение известных методов логического вывода. Введя затем понятие лингвистической переменной и допустив, что в качестве ее значений (термов) выступают нечеткие множества, Л.Заде создал аппарат для описания процессов интеллектуальной деятельности, включая нечеткость и неопределенность выражений. Дальнейшие работы профессора Л.Заде и его последователей заложили прочный фундамент новой теории и создали предпосылки для внедрения методов нечеткого управления в практику.
Для обращения с неточно известными величинами также применяется аппарат теории вероятностей. Однако случайность связана с неопределенностью, касающейся принадлежности или непринадлежности некоторого объекта к обычному нерасплывчатому множеству. Это различие между нечеткостью и случайностью приводит к тому, что математические методы нечетких множеств совершенно не похожи на методы теории вероятностей. Они во многих отношениях проще вследствие того, что понятию вероятностной меры в теории вероятностей соответствует более простое понятие функции принадлежности в теории множеств. По этой причине даже в тех случаях, когда неопределенность в процессе принятия решений может быть представлена вероятностной моделью, обычно удобнее оперировать с ней методами нечетких множеств без привлечения аппарата теории вероятностей [91].
При управлении различными процессами необходимо обеспечить в реальном масштабе времени расчет и оптимизацию режима, который гарантированно будет лежать в области допустимых режимов. Стандартно применяемые методы мало подходят для решения задач такого класса из-за возможности появления произвольных неконтролируемых ошибок в результатах при наличии погрешностей в исходных данных. Поэтому при управлении такими системами приходится ориентироваться на самое неблагоприятное (экстремальное) сочетание факторов неопределенности и использовать понятие гарантированного результата [38, 48]. Наиболее перспективными для нахождения решений с учетом отмеченных особенностей в условиях неопределенности являются интервальные [35,66,96,99,100] и нечеткие [1,65] методы. Применение интервальных методов в вычислительных процессах позволяет находить интервалы, гарантированно содержащие решения (множество решений) тех или иных задач, что позволяет более адекватно учитывать имеющуюся неопределенность постановки задачи.
В моделях управления наличие неопределенности может быть учтено представлением неопределенных параметров как случайных величин с известными вероятностными характеристиками, как нечетких величин с заданными функциями принадлежности или как интервальных величин с фиксированными интервалами изменения и нахождения решения задачи с помощью методов стохастического, нечеткого или интервального программирования. Как показывает практика, использование детерминированных моделей с четкими значениями параметров приводит к тому, что модель оказывается излишне грубой. Методы интервального анализа дают возможность построить модель для случая, когда для каждого из параметров задан интервал допустимых значений. Однако на практике в связи с наличием информации о том, что какие-то значения коэффициентов более допустимы, чем другие, описание этих параметров в виде нечетких множеств является более удачным. В этом случае на интервале дополнительно задается функция принадлежности, причем, если информация о различии допустимости имеет статистический характер, то эта функция может быть определена объективно, если нет - то субъективно, на основе приближенного отражения экспертом в агрегированном виде имеющегося у него неформализованного представления о значении этого параметра.
Основные приложения математического моделирования в условиях вышеуказанной неопределенности находятся в таких областях, как искусственный интеллект, лингвистика, поиск информации, процессы принятия решений, распознавание образов, медицинская диагностика, психология, педагогика, право, экономика и других областях человеческой деятельности.
Обоснование труднорешаемости нахождения ПМА векторной задачи о сочетаниях на гиперграфе
Цели и задачи современного образования, положенные в основу концепции личностно-ориентированного обучения школьников, направлены на разрешение противоречий между базой знаний, умений и навыков, которые закладывает традиционная школа, и постоянно меняющимися требованиями, предъявляемыми к личности современными общественно-экономическими отношениями. Возникающие противоречия между уникальностью каждой личности и авторитарной методикой обучения с её набором педагогических штампов усиливают направленность школьного образования на его гуманизацию, на формирование личности ученика как наивысшей ценности. Изменения в целевых установках общеобразовательной школы, ориентация на создание оптимальных условий для развития творческого потенциала ребёнка с учётом его индивидуальных особенностей обозначили нижеследующую задачу.
На пути реализации личностно-ориентированного обучения администрацией школы и педагогическим коллективом решается множество проблем. Одной из них является задача оптимального назначения учителей-предметников в классы. Решение этой задачи особенно важно при переходе параллели классов из начальной в общеобразовательную школу.
В конце учебного года учителем и школьным психологом с помощью анкетирования, тестов и итоговых оценок проводится диагностика обучаемости, обученности, а также способности учащихся самостоятельно учиться, которая выражается показателем эффективности самостоятельной умственной деятельности [9,54,86,87]. Полученные при этом результаты каждой диагностики классов заносятся в таблицу, что позволит учителю в дальнейшем наиболее целесообразно спланировать свою работу с классом по формированию необходимых знаний, умений и навыков по предмету, включая самоконтроль и самоуправление развитием. Более того, совокупность всех результатов диагностики позволяет ставить вопрос о наиболее целесообразном распределении учителей по классам рассматриваемой параллели с учетом их профессионального мастерства.
Исходными данными для построения математической модели организации личностно-ориентированного обучения в школе являются: U = {г/}- множество учителей, назначаемых в классы данной параллели. Т = {t}- множество современных педагогических технологий обучения [87]. Например, технология модульного обучения, интегральная технология, технология обучения с применением глобальных информационных сетей, технология уровневой дифференциации и методики диагностического целеполагания. К = {к}- множество классов данной параллели. Классы на основании результатов проведённых тестов отнесены к одному из уровней q є Q сформированности учебно-организационных умений. Множество этих уровней Q = {q} определяется следующим образом: q = 0 - у учащихся отсутствует мотивация учебной деятельности; q = 1 - учащиеся работают на репродуктивном уровне; q = 2 - учащиеся работают на конструктивном уровне; q = 3 - учащиеся работают на творческом уровне. Сформулируем следующую задачу. В каждый класс к є К требуется назначить одного из учителей UE.II , рекомендуя ему использовать в процессе обучения одну из технологий t є Т с учетом психолого-педагогических характеристик этого класса. Результатом такого назначения должно стать повышение уровня мотивации учебной деятельности, эффективности обучения в школе, повышение уровня обученности и самостоятельной умственной деятельности учащихся. Математическая модель рассматриваемой в настоящей работе задачи базируется на 3-дольном 3-однородном гиперграфе G = (v,E) = (Vx,V2,V3,E), который строится следующим образом. Вершины первой доли, т.е. v є Vx, взаимно однозначно соответствуют элементам множества учителей U. Каждой вершине vєVx, соответствующей учителю ueU, приписано число т(у), определяемое нагрузкой учителя, а именно количеством классов рассматриваемой параллели, в которых данный учитель будет работать. Каждая вершина второй доли v є V2 однозначно соответствует некоторому элементу из множества технологий обучения Т. Вершины третьей доли v є V3 взаимно однозначно соответствуют элементам множества классов К. Для построения множества рёбер Е = {е) рассматриваем всевозможные тройки вершин (v,,v2,v3) такие, что vxeVx, v2eV2, v3eV3. Всякую такую тройку называем допустимой, если учитель vx может вести занятия в классе v3, используя технологию обучения v2. Множество всех рёбер Е = {е} определяется как множество всех допустимых троек e = (vl,v2,v3), V.Viy / = 1,3. Тем самым 3-дольный 3-однородный гиперграф G = (yXiV2,V3,E) построен. В рассматриваемой задаче для данного гиперграфа G iyi,V2iVi,E) выполняются следующие условия: 1) в каждом ребре e = (vl,v2,v3)e Е выделена пара вершин v15v3, называемых концевыми для этого ребра; 2) вершины v eV2 являются внутренними вершинами, и множество V2 состоит из непустых попарно непересекающихся множеств V2(v3), v3eV3, причем каждый элемент veV2(v3) однозначно соответствует некоторой технологии t є Т; 3) концевые вершины v3 є V3Z являются висячими вершинами (степени 1); 4) для каждой вершины v из V1 указано число т(у), которое является параметром следующего условия: принадлежащая допустимому покрытию звезда с центром в вершине v имеет степень r(v) = m(v) и при этом выполняется равенство]Гт(у) = \V3\. По своему определению допустимое покрытие 3-дольного гиперграфа G = {у,Е)={у1У2,Уъ,Е) представляет собой такой его подгиперграф x = (Vx,Ex), Vx с V, ЕХ Е, в котором каждая компонента связности является звездой с центром в определенной вершине v є V1, причем ее степень равна r(v).
Алгоритм нахождения множества допустимых решений задачи покрытия -дольного -однородного гиперграфа звездами
Следовательно, если, согласно условию теоремы она является квадратной, то она состоит из m строк. При этом, по определению, таблица Tq состоит из ти частей Tq, k = \,m, откуда каждая часть Tq состоит из единственной строки. Это означает, что в тупиковом подграфе Sq каждая доля Uq состоит из единственной вершины. Последнее означает, что для каждого столбца к = 1,2,...,ти каждая его клетка Tq, 1 і Nq содержит один и тот же элемент, а именно единственную вершину, составляющую долю Uq. Эта вершина в силу непустоты клеток в каждой из строк таблицы МС смежна со всеми остальными вершинами, образующими соответствующие доли тупикового подграфа Sq. Отсюда, удовлетворяющий этому условию подграф является полным ти-вершинным графом, т.е. множество его вершин образует клику размерности m.
Следствие 2.3. Всякая вершина, принадлежащая некоторой ти-вершинной клике не будет удалена из множеств смежности Uq в процессе работы алгоритма ах, в силу чего соответствующая этой вершине строка в таблице МС сохранится до окончания работы алгоритма а,, и т.о. тупиковая таблица МС не будет являться пустой, т.е. Тq = 0. С учетом этого является справедливой Лемма 2.8. Если гиперграф G содержит совершенное сочетание, то на выходе алгоритма ах получаем непустой тупиковый подграф S . Доказательство. Если на подэтапе (t +1) алгоритма ах строка і = t + 2 вошла в состав тупиковой таблицы МС Т , то это означает, что в каждой из остальных частей Тк для нее существует хотя бы одна строка у, дающая непустое пересечение МС со строкой і, т.е. Tq r\Tq 0, A: = 1,2,...,ти. Тогда из этих строк, включая строку /, составим квадратную тхт таблицу V, которая согласно теореме 2.6 определяет собой т -вершинную клику. Лемма 2.8 доказана. На основании предыдущих лемм 2.6-2.8 можно сформулировать Примечание 2.4. Вхождение вершины в тупиковый подграф Sq является необходимым условием ее принадлежности хотя бы одной клике размерности т. Также является справедливой Лемма 2.9. Если для гиперграфа G на выходе алгоритма ах получаем тупиковый подграф S = 0, то G не содержит совершенного сочетания. Доказательство. На подэтапе (t +1) алгоритма ах вершина удаляется из специального подграфа Sq по той причине, что она не смежна ни с какой вершиной хотя бы одной доли в Sq, а, как известно, т -вершинная клика должна содержать взаимно смежные вершины-представительницы из каждой доли специального графа Sq. Поэтому, если по завершению всех подэтапов алгоритма ах из подграфа Sq удалены все вершины, а из таблицы МС Тч удалены все соответствующие этим вершинам строки, и тупиковая таблица Тч оказалась пустой, то из этого следует, что в специальном подграфе Sq нет взаимно смежных вершин-представительниц из каждой доли, а специальный подграф Sq не содержит m -вершинной клики. Лемма 2.9 доказана. Оценим вычислительную сложность т{ах) алгоритма ах. Трудоемкость алгоритма ах определяется трудоемкостью его работы с таблицами Тч, q = l,2,...,Ll, Ц=\их\ - количество вершин первой доли специального графа S. Заметим, что в процессе построения специального графа S для каждой вершины е формируются ее множества смежности и трудоемкость этого процесса для одной вершины е не превосходит числа \U\ вершин в специальном графе S. В процессе построения таблицы Tq каждое ребро подграфа Sq просматривается по два раза, причем число элементов в какой-либо строке таблицы Tq не превосходит \Uq\. Отсюда вычислительная сложность процесса формирования таблицы Tq ограничена сверху величиной 0(/9 ). В процессе построения тупикового подграфа Sq і і2 для каждой строки таблицы осуществляется не более \Uq\ операций поэлементарного сравнения и вычеркивания в таблице Тч некоторых строк. Причем, при вычеркивании отдельных строк и вычеркивании соответствующих вершин каждая вершина множеств смежности в таблице Тч просматривается конечное число раз. Таким образом, для вычислительной сложности получения тупикового подграфа и тупиковой таблицы справедлива верхняя оценка r(aq) 0(jfJq\ ), а верхняя оценка трудоемкости алгоритма ах с учетом [/ = \Е\ составляет т{а,) 0 Если в результате работы алгоритма ах получен непустой тупиковый подграф S(G), то для выделения совершенных сочетаний в многодольном гиперграфе используется представленный далее алгоритм а2. На вход алгоритма а2 подается m -дольный тупиковый подграф S (G), из которого в ходе работы алгоритма а2 выделяются m -вершинные клики, каждая из которых однозначно определяет собой некоторое совершенное сочетание в -дольном -однородном гиперграфе. На выходе алгоритма аг формируется множество клик размерности m, которое определяет собой МДР X = X(G) задачи о совершенных сочетаниях на гиперграфе.
Общая постановка интервальных оптимизационных задач на гиперграфах
Такой подход дает приближенные, но в то же время эффективные способы описания поведения систем, настолько сложных и плохо определенных, что они не поддаются точному математическому анализу. До работ Л.Заде подобная качественная информация, по существу, просто терялась - было непонятно, как ее использовать в формальных схемах анализа альтернатив. Теоретические же основания данного подхода вполне точны и строги в математическом смысле и не являются сами по себе источником неопределенности. В каждом конкретном случае степень точности решения может быть согласована с требованиями задачи и точностью имеющихся данных. Подобная гибкость составляет одну из важных черт рассматриваемого метода. Основные приложения данного подхода находятся в таких областях, как искусственный интеллект, лингвистика, поиск информации, процессы принятия решений, распознавание образов, медицинская диагностика, психология, право, экономика и других отраслях человеческой деятельности.
Для реальных сложных систем характерно наличие одновременно разнородной информации: 1) точечных замеров и значений параметров; 2) допустимых интервалов их измерения; 3) статистических законов распределения для отдельных величин; 4) лингвистических критериев и ограничений, полученных от специалистов-экспертов, и т.д. Реальные задачи содержат в себе нечеткие условия и некоторую нечеткость цели в связи с тем, что их постановку осуществляет человек. Учет фактора неопределенности при решении задач во многом изменяет методы принятия решения: меняется принцип представления исходных данных и параметров модели, становятся неоднозначными понятия решения задачи и оптимальности решения. Чаще всего конкретное содержание задачи требует обеспечения заданного уровня нечеткости решения. Наличие неопределенности может быть учтено непосредственно в моделях соответствующего типа представлением недетерминированных параметров как случайных величин с известными вероятностными характеристиками, как нечетких величин с заданными функциями принадлежности или как интервальных величин с фиксированными интервалами изменения. Попытки применения какого-либо конкретного математического аппарата (интервального анализа, статистических методов, теории игр, детерминированных моделей и т.д.) для принятия решений в условиях неопределенности позволяет отразить в модели лишь отдельные виды данных и приводит к безвозвратной потере информации других типов. Обычно на практике всегда имеется возможность наряду с точечной оценкой параметра (наиболее допустимым его значением) указать минимальное и максимальное значение (интервал), которые может принимать нечеткая величина. Кроме того, иногда удается построить и функцию, характеризующую допустимость каждого значения внутри заданного интервала на основе статистического материала или опроса группы экспертов. Теория нечетких множеств дает возможность проводить вычисления не с одним точечным значением, а с характеристической функцией и получать в результате вычислений нечеткую величину, для которой по максимуму значения функции может быть получена точечная (точная) оценка. Применение теории нечетких множеств позволяет провести также согласование различных нечетких решений при наличии нечетких целей, ограничений, коэффициентов, начальных и граничных условий. Даже в тех случаях, когда неопределенность в процессе принятия решений может быть представлена вероятностной моделью, обычно удобнее оперировать с ней методами теории нечетких множеств без привлечения теории вероятностей [4, 36]. В работе Atsushi Degawa было проведено сравнение аппарата теории нечетких множеств и теории вероятностей в случае, когда стохастические переменные определяются на тех же базовых множествах что и соответствующие нечеткие переменные. Делается заключение, что понятие неопределенности лучше выражается нечеткостью, чем случайностью, а аппарат теории нечетких множеств вычислительно намного проще, чем теории вероятностей [91]. В целом алгоритмы на базе нечетких множеств зарекомендовали себя на практике для самого разнообразного круга задач: 1. В системах искусственного интеллекта для управления работой технологического оборудования [38]. 2. Для оценки показателей качества программных средств [37]. 3. Применение нечетких уравнений и элементов нечеткой логики для диагностирования сложных систем - пакет программ Thermix - 2D для анализа динамики АЭС [97]. 4. Поведение диспетчерского персонала лучше всего описывается лингвистическими правилами поведения, а отклонение от принятых алгоритмов (ошибки и плохая работа диспетчеров, неисправности, возникшие помехи) хорошо моделируются с использованием нечетких алгоритмов [63]. 5. Автором были предложены модель диагностики дефляции структуры почвы пахотных площадей в условиях нечеткой информации [67], математическая модель диагностики выполнения работы с помощью уравнений нечетких отношений в индустриально-организационной психологии [69]. Получение во всех подобных моделях решений в нечеткой форме позволяет довести до сведения специалиста, принимающего решение, что если он согласен или вынужден довольствоваться нечеткой формулировкой проблемы и нечеткими сведениями о модели, то он должен быть удовлетворен и нечетким решением задачи.
