«ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ ...»

Теорема 1.2. Всякая векторная задача о покрытии l -дольного l однородного гиперграфа звездами является полной, если ее ВЦФ содержит не менее двух весовых критериев вида MAXSUM и MAXMIN, и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества построение математических моделей на гиперграфах: двукритериальной задачи кадрового менеджмента [68], задачи управления космическим командно-измерительным комплексом [41, 42], математической модели обучения сотрудников организации, математической модели назначения учителей в классы с учетом технологий обучения [70].

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

Одним из важнейших структурных свойств n -вершинного гиперграфа G = (V, E ) является количество ребер E в нем. В общем случае, когда речь справедлива следующая Теорема 2.1. В любом гиперграфе число ребер ограничено сверху полиномом, причем, эта верхняя оценка является достижимой, если n кратно l, т.е. в случае, когда доли гиперграфа G равномощны.

Из теоремы 2.1 следует, что для задач, формулируемых на l -дольных полиномиально ограниченным в случае, когда l представляет собой независящую от n константу. Важно отметить, что предлагаемые в главе математические модели базируются именно на гиперграфах такого вида.

В контексте проблемы обоснования оценок вычислительной сложности векторных задач на гиперграфах обоснование их труднорешаемости существенным образом опирается на оценки максимальной мощности их МДР. В случае полноты рассматриваемой задачи мощности искомого ПМА и МДР совпадают, и максимальная мощность МДР, очевидно, является нижней оценкой вычислительной сложности нахождения ПМА, и, следовательно, рассматриваемая задача труднорешаема, если эта максимальная мощность растет экпоненциально от числа ребер в полном гиперграфе. Через µ1 (n, l) обозначим максимальную мощность МДР задачи о совершенных сочетаниях на n -вершинном l -дольном l -однородном гиперграфе. Справедлива Теорема 2.2. При n, кратном l, максимальная мощность МДР задачи о равенством µ1 (n, l) = (m !) l 1, где m =.

Следствие 2.1. Максимальная мощность µ1 (n, l) МДР задачи о совершенных сочетаниях на гиперграфе растет экспоненциально от размерности n.

С учетом представленного в теореме 1.1 свойства полноты и следствия 2.1 является справедливой следующая теорема.

Теорема 2.3. Задача о совершенных сочетаниях на n -вершинном l дольном гиперграфе является труднорешаемой, если ее ВЦФ содержит не менее двух критериев вида MAXSUM.

В задаче о покрытии n -вершинного l -дольного l -однородного гиперграфа звездами обозначим через r = (r1, r2,..., rn ) вектор степеней звезд в допустимом покрытии x X ; сумму этих степеней обозначим m = rt.

Через J (n, l, n1 ) = {G} обозначим множество всех n -вершинных l -дольных l -однородных гиперграфов G = (V1,...,Vl, E ), n = n1 + m(l 1), в которых мощности долей Vs = n s, s = 1, l удовлетворяют следующим условиям:

V1 = n1, n1 m и оставшиеся доли являются равномощными ns = m, s = 2, l.

При выполнении этих условий допустимым решением задачи о покрытии гиперграфа звездами является такой реберный подгиперграф x = (V1,...,Vl, E x ) представляет простую звезду степени rt r с центром в соответствующей вершине vt V1, t = 1,2,..., n1. Количество таких звезд в покрытии x равно числу n1 вершин в первой доле. Через µ 2 (n, l, r ) обозначим максимальную по всем векторам степеней r мощность МДР задачи о покрытии n -вершинного l -дольного l -однородного гиперграфа звездами. Оказывается, что эта максимальная мощность не зависит от варьирования компонент данного вектора степеней r = (r1, r2,..., rn ), и является справедливой удовлетворяющего условию задачи о покрытии n -вершинного l -дольного l -однородного гиперграфа Следствие 2.2. Максимальная мощность µ 2 (n, l) МДР задачи покрытия гиперграфа звездами растет экспоненциально от размерности n.

С учетом представленного в теореме 1.2 свойства полноты и следствия 2.2 является справедливой следующая теорема.

Теорема 2.5. Задача о покрытии n -вершинного l -дольного l однородного гиперграфа звездами является труднорешаемой, если ее ВЦФ содержит не менее двух критериев вида MAXSUM.

Для распознавания наличия совершенного сочетания в многодольном полиномиальный алгоритм 1, который распознает и отсеивает ребра e E, не принадлежащие никакому совершенному сочетанию в G. Алгоритм специальным графом S = S (G ) = (U 1,...,U k,...,U m, R). Между ребрами e E и соответствие, причем ребро = (e, e) принадлежит R тогда и только тогда, когда ребра e, e E не пересекаются в G. Идея алгоритма 1 заключается в том, что всякому совершенному сочетанию в гиперграфе G взаимно однозначно соответствует m -гипервершинная клика в специальном графе S.

Сформулированы и доказаны необходимые условия принадлежности e U гипервершины удаляются из S. На выходе алгоритма 1 получается тупиковый подграф S = S (G ). Доказаны следующие достаточные условия.

Лемма 2.8. Если гиперграф G содержит совершенное сочетание, то на выходе алгоритма 1 получаем непустой тупиковый подграф S.

Лемма 2.9. Если для гиперграфа G на выходе алгоритма 1 получаем тупиковый подграф S =, то G не содержит совершенного сочетания.

Верхняя оценка трудоемкости алгоритма 1 составляет ( 1 ) O E Если в результате работы алгоритма 1 получен непустой тупиковый подграф S (G ), то для выделения совершенных сочетаний в гиперграфе используется представленный далее алгоритм 2. На вход алгоритма подается m -дольный тупиковый подграф S (G ), из которого в ходе работы алгоритма выделяются m -вершинные клики, каждая из которых однозначно определяет собой некоторое допустимое решение исходной задачи о нахождении множества X = X (G ) всех совершенных сочетаний на l дольном l -однородном гиперграфе. На выходе алгоритма 2 формируется множество клик размерности m, которое определяет собой МДР X = X (G ) задачи о совершенных сочетаниях на гиперграфе. Оценивая вычислительную сложность ( 2 ), отметим, что все клики формируются последовательно и бесповторно, при этом каждое ребро R просматривается не более, чем количество этих клик. Отсюда получаем оценку сложности перечисления алгоритмом 2 всех совершенных сочетаний в l -дольном l -однородном n n вершинном гиперграфе ( 2 ) O( R )(m !) l 1, m =.

Далее в главе 2 описывается процесс нахождения множества гиперграфа звездами, который состоит из трех этапов. Суть первого этапа заключается в полиномиальном сведении задачи покрытия звездами к задаче о совершенных сочетаниях на гиперграфе. Второй этап представляет собой последовательное выполнение алгоритмов 1 и 2, т.е. результатом второго этапа является МДР задачи о совершенных сочетаниях. Третий этап на базе МДР задачи о совершенных сочетаниях находит МДР задачи покрытия звездами данного l -дольного гиперграфа.

