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

Суть этого свойства состоит в следующем. Пусть дан граф G = (V, E ) и определено его МДР X (G ) = {x}. Пополним множество E некоторым новым ребром e, в результате чего получен новый граф G = (V, E ), где E = E {e}. Тогда свойство монотонности по ребрам заключается в том, что для мощностей полученных МДР всегда выполняется неравенство X (G ) X (G ). В частности, задача о паросочетаниях на графах является монотонности по ребрам присуще и сформулированным выше в главе задачам о сочетаниях на гиперграфе и о покрытии гиперграфа звездами.

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

Через µ1 (n, l) обозначим максимальную мощность МДР задачи Z 1l о совершенных сочетаниях на n -вершинном l -дольном l -однородном гиперграфе. Справедлива Теорема 2.2. При n, кратном l, максимальная мощность МДР задачи Z1l на n -вершинном гиперграфе определяется равенством µ1 (n, l) = (m!) l 1, Доказательство. Сначала отметим, что множество совершенных сочетаний G = (V1,V2,...,Vl, E ) является непустым только в случае равномощности долей допустимое решение x состоит из m ребер, которые обозначим через ek, где индекс k {1,2,..., m} приписан тому ребру, которое содержит вершину vk V1. Через E (v1 ) будем обозначать подмножество всех ребер e E, инцидентных вершине v1 из первой доли V1.

последовательно строить элементы x X (G ), выбирая для очередного совершенного сочетания x его ребра e в порядке возрастания индекса k :

e1 = (v1, v, v3,..., vl ) E (v11 ) для фиксированной вершины v1 выбор каждой из оставшихся вершин v из соответствующих долей Vs, s = 2, l можем осуществить количеством способов, равным Vs = m. Таким образом, ребро e1 можем выбрать m l 1 различными способами.

Например, в представленном на рис.2.1 подмножестве E (v1 ) 9вершинного 3-дольного 3-однородного ( l = 3, m = 3 ) полного гиперграфа G = (V1,V2,V3, E ) ребро e1 E (v1 ) можем выбрать числом способов, равным Рис.2.1. Подмножество E (v1 ) E полного 9-вершинного 3-дольного 3однородного гиперграфа G = (V1,V2,V3, E ) Следовательно, ребро e можно выбрать (m 1) l 1 способами. Пусть выбраны k 2 ребер, составляющих сочетание x. Тогда выбор очередного (k + 1) -го ребра e +1 можно осуществить числом способов, равным (m k ) l 1. Отсюда следует, что число всех различных способов, которыми можно выбрать l Теорема 2.2 доказана.

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

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

Теорема 2.3. Задача Z1l является труднорешаемой, если ее ВЦФ (1.1) – (1.3) содержит не менее двух критериев вида MAXSUM (1.2).

Доказательство. Рассмотрим задачу Z 1l, ВЦФ которой содержит не менее двух критериев вида MAXSUM. Согласно теореме 2.2 и лемме 2.3 в случае полного n -вершинного l -дольного l -однородного гиперграфа для записи искомого ПМА X 0 потребуется не менее (m!) l 1 операций, m =.

При представлении этой трудоемкости в качестве единицы измерения используем оценку (2.9), т.е. разделим (m!) получим нижнюю оценку трудоемкости записи ПМА, равную Используя известную формулу Стирлинга убедиться, что для достаточно ограниченных значений l величина (2.10) растет экспоненциально с ростом n.

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

2.3. Оценки вычислительной сложности векторной задачи покрытия гиперграфа звездами Среди поставленных в п.1.2 задач реальную практическую значимость имеет задача покрытия l -дольного l -однородного гиперграфа простыми обозначив ее через Z 2l (r ), где r = (r1, r2,..., rn ) представляет собой вектор степеней звезд в допустимом покрытии x X ; сумму этих степеней обозначим через m = rt. Через J (n, l, n1 ) = {G} обозначим множество всех n -вершинных l -дольных l -однородных гиперграфов n = n1 + m(l 1), в которых мощности долей Vs = ns, s = 1, l удовлетворяют следующим условиям: мощность первой доли V1 = n1, n1 m и оставшиеся доли являются равномощными с количеством вершин в каждой из них:

ns = m, s = 2, l. При выполнении этих условий допустимым решением формулируемой задачи Z 2l (r ) является такой реберный подгиперграф x = (V1,...,Vl, E x ) гиперграфа G J (n, l, n1 ), в котором каждая компонента связности представляет собой простую звезду степени rt r с центром в соответствующей вершине vt V1, t = 1,2,..., n1. Количество таких звезд в покрытии x равно числу n1 вершин в первой доле; X = X (G ) = {x} – МДР задачи Z 2l (r ) на гиперграфе G.

При фиксированных значениях параметров n, l, r через µ 2 (n, l, r ) обозначим максимальную по всем векторам степеней r мощность МДР Z 2l (r ) о покрытии n -вершинного l -дольного l -однородного задачи гиперграфа звездами. Оказывается, что эта максимальная мощность не зависит от варьирования компонент данного вектора степеней r = (r1, r2,..., rn ), и является справедливой удовлетворяющего условию задачи Z 2l (r ) на гиперграфе G = (V1,V2,...,Vl, E ) J (n, l, n1 ) определяется покрытий x X (G ) будем использовать специальный полный (n n1 ) вершинный (l 1) -дольный гиперграф G * = (V2,V3,...,Vl, E * ), равномощные доли которого унаследованы от рассматриваемого исходного гиперграфа e = (v1, v2, v3,..., vl ) E вершины v1 V 1. Через X (G * ) обозначим множество всех совершенных сочетаний в специальном полном гиперграфе G *.

';

Примечание 2.2. Согласно теореме 2.2 мощность X (G * ) множества всех совершенных сочетаний в полном (l 1) -дольном гиперграфе G * определяется формулой µ1 (n n1, l 1) = X (G * ) = (m!) l 2.

