Книги, научные публикации Pages:     | 1 | 2 |

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ КАРАЧАЕВО-ЧЕРКЕССКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ на правах рукописи Омельченко Галина Георгиевна ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ ...

-- [ Страница 2 ] --

e 2 e5 e e e e3 e e Рис.2.5. Подграф S Таблица 2. Tk T k =1 k = 2 e1 {e1} k = k= k = {e, e3 } {e } 2 {e5, e6 } {e7, e8 } T e {e1} e3 {e1} {e } {e3 } {e } {e } {e6 } {e5 } {e8 } {e7 } T3 T e {e1} e5 {e1} e6 {e1} {e, e3 } {e } 2 4 {e3 } {e } 2 {e3 } {e } 2 {e } 4 {e } 4 {e } 4 {e } {e5, e6 } {e7, e8 } {e5 } {e6 } {e6 } {e5 } {e8 } {e7 } {e7 } {e8 } T e7 {e1} e8 {e1} Приведем описание работы этапа q алгоритма 1. Этап q состоит из q подэтапов, перенумерованных индексом t = 1,2,..., N q N m 1. На вход q подэтапа t = 1 подаются подграф S q = (U q, R q ) = (U 1q,U 2q,...,U kq,...,U m, R q ) и соответствующая ему таблица МС T q = Tikq, i = 1,2,..., N q, k = 1,2,..., m.

q Вершины множества U q = {e1q, e2q,..., eiq,..., e N } перенумерованы индексом i q так, что существует взаимно однозначное соответствие между номерами вершин из U q и номерами строк таблицы МС T q. При этом для каждого k существует также взаимно однозначное соответствие между номерами вершин в доле U kq и номерами строк части Tkq в таблице T q. На подэтапе t = 1 в таблице T q выделяется строка i = 2, которая по определению принадлежит части T2q таблицы T q. Для выделенной строки осуществляется проверка выполнения необходимого условия 2 по отношению к каждой из последующих частей Tkq, k = 3,4,..., m. Если это условие для строки i = 2 не выполняется по отношению к некоторой из частей Tkq, то работа подэтапа t = 1 завершается вычеркиванием из таблицы q T q этой строки, а также удалением всех вхождений вершины e2q в клетки Ti 2, i 2. Наряду с этим в подграфе S q указанная вершина e2q также удаляется вместе с инцидентными ей ребрами. Оставшиеся части таблицы T q и подграфа S q обозначаем соответственно через T1q = Tikq,1, 1 i N q, i 2, q k = 1, m и S1q = (U 1q,1,...,U kq,1,...,U m,1, R1q ), причем, номера строк в таблице T1q остаются без изменения. Если же подэтап t = 1 устанавливает выполнение необходимого условия 2, то таблица T q и подграф S q остаются без изменения, но при этом получают соответственно новые обозначения T1q и S1q.

Пусть осуществлено t подэтапов, по завершению которых получены таблица Tt q = Tikq,t, 1 i N q, i t, k = 1, m, состоящая из частей Tkq,t, k = 1, m, q и подграф S tq = (U 1q,t,...,U kq,t,...,U m,t, Rtq ) ;

в таблице Tt q сохранена нумерация строк таблицы T q. Для таблицы Tt q осуществляется проверка, является ли непустой каждая из ее m частей. Если окажется, что в некоторой части Tkq,t по завершению подэтапа t все ее строки являются вычеркнутыми, то на этом подэтапе заканчивается вся работа этапа q, т.е. его работа оказывается безрезультатной, и далее следует переход к этапу q + 1. Если работа подэтапа t 1 оказалась результативной, тогда следует переход к подэтапу t + 1, работа которого начинается с выделения в таблице Tt q строки i = t + 2, которой соответствует вершина etq+ 2 в подграфе S tq. Пусть эта строка принадлежит некоторой части Tkq,t, k m 1. Тогда для выделенной строки i осуществляется проверка выполнения необходимого условия 2 по отношению к каждой из остальных частей Trq,t, r k таблицы Tt q. Если это условие для строки i = t + 2 не выполняется по отношению к некоторой из этих частей, то работа подэтапа t + завершается вычеркиванием из таблицы Tt q этой строки, а также удалением всех вхождений вершины etq+ 2 в клетки Trq,t, r k, 1 r m. Наряду с этим в подграфе S tq указанная вершина etq+ 2 также удаляется вместе с инцидентными ей ребрами. Оставшиеся после этого вычеркивания части таблицы Tt q и q подграфа S tq обозначаем соответственно через Tt +1 = Tikq,t +1, 1 i N q, k = 1, m и q S tq+1 = (U 1q,t +1,...,U kq,t +1,...,U m,t +1, Rtq+1 ).

При этом таблица q Tt + наследует нумерацию строк таблицы Tt q. Работа алгоритма 1 считается результативной, если по завершению q подэтапа t = N q N m 1 получены такой подграф S tq, в котором каждая из m долей U kq,t не является пустой, и такая таблица МС Tt q, в которой каждая ее часть Tkq,t, k = 1, m содержит хотя бы одну не вычеркнутую строку. При этом каждая клетка Tikq,t этой таблицы не является пустым множеством.

Удовлетворяющие этим условиям подграф S q = S tq и таблицу МС T q = Tt q будем называть терминами тупиковый подграф и тупиковая таблица МС. На рис.2.6 представлен тупиковый подграф S 1 = (U 11,U 21,U 31,U 41, R 1 ) специального графа S (G ) на рис 2.3. Соответствующая ему тупиковая таблица МС T q представлена таблицей 2.3.

e3 e1 e e Рис.2.6. Тупиковый подграф S 1 : S 1 = (U 11,U 21,U 31,U 41, R 1 ) Таблица 2. k =1 k = 2 e11 = e k = k = {e1} {e2 } {e2 } {e3 } {e3 } {e4 } {e4 } e1 = e2 {e1} 1 e3 = e3 1 e6 = e {e1} {e1} {e2 } {e2 } {e3 } {e3 } {e4 } {e4 } Примечание 2.3. Не трудно видеть, что трудоемкость алгоритма 1 ограничена сверху полиномом от размерности подграфа S q. Поэтому представляют интерес такие свойства тупиковой таблицы T q и тупикового подграфа Sq, которые определяют собой достаточное условие существования в подграфе S q m -вершинной клики. Справедлива Теорема 2.6. Если тупиковая таблица T q является квадратной, то тупиковый подграф S q представляет собой m -вершинную клику в подграфе Sq.

Доказательство. По определению таблица T q имеет m столбцов. Следовательно, если, согласно условию теоремы она является квадратной, то она состоит из m строк. При этом, по определению, таблица T q состоит из m частей Tk q, k = 1, m, откуда каждая часть Tk q состоит из единственной строки. Это означает, что в тупиковом подграфе S q каждая доля U kq состоит из единственной вершины. Последнее означает, что для каждого столбца k = 1,2,..., m каждая его клетка Tikq, 1 i N q содержит один и тот же элемент, а именно единственную вершину, составляющую долю U kq. Эта вершина в силу непустоты клеток в каждой из строк таблицы МС смежна со всеми остальными вершинами, образующими соответствующие доли тупикового подграфа S q. Отсюда, удовлетворяющий этому условию подграф является полным m -вершинным графом, т.е. множество его вершин образует клику размерности m. Теорема 2.6 доказана. Из описания работы алгоритма 1 и необходимых условий 1 и 2 вытекает Следствие 2.3. Всякая вершина, принадлежащая некоторой m вершинной клике не будет удалена из множеств смежности U q в процессе работы алгоритма 1, в силу чего соответствующая этой вершине строка в таблице МС сохранится до окончания работы алгоритма 1, и т.о. тупиковая таблица МС не будет являться пустой, т.е. T q. С учетом этого является справедливой Лемма 2.8. Если гиперграф G содержит совершенное сочетание, то на выходе алгоритма 1 получаем непустой тупиковый подграф S. Доказательство. Если на подэтапе (t + 1) алгоритма 1 строка i = t + 2 вошла в состав тупиковой таблицы МС T, то это означает, что в каждой из остальных частей Tk для нее существует хотя бы одна строка j, дающая непустое пересечение МС со строкой i, т.е. Tikq T jkq, k = 1,2,..., m. Тогда из этих строк, включая строку i, составим квадратную m m таблицу T i, которая согласно теореме 2.6 определяет собой m -вершинную клику. Лемма 2.8 доказана. На основании предыдущих лемм 2.6 - 2.8 можно сформулировать Примечание 2.4. Вхождение вершины в тупиковый подграф S q является необходимым условием ее принадлежности хотя бы одной клике размерности m. Также является справедливой Лемма 2.9. Если для гиперграфа G на выходе алгоритма 1 получаем тупиковый подграф S =, то G не содержит совершенного сочетания. Доказательство. На подэтапе (t + 1) алгоритма 1 вершина удаляется из специального подграфа S tq по той причине, что она не смежна ни с какой вершиной хотя бы одной доли в S tq, а, как известно, m -вершинная клика должна содержать взаимно смежные вершины-представительницы из каждой доли специального графа S q. Поэтому, если по завершению всех подэтапов алгоритма 1 из подграфа S q удалены все вершины, а из таблицы МС T q удалены все соответствующие этим вершинам строки, и тупиковая таблица T q оказалась пустой, то из этого следует, что в специальном подграфе S q нет взаимно смежных вершин-представительниц из каждой доли, а специальный подграф S q не содержит m -вершинной клики. Лемма 2.9 доказана. Оценим вычислительную сложность ( 1 ) алгоритма 1.

Трудоемкость алгоритма 1 определяется трудоемкостью его работы с таблицами T q, q = 1,2,..., L1, L1 = U 1 - количество вершин первой доли специального графа S. Заметим, что в процессе построения специального графа S для каждой вершины e формируются ее множества смежности и трудоемкость этого процесса для одной вершины e не превосходит числа U вершин в специальном графе S. В процессе построения таблицы T q каждое ребро подграфа S q просматривается по два раза, причем число элементов в какой-либо строке таблицы T q не превосходит U q. Отсюда вычислительная сложность процесса формирования таблицы T q ограничена сверху величиной O( U q ). В процессе построения тупикового подграфа S q для каждой строки таблицы осуществляется не более U q операций поэлементарного сравнения и вычеркивания в таблице T q некоторых строк. Причем, при вычеркивании конечное отдельных число строк и вычеркивании образом, для соответствующих вершин каждая вершина множеств смежности в таблице Tq просматривается раз.

Таким вычислительной сложности получения тупикового подграфа и тупиковой таблицы справедлива верхняя оценка ( 1q ) O( U q ), а верхняя оценка трудоемкости алгоритма 1 с учетом U = E составляет ( 1 ) O E.

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

Работа алгоритма 2 состоит из q этапов, q = 1, L1. На вход этапа q представляется m -дольный тупиковый подграф S q = (U 1q,U 2q,...,U mq, R q ). Работа этапа q состоит из (m 2) подэтапов. На первом подэтапе в долях U mq, U mq1, U mq 2 формируется множество K 3q ={ 3 } всех клик размерности следующим образом. Для каждого ребра = (e, e), e U mq, e U mq1 в доле U mq 2 отыскиваются вершины e, которые смежны с e и e. Всякая такая тройка вершин e, e, e образует некоторую клику 3 размерности 3, т.е. тупиковый подграф S q содержит такую клику 3 в том случае, когда множество R q содержит тройку ребер = (e, e), = (e, e), = (e, e).

e2 e4 e e1 e e6 e e Рис.2.7. 5-дольный тупиковый подграф S k =1 e1 e2 e3 e4 e5 e6 e7 e {e1 } {e1 } {e1 } {e1 } {e1 } {e1 } {e1 } {e1 } {e1 } Таблица 2. k = {e8, e 9 } {e8, e 9 } {e8, e 9 } {e8, e 9 } {e8, e 9 } {e8 } {e9 } {e8 } {e9 } k = {e 2, e3 } {e 2 } {e3 } {e 2 } {e3 } {e 2, e3 } {e 2, e3 } {e 2, e3 } {e 2, e3 } k = {e 4, e5 } {e 4 } {e5 } {e 4 } {e5 } {e 4, e5 } {e 4, e5 } {e 4, e5 } {e 4, e5 } k = {e 6, e 7 } {e 6, e 7 } {e 6, e 7 } {e 6, e 7 } {e 6, e 7 } {e 6 } {e 7 } {e 6 } {e 7 } e На рис.2.7 представлен 5-дольный тупиковый подграф S 1. Для него соответствующая тупиковая таблица T 1 представлена таблицей 2.4. В долях U 51, U 41, U 31 формируется множество клик размерности 3:

1 K 3 = { 3j }, j = 1,4, где 3 1 = {e8, e6, e4 }, 3 = {e8, e6, e5 }, 3 = {e9, e7, e4 }, 3 = {e9, e7, e5 }. 4 Пусть осуществлено s подэтапов, 1 s m 3, в результате чего сформировано множество K sq+ 2 = { s + 2 } клик размерности s + 2. Если это множество является пустым ( K sq+ 2 = ), то подэтап s, а вместе с ним и этап q в целом заканчивает свою работу безрезультатно. В противном случае следует переход к подэтапу s + 1 следующим образом. Из множества K sq+ 2 последовательно выбираются клики s + 2 = {e1q,..., erq,..., esq+ 2 }, в каждой их которых имеется по одному представителю от каждой из последних ( s + 2) долей, т.е. erq U mq r +1, r = 1, s + 2. Затем в доле U mq s 2 выделяются такие вершины e*, каждая из которых смежна с каждой вершиной этой клики, т.е. в R q находим ( s + 2) ребер вида r = (e *, erq ), erq s + 2, r = 1, s + 2. Тогда пополняя рассматриваемую клику s + 2 вершиной e*, получаем клику s +3 = {e *, e1q, e2q,..., esq+ 2 } размерности ( s + 3), их совокупность обозначим через K sq+3 = { s +3 }, что и представляет собой результат работы подэтапа s + 1.