задачи о покрытии такого гиперграфа звездами к задаче о совершенных сочетаниях осуществляется с помощью представленного в работе алгоритма 3. На выходе алгоритма 3 имеем n -вершинный l -дольный l -однородный n = n + (rt 1) = n + (m n1 ) = ml. Результатом применения алгоритмов 1 и 2 к гиперграфу G является множество всех его совершенных сочетаний X (G ) = {x}.

Лемма 2.10. Всякое совершенное сочетание x в гиперграфе G однозначно определяет собой допустимое покрытие x гиперграфа G звездами.

двухуровневого подхода в математическом моделировании дискретных задач Двухуровневое моделирование заключается в следующем:

1) разработка общей схемы двухуровневого моделирования и выбор численных методов ее реализации;

2) разработка модели нижнего уровня, т.е. моделирование исходных данных и параметров задачи для модели верхнего уровня;

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

Математическая модель верхнего уровня – это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное решение поставленной задачи [6].

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

Далее в главе 3 исследуется разрешимость интервальной задачи о совершенных сочетаниях на 3-дольном гиперграфе с помощью алгоритмов линейной свертки критериев (АЛСК). Интервальная задача заключается в том, что в гиперграфе G = (V, E ) вес всякого ребра e E представляется интервалом, т.е. отрезком числовой прямой w(e) = [ w1 (e), w2 (e)]. Следует неопределенности и возникают в условиях неточных заданных параметров задачи [40]. В этом случае на МДР X = {x} задается интервальная целевая определению операции сложения интервалов получим значение ИЦФ интервальной задачи понимается такой элемент x 0 X, на котором значение ИЦФ достигает максимума. В этом случае рассматриваемая задача сводится к 2-критериальной задаче с тем же множеством допустимых решений X и Теорема 3.1. Паретовское множество задач с ИЦФ w(x) и ВЦФ F (x) совпадают.

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

Утверждение 3.1. Для любого вектора F ( x) = F ( x) целевых функций F ( x), = 1,2,..., N, является ПО.

Заметим, что АЛСК не всегда гарантируют нахождение всех ПО ~ X. Если ПМ X индивидуальной интервальной задачи и 2-критериальной задачи содержит такой элемент x *, на котором не достигает максимума значение свертки F (x) ни при каком 2, то эти задачи неразрешимы с помощью АЛСК.

Теорема 3.2. Для всякого 3-дольного гиперграфа G интервальная

MAXSUM

В Заключении сформулированы основные результаты и выводы диссертации, которые выносятся на защиту.

Пользуясь возможностью, автор выражает глубокую благодарность своему научному руководителю зав. кафедрой прикладной математики Карачаево-Черкесской государственной технологической академии доктору физ.-мат.наук, профессору Виталию Афанасьевичу Перепелице. Хочу выразить огромную признательность руководителю Одесского научноисследовательского семинара по теории графов и гиперграфов профессору Александру Александровичу Зыкову за постоянную поддержку и внимание к моей работе. Особую благодарность и признательность выражаю профессору Израилю Хаимовичу Сигалу за многократные полезные консультации и помощь, а также за доверие, оказанное мне как молодому ученому.

Благодарю профессора Елену Витальевну Попову, оказавшую техническую помощь при оформлении материалов диссертации.

ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОГО

МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ НА БАЗЕ

ТЕОРИИ ГИПЕРГРАФОВ

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

Наиболее поразительным свойством человеческого интеллекта является способность принимать правильные решения в обстановке неполной и нечеткой информации [80]. Построение моделей приближенных рассуждений человека и использование их в компьютерных системах будущих поколений представляет сегодня одну из важнейших проблем науки управления, а проблемы принятия решений в условиях неопределенности занимают в настоящее время особое место в информационных технологиях [33]. Математические методы стали широко применяться для описания и анализа сложных экономических, социальных и других систем [84]. Теория оптимизации создала совокупность методов, помогающих с использованием ЭВМ эффективно принимать решения при известных и фиксированных параметрах. Определенные успехи имеются и в том случае, когда параметры – случайные величины с известными законами распределения. Однако основные трудности возникают тогда, когда параметры обстановки оказываются неопределенными (хотя, может быть, и не случайными) и когда они в то же время сильно влияют на результаты решения.

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

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

Мир руководителя – нечеткий. Это утверждение наводит на мысль о том, что для моделей процессов управления больше подошли бы нечеткие математические методы, нежели классические.

Значительное продвижение в этом направлении сделал Лотфи Заде в 1965 году. Предложенная им теория нечетких (размытых) множеств предназначалась для преодоления трудностей представления неточных понятий, анализа и моделирования систем, в которых участвует человек.

Л.Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 либо 1. Такие множества были названы им нечеткими (fuzzy).

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

Для обращения с неточно известными величинами также применяется аппарат теории вероятностей. Однако случайность связана с неопределенностью, касающейся принадлежности или непринадлежности некоторого объекта к обычному нерасплывчатому множеству. Это различие между нечеткостью и случайностью приводит к тому, что математические методы нечетких множеств совершенно не похожи на методы теории вероятностей. Они во многих отношениях проще вследствие того, что понятию вероятностной меры в теории вероятностей соответствует более простое понятие функции принадлежности в теории множеств. По этой причине даже в тех случаях, когда неопределенность в процессе принятия решений может быть представлена вероятностной моделью, обычно удобнее оперировать с ней методами нечетких множеств без привлечения аппарата теории вероятностей [91].

При управлении различными процессами необходимо обеспечить в реальном масштабе времени расчет и оптимизацию режима, который гарантированно будет лежать в области допустимых режимов. Стандартно применяемые методы мало подходят для решения задач такого класса из-за возможности появления произвольных неконтролируемых ошибок в результатах при наличии погрешностей в исходных данных. Поэтому при управлении такими системами приходится ориентироваться на самое неблагоприятное (экстремальное) сочетание факторов неопределенности и использовать понятие гарантированного результата [38, 48]. Наиболее перспективными для нахождения решений с учетом отмеченных особенностей в условиях неопределенности являются интервальные [35,66,96,99,100] и нечеткие [1,65] методы. Применение интервальных методов в вычислительных процессах позволяет находить интервалы, гарантированно содержащие решения (множество решений) тех или иных неопределенность постановки задачи.

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

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

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

Отметим, что все недостающие термины и определения понятий теории графов достаточно полно изложены в монографиях [8,28,72,85,89].

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

Пусть V – конечное непустое множество, Е – некоторое семейство непустых подмножеств множества V. Пара (V, E ) называется гиперграфом G = (V, E ) с множеством вершин V = {v} и множеством ребер E = {e}.

размерностью этого гиперграфа. Если V = n и E = m (с учетом кратности ребер), то G называется (n, m) -гиперграфом.

Если вершина v V принадлежит ребру e E, то будем говорить, что множество всех инцидентных ей ребер. Число называется степенью вершины v, а число вершин в ребре deg(e) = e – степенью ребра e. Поскольку ребрами гиперграфа могут быть лишь непустые подмножества вершин, то степень любого ребра не меньше единицы, т.е. deg(e) 1.

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

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