x = (V1,...,Vl, E x ) X (G ), E x E, осуществляется в два этапа. На первом этапе в специальном гиперграфе G * выделяется совершенное сочетание x * = (V2,V3,...,Vl, E x* ), E x* E *, состоящее из m ребер ek* = (v2k,..., v sk,..., vlk ), v sk Vs, s = 2, l, перенумерованных индексом k = 1,2,..., m. На втором этапе множество этих ребер разбивается на n1 подмножеств, перенумерованных индексом t = 1,2,..., n1 так, что t -ое подмножество состоит из rt ребер, где rt – ek = (vt, v2k,..., vsk,..., vlk ) размерности l, принадлежащее исходному гиперграфу G. Тогда для фиксированного t полученные таким образом rt ребер образуют звезду степени rt с центром в вершине vt, причем эта звезда принадлежит исходному гиперграфу G. Множество полученных таким образом звезд с центрами в вершинах vt V1, t = 1,2,..., n1 образует по построению допустимое покрытие x X (G ).

покрытий звездами x X (G ). Этот алгоритм состоит из этапов 1* и 2. Этап 1* представляет собой алгоритм перечисления элементов множества гиперграфа G *. На этапе 2 всякое совершенное сочетание x * X (G * ) порождает множество M ( x * ) X (G ) всех допустимых решений x X (G ), каждое их которых состоит из звезд таких, что в результате удаления центров в этих звездах получаем ребра, образующие совершенное сочетание x *.

Для описания процесса порождения множества M ( x * ) и вычисления k = 1,2,..., m. При порождении всех звезд степени r1 с центром в вершине v1 V1 можем из множества E x* выбрать r1 ребер C m различными способами.

Далее при порождении следующей звезды с центром v2 V1 можем выбрать r2 ее ребер C mr различными способами. Продолжая это рассуждение, получаем, что мощность множества M ( x * ) составляет где с учетом равенства r1 + r2 +... + rn = m полагаем C m r r... r = C0 = 1.

Перенумеруем элементы множества X (G * ) и выберем из него пару всякой такой пары по определению множества X (G * ) всегда выполняется неравенство На основании определения множества M ( x * ), x * X (G * ) для всякого полного гиперграфа G * и соответствующего ему специального гиперграфа G * рассуждением от противного из неравенства (2.12) непосредственно получаем, что является справедливой следующая Лемма 2.4. Каждая пара совершенных сочетаний x1*, x2 X (G * ), x1* x M ( x1* ), M ( x2 ) X (G ) ; т.е. разные сочетания из X (G * ) не могут породить Заметим, что для всякой пары «полный гиперграф G = (V1,...,Vl, E ) – его специальный гиперграф G * » множество всех совершенных сочетаний X (G * ) можно получить путем последовательного удаления из всех ребер e E x непосредственно получаем, что является справедливой Лемма 2.5. Для всякой пары «полный гиперграф G = (V1,...,Vl, E ) – его совершенным сочетаниям x * X (G * ) составляет МДР задачи Z 2l (r ) на Поскольку соотношение (2.11) выполняется для каждого x * X (G * ), то из лемм 2.4, 2.5 и теоремы 2.2 с учетом примечания 2.2 и равенств (2.11) получаем, что объединение всех порождаемых множеств M ( x * ) X (G ) по Мощность этого МДР является максимальной (т.е.

определяется формулой Теорема 2.4 доказана.

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

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

Теорема 2.5. Задача Z 2l (r ) является труднорешаемой, если ее ВЦФ (1.1) – (1.3) содержит не менее двух критериев вида MAXSUM (1.2).

Доказательство. Рассмотрим такой полный n -вершинный l -дольный гиперграф G = (V1,...,Vl, E ), G J (n, l, n1 ), для которого выполняется условие n1 =. Тогда m = = и, согласно теореме 2.4 и лемме 2.3, для записи Используя в качестве единицы измерения трудоемкости оценку (2.9), трудоемкости записи ПМА, равную Используя формулу Стирлинга n! (n e) n 2n, нетрудно убедиться, что экспоненциально с ростом n. Тем самым по аналогии с теоремой 2. получаем доказательство теоремы 2.5.

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

2.4. Алгоритм проверки выполнения необходимых условий существования совершенного сочетания в многодольном Пусть n кратно l и для пары n, l задан n -вершинный l -дольный l однородный гиперграф G = (V, E ) = (V1,...,Vl, E ), в котором доли равномощны ( V1 = V2 =... = Vl ), что является необходимым условием существования в G совершенного сочетания. Для этого гиперграфа через S = S (G ) = (U, R ) обозначим так называемый «специальный граф». Элементами множества U определенное (взаимно однозначным соответствием) ребро исходного гиперграфа G ; R = { } – множество ребер графа S. Таким образом, количество гипервершин специального графа S совпадает с количеством ребер гиперграфа G : U = E. Условимся гипервершины в U обозначать символами ребер в гиперграфе G, т.е. U = {e}. Специальный граф S по S = (U 1,U 2,...,U m, R ).

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

Вершины, составляющие такую клику в специальном графе S, однозначно совершенное сочетание. Ниже приводится описание процедуры построения специального графа S = S (G ).

На рис.2.2 и 2.3 представлены 12-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) и соответствующий ему специальный граф определению, является 10-вершинным (т.к. в исходном гиперграфе G число ребер E = 10 ) и 4-дольным (т.к. в гиперграфе G мощность первой доли V1 = 4 ).

Рис.2.2. 12-вершинный 3-дольный 3-однородный гиперграф G = (V1,V2,V3, E ) e1 = (1,5,9) e2 = (2,6,10) e3 = (3,7,11) e4 = (4,8,12) e5 = (1,7,12) e6 = (4,8,9) e7 = (3,6,10) e8 = (2,5,11) e9 = (1,6,11) e10 = (3,7,12) Рис.2.3. Специальный граф S = S (G ) для гиперграфа G на рис.2. Построение специального графа S = S (G ) = (U, R) = (U 1,...,U k,...,U m, R) осуществляется следующим образом. Пусть в гиперграфе G первая доля специального графа U = {e} ставится во взаимно однозначное соответствие множеству ребер E = {e} так, что всякий элемент e U специального графа S представляет собой подмножество вершин v V данного гиперграфа G = (V, E ), образующих некоторое ребро e E, т.е. e V. Затем множество U разбивается на m долей таким образом, что доля U 1 состоит из всех таких вершин e U, каждая из которых содержит вершину v1 в первой доле исходного гиперграфа G, т.е. v1 V1 (на рис.2.3 доля U 1 состоит из вершин e1, e5, e9, каждая из которых содержит вершину v1 гиперграфа G на рис.2.2);