3 Например, для подграфа на рис. 2.7 на подэтапе s = 2 клики 1 и 3 пополняются вершиной e * = e2, а клики 3 и 3 пополняются вершиной e3, в 2 4 результате чего получим множество клик K 4q = { 4j }, j = 1,4, где 4 14 = {e8, e6, e4, e2 }, 4 = {e9, e7, e4, e2 }, 3 = {e8, e6, e5, e3 }, 4 = {e9, e7, e5, e3 }. На 2 заключительном этапе s = 3 каждая из этих клик пополняется одной и той же вершиной e q = e1, образуя множество клик размерности m = 5. Последнее определяет гиперграфе. собой множество совершенных сочетаний в исходном Если каждый из ( m 2) подэтапов алгоритма является q результативным, то по завершению этапа q в целом получаем множество K m клик размерности m, каждая из которых однозначно определяет собой некоторое допустимое решение исходной задачи о нахождении множества X = X (G ) всех совершенных сочетаний на l -дольном l -однородном гиперграфе. По завершению последнего, т.е. L1 -го этапа формируется теоретикомножественное объединение UK q = L q m, которое определяет собой МДР X = X (G ) задачи.

Оценивая вычислительную сложность алгоритма 2, заметим, что все клики s + 2 K sq+ 2, s = 1,2,..., m формируются последовательно и бесповторно, при этом ребро R просматривается не более, чем количество этих клик. Последнее ограничено числом всех совершенных l сочетаний в полном l -дольном l -однородном n -вершинном гиперграфе, которое согласно теореме 2.2 равно (m!) l 1, где m = n. Отсюда получаем l n l (2.14) ( 2 ) O( R (m!) l 1 ), m =.

2.6. Алгоритм нахождения множества допустимых решений задачи покрытия l -дольного l -однородного гиперграфа звездами Используем обозначения, введенные в п.2.3 для задачи Z 2l (r ), где r = (r1, r2,..., rn ) является вектором степеней простых звезд в допустимом покрытии x = (V1,V2,...,Vl, E x ) X данного l -дольного l -однородного гиперграфа G = (V1,...,Vl, E ) J (n, l, n1 ). Здесь параметр n1 = V1 представляет собой количество звезд в покрытии или, что то же самое, количество вершин первой доли, которые по определению представляют в допустимых решениях x X центры простых звезд.

На рис. 2.9 для вектора степеней r = (r1, r2 ) = (2,4) представлено допустимое покрытие звездами 20-вершинного 4-дольного 4-однородного гиперграфа G = (V1,V2,V3,V4, E ), изображенного на рис. 2. 3 9 10 4 1 16 17 11 6 2 13 19 Рис.2.8. 20-вершинный 4-дольный 4-однородный гиперграф G = (V1,V2,V3,V4 E ), E = {e1, e2,..., e8 }, где e1 = (1,3,9,15) e2 = (1,6,13,20) e3 = (1,5,11,17) e4 = (2,4,11,18) e5 = (2,5,10,16) e6 = (2,7,12,17) e7 = (2,8,14,19) e8 = (2,7,14,20) 3 4 1 5 9 10 11 16 17 6 2 12 19 Рис.2.9. Допустимое покрытие звездами x = (V1,V2,V3,V4, E x ), E x = {e1, e2, e4, e5, e6, e7 } гиперграфа, представленного на рис.2. Представленный ниже алгоритм 3 целенаправленного перебора 1 допустимых покрытий x X состоит из четырех этапов 3, 32, 33 и 34. 1 Суть этапа 3 заключается в полиномиальном сведении задачи покрытия звездами Z 2l (r ) к задаче покрытия совершенными сочетаниями Z 1l. Этап 32 представляет собой описанный выше алгоритм распознавания совершенных сочетаний в гиперграфе, на этапе 33 с помощью описанного выше алгоритма 2 выделяются все совершенные сочетания в l -дольном l однородном гиперграфе, т.е. результатом третьего этапа является МДР задачи Z1l. Этап 34 на базе МДР задачи Z 1l находит множество всех допустимых решений x = (V1,V2,...,Vl, E x ) X (G ) задачи Z 2l (r ) покрытия звездами данного l -дольного гиперграфа G = (V1,V2,...,Vl, E ).

1 Сведение задачи Z 2l (r ) к задаче Z 1l начинается с реализации этапа следующим образом. Пусть дан n -вершинный l -дольный l -однородный гиперграф G = (V1,V2,...,Vl, E ), в котором мощности долей удовлетворяют равенствам V1 = n1, Vs = m = n n1, l s = 2, l. Формулируемая на этом гиперграфе задача Z 2l (r ) имеет непустое МДР X = X (G ) тогда, когда для заданного вектора степеней условие r = (r1, r2,..., rn ) выполняется необходимое r t = n t = m. Считаем, что каждая вершина первой доли vt V1 окрашена в свой цвет t, t = 1,2,..., n1. Процесс сведения задачи Z 2l (r ) к задаче Z 1l начинается с того, что в первой доле V1 каждая вершина vt заменяется на множество вершин V1t = {vtk }, k = 1, rt, окрашенных в один и тот же цвет t, t = 1, n1. В результате в данном гиперграфе G преобразуется в множество V1 = UV1t = {vtk }, t =1 n его первая доля V k = 1, rt, t = 1, n1, причем мощность V1 = rt = m.

t = n В процессе замены доли V1 на долю V1 осуществляется следующее преобразование множества ребер E данного гиперграфа G = (V1,...,Vl, E ). Для каждой фиксированной вершины vt V1 из E выделяется множество Et, состоящее из ребер e E, инцидентных вершине vt. Далее множество Et порождает собой rt равномощных подмножеств Etk, Etk = Et, k = 1, rt следующим образом. Для каждого фиксированного индекса k в множестве Et в каждом его ребре вершина vt заменяется на вершину vtk. Полученное в результате таких замен множество обозначаем Etk, k = 1, rt. Объединяя по индексу k, получаем множества Et = U E, t = 1, n1 ;

обозначим E = U Et.

k =1 k t t =1 rt n Полученное множество E по своему определению образует n -вершинный l -дольный l -однородный гиперграф G = (V1,V2,...,Vl, E ) с равномощными 1 долями, где n = n + (rt 1) = n + (m n1 ) = ml. На этом работа этапа t =1 n заканчивается. Результатом применения этапов 32 и 33 к гиперграфу G является множество гиперграфе G. В процессе этапа 34 используется новая операция vv совмещения пары вершин v и v в рассматриваемых ребрах. Для определения этой операции в общем случае рассмотрим пару ребер X = X (G ) = {x} всех совершенных сочетаний в e = (v1, v,..., v ), 2 r e = (v1, v2,..., vk), которые могут пересекаться или не пересекаться по их вершинам. Предполагая несовпадение v1 v1, в качестве результата совмещения этих вершин вводим в рассмотрение новую вершину v1, которая не является элементом множества (e e). Тогда результатом операции e v1v1 e является пара пересекающихся ребер {(v1, v2,..., v ), (v1, v,..., v)}. r 2 k При этом отметим, что в случае непересекающихся ребер e, e результатом применения к ним операции совмещения пары вершин является простая звезда степени 2 с центром в новой вершине v1. Данное выше определение операции совмещения пары вершин, инцидентных паре различных ребер, очевидным образом обобщается на произвольное число r 3 ребер. При этом, если рассматриваемые ребра попарно не пересекаются, то в результате применения к ним операции совмещения вершин получаем простую звезду степени r с центром в новой вершине. На рис. 2.10 показана операция совмещения трех вершин v1, v1, v1, инцидентных тройке различных ребер e, e, e, и образование простой звезды степени 3 с центром в новой вершине v1.

v e e e v 2 v 2 v v3 v3 v v v v1 v v v v 3 v v Рис.2.10. Образование простой звезды с центром в вершине v1 в результате операции совмещения трех вершин v1, v1, v1 Пусть в гиперграфе G выделено совершенное сочетание x = (V1,V2,...,Vl, E x ), в котором доля V1 согласно построению гиперграфа G разбивается на подмножества V1t = {vtk }, k = 1, rt такие, что все вершины v V1t окрашены в один и тот же цвет t, t = 1, n1. Эти подмножества V1t однозначно определяют собой разбиение множества ребер Ex на подмножества E xt = {etk }, k = 1, rt, t = 1, n1. В подмножестве E xt нумерация индексом k ребер etk производится в соответствии с нумерацией этим же индексом вершин vtk V1t. В свою очередь каждое ребро e E xt однозначно соответствует некоторому ребру e Et, Et E в том смысле, что имеет место совпадение в ребрах e и e всех вершин, принадлежащих долям V2,V3,...,Vl, т.е., рассматривая ребра e и e в качестве множеств вершин, получаем следующее теоретико-множественное совпадение e (V \ V1 ) = e (V \ V1 ), e E xt, e Et, Et E.

Фиксируем номер цвета (2.15) t {1,2,..., n1} и применяем операцию совмещения вершин первой доли vtk V1t, k = 1, rt в ребрах etk E xt. В результате, согласно (2.15), получаем простую звезду степени rt с центром в новой вершине vt V1.

Отсюда с учетом определения гиперграфа G = (V1,V2,...,Vl, E ) получаем, что является справедливой следующая Лемма 2.10. Всякое совершенное сочетание x в гиперграфе G однозначно определяет собой допустимое покрытие x гиперграфа G звездами, причем, это покрытие получается в результате применения операции совмещения одноцветных вершин первой доли в ребрах из x. Результатом применения этапов 32 и 33 к гиперграфу G является множество всех его совершенных сочетаний X (G ) = {x}. Перенумеруем индексом i = 1,2,..., X (G ) элементы x X (G ). В каждом совершенном сочетании x X (G ) осуществляется операция совмещения одноцветных вершин в ребрах xi. После выполнения этой операции получаем последовательность допустимых покрытий xi, i = 1,2,..., X (G ) гиперграфа G звездами, среди которых встречаются одинаковые покрытия. Результатом этапа является теоретико-множественное объединение элементов указанной последовательности, обозначаемое через X (G, 34 ). Из леммы 2.10 вытекает, что имеет место включение X (G, 34 ) X (G ).

(2.16) Используя лемму 2.10, или рассуждая от противного, приходим к обратному включению X (G ) X (G, 34 ), откуда с учетом (2.16) и леммы 2.10 получаем равенство X (G ) = X (G, 34 ).

Рассмотрим иллюстративный пример процесса покрытия многодольного однородного гиперграфа звездами. На рис. 2.11 представлен исходный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ), в котором первая доля содержит две вершины V1 = 2, V1 = {1,2}, а вторая и третья доли равномощны V2 = V3 = 4.

Задано множество ребер гиперграфа E = {e1, e2, e3, e4, e5 }, где e1 = (1,3,7), e2 = (1,4,8), e3 = (2,5,9), e4 = (2,6,10), e5 = (1,5,9).

e e e e e Рис.2.11. Исходный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) Пусть необходимо найти множество допустимых покрытий этого гиперграфа звездами с вектором степеней r = (r1, r2 ) = (2,2), тогда результатом 1 реализации этапа 3 алгоритма 3 будет представленный на рис. 2. гиперграф G = (V1,V2,V3, E ), в котором первая доля V1 представляет собой 1 преобразованное в ходе этапа 3 множество V1 исходного гиперграфа V1 = {11,12,21,2 2 }, а также осуществлено преобразование множества ребер E 1 1 исходного гиперграфа во множество E = {e11, e1, e5, e12, e22, e52, e3, e1, e32, e42 }, где 2 4 1 e11 = (11,3,7), e1 = (11,4,8), e5 = (11,5,9), e12 = (12,3,7), e22 = (12,4,8), e52 = (12,5,9), 2 1 e3 = (21,5,9), e1 = (21,6,10), e32 = (2 2,5,9), e42 = (2 2,6,10). 11 3 Рис.2.12. Гиперграф G = (V1,V2,V3, E ), полученный из гиперграфа 1 G = (V1,V2,V3, E ) на рис. 2.11 в результате работы этапа 3 Далее в результате применения этапов 32 и 33 к гиперграфу G получено представленное на рис. 2.13 (а, б, в, г) множество всех его совершенных сочетаний X (G ) = {x} = {x1, x2, x3, x4 }, которые соответствуют покрытию исходного гиперграфа G звездами.

1 e 2 e e1 2 e 1 Рис.2.13(а). Совершенное сочетание x1 = (V1,V2,V3, E x ), E x = {e11, e22, e3, e42 }, соответствующее покрытию гиперграфа G звездами 1 11 2 e e1 e1 2 e 1 Рис.2.13(б). Совершенное сочетание x2 = (V1,V2,V3, E x ), E x = {e12, e1, e3, e42 }, 2 соответствующее покрытию гиперграфа G звездами 2 1 e 2 e 2 e e1 Рис.2.13(в). Совершенное сочетание x3 = (V1,V2,V3, E x ), E x = {e11, e22, e32, e1 }, 4 соответствующее покрытию гиперграфа G звездами 3 2 e e1 2 e e1 Рис.2.13(г). Совершенное сочетание x4 = (V1,V2,V3, E x ), E x = {e12, e1, e32, e1 }, 2 4 соответствующее покрытию гиперграфа G звездами 4 После применения операции совмещения вершин и 21 2 на этапе 34 получаем искомое покрытие гиперграфа G звездами с вектором степеней r = (r1, r2 ) = (2,2), представленное на рис. 2.14, которое и является результатом работы алгоритма 3.