На рис. 1.1 изображен гиперграф G = (V, E ) с множеством вершин e7 = (v1, v2, v8 ). В гиперграфе G вершина v9 является изолированной, а ребра e1 и e7 кратными. Ребра нарисованы в виде эллипсов, охватывающих инцидентные им вершины. Заметим, что ребра степени 2 можно изображать вместо эллипсов простыми линиями, как в случае обычных графов.

Гиперграфы G = (V, E ) и G = (V, E ) называются изоморфными, если существует сохраняющее отношение инцидентности взаимно однозначное соответствие между множествами вершин V, V и множествами ребер E, Гиперграф G = (V, E ) называется частью гиперграфа G = (V, E ), если V V и E E. Часть G = (V, E ) гиперграфа G = (V, E ) называется его подгиперграфом, если он образуется из исходного гиперграфа G путем удаления некоторых его вершин вместе с инцидентными им ребрами. Часть G = (V, E ) гиперграфа G = (V, E ) назовем реберным подгиперграфом, если из G удаляются только ребра [28].

Сочетанием в гиперграфе G называется такое подмножество E E, для любых двух различных ребер e и e которого их пересечение e e =, т.е. любые два ребра из E не смежные. Это сочетание называется максимальным, если оно содержит максимальное число несмежных ребер.

Сочетание назовем совершенным, если его ребра покрывают все вершины гиперграфа G, и каждая вершина v V инцидентна в точности одному ребру этого сочетания. Среди всех совершенных сочетаний выделяем такое, у которого число сочетания (G ) = E является минимальным, и называем его минимальным совершенным сочетанием данного гиперграфа G.

Если в гиперграфе G нет кратных ребер и степень всякого ребра e E равна l ( e = l ), то такой гиперграф называют l -однородным. Из этого определения следует, что у n -вершинного l -однородного гиперграфа G каждое сочетание является минимальным совершенным сочетанием, и число этого сочетания равно n. Ясно, что всякий 2-однородный гиперграф является графом. Таким образом, гиперграф – обобщение известного понятия «граф» [8,28,72,89]. При l = 3 гиперграф G будем называть 3-однородным.

Рис. 1.2. 11-вершинный 3 -дольный 3 -однородный Гиперграф G = (V, E ) называется l -дольным, если множество V его вершин разбито на доли (подмножества) Vs, s = 1, l так, что выполняются два условия: 1) всякая пара вершин из одной доли является не смежной; 2) у всякого ребра e E каждая пара вершин v, v e принадлежит различным долям. Гиперграф G называется 3-дольным 3-однородным, если множество вершин V разбито на три подмножества Vs, s = 1,3 так, что в каждом ребре e = (v1, v 2, v3 ) E его вершины принадлежат различным долям, т.е. v S VS, G = (V1,V2,V3, E ).

Рассмотрим гиперграф G = (V1,V2,V3, E ), V1 = {1,2,3,4}, V2 = {5,6,7}, V3 = {8,9,10,11}, E = {e1, e2,..., e5 }, где e1 = (1,5,9), e2 = (3,6,10), e3 = (4,7,11), e4 = (1,7,10), e5 = (2,5,8), представленный на рис. 1.2. Нетрудно увидеть, что называется тупиковым, если любое ребро e ( E \ E0 ) пересекается хотя бы с одним ребром из E0. Отметим, что максимальное (совершенное) сочетание, согласно этого определения, также является тупиковым. Гиперграф, изображенный на рис. 1.2, содержит два максимальных сочетания E1 и E2.

На рис.1.3 представлен 9-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) с множеством ребер E = {e}, где e1 = (1,4,7), e2 = (2,5,8), e3 = (3,6,9), e4 = (1,5,8), e5 = (2,4,7), e6 = (3,5,8).

Рис.1.3. 9-вершинный 3-дольный 3-однородный гиперграф На рис.1.4 и рис.1.5 для гиперграфа G = (V1,V2,V3, E ) представлены его совершенные сочетания x1 = (V, E x ) и x 2 = (V, E x ), в которых E x = {e1, e2, e3 ) В гиперграфе G = (V1,V2,V3, E ) звездой называется такая его часть z = (V1Z,V2Z,V3Z, E Z ), VSZ VS, s = 1,3, в которой любые ребра e, e E Z пересекаются в одной и той же вершине v V 1 Z, т.е. мощность V1Z = 1, и не пересекаются ни в какой вершине v V3Z. Звезда называется простой, если всякая пара ребер e, e E Z пересекается только в одной вершине v V1Z.

Степенью звезды r называют число рёбер в ней.

компонента связности является звездой с центром в некоторой вершине v V1, то G называем покрытием гиперграфа звездами. Допустимым которых равны r (v), и каждая вершина v V3 инцидентна только одному ребру некоторой звезды с центром v V1.

Рис.1.6. 14-вершинный 3-дольный 3-однородный гиперграф На рис.1.6 представлен 14-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) с множеством ребер E = {e}, где e1 = (1,3,9), e2 = (1,5,10), e3 = (1,6,11), e4 = (2,4,12), e5 = (2,7,13), e6 = (2,8,14), e7 = (1,4,9), e8 = (2,6,13).

По своему определению допустимое покрытие 3-дольного гиперграфа подгиперграф x = (Vx, E x ), V x V, E x E, в котором каждая компонента связности является звездой с центром в определенной вершине v V1, причем ее степень равна r (v). На рис.1.7 показано допустимое покрытие звездами с вектором степеней r = (r1, r2 ) = (3,3) гиперграфа, изображенного на рис.1.6.