доля U 2 состоит из всех таких вершин e U, каждая из которых содержит вершину v2 также в первой доле исходного гиперграфа G, т.е. v2 V1 (на рис.2.3 доля U 2 состоит из вершин e2, e8, каждая из которых содержит вершину v2 гиперграфа G на рис.2.2); … ; доля U m состоит из всех таких вершин, каждая из которых содержит вершину vm также в первой доле исходного гиперграфа G, т.е. vm V1 (на рис.2.3 доля U m, m = 4 состоит из вершин e4, e6, каждая из которых содержит вершину v4 в первой доле гиперграфа G на рис.2.2). Далее определяется множество ребер R = { } специального графа S. Для всякой пары вершин e, e U ребро = (e, e) включается в R тогда и только тогда, когда пересечение этой пары является пустым, т.е. e e = (среди десяти вершин e1, e2,..., e10 специального графа S = (U, R) на рис.2.3 двадцать пять пар вида (ei, e j ), 1 i < j 10 имеют Формированием множества ребер R завершается построение специального графа S.

выполнения необходимых условий существования совершенного сочетания в l -дольном l -однородном гиперграфе G. На вход этого алгоритма подается специальный граф S = S (G ) = (U, R ), в котором вершины первой доли перенумерованы индексом q = 1,2,..., L1, т.е. U 1 = {e1,..., e q,..., e L }, L1 = U 1.

Работа алгоритма 1 состоит из L1 этапов. Начало очередного q -го этапа состоит в фиксации очередной вершины e q U 1. Обозначим через U kq фиксированной вершиной e q, k = 2,3,..., m. Объединение этих подмножеств этап q проверяет наличие m -вершинных клик в множестве U q и в случае их существования выделяет их. Если хотя бы одно из подмножеств U kq, k = 2, m является пустым, то этап q завершает работу безрезультатно, установив, что множество U q искомой клики не содержит. Например, в специальном графе на рис.2.3 для вершины e 3 = e9 подмножество U 23 является пустым, и поэтому этап q = 3 завершает работу безрезультатно. В противном случае в начале своей работы этап q объединяет эти подмножества вместе с e q и образует множество смежности этой вершины U q, U q U.

Например, в специальном графе на рис.2.3 для вершины e1 = e1 это множество имеет вид U = {e } UU k1, где U 2 = {e2 }, U 3 = {e3, e7, e10 }, представляется как U 1 = {e1} {e2 } {e3, e7, e10 } {e4 }. Индуцированный этим S q = (U q, R q ) = (U 1q,...,U kq,...,U m, R q ). Отметим, что в специальном графе на рис.2.3 индуцированный множеством подграф S 1 представлен на рис.2.4.

Рис.2.4. Подграф S 1 специального графа S на рис.2. Цель работы этапа q состоит в проверке ряда определенных ниже необходимых условий принадлежности рассматриваемой вершины какойлибо m -вершинной клике в подграфе S q. Если хотя бы одно из этих условий не выполняется, то этап q завершает свою работу безрезультатно.

Работа этапа q реализуется на базе так называемой таблицы множеств смежности (кратко «таблицы МС») T q = Tikq, в которой индекс k = 1,2,..., m представляет собой номера долей подграфа S q, а индекс i = 1,2,..., N q представляет собой новую порядковую нумерацию вершин этого подграфа.

U q = {e1q, e2q,..., eiq,..., e N }, N q = U q – мощность множества вершин подграфа S q. Условимся, что элементы множества U q нумеруются в порядке исчерпания долей U kq, k = 1, m подграфа S q.

В таблице T q клетка Tikq представляет собой «множество смежности»

(МС), более точно это МС является подмножеством Tikq U kq, состоящим из подграфе S q. Если вершина eiq является элементом доли U kq, то согласно этому определению получаем одноэлементное МС Tikq = {eiq }, считая, что всякая вершина всегда «смежна сама с собой». С учетом дольности подграфа S q таблица T q естественным образом разбивается на части Tkq, k = 1,2,..., m, где часть Tkq состоит из всех таких строк, которые соответствуют вершинам одной и той же доли U kq m -дольного подграфа S q. Число строк N kq, составляющих часть Tkq, равно числу вершин в доле U kq : N kq = U kq.

В качестве иллюстративного примера построим таблицу МС для подграфа S 1 = (U 1, R1 ) на рис.2.4, у которого значение индекса q = 1 и вершина e q = e1 = e1. Элементы множества вершин этого подграфа в новой перенумерации индексом i = 1,2,...,6 получают следующие обозначения:

e1 = e11, e2 = e1, e3 = e3, e7 = e1, e10 = e5, e4 = e6. Т.к. число долей в S 1 равно 4, то таблица МС T 1 = Tik1 для подграфа S 1 получает размерность N1 m = (см. таб.2.1).

С учетом определения понятия « m -вершинная клика» рассуждением от противного легко доказываются следующие ниже леммы о необходимых вершинной клике в подграфе S q.

Лемма 2.6 (Условие 1). Если вершина eiq принадлежит какой-либо m вершинной клике, то в i -ой строке таблицы МС T q каждая клетка Tik не является пустым множеством: Tik, k = 1,2,..., m.

Для рассматриваемого иллюстративного примера таб.2.1 в строках i = 4 и i = 5 содержатся клетки с пустыми множествами. Эти строки соответствуют вершинам e7 и e10. Т.о. эти вершины можно исключить из рассмотрения и соответствующие им строки в таблице МС вычеркнуть.

Рассмотрим в данной таблице МС размерности N m пару строк i, j, соответствующих вершинам ei, e j. Условимся, что термин «пересечение МС строк i, ( Tik T jk ), для каждого k = 1,2,..., m. Это пересечение называется непустым, если каждое из составляющих его множеств является непустым, т.е.

Tik T jk, k = 1,2,..., m. С учетом этих терминов, а также разбиения таблицы T q на части Tkq, k = 1, m сформулируем следующее необходимое условие.

Лемма 2.7 (Условие 2). Если вершина eiq принадлежит какой-либо m вершинной клике, то i -я строка таблицы T q имеет непустое пересечение хотя бы с одной строкой из каждой части Tkq, k = 1, m этой таблицы.

Для иллюстрации необходимого условия 2, представленного леммой 2.7, рассмотрим 5-дольный подграф S на рис.2.5. Соответствующая ему таблица МС представлена в виде таб.2.2, в которой каждая клетка Tik не является пустым множеством, т.е. имеет место выполнение необходимого условия 1, представленного леммой 2.6, для каждой вершины данного подграфа S. С учетом представленного разбиения таб.2.2 на части Tk, k = 1,5 рассмотрим пересечения МС строки 8 и строк 2 и 3, составляющих необходимого условия 2: T84 T24 = {e5 } {e6 ) = и T82 T32 = {e } {e3 } =.

Следовательно, вершина e8 не принадлежит никакой 5-вершинной клике в данном 5-дольном подграфе S. Аналогично необходимое условие 2 не выполняется для строки 7 в таб.2.2. Поскольку рассмотренная пара вершин составляет всю 5-ю долю данного подграфа S, то является справедливым утверждение о том, что подграф S на рис.2.5 не содержит m -вершинных клик, откуда следует, что соответствующий ему исходный гиперграф не содержит совершенного сочетания, включающего ребро e1.

Рис.2.5. Подграф S Приведем описание работы этапа q алгоритма 1. Этап q состоит из подэтапов, перенумерованных индексом t = 1,2,..., N q N m 1. На вход подэтапа 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.

Вершины множества U q = {e1q, e2q,..., eiq,..., e N } перенумерованы индексом i так, что существует взаимно однозначное соответствие между номерами вершин из U q и номерами строк таблицы МС T q. При этом для каждого k существует также взаимно однозначное соответствие между номерами вершин в доле U kq и номерами строк части Tkq в таблице T q.

На подэтапе t = 1 в таблице T q выделяется строка i = 2, которая по определению принадлежит части T2q таблицы T q. Для выделенной строки отношению к каждой из последующих частей Tkq, k = 3,4,..., m. Если это условие для строки i = 2 не выполняется по отношению к некоторой из частей Tkq, то работа подэтапа t = 1 завершается вычеркиванием из таблицы T q этой строки, а также удалением всех вхождений вершины e2q в клетки Ti 2, i 2. Наряду с этим в подграфе S q указанная вершина e2q также удаляется вместе с инцидентными ей ребрами. Оставшиеся части таблицы T q и подграфа S q обозначаем соответственно через T1q = Tikq,1, 1 i N q, i 2, 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, и подграф 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, выделенной строки i осуществляется проверка выполнения необходимого условия 2 по отношению к каждой из остальных частей Trq,t, r k таблицы Tt q. Если это условие для строки i = t + 2 не выполняется по отношению к вычеркиванием из таблицы Tt q этой строки, а также удалением всех вхождений вершины etq+ 2 в клетки Trq,t, r k, 1 r m. Наряду с этим в подграфе S tq указанная вершина etq+ 2 также удаляется вместе с инцидентными ей ребрами. Оставшиеся после этого вычеркивания части таблицы Tt q и подграфа S tq обозначаем соответственно через Tt +1 = Tikq,t +1, 1 i N q, k = 1, m нумерацию строк таблицы Tt q.

Работа алгоритма 1 считается результативной, если по завершению подэтапа 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.

Примечание 2.3. Не трудно видеть, что трудоемкость алгоритма ограничена сверху полиномом от размерности подграфа S q. Поэтому представляют интерес такие свойства тупиковой таблицы T q и тупикового существования в подграфе 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.3. Всякая вершина, принадлежащая некоторой m вершинной клике не будет удалена из множеств смежности U q в процессе работы алгоритма 1, в силу чего соответствующая этой вершине строка в таблице МС сохранится до окончания работы алгоритма 1, и т.о. тупиковая таблица МС не будет являться пустой, т.е. T q.

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

Доказательство. Если на подэтапе (t + 1) алгоритма 1 строка i = t + вошла в состав тупиковой таблицы МС 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 определяется трудоемкостью его работы с таблицами 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 некоторых строк.

соответствующих вершин каждая вершина множеств смежности в таблице вычислительной сложности получения тупикового подграфа и тупиковой таблицы справедлива верхняя оценка ( 1q ) O( U q ), а верхняя оценка трудоемкости алгоритма 1 с учетом U = 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).