e e e e Рис.2.14. Покрытие гиперграфа G звездами x = (V1,V2,V3, E x ), E x = {e1, e2, e3, e4 } с вектором степеней r = (r1, r2 ) = (2,2) Оценивая вычислительную сложность алгоритма 3, условимся 1 1 обозначать через 3, 2, 3 совместное выполнение этапов 3, 32 и 33. Пусть 1, 2 (G ) обозначает собой алгоритм нахождения множества X (G ) всех совершенных сочетаний в гиперграфе G. Нетрудно видеть справедливость следующей оценки вычислительной сложности ( 31, 2,3 ) O( ( 1, 2 (G ) ).

На этапе (2.17) рассматриваются и сравниваются между собой совершенные сочетания и соответствующие им множества звезд, каждое из которых состоит из m = n l l -элементных подмножеств вершин. Тогда вычислительная сложность перехода от множества совершенных сочетаний X (G ) к множеству X (G, 3 ) всех покрытий гиперграфа G звездами ограничена сверху величиной O (ml X (G ) ) 2. Отсюда с учетом (2.17) получаем верхнюю оценку трудоемкости алгоритма 3 :

( ) ( 3 ) O( ( 1, 2 (G )) ) + O((ml X (G ) ) 2 ), где верхняя оценка для ( 1, 2 (G ) ) представляется формулой (2.14).

2.7. Выводы по второй главе Выносимые на защиту результаты второй главы по своему математическому содержанию делятся на две группы. Первая группа характеризует, во-первых, структурную сложность гиперграфов (т.е. максимально возможное число его элементов) и, во-вторых, вычислительную сложность многокритериальных постановок задач на гиперграфах. Теорема 2.1 отражает принципиальное различие между структурной сложностью графов и структурной сложностью гиперграфов: если в графах эта сложность ограничена полиномом второй степени от числа вершин, то достижимая верхняя оценка структурной сложности гиперграфов растет экспоненциально с ростом числа его вершин. от Теоремы числа 2.2 - 2.5 устанавливают множества экспоненциально растущую вершин мощность допустимых решений рассматриваемых в диссертации задач о совершенных сочетаниях и о покрытии звездами, а также обосновывают достаточные условия, при выполнении которых эти задачи являются труднорешаемыми. Вторую группу результатов второй главы представляют три алгоритма. Первый из них предназначен для решения NP -полной задачи распознавания совершенного сочетания в многодольном гиперграфе. Этот алгоритм представляет научный интерес прежде всего тем, что его вычислительная сложность является полиномиально ограниченной, а для рассматриваемой задачи распознавания в научных публикациях отсутствуют полиномиальные алгоритмы в силу NP -полноты этой задачи. Второй алгоритм предназначен для перечисления всех совершенных сочетаний в многодольном гиперграфе, его ценность характеризуется тем, что это перечисление является бесповторным. Третий алгоритм предназначен для сведения задачи о покрытии гиперграфа звездами к задаче о совершенных сочетаниях, и его ценность заключается в том, что вычислительная сложность такого сведения является полиномиально ограниченной.

ГЛАВА 3. АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ НАХОЖДЕНИЯ МНОЖЕСТВА АЛЬТЕРНАТИВ ДЛЯ ЗАДАЧИ О СОВЕРШЕННОМ СОЧЕТАНИИ В МНОГОДОЛЬНОМ ГИПЕРГРАФЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ 3.1. Проблема неопределенности в математическом моделировании В настоящее время наблюдается большой интерес специалистов в области экономики, бизнеса, сферы управления, психологии и образования к применению математических методов в моделировании сложных экономических и социальных систем. Особенность моделирования подобных систем определяется принципом несовместимости [4]: чем сложнее система, тем менее мы способны дать точные и в то же время имеющие практическое значение суждения о ее поведении. Такого рода ситуации могут возникать как вследствие недостаточной изученности объектов, так и вследствие участия в наблюдаемых процессах человека или группы лиц. В результате значительная часть необходимой для математического описания информации существует в виде нечетких представлений или пожеланий экспертов, параметры системы оказываются неопределенными (хотя и не случайными) и в то же время сильно влияющими на ход решения. Обычные количественные методы анализа по своей сути мало пригодны и не эффективны для систем такого рода. Неточно заданные параметры либо не принимаются во внимание, либо с учетом определенных предположений и допущений заменяются средними оценками. Именно в этом смысле традиционные методы точного количественного анализа не имеют требуемого практического значения в реальных экономических, социальных и других системах. Кроме того, при моделировании процессов, связанных с участием человека, классические подходы не в состоянии отразить нечеткость человеческого мышления и поведения. Все указанное выше приводит к мысли о том, что для моделирования процессов управления больше подошли бы нечеткие математические методы, нежели классические. В этом плане любопытна точка зрения американского математика Л.Заде: Я считаю, что излишнее стремление к точности стало оказывать действие, сводящее на нет теорию управления и теорию систем, так как оно приводит к тому, что исследования в этой области сосредоточиваются на тех и только тех проблемах, которые поддаются точному решению. В результате многие классы важных проблем, в которых данные, цели и ограничения являются слишком сложными или плохо определенными для того, чтобы допустить точный математический анализ, оставались и остаются в стороне по той причине, что они не поддаются математической трактовке. Для того, чтобы сказать что-либо существенное для проблем подобного рода, мы должны отказаться от наших требований точности и допустить результаты, которые являются несколько размытыми или неопределенными. Согласно работе М.Блэка, неопределенность имеет место, когда универсальное множество [16, 44] состоит более, чем из одной точки [36]. Если для этих элементов множества заданы соответствующие вероятности или другие вероятностные характеристики, то имеет место вероятностная неопределенность [12]. Если известны только граничные элементы множества - интервальная неопределенность [3, 35]. И, наконец, при задании для каждого элемента множества соответствующей степени принадлежности - нечеткость [4, 44]. Неопределенность можно классифицировать по степени неопределенности (полная определенность, вероятностная, лингвистическая, интервальная, полная неопределенность), по характеру неопределенности (параметрическая, [12, 63]. Для преодоления трудностей представления неточных понятий, анализа и моделирования систем, в которых участвует человек, американским математиком Лотфи Заде в 1965 г. была предложена теория структурная, ситуационная) и по использованию получаемой в ходе управления информации (устранимая и неустранимая) нечетких (размытых) множеств [31]. Подход на основе теории нечетких множеств является, по сути дела, альтернативой общепринятым количественным методам анализа систем. Он имеет три основные отличительные черты: 1) вместо или в дополнение к числовым переменным используются нечеткие величины и так называемые лингвистические переменные;

2) простые отношения между переменными описываются с помощью нечетких высказываний;

3) сложные отношения описываются нечеткими алгоритмами. Такой подход дает приближенные, но в то же время эффективные способы описания поведения систем, настолько сложных и плохо определенных, что они не поддаются точному математическому анализу. До работ Л.Заде подобная качественная информация, по существу, просто терялась - было непонятно, как ее использовать в формальных схемах анализа альтернатив. Теоретические же основания данного подхода вполне точны и строги в математическом смысле и не являются сами по себе источником неопределенности. В каждом конкретном случае степень точности решения может быть согласована с требованиями задачи и точностью имеющихся данных. Подобная гибкость составляет одну из важных черт рассматриваемого метода. Основные приложения данного подхода находятся в таких областях, как искусственный интеллект, лингвистика, поиск информации, процессы принятия решений, распознавание образов, медицинская диагностика, психология, право, экономика и других отраслях человеческой деятельности. Для реальных сложных систем характерно наличие одновременно разнородной информации: 1) точечных замеров и значений параметров;

2) допустимых интервалов их измерения;

3) статистических законов распределения для отдельных величин;

4) лингвистических критериев и ограничений, полученных от специалистов-экспертов, и т.д. Реальные задачи содержат в себе нечеткие условия и некоторую нечеткость цели в связи с тем, что их постановку осуществляет человек. Учет фактора неопределенности при решении задач во многом изменяет методы принятия решения: меняется принцип представления исходных данных и параметров модели, становятся неоднозначными уровня быть понятия решения решения. в задачи и оптимальности решения. Чаще всего конкретное содержание задачи требует обеспечения заданного может нечеткости Наличие моделях неопределенности учтено непосредственно соответствующего типа представлением недетерминированных параметров как случайных величин с известными вероятностными характеристиками, как нечетких величин с заданными функциями принадлежности или как интервальных величин с фиксированными интервалами изменения. Попытки применения (интервального какого-либо анализа, конкретного статистических математического методов, аппарата игр, теории детерминированных моделей и т.д.) для принятия решений в условиях неопределенности позволяет отразить в модели лишь отдельные виды данных и приводит к безвозвратной потере информации других типов. Обычно на практике всегда имеется возможность наряду с точечной оценкой параметра и (наиболее допустимым значение его значением) которые указать может минимальное максимальное (интервал), принимать нечеткая величина. Кроме того, иногда удается построить и функцию, характеризующую допустимость каждого значения внутри заданного интервала на основе статистического материала или опроса группы экспертов. Теория нечетких множеств дает возможность проводить вычисления не с одним точечным значением, а с характеристической функцией и получать в результате вычислений нечеткую величину, для которой по максимуму значения функции может быть получена точечная (точная) оценка. Применение теории нечетких множеств позволяет провести также согласование различных нечетких решений при наличии нечетких целей, ограничений, коэффициентов, начальных и граничных условий. Даже в тех случаях, когда неопределенность в процессе принятия решений может быть представлена вероятностной моделью, обычно удобнее оперировать с ней методами теории нечетких множеств без привлечения теории вероятностей [4, 36]. В работе Atsushi Degawa было проведено сравнение аппарата теории нечетких множеств и теории вероятностей в случае, когда стохастические переменные определяются на тех же базовых множествах что и соответствующие нечеткие переменные. Делается заключение, что понятие неопределенности лучше выражается нечеткостью, чем случайностью, а аппарат теории нечетких множеств вычислительно намного проще, чем теории вероятностей [91]. В целом алгоритмы на базе нечетких множеств зарекомендовали себя на практике для самого разнообразного круга задач: 1. В системах искусственного интеллекта для управления работой технологического оборудования [38]. 2. Для оценки показателей качества программных средств [37]. 3. Применение нечетких уравнений и элементов нечеткой логики для диагностирования сложных систем - пакет программ Thermix - 2D для анализа динамики АЭС [97]. 4. Поведение диспетчерского персонала лучше всего описывается лингвистическими правилами поведения, а отклонение от принятых алгоритмов (ошибки и плохая работа диспетчеров, неисправности, возникшие помехи) хорошо моделируются с использованием нечетких алгоритмов [63]. 5. Автором были предложены модель диагностики дефляции структуры почвы пахотных площадей в условиях нечеткой информации [67], математическая модель диагностики выполнения работы с помощью уравнений нечетких отношений в индустриально-организационной психологии [69]. Получение во всех подобных моделях решений в нечеткой форме позволяет довести до сведения специалиста, принимающего решение, что если он согласен или вынужден довольствоваться нечеткой формулировкой проблемы и нечеткими сведениями о модели, то он должен быть удовлетворен и нечетким решением задачи.

3.2. Двухуровневый подход в математическом моделировании При математическом моделировании процессов, для которых характерны множественность критериев, интервальность или нечеткость значений исходных данных, классические методы точного количественного анализа задач оказываются недостаточными в силу слабой структурированности и неопределенности их параметров. Для решения задач в условиях многокритериальности и неопределенности данных предлагается концепция двухуровневого подхода в их моделировании. Эта концепция заключается в следующем: 1) 2) разработка общей схемы двухуровневого моделирования и выбор численных методов ее реализации;

разработка модели нижнего уровня, т.е. моделирование исходных данных и параметров задачи на базе аппарата нечеткой и интервальной математики, теории вероятностей и математической статистики, а также фрактального анализа [76]. Таким образом, на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня;

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

3.2.1. Моделирование на нижнем уровне Компания предлагает вниманию клиентов четыре ассортиментных позиции в продуктовой линейке: комфортабельная квартира в многоэтажном доме, комфортабельная квартира в многоэтажном панельном доме, коттедж и коттеджная секция. Под строительство Компании выделены участки: в центре города, в двух городских районах и пригороде. На базе строительной Компании скомплектованы четыре бригады рабочих разной квалификации, оснащенные специальной строительной техникой, причем две бригады имеют лицензию на строительство многоэтажного жилья, а две другие - на строительство малоэтажного жилья. Целью Компании является наиболее полное удовлетворение потребности в жилье с учетом пожеланий потребителей и возможностей Компании. Таким образом, построение стратегии ведения строительства Компанией базируется на векторных оценках следующих трех заинтересованных сторон: 1) оценка представляемой Компанией продуктовой линейки;

2) оценка предпочтений потребителей;

3) оценка имеющихся в распоряжении Компании ресурсов. На базе каждой из этих векторных оценок формируется интегральная оценка соответственно показателя привлекательности представляемых строительной Компанией проектов (P), показателя их потребительского качества (S) и оценка качественного уровня выполнения работы каждой бригады (Q). Указанное формирование оценок производится изложенным ниже методом аналитической иерархии (Analytic Hierarchy Process - AHP), получившим в настоящее время широкое распространение [81]. Достоинством метода AHP является то, что он может применяться в тех случаях, когда эксперты или лица, принимающие решения, не могут дать абсолютные оценки альтернатив по критериям и пользуются более слабыми сравнительными измерениями. На нижнем (первом) уровне иерархии AHP специалисты отдела маркетинга и сбыта строительной Компании (эксперты), используя шкалу относительной важности, попарным сравнением расставляют коэффициенты важности для каждого уровня иерархии: критерии - альтернативы. Заметим, что уровни относительной важности шкалы представляют собой лингвистические переменные (см. левый столбец в таб. 3.1), которые приведены к числовым значениям (см. правый столбец в таб. 3.1).

Шкала относительной важности Таблица 3.1 1 3 5 7 Уровень относительной важности Равная важность Умеренное превосходство Существенное или сильное превосходство Значительное (большое) превосходство Очень большое превосходство Далее вычисляются коэффициенты Количественное значение важности каждого уровня и подсчитывается показатель качества каждой альтернативы. Описание реализации этапов метода AHP представим на конкретном примере групп критериев, относящихся к каждой из трех сторон и конкретных экспертных оценках уровней относительной важности. Строительная Компания предлагает вниманию клиентов продуктовую линейку, состоящую из четырех ассортиментных позиций, называемых проектами H j, j = 1, m, ( m = 4 ):

H 1 - комфортабельная квартира в многоэтажном кирпичном доме;

H 2 - комфортабельная квартира в многоэтажном панельном доме;

H 3 - коттедж;

H 4 - коттеджная секция.

На множестве этих проектов определены критерии Компании:

K1 - экономичность проекта;

K 2 - доходность строительства этого варианта жилья для Компании;

K 3 - время строительства;

K 4 - трудоемкость строительных работ.

С помощью экспертов Компании, используя шкалу относительной важности, заполняется таблица 3. Матрица сравнений критериев Компании Таблица 3.2 Вес wi 0,151 0,391 0,067 0, вектор Критерии K 1 3 1/3 K 1/3 1 1/5 K 3 5 1 K 1/3 1 1/5 Собственный K K2 K3 K 0,760 1,968 0,340 1, Отметим, что критерии доходность строительства данного вида жилья ( K 2 ) и трудоемкость строительных работ ( K 4 ) имеют для Компании равную важность, умеренно превосходят по важности критерий лэкономичность проекта ( K1 ) и существенно превосходят критерий время строительства ( K 3 ). Для расчета коэффициентов важности критериев необходимо вычислить собственный вектор матрицы, извлекая корень n -й степени ( n - размерность матрицы сравнений) из произведений элементов каждой строки, а затем путем нормирования элементов собственного вектора матрицы определяются коэффициенты важности или веса критериев wi, i = 1, n, w i = n i = 1.