Рис 1.7. Допустимое покрытие гиперграфа звездами Ребро e E гиперграфа G называется взвешенным ( N -взвешенным), если ему поставлено в соответствие некоторое неотрицательное число w(e) 0 (последовательность чисел называется взвешенным ( N -взвешенным), если каждое его ребро является взвешенным ( N -взвешенным).

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

Z 1 – задача о совершенных сочетаниях на гиперграфах;

Z 2 – задача о покрытии гиперграфа простыми звездами.

При формулировке задачи Z 1 считается заданным взвешенный n вершинный l -однородный гиперграф G = (V, E ). Допустимым решением задачи Z 1 является совершенное сочетание x = (V, E x ), E x E на гиперграфе При формулировке задачи Z 2 считается заданным взвешенный n вершинный l -однородный гиперграф G = (V, E ). Допустимым решением этой задачи является такой реберный подгиперграф x = (V, E x ), E x E гиперграфа G, в котором каждая компонента связности представляет собой простую звезду.

Обозначим через X = X (G ) = {x} множество всех допустимых решений (МДР) задачи Z 1 ( Z 2 ). Математическое моделирование реальных задач приводит зачастую к многокритериальным постановкам, для которых многокритериальности возникает необходимость вместо оптимума искать множество альтернатив (МА) [79,83].

Среди различных постановок векторных задач в обзоре [27] рассмотрим многокритериальную задачу, в которой качество допустимых решений x X оценивается векторной целевой функцией (ВЦФ) первые N 1 критериев которой имеют вид MAXSUM а остальные ( N N 1 ) критериев имеют вид MAXMIN В определении этих критериев используются веса приписанные ребрам e E. ВЦФ (1.1) – (1.3) определяет собой на МДР X задачи Z s, s = 1,2 паретовское множество (ПМ) X X, состоящее из Подмножество X 0 X называется ПМА, если оно имеет минимальную мощность X 0 и при этом выполняется равенство F ( X 0 ) = F ( X ), где Принято говорить, что задача Z s, s = 1,2 с ВЦФ (1.1) – (1.3) обладает свойством полноты [26,73], если для всякого МДР X = X (G ) = {x} этой задачи существуют такие параметры ее ВЦФ, при которых выполняются равенства многокритериальных дискретных задач, сформулированных на графах [26].

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

Пусть R N – евклидово пространство размерности N. Из определения ПМ и ПМА [79,83] вытекает, что справедлива следующая Лемма 1.1. Для всякой задачи с ВЦФ вида F : X R N выполняется равенство мощностей X 0 = F ( X ).

Для какой-либо задачи Z s, s = 1,2 с ВЦФ (1.1) – (1.3) рассмотрим конкретную индивидуальную задачу с МДР X, ПМ X и ПМА X 0. Добавим к ВЦФ (1.1) – (1.3) новые критерии. Тогда получим другую индивидуальную задачу, у которой новая (расширенная) ВЦФ определяет на прежнем МДР X другие множества альтернатив (МА). Возникает вопрос о том, как соотносятся «старые» и «новые» МА. С учетом того, что добавление новых критериев не изменяет значений «старых» критериев (1.1) – (1.3) на всех допустимых решениях x X, справедлива следующая Лемма 1.2. При любом N 2 для всякой индивидуальной задачи с ВЦФ (1.1) – (1.3) добавление новых критериев к этой ВЦФ либо оставит ПМ X и ПМА X 0 неизменным, либо пополнит их новыми решениями.

Теорема 1.1. Всякая векторная задача о совершенных сочетаниях на l однородных гиперграфах является полной, если ее ВЦФ (1.1) содержит не менее двух весовых критериев вида (1.2) – (1.3) и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества ребер E x, x X.

Доказательство. Рассмотрим какую-либо задачу выберем произвольное МДР X = X (G ), которое определяется данным n вершинным гиперграфом G = (V, E ). Для тривиальных случаев ( X = и X = 1) утверждение теоремы 1.1 очевидно.

Пусть X = X (G ) имеет мощность X 2 и на X определена ВЦФ (1.1) – (1.3). Покажем возможность задания весов ребер w(e) гиперграфа G так, что для определяемых этой ВЦФ ПМ X и ПМА X 0 будут выполняться равенства (1.4). Для этого в гиперграфе G ребра e E перенумеруем числами t = t (e) = 1,2,..., E и веса этих ребер определим следующим образом:

В настоящем доказательстве существенным образом используется равенство которое выполняется для каждого МДР X = X (G ), определяемого для всякого n -вершинного гиперграфа G. Из (1.5) и (1.6) получаем Обозначим разность R1, 2 = E1 \ E 2 для пары допустимых решений x1, x 2 X. Тогда для всякой пары x1, x 2 X имеем Пусть среди элементов множества R1, 2 R2,1 ребро e с наименьшим номером t = t (e) принадлежит R1, 2. Тогда из (1.1) – (1.8) вытекают неравенства F1 ( x1 ) > F1 ( x 2 ), F2 ( x1 ) > F2 ( x 2 ), которые означают, что любая пара x1, x 2 X является векторно несравнимой по ВЦФ (1.1) – (1.3).

Последнее с учетом леммы 1.1 означает выполнение равенства (1.4). Для N = 2 теорема 1.1 доказана.

В силу леммы 1.2 равенства (1.4) выполняются и при N 3, если для = 1,2 критерии (1.2) – (1.3) определим согласно (1.5), а для = 3,4,..., N критерии (1.2) – (1.3) определим произвольным образом.

Теорема 1.1 доказана.

гиперграфа звездами, отметим, что для нее, как и для рассмотренной выше задачи Z1 выполняется равенство (1.6). Отсюда, фактически повторяя доказательство теоремы 1.1, получаем, что является справедливой Теорема 1.2. Всякая векторная задача о покрытии l -дольного l однородного гиперграфа звездами является полной, если ее ВЦФ (1.1) содержит не менее двух весовых критериев вида (1.2) – (1.3) и все ее допустимые решения x = (V, E x ) состоят из одного и того же количества 1.4. Постановка задач и построение математических моделей на 1.4.1. Двукритериальная задача кадрового менеджмента Рассмотрим экономико-математическую модель процесса кадрового обеспечения организации с учетом основных положений и методов индустриально-организационной психологии [20].

Объекты моделирования представлены в виде трех множеств: M 1 – множество людей, прошедших отбор и рассматриваемых в качестве претендентов на множество M 2. Элементами множества M 2 являются вакантные (условно вакантные) должности, которые включены в бизнес-план данной организации. M 3 – множество видов обучения, выполняющих поддерживающую функцию, функцию социализации и мотивации представителей множества M 1 [20]. Элементами множества M 3 являются виды начального, повторного и развивающего обучения: рабочий инструктаж, ротация должностей, обучение в учебном центре на базе организации, обучение в вечерней школе, обучение на курсах повышения квалификации и переподготовки кадров, обучение в лицеях, колледжах, ВУЗах и академиях.

Сформулируем следующую задачу. Претендента из M 1, прошедшего определенный вид обучения из M 3, назначить на соответствующую его способностям, образованию и ожиданиям должность из M 2. Результатом такого назначения должно стать повышение эффективности деятельности организации, выраженное в повышении общего уровня выполнения работы, реализации профессионального потенциала каждого сотрудника и формирования резерва талантливых людей, способностями которых организация могла бы воспользоваться в будущем. С точки зрения математического моделирования эта задача представляет собой обобщение известной в теории дискретной оптимизации задачи о назначениях [82]. При определении допустимых решений этой задачи должны быть учтены ограничения на финансовые, производственные, трудовые и временные ресурсы, имеющиеся в распоряжении данной организации. Качество этих решений оценивается как экономическими (в рублях), так и социальнопсихологическими критериями. Значениями социально-психологических критериев могут служить результаты тестов (в баллах), которые проводятся для оценки детерминант, определяющих уровень и качество выполнения работы. Например, такими детерминантами в [20] являются способность, рассматриваемая задача формулируется как многокритериальная.

Математическая постановка рассматриваемой задачи базируется на 3дольном 3-однородном гиперграфе G = (V1,V2,V3, E ), который определяется следующим образом. Вершины первой доли V1 (второй доли V2 ) поставлены во взаимно однозначное соответствие указанному выше множеству претендентов M 1 (множеству должностей M 2 ), т.е. имеет место равенство мощностей: V1 = M 1 ( V2 = M 2 ). Вершины третьей доли V3 отражают множество видов обучения претендентов с учетом представленных выше перенумерованы индексом r = 1,2,..., L, и для каждого значения r определено максимально возможное количество mr людей, для которых организация может осуществить r -й вид обучения; обозначим R = mr. Каждому индексу r {1,2,..., L} поставим в соответствие множество V3r = {v} мощности V3r = mr. Тогда третья доля V3 определяется как теоретико-множественное объединение всех множеств V, т.е. V3 = UV3r.

определенного претендента, а v2 представляет определенную должность.

Тогда, если кандидат v1 может заполнить вакансию v2 после прохождения r го вида обучения, согласно стратегии принятия решений о распределении вакантных должностей в данной организации [20], то считаем, что множество E содержит mr ребер вида В противном случае множество E не содержит ни одного ребра вида (1.9). Ребро вида (1.9) условимся называть допустимой тройкой. Множество E всех ребер гиперграфа G = (V1,V2,V3, E ), V3 = UV3r образуется в результате теоретико-множественного объединения допустимых троек вида (1.9) по всем элементам v1 V1, v2 V2, v3 V3, r = 1,..., L.

В классической постановке задачи о назначениях, сформулированной на 2-дольном графе, как правило, термин «допустимое решение» означает совершенное (максимальное) паросочетание на этом графе. Допустимым решением рассматриваемой задачи на гиперграфе является всякое тупиковое представляем в виде его подгиперграфа x = (Vx, Ex ), Vx V, Ex E. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи о сочетаниях на гиперграфе G.

Каждому ребру e E вида (1.9) гиперграфа G = (V, E ) приписаны два веса w (e), = 1,2, которые означают w1 (e) = f1 (v1, v2, v3 ) – экономический представленный вершиной v3, и назначен на должность, представленную вершиной v2 ; w2 (e) = f 2 (v1, v2, v3 ) – социально-психологический эффект, т.е.

ожидаемый уровень социализации [20] претендента (в баллах) в этом же случае.

помощью векторной целевой функции (ВЦФ) состоящей из критериев вида MAXSUM Критерий F1 ( x) означает ожидаемый суммарный доход организации от указанного выше назначения. Критерий F2 ( x) означает ожидаемый уровень должности.

ВЦФ (1.10) – (1.11) определяет в МДР X паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) x [27]. В случае, если максимальную систему векторно несравнимых ПО из X, X 0 X.