На рис.2.7 представлен 5-дольный тупиковый подграф S 1. Для него соответствующая тупиковая таблица T 1 представлена таблицей 2.4.

В долях U 51, U 41, U 31 формируется множество клик размерности 3:

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

Например, для подграфа на рис. 2.7 на подэтапе s = 2 клики 1 и пополняются вершиной e * = e2, а клики 3 и 3 пополняются вершиной e3, в заключительном этапе s = 3 каждая из этих клик пополняется одной и той же вершиной e q = e1, образуя множество клик размерности m = 5. Последнее гиперграфе.

результативным, то по завершению этапа q в целом получаем множество K m клик размерности m, каждая из которых однозначно определяет собой некоторое допустимое решение исходной задачи о нахождении множества X = X (G ) всех совершенных сочетаний на l -дольном l -однородном гиперграфе.

По завершению последнего, т.е. L1 -го этапа формируется теоретикоL X = X (G ) задачи.

Оценивая вычислительную сложность алгоритма 2, заметим, что все бесповторно, при этом ребро количество этих клик. Последнее ограничено числом всех совершенных l сочетаний в полном l -дольном l -однородном n -вершинном гиперграфе, 2.6. Алгоритм нахождения множества допустимых решений задачи покрытия l -дольного l -однородного гиперграфа звездами Используем обозначения, введенные в п.2.3 для задачи Z 2l (r ), где r = (r1, r2,..., rn ) является вектором степеней простых звезд в допустимом гиперграфа 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. Рис.2.8. 20-вершинный 4-дольный 4-однородный гиперграф 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) Рис.2.9. Допустимое покрытие звездами x = (V1,V2,V3,V4, E x ), Представленный ниже алгоритм 3 целенаправленного перебора допустимых покрытий x X состоит из четырех этапов 3, 32, 33 и 34.