Таким же способом рассчитывается относительная важность v ji каждого проекта H j по каждому из критериев K i, j = 1, m, i = 1, n.

Результаты этих расчетов представлены в таблицах 3.3 - 3.6.

Относительная важность проектов по отдельным критериям строительной Компании Х По критерию K1 Экономичность проекта Таблица 3. H Проекты Hj H1 H2 H3 H H H H Собственный вектор 1,16 3,34 0,39 0, Вес v j1 0,23 0,65 0,08 0, 1 5 1/3 1/ 1/5 1 1/5 1/ 3 5 1 3 5 1/3 Х По критерию K 2 Доходность строительства данного вида жилья Таблица 3. H1 H Проекты H j H1 H H H 1 1/3 1/5 1/ 3 1 1/5 1/ 5 5 1 7 3 1/3 Собственный вектор 3,20 1,50 0,34 0, Вес v j 2 0,57 0,26 0,06 0, H H Х По критерию K 3 Время строительства Таблица 3. Проекты H j H1 H2 H1 H H H 1 5 1/3 1/ 1\5 1 1/5 1/ 3 5 1 3 3 1 Собственный вектор 1,16 2,94 0,51 0, Вес v j 3 0,22 0,57 0,10 0, H H Х По критерию K 4 Трудоемкость или качество строительных работ Таблица 3. Проекты H j H1 H2 H1 H H H 1 1/3 5 3 1 7 1/5 1/7 1 1/ 1/3 1/5 3 Собственный вектор 0,67 0,31 3,20 1, Вес v j 4 0,12 0,06 0,56 0, H H Далее на основании результатов, представленных в таблицах 3.2 - 3.6, осуществляется определение качества каждой альтернативы. Для этого, используя метод аналитической иерархии, необходимо произвести синтез полученных коэффициентов важности.

N Требуемые вычисления осуществляются по формуле S j = wi v ji, i = (3.1) где S j - показатель качества j -й альтернативы;

wi - вес i -го критерия (см.таб. 3.2);

v ji - важность j -й альтернативы по i -му критерию (см. таб. 3.3 - 3.6).

Для четырех вариантов жилья проведенные вычисления позволяют провести расчет показателей Pj привлекательности проектов для Компании:

P1 = 0,151*0,23 + 0,391*0,57 + 0,067*0,22 + 0,391*0,12 = 0, P2 = 0,151*0,65 + 0,391*0,26 + 0,067*0,57 + 0,391*0,06 = 0, P3 = 0,151*0,08 + 0,391*0,06 + 0,067*0,10 + 0,391*0,56 = 0, (3.2) P4 = 0,151*0,04 + 0,391*0,11 + 0,067*0,11 + 0,391*0,26 = 0, В результате опроса и анкетирования потребителей специалистами отдела маркетинга и сбыта строительной Компании (экспертами) выделены следующие потребительские критерии к представленным видам жилья Ci :

С1 - географическое месторасположение;

С2 - экологическая безопасность;

С3 - качество строительных работ;

С4 - инфраструктура жилья и жилищного комплекса.

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

Матрица сравнений потребительских критериев Сi Таблица 3.7 Вес wi 0,499 0,098 0,090 0, Критерии C 1 1/3 1/3 1/ C 3 1 1 C 3 1 1 C 5 1/5 1/7 Собственный вектор Сi C C2 C3 C 2,590 0,508 0,467 1, Критерий географическое месторасположение C1 существенно превосходит критерий линфраструктура C 4 и умеренно превосходит критерии лэкологическая безопасность C 2 и качество строительных работ C3 . Критерии лэкологическая безопасность и качество строительных работ имеют равную важность. Критерий линфраструктура существенно превосходит критерий лэкологическая безопасность и значительно - критерий качество строительных работ. В численном виде эти соотношения представлены в таблице 3.7. При этом расчет компонент собственного вектора и коэффициентов важности критериев, т.е. весов wi, осуществляется аналогично описанному выше расчету данных таблиц 3.3 - 3.6. Поскольку строительная Компания может строить любой из четырех видов жилья на любом из четырех выделенных ей участков, то потребителям предлагаются следующие проекты L j, j = 1,16 : j = 1 - комфортабельная квартира в многоэтажном кирпичном доме в центре города, j=2 - комфортабельная квартира в многоэтажном кирпичном доме в пригороде, j = 3 - комфортабельная квартира в многоэтажном кирпичном доме в первом городском районе, j = 4 - комфортабельная квартира в многоэтажном кирпичном доме во втором городском районе, j = 5 - комфортабельная квартира в многоэтажном панельном доме в центре города, j=6 - комфортабельная квартира в многоэтажном панельном доме в пригороде, j = 7 - комфортабельная квартира в многоэтажном панельном доме в первом городском районе, j = 8 - комфортабельная квартира в многоэтажном панельном доме во втором городском районе, j = 9 - коттедж в центре города, j = 10 - коттедж в пригороде, j = 11 - коттедж в первом городском районе, j = 12 - коттедж во втором городском районе, j = 13 - коттеджная секция в центре города, j = 14 - коттеджная секция в пригороде, j = 15 - коттеджная секция в первом городском районе, j = 16 - коттеджная секция во втором городском районе. По аналогии с формированием предыдущих таблиц вычисляем элементы таблиц 3.8 - 3.11, отражающих относительную важность проектов L j по потребительским критериям Ci.

Относительная важность проектов по потребительским критериям Х j По критерию С1 Географическое месторасположение 1 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 2 7 1 5 3 7 1 5 3 7 1 5 3 7 1 5 3 3 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 4 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 6 7 1 5 3 7 1 5 3 7 1 5 3 7 1 5 3 7 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 8 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 9 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 10 7 1 5 3 7 1 5 3 7 1 5 3 7 1 5 3 11 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 12 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 13 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 14 7 1 5 3 7 1 5 3 7 1 5 3 7 1 5 3 15 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1 1/ Таблица 3. 16 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 5 1/3 3 1 3,20 0,31 1,50 0,67 3,20 0,31 1,50 0,67 3,20 0,31 1,50 0,67 3,20 0,31 1,50 0, v j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0,14 0,01 0,07 0,03 0,14 0,01 0,07 0,03 0,14 0,01 0,07 0,03 0,14 0,01 0,07 0, Х j По критерию С 2 Экологическая безопасность 1 1 5 3 1 1 5 1/3 1/3 5 7 5 3 3 7 1 3 2 1/5 1 1/7 1/7 1/7 1/3 1/7 1/9 1/3 3 1 1 1/3 3 1/3 1/5 3 1/3 7 1 1/3 1/3 3 1/3 1/5 3 3 3 3 1 7 3 1 4 1 7 3 1 1 5 1 1/3 5 5 7 5 5 7 3 3 5 1 7 3 1 1 5 1 3 7 9 7 7 7 9 7 5 6 1/5 3 1/3 1/5 1/5 1 1/3 1/5 1/5 3 1 1 1/3 5 1 1/5 7 3 7 3 1 1 3 1 1/3 1 5 5 3 3 7 5 3 8 3 9 5 3 1/3 5 3 1 3 5 7 7 5 7 7 7 9 1/5 3 1/3 1/5 1/7 5 1 1/3 1 5 3 3 1 3 1 1 10 1/7 1/3 1/3 1/5 1/9 1/3 1/5 1/5 1/5 1 1/3 1/3 1/3 1 1/3 1/5 11 1/5 1 1/3 1/7 1/7 1 1/5 1/7 1/3 3 1 1/3 1/3 1 1/3 1/3 12 1/3 1 1/3 1/5 1/7 1 1/3 1/7 1/3 3 3 1 1 3 1 1/3 13 1/3 3 1 1/5 1/7 3 1/3 1/5 1 3 3 1 1 3 3 1 14 1/7 1/3 1/7 1/7 1/9 1/5 1/7 1/7 1/3 1 1 1/3 1/3 1 1/3 1/5 15 1 3 1/3 1/3 1/7 1 1/5 1/7 1 3 3 1 1/3 3 1 1/ Таблица 3. 16 1/3 5 1 1/3 1/5 5 1/3 1/7 1 5 3 3 1 5 3 1 0,46 2,62 0,76 0,37 0,26 1,77 0,41 0,26 0,98 3,46 2,48 2,32 1,05 3,63 1,41 0, v j 0,02 0,11 0,03 0,02 0,01 0,08 0,02 0,01 0,04 0,15 0,11 0,10 0,05 0,16 0,06 0, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Х j По критерию С3 Качество строительных работ 1 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 2 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 3 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 4 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 5 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 6 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 7 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 8 1 1 1 1 1 1 1 1 9 9 9 9 5 5 5 5 9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1 1 1 1 1/7 1/7 1/7 1/7 10 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1 1 1 1 1/7 1/7 1/7 1/7 11 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1 1 1 1 1/7 1/7 1/7 1/7 12 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1 1 1 1 1/7 1/7 1/7 1/7 13 1/5 1/5 1/5 1/5 1/5 1/5 1/5 1/5 7 7 7 7 1 1 1 1 14 1/5 1/5 1/5 1/5 1/5 1/5 1/5 1/5 7 7 7 7 1 1 1 1 15 1/5 1/5 1/5 1/5 1/5 1/5 1/5 1/5 7 7 7 7 1 1 1 Таблица 3. 16 1/5 1/5 1/5 1/5 1/5 1/5 1/5 1/5 7 7 7 7 1 1 1 1 0,38 0,38 0,38 0,38 0,38 0,38 0,38 0,38 4,88 4,88 4,88 4,88 1,37 1,37 1,37 1, v j 0,01 0,01 0,01 0,01 0,01 0,01 0,01 0,01 0,18 0,18 0,18 0,18 0,05 0,05 0,05 0, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Х По критерию С 4 Инфраструктура жилья и жилищного комплекса Таблица 3. j 1 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/ 2 7 1 5 5 7 1 5 3 7 1/3 5 1 7 1/3 3 3 3 1/5 1 1/3 3 1/5 1 1/3 3 1/5 1/3 1/3 3 1/7 1/3 1/ 4 5 1/5 3 1 5 1/3 3 1 5 1/5 1 1/3 5 1/5 1 1/ 5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/ 6 7 1 5 3 7 1 5 3 7 1/3 3 3 7 1/3 5 7 3 1/5 1 1/3 3 1/5 1 1/3 3 1/7 1/3 1/5 3 1/7 1/3 1/ 8 5 1/3 3 1 5 1/3 3 1 5 1/5 1 1/3 5 1/3 1 1/ 9 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/ 10 7 3 5 5 7 3 7 5 7 1 5 3 7 1 5 11 3 1/5 3 1 3 1/3 3 1 3 1/5 1 1/3 3 1/5 3 12 5 1 3 3 5 1/3 5 3 5 1/3 3 1 5 1/3 3 13 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/5 1 1/7 1/3 1/ 14 7 3 7 5 7 3 7 3 7 1 5 3 7 1 3 15 3 1/3 3 1 3 1/5 3 1 3 1/5 1/3 1/3 3 1/3 1 1/ 16 5 1/3 5 3 5 1/3 5 3 5 1/3 1 1 5 1/3 3 1 3,20 0,38 1,81 0,97 3,20 0,37 1,91 0,91 3,20 0,25 0,96 0,53 3,20 0,26 1,14 0, v j 0,14 0,02 0,08 0,04 0,14 0,02 0,08 0,04 0,14 0,01 0,04 0,02 0,14 0,01 0,05 0, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Далее с учетом данных таблиц 3.7 - 3.11 производится расчет показателей потребительского качества S j проектов L j по формуле (3.1):

S1 = 0,499*0,14 + 0,098*0,02 + 0,09*0,01 + 0,313*0,14 = 0, S 2 = 0,499*0,01 + 0,098*0,11 + 0,09*0,01 + 0,313*0,02 = 0, S 3 = 0,499*0,07 + 0,098*0,03 + 0,09*0,01 + 0,313*0,08 = 0,064 S 4 = 0,499*0,67 + 0,098*0,02 + 0,09*0,01 + 0,313*0,04 = 0, S 5 = 0,499*0,14 + 0,098*0,01 + 0,09*0,01 + 0,313*0,14 = 0, S 6 = 0,499*0,01 + 0,098*0,08 + 0,09*0,01 + 0,313*0,02 = 0, S 7 = 0,499*0,07 + 0,098*0,02 + 0,09*0,01 + 0,313*0,08 = 0, S 8 = 0,499*0,03 + 0,098*0,01 + 0,09*0,01 + 0,313*0,04 = 0,030 S 9 = 0,499*0,14 + 0,098*0,04 + 0,09*0,18 + 0,313*0,14 = 0, (3.3) S10 = 0,499*0,01 + 0,098*0,15 + 0,09*0,18 + 0,313*0,01 = 0, S11 = 0,499*0,07 + 0,098*0,11 + 0,09*0,18 + 0,313*0,04 = 0, S12 = 0,499*0,03 + 0,098*0,10 + 0,09*0,18 + 0,313*0,02 = 0, S13 = 0,499*0,14 + 0,098*0,05 + 0,09*0,05 + 0,313*0,14 = 0, S14 = 0,499*0,01 + 0,098*0,16 + 0,09*0,05 + 0,313*0,01 = 0, S15 = 0,499*0,07 + 0,098*0,06 + 0,09*0,05 + 0,313*0,05 = 0,062 S16 = 0,499*0,03 + 0,098*0,04 + 0,09*0,05 + 0,313*0,03 = 0, В результате проведенных расчетов строительная Компания принимает решение не рассматривать проекты j = 2,6,8,14,16, как проекты с низким показателем потребительского качества. Таким образом, Компанией не будут строиться многоэтажный кирпичный дом в пригороде ( L2 ), многоэтажный панельный дом в пригороде ( L6 ), многоэтажный панельный дом во втором городском районе ( L8 ), коттеджные секции в пригороде ( L14 ) и коттеджные секции во втором городском районе ( L16 ). Качество выполнения работы каждой из сформированных в Компании четырех альтернативных строительных бригад B j, j = 1,4 оценивается критериями Fi, i = 1,2 : F1 - профессионализм;