Наиболее целесообразное решение выбирается из ПМА с помощью процедур теории выбора и принятия решений [50].

1.4.2. Математическая модель задачи управления космическим командно-измерительным комплексом Командно-измерительный комплекс – это система сооружений и оборудования, необходимого для контроля и управления полетом космических объектов, приема от них информации и ее обработки [7]. Для автоматизации, широкое применение различного рода радиотехнических систем и ЭВМ, Любое применение спутников предполагает, что с ними поддерживается хорошо налаженная, устойчивая двусторонняя радиосвязь.

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

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

несколькими десятками космических объектов различного назначения.

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

необходимо обозначить исходные данные, объекты моделирования, выделить основные параметры, определяющие решение задачи, а также выбрать метод ее решения.

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

Продолжительность сеанса радиосвязи со спутником (t ) равна интервалу времени между двумя моментами: первым, когда спутник входит в зону видимости, и вторым, когда спутник выходит из нее. Зона видимости – это область земной поверхности, пролетая над которой спутник может наблюдаться с измерительного пункта. Размеры зоны видимости определяются видом орбиты спутника (круговой или эллиптической), ее высотой, а также расстоянием смещения трассы спутника от центра зоны видимости. Кроме того, передача и прием сигналов со спутника, находящегося близко от горизонта, бывают неустойчивыми. Сеанс связи начинается не сразу от горизонта, а когда спутник поднимается над ним на некоторый угол, называемый минимальным углом возвышения антенны.

Поэтому продолжительность сеанса связи (t ) с учетом вышеуказанных условий рассчитывается специалистами Центра управления для каждой пары «спутник – измерительный пункт» и, очевидно, представляет собой интервальную оценку. Стоимость сеанса связи (s ) отражает экономические затраты на обслуживание используемых в сеансе радиотехнических систем и ЭВМ, на создание программ и оплату работы сотрудников командноизмерительного комплекса, задействованных в данном сеансе связи.

Очевидно, что стоимость сеанса связи является экспертной оценкой.

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

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

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

допустимых интервалов параметра t ;

2) статистических законов распределения и вероятностных оценок 3) экспертных (лингвистических) оценок параметров k и s.

Все эти параметры отражают ту или иную степень неопределенности данных задачи.

Исходные данные задачи представлены в виде нижеследующих множеств M i, i = 1,3.

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

представляет достаточное время для проверки правильности командной информации.

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

Существуют многофункциональные командно-измерительные системы:

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

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

Содержательная суть задачи заключается в том, чтобы информацию (программу) из M 1 через задействованный измерительный пункт из M передать на космический объект (спутник) из M 3. В результате полученное распределение с минимальными затратами экономических и временных ресурсов должно привести к повышению уровня достоверности передаваемой и получаемой информации. При определении решений этой задачи должны быть учтены ограничения на технические, временные, а также экономические ресурсы командно-измерительного комплекса. С точки зрения математического моделирования эта задача представляет собой обобщение известной задачи о назначениях [82].

Математическая постановка рассматриваемой задачи базируется на 3 дольном 3 -однородном гиперграфе G = (V1,V2,V3, E ), который определяется следующим образом. Вершины первой доли v V1 взаимно однозначно соответствуют элементам множества программ M 1. Каждая вершина второй доли v V2 взаимно однозначно соответствует элементам множества M задействованных измерительных пунктов командно-измерительного однозначное соответствие элементам множества спутников построения множества ребер E = {e} рассматриваем всевозможные тройки вершин (v1, v 2, v3 ) такие, что v1 V1, v2 V2, v3 V3. Всякую тройку называем допустимой, если программу v1 можно передать через измерительный пункт v 2 на космический объект v3. Множество всех ребер E = {e} определяется как множество всех допустимых троек e = (v1, v 2, v3 ), v s Vs, s = 1,3.

Допустимым решением рассматриваемой задачи является всякое совершенное сочетание в гиперграфе G. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи о сочетаниях на гиперграфе G. Содержательно МДР представляет множество всевозможных вариантов организации одновременных сеансов связи измерительных пунктов командно-измерительного комплекса со спутниками.

Каждому ребру e E гиперграфа G = (V1,V2,V3, E ) приписаны три веса продолжительность сеанса связи со спутником (t, мин) в случае, когда пунктом, представленным вершиной v 2 ; w2 (e) = f 2 (v1, v 2, v3 ) – стоимость сеанса связи ( s, руб ), отражает экономические затраты в случае, когда представленный вершиной v3, через измерительный пункт, представленный вершиной v 2 ; w3 (e) = f 3 (v1, v 2, v3 ) – качество передаваемой информации (k,%) в этом же случае.