Суть этапа 3 заключается в полиномиальном сведении задачи покрытия звездами Z 2l (r ) к задаче покрытия совершенными сочетаниями Z 1l. Этап совершенных сочетаний в гиперграфе, на этапе 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 ).

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

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

Полученное множество E по своему определению образует n -вершинный l -дольный l -однородный гиперграф G = (V1,V2,...,Vl, E ) с равномощными долями, где n = n + (rt 1) = n + (m n1 ) = ml. На этом работа этапа заканчивается. Результатом применения этапов 32 и 33 к гиперграфу G гиперграфе G.

В процессе этапа 34 используется новая операция vv совмещения пары вершин v и v в рассматриваемых ребрах. Для определения этой e = (v1, v2,..., vk), которые могут пересекаться или не пересекаться по их вершинам. Предполагая несовпадение совмещения этих вершин вводим в рассмотрение новую вершину v1, которая не является элементом множества (e e). Тогда результатом операции e v1v1 e является пара пересекающихся ребер {(v1, v2,..., v ), (v1, v,..., v)}.

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

Данное выше определение операции совмещения пары вершин, инцидентных паре различных ребер, очевидным образом обобщается на произвольное число r 3 ребер. При этом, если рассматриваемые ребра попарно не пересекаются, то в результате применения к ним операции совмещения вершин получаем простую звезду степени r с центром в новой вершине. На рис. 2.10 показана операция совмещения трех вершин v1, v1, v1, инцидентных тройке различных ребер e, e, e, и образование простой звезды степени 3 с центром в новой вершине v1.

Рис.2.10. Образование простой звезды с центром в вершине v1 в результате операции совмещения трех вершин v1, v1, v x = (V1,V2,...,Vl, E x ), в котором доля V1 согласно построению гиперграфа G разбивается на подмножества V1t = {vtk }, k = 1, rt такие, что все вершины v V1t окрашены в один и тот же цвет t, t = 1, n1. Эти подмножества V1t подмножества 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 в качестве множеств вершин, получаем следующее теоретико-множественное совпадение Фиксируем номер цвета совмещения вершин первой доли vtk V1t, k = 1, rt в ребрах etk E xt. В результате, согласно (2.15), получаем простую звезду степени rt с центром в G = (V1,V2,...,Vl, E ) получаем, что является справедливой следующая Лемма 2.10. Всякое совершенное сочетание x в гиперграфе G однозначно определяет собой допустимое покрытие x гиперграфа G звездами, причем, это покрытие получается в результате применения операции совмещения одноцветных вершин первой доли в ребрах из x.

множество всех его совершенных сочетаний 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. вытекает, что имеет место включение Используя лемму 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}, а вторая и третья доли 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).

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

Рис.2.12. Гиперграф G = (V1,V2,V3, E ), полученный из гиперграфа Далее в результате применения этапов 32 и 33 к гиперграфу G получено представленное на рис. 2.13 (а, б, в, г) множество всех его совершенных сочетаний X (G ) = {x} = {x1, x2, x3, x4 }, которые соответствуют покрытию исходного гиперграфа G звездами.

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

Рис.2.14. Покрытие гиперграфа G звездами x = (V1,V2,V3, E x ), Оценивая вычислительную сложность алгоритма 3, условимся обозначать через 3, 2, 3 совместное выполнение этапов 3, 32 и 33. Пусть 1, 2 (G ) обозначает собой алгоритм нахождения множества X (G ) всех совершенных сочетаний в гиперграфе G. Нетрудно видеть справедливость следующей оценки вычислительной сложности На этапе 34 рассматриваются и сравниваются между собой совершенные сочетания и соответствующие им множества звезд, каждое из которых состоит из m = l -элементных подмножеств вершин. Тогда вычислительная сложность перехода от множества совершенных сочетаний X (G ) к множеству X (G, 3 ) всех покрытий гиперграфа G звездами ограничена сверху величиной O (ml X (G ) ) 2. Отсюда с учетом (2.17) получаем верхнюю оценку трудоемкости алгоритма 3 :

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

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

Вторую группу результатов второй главы представляют три алгоритма. Первый из них предназначен для решения 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, 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), Достоинством метода AHP является то, что он может применяться в тех случаях, когда эксперты или лица, принимающие решения, не могут дать абсолютные оценки альтернатив по критериям и пользуются более слабыми сравнительными измерениями. На нижнем (первом) уровне иерархии AHP специалисты отдела маркетинга и сбыта строительной Компании (эксперты), используя шкалу относительной важности, попарным сравнением расставляют коэффициенты важности для каждого уровня иерархии:

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

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

Строительная Компания предлагает вниманию клиентов продуктовую линейку, состоящую из четырех ассортиментных позиций, называемых проектами H j, j = 1, m, ( m = 4 ):

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

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

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

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

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

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

С помощью экспертов Компании, используя шкалу относительной важности, заполняется таблица 3. Матрица сравнений критериев Компании Отметим, что критерии «доходность строительства данного вида жилья ( K 2 )» и «трудоемкость строительных работ ( K 4 )» имеют для Компании «экономичность проекта ( K1 )» и существенно превосходят критерий «время строительства ( K 3 )».

вычислить собственный вектор матрицы, извлекая корень n -й степени ( n – размерность матрицы сравнений) из произведений элементов каждой строки, а затем путем нормирования элементов собственного вектора матрицы определяются коэффициенты важности или веса критериев wi, i = 1, n, Таким же способом рассчитывается относительная важность v ji Результаты этих расчетов представлены в таблицах 3.3 – 3.6.

Относительная важность проектов по отдельным критериям • По критерию K1 «Экономичность проекта»

• По критерию K 2 «Доходность строительства данного вида жилья»

• По критерию K 3 «Время строительства»