F2 - производительность труда. Критерий профессионализм ( F1 ) отражает то, как бригада планирует и организует свою работу, какими современными технологиями пользуется, как применяются технические, научные и профессиональные знания и способности работников, насколько рационально используется оборудование и материалы [20]. Критерий производительность труда ( F2 ) отражает такой показатель качества работы бригады, как время выполнения работы [20].

Матрица сравнений критериев уровня качества выполнения работы Fi Критерии Fi F1 F2 F1 F Вес wi 1,732 0,577 0,75 0, 1 1/ 3 Относительная оценка бригад по критериям качества выполнения работы Х По критерию F1 Профессионализм Бригады Bj B1 B2 B1 B Таблица 3. B B Собственный вектор Вес v j 1 1/3 1/5 1/ 3 1 1/3 1/ 5 3 1 1/ 7 5 3 3,20 1,50 0,67 0, 0,56 0,26 0,12 0, B B Х По критерию F2 Производительность Бригады Bj B1 B2 B1 B Таблица 3. B B Собственный вектор Вес v j 1 3 3 1/3 1 1 1/ 1/3 1 1 1/ 1 3 3 0,58 1,73 1,73 0, 0,13 0,37 0,37 0, B B С учетом данных таблиц 3.12 - 3.14 производится расчет показателей качества работы бригад Q j, j = 1,4 по формуле (3.1):

Q1 = 0,75*0,56 + 0,25*0,13 = 0, Q2 = 0,75*0,26 + 0,25*0,37 = 0, Q3 = 0,75*0,12 + 0,25*0,37 = 0, (3.4) Q4 = 0,75*0,06 + 0,25*0,13 = 0,078.

На основании численных значений (3.2) и (3.4) определим показатель качества R jk = Pj Qk реализации проекта Hj, j = 1, строительной Компанией в случае, когда этот j -й проект выполняется бригадой Bk, k = 1,4 :

R11 = 0,320*0,453 = 0,115 - кирпичный дом строится 1-ой бригадой;

R12 = 0,320*0,288 = 0,092 - кирпичный дом строится 2-ой бригадой;

R21 = 0,261*0,453 = 0,118 - панельный дом строится 1-ой бригадой;

R22 = 0,261*0,288 = 0,075 - панельный дом строится 2-ой бригадой;

R33 = 0,261*0,183 = 0,048 - коттедж строится 3-ей бригадой;

R34 = 0,261*0,078 = 0,020 - коттедж строится 4-ой бригадой;

(3.5) R43 = 0,158*0,183 = 0,029 - коттеджные секции строятся 3-ей бригадой;

R44 = 0,158*0,078 = 0,012 - коттеджные секции строятся 4-ой бригадой.

Таким образом, в завершение моделирования на нижнем уровне получены численные значения для следующих входных данных верхнего уровня моделирования: представленные в (3.3) показатели потребительского качества проектов S j, j = 1,16 ;

представленные в (3.5) показатели качества реализации проекта строительной Компанией R jk, j = 1,4, k = 1,4.

3.2.2. Моделирование на верхнем уровне На верхнем уровне моделирования рассматривается экономикоматематическая модель оптимизации процесса ведения строительства Компанией. Объекты моделирования представлены в виде трех множеств:

B = {b} - множество бригад, сформированных на базе строительной Компании для ведения строительства объектов, где b1 и b2 - соответственно 1-я и 2-я бригады, специализирующиеся на строительстве многоэтажного жилья, b3 и b4 - соответственно 3-я и 4-я бригады, специализирующиеся на строительстве малоэтажного элитного жилья;

H = {h} - множество вариантов жилья, составляющих продуктовую линейку строительной Компании, где h1 - многоэтажный кирпичный дом, h2 - многоэтажный панельный дом, h3 - коттедж, h4 - коттеджные секции;

U = {u} - множество участков, выделенных под строительство объектов, где u1 - участок в центре города, u 2 - участок в пригороде, u3 - участок в первом городском районе, u 4 - участок во втором городском районе.

Сформулируем следующую задачу. Бригаду b B назначить на строительство объекта h H на одном из выделенных под строительство участке u U. Результатом такого назначения должно стать удовлетворение потребности клиентов в жилье с учетом пожеланий потребителей и возможностей строительной Компании, т.е. строительной Компании необходимо выбрать такую стратегию ведения строительных работ, чтобы максимально удовлетворить как потребительское качество, так и качество реализации и привлекательности проектов для самой строительной Компании. С точки зрения математического моделирования эта задача представляет собой обобщение известной в теории дискретной оптимизации задачи о назначениях [82]. Математическая постановка рассматриваемой задачи базируется на 3дольном 3-однородном гиперграфе G = (V1,V2,V3, E ), который определяется следующим образом. Вершины первой доли v V1 поставлены во взаимно однозначное соответствие указанному выше множеству бригад B. Каждая вершина второй доли v V2 однозначно соответствует некоторому элементу из множества H вариантов жилья продуктовой линейки строительной Компании. Вершины третьей доли v V3 отражают множество участков U, выделенных под строительство объектов. Для построения множества ребер E = {e} рассматриваем всевозможные тройки вершин (v1, v2, v3 ) такие, что v1 V1, v2 V2, v3 V3. Всякую тройку называем допустимой, если бригада v может вести строительство объекта v2 на участке v3. Множество всех ребер E = {e} определяется как множество всех допустимых троек e = (v1, v2, v3 ), vi Vi, i = 1,3. Каждому ребру e E гиперграфа G = (V1,V2,V3, E ) приписаны два веса w (e), = 1,2, которые означают следующее: w1 (e) = f1 (v1, v2, v3 ) - показатель потребительского качества проекта S j, w2 (e) = f 2 (v1, v2, v3 ) - показатель качества реализации проекта строительной Компанией R jk. Показатели S j и R jk определены на нижнем уровне моделирования и представлены в (3.3) и (3.5). Допустимым решением x рассматриваемой задачи является совершенное сочетание x = (V, E x ), E x E на гиперграфе G = (V1,V2,V3, E ). Содержательно совершенное сочетание представляет одну из стратегий ведения строительных работ Компании. Через X = X (G ) = {x} обозначим множество всех допустимых решений (МДР) задачи о совершенных сочетаниях на гиперграфе G. Содержательно МДР представляет для Компании множество всевозможных стратегий ведения строительства. Качество оценивается с допустимых помощью решений векторной представляемой целевой задачи x X (ВЦФ) функции F ( x) = ( F1 ( x), F2 ( x)), состоящей из критериев вида MAXSUM и MAXMIN :

F1 ( x) = eE x w (e) max, F2 ( x) = min w2 (e) max. Критерий F1 ( x) означает eE x суммарный показатель потребительского качества данной стратегии строительства, критерий F2 ( x) - самый низкий показатель качества реализации проекта в выбранной стратегии ведения строительства. ~ ВЦФ F (x) определяет в МДР X паретовское множество (ПМ) X, состоящее из паретовских оптимумов (ПО) ~ [27]. В случае, если x одинаковые по значению ВЦФ решения ~ X x, x X считаются эквивалентными (неразличимыми), то из ПМ множество альтернатив (ПМА) выделяется полное представляет собой ~ ~ максимальную систему векторно-несравнимых ПО из X, X 0 X. Наиболее выбора и принятия решений [50].

X 0. ПМА X целесообразное решение выбирается из ПМА с помощью процедур теории Для представленной задачи множество ребер E = {e} гиперграфа G = (V1,V2,V3, E ) и веса ребер w (e), = 1,2 с учетом (3.3) и (3.5) заданы следующей таблицей 3.15. Ребро Вершины 1,5,9 1,5,11 1,5,12 1,6,9 1,6,11 2,5,9 2,5,11 2,5,12 2,6,9 2,6,11 3,7,9 3,7,10 3,7,11 3,7,12 3,8,9 3,8,11 4,7,9 4,7,10 4,7,11 4,7,12 4,8,9 4,8,11 Таблица 3. w 0,117 0,064 0,350 0,116 0,063 0,117 0,064 0,350 0,116 0,063 0,134 0,039 0,075 0,047 0,093 0,062 0,134 0,039 0,075 0,047 0,093 0, w 0,115 0,115 0,115 0,118 0,118 0,092 0,092 0,092 0,075 0,075 0,048 0,048 0,048 0,048 0,029 0,029 0,020 0,020 0,020 0,020 0,012 0, e e2 e e4 e5 e6 e e8 e e10 e11 e e13 e14 e e16 e17 e e19 e20 e e С помощью алгоритмов 1 и 2, представленных в главе 2, находим МДР X = {x} задачи о совершенных сочетаниях в гиперграфе G = (V1,V2,V3, E ). МДР X = {x} и значения критериев F1 ( x) и F2 ( x) для каждого решения отражены в таблице 3.16. Таблица 3. x F1 ( x) F2 ( x) 0,012 0,012 0,020 0,020 0,012 0,012 0,020 0, x1 x x3 x4 x5 x {e1, e9, e12, e22 } {e3, e10, e12, e21} {e3, e9, e16, e18 } {e3, e10, e15, e18 } {e4, e8, e12, e22 } {e5, e8, e12, e21 } 0,334 0,545 0,567 0,545 0,567 0,545 0,567 0, x7 x {e4, e8, e16, e18 } {e5, e8, e15, e18 } Используя таблицу 3.16, находим решение представленной задачи. ~ Решением задачи является ПМ и ПМА X = X 0 = {x3, x7 }. На рис.3.1 представлено одно из альтернативных решений x3, которое отражает следующую стратегию ведения строительства: 1-я бригада строит многоэтажный кирпичный дом во втором городском районе, 2-я бригада строит панельный дом в центре города, 3-я бригада в первом городском районе строит коттеджные секции, 4-я бригада назначается на строительство коттеджа в пригороде. Другое альтернативное решение x7 соответствует такой стратегии ведения строительства Компанией, когда 1-я бригада строит многоэтажный панельный дом в центре города, 2-я бригада поставлена на строительство кирпичного многоэтажного дома во втором городском районе, 3-я бригада в первом городском районе строит коттеджные секции, а 4-я бригада назначена на строительство коттеджа в пригороде. Решение x7 представлено на рис.3.2.

e e e 3 7 e 4 Рис.3.1. Одно из альтернативных решений задачи x e e e 3 e 4 8 Рис.3.2. Одно из альтернативных решений задачи x 3.3. Интервальные модели и многокритериальность При оптимизации систем управления в условиях неопределенности очень часто приходится ориентироваться на самое неблагоприятное (экстремальное) сочетание факторов неопределенности и использовать понятие гарантированного результата, т.е.

возникает необходимость обеспечить расчет и оптимизацию режима работы, который гарантированно будет лежать в области допустимых значений [39]. В этом случае наиболее перспективным способом адекватного отражения исследуемого объекта является построение интервальной модели [12, 40, 94]. Подобного рода экстремальные задачи исследовались на графах при моделировании задач землепользования [75], а также в области проектирования электронной техники [13, 17], транспортных сетей [19] и др. Большой интерес представляет исследование экстремальных интервальных задач на гиперграфах, когда на нижнем уровне математического моделирования исходные данные и параметры задачи представляются в виде интервальных значений, а на верхнем уровне формулируется и исследуется модель теории оптимизации, построенная на базе теории гиперграфов. В случае интервального задания параметров целевой функции возникает принципиальный методологический вопрос определения понятия оптимума x 0 X. Тем более остается открытым вопрос об алгоритмах нахождения задачи наилучшего решения. В настоящей главе к предлагается дискретной конструктивное решение указанных вопросов путем сведения интервальной математического программирования многокритериальной (векторной) задаче. Представленный выше переход от интервальной задачи к многокритериальной порождает определенные алгоритмические проблемы, к рассмотрению которых мы переходим.

3.3.1. Общая постановка интервальных оптимизационных задач на гиперграфах Под интервалом A = [a1, a2 ] = {t | a1 t a 2, a1a 2 R} будем понимать замкнутый отрезок вещественной прямой R [3];

I (R) - множество всех замкнутых интервалов на R. Всякое вещественное число x может считаться интервалом и записываться [ x, x]. Два интервала A = [a1, a2 ] и B = [b1, b2 ] называются равными ( A = B ), если они равны в теоретико-множественном смысле. Из этого определения следует, что A = B a1 = b1, a 2 = b2. Символ понимается в обычном теоретико-множественном смысле, причем обозначает не обязательно строгое включение, т.е. соотношение A B допускает равенство интервалов. Отношение порядка на множестве I (R) определяется следующим образом: A < B тогда и только тогда, когда a1 b1 или a2 b2, причем хотя бы одно из этих неравенств является строгим. Пересечение A B интервалов A и B пусто, если a2 b1 или b2 < a1, в противном случае A B = [max{a1, b1}, min{a 2, b2 }]. Значения суммы и произведения интервалов A = [a1, a2 ] и B = [b1, b2 ] могут быть получены с помощью формул:

A + B = [a1 + b1, a2 + b2 ], A B = [min{a1b1, a1b2, a2 b1, a2 b2 }, max{a1b1, a1b2, a2 b1, a2 b2 }].

Обоснование введенных таким образом операций, а также существование изоморфизма между вещественными числами a,b,... и интервалами [a, a ], [b, b], Е можно найти в [3]. Под интервальной задачей на гиперграфах будем понимать задачу, которая формулируется следующим образом. Пусть дан n -вершинный гиперграф G = (V, E ), в котором каждому ребру e E приписан вес w(e), заданный в виде интервала w(e) = [ w1 (e), w2 (e)], где w1 (e) w2 (e). Допустимое решение рассматриваемой задачи определяется в виде реберного подгиперграфа x = (Vx, E x ), Vx V, E x E. Через X = {x} обозначается МДР этой задачи. На X определена интервальная целевая функция (ИЦФ) вида MAXSUM w( x) = eE x w(e) max.