помощью векторной целевой функции (ВЦФ) F ( x) = ( F1 ( x), F2 ( x), F3 ( x)), где максимальное время для «наихудшей» по продолжительности сеанса связи F3 ( x) = w3 (e) max – мультипликативная целевая функция, отражает достоверность всей передаваемой и получаемой командно-измерительным комплексом информации в данном варианте распределения сеансов связи.

паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) ~ [27]. В случае, если одинаковые по значению ВЦФ решения x, x X считаются эквивалентными (неразличимыми), то из ПМ X выделяется полное множество альтернатив (ПМА) X 0. ПМА X 0 представляет собой максимальную систему векторно несравнимых ПО из X, т.е. X 0 X.

Решение задачи заканчивается тем, что из ПМА выбирается наиболее целесообразное решение с помощью процедур теории выбора и принятия решений [50].

1.4.3. Математическая модель обучения сотрудников организации Одним из важных этапов процесса социализации является обучение сотрудников организации [20]. Существует три варианта проведения обучения: на рабочем месте, на базе организации и в учебных заведениях. В выборе места обучения каждая организация учитывает особенности конкретной ситуации, характер работы, а также ресурсы, которые выделяются на обучение.

Обучение на базе организации, как правило, проводят кадровые инструкторы в специальном помещении – учебном центре, и таким образом организация защищена от последствий слишком медленного или неправильного выполнения работы и, кроме этого, осуществляет полный контроль над качеством обучения. Требования к знаниям и умениям, которых должны достичь обучаемые в центре сотрудники, определяют программу обучения, в которой основным элементом является педагогическая методика, применяемая для научения в данной ситуации. Методы обучения для удобства разбиты на категории: методы пассивного, индивидуального активного и группового активного обучения [20]. Три основных метода обучения различаются в плане использования практики, обратной связи и подкрепления желаемого результата. Обучающий потенциал метода зависит не только от заложенных в нем возможностей, но и от того, как эти возможности используются. Эффективность любого метода можно повысить, если его будет применять высококвалифицированный инструктор. При выборе программы обучения следует учитывать и то, что ученики сильно отличаются друг от друга по своим способностям к учебе и в результате обучения достигают разных уровней того или иного умения. На эффективность конкретной программы обучения также влияют установки и ожидания обучающихся. Тесты способностей позволяют формировать группы по уровню обучаемости, чтобы, применив в программе обучения соответствующую этому уровню методику, достичь эффективности обучения.

Исходными данными для построения математической модели обучения сотрудников на базе организации являются: G = {g} – множество групп учебного центра, сформированных по целям и задачам обучения, а также по уровню обучаемости на основании проведенного тестирования; M = {m} – множество методов обучения [20]. Например, методы пассивного обучения, программированное обучение, компьютеризированное обучение, моделирование, дискуссионные методы, проигрывание ролей и следование образцу поведения, обучение с использованием видеоконференции; I = {i} – множество кадровых инструкторов учебного центра, причем каждый инструктор, в зависимости от опыта, владеет несколькими методиками и может обучать одновременно несколько групп.

Содержательная суть формулируемой задачи состоит в следующем. В каждую группу g G требуется назначить одного из инструкторов учебного центра i I, рекомендуя ему использовать в процессе обучения один из методов m M с учетом уровня обучаемости группы, знаний и умений, которых должны достичь обучающиеся сотрудники. Результатом такого назначения должно стать повышение эффективности обучения, оценку которой можно проводить на основе внутренних или внешних критериев.

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

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

Математическая модель рассматриваемой в настоящей работе задачи G = (V, E ) = (V1, V2, V3, E ), который строится следующим образом. Вершины первой доли, т.е. v V1, взаимно однозначно соответствуют элементам множества инструкторов учебного центра I. Каждой вершине v V1, соответствующей инструктору i I, приписано число n(v), определяемое числом групп, в которых данный инструктор будет работать. Вершинами второй доли v V2 являются элементы множества методов обучения M, а вершины третьей доли v V3 взаимно однозначно соответствуют элементам множества групп учебного центра. Для построения множества ребер E рассматриваем всевозможные тройки вершин (v1, v 2, v3 ) такие, что v1 V1, v 2 V2, v3 V3. Всякую тройку называем допустимой, если инструктор v может обучать группу v3, используя метод обучения v 2. Множество всех E = {e} определяется как множество всех допустимых троек ребер гиперграф G = (V1, V2, V3, E ) построен. В рассматриваемой задаче для данного гиперграфа G = (V, E ) определены следующие условия:

Допустимым является такое покрытие гиперграфа G звёздами, степени которых равны r (v), и каждая вершина v V3 инцидентна только одному ребру некоторой звезды.

Допустимым решением рассматриваемой задачи является всякий подгиперграф связности которого представляет собой звезду. Через обозначим множество всех допустимых решений (МДР) задачи покрытия гиперграфа G звездами.

Каждому ребру e E гиперграфа G = (V, E ) приписаны три веса w (e ), = 1,3, которые означают следующее: w1 (e ) = f 1 (v1, v 2, v3 ) – экономический эффект обучения, т.е. ожидаемый доход организации (в рублях) в случае, w2 (e ) = f 2 (v1, v 2, v3 ) – ожидаемый уровень обученности группы (в %);

w3 (e ) = f 2 (v1, v 2, v3 ) – социально-психологический эффект, т.е. ожидаемый уровень мотивации членов группы (в %) в этом же случае.

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

ВЦФ (1.12) – (1.13) определяет в МДР X паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) ~ [27]. В случае, если максимальную систему векторно несравнимых ПО из X, X 0 X.

Наиболее целесообразное решение выбирается из ПМА с помощью процедур теории выбора и принятия решений [50].

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

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

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

организации личностно-ориентированного обучения в школе являются:

параллели.

T = {t}– множество современных педагогических технологий обучения [87]. Например, технология модульного обучения, интегральная технология, технология обучения с применением глобальных информационных сетей, технология уровневой дифференциации и методики диагностического целеполагания.

K = {k } – множество классов данной параллели. Классы на основании результатов проведённых тестов отнесены к одному из уровней q Q сформированности учебно-организационных умений. Множество этих уровней Q = {q} определяется следующим образом: q = 0 – у учащихся отсутствует мотивация учебной деятельности; q = 1 – учащиеся работают на репродуктивном уровне; q = 2 – учащиеся работают на конструктивном уровне; q = 3 – учащиеся работают на творческом уровне.

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

Математическая модель рассматриваемой в настоящей работе задачи базируется на 3-дольном 3-однородном гиперграфе G = (V, E ) = (V1, V2, V3, E ), который строится следующим образом. Вершины первой доли, т.е. v V1, взаимно однозначно соответствуют элементам множества учителей U.