• По критерию K 4 «Трудоемкость или качество строительных работ»

Далее на основании результатов, представленных в таблицах 3.2 – 3.6, осуществляется определение качества каждой альтернативы. Для этого, используя метод аналитической иерархии, необходимо произвести синтез осуществляются по формуле где 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,261 (3.2) P3 = 0,151*0,08 + 0,391*0,06 + 0,067*0,10 + 0,391*0,56 = 0, 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 )»

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

превосходит критерий «инфраструктура C 4 » и умеренно превосходит критерии «экологическая безопасность C 2 » и «качество строительных работ C3 ». Критерии «экологическая безопасность» и «качество строительных работ» имеют равную важность. Критерий «инфраструктура» существенно превосходит критерий «экологическая безопасность» и значительно – соотношения представлены в таблице 3.7. При этом расчет компонент собственного вектора и коэффициентов важности критериев, т.е. весов wi, осуществляется аналогично описанному выше расчету данных таблиц 3.3 – 3.6.

Поскольку строительная Компания может строить любой из четырех видов жилья на любом из четырех выделенных ей участков, то потребителям предлагаются следующие проекты L j, j = 1,16 : j = 1 – комфортабельная квартира в многоэтажном кирпичном доме в центре города, комфортабельная квартира в многоэтажном кирпичном доме в пригороде, j = 3 – комфортабельная квартира в многоэтажном кирпичном доме в первом городском районе, кирпичном доме во втором городском районе, j = 5 – комфортабельная квартира в многоэтажном панельном доме в центре города, комфортабельная квартира в многоэтажном панельном доме в пригороде, j = 7 – комфортабельная квартира в многоэтажном панельном доме в первом городском районе, панельном доме во втором городском районе, j = 9 – коттедж в центре города, j = 10 – коттедж в пригороде, j = 11 – коттедж в первом городском районе, j = 12 – коттедж во втором городском районе, j = 13 – коттеджная секция в центре города, j = 14 – коттеджная секция в пригороде, j = 15 – коттеджная секция в первом городском районе, j = 16 – коттеджная секция во втором городском районе. По аналогии с формированием предыдущих таблиц вычисляем элементы таблиц 3.8 – 3.11, отражающих относительную важность проектов L j по потребительским критериям Ci.

Относительная важность проектов по потребительским критериям • По критерию С 4 «Инфраструктура жилья и жилищного комплекса»

Далее с учетом данных таблиц 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, 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 8 = 0,499*0,03 + 0,098*0,01 + 0,09*0,01 + 0,313*0,04 = 0, S 9 = 0,499*0,14 + 0,098*0,04 + 0,09*0,18 + 0,313*0,14 = 0, 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, 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, критериями Fi, i = 1,2 : F1 – профессионализм; F2 – производительность труда.

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

Матрица сравнений критериев уровня качества выполнения работы Fi Относительная оценка бригад по критериям качества выполнения С учетом данных таблиц 3.12 – 3.14 производится расчет показателей качества работы бригад Q j, j = 1,4 по формуле (3.1):

Q1 = 0,75*0,56 + 0,25*0,13 = 0, Q3 = 0,75*0,12 + 0,25*0,37 = 0, Q4 = 0,75*0,06 + 0,25*0,13 = 0,078.

На основании численных значений (3.2) и (3.4) определим показатель Компанией в случае, когда этот 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-ой бригадой; (3.5) R33 = 0,261*0,183 = 0,048 – коттедж строится 3-ей бригадой;

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

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

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

Таким образом, в завершение моделирования на нижнем уровне получены численные значения для следующих входных данных верхнего уровня моделирования:

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

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

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

строительство объекта 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 = (V, E x ), E x E на гиперграфе G = (V1,V2,V3, E ).

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

F ( x) = ( F1 ( x), F2 ( x)), состоящей из критериев вида MAXSUM и MAXMIN :

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

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

Для представленной задачи множество ребер E = {e} гиперграфа G = (V1,V2,V3, E ) и веса ребер w (e), = 1,2 с учетом (3.3) и (3.5) заданы С помощью алгоритмов 1 и 2, представленных в главе 2, находим G = (V1,V2,V3, E ). МДР X = {x} и значения критериев F1 ( x) и F2 ( x) для каждого решения отражены в таблице 3.16.

Используя таблицу 3.16, находим решение представленной задачи.

Решением задачи является ПМ и ПМА X = X 0 = {x3, x7 }.

На рис.3.1 представлено одно из альтернативных решений x3, которое отражает следующую стратегию ведения строительства: 1-я бригада строит многоэтажный кирпичный дом во втором городском районе, 2-я бригада строит панельный дом в центре города, 3-я бригада в первом городском районе строит коттеджные секции, 4-я бригада назначается на строительство коттеджа в пригороде. Другое альтернативное решение x7 соответствует такой стратегии ведения строительства Компанией, когда 1-я бригада строит многоэтажный панельный дом в центре города, 2-я бригада поставлена на строительство кирпичного многоэтажного дома во втором городском районе, 3-я бригада в первом городском районе строит коттеджные секции, а 4-я бригада назначена на строительство коттеджа в пригороде. Решение x представлено на рис.3.2.

Рис.3.1. Одно из альтернативных решений задачи x Рис.3.2. Одно из альтернативных решений задачи x 3.3. Интервальные модели и многокритериальность При оптимизации систем управления в условиях неопределенности очень часто приходится ориентироваться на самое неблагоприятное (экстремальное) сочетание факторов неопределенности и использовать понятие гарантированного результата, т.е. возникает необходимость обеспечить расчет и оптимизацию режима работы, который гарантированно будет лежать в области допустимых значений [39]. В этом случае наиболее перспективным способом адекватного отражения исследуемого объекта является построение интервальной модели [12, 40, 94].

Подобного рода экстремальные задачи исследовались на графах при проектирования электронной техники [13, 17], транспортных сетей [19] и др.

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

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

3.3.1. Общая постановка интервальных оптимизационных задач на замкнутый отрезок вещественной прямой 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 b или a2 b2, причем хотя бы одно из этих неравенств является строгим.