(3.6) Согласно определению операции сложения интервалов [3] получим значение ИЦФ w( x) = [ w1 ( x), w2 ( x)], (3.7) где wi ( x) = eE x w (e), i i = 1,2. Требуется найти такой элемент x 0 X, на котором значение ИЦФ (3.6) - (3.7) достигает максимума. В случае задания интервальных весов решение задачи, вообще говоря, неединственно, и нахождение оптимума наталкивается на проблему выбора наиболее целесообразного решения из множества несравнимых альтернатив. В связи с этим для определения подмножества решений необходимо ввести отношения предпочтения, эквивалентности и несравнимости [12, 35]. Определение 3.1. Решение x1 предпочтительнее решения x2 или, другими словами, решение x доминируется решением x1, если wi ( x1 ) wi ( x2 ), i = 1,2, при этом хотя бы одно неравенство должно быть строгим. Эту предпочтительность обозначим через x1 f x2. Определение 3.2. Решения x1, x2 X называются несравнимыми, когда имеет место строгое вложение интервалов, т.е. выполняется либо w( x1 ) w( x2 ), либо w( x2 ) w( x1 ). Несравнимость пары x1 и x2 обозначаем через x1 x2. Определение 3.3. Решения x1, x2 X эквивалентны, если совпадают соответствующие им интервалы w( x1 ) = w( x2 ). Обозначим эквивалентность этих решений как x1 x2. бинарные отношения предпочтения и ~ несравнимости порождают ПМ [62, 79] X X. Паретовское множество состоит из паретовских оптимумов, которые в свою очередь определяются следующим образом. Введенные на МДР X x Определение 3.4. Решение ~ X называется паретооптимальным для x задачи (3.6), если не существует x X такого, что x f ~.

~ Таким образом, X состоит из неразличимых решений. В качестве искомого решения интервальной ~ рассматривается как ПМ X, так и ПМА X 0 [27]. задачи (3.6) 3.3.2. Сведение интервальной задачи к 2-критериальной Сформулированная выше интервальная задача (3.6) сводится к задаче многокритериальной оптимизации с тем же множеством допустимых решений X и векторной целевой функцией ВЦФ вида F ( x) = ( F1 ( x), F2 ( x)), где (3.8) F1 ( x) = eE x w ( x) max, (3.9) (3.10) (3.11) F2 ( x) = eE x d (e) max, d (e) = w2 (e) w1 (e).

Определение 3.5. Решение ~ X называется ПО для задачи с ВЦФ x (3.8) - (3.10), если не существует такого x * X, что F ( x * ) F ( ~ ), = 1,2, x при этом хотя бы одно неравенство является строгим. При исследовании задачи с ВЦФ (3.8) - (3.10) будем учитывать справедливость следующих утверждений. Лемма 3.1. Пусть на множестве допустимых решений X = {x} задачи векторной оптимизации с максимизируемыми критериями ВЦФ (3.8) - (3.10) ~ порождает ПМ X, а ВЦФ FC ( x) = ( F1 ( x), F2 ( x) + C ), (3.12) ~ где C - некоторая константа, порождает ПМ X C. Тогда справедливо ~~ равенство X = X C. Доказательство леммы 3.1 непосредственно следует из определения ПМ для задачи векторной оптимизации. Лемма 3.2. ПМ задачи векторной оптимизации на n -вершинном гиперграфе G = (V, E ) с максимизируемыми критериями вида (3.6) и вида (3.9) - (3.10) совпадают, если для каждого решения x X множества ребер E x = const. мощность Доказательство. Задача с критериями (3.9) - (3.10) является частным случаем задачи с критериями вида (3.6). Покажем, что любую задачу с критериями (3.9) - (3.10) можно преобразовать в задачу с критериями вида (3.6). Действительно, пусть каждое ребро e E гиперграфа G = (V, E ) взвешено двумя весами w1 (e) и d (e) = w2 (e) w1 (e). Добавим ко второму весу d (e) каждого ребра e E некоторую постоянную величину k, так чтобы выполнялось неравенство w1 (e) d (e) + k. МДР задачи при этом не изменится. Пусть x X - некоторое допустимое решение, для которого w1 ( x) = eE x w ( e), d ( x) = eE x d (e). Тогда значение целевой функции по первому w1* ( x) = w1 ( x), критерию (3.7) остается прежним а значение целевой функции по второму критерию (3.7) будет иметь вид * w2 ( x) = d ( x) + E x k.

Величина C = E x k по условию является постоянной. Следовательно, * критерии w1* и w2 имеют вид (3.12). Таким образом, по лемме 3.1 ПМ задач с весами ребер w1 (e), d (e) и w1 (e), d (e) + k будут совпадать. Лемма 3.2 доказана. Теорема 3.1. ПМ задач с ИЦФ (3.6) - (3.7) и ВЦФ (3.8) - (3.11) совпадают. Доказательство. Поскольку ПО задач с ИЦФ (3.6) - (3.7) и ВЦФ (3.8) - (3.11) эквивалентны, то ПМ указанных задач совпадают. Далее, согласно лемме 3.2, получаем, что ПМ задач с критериями (3.9) - (3.11) и (3.6) - (3.7) также совпадают. Отсюда следует утверждение теоремы. Таким образом, согласно теореме 3.1, при исследовании ПМ интервальной (3.11). задачи можно использовать утверждения, полученные относительно 2-критериальной задачи с весовыми критериями вида (3.9) - 3.3.3. О разрешимости задач многокритериальной оптимизации с помощью алгоритмов линейной свертки критериев В задачах многокритериальной оптимизации оптимальность по Парето является центральным понятием теории исследования операций и принятия решений. Разрешимость этих задач с помощью алгоритмов линейной свертки критериев задачу с (АЛСК) часто рассматривается критерием, критериев как практический получается свертыванием метод нахождения оптимальных решений. АЛСК решают однокритериальную обобщенным частных который линейной частных комбинацией (линейным критериев в один). Широкий класс многокритериальных задач, все эффективные решения которых находятся с помощью АЛСК, указан в [24, 92]. Вместе с тем, можно говорить о существовании дискретных многокритериальных задач, для которых АЛСК не обеспечивает получение всех эффективных решений. Изучение возможности применения АЛСК для нахождения ПМ и его подмножеств было начато работой Кумпанса [98]. Многие результаты в этой области были систематизированы в [93]. Полученные с тех пор результаты [25, 11] существенно расширили перечень примеров пропуска линейной сверткой эффективных решений и уточнили оценки мощности ПМ. Так, например, в работах [55, 56] показано, какие именно из оптимальных по Парето (эффективных) решений находит линейная свертка критериев. Проведенный вычислительный эксперимент [58, 61, 59] по решению бикритериальных и трехкритериальных задач о назначениях и покрывающих деревьях показал, что доля находимых с применением линейной свертки оптимальных по Парето решений невелика, монотонно убывает с увеличением мощности ПМ и не зависит от специфики задачи. Интересным для исследования представляется вопрос о разрешимости с помощью АЛСК задач нахождения ПМ и ПМА на гиперграфах. В настоящей главе рассматривается вопрос о разрешимости с помощью АЛСК интервальной задачи о сочетаниях на 3-дольных 3-однородных гиперграфах.

3.3.4.

Исследование разрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи о сочетаниях с критериями вида MAXSUM на 3-дольном гиперграфе.

Пусть дана интервальная задача, которая, как показано в п. 3.3.2, сведена к 2-критериальной задаче с ВЦФ (3.8), состоящей из критериев (3.9) и (3.10). Для определения понятия линейная свертка критериев введем множество векторов размерности N :

N = { = (1, 2,..., N ) : = 1, > 0, = 1,2,..., N } = N (3.13) Рассматривая конкретную ВЦФ (3.8) при N = 2, линейную свертку ее критериев (ЛСК) условимся обозначать через F (x). Для выбранного вектора N ЛСК определяется выражением F ( x) = F ( x).

= N (3.14) Любой точный алгоритм, максимизирующий (минимизирующий) линейную свертку критериев (3.14), называется алгоритмом линейной свертки критериев (АЛСК) [29, 62, 75]. Вычислительная схема всякого АЛСК строится с учетом того, что является справедливым следующее Утверждение 3.1. Для любого вектора из множества (3.13) элемент x *, максимизирующий на МДР X линейную свертку критериев (3.14) данной ВЦФ, является ПО [27, 78]. Таким образом, интервальная задача с критерием (3.6) называется ~ x разрешимой с помощью АЛСК, если ~ X найдется вектор > 0, удовлетворяющий равенству F ( ~ ) = max F ( x). x x X Однако, как было отмечено выше, АЛСК не всегда обеспечивают ~ x получение всех ПО ~ X [27, 45, 74]. Интервальная задача (3.6) неразрешима с помощью АЛСК, если существует индивидуальная задача, для которой выполняется условие:

~ ~ X такое, что для всякого [0,1] F ( ~ ) < max F ( x), x x x X (3.15) ~ которое называется условием неразрешимости. Иными словами, если ПМ X хотя бы одной индивидуальной задачи о совершенном сочетании на 3дольном 3-однородном гиперграфе содержит такой элемент x *, на котором ни при каком 2 не достигает максимума значение свертки (3.14), то можно говорить о неразрешимости с помощью АЛСК однородном гиперграфе. Теорема 3.2. Для всякого 3-дольного гиперграфа G интервальная задача о совершенном сочетании с критериями вида MAXSUM неразрешима с помощью АЛСК. Доказательство. Следуя подходу, предложенному в [95], в качестве доказательства приведем пример, показывающий для индивидуальной задачи существование такого паретооптимального решения, которое невозможно получить ни при какой свертке критериев. Рассмотрим такую индивидуальную задачу о совершенном сочетании на 6-вершинном 3-дольном 3-однородном гиперграфе (см. рис. 3.3) соответствующей массовой интервальной задачи о совершенном сочетании на 3-дольном 3 G = (V1,V2,V3, E ), в котором V1 = {1,2}, V2 = {3,4}, V3 = {5,6}, E = {e1, e2,..., e6 }, где e1 = (1,3,5), e2 = (2,4,6), e3 = (1,3,6), e4 = (2,4,5), e5 = (1,4,5), e6 = (2,3,6).

Рис.3.3. 6-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) Множеством допустимых решений задачи является X = X (G ) = {x1, x2, x3 }, где x1 = {e1, e2 }, x2 = {e3, e4 } и x3 = {e5, e6 }. Допустимые решения и веса ребер представлены на рис. 3.4, 3.5, 3.6.

e [9,47] e [11,53] Рис.3.4. Допустимое решение x1 = {e1, e2 }, где w(e1 ) = [9,47] w(e2 ) = [11,53] [10,38] e [15,32] e Рис.3.5. Допустимое решение x2 = {e3, e4 }, где w(e3 ) = [10,38] w(e4 ) = [15,32] [31,42] e e [14,18] Рис.3.6. Допустимое решение x3 = {e5, e6 }, где w(e5 ) = [14,18] w(e6 ) = [31,42] Согласно определению операции сложения интервалов, ИЦФ (3.6) - (3.7) на допустимых решениях принимает интервальные значения:

w( x1 ) = eE x w(e) = [9,47] + [11,53] = [20,100] w( x2 ) = w( x3 ) = В eE x w(e) = [10,38] + [15,32] = [25,70] eE x w(e) = [14,18] + [31,42] = [45,60] индивидуальной интервальной задаче на рассматриваемой гиперграфе G МДР X = X (G ) состоит из трех допустимых решений X = {x1, x2, x3 }.

Согласно введенным на множестве X отношениям предпочтения, несравнимости и эквивалентности, определяем, что x1 x2, x1 x3, x2 x3. Таким образом, значения ИЦФ w(x) (3.6) - (3.7) показывают, ~ ~ что для МДР X, ПМ X и ПМА X 0 выполняются равенства X = X = X 0.

Соответствующую ВЦФ (3.8) - (3.10) свертку (3.14) условимся обозначать через w (x). Используя это обозначение, покажем, что решение x невозможно найти с помощью свертки w ( x) = w ( x). Для обоснования = этого утверждения покажем, что для решения x2 X 0 выполняется условие неразрешимости (3.15):

w1 ( x2 ) + (1 ) w2 ( x2 ) < max{ w1 ( xk ) + (1 ) w2 ( xk )} [0,1]. k =1, Подставим значения ИЦФ (3.6) - (3.7) w1 ( xk ) и w2 ( xk ), k = 1,3 в последнее неравенство и получим выражение 25 + 70(1 ) < max{20 + 100(1 ),45 + 60(1 )} или, что то же самое, 70 45 < max{100 80,60 15} или иначе (3.16) f 2 ( ) < max( f1 ( ), f 3 ( )), где f1 ( ) = w( x1, ) = 100 80, f 2 ( ) = w( x2, ) = 70 45, f 3 ( ) = w( x3, ) = 60 15.

Чтобы убедиться в справедливости неравенства (3.16) построим на отрезке [0,1] графики функций f1 ( ) = 100 80, f 2 ( ) = 70 45, f 3 ( ) = 60 15 (см. рис. 3.7).

f k ( ) 90 80 70 60 50 40 30 20 10 0 f 3 ( ) f 2 ( ) f 1 ( ) Рис.3.7. Графики функций f k ( ), k = 1,3, [0,1] Из рис.3.7 видно, что функции f1 ( ) и f 3 ( ) образуют паретовскую границу рассматриваемого конкретного критериального Отсюда с пространства очевидностью f ( ) = w( x, ) = max{ f1 ( ), f 3 ( )}, [0,1].

вытекает, что рассмотренная выше индивидуальная задача о совершенном сочетании на 3-дольном 3-однородном гиперграфе неразличима с помощью АЛСК, т.к. никакая линейная свертка ее критериев не достигает максимума на элементе x2. Теорема 3.2 доказана.

3.4. Выводы по третьей главе Основным результатом третьей главы является предложенный автором конструктивный двухуровневый (т.е. подход реализованный к конкретным алгоритмом) таких математическому моделированию дискретных слабо структурированных многокритериальных задач, у которых исходные данные представляют собой экспертные оценки. Теоретическая и прикладная ценность этого подхода состоит в том, что слабоструктурированная задача полностью структурируется, т.е. сводится к четкой математической постановке в виде векторной задачи о совершенных сочетаниях на 3 -дольном 3 -однородном гиперграфе. Эта постановка включает в себя также известный случай наибольшей неопределенности, когда исходные данные (экспертные оценки) представляются в виде интервалов. Исследованию последнего, т.е. интервального, случая посвящена заключительная часть третьей главы. Доказанные в этой части теоремы 3.1 и 3.2, во-первых, конструктивно обосновывают сведение интервальной задачи к двукритериальной и, во-вторых, выявляют факт неразрешимости интервальной задачи с помощью алгоритмов линейной свертки критериев. Особая ценность первого из этих результатов заключается в том, что в научных публикациях отсутствуют алгоритмы решения экстремальных интервальных задач, сформулированных как на графах, так и на гиперграфах.