Каждой вершине v V1, соответствующей учителю u U, приписано число m(v ), определяемое нагрузкой учителя, а именно количеством классов рассматриваемой параллели, в которых данный учитель будет работать.

Каждая вершина второй доли v V2 однозначно соответствует некоторому элементу из множества технологий обучения T. Вершины третьей доли v V3 взаимно однозначно соответствуют элементам множества классов K.

Для построения множества рёбер E = {e} рассматриваем всевозможные тройки вершин (v1, v 2, v3 ) такие, что v1 V1, v 2 V2, v3 V3. Всякую такую тройку называем допустимой, если учитель v1 может вести занятия в классе v 3, используя технологию обучения v 2. Множество всех рёбер определяется как множество всех допустимых троек e = (v1, v2, v3 ), vi Vi, i = 1,3. Тем самым 3-дольный построен.

В рассматриваемой задаче для данного гиперграфа G = (V1,V2,V3, E ) выполняются следующие условия:

называемых концевыми для этого ребра;

вершины v V2 являются внутренними вершинами, и множество V2 состоит из непустых попарно непересекающихся множеств V2 (v3 ), v3 V3, причем каждый элемент v V2 (v3 ) однозначно соответствует некоторой технологии t T ;

(степени 1);

является параметром следующего условия: принадлежащая допустимому покрытию звезда с центром в вершине v имеет степень r (v) = m(v) и при этом выполняется равенство m(v ) = V3.

По своему определению допустимое покрытие 3-дольного гиперграфа x = (V x, E x ), V x V, E x E, в котором каждая компонента связности является звездой с центром в определенной вершине v V1, причем ее степень равна r (v).

G = (V, E ) = (V1,V2,V3, E ) допустимым решением рассматриваемой задачи является всякий такой его подгиперграф x = (V X, E X ), V X V, E X E, в котором каждая компонента связности представляет собой простую звезду степени r (v) с центром в вершине v V1. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи покрытия гиперграфа G звездами.

Каждому ребру e E гиперграфа G = (V, E ) приписаны три веса w (e ), = 1,3, которые означают следующее: w1 (e ) = f1 (v1, v 2, v3 ) – ожидаемое изменение коэффициента мотивации учебно-познавательной деятельности учащихся класса (в %) в случае, когда учитель, представленный вершиной v1, назначен в класс, представленный вершиной v3 с использованием технологии обучения, представленной вершиной v2 ; w2 (e ) = f 2 (v1, v 2, v3 ) – ожидаемое изменение (в том же случае) коэффициента обученности учащихся класса (в %); w3 (e ) = f 3 (v1, v 2, v3 ) – ожидаемое изменение показателя эффективности активной самостоятельной умственной деятельности учащихся (в %) в этом же случае.

Качество допустимых решений этой задачи x X оценивается с помощью векторной целевой функции (ВЦФ) где F1 ( x ) - критерий вида MAXMIN, F1 ( x ) = min w1 (e ) max, что означает учащихся класса параллели, находящихся на самом низком уровне сформированности учебно-организационных умений;

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

ВЦФ F ( x ) определяет в МДР X паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) ~ [4]. В случае, если одинаковые (неразличимыми), то из ПМ X выделяется полное множество альтернатив (ПМА) X 0. ПМА X 0 представляет собой максимальную систему векторно несравнимых ПО из X, X 0 X.

Наиболее целесообразное решение выбирается из ПМА с помощью процедур теории выбора и принятия решений [50].

В качестве примера рассмотрим следующую ситуацию. Параллель состоит из пяти классов, которые обозначим K = {k1, k 2, k 3, k 4, k 5 }. Результаты проведенных тестов в этих классах определили множество рекомендуемых для использования технологий T = {t1, t 2, t3, t 4 }. Администрацией школы запланировано, что в этой параллели классов будут работать два учителя U = {u1, u 2 }, причем u1 будет работать в двух классах, а u 2 – в трех, и при этом принято решение, что учитель u1 (u 2 ) должен обязательно работать в классе k1 (k 5 ).

Опишем процесс построения гиперграфа соответствие множеству U (K ). Доля V2 поставлена во взаимно однозначное соответствие множеству T, элементы которого рекомендованы методистом и школьным психологом для каждого класса и занесены в таб.1.1.

Построим множество ребер.

Веса ребер w 0, = 1,3 заданы следующей таб.1.2.

Представим все элементы МДР X = {x} рассматриваемой задачи.

Запишем в таб.1.3 значения критериев ВЦФ (1.14):

На рис.1.8 представлено одно из допустимых решений x 4.

Из таб.1.3 получаем, что ВЦФ определяет в МДР X ПМ X, которое в данном примере совпадает с ПМА X 0 : X = {x5, x8, x11, x12 } = X 0.

Найдем лексико-графический оптимум ЛГО этой задачи. Пусть критерии ВЦФ упорядочены и пронумерованы в порядке их относительной важности как в таб.1.3. Это означает, что для администрации школы в первую очередь необходимо повышение мотивации учебно-познавательной деятельности учащихся классов самого низкого уровня сформированности учебно-организационных умений, а затем повышение уровня обученности по предмету и повышение уровня активной самостоятельной деятельности учащихся всех классов параллели.

Найдем X (1) – подмножество всех элементов x X, оптимальных по первому критерию F1 ( x), X (1) = {x5, x 6 }.

критерию F2 ( x), X ( 2 ) = {x5 }.

Заметим, что x5 является ЛГО, а также ПО этой задачи. Это означает, что администрации школы можно рекомендовать назначить учителя u1 в класс k1 с использованием технологии t1 и в класс k 3 с использованием t 4, а учителя u 2 назначить в класс k 2 с использованием технологии обучения t1, в класс k 4 с использованием технологии t 2 и в класс k 5, рекомендуя при этом 1.5. Выводы по первой главе Основной теоретический результат первой главы представляют теоремы 1.1 и 1.2 о достаточных условиях выполнения свойства полноты соответственно для многокритериальных задач о совершенных сочетаниях и о покрытии звездами l -дольного l -однородного гиперграфа. Важность этого результата заключается в том, что он является базой для обоснования факта труднорешаемости рассматриваемых в диссертации задач на гиперграфах.

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

ГЛАВА 2. АЛГОРИТМЫ НАХОЖДЕНИЯ ВСЕХ

СОВЕРШЕННЫХ СОЧЕТАНИЙ И ПОКРЫТИЙ

ЗВЕЗДАМИ МНОГОДОЛЬНЫХ ОДНОРОДНЫХ

ГИПЕРГРАФОВ

Представленные в главе 1 математические модели базируются на 3G = (V1,V2,V3, E ), V1 + V2 + V3 = n.

дольных 3-однородных гиперграфах Важно отметить, что для таких гиперграфов мощность множества ребер E ограничена сверху полиномом 3-й степени от n. В общем случае, когда речь идет о l -дольном l -однородном гиперграфе G = (V1,V2,...,Vl, E ) справедлива следующая Теорема 2.1. В любом n -вершинном l -дольном l -однородном гиперграфе число ребер ограничено сверху полиномом, причем, эта верхняя оценка является достижимой, если n кратно l, т.е. в случае, когда доли гиперграфа G равномощны.