Пересечение A B интервалов A и B пусто, если a2 b1 или b2 < a1, в противном случае произведения интервалов A = [a1, a2 ] и B = [b1, 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

Согласно определению операции сложения интервалов [3] получим значение ИЦФ котором значение ИЦФ (3.6) – (3.7) достигает максимума.

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

В связи с этим для определения подмножества решений необходимо ввести отношения предпочтения, эквивалентности и несравнимости [12, 35].

Определение 3.1. Решение x1 предпочтительнее решения x2 или, 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. Паретовское множество состоит из паретовских оптимумов, которые в свою очередь определяются следующим образом.

Определение 3.4. Решение ~ X называется паретооптимальным для задачи (3.6), если не существует x X такого, что x f ~.

Таким образом, X состоит из неразличимых решений.

рассматривается как ПМ X, так и ПМА X 0 [27].

3.3.2. Сведение интервальной задачи к 2-критериальной Сформулированная выше интервальная задача (3.6) сводится к задаче многокритериальной оптимизации с тем же множеством допустимых решений X и векторной целевой функцией ВЦФ вида где Определение 3.5. Решение ~ X называется ПО для задачи с ВЦФ (3.8) – (3.10), если не существует такого x * X, что F ( x * ) F ( ~ ), = 1,2, при этом хотя бы одно неравенство является строгим.

При исследовании задачи с ВЦФ (3.8) – (3.10) будем учитывать справедливость следующих утверждений.

Лемма 3.1. Пусть на множестве допустимых решений X = {x} задачи векторной оптимизации с максимизируемыми критериями ВЦФ (3.8) – (3.10) порождает ПМ X, а ВЦФ где 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, так чтобы выполнялось неравенство изменится. Пусть x X – некоторое допустимое решение, для которого критерию (3.7) остается прежним а значение целевой функции по второму критерию (3.7) будет иметь вид Величина 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, при исследовании ПМ относительно 2-критериальной задачи с весовыми критериями вида (3.9) – (3.11).

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 :

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

Таким образом, интервальная задача с критерием (3.6) называется разрешимой с помощью АЛСК, если ~ X найдется вектор > 0, удовлетворяющий равенству Однако, как было отмечено выше, АЛСК не всегда обеспечивают получение всех ПО ~ X [27, 45, 74].

Интервальная задача (3.6) неразрешима с помощью АЛСК, если существует индивидуальная задача, для которой выполняется условие:

которое называется условием неразрешимости. Иными словами, если ПМ X хотя бы одной индивидуальной задачи о совершенном сочетании на 3дольном 3-однородном гиперграфе содержит такой элемент x *, на котором ни при каком 2 не достигает максимума значение свертки (3.14), то массовой интервальной задачи о совершенном сочетании на 3-дольном 3однородном гиперграфе.

Теорема 3.2. Для всякого 3-дольного гиперграфа G интервальная задача о совершенном сочетании с критериями вида MAXSUM неразрешима с помощью АЛСК.

Доказательство. Следуя подходу, предложенному в [95], в качестве доказательства приведем пример, показывающий для индивидуальной задачи существование такого паретооптимального решения, которое невозможно получить ни при какой свертке критериев.

Рассмотрим такую индивидуальную задачу о совершенном сочетании на 6-вершинном 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-однородный гиперграф X = X (G ) = {x1, x2, x3 }, где x1 = {e1, e2 }, x2 = {e3, e4 } и x3 = {e5, e6 }. Допустимые решения и веса ребер представлены на рис. 3.4, 3.5, 3.6.

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

гиперграфе G МДР X = X (G ) состоит из трех допустимых решений предпочтения, несравнимости и эквивалентности, определяем, что 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) = w ( x). Для обоснования этого утверждения покажем, что для решения x2 X 0 выполняется условие неразрешимости (3.15):

Подставим значения ИЦФ (3.6) – (3.7) w1 ( xk ) и w2 ( xk ), k = 1,3 в последнее неравенство и получим выражение 25 + 70(1 ) < max{20 + 100(1 ),45 + 60(1 )} или, что то же самое, или иначе Чтобы убедиться в справедливости неравенства (3.16) построим на f 3 ( ) = 60 15 (см. рис. 3.7).

Рис.3.7. Графики функций f k ( ), k = 1,3, [0,1] Из рис.3.7 видно, что функции f1 ( ) и f 3 ( ) образуют паретовскую вытекает, что рассмотренная выше индивидуальная задача о совершенном сочетании на 3-дольном 3-однородном гиперграфе неразличима с помощью АЛСК, т.к. никакая линейная свертка ее критериев не достигает максимума на элементе x2.

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

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

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

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

ЗАКЛЮЧЕНИЕ

В ходе проделанной исследовательской работы получены следующие основные результаты:

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

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

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

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

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

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

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

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

ЛИТЕРАТУРА

1. Абрамович Ф.П., Вагенкнехт М.А., Хургин Я.И. Решение нечетких систем линейных алгебраических уравнений LR-типа. – В сб.: Методы и системы принятия решений. Рига: РПИ, 1987, с.35 -47.

2. Айзерман М.А., Алексеров Ф.Т. Выбор вариантов. Основы теории.

М.: Наука, ГРФМЛ, 1990.-236 с.

3. Алефельд Г., Хельцбергер Ю. Введение в интервальные вычисления.

М.: Мир, 1987. - 542с.

4. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях: Монография. Тюмень: Издательство Тюменского государственного университета, 2000. 352с.

5. Алтунин А.Е., Чуклеев С.Н., Семухин М.В., Крел Л.Д. Методическое руководство по технологическим расчетам сложных систем газодобычи при неточных параметрах. Тюмень, 1984, 48 с.

6. Аоки М. Введение в методы оптимизации. М.: Наука, 1977, 344 с.

7. Безбородов В.Г., Жаков А.М. Суда космической службы. – Л.:

Судостроение, 1980, с. 8. Берж К. Теория графов и ее применения. М.: Изд. иностр. лит-ры, 1962.-320с.

9. Беспалько В. П. Педагогика и прогрессивные технологии обучения.

М.:Школа, 1995. - 255с.