ЗАКЛЮЧЕНИЕ В ходе проделанной исследовательской работы получены следующие основные результаты: 1. Обосновано свойство полноты задачи о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами. 2. Дан строгий вывод достижимых верхних оценок структурной сложности многодольных однородных гиперграфов: верхняя оценка количества ребер в полном многодольном однородном гиперграфе, оценка максимальной мощности множества совершенных сочетаний и максимальной мощности множества покрытий многодольного гиперграфа звездами. 3. Обоснована труднорешаемость задач о совершенных сочетаниях и о покрытии многодольного гиперграфа звездами в многокритериальной постановке. 4. Построен полиномиальный алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном гиперграфе. 5. Построен алгоритм бесповторного перебора всех совершенных сочетаний в многодольном гиперграфе. 6. Построен полиномиальный алгоритм сведения задачи покрытия многодольного 7. Сформулирована однородного концепция гиперграфа звездами к задаче о совершенных сочетаниях на гиперграфе. двухуровневого моделирования дискретных задач в условиях неопределенности: на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня, математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное управление рассматриваемым процессом. В качестве конкретной реализации двухуровневого моделирования представлена модель процесса выбора и принятия стратегии ведения строительства некоторой строительной компании. 8. Доказана неразрешимость с помощью алгоритмов линейной свертки критериев интервальной задачи о совершенных сочетаниях с критериями вида MAXSUM на 3-дольных гиперграфах.

ЛИТЕРАТУРА 1.

Абрамович Ф.П., Вагенкнехт М.А., Хургин Я.И. Решение нечетких систем линейных алгебраических уравнений LR-типа. - В сб.: Методы и системы принятия решений. Рига: РПИ, 1987, с.35 -47. 2. 3. 4. Айзерман М.А., Алексеров Ф.Т. Выбор вариантов. Основы теории. Алефельд Г., Хельцбергер Ю. Введение в интервальные вычисления. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в М.: Наука, ГРФМЛ, 1990.-236 с. М.: Мир, 1987. - 542с. нечетких условиях: Монография. Тюмень: Издательство Тюменского государственного университета, 2000. 352с. 5. Алтунин А.Е., Чуклеев С.Н., Семухин М.В., Крел Л.Д. Методическое руководство по технологическим расчетам сложных систем газодобычи при неточных параметрах. Тюмень, 1984, 48 с. 6. 7. 8. 9. 10. 11. Аоки М. Введение в методы оптимизации. М.: Наука, 1977, 344 с. Безбородов В.Г., Жаков А.М. Суда космической службы. - Л.: Берж К. Теория графов и ее применения. М.: Изд. иностр. лит-ры, Беспалько В. П. Педагогика и прогрессивные технологии обучения. Бэстенс Д.-Э., Ван Ден Берг В.-М., Вуд Д. Нейронные сети и Волконский В.А., Еганян Г.К., Поманский А.Б. О множестве Судостроение, 1980, с.248 1962.-320с. М.:Школа, 1995. - 255с. финансовые рынки. - М.: ТВП Научное издательство, 1998. эффективных точек в линейных многокритериальных задачах //Сиб. Матем. Журнал. 1983. 24-№2.-С.9-17 12. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. М.: Наука, 1989.-420с.

13. 14. 15. 16.

Вязгин В.А.Б Федоров В.В.

Математические методы автоматизированного проектирования. - М.: Высшая школа, 1989. - 184 с. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Глушков В.М. О системной оптимизации//Кибернетика. - 1980. -№5.Гудмен И. Нечеткие множества как классы эквивалентности Наука, ГРФМЛ, 1971.-383 с. С.89-90. случайных множеств. В сб.: Нечеткие множества и теория возможностей. М: Радио и связь, 1986, с.241 - 264. 17. 18. 19. Гуткин Л.С. Оптимизация радиоэлектронных устройств по совокупности показателей качества. - М.: Сов. радио. 1975. - 368 с. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые Демченко А.И. Синтез транспортных сетей в условиях задачи. М.: Мир, 1982.-416 с. неопределенности исходной информации// Труды семинара по интервальной математике, Саратов, 29 - 31 мая, 1990: Саратов, 1990. - С. 10 - 16. 20. 21. 22. Джуэлл Л. Индустриально-организационная психология. СПб.: Питер,2001.-720с. Дресслер Г. Управление персоналом. М.: Бином, 1997. - 418 с. Евдокимов М.В., Медницкий В.Г., Сигал И.Х. Бикритериальная задача переоборудования производства. //Известия РАН. Теория и системы управления. -№ 5. - 2001. С. 90-96. 23. 24. Ежов А.А., Шумский С.А. Нейрокомпьютинг и его применение в Емеличев В.А., Кравцов М.К., Янушкевич О.Я. Разрешимость экономике и бизнесе. - М.: ЭАИ МИФИ, 1998. векторной траекторной задачи на лузкие места с помощью алгоритма линейной свертки // Доклады Академии наук Белоруси. 1996. 40-№4. С. 25.

Емеличев В.А., Перепелица В.А. К вычислительной сложности дискретных многокритериальных задач // Изв. АН СССР. Техн.кибернетика. 1988. №1. С.78 - 85 26. - 504. 27. 33 28. 29. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384с. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах// Журн. вычис. математики и мат.физики. - 1989. - Т.29., №2. - С.171 - 183. 30. 31. 32. 33. Жак С.В. Математические модели менеджмента и маркетинга. - Заде Л.А. Понятие, лингвистической переменной и его применение к Зыков А.А. Гиперграфы//Успехи Матем. наук. - 1974. -Т. 29. вып.6.-С. Ивченко Б.П., Мартыщенко Л.А., Монастырский М.Л. Теоретические Ростов-на-Дону: ЛаПО, 1997. - 320 с. принятию приближенных решений. М.: Мир, 1976, 165с. 89-154. основы информационно-статистического анализа сложных систем. - СПб.: Питер, 1997. 34. 35. 36. Ильин Н.И., Лукманова И.Г. и др. Управление проектами. - СПб.: Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального Кандель А., Байатт У.Дж. Нечеткие множества, нечеткая алгебра, статистика. Труды американского общества инженеров Два - ТрИ, 1996. - 610 с. анализа.-Новосибирск: Наука, Сибирское отделение, 1986. - 590с. нечеткая Емеличев В. А., Перепелица В. А. Сложность дискретных многокритериальных задач // Дискретная математика. - 1994. - Т.6, №1.-С.ЗЕмеличев В.А., Перепелица В.А. Полные задачи многокритериальной дискретной оптимизации//Сообщения АН ГССР. - 1988. - Т.131, №3. - С. радиоэлектронников, т.66, 1978, с.37- 37.

Карповский Е.Я., Чижов С.А.

Оценка показателей качества программных средств с использованием лингвистических переменных. Управляющие системы и машины, №2, 1987, с. 17 -19 38. 39. 40. Кейн Л.А. Искусственный интеллект в обрабатывающих отраслях Кейн В.М. Оптимизация систем управления по минимаксному Ким-Гю-Пхир. Оптимальное распределение ресурса в условиях неопределенности// Международная конференция по промышленности. Нефть, газ и нефтехимия за рубежом, №9, 1986,с. 117-122 критерию. - М.: Наука, 1985, 248 с. интервальной интервальным и стохастическим методам в науке и технике (Интервал - 92): Сборник трудов - Москва, 1992. - Т.I. С.60 - 63. 41. Ковалев В.И., Бондарева М.К., Омельченко Г.Г. и др. Исследование на основе адаптации системы управления Отчет о КА к путей и способов повышения эффективности управления орбитальными группировками изменяющимся 42. условиям космической обстановки// НИР Перспектива - 31. - М.: МО РФ, в/ч 32103, 2001 г. 52 с. Ковалев В.И., Бондарева М.К., Омельченко Г.Г. и др. Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами// Отчет о НИР Голкипер. - М.: МО РФ, в/ч 32103, 2000 г. 112 с. 43. 173. 44. 45. Кофман А. Введение в теорию нечетких множеств. М: Радио и связь, Кравцов М.К. Неразрешимость задач векторной дискретной 1982,432 с. оптимизации в классе алгоритмов линейной свертки критериев //Дискретная математика. - 1996.8 - №2. - С.89 - 96 46. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.-432с. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер//Успехи матем. наук. - 1985. - Т.40, №1 (241).-С. 107 47. 48. 49. 50. 200с. 51. 52. 53. 54. 55. в Куржанский Кучин Б.Л.

А.Б.

Управление и наблюдение в АСУ в условиях неопределенности. М.: Наука, 1977, 392 с. Оперативная информация магистральных газопроводов. М: Недра,1979. Кучин Б.Л., Алтунин А.Е. Управление системой газоснабжения в Ларичев О.И. Наука и искусство принятия решения. - М.: Наука, 1979.Лебедев В.В. Математическое моделирование социальноосложненных условиях эксплуатации. - М.: Недра, 1987, 209 с.

экономических процессов. - М.: Изограф, 1997. Лизинский В.М. Диагностико-аналитические процедуры и активноЛовас Л., Пламмер М. Прикладные задачи теории графов. Теория Машарова Т.В. Педагогические теории, системы и технологии Меламед И. И., Сигал И. X. Исследование линейной свертки критериев многокритериальном дискретном программировании. //Журнал игровые формы в управлении. - М.: Новая школа, 1996. - 300с. паросочетаний в математике, физике, химии - М.: Мир, 1998. - 653 с. обучения. - Киров: ВГПУ, 1997. - 370с.

вычислительной математики и математической физики. 1995. - Т.35. - №8. С. 1260-1270. 56. Меламед И. И., Сигал И. X. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. - М.:В - РАН. 1996.-52 с. 57. Меламед И.И. Методы оптимизации в транспортном процессе. ЦИ НТ. ВИНИТИ. Сер. Оптимизация управления транспортом. Т.10.-М.: ВИНИТИ. 1991.-162 с. 58. Меламед И.И., Сигал И.Х. Вычислительное исследование линейной свертки критериев в многокритериальном дискретном программировании // Докл. РАН. 1995. Т.345. №4. С.463 - 59.

Меламед И.И., Сигал И.Х. Распределение эффективных решений в некоторых бикритериальных задачах дискретного программирования. М.: В - РАН, 2001 60. 1996 61. Меламед И.И., Сигал И.Х. Вычислительное исследование трикритериальных задач о деревьях и назначениях // Ж. вычисл.матем. и матем. физ. 1998. Т.38 №10. С.1780-1787 62. 63. 64. 65. 66. 67. 68. Михалевич В.С., Волкович В.Л. Вычислительные методы исследования Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, Негойце К. Применение теории систем к проблемам управления. М: Норри Д., Ж. де Фриз. Введение в метод конечных элементов. - М: Омельченко Г.Г., Салпагаров С.И. Диагностика дефляции пахотных Омельченко Г.Г., Салпагаров С.И. Двукритериальная задача и проектирования сложных систем. М.: Наука, 1982. - 286 с. 1981, 488 с. 1975,528с. Мир, 1981, 179 с. Мир, 1981, 304с. площадей// Успехи современного естествознания. - 2003-№4. - С.99-100 оназначениях индустриально-организационной психологии// Современные аспекты экономики. - 2002. - 1(14). - С.139-144. 69. Омельченко ГГ., Салпагаров С.И. Математическая модель диагностики работы трудов с V помощью уравнений нечетких отношений. Всероссийского симпозиума Математическое выполнения Сб.научных Меламед И.И., Сигал И.Х. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. М.: В - РАН, моделирование и компьютерные технологии. -Кисловодск, 2002. -С. 10-12.

70.

Омельченко Г.Г., Салпагаров С.И.

Математическая обучения модель на организации 71.

личностно-ориентированного учащихся гиперграфе// Успехи современного естествознания. - 2004. - №1. - С. 9 - 12. Омельченко Г.Г., Перепелица В.А. Алгоритм выделения совершенных сочетаний на многодольном гиперграфе/ Доклады Одесского семинара по дискретной математике. Южный научный центр НАН и МОН Украины. - Одесса: Астропринт. - 2004. - №1. - С. 26 - 43. 72. 73. с. 74. Перепелица В.А., Сергеева Л.Н. Исследование неразрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач // Кибернетика и системный анализ. - 1996. - №2. - С. 71 - 77 75. Перепелица В.А., Сергиенко И.В. Исследование одного класса целочисленных многокритериальных задач// Журн. вычислит. математики и мат. физики. - 1988. - Т.28., №3. - С. 400 - 419 76. 333 с. 77. 78. 79. 80. Пищулин Н.П., Ананишнев В.М. Образование и управление. - М.: Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно Подиновский В.В., Ногин В.Д. Парето-оптимальные решения Жизнь и мысль, 1999. - 296 с. применяемым критериям. ЦМ.: Сов. Радио, 1975.-192с. многокритериальных задач. ЦМ.: Наука, 1982. - 256 с. Пратусевич Ю.М., Сербиненко М.В., Орбачевская Г.Н. Системный анализ процесса мышления. - М.: Медицина, 1989. Петерс Э. Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка: Пер. с англ. ЦМ.: Мир. 2000. Оре О. Теория графов. - М.: Наука, 1980. - 336 с. Перепелица В.А., Мамедов А.А. Исследование сложности и разрешимости векторных задач на графах: Уч.пособие. Черкесск, 1995. - 81. 82. 83.