Доказательство. Рассмотрим n -вершинный l -дольный l -однородный гиперграф G = (V1,V2,...,Vl, E ), для которого через ns обозначим мощность s й доли Vs = ns, Обозначим через E (v) множество всех ребер e E, инцидентных вершине v V1. Для мощности этого множества m(v) из определения l -дольного l однородного гиперграфа вытекает следующая верхняя оценка которая является достижимой.

В силу условия l -однородности l -дольного гиперграфа для мощности множества его ребер с учетом (2.2) справедлива следующая верхняя оценка которая также является достижимой. Правую часть выражения (2.3) можно интерпретировать, как объем l -мерного параллелепипеда в l -мерном евклидовом пространстве при условии, что сумма длин его сторон вида (2.1) равна одной и той же величине. Иными словами, вычисление верхней оценки мощности E свелось к известной изопериметрической задаче. Согласно этой задаче максимальное значение правой части оценки (2.3) достигается при выполнении равенств ns =, s = 1, l. Таким образом, получаем верхнюю оценку E, которая оказывается достижимой в случае, когда n кратно l, т.е. доли являются равномощными.

Теорема 2.1 доказана.

Примечание 2.1. Рассмотрим отмеченный в теореме 2.1 случай, когда в данном n -вершинном l -дольном гиперграфе G = (V1,V2,...,Vl, E ) его доли являются равномощными, т.е. их мощности Vs = m, s = 1, l, n = ml. Задачу Z 1 о сочетаниях в этом случае по аналогии с задачами на графах называем термином «задача о совершенных сочетаниях на l -дольном l -однородном гиперграфе». Последний термин условимся обозначать символом Z1l. В G = (V1,V2,...,Vl, E ) всегда будем подразумевать выполнение равенства n = ml.

Из теоремы 2.1 следует, что для задач, формулируемых на l -дольных l однородных гиперграфах, объем исходных данных является полиномиально ограниченным в случае, когда l представляет собой независящую от n константу. Важно отметить, что предлагаемые в главе 1 математические модели базируются именно на гиперграфах такого вида.

2.2. Обоснование труднорешаемости нахождения ПМА векторной Принято говорить, что задача Z s, s = 1,2 с ВЦФ (1.1) – (1.3) обладает свойством полноты [27], если для всякого МДР X = X (G ) = {x} этой задачи существуют такие параметры ее ВЦФ, при которых выполняются равенства К настоящему времени свойство полноты установлено для ряда многокритериальных дискретных задач, сформулированных на графах, в том числе и для задач о сочетаниях и гамильтоновых контурах [27]. Однако для многокритериальных задач на гиперграфах вопрос о свойстве полноты до сих сформулированных выше задач на гиперграфах.

Пусть R N – евклидово пространство размерности N. Из определения ПМ и ПМА [27, 79] вытекает, что справедлива следующая Лемма 2.1. Для всякой задачи с ВЦФ вида F : X R N выполняется равенство мощностей X 0 = F ( X ).

Для какой-либо задачи Z s, s = 1,2 с ВЦФ (1.1) – (1.4) рассмотрим конкретную индивидуальную задачу с МДР X, ПМ X и ПМА X 0. Добавим к ВЦФ (1.1) – (1.3) новые критерии. Тогда получим другую индивидуальную задачу, у которой новая (расширенная) ВЦФ определяет на прежнем МДР X другие множества альтернатив (МА), например, ПМ или ПМА. Возникает вопрос о том, как соотносятся «старые» и «новые» МА. С учетом того, что добавление «новых» критериев не изменяет значение «старых» критериев (1.1) – (1.3) на всех допустимых решениях x X, справедлива следующая Лемма 2.2. При любом N 2 для всякой индивидуальной задачи с ВЦФ (1.1) – (1.3) добавление новых критериев к этой ВЦФ либо оставит ПМ X и ПМА X 0 неизменными, либо пополнит их новыми решениями.

Через J (n) = {G} условимся обозначать множество всех n -вершинных гиперграфов (графов). Пусть X = X (G ) = {x} – множество всех допустимых решений x = (Vx, E x ) рассматриваемой задачи на гиперграфе G = (V, E ), Vx V, E x E. Сформулированную на n -вершинных гиперграфах или графах G = (V, E ) задачу будем называть однородной, если для всякого гиперграфа G J (n) каждое допустимое решение x X (G ) содержит одинаковое количество ребер E x.

С учетом п.1.3 будем считать, что однородные задачи на гиперграфах занумерованы индексом s = 1,2,... и обозначаются Z s.

Лемма 2.3. Всякая однородная векторная задача на гиперграфах является полной, если ее ВЦФ (1.1) содержит не менее двух весовых критериев вида MAXSUM (1.2).

Доказательство. Рассмотрим какую-либо задачу Zs и ее МДР X = X (G ) на произвольном n -вершинном гиперграфе G = (V, E ). Для тривиальных случаев ( X = и X = 1) утверждение леммы 2.3 очевидно.

Пусть X = X (G ) имеет мощность X 2 и на X определена ВЦФ (1.1) – (1.3). Покажем возможность задания весов ребер w(e) гиперграфа G так, что для определяемых этой ВЦФ ПМ X и ПМА X 0 будут выполняться равенства (2.4). Для этого в гиперграфе G ребра e E перенумеруем числами t = t (e) = 1,2,..., E и веса этих ребер определим следующим образом:

В настоящем доказательстве существенным образом используется равенство которое в силу условия однородности рассматриваемой задачи выполняется для каждого МДР X = X (G ), определяемого для всякого n -вершинного гиперграфа G. Из (2.5) и (2.6) получаем Обозначим разность R1, 2 = E1 \ E2 для пары допустимых решений x1, x2 X. Тогда для всякой пары x1, x2 X имеем Пусть среди элементов множества R1, 2 R2,1 ребро e с наименьшим номером t = t (e) принадлежит R1, 2. Тогда при выполнении неравенства N1 2 в ВЦФ (1.1) – (1.3) из соотношений (2.5) – (2.8) вытекают неравенства F1 ( x1 ) > F1 ( x2 ), F2 ( x1 ) > F2 ( x2 ), которые означают, что любая пара x1, x2 X является векторно-несравнимой по ВЦФ (1.1) – (1.3). Последнее с учетом леммы 2.1 означает выполнение равенства (2.4). Для N = 2 лемма 2. доказана.

В силу леммы 2.2 равенства (2.4) выполняются и при N 3, если для = 1,2 критерии вида MAXSUM (1.2) определим согласно (2.5), а для = 3,4,..., N критерии (1.2) – (1.3) определим произвольным образом.

Лемма 2.3 доказана.

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

При обосновании оценок максимальной мощности МДР для задач на графах учитывалось свойство «монотонность по ребрам» для этих задач [43].