10. Бэстенс Д.-Э., Ван Ден Берг В.-М., Вуд Д. Нейронные сети и финансовые рынки. – М.: ТВП Научное издательство, 1998.

11. Волконский В.А., Еганян Г.К., Поманский А.Б. О множестве эффективных точек в линейных многокритериальных задачах //Сиб. Матем.

Журнал. 1983. 24-№2.-С.9- неопределенности. М.: Наука, 1989.-420с.

автоматизированного проектирования. – М.: Высшая школа, 1989. – 184 с.

14. Гермейер Ю.Б. Введение в теорию исследования операций. М.:

Наука, ГРФМЛ, 1971.-383 с.

15. Глушков В.М. О системной оптимизации//Кибернетика. - 1980. -№5.С.89-90.

16. Гудмен И. Нечеткие множества как классы эквивалентности случайных множеств. В сб.: Нечеткие множества и теория возможностей.

М: Радио и связь, 1986, с.241 - 264.

совокупности показателей качества. – М.: Сов. радио. 1975. – 368 с.

18. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.-416 с.

неопределенности исходной информации// Труды семинара по интервальной математике, Саратов, 29 – 31 мая, 1990: Саратов, 1990. – С. 10 – 16.

20. Джуэлл Л. Индустриально-организационная психология. СПб.:

Питер,2001.-720с.

21. Дресслер Г. Управление персоналом. М.: Бином, 1997. – 418 с.

22. Евдокимов М.В., Медницкий В.Г., Сигал И.Х. Бикритериальная задача переоборудования производства. //Известия РАН. Теория и системы управления. -№ 5. - 2001. С. 90-96.

23. Ежов А.А., Шумский С.А. Нейрокомпьютинг и его применение в экономике и бизнесе. – М.: ЭАИ МИФИ, 1998.

24. Емеличев В.А., Кравцов М.К., Янушкевич О.Я. Разрешимость векторной траекторной задачи на «узкие места» с помощью алгоритма линейной свертки // Доклады Академии наук Белоруси. 1996. 40-№4. С.29Емеличев В.А., Перепелица В.А. К вычислительной сложности дискретных многокритериальных задач // Изв. АН СССР. Техн.кибернетика.

1988. №1. С.78 - 26. Емеличев В.А., Перепелица В.А. Полные задачи многокритериальной дискретной оптимизации//Сообщения АН ГССР. – 1988. – Т.131, №3. – С. – 504.

многокритериальных задач // Дискретная математика. - 1994. - Т.6, №1.-С.ЗЕмеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.

Лекции по теории графов. М.: Наука, 1990. 384с.

29. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах// Журн. вычис.

математики и мат.физики. – 1989. – Т.29., №2. – С.171 – 183.

30. Жак С.В. Математические модели менеджмента и маркетинга. – Ростов-на-Дону: ЛаПО, 1997. – 320 с.

31. Заде Л.А. Понятие, лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976, 165с.

32. Зыков А.А. Гиперграфы//Успехи Матем. наук. - 1974. -Т. 29. вып.6.-С.

89-154.

33. Ивченко Б.П., Мартыщенко Л.А., Монастырский М.Л. Теоретические основы информационно-статистического анализа сложных систем. – СПб.:

Питер, 1997.

34. Ильин Н.И., Лукманова И.Г. и др. Управление проектами. – СПб.:

«Два – ТрИ», 1996. – 610 с.

35. Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального анализа.-Новосибирск: Наука, Сибирское отделение, 1986. - 590с.

36. Кандель А., Байатт У.Дж. Нечеткие множества, нечеткая алгебра, нечеткая статистика. Труды американского общества инженеров радиоэлектронников, т.66, 1978, с.37- 37. Карповский Е.Я., Чижов С.А. Оценка показателей качества программных средств с использованием лингвистических переменных.

Управляющие системы и машины, №2, 1987, с. 17 - 38. Кейн Л.А. Искусственный интеллект в обрабатывающих отраслях промышленности. Нефть, газ и нефтехимия за рубежом, №9, 1986,с. 117- 39. Кейн В.М. Оптимизация систем управления по минимаксному критерию. – М.: Наука, 1985, 248 с.

40. Ким-Гю-Пхир. Оптимальное распределение ресурса в условиях интервальной неопределенности// Международная конференция по интервальным и стохастическим методам в науке и технике (Интервал – 92):

Сборник трудов – Москва, 1992. – Т.I. С.60 – 63.

41. Ковалев В.И., Бондарева М.К., Омельченко Г.Г. и др. «Исследование путей и способов повышения эффективности управления орбитальными изменяющимся условиям космической обстановки»// Отчет о НИР «Перспектива – 31». – М.: МО РФ, в/ч 32103, 2001 г. 52 с.

42. Ковалев В.И., Бондарева М.К., Омельченко Г.Г. и др. «Исследование вопросов создания системы оценки космической обстановки для учета изменяющихся условий управления космическими аппаратами»// Отчет о НИР «Голкипер». – М.: МО РФ, в/ч 32103, 2000 г. 112 с.

43. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер//Успехи матем. наук. - 1985. - Т.40, №1 (241).-С. 107Кофман А. Введение в теорию нечетких множеств. М: Радио и связь, 1982,432 с.

45. Кравцов М.К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев //Дискретная математика. - 1996.8 - №2. - С.89 - 46. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.-432с.

неопределенности. М.: Наука, 1977, 392 с.

газопроводов. М: Недра,1979.

49. Кучин Б.Л., Алтунин А.Е. Управление системой газоснабжения в осложненных условиях эксплуатации. – М.: Недра, 1987, 209 с.

50. Ларичев О.И. Наука и искусство принятия решения. - М.: Наука, 1979.с.

51. Лебедев В.В. Математическое моделирование социальноэкономических процессов. – М.: Изограф, 1997.

52. Лизинский В.М. Диагностико-аналитические процедуры и активноигровые формы в управлении. - М.: Новая школа, 1996. - 300с.

53. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии – М.: Мир, 1998. – 653 с.

54. Машарова Т.В. Педагогические теории, системы и технологии обучения. - Киров: ВГПУ, 1997. - 370с.