Саати Т., Кернc К. Аналитическое планирование. Организация систем. Сакович В.А. Исследование операций. ЦМинск.: Вышэйшая школа, Сергиенко И.В., Перепелица В.А. К проблеме нахождения множеств ЦМ.: Радио и связь, 1991. 1984.-256 с. альтернатив в дискретных многокритериальных задачах //Кибернетика. 1987. - №5. - С. 85 - 93. 84. 85. 86. 87. 88. 89. 90. Сидоренко Е.В. Методы математической обработки в психологии. - Татт У. Теория графов. - М.: Мир, 1988. - 320 с. Третьяков П.И. Управление школой по результатам. - М.: Новая Третьяков П.И., Сенновский И.Б. Технология модульного обучения в Трояновский В.М. Математическое моделирование в менеджменте. Харари Ф. Теория графов. - М.: Мир, 1973. - 300 с. Хубаев Г.Н. Сложные системы: экспертные методы сравнения/ СПб.: Социально-психологический центр, 1996.

школа, 1997.-288 с. школе. - М.: Новая школа, 1997. - 160 с. М.: Русская Деловая Литература, 1999. - 240 с.

Приложение к журналу Известия высших учебных заведений: СевероКавказский регион, общественные науки, 1999 г., №3. - С. 7 - 24. 91. Atsushi Degawa. Улучшение методов обнаружения и подавления "плохой" информации при оценке состояния энергосистем. "Дэнки гаккай ромбуси, Trans. Inst. Elec. Eng. Jap.", 1984, №2, p.69 - 76 (яп.) 92. 93. 94. Brucker P. Discrete Parameter optimization problem and essential efficient points//Operat.Res. - 1972/16 №5. pp.189 - 197 Charnes A., Cooper W.W. Management Models and Industrial Application of Csendes T. An Interval Method for Bounding Level Sets of Parameter Linear Programming. N.Y.: Wiley, 1961. Estimation Problems/ Computing 41 (1989), pp.75 - 86.

95. 96. 97. 98.

Emelichev V.A. and Perepelitsa V.A. Multiobjective problems on the Gessing R. Two-level hierarchical control for stochastic optimal resource Kitowski J. Zastosowanie relacyjnych rownan rozmytych."Zesz.nauk.AGH: Koopmans T.C. Analysis of production as an efficient combination T.C. Koopmans. Activity Analysis Production spanning trees of a graph. Soviet Math. Dokl. Vol. 37 (1988), 1, pp.114 - 117. allocation. УInt. J. Contr.Ф, 1985, №1, p.161 - 175. Autom." 1984, №37, 107p. ofactivities / Ed. 99.

andAllocation. N.Y.: Wiley, 1951. P. 33-97 Moor R.E. A servey of interval methods for differential equations, УProc. 23 rd IEEE Conf. Decis. And Contr., Las Vegas, Nev., 1984, v.3Ф, New York, 1984, p.1529 - 1535. 100. Schwandt H. An interval arithmetic approach for the constraction of an almost globally convergent method for the solution of the nonlinear on the unit square. УSIAM J. Sci. A St. Comput.Ф, 1984, v.5, №2, p.427 - 452. 101. Voloshin V.I. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. Fields Institute for Research in Mathematical Sciences, 2002, 182 p.

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

label 10,20,30,40,50,60,70,80,90,100,110;

var n,l,i,j,j1,k,m,m0,m1,p,o,kchas,w,sum,wybr,k1,k2,k3,k4,k5,m2,kontr,sumk,p1,p2,p3, p4:integer;

e:array[1..20,1..3] of integer;

r:array[1..20,1..20,1..20] of integer;

r1,r2,r3,sum1,r4,r5,r6:array[1..20,1..20] of integer;

kch:array[0..500] of integer;

sum2,chet1,chet2,chet3,chet4:array[0..10] of integer;

s:string;

begin {Ввод данных} write('Введите:кол-во веpшин ');

readln(n);

write(' кол-во долей ');

readln(l);

write(' кол-во pебеp ');

readln(i);

writeln('Список pебеp');

for j:=1 to i do begin for k:=1 to l do begin write('pебpо ',j,', веpшина ',k,' - ');

readln(e[j,k]);

end;

end;

writeln;

for j:=1 to i do begin p:=1;

for k:=1 to l do begin for m:=1 to i do begin if e[j,k]<>e[m,k] then r[j,m,p]:=1 else r[j,m,p]:=0;

end;

p:=p+1;

end;

end;

writeln('Постpоение исходной таблицы смежности');

for j:=1 to i do begin p:=2;

for o:=1 to i do begin for k:=1 to l do begin if r[j,o,k]=0 then goto 10;

end;

r1[j,p]:=o;

p:=p+1;

10:;

end;

r1[j,1]:=p-1;

end;

kchas:=trunc(n/l);

for j:=1 to kchas do begin kch[j]:=0;

end;

w:=0;

for k:=1 to kchas do begin for j:=1 to i do begin if e[j,1]=k then begin kch[k]:=kch[k]+1;

w:=w+1;

r2[1,w]:=j;

end;

end;

end;

{kchas-число блоков kch[j]-pазмеp блока} for j:=i+1 downto 2 do r2[1,j]:=r2[1,j-1];

r2[1,1]:=0;

for j:=2 to i+1 do begin r2[j,1]:=r2[1,j];

end;

for j:=2 to i+1 do begin for k:=2 to i+1 do begin for j1:=2 to r1[r2[j,1],1] do begin if r1[r2[j,1],j1]=r2[1,k] then r2[j,k]:=r2[1,k];

end;

end;

end;

for j:=1 to i+1 do begin for k:=1 to i+1 do begin if r2[1,j]=r2[k,1] then r2[k,j]:=r2[1,j];

write (r2[j,k]:4,' ');

end;

writeln;

end;

writeln;

writeln('Pабота алгоpитма - пеpесечение стpок');

for j:=2 to i+1 do begin m0:=0;

m1:=0;

for m:=1 to kchas do begin m1:=m1+kch[m];

m0:=m1-kch[m]+1;

sum:=0;

for k:=m0+1 to m1+1 do begin sum:=sum+r2[j,k];

end;

if sum=0 then begin writeln('Pебpо ',r2[j,1],' выбpосить');

wybr:=j;

goto 20;

end;

end;

20:;

end;

for k1:=2 to i+1 do begin for j:=2 to i+1 do begin if (k1=wybr) or (j=wybr) then r2[k1,j]:=0;

end;

end;

for j:=1 to i+1 do begin for k:=1 to i+1 do begin write (r2[j,k]:4,' ');

end;

writeln;

end;

for j:=2 to i+1 do begin k2:=1;

for m:=1 to kchas do begin k2:=k2+kch[m];

k1:=k2-kch[m]+1;

if (j>=k1) and (j<=k2) then goto 30;

for k:=k1 to k2 do begin k4:=1;

sum1[j,k]:=0;

for m2:=1 to kchas do begin k4:=k4+kch[m2];

k3:=k4-kch[m2]+1;

for k5:=k3 to k4 do begin if (r2[j,k5]=r2[k,k5]) and (r2[j,k5]<>0) then begin sum1[j,k]:=sum1[j,k]+1;

goto 50;

end;

end;

50: end;

60: end;

30: end;

end;

for j:=1 to i do begin for k:=1 to i do begin sum1[j,k]:=sum1[j+1,k+1];

end;

end;

writeln;

for j:=1 to i do begin kontr:=0;

k4:=0;

sumk:=0;

for m2:=1 to kchas do begin k4:=k4+kch[m2];

k3:=k4-kch[m2]+1;

sumk:=0;

if (j>=k3) and (j<=k4) then goto 70;

kontr:=k4-k3+1;

for k5:=k3 to k4 do begin if sum1[j,k5]=kchas then goto 70;

sumk:=sumk+1;

end;

if sumk=kontr then begin p4:=j+1;

for j1:=2 to i+1 do begin r2[j+1,j1]:=0;

r2[j1,j+1]:=0;

end;

end;

70:sumk:=0;

80: end;

end;

writeln;

writeln('Pебpо ',r2[p4,1],' выбpосить');

for j:=1 to i+1 do begin for k:=1 to i+1 do begin write (r2[j,k]:4,' ');

end;

writeln;

end;

for j:=2 to kch[1]+1 do begin k4:=kch[1]+1;

p:=1;

for m2:=2 to kchas do begin k4:=k4+kch[m2];

k3:=k4-kch[m2]+1;

for k5:=k3 to k4 do begin sum:=0;

k2:=1;

for m:=1 to kchas do begin k2:=k2+kch[m];

k1:=k2-kch[m]+1;

for k:=k1 to k2 do begin if r2[j,k]=0 then goto 100;

if r2[j,k]=r2[k5,k] then begin sum:=sum+1;

goto 110;

end;

100: end;

110: end;

if sum=kchas then begin if j=2 then begin chet1[p]:=k5;

p1:=p;

end;

if j=3 then begin chet2[p]:=k5;

p2:=p;

end;

if j=4 then begin chet3[p]:=k5;

p3:=p;

end;

p:=p+1;

end;

end;

90: end;

end;

writeln;

writeln('Pезультат pаботы алгоpитма - тупиковая таблица');

writeln('Для стpоки 1 -',r2[1,2]);

for j:=1 to p1 do begin for k:=1 to i+1 do begin r4[j,k]:=r2[chet1[j],k];

write(r4[j,k]:4);

end;

writeln;

end;

writeln;

writeln('Для стpоки 2 - ',r2[1,3]);

for j:=1 to p2 do begin for k:=1 to i+1 do begin r5[j,k]:=r2[chet2[j],k];

write(r5[j,k]:4);

end;

writeln;

end;

readln(s);

end.

Приложение 2 НЕЧЕТКАЯ ЭКСПЕРТНАЯ СИСТЕМА ДИАГНОСТИКИ ФАКТОРОВ ВЫПОЛНЕНИЯ РАБОТЫ Индустриально-организационные психологи и другие специалисты, изучающие работу организаций и поведение сотрудников, занимаются множеством проблем, но вопрос выполнения работы остается среди них ключевым. Как и в случае с любым другим человеческим поведением, уровень и качество выполнения работы определяется множеством переменных, связанных с личностью и средой [20]. Бламберг М. и Прингл К. предложили модель выполнения работы, которая объединяет широкий круг индивидуальных факторов и факторов, связанных со средой [20]. Эти факторы авторы называют способностью, готовностью и возможностью выполнять работу. Дополняя друг друга, способность, готовность и возможность определяют уровень выполнения конкретной работы. Оценка выполнения работы играет координирующую роль в деятельности организации по управлению персоналом. На организационном уровне информация, полученная в ходе оценки выполнения работы, дает представление о сильных и слабых сторонах рабочей силы в целом, которое можно использовать для более эффективного планирования человеческих ресурсов. Для формализованного описания указанной выше ситуации, в которой нет полной определенности и однозначности, используется математический аппарат теории нечетких множеств [47]. Одна из областей применения аппарата теории нечетких множеств и нечеткой логики - построение диагностических нечетких экспертных систем, что по существу является методом моделирования с помощью уравнений нечетких отношений.

В настоящей работе предложена математическая модель диагностической системы выполнения работы. Пусть полное пространство предпосылок X состоит из m факторов, а полное пространство заключений Y - из n симптомов: X = {x1, x2,..., xm }, Y = { y1, y 2,..., y n }.

Рассмотрим модель диагностики выполнения работы при m = 3 и n = 3 :

x1 - способность выполнять работу;

x2 - готовность выполнять работу;

x3 - возможность выполнять работу;

y1 - объем выполненной работы;

y 2 - точность выполнения работы;

y3 - креативные способности, способность подавать новые идеи, находить новые и лучшие пути выполнения производственных операций и проявлять воображение.

x1 x2 x А Входы R = [rij ] i = 1, m Выходы y1 y y В j = 1, n R B = AХ R А - нечеткое множество в X (факторы выполнения работы);

В - нечеткое множество в Y (заключения, оценки выполнения работы);

Х - правило композиции нечетких выводов.

При этом между каждым членом предпосылок и каждым членом заключений существуют причинные отношения:

xi y j или rij, представляющие собой нечеткие отношения xi и y j. Если собрать вместе нечеткие отношения между всеми xi и y j, то получим m n -матрицу нечетких отношений R : R = [rij ], i = 1, m, j = 1, n. Далее, для каждого rij введем меру причинных отношений в виде вещественного числа в интервале [0,1]. Кроме того предпосылки будем рассматривать как вход, а заключения - как выход. При этом указанные выше состояния можно рассматривать как состояния нечеткой системы. В случае диагностики R идентифицируется по знаниям эксперта [87]. В процессе диагностики наблюдаются выходы B (оценки выполнения работы), а определяются входы A (состояние факторов выполнения работы). Например, знания эксперта, оценивающего выполнение работы, преобразуется в вид 0,4 0,5 0,7 R = 0,8 0,5 0,6. 0,2 0,6 0, Если при оценке выполнения работы обнаружена небрежность и допущение одних и тех же ошибок, т.е. плохая точность выполнения работы, и при этом объем выполненной работы и креативные способности в норме, то состояние работы можно оценить как B = 0,2 | y1 + 0,6 | y 2 + 0,3 | y3. Желательно определить причины такого состояния A = a1 | x1 + a 2 | x2 + a3 | x3. В этом случае A и B представим в виде нечетких векторов-строк B = [0,2;

0,6;

0,3] ;

A = [a1, a2, a3 ].

Тогда B = A Х R можно представить в виде 0,4 0,5 0,7 [0,2;

0,6;

0,3] = [a1, a 2, a3 ] 0,8 0,5 0,6 0,2 0,6 0, либо, трансформируя, в виде нечетких векторов-столбцов 0,2 0,4 0,8 0,2 a1 0,6 = 0,5 0,5 0,6 a. 2 0,3 0,7 0,6 0,3 a3 Получаем уравнения нечетких отношений 0,2 = (0,4 a1 ) (0,8 a2 ) (0,2 a3 ) 0,6 = (0,5 a1 ) (0,5 a 2 ) (0,6 a3 ) 0,3 = (0,7 a1 ) (0,6 a2 ) (0,3 a3 ).

Отсюда, 0,2 = 0,8 a2 0,6 = 0,6 a 0,3 = 0,7 a1.

Таким образом, решением являются 0 a1 0, 0 a2 0, 1 a3 0,6, т.е. при заданных экспертных оценках необходимо обратить внимание на такой фактор как возможность совершить работу, детерминантами которого являются: инструменты, оборудование, материалы и запчасти, условия труда, действие коллег, поведение лидера, наставничество, организационная политика, информация, время и оплата труда [20].

Pages:     | 1 | 2 |    Книги, научные публикации