Книги, научные публикации
Pages: | 1 | 2 | МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КАРАЧАЕВО-ЧЕРКЕССКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ На правах рукописи Темирова Лилия Гумаровна ДВУХУРОВНЕВОЕ МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ ...
-- [ Страница 2 ] --Исследуя какую-либо задачу, в качестве основной проблемы рассматривается построение достаточно эффективного алгоритма нахождения требуемого МА этой задачи. Отметим, что в классических оптимизационных (т.е. однокритериальных) задачах с четкими числовыми данными ПМА образуется одним оптимальным решением x 0 X. 3.2. Математическая постановка векторной задачи покрытия графа 4- циклами (паросочетаниями, звездами) Для общей постановки исследуемых задач в условиях многокритериальности введем ряд терминов и обозначений. Пусть G = (V, E ) - n вершинный граф [22], в котором каждому ребру e E приписаны N весов, т.е. чисел w (e ) > 0, v = 1, N. Циклом называется замкнутая цепь, у которой начало и конец совмещены в одной и той же вершине. Длиной цикла l называется число ребер в цикле. Цикл длины l будем называть l - циклом, 2 l n. Паросочетанием называется произвольное подмножество попарно непересекающихся ребер графа. Звездой называется связный двудольный граф в первой доле, которого содержится одна вершина, смежная с множеством вершин второй доли. Допустимым покрытием графа G будет являться всякий его остовный подграф x = (V, E x ), E x E, у которого каждая компонента связности для задачи покрытия графа 4-циклами представляет собой 4цикл;
для задачи покрытия графа паросочетаниями - ребро;
в задачах покрытия графа звездами каждая компонента связности в x представляет собой звезду с определенным числом вершин. В области дискретной оптимизации допустимое покрытие принято называть термином допустимое решение. Множество всех допустимых решений (МДР) обозначим через X = X (G ) = {x}.
Качество или эффективность допустимого решения x X при N 2 определяется векторной целевой функцией (ВЦФ) F ( x ) = (F1 ( x ), F2 ( x ),..., FN ( x )), которая в общем случае включает в себя критерии вида MAXSUM F ( x ) = eE x (3.1) w (e) max, v = 1, N (3.2) или критерии вида MAXMIN F ( x ) = min w (e ) max, v = 1, N.
eE x (3.3) ~ Эта ВЦФ определяет в МДР X паретовское множество (ПМ) X, состоящее из всех паретовских оптимумов (ПО). Искомым математическим решением векторной задачи чаще всего является полное множество альтернатив (ПМА) X 0, из которого осуществляется выбор наиболее целесообразной альтернативы (так называемый компромиссный или интегральный оптимум). Сформулированные выше математические постановки проблем нахождения полного множества альтернатив условимся называть терминами зада ча покрытия графа 4-циклами, задача покрытия графа паросочетаниями и задача покрытия графа звездами, уточняя при этом состав критериев ВЦФ (3.1)-(3.3). Эти же задачи рассматриваются в настоящей работе в оптимизационной (т.е. однокритериальной) постановке в случае, когда в исходных графах веса их ребер представляют собой нечеткие множества [2,44] или интервалы [1,6,14,90]. Именно на этих задачах мы покажем, что ни одно из известных определений такого понятия как суммирование двух нечетких множеств не является адекватным содержательному смыслу задач землепользования. По этой причине является объективно необходимым осуществить критический анализ известных определений операции суммирования нечетких весов и, вместе с тем, представить и обосновать такое определение операции суммирования нечетких множеств, которое было бы вполне адекватным содержанию задач землепользования, рассматриваемых в настоящей работе.
3.3. Анализ арифметических операций и отношения предпочтения для задач с нечеткими данными Нечеткое множество (fuzzy set) [2,44,92] - это математическая модель численного представления лингвистических переменных, т.е. свойств (объектов) с нечеткими или, иначе, размытыми границами. В основе понятия нечеткое множество лежит представление о том, что составляющие данное множество элементы, обладающие общим свойством, могут обладать этим свойством в различной степени и, следовательно, принадлежать данному множеству с различной степенью. Введем основные термины и определения теории нечетких множеств (НМ). Лингвистической переменной называется переменная, значениями которой могут быть слова или словосочетания некоторого естественного или искусственного языка, которые описываются нечеткими значениями.
Терм-множеством называется множество всех возможных значений лингвистической переменной. При этом сами элементы этого множества называются термами. Нечетким множеством A некоторого универсального множества X называется совокупность пар вида {(x, (x ))}, где (x ) A A - степень принадлеж ности элемента x X множеству A. Понятия множества и подмножества в их классическом определении будем называть терминами четкое множество и четкое подмножество Степень принадлежности - это число из диапазона [0,1], являющееся некоторой элементарной характеристикой явления (степень загрязненности участка, степень эффективности режима и т.д.). Чем выше степень принадлежности, тем в большей мере элемент универсального множества соответствует свойствам нечеткого множества. Функцией принадлежности (ФП) называется функция, которая позволяет численно отразить степень принадлежности произвольного элемента универсального множества [2,44] определенному НМ. Носителем нечеткого подмножества A называется четкое подмножество из X, на котором A ( x ) > 0. Перейдем к анализу известных операций суммирования нечетких множеств, для которых к настоящему времени существуют три аксиоматически определенных метода [67]:
-алгебраический A + B, A B, B W : A+B (w) = A (w) + B (w) A (w) B (w) ;
-граничный A B : A B (w) = ( A (w) + B (w)) 1, для wW ;
-драстический AB : где AB (w) = B (w), если A (w) = 0, AB (w) = A (w), если B (w) = 0 wW и AB (w) = 1 в других случаях. Каждый из этих методов, что принципиально важно, представляет собой некий вариант теоретикомножественного суммирования, т.е. сумма двух НМ W ' и W '' есть либо теоретико-множественное объединение их терм-множеств, либо некоторая его модификация. Можно утверждать, что представленные три метода суммирова ния НМ принципиально не соответствуют содержательному смыслу суммирования eE x нечетких весов (НВ) w(e ) в целевой функции w(e) еxtr, extr {min, max} задач землепользования, что вынуждает предла гать и обосновывать новое определение операции суммирования НВ ребер в допустимых решениях x X задач, сформулированных в п.3.2. В большинстве литературных источников операция суммирования рассматривается как теоретико-множественное объединение. В [2] удалось избежать подмены арифметического сложения следующим видом суммирования. Следуя [2], рассмотрим два НВ w(e) и w(e), для которых определены соответственно два множества-носителя W = {w1, w,..., wl } и W = {w1, w,..., wl }. 2 1 Для элементов этих множеств априори известны дискретные функции принадлежности = (w) и = (w), 0 (w), (w) 1. Предполагая, что множества W и W упорядочены по возрастанию, получаем множествоноситель для суммы носителей НВ W +W, представляющее собой такое упорядоченное по возрастанию множество W = {w1, w2,..., wl }, в котором w1 = w1 + w1, w1 + w2,..., wl = wl1 + wl. Определение функции принадлежности = (w) элементов w в сумме W представим на примере одного элемента w0 W. В процессе суммирования представителей носителей НВ W и W элемент w 0 может получаться в результате сложения элементов определенных q пар:
w1 + w1, s s w2 + w2,..., wq + wq, s1 < s <... < s q, s1 < s <... < s. Тогда степень принадлежности s s s s 2 2 q элемента w 0 в W определяется согласно следующего выражения [6] (w 0 ) = ( w+ w )= w sup {min( (w), (w))}, W W (3.4) принадлежности:
W удовлетворяющего общепринятому свойству меры 0 1. Таким образом, множество W и определенная для его элементов функция принадлежности W (wr ), r = 1,2,..., l представляют собой НВ, являющийся нечетким множеством.
В качестве иллюстративного примера неадекватности такого (отметим, уже четвертого по счету) способа суммирования содержанию рассматриваемой задачи землепользования рассмотрим два конкретных НВ, полученных на выходе прогнозной модели [61], которая была применена для временного ряда (ВР) урожайности озимой пшеницы по Волгоградской области:
w(e) = w(e) = {(10;
0,5), (25;
0,4 ), (40;
0,1)}.
(3.5) В выражении (3.5) веса w(e ) и w(e ) представляют собой ожидаемые урожайности, т.е. ожидаемые урожаи, которые могут быть получены с единичной площади 1га на двух различных полях. Здесь ожидается: низкий урожай H = 10ц / га с функцией принадлежности (ФП) Н = 0,5 ;
средний урожай С = 25ц / га с ФП С = 0,4 и высокий урожай В = 40ц / га с ФП В = 0,1. Тогда содержательно непротиворечивым суммированием этих двух одинаковых урожайностей является выражение w(e) + w(e) = {(20;
0,5), (50;
0,4 ), (80;
0,1)}.
(3.6) с ФП Содержательный смысл выражения (3.6) состоит в том, что на площади 2 га ожидается следующий урожай:
H = 20ц / 2 га Н = 0,5, С = 50ц / 2 га с ФП С = 0,4, В = 80ц / 2 га с ФП В = 0,1.
Вычислим теперь сумму w(e ) + w(e ), используя формулу (3.4):
w(e) + w(e) = {(20;
0,5), (35;
0,4 ), (50;
0,4 ), (65;
0,1), (80;
0,1)} (3.7) Сравнивая правые части выражений (3.6) и (3.7) видим, что каждый из них представляет собой НМ, причем НМ (3.6) является собственным подмножеством нечеткого множества (3.7). Иными словами, в нечетком множестве (3.7) по сравнению с (3.6) появились два новых элемента: (35;
0,4), (65;
0,1), (3.8) которые по сути дела привносят собой ненужную, более того, отвлекающую информацию о результатах выполнения операции сложения. Действительно, представленные в (3.8) урожайности 35ц / 2 га с функцией принадлежности 40% и 65ц / 2 га с ФП 10% просто непредусмотрены содержательным смыс лом рассматриваемой ситуации (о суммарном выходе продукции с пахотных угодий площадью 2 га ). Таким образом, представленные выше известные определения операции суммирования нечетких множеств [2,24,44,67] не позволяют адекватно отразить операцию суммирования нечетких весов в рассматриваемой математической модели. Применительно к рассматриваемой задаче землепользования представим новое более адекватное реальной ситуации определение операции суммирования двух нечетких множеств.
3.4. Новые определения операций суммирования и сравнения, адекватных математической модели задачи землепользования с нечеткими данными 3.4.1. Математическая постановка задачи Для математической постановки задачи введем следующие обозначения: k = 1,2,..., m - индекс, которым занумерованы культуры, выращиваемые в хозяйстве;
i = 1,2,..., n - индекс, которым занумерованы поля, засеваемые этими культурами;
ck - стоимость единицы k -ой культуры;
si - площадь i -го поля;
d k - директивное ограничение на минимальный объем выхода культуры k ;
G = (V1, V2, E ) двудольный граф, в котором вершины первой доли V1 = {v1,..., vk,..., vm } перенумерованы индексами культур k = 1,2,..., m, а вершины второй доли V2 = {v1,..., vi,..., v n }перенумерованы индексами полей i = 1,2,..., n ;
E = {e}- множество ребер графа G, которое содержит ребро e = (vk, vi ) тогда и только тогда, когда в прогнозируемом году разрешается засевать культуру k на пахотное угодие поля i. Каждому ребру e = (vk, vi ) E, приписан вес W k,i, k k k представляющий собой НМ W k,i = {(W Hk,i ;
H ), (WCk,i ;
C ), (W Bk,i ;
B )}, где элементk k k носитель [10] W Hk,i = c k s i U H,i ( WCk,i = c k s i U C,i, W Bk,i = c k s i U B,i ) содержатель но означает ожидаемый объем выхода продукции в рублях культуры k с поля i в случае низкого (среднего, высокого) прогнозируемого урожая (U (U k,i H k,i C k, U B,i. В общем случае единицей измерения каждого веса Wk,i, )) {H, C, B} могут быть рубли, протеиновые единицы и др.
Теоретико-графовая постановка сформулированной выше задачи представляет собой задачу покрытия 2-дольного графа звездами [53]. Допустимое решение на 2-дольном графе G = (V1, V 2, E ) этой задачи представляет собой такой его остовный подграф x = (V,V, E ), E x E, в котором каждая компо1 x нента связности представляет собой звезду x k = ({v k },V2k, E xk ), k V1, V2k V2, E xk E x с центром в определенной вершине vk из первой доли V1 и множеством V2k висячих вершин из второй доли V2 ;
звезды x k, k = 1,2,..., m, являющиеся по определению 2-дольными графами, определяют собой разбиение вершин второй доли и множества ребер E x в допустимом решении:
1 V21 V22... V2m = V2, E x E x2... E xm = E x. На множестве допустимых решений (МДР) графа G определена целевая функция (ЦФ) F (x ) max следующим образом. Для каждой пары (v k, vi ), vk V1, vi V2 определен объем W k,i ожидаемого урожая культуры k на поле i, т.е. ребру e = (v k, vi ) E при писан вес w(e ) = W k,i.
m Допустимым является всякое такое решение x = (V1,V2, E x ), E x = U E xk, для которого выполняются все неравенства следуюk = щей системы:
k eE x w(e) d k, k = 1, m ;
(3.9) X = X (G ) = {x} - множество всех допустимых решений на графе G. Если целевой функцией (ЦФ) F ( x ) является экономический эффект, то она определяется на МДР X следующим образом:
F ( x ) = c k w(e ) = с k k k =1 eE x m m k = k eE x w(e) max (3.10) Задача состоит в том, чтобы найти оптимальное, т.е. максимизирующее значение ЦФ (3.10) допустимое решение. Точнее, требуется построить и обосновать достаточно эффективный алгоритм нахождения указанного опти мума. При этом с учетом проведенного в п.3.3 анализа возникает проблема, состоящая в том, чтобы операцию суммирования двух НВ адекватно определить с учетом содержания рассматриваемой задачи землепользования.
3.4.2. Новая операция суммирования (+) нечетких весов Суть содержательных особенностей рассматриваемой задачи землепользования требует такого определения операции суммирования (+) нечетких весов, которая удовлетворяет следующим условиям: 10. В данном 2-дольном графе G = (V1, V2, E ) множество ребер E разбито на подмножества E k, k = 1, m, m = V1, где E k = {eik } состоит из всех таких ребер eik = (v k, v i ), каждое из которых соединяет вершину v k V1, соответствующую культуре k, с вершиной vi V2, которая соответствует полю i. Каждому ребру eik E приписан нечеткий вес w eik = W k,i, который для каждого k = 1, m и каж () дого i = 1, n имеет одну и ту же структуру, соответствующую принятому терммножеству W 0, т.е., если W 0 = {} = {H, C, B}, то k k w eik = w,i ;
w,i : W ( ) {( ( )) }e k i E.
(3.11) 20. Пусть для каждого фиксированного k {1,2,..., m} является одинакоk k вым для всех ребер eik E k значение функции принадлежности (w, i ) = , i = 1, n, W 0. Если конкретное допустимое решение x X (G ) состоит из звезд z k = v k, E k, v k V1, k = 1, m, то НВ w z k ( ) () одной звезды z k, представляющий сумму НВ ребер этой звезды, определяется выражением:
k w z k = (+) w(e ) = w z k ;
: W 0, k eE x () {( ( ) ) } (3.12) где значение w (z k ) элементов-носителей определяется скалярным суммированием НВ ребер рассматриваемой звезды w z k = ( ) w (e), W k eE x, k = 1, m, (3.13) причем, терм-множество W 0 является одинаковым для всех звезд, хотя в общем случае не обязательно должно иметь вид W 0 = {H, C, B}. Иными словами, НВ звезды имеет ту же структуру, что и НВ ребра. Рассмотрим две звезды z1 = z k и z 2 = z k, для которых вычислены их НВ 1 согласно (3.12). Тогда операция суммирования (+) этих НВ определяется выражением w(z1 ) (+ ) w( z 2 ) = {((w (z ) + w (z ));
(w (z ) + w (z ))) : W }, 1 2 1 0 (3.14) в котором суммирование элементов-носителей (w (z1 ) + w (z x 2 )) является скалярным, а значение функции принадлежности вычисляется согласно правила центра тяжести, используемого в операции дефазификации [24]:
(w ( z1 ) (+ ) w ( z 2 )) = L ( z1, z 2 ), N ( z1, z 2 ) N ( z1, z 2 ) = w ( z1 ) + w ( z 2 ), (3.15) W 0.
где L (z1, z 2 ) = w (z1 ) (z1 ) + w (z 2 ) (z 2 ), (+) представляется следующим образом:
В этих обозначениях определенное выражениями (3.14)-(3.15) суммирование L (z, z ) w( z1 ) (+ ) w( z 2 ) = N ( z1, z 2 ) ;
1 2 : W 0. N ( z1, z 2 ) Примечание 3.1. Определенная согласно (3.14) и (3.15) операция сум мирования (+) в случае одинаковых значений функций принадлежности (z1 ), ( z 2 ) полностью совпадает с операцией скалярного суммирования (3.12), относящейся к суммированию НВ ребер одной и той же звезды. Рассмотрим задачу покрытия двудольного графа G = (V1, V2, E ) звездами, где множество ребер E разбивается на подмножества E k ребер, инцидентных центрам звезд v k V1, k = 1, m. При определении ЦФ (3.10) на допустимых решениях x = (V1, V2, E x ) X (G ) множество ребер E x представляется в виде подмножеств E xk, состоящих соответственно из ребер звезд z k = z k (x ), k = 1,2,..., m. В ЦФ (3.10) суммируются НВ w(e ), которые в случае принадлежности ребра k k e E xk имеют вид w(e ) = w (e ), w (e ) : W 0. Пусть для всякого фиксирован { ( ) } k фиксированного k {1,2,..., m} значение (w ) одинаковы для всех ребер e E k, k E k E и равны числу , т.е. k k w(e ) = w (e ), : W 0, e E k.
{( ) Введем m обозначения:
k N ( x ) = w } (E ) = w (e) ;
k x k k eE x (3.16) k k Lk ( x ) = N ( x ) ;
k N (x ) = c k N (x ), k = L ( x ) = c k Lk ( x ). В этих обозначениях использование в k = m ЦФ (3.10) операции суммирования (+), определяемой согласно (3.14), (3.15), приводит с учетом (3.16) к следующему представлению значения этой ЦФ в виде НВ:
F (x ) = ck k =1 m m k eE x {(w (e), ) : W } = k k k k = N ( x ), : W 0 = ( N ( x ) ;
(x )) : W 0 k = {( ) }{ }, (3.17) где (x ) = L ( x ). N (x ) Следует отметить, что НВ, представляющий значение ЦФ (3.10), также имеет ту же структуру, что и НВ ребра или звезды. В качестве иллюстративного примера рассмотрим задачу покрытия 2дольного 8-вершинного графа G = (V1, V 2, E ), V1 = {v k }, v k {v, v } (рис.3.1) G e v V e е е е V е е v е Рисунок 3.1. 8-вершинный 2-дольный граф G = (V1,V2, E ), V1 = {v k }, v k {v, v} двумя звездами z1 = {e1, e 2,..., e r,}, z1 = {e1, e 2,..., e }, r + r = 6, образующими доr пустимое решение x1 = (V1, V2, E x ) X (G ). Нечеткие веса для ребер двух звезд, соответствующих культуре лодин штрих и культуре два штриха, представлены в виде нечетких множеств, состоящих из совокупности пар вида W = {w;
(w)}, где w - элемент-носитель данного НВ, а (w) - значение функции принадлежности этого элемента.
w(e1 ) = {(8;
0,3), (18;
0,2), (38;
0,5)};
w(e ) = {(10;
0,3), (20;
0,2 ), (40;
0,5)} ;
2 w(e1) = {(18;
0,1), (38;
0,6 ), (56;
0,3)} ;
w(e ) = {(20;
0,1), (40;
0,6 ), (58;
0,3)} ;
w(e3 ) = {(12;
0,3), (22;
0,2 ), (42;
0,5)} ;
w(e ) = {(14;
0,3), (24;
0,2 ), (44;
0,5)} ;
4 x e1 z w(e3 ) = {(22;
0,1), (42;
0,6), (60;
0,3)} ;
w(e ) = {(24;
0,1), (44;
0,6 ), (62;
0,3)}. 4 x x e1 z v v e2 e e 2 e e z3 v e1 e z1 v e1 e2 e z v e e e z v e 2 e e а) б) в) Рисунок 3.2. Допустимые покрытия x r 8-вершинного 2-дольного графа звездами z и z, r = 1,2,3 r r Проиллюстрируем этапы суммирования нечетких весов для каждого из решений x1, x 2 и x 3 (рис. 3.2 а,б,в). Для x1, согласно (3.12) и (3.13) внутри одной звезды суммируем НВ ре бер первой звезды w(z1 ) = w(e1 ) + w(e ) + w(e3 ) = {(30;
0,3), (60;
0,2), (120;
0,5)} и НВ ребер 2 второй звезды w(z1) = w(e1) + w(e 2 ) + w(e3 ) = {(60;
0,1), (120;
0,6), (174;
0,3)}. Таким обра зом, вычислены нечеткие веса двух звезд w(z1 ) и w(z1). Далее, согласно (3.14) и (3.15) находим сумму НВ для этих двух звезд, при этом, суммирование элементов-носителей является скалярным, а значение функции принадлежности вычисляется согласно (3.15):
w H ( z1 ) + w H ( z1) = 30 + 60 ;
H (w H ( z1 ) (+) w H ( z1)) = wC ( z1 ) + wC (z1) = 60 + 120 ;
С (wС ( z1 ) (+) wС (z1)) = w B ( z1 ) + w B ( z1) = 120 + 174 ;
B (w B ( z1 ) (+ ) w B ( z1)) = 30 0,3 + 60 0,1 15 = = 0,17 30 + 60 90 60 0,2 + 120 0,1 84 = = 0,47 60 + 120 180 120 0,2 + 174 0,3 112,2 = = 0,38. 120 + 174 таким образом, для решения x1 из рис.3.2 значение ЦФ (3.10) представляется в виде НМ F (x1 ) = {(90;
0,17 ), (180;
0,47 ), (294;
0,38)}. Для наглядности на рис. 3.3 приведено графическое представление слагаемых НВ w(z1 ) и w(z1), а также их суммы, представляющей НВ решения x1.
1 0,8 0,6 0,4 0,2 0 0 25 50 75 100 125 150 175 200 225 250 275 (w( z )) w( z1) w( z1 ) w( z1 ) + w( z1) w( z ) Рисунок 3.3. Графическое представление значения нечеткого множества суммы весов двух звезд w( z1 ) и w( z1), представляющих культуру лодин штрих и культуру два штриха Для решения x 2 аналогично находим НВ соответствующих звезд z1 и z : w(z 2 ) = w(e1 ) + w(e 2 ) + w(e3 ) + w(e 4 ) = {(44;
0,3), (84;
0,2), (164;
0,5)} и w(z 2 ) = w(e3 ) + w(e 4 ) = {(46;
0,1), (86;
0,6), (122;
0,3)}. Далее, сумма НВ этих двух звезд w( z 2 ) и w( z ) определяется по формуле (3.15): w H ( z 2 ) + w H ( z 2 ) = 44 + 46 ;
H (w H (z 2 ) (+) w H ( z 2 )) = wC ( z ) + wC ( z ) = 84 + 86 ;
С (wС ( z 2 ) (+) wС ( z 2 )) = 2 44 0,3 + 46 0,1 17,8 = = 0,17 44 + 46 84 0,2 + 86 0,6 68,4 = = 0,40 60 + 120 170 164 0,5 + 122 0,3 118,6 = = 0,41. 164 + 122 w B ( z ) + w B ( z ) = 164 + 122 ;
B (w B (z 2 ) (+) w B (z 2 )) = 2 Таким образом, для решения x на рис.3. значение ЦФ F ( x 2 ) = {(90;
0,20 ), (170;
0,40 ), (286;
0,41)}.
По аналогии с x1 и x 2 для решения x 3 (см. рис.3.2 в) находим НВ соответст вующих ему звезд: w(z 3 ) = w(e3 ) + w(e 4 ) = {(18;
0,3), (38;
0,2), (78;
0,5)} и w(z 3 ) = w(e1) + w(e 2 ) + w(e3 ) + w(e 4 ) = {(84;
0,1), (164;
0,6), (236;
0,3)}. Далее, в соответст вии с (2.14) и (2.15) находим сумму НВ этих звезд:
w H ( z 3 ) + w H ( z 3 ) = 18 + 84 ;
H (w H ( z 3 ) (+) w H (z 3 )) = wC ( z 3 ) + wC ( z 3 ) = 38 + 164 ;
С (wС ( z 3 ) (+) wС ( z 3 )) = w B ( z 3 ) + w B ( z 3 ) = 78 + 236 ;
B (w B ( z 3 ) (+) w B ( z 3 )) = 18 0,3 + 84 0,1 13,8 = = 0,14 18 + 84 102 38 0,2 + 164 0,6 106 = = 0,52 38 + 164 202 78 0,5 + 236 0,3 109,8 = = 0,35. 78 + 236 Результатом суммирования НВ двух звезд (рис.2.2 в) является нечеткое мно жество значения ЦФ F (x3 ) = w(z 3 ) + w(z 3 ) = {(102;
0,14), (164;
0,6), (236;
0,3)}.
Представим графически на (рис.3.4) нечеткие значения ЦФ рассмотренных трех решений x1, x 2 и x 3. Эти НВ рассмотрим при определении операции сравнения нечетких значений максимизируемой ЦФ.
0,6 0,5 0,4 0,3 0,2 0,1 0 0 50 100 150 200 250 300 (F ( x r )) x x x F (x r ) Рисунок 3.4. Графическое представление результатов нечетких весов значений ЦФ F ( x r ), r = 1, r.
3.4.3. Операция сравнения НВ Отметим теперь, что к настоящему времени отсутствует общепризнанный метод упорядочения двух НВ или НМ по предпочтительности в задачах оптимизации. Практически все известные методы такого упорядочения [2,44] оперируют только значениями функции принадлежности без учета численных значений элементов-носителей сравниваемых НВ, что совершенно не адекватно целям рассматриваемой задачи землепользования. Предлагаемый в настоящей работе метод упорядочения НВ по предпочтительности базируется на процедуре дефазификации [24]. Прежде, чем приводить описание этой процедуры, отметим условия, при которых она не нужна. Для этого рассматриваем 2 допустимых решения x1, x 2 X, на которых ЦФ (3.10) принимает значения в виде двух НВ F (x j ) = {(w (x j );
(x j ))}, {Н, С, В}, j = 1,2, (3.23) Тогда, рассматривая величины w (x j ) и (x j ) в качестве максимизируемых показателей, можно утверждать, что вариант x1 предпочтительнее варианта x 2, если выполняются следующие неравенства w ( x1 ) w ( x 2 ), (x1 ) ( x 2 ), {Н, С, В}, (3.24) среди которых хотя бы одно является строгим. В случае невыполнения условия (3.24) реализуется следующая процедура дефазификации. Сначала вычисляются следующие величины:
L (x j ) = W w (x ) (x ), j j M (x j ) = W (x ), j N (x j ) = W w (x ), j j = 1,2.
(3.25) Далее вычисляются центры тяжести носителей (ЦТН) и соответствующие им степени принадлежности (СП):
w(x j ) = L(x j ) M (x j ), (x j ) = L(x j ) N (x j ).
(3.26) Пару (w(x j );
(x j )) условимся называть сверткой нечетких весов (СНВ). Для упорядочения вариантов x j, j = 1,2 по предпочтительности осуществляется операция сравнения интервалов [42] [ (x j ), w(x j )], j = 1,2. При этом гра ницы этих интервалов рассматриваются показателей.
в качестве максимизируемых Определение 3.1. Вариант x1 предпочтительнее варианта x2 (эквива лентен варианту x 2 ), или в другой терминологии, x2 доминируется вариантом x1 (x1 f x 2 ), если выполняются неравенства (x1 ) (x 2 ), w(x1 ) w(x 2 ), среди которых хотя бы одно является строгим (равенства (x1 ) = (x 2 ), w(x1 ) = w(x 2 ) ). Эквивалентность этих вариантов обозначаем через x1 ~ x 2.
Определение 3.2. Варианты x1 и x 2 являются несравнимыми ( x1 x2 ), если в паре интервалов [ (x j ), w (x j )], j = 1,2 один из них является строгим включением другого.
Примечание 3.2. Нетрудно убедиться в том, что при выполнении нера венств (3.24) вариант x1 преподчтительней x2. Если в (3.24) выполняются равенства, то x1 ~ x 2. Определенные выше бинарные отношения БО предпочтительности f, эквивалентности ~ и несравнимости позволяют вычленить из МДР X = {x} ~ паретовское множество (ПМ) X, на котором для каждой пары НВ ((w(x );
(x )), (w(x );
(x ))) выполняется БО несравнимости и БО эквивалентности. Последнее разбивает ПМ X на классы эквивалентности. Выбирая из каждого класса по одному представителю, получаем полное множество альтернатив (ПМА) X 0, X 0 X X. Определенное таким образом ПМА X 0 является искомым математическим решением задачи дискретного программирования с нечеткими данными. Далее элементы ПМА X 0 упорядочиваются по предпочтительности в смысле принятия решения [7,35,44]. Решение выше приведенного примера представляется в виде МДР X = {x1, x 2, x 3 }. Полученное МДР проверяется на выполнение для всех пар из X условия (3.24), при котором решения упорядочиваются по предпочтитель~ ~ ности и при этом операция дефазификации не нужна. Проведенная проверка выполнения условия (3.24) дала такой результат, что это условие не выполня ется для каждой пары решений из X. В связи с эти переходим к следующему этапу, а именно к вычислению величин (3.25). Согласно этой процедуры вычисляем центры тяжести элементов-носителей и соответствующие им степени принадлежности:
w(x1 ) = 90 0,17 + 180 0,47 + 294 0,38 211,62 = = 207,5 ;
0,17 + 0,47 + 0,38 1, ( x1 ) = w(x 2 ) = 90 0,17 + 180 0,47 + 294 0,38 211,62 = = 0,45 ;
90 + 180 + 294 474 90 0,20 + 170 0,40 + 286 0,41 203,26 = = 201,25 ;
0,20 + 0,40 + 0,41 1,01 90 0,20 + 170 0,40 + 286 0,41 203,26 = = 0,372 ;
90 + 170 + 286 546 102 0,14 + 202 0,52 + 314 0,35 229,22 = = 227 ;
0,14 + 0,52 + 0,35 1,01 102 0,14 + 202 0,52 + 314 0,35 229,22 = = 0,370. 102 + 202 + 314 (x 2 ) = w(x 3 ) = (x3 ) = Согласно (3.26) вычисленные центры тяжести элементов-носителей и соответствующие им степени принадлежности можно представить в виде пар w( x1 ) = 207,5, ( x1 ) = 0,45 ;
w( x 2 ) = 201,25, ( x 2 ) = 0,372 ;
w(x 3 ) = 227, ( x3 ) = 0,370.
Каждую пару вида ( w;
) можно назвать результатом свертки нечетких весов. Для упорядочения их по предпочтительности осуществляется сравнения интервалов вида [ ;
w]. Результаты применения операции сравнения для решения примера сведены в таблицу 3.1.
Таблица 3.1 Результат свертки нечетких весов в МДР X = {x1, x 2, x 3 }.
xr (x r ), w( x r ) (xi ) w( x i ) x1 x2 x 0,45 0,372 0, 207,5 201,25 Согласно определения 3.1 и значений ЦФ (3.10) из МДР X выделяем множество альтернатив (МА) X * X, состоящее из векторно несравнимых, т.е. взаимно недоминируемых допустимых решений. Из табл.2.1 видно, что x1 предпочтительнее x 2 ( x1 f x 2 ), т.е x 2 доминируется x1, а x1 и x 3 по опреде лению 3.2 несравнимы: (x1 x 2 ). Тогда исключив из X решение x 2, получаем ПМ, совпадающее с ПМА X = X 0 = {x1, x3 }.
Выводы ~ 1. Сформулирован и обоснован вывод о том, что искомым решением оптимизационной или векторной задачи в условиях неопределенности (интервальные и нечеткие исходные данные) является определенное множество альтернатив, а не отдельное допустимое решение. В качестве конкретной модели для диссертационного исследования сформулирована векторная постановка задачи покрытия графа звездами и паросочетаниями с нечеткими весами. 2. Дано обоснование заключения о том, что все известные к настоящему времени определения операции суммирования для нечетких множеств являются неадекватными содержательной сущности рассматриваемой задачи землепользования. 3. Сформулированы и обоснованы новые определения операций суммирования и сравнения, адекватных математической модели задачи землепользования с нечеткими данными.
ГЛАВА 4. ЗАДАЧИ ВЕРХНЕГО УРОВНЯ. ИССЛЕДОВАНИЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ, РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙНОЙ СВЕРТКИ И АЛГОРИТМ С ОЦНКАМИ ЗАДАЧ ПОКРЫТИЯ ГРАФА 4ЦИКЛАМИ В предыдущей главе рассматривалась проблема получения прогнозных значений урожайностей. Эта проблема относится к нижнему уровню общей 2-уровневой модели землепользования пахотными угодьями. Полученные в виде нечетких или скалярных значений результаты прогнозирования, выполненные на нижнем уровне, представляют собой исходные данные для экстремальных задач на графах, рассматриваемых на верхнем уровне моделирования. Такого рода задачи рассматривались в многочисленных публикациях, относящихся к проблематике дискретной оптимизации. Вместе с тем следует отметить, что практически во всех таких публикациях рассматриваемые задачи формулируются в предположении, что в данном графе весами ребер являются обычные числа или в условиях многокритериальности ребра взвешены векторами чисел. Экстремальные задачи на графах с нечеткими весами для ребер до настоящего времени фактически не исследовались. Поэтому для таких задач остаются открытыми все вопросы, касающиеся таких фундаментальных характеристик, как оценки вычислительной сложности, разрешимость с помощью алгоритмов линейной свертки критериев (АЛСК), приближенные методы с априорными оценками точности и трудоемкости и т.д. В качестве конкретного исследования главы 4 выбрана задача покрытия 4- циклами графа с нечеткими либо интервальными весами в силу ряда причин: во-первых, эта задача остается неисследованной даже для случая, когда весами ребер являются обычные числа;
во-вторых в прикладном отношении эта задача является актуальной в силу наметившейся в землепользовании тенденций культивирования так называемых коротких (3-польных, 4польных) севооборотов;
в-третьих, методологическая проблема, обусловлен ная нечеткими весами, в равной мере присуща всем задачам покрытия графа типовыми подграфами. В [86,87] представлена статья, посвященная взаимосвязи между интервальной математикой и теорией нечетких множеств. Связь между интервальной математикой и теорией НМ очевидна в общем случае, а также в арифметике, логике и в исследованиях математических неопределенностей. Многие исследователи по сегодняшний день используют интервальную математику в теории нечетких множеств. Влияние нечеткой теории на интервальную математику не совсем очевидно, но вместе с тем результаты, полученные в области нечеткого множества используют в исследованиях, относящиеся к области интервальной математики. Кажущиеся различия между ними возникли в силу того, что основные направления интервальной математики и теории нечеткого множества развивались параллельно, практически не пересекаясь. Теория приближений независимо развилась из того, что было известно в обобщенном интервальном анализе, и вместе с тем, она может быть использована в обобщенной теории нечетких множеств. Одно из направлений интервальной математики привело к валидационному анализу. Сравнимый аналог этого анализа можно использовать в нечетких множествах. Интервальный анализ - это метод моделирования неопределенностей, возникающих в результате компьютерных вычислений. Таким образом, интервальный анализ - это часть математического моделирования в поле теории нечетких множеств. Появились публикации [2,87], посвященные применению интервальных методов в теории нечетких множеств. Можно также утверждать, что эти области являются взаимодополняющими. Кроме того, сегодня уже есть достаточно много работ, посвященных методам оптимизации как в области интервального анализа, так и в теории нечетких множеств. Эти работы устанавливают взаимосвязь между интервальной и нечеткой оптимизациями.
4.1. Формулировка интервальной экстремальной задачи Интервальные задачи возникают в условиях неточных данных ее параметров [1,14,68]. В математических моделях землепользования интервальный вес может, например, представлять урожайность культуры, прогнозируемое значение которой в принципе не может быть задано в виде однозначно определенного числа [47]. Сформулируем интервальную экстремальную задачу на графах. В заданном n -вершинном графе G = (V, E ) каждое ребро e E взвешено интервалом w(e ), т.е. отрезком w(e ) = [w1 (e ), w2 (e )], где w1 (e ) w2 (e ). Подграф x = (V x, E x ), V x V, E x E представляет собой допустимое решение рассматриваемой за дачи. Обозначим через X = {x} МДР рассматриваемой задачи, на котором определена интервальная целевая функция (ИЦФ) w( x ) = eE x w(e) max (4.1) или ИЦФ w( x ) = min w(e ) max.
eE x (4.2) Значение этих ИЦФ можно получить из свойств операций сложения интервалов [1,14,27] и сравнения интервалов [1], представляющих значение ИЦФ w(x ) = [w1 ( x ), w2 ( x )], (4.3) где wi (x ) = eE x w (e), i i = 1,2. Под решением интервальной задачи понимается та кой элемент x 0 X, на котором значение ИЦФ (4.1) или (4.2) достигает требуемого экстремума. В случае интервальных весов нахождение оптимума наталкивается на проблему выбора наиболее целесообразного решения из множества несравнимых альтернатив. В связи с этим необходимо ввести отношения предпочтения, эквивалентности и несравнимости [14,27]. Определение 4.1. Бинарное отношение (БО) предпочтительности усло вимся обозначать символом f, БО несравнимости - символом, БО эквивалентности - символом ~. Из двух решений x1 и x 2, x1, x 2 X, x1 предпочтительнее решения x 2 ( x1 f x 2 ), если wi (x1 ) wi (x 2 ), i = 1,2, при этом хотя бы одно неравенство является строгим. Решения x1 и x 2 несравнимы ( x1 x 2 ), когда имеет место строгое вложение интервалов w(x1 ) w(x2 ), либо w(x2 ) w(x1 ). Эти решения эквивалентны ( x1 ~ x 2 ), если совпадают соответствующие им интервалы w(x1 ) = w(x 2 ). Отношения предпочтения и несравнимости порождают на МДР X паретовское множество (ПМ) X X [65], состоящее из паретовских оптимумов (ПО). Определение 4.2. Для задачи с ИЦФ (4.1) решение ~ X называется x ПО, если не существует x * X такого, что x * f ~. x В качестве искомого решения сформулированной задачи можно рассматривать как ПМ X, так и используемое в многокритериальной оптимизации понятие ПМА X 0 [47]. Определение 4.3. ПМА есть подмножество X 0 X ~ x X, где w( x ) есть значение ИЦФ (4.1).
~ ~ ~ минимальной мощности, содержащее по одному представителю на каждое значение w(x ), Примечание 4.1. Введение указанных бинарных отношений порядка f, и ~ на МДР X диктуется содержательной постановкой задачи. Отме тим, что отношения порядка, представленные в определении 4.1, порождают паретовское множество меньшей мощности, нежели отношения порядка, предлагаемые в работах [28]. 4.2. Аппроксимация интервальной задачи покрытия графа 4- циклами векторной задачей Поясним термины векторная задача на графах с критериями вида MAXSUM и л2-критериальная задача на графах с критериями вида MAXMIN. Рассматривается n -вершинный граф G = (V, E ), в котором каждое реб ро e E взвешено парой весов W1 (e ), W2 (e ), причем, является обязательным выполнение неравенства W1 (e ) W2 (e ). На МДР X определена векторная целевая функция (ВЦФ) F ( x ) = (F1 ( x ), F2 ( x )), (4.4) (4.5) состоящая из критериев вида MAXSUM F (x ) = eE x W (e) max, = 1, или критериев вида MAXMIN F (x ) = min W (e ) max, = 1, 2.
eE x (4.6) ~ ВЦФ (4.4)-(4.6) определяет в МДР X ПМ X, а также ПМА X 0. В качестве искомого решения этой 2-критериальной задачи в различных работах рассматривается как ПМ X, так и ПМА X 0. Примечание 4.2. Всякая математическая постановка векторной задачи на графах всегда предполагает строгое определение допустимого решения x, МДР X, а также критериев F (x ) extr, = 1, N, extr {min, max}, соответствующей ВЦФ F ( x) = (F1 ( x), F2 ( x),..., FN ( x) ). Перейдем теперь к проблеме определения методов решения интервальных задач на графах. В работе [90] представлено обоснование утверждения о том, что всякая интервальная задача на графах с ИЦФ (4.1) эквивалентна соответствующей 2-критериальной задаче с ВЦФ (4.4)-(4.5), а всякая интервальная задача на графах с ИЦФ (4.2) эквивалентна 2-критериальной задаче с ВЦФ (4.4)-(4.6). При этом заметим, что в критериях этих задач значения весов W (e) определяются равенствами: W1 (e ) = w1 (e ), W2 (e ) = w2 (e ), e E. Здесь термин лэквивалентность означает, что ИЦФ (4.1) и ВЦФ (4.4)-(4.5) задают на МДР этих задач соответственно совпадающие ПМ и ПМА. Следовательно, для нахождения паретовских оптимумов данных интервальных задач можно их свести к 2-критериальным задачам с последующим использованием подходящих АЛСК. До настоящего времени оставался открытым вопрос о разрешимости с ~ помощью АЛСК именно тех векторных задач, к которым сводятся соответствующие интервальные задачи. Перейдем к рассмотрению этого вопроса. Как указано выше, интервальная задача покрытия графа 4 - циклами сводится к соответствующей 2-критериальной задаче [90], которая формулируется следующим образом. В данном графе G = (V, E ) каждому ребру e E приписана пара весов w (e ), = 1, 2, причем для всякой такой пары выполняется неравенство w1 (e ) w2 (e ). Будем называть h -вершинный цикл h -циклом, 2 h n. Допустимым покрытием графа G циклами называется всякий его остовный подграф x = (V, Ex ), Ex E, у которого каждая компонента связности представляет собой некоторый h -цикл, h H. Для заданной пары G, H соответствующее ей МДР обозначается через X = X (G, H ) = {x}. На МДР X определена ВЦФ (4.3), состоящая из критериев вида MAXSUM F ( x ) = eE x w (e) max, = 1, (4.7) и критериев вида MAXMIN F (x ) = min w (e ) max, = 1, 2, eE x (4.8) причем, для каждого ребра графа G его веса удовлетворяют условию w1 (e ) w2 (e ), e E.
(4.9) ВЦФ вида (4.4), (4.7), (4.9) и соответственно ВЦФ (4.4), (4.8), (4.9) задают в МДР X и ПМ X, которые, в свою очередь, содержат искомое ПМА ~ X 0. Нахождение этих ПМА и означает решение исходных интервальных задач с ИЦФ (4.1)-(4.3). 4.3. Исследование разрешимости с помощью алгоритмов линейной свертки критериев задачи с интервальными данными и критериями вида MAXSUM Для определения понятия линейная свертка критериев введем множество векторов размерности N :
N = = ( 1, 2,..., N ) :
= 1, = N > 0, = 1,2,..., N.
(4.10) Линейную свертку критериев (ЛСК) будем обозначать через F ( x ). Для выбранного вектора N ЛСК определяется выражением F ( x ) = F ( x ).
= N (4.11) Вычислительная схема АЛСК, чаще всего, строится с учетом того, что является справедливым следующее Утверждение 4.1. Для любого вектора из множества векторов (4.7) элемент x *, максимизирующий на МДР X линейную свертку критериев (4.11) целевых функций F (x ), = 1,2,..., N, является ПО [65]. Однако, как было отмечено выше, АЛСК не всегда обеспечивают по~ ~ лучение всех ПО ~ X [32,52]. Если ПМ X хотя бы одной индивидуальной x интервальной задачи и соответствующей ей 2-критериальной задачи содержит такой элемент x*, на котором ни при каком 2 не достигает максимума значение свертки (4.11), то можно говорить о неразрешимости с помощью АЛСК соответствующей массовой задачи [17]. Рассмотрим конкретную индивидуальную задачу покрытия 8вершинного графа G* = (V *, E * ) 4-вершинными циклами (рис.4.1). Множество его вершин содержит 8 вершин, V * = 8, а множество E * = {ei }, i = 1,24 состоит из следующих ребер:
e1 = (1,2 ), e2 = (1,4 ), e3 = (1,6), e9 = (3,6), e15 = (5,2), e21 = (4,8), e4 = (1,8), e5 = (1,5), e11 = (5,7 ), e6 = (1,3), e12 = (5,8), e7 = (3,7 ), e13 = (5,6), e19 = (7,2), e8 = (3,8), e14 = (5,4 ), e10 = (3,4), e16 = (7,8), e22 = (2,6 ), e17 = (7,6), e23 = (2,4 ), e18 = (7,4), e24 = (2,3), e20 = (6,8), этим ребрам приписаны интервальные веса:
w(e1 ) = [5, 40], w(e2 ) = [10,50], w(e3 ) = [5,35], w(e7 ) = [15,35], w(e11 ) = [20,25], w(e4 ) = [10,30], w(e5 ) = [10,30], w(e9 ) = [10,15], w(e13 ) = [10,30], w(e17 ) = [10,15], w(e21 ) = [5, 10], w(e6 ) = [15,35], w(e10 ) = [5,15], w(e14 ) = [10,50], w(e8 ) = [10,30], w(e12 ) = [25,40], w(e15 ) = [10,20], w(e19 ) = [20,30], w(e23 ) = [10,25], w(e16 ) = [30,35], w(e20 ) = [10,15], w(e24 ) = [15,30].
w(e18 ) = [5, 20], w(e22 ) = [10,15], e1 e e6 e e e e 23 e e e 10 e9 e7 e e e 14 e e e e19 e18 e 6 e e e Рисунок 4.1. 8- вершинный граф G = (V, E ) Сведем эту интервальную задачу к 2-критериальной задаче с ВЦФ (4.5). В результате этого сведения получаем тот же, т.е. представленный на рис.4.1 граф, который является 2-взвешенным и обозначается через G = (V, E ).
Согласно п.4.2 каждому ребру e E с учетом исходных интервальных весов w ( e ) приписываются 2 веса w1 ( e ) и w2 ( e ) :
w1 (e1 ) = 5, w2 (e1 ) = 40 ;
w1 (e2 ) = 10, w2 (e2 ) = 50 ;
w1 (e13 ) = 10, w2 (e13 ) = 30 ;
w1 (e14 ) = 10, w2 (e14 ) = 50 ;
w1 (e3 ) = 5, w2 (e3 ) = 35 ;
w1 (e4 ) = 10, w2 (e4 ) = 30 ;
w1 (e15 ) = 10, w2 (e15 ) = 20 ;
w1 (e16 ) = 30, w2 (e16 ) = 35 ;
w1 (e17 ) = 10, w2 (e17 ) = 15 ;
w1 (e18 ) = 5, w2 (e18 ) = 20 ;
w1 (e19 ) = 20, w2 (e19 ) = 30 ;
w1 (e20 ) = 10, w2 (e20 ) = 15 ;
w1 (e21 ) = 5, w2 (e21 ) = 10 ;
w1 (e22 ) = 10, w2 (e22 ) = 15 ;
w1 (e5 ) = 10, w2 (e5 ) = 30 ;
w1 (e6 ) = 15, w2 (e5 ) = 35 ;
w1 (e7 ) = 15, w2 (e7 ) = 35 ;
w1 (e8 ) = 10, w2 (e8 ) = 30 ;
w1 (e9 ) = 10, w2 (e9 ) = 15 ;
w1 (e10 ) = 5, w2 (e10 ) = 15 ;
w1 (e11 ) = 20, w2 (e11 ) = 25 ;
w1 (e12 ) = 35, w2 (e12 ) = 40 ;
(4.12) w1 (e23 ) = 10, w2 (e23 ) = 25 ;
w1 (e24 ) = 15, w2 (e24 ) = 30.
МДР X рассматриваемой интервальной задачи на графе G состоит из 12-ти допустимых покрытий xr = (V, Exr ), r = 1,12, представленных на рисунках 4.2-4.13:
e e6 e10 e13 e e e e 22 e e 24 e e e 2 e23 5 e17 7 6 e Рисунок 4.2.
e Рисунок 4.3.
1 2 e e4 e e8 e e e e22 e e 3 e e 6 e e19 e7 7 Рисунок 4.4.
Рисунок 4.5.
1 e e e1 e1 0 e1 3 e 21 e1 6 e e e6 e e e e 4 e e11 8 Рисунок 4.6.
8 Рисунок 4.7. e e e e e e9 e e e e e e e 6 e18 e e Рисунок 4.8.
1 e5 e Рисунок 4.9.
2 e23 5 4 6e 20 8 e3 e 2 e e23 e e e e e 4 6e e e Рисунок 4.10.
1 e 23 e Рисунок 4.11.
e e e e e e e e e e e e e 6 6 e Рисунок 4.12.
Рисунок 4.13.
МДР X представляет собой множество X = { xr }, xr = (V, Exr ), r = 1,12 где E x1 = {e1, e6, e10, e11, e13, e16, e20, e23 }, E x2 = {e2, e5, e7, e12, e17, e21, e22, e24 }, E x3 = {e3, e4, e8, e9, e14, e15, e18, e19 }, E x4 = {e4, e5, e7, e9, e14, e15, e18, e19 }, E x5 = {e1, e5, e7, e10, e13, e16, e21, e22 }, E x6 = {e2, e6, e8, e11, e15, e17, e21, e22 }, E x7 = {e3, e5, e8, e11, e17, e21, e23, e24 }, E x8 = {e1, e6, e9, e11, e14, e16, e18, e22 }, E x9 = {e3, e5, e7, e12, e18, e20, e23, e24 }, E x10 = {e3, e6, e8, e11, e15, e18, e20, e23 }, E x11 = {e1, e5, e7, e9, e13, e14, e16, e20 }, E x12 = {e3, e6, e7, e12, e15, e17, e21, e23 }.
(4.13) Для каждого допустимого решения xr X, r = 1,12 вычислим значения критериев F1 ( x1 ) = F ( xr ) = eE x w (e) max, = 1, 2 :
1 1 1 6 1 10 1 11 1 13 1 16 1 20 1 eE x w (e) = w (e ) + w (e ) + w (e ) + w (e ) + w (e ) + w (e ) + w (e ) + w (e ) = = 5 + 15 + 5 + 20 + 10 + 30 + 10 + 10 = 105.
F2 ( x1 ) = eE x w (e) = w (e ) + w (e ) + w (e ) + w (e ) + w (e ) + w (e ) + w (e ) + w (e ) = 2 2 1 2 6 2 10 2 11 2 13 2 16 2 20 2 = 40 + 35 + 15 + 25 + 30 + 35 + 15 + 25 = 220.
Далее аналогично этому вычисляем значения критериев F (x r ), = 1,2 на остальных решениях из X :
F1 ( x 2 ) = 10 + 10 + 15 + 35 + 10 + 5 + 10 + 15 = 110 F2 (x 2 ) = 50 + 30 + 35 + 40 + 15 + 10 + 15 + 30 = F1 ( x3 ) = 5 + 10 + 10 + 10 + 10 + 10 + 5 + 20 = 80 F2 (x3 ) = 35 + 30 + 30 + 15 + 50 + 20 + 20 + 30 = 230 F1 ( x 4 ) = 10 + 10 + 15 + 10 + 10 + 20 + 5 + 10 = 90 F2 (x 4 ) = 30 + 30 + 35 + 15 + 50 + 30 + 10 + 15 = 215 F1 ( x5 ) = 5 + 10 + 15 + 5 + 10 + 30 + 5 + 10 = 90 F2 (x5 ) = 40 + 30 + 35 + 15 + 30 + 35 + 10 + 15 = 210 F1 ( x6 ) = 10 + 15 + 10 + 20 + 10 + 10 + 5 + 10 = 80 F2 (x6 ) = 50 + 35 + 30 + 25 + 20 + 15 + 10 + 15 = 200 F1 ( x7 ) = 5 + 10 + 10 + 20 + 10 + 5 + 10 + 15 = 85 F2 (x7 ) = 35 + 30 + 30 + 25 + 15 + 10 + 25 + 30 = 200 F1 ( x8 ) = 5 + 15 + 10 + 20 + 10 + 30 + 5 + 10 = (4.14) F2 (x8 ) = 40 + 35 + 15 + 25 + 50 + 35 + 20 + 15 = 225 F1 ( x9 ) = 5 + 10 + 15 + 35 + 5 + 10 + 10 + 15 = 105 F2 (x9 ) = 35 + 30 + 35 + 40 + 20 + 15 + 25 + 30 = 220 F1 ( x10 ) = 5 + 15 + 10 + 20 + 10 + 5 + 10 + 10 = 85 F2 (x10 ) = 30 + 35 + 30 + 25 + 20 + 20 + 15 + 25 = 205 F1 ( x11 ) = 5 + 10 + 15 + 10 + 10 + 10 + 30 + 10 = 100 F2 (x11 ) = 40 + 30 + 35 + 15 + 30 + 50 + 35 + 15 = 250 F1 ( x12 ) = 5 + 15 + 15 + 35 + 10 + 10 + 5 + 10 = 110 F2 (x12 ) = 35 + 35 + 35 + 40 + 20 + 15 + 10 + 25 = Результаты вычислений занесем в таб. 4. Таблица 4.1. МДР X = {x r }, r = 1,12 и ВЦФ для заданной 2-критериальной задачи xr F1 ( xr ) F2 ( xr ) 105 220 x1 110 225 x2 80 230 x x4 x 90 90 80 85 105 105 85 100 215 210 200 200 225 230 205 250 x6 x7 x8 x9 x x11 x Из таб. 4.1 видно, что оптимальными являются векторнонесравнимыми, точнее паретоx2, элементы x и x11, а элементы x1, x3, x4, x5, x6, x7, x8, x10, x12 являются доминируемыми по ВЦФ (4.4)-(4.5). Со % гласно представленных в таб. 4.1 значений F ( xr ), = 1,2, xr X, получаем совпадение ПМ и ПМА: X = X 0 = {x2, x9, x11 }. Образуем теперь линейные свертки критериев, пользуясь формулой ~ (4.11):
F ( xr ) = F ( xr ), = r = 1,12, где (1, 2 ) 2.
(4.15) Согласно (4.12)-(4.15) свертки критериев решений x2, x9, x11 принимают вид:
F ( x2 ) = 1 w1 ( x2 ) + 2 w2 ( x2 ) = 1101 + 2252 ;
F ( x9 ) = 1 w1 ( x9 ) + 2 w2 ( x9 ) = 1051 + 2302 ;
F ( x11 ) = 1 w1 ( x11 ) + 2 w2 (x11 ) = 1001 + 250 2.
(4.16) С учетом равенства 2 = 1 1 и согласно таблице 4.1, вместо представленных выражением (4.16) сверток рассмотрим их представление в виде функции от 1 :
F (1, x 2 ) = 1101 225(1 1 ) ;
F (1, x 9 ) = 1051 230(1 1 ) ;
F (1, x11 ) = 1001 250(1 1 ).
(4.17) После раскрытия скобок из (4.17) получим:
F (1, x 2 ) = 225 1151 ;
F (1, x 9 ) = 230 1251 ;
F (1, x11 ) = 250 1501.
(4.18) Графическое представление сверток (4.18) дано на рис.4. F (1, x11 ) F (1, x 9 ) 230 225 F (1, x 2 ) 110 105 Рисунок 4.14. Графическое представление сверток F (1, x2 ), F (1, x9 ), F (1, x11 ) Из графического представления сверток F (1, x2 ), F (1, x9 ), F (1, x11 ) видно, что графики сверток F (1, x9 ) и F (1, x11 ) образуют верхнюю границу паретовского множества, т.е. F (1, x) = max(F (1, x9 ), F (1, x11 )). График свертки F (1, x 2 ) находится строго ниже этой границы, представленной на рис.4. жирной ломаной, т.е. F (1, x 2 ) < F (1, x ) при любом 1 [ 0,1]. Таким образом получаем, что для всякого значения 1 [0,1] и соответственно для любого 2 значение F ( 1, x ), а вместе с ним и F ( x ) может достигаться либо на элементе x 2, либо на элементе x11 и ни при каком значении 2 этот максимум не достигается на элементе x 2. Таким образом, мы получили, что приведенная индивидуальная интервальная задача неразрешима с помощью АЛСК, поскольку линейная свертка ее критериев достигает максимума на элементах x9 и x11. Рассмотрим теперь случай покрытия произвольного n -вершинного графа 4-циклами. Представленный на рис.4.15 граф G = (V, E ) получен из G последовательным (по шагам k = 1, 2,... ) присоединением очередного 4-цикла к каждой следующей несмежной паре вершин.
1 2 6 Рис.4.15. n -вершинный граф G = (V, E ) полученный из G последовательным (по шагам k = 1, 2,... ) присоединением очередного 4-цикла к каждой следующей несмежной паре вершин В результате реализации шага k получается n -вершинный ( n = 4k + 8 ) s -реберный ( s = 9k + 24 ) граф. МДР X = {x1, x 2, x3, x4, x5, x6, x7, x8, x 9, x10, x11, x12 } рассматриваемой задачи на графе G получается соответственно из МДР 2 X = {x1, x, x 3, x 4, x 5, x 6, x 7, x8, x 9, x10, x11, x12,} этой же задачи на графе G. Каждое ребро присоединенного 4-цикла взвешено точечным интервалом w1 ( e), w2 ( e) = [1,1] =1. Вычислим значения F (xr ) для каждого x X : r F1 (x1 ) = 4k + 105, F1 (x3 ) = 4k + 80, F1 (x5 ) = 4k + 90, F1 (x7 ) = 4k + 85, F2 (x1 ) = 4k + 220, F2 ( x3 ) = 4k + 230, F2 ( x5 ) = 4k + 210, F2 ( x7 ) = 4k + 200, F1 (x ) = 4k + 110, 2 F1 (x4 ) = 4k + 90, F1 (x6 ) = 4k + 80, F1 (x8 ) = 4k + 105, F2 (x ) = 4k + 225, 2 F2 (x4 ) = 4k + 215, F2 ( x6 ) = 4k + 200, F2 (x8 ) = 4k + 225, (4.19) F1 (x9 ) = 4k + 105, F1 (x11 ) = 4k + 100, F2 (x9 ) = 4k + 220, F2 ( x11 ) = 4k + 250, F1 (x10 ) = 4k 6 + 85, F1 (x12 ) = 4k + 110, F2 ( x10 ) = 4k + 205, F2 ( x12 ) = 4k + 215.
Из представленных выше значений ВЦФ на МДР X видно, что элемен ты x1, x 3, x 4, x 5, x 6, x 7, x8, x10, x12 являются доминируемыми по обоим критериям ~ F ( x ), = 1,2. Таким образом, паретовское множество X X состоит из эле ментов x 2, x 9, x11. Кроме того, среди последних нет эквивалентных. Следова тельно, искомые ПМ и ПМА совпадают: X = X 0 = {x, x 9, x11 }. 2 ~ По аналогии с (4.16)-(4.18) получим:
F (1, x 2 ) = 4k + 225 1151 ;
F (1, x 9 ) = 4k + 230 1251 ;
F (1, x11 ) = 4k + 250 1501.
(4.20) Графическое представление сверток F (1, xr ), r = 2,9,11 можно получить из рис.4.14, осуществив параллельный перенос всех его графиков параллельно оси ординат на величину 4k. Ясно, что подобное преобразование не повлияет на топологическую характеристику графиков сверток (4.16). Т.е. свертка F (1, x ) будет находиться ниже паретовской границы F (1, x) = max(F (1, x9 ), F (1, x11 )). Таким образом на элементе x не достигает максимума значение свертки (4.20), т.е. являются справедливыми следующие утверждения.
Теорема 4.1. Задача покрытия графа G 4-циклами с ВЦФ (4.4), (4.5), (4.6) неразрешима с помощью АЛСК.
Теорема 4.2. Для всякого n -вершинного графа G ( n кратно 4), интер вальная задача покрытия графа G 4-циклами с ВЦФ (4.4), (4.5), (4.6) неразрешима с помощью АЛСК. В качестве базы для реализации АЛСК в настоящей главе предлагается приближенный алгоритм покрытия графа 4-циклами и произведено обоснование его статистической эффективности. Необходимость разработки такого алгоритма обусловлена тем обстоятельством, что для решения рассматривае мых задач верхнего уровня неприменимы какие-либо известные алгоритмы, в том числе и алгоритмы линейного или целочисленного программирования. Указанная неприменимость, в свою очередь, обусловлена тем фактом, что представленные в главе 1 МДР X = {x} невозможно определить системой линейных равенств и неравенств, т.е. невозможно представить в виде многогранника в соответствующем пространстве.
4.4. Обоснование свойства полноты задачи покрытия графа 4- циклами В [49] сформулирован ряд массовых модельных задач zq на графах q = 1,9. Каждая задача zq идентифицируется собственным названием и опре делением своего допустимого решения x, где x - подграф (Vx, Ex ) данного графа G = (V, E ), Vx V, Ex E. В исследуемой задаче z9 (задача покрытия графа 4-циклами) допустимым решением является остовный подграф x графа G, каждая компонента связности которого является звездой из заданного МТЗ H.
Обозначим через W = {X } семейство всех множеств допустимых решений задачи z9, т.е. W получается путем объединения множеств X по всем индивидуальным задачам, порождающим эти множества.
Определение 4.4. Векторная задача zq называется полной или обла дающей свойством полноты, если для каждого множества X W существуют такие параметры ее ВЦФ F ( x ), при которых выполняется равенство % X0 = X = X.
(4.21) Очевидным является интерес к полным задачам. Для них легче обосновать оценки сложности нахождения любого МА, а также облегчается исследование структуры ПМ, ПМА. Пусть R N - евклидово пространство размерности N. Из определения ПМ и ПМА вытекает, что справедлива Лемма 4.1. Для всякой векторной задачи с ВЦФ вида F : X R N вы полняется равенство мощностей X 0 = F (X ).
~ Для задачи z9 с ВЦФ (3.3) рассмотрим некоторую ее индивидуальную задачу с МДР X, ПМ X, ПМА X 0. После добавления к ВЦФ (3.3) новых критериев получим другую индивидуальную задачу, у которой новая (расширенная) ВЦФ определяет, вообще говоря, другие МА. Возникает вопрос о том, как соотносятся старые и новые МА. С учетом того, что добавление новых критериев не изменяет значения старых критериев (3.4) на всех элементах x X, справедлива Лемма 4.2. При любом N 2 для всякой индивидуальной задачи с ВЦФ ~ (3.3)-(3.5) добавление новых критериев к этой ВЦФ либо оставляет ПМ X и ПМА X 0 неизменными, либо дополняет их новыми альтернативами.
Теорема 4.3. Векторная задача z9 является полной, если ее ВЦФ (3.3) ~ содержит не менее двух весовых критериев вида (3.4). Доказательство. Выберем произвольное X W, которое определяется данным n - вершинным графом G = (V, E ). Для случаев X = или одноэлементного МДР (мощность X = 1 ) утверждение теоремы 4.3 очевидно. Пусть мощность МДР X 2. Рассматриваем вначале случай N = 2, когда ВЦФ (3.3) имеет вид F ( x ) = (F1 ( x ), F2 ( x )) = (w1 ( x ), w2 ( x )), (4.22) где значения ее критериев w (x ) = eE x w (e), = 1, 2. В данном 2-взвешенном графе G ребра e E перенумеруем числами t = t (e ) = 1, 2,..., m, m = E, причем веса этих ребер определим следующим образом:
w1 (t ) = 2 t, w2 (t ) = r0 w1 (t ), t = 1,..., m, (4.23) где r0 = 2m + 1. Согласно определению задачи z 9, сформулированной на данном графе G, для допустимых решений x = (V, E x ) выполняется равенство Ex = c0 x X ( G, H ), (4.24) где с 0 независящая от допустимых решений x X рассматриваемой задачи (для всякой фиксированной размерности n. Из (4.23) и (4.24) получаем равенство F1 ( x ) + F2 (x ) = c 0 r0 x X ( G, H ).
(4.25) множеств ребер, Обозначим через Rl,s = El E s разность определяющих допустимые решения xl, x s X. Тогда для всяких x1, x 2 X R1, 2 I R2, 1 =, R1, 2 = R2,1.
для пары (4.26) Пусть среди элементов множества R1, 2 I R2,1 ребро e с наибольшим номером t = t (e ) принадлежит R1, 2. Тогда из (4.22)-(4.25) вытекают неравенства F1 ( x1 ) > F1 ( x 2 ), F2 ( x1 ) < F2 ( x2 ), которые означают, что любая пара x1, x 2 X яв ляется векторно-несравнимой по ВЦФ (4.22). Последнее с учетом леммы 5.1 означает выполнение равенства (4.21). Для N = 2 теорема 4.3 доказана. В силу леммы 4.2 равенство (4.21) выполняется и при N 3, если =1, 2 критерии (3.2) определены согласно (3.4), (3.5), а для = 3,..., N - произвольным образом. Теорема 4.3 доказана.
4.5. Исследование вычислительной сложности Понятие трудоемкости алгоритма определяется как его вычислительная сложность, которая оценивается относительно входа [3,4,40,45] количеством элементарных операций, затрачиваемых на нахождение и представление в явном виде искомого МА. В настоящем параграфе обосновываются оценки для двух видов вычислительной сложности: сложность в худшем случае [3], выражаемая в терминах гарантированных объемов вычислений, и сложность для почти всех индивидуальных задач [4] рассматриваемой многокритериальной задачи. Полученные в настоящей главе оценки вычислительной сложности ха рактеризуют асимптотическую временную сложность [3,45]. Последнее отражает поведение вычислительной сложности как функция от размера входа в пределе при увеличении размера задачи. При этом, придерживаясь терминологии [3], мы условимся, что предлагаемые алгоритмы реализуются на машинах с произвольным доступом у памяти. Наряду с понятием вычислительная сложность алгоритма в настоящей главе рассматривается также понятие вычислительная сложность задачи или кратко, сложность задачи. Оценивая вычислительную сложность задачи в худшем случае, используем сложившуюся к настоящему времени иерархию вида: полиномиальные задачи - л NP -трудные задачи- труднорешаемые задачи. Учитывая, что понятие NP -полноты относится только к задачам распознавания [3,45], условимся использовать упомянутую шкалу (иерархию) вычислительной сложности в контексте алгоритмических вопросов многокритериальной оптимизации. Это предложение означает следующее. Ставшая уже классической теория полиномиальной сводимости [3,45] была построена для задач распознавания свойств. Аналогичную теорию полиномиальной сводимости [45] можно построить и для экстремальных дискретных задач. При построении указанной теории можно не пользоваться моделью вычислительного устройства (например, машины Тьюринга), т.е. сделать ее машинно независимой и использовать термины вычислимых операторов над функциями. Это положение фактически используется в настоящей работе при обосновании оценок вычислительной сложности многокритериальных задач, базируясь на известном тезисе о том, что задача оптимизацииэто три (эквивалентные) задачи (распознавания, вычислительная и оптимизационная). Обоснование этого тезиса дано в [45]. Выражение л NP -полная многокритериальная задача можно интерпретировать как свойство сравнительно простого (полиномиального) сведения этой многокритериальной задачи к последовательности задач распознавания [40]. Таким образом, математическая постановка проблемы нахождения МА обобщает вопрос нахождения оптимума в задачах дискретного программирования [3,8]. В настоящей главе используемые понятия формулируются в терминах дискретного программирования (комбинаторной оптимизации) с привлечением тех же задач, которые наиболее часто используются в указанных источниках в качестве модельных объектов исследования. Термины и понятия, отражающие специфику многокритериальности, достаточно полно определены в [10,65].
Примечание 4.3. Упомянутая выше мера вычислительной сложности, определяемая как граница вычислительной сложности в наихудшем случае, является традиционной, т.е. представляется как классическое определение вычислительной сложности. Однако, такой подход, базирующийся на анализе худшего случая, часто подвергается обоснованной критике из-за слишком пессимистических результатов, которые этот подход дает. В случае NP трудных или трудноразрешимых комбинаторных задач экспоненциальные оценки вычислительной сложности имеют ограниченное значение для практических целей. В таких случаях средняя вычислительная сложность или, например, вычислительная сложность в типичном (наиболее часто встречающемся) случае представляется более информативной. Поиски эффективных и точных методов для многих NP -трудных или трудноразрешимых задач не имеют практического смысла. В этой ситуации мы вынуждены либо переходить к изучению более частных задач и поискам для них малотрудоемких алгоритмов, либо строить приближенные алгоритмы. Отсюда возникает подход к алгоритмическим проблемам, который получил название лалгоритмы с оценками [15]. Речь идет о векторной оценке качества алгоритмов. Критериями, т.е. компонентами этой векторной функции (т.е. оценки) являются вычислительная сложность, точность, объем памяти, размер области, в пределах которой почти всегда на выходе алгоритма получается искомое решение (МА), и т.д. Обосновать какой-либо результат для той или иной задачи Z в самом общем ее виде, как правило, затруднительно. Желаемое обоснование удается получить обычно в предположении, что выполняются те или другие ограничения, условия. Например, задачу Z n о коммивояжере можем рассматривать только на полных графах или в предположении, что веса ребер ограничены независящей от n константой, и т.д. Иными словами, рассматривая задачу Z при тех или иных ограничениях (условиях) мы рассматриваем тот или иной класс K индивидуальных задач нашей задачи Z. Не опасаясь возможных недоразумений, в дальнейшем вместо выражения класс индивидуальных задач K будем говорить класс задач K и считать, что он состоит из элементов, т.е. индивидуальных задач, обозначаемых символом z. При этом, не оговаривая особо, подразумеваем, что ВЦФ, а также искомое МА заданы, т.е. они тоже рассматриваются в качестве заранее оговоренных условий, определяющих класс K. Вначале сформулируем определения в терминах дискретной оптимизации. Пусть K - некоторый класс однокритериальных задач, L(z ) - оптимальное значение целевой функции для задачи z K. Будем считать, что рассматриваются задачи на минимум и L(z ) > 0 для всех z K. Рассмотрим теперь некоторый алгоритм, который может быть применен к любой задаче z класса K, так что результатом этого применения является допустимое (не обязательно оптимальное) решение задачи z со значением целевой функции L (z ). При этом не исключается, что применение алгоритма к некоторым задачам из K может оказаться безрезультатным. Если получено допустимое решение задачи z, то качество решения данной задачи может быть оценено величиной L ( z ) L( z ) L (Z ) (4.27) относительным уклонением от оптимума L ( z ) значения целевой функции, полученного в результате применения алгоритма. Задаваясь некоторым 0, можно определить множество задач K = {z K : L (z ) (1 + )L( z )}, (4.28) для которых относительная погрешность получаемых алгоритмов решений не превышает заданной величины. Набор множеств K для разных 0 мог бы служить достаточно полной характеристикой алгоритма с точки зрения точности получаемых решений. Это, в свою очередь, позволяло бы сравнивать разные алгоритмы по указанным наборам множеств. Но трудность такого подхода к сравнению алгоритмов заключается в том, что практически мы, как правило, не имеем возможности получить простое описание множеств K в явном виде.
В подобной ситуации не остается ничего иного, как пытаться использовать различные возможности косвенного описания, находить какие-то нетривиальные характеристики этих множеств. В качестве таких характеристик 0 можно, например, рассматривать меры множеств K относительно различ ных вероятностных распределений на классе K, что и осуществляется одним из возможных способов. Пусть заданы класс задач K и некоторое семейство вероятностных мер, определенных на K. Будем говорить, что алгоритм имеет тип (, ) относительно, если вероятность P{L ( z ) (1 + )L( z )} 1, (4.29) для всех P. Как было сказано ранее, каждый класс задач можно описать с помощью некоторых параметров, и на практике, говоря об алгоритме решения задач этого класса, интересуются свойствами алгоритма в зависимости от этих параметров. В качестве таких параметров часто применяют величины, характеризующие размерность задачи, вкладывая в это понятие всякий раз свой смысл. Например, говорят о классе K n задач коммивояжера с n городами. Здесь число n выступает в качестве основного параметра класса задач. В связи с этим будем далее говорить о классах K (n ) семейства (n ), оценках ( (n ), (n )) и их свойствах в зависимости от параметра n.
Алгоритм с оценками ( (n ), (n )) относительно семейства распределений (n ) будем называть асимптотически точным относительно (n ), если ( n ) 0 и ( n ) 0 при n.
0 Пусть q - алгоритм нахождения ПМА для некоторой задачи Z q с по0 ложительно определенной ВЦФ, например (3.1), причем q не гарантирует получение точного решения, т.е. не для всех индивидуальных задач на выходе алгоритма получаем МА, содержащее искомое ПМА. Обозначим через 0 X * = {x* } результат применения q к некоторой индивидуальной задаче рас сматриваемой задачи Z q. Будем говорить, что если F (X 0 ) \ F (X * ), то X * аппроксимирует искомое ПМА X 0. При этом аппроксимацию понимаем в общепринятом смысле как замену одного математического объекта (в данном случае ПМА X 0 ) другим (в данном случае подмножеством X * ). Рассматривая некоторую задачу Z, представим ее в виде совокупности U{Z } n = n множеств {Z }n индивидуальных задач размерности n. При этом счита ем выполненным естественное условие монотонного возрастания мощности {Z }n с ростом n. Пусть {Z } {Z }n представляет собой подмножество таких n индивидуальных задач из множества {Z }n, каждая из которых обладает определенным свойством. Например, для каждого представителя из {Z } данn ный алгоритм находит оптимум. Тогда говорим, что почти всегда (или почти все) индивидуальные задачи рассматриваемой задачи Z обладают свойством, если lim {Z } / {Z }n = 1. n n Пусть l (z ) обозначает длину входных данных некоторой задачи z K. Алгоритм статистически эффективен в классе K, если: он почти каждую задачу z K решает (находит требуемое МА) точно;
его вычислительная сложность полиномиальна по l (z ) для почти всех z K.
Сначала заметим, что в некотором смысле сформулированная выше задача о 4- циклах аналогична известной задаче о 3-сочетаниях [45], в которой допустимое решение представляет собой покрытие исходного графа 3вершинными циклами. Задача о 3-сочетаниях является NP-трудной [45], вследствии чего для нее к настоящему времени неизвестны полиномиальные алгоритмы. Этот факт можно рассматривать в качестве косвенного довода для утверждения об NP- трудности задачи покрытия графа 4-циклами. В случае своей многокритериальной постановки [5] задача о покрытии графа 4-циклами является труднорешаемой в том смысле, что вычислительная сложность нахождения искомого множества альтернатив растет экспоненциально с ростом размерности задач. Строгое обоснование этого факта на представленное ниже вспомогательное утверждение относящееся к задаче покрытия n вершинного графа типовыми h вершинными подграфами доказана в [53].
Лемма 4.3. Для всякого h < n, n кратно h величина мощности МДР с ростом n не ограничена сверху никаким полиномом от n. Рассматривая проблему перебора всех допустимых решений рассматриваемой дискретной задачи, на основании леммы 4.3 сформулируем следующее утверждение.
Лемма 4.4. Перебор в худшем случае всех допустимых покрытий пол ного графа 4-циклами не ограничен сверху никаким полиномом от n, т.е. растет экспоненциально с ростом размерности задачи. В п.4.4 доказано, что если ВЦФ (3.1) содержит не менее двух критериев вида MAXSUM, то для всякого графа G можно подобрать веса ребер так, что будет иметь место совпадение ПМА с множеством всех покрытий, т.е. будет выполняться равенство X 0 = X = X (свойство полноты). Тогда с учетом терминологии [17,45], из лемм 4.3 и 4.4 вытекает Теорема 4.4. Векторная задача о покрытии графа 4-циклами является ~ труднорешаемой, т.е. вычислительная сложность нахождения ее ПМА растет экспоненциально с ростом размерности задачи, если ее ВЦФ содержит хотя бы пару критериев весового вида (3.2). Хотя в худшем случае мощность ПМА X 0 экспоненциальна, тем не менее, можно показать, что доля таких плохих случаев стремится к нулю с ростом размерности задачи. При этом оказывается, что почти всегда мощность ПМА X 0 = 1 и можно предложить быстрый алгоритм, который почти всегда находит ПМА [15]. Другими словами, для некоторых постановок многокритериальной задачи покрытия графа 4-циклами вычислительная сложность нахождения ПМА почти всегда полиномиальна. С учетом вышесказанного для рассматриваемой задачи покрытия графа 4-циклами является актуальной проблемой построение такого малотрудоемкого (полиномиального) приближенного алгоритма, для которого становится возможным представить строгое обоснование оценок его эффективности: точности, вычислительной сложности и т.д. Такие методы принято называть термином лалгоритмы с оценками [17]. Среди алгоритмов с оценками особый интерес представляет так называемые статистически эффективные алгоритмы [45]. Нестрого говоря, приближенный алгоритм называется статистически эффективным, если при определенных условиях он почти всегда приводит к нахождению искомого оптимума.
4.6. Оценки точности приближенных алгоритмов Говоря о приближенных алгоритмах, т.е. об алгоритмах с оценками [15], основное внимание сосредоточим на двух показателях эффективности алгоритма - точность и трудоемкость. Чаще всего точность выражается через погрешность. Как известно, существуют две формы определения этого показателя - лабсолютная погрешность и лотносительная погрешность. В дальнейшем будем придерживаться второй формы. Ее смысл для оптимизационной задачи состоит в том, что сначала вычисляется абсолютная погрешность как величина уклонения значения ЦФ на получаемом решении от значения ЦФ на оптимальном решении. После чего относительная погреш ность вычисляется в виде отношения этого уклонения к оптимальному значению ЦФ. При этом подразумевается, что указанное оптимальное значение является строго положительным. Понятие точность решения векторной задачи обобщает это же понятие для оптимизационной, т.е. 1-критериальной задачи и вместе с тем нуждается в уточнении. Говоря о приближенном решении векторной задачи с ВЦФ F ( x ) = (F1 ( x ), F2 ( x ),..., FN ( x )), подразумеваем в общем случае определенное под множество X * X такое, что его мощность X * = F ( X * ). Абсолютная погрешность решения X * представляется в виде вектора вычисляемых оценок:
( X * ) = 1 ( X * ),..., ( X * ),..., N ( X * ) ( % ), где ( X ) = max min F ( x ) F ( x ), = 1, N. От * xX * % xX * носительная погрешность по критерию F ( x ) extr определяется в виде отношения = (X * ) = 1 X * a ( ), 1 N, где a - значение критерия F ( x ) на оп тимальном решении x 0 : a = F (x 0 ). Относительная погрешность решения X * определяется как вектор = (X * ) = ( 1, 2,..., N ). Если значение = 0, то говорим, что полученное решение является оптимальным по критерию F (x ).
4.7. Приближенный алгоритм покрытия графа 4-циклами Предполагаемый ниже алгоритм условимся обозначать через. Работа алгоритма состоит из подготовительного этапа, четырех вычислительных этапов и заключительного этапа формирования результатов. Подготовительный этап заключается в том, что в данном n - вершинном графе G = (V, E ) множество V разбивается на четыре равномощных подмножества Vs мощности Vs = m =, s = 1,4. Заметим, что по условию задачи всегда рассматривается случай n кратно 4. Далее, для двух пар V1,V2 и V2,V3 строятся два двудольных графа Gst = (Vs,Vt, Est ), 1 s < t 3, где множество Est n состоит из всех таких ребер e = (v, v) E, у каждого из которых один конец v Vs, а другой конец v Vt.
Второй этап состоит из двух вычислительных подэтапов. Работа этих подэтапов состоит в том, что в каждом из двудольных графов G12 и G 23 осуществляется нахождение оптимальных совершенных паросочетаний, которые обозначим соответственно через M 12 и M 23. Для нахождения каждого из таких паросочетаний M st = {e} можно воспользоваться каким-либо известным алгоритмом [71], например, либо венгерским алгоритмом, либо более экономным алгоритмом Лоулера [45]. Объединяя паросочетания M 12 и M 23, получаем m пар пересекающихся рёбер вида e = (v1, v 2 ), e = (v 2, v 3 ),. Такие пары рёбер объединяем в 3 вершинные цепи вида c = [v1, v2, v3 ], множество этих цепей обозначим C = {c}.
V V V G1 2 = (V1,V2, E1 2 ) G2 3 = (V2,V3, E2 3 ) Рисунок 4.16. Результат работы 1-го и 2-го этапов работы алгоритма Третий этап состоит в построении специального двудольного графа D = (V 4, B, ) с равномощными долями мощности V4 = B = m. Доля B = {b}со стоит из вершин b B, которые поставлены во взаимнооднозначное соответствие цепям с С. Если ребро 0 = (v0, b) содержится в, то оно определяется следующим образом: ребро 0 = (v0, b) включается в состав тогда и толь ко тогда, когда в исходном графе G = (V, E ) множество E содержит пару рёбер e и e, следующего вида:
e = (v 0, v1 ), e = (v 0, v 3 ), (4.30) где v1 и v3 являются висячими вершинами цепи c = [v1, v 2, v 3 ], (4.31) поставленной в соответствие вершине b. При этом ребру 0 приписывается вес W ( 0 ) = w(e ) + w(e ).
Рисунок 4.17. Результат 3-4-го и заключительного этапов работы алгоритма Если же пара рёбер e, e, удовлетворяющая указанным условиям (4.30) и (4.31) отсутствует в данном графе G, то соответственно ребро 0 не включается в множество. Четвертый вычислительный этап состоит в том, что с помощью соответствующего алгоритма [45] в двудольном графе D = (V, B, ) выделяется оптимальное паросочетание M 4 = {}.
Примечание 4.4. Согласно определению 3-го этапа определяемая вы ражением (4.30) пара рёбер e и e образует цепь вида c = [v1, v 0, v 3 ], которая замыкает соответствующую цепь c = [v1, v 2, v 3 ] вида (4.31) в 4-вершинный цикл c = [v1, v 0, v 3, v 2 ].
Заключительный этап алгоритма состоит в том, что согласно примечанию 4.4 для каждого ребра, принадлежащего выделенному паросочетанию M 4, в графе G выделяется соответствующая ему пара рёбер e и e, которая замыкает соответствующую цепь c = [v1, v 0, v 3, v 2 ].
c = [v1, v 2, v 3 ] в 4-вершинный цикл Работа алгоритма завершается проверкой, все ли вершины исходного графа G оказались покрытыми выделенными 4-циклами. В случае положительного исхода множество выделенных циклов представляется в виде допустимого решения задачи о покрытии графа 4-циклами.
4.8. Обоснование достаточных условий статистической эффективности алгоритма В дальнейшем будем использовать следующие обозначения:
= (n n ) - сколь угодно медленно растущая функция от n такая, что lim (n ) =, например, = ln ln n ;
G (n, p ) - вероятностный n - вершинный граф, в котором для каждой па ры вершин v, v V ребро e = (v, v) появляется с вероятностью р и не появляется с вероятностью q = 1 p, независимо от других ребер;
G st (m, p ) - вероятностный двудольный граф с равномощными долями Vs,Vt, Vs = Vt = m, в котором для каждой пары вершин v V s, v Vt ребро e = (v, v) появляется с вероятностью p, и не появляется с вероятностью q = 1 p ;
(n, R ) = {G}- множество всех п - вершинных графов G = (V, E ), в каждом из которых всякому ребру e E, приписан вес w(e ) {1,2,3,..., R} ;
st (m, R ) = {(Vs,Vt, R )} - множество всех двудольных графов Gst = (Vst,Vt, Est ) с равномощными долями Vs = Vt = m, у которых каждому ребру e Est приписан вес w(e ) {1,2,3,..., R}.
Осуществляя вероятностный анализ алгоритма, рассмотрим вероятностный граф G = (n, p ), в котором выделены два вероятностных двудольных подграфа G st (m, p ), 1 s < t 3. Если в этом графе или его подграфе содержится некоторое допустимое решение x с вероятностью P 1, = (n) 0 при n, то в этом случае принято говорить, что вероятностный граф почти всегда содержит указанное решение x. Применим алгоритм к вероятностному графу G = (n, p ) и оценим значение вероятности P, при которой каждый из вычислительных этапов алгоритма почти всегда окажется результативным.
Лемма 4.5. Если в графе G = (n, p ) вероятность p появления ребра удовлетворяет неравенству p 4 ln n +, n (4.32) то почти всегда каждый из подэтапов второго этапа алгоритма окажется результативным, т.е. с вероятностью P 1 (n), lim (n) = 0 в двудольном подn графе G st (m, p) будет выделено совершенное паросочетание. Доказательство. Рассматривая последовательность множеств двудольных графов st (m, R ) = {(Vs,Vt, R )}, m = 1,2,..., будем обозначать через k = k (m ) число рёбер в двудольных графах из st (m, R ). Кроме того, условимся говорить, что Уграф обладает свойством Ф, если в этом графе содержится совершенное паросочетание тогда и только тогда, когда k = k (n ) = n(ln n + ), = O( ). В [31] установлена связь между числом k и вероятностью P, при которых обеспечивается выполнение всякого монотонного по рёбрам свойства для почти всех графов G st (m, R) и почти всегда с вероятностью P 1 (n), lim (n) = 0, для вероятностного графа G (n, p). Согласно этому из теоремы 1 в n [30] вытекает, что почти всегда G st (m, R) обладает свойством, если P = ( R + 1) 1 (ln m + ) / m n (4.33) Заметим, что в случае lim (n) = является справедливым равенство + c = O( ), (4.34) где c - константа, которая не зависит от аргумента m функции = (т). Поскольку m =, то с учетом (4.34) неравенство (4.33) можно переписать в виде (4.32). Лемма 4.5 доказана. Обратимся к описанию алгоритма и через 2 обозначим второй подэтап алгоритма. Напомним, что в применении к графу G (n, p) в процессе работы этапа 2 осуществляется выделение в двудольных подграфах n G12 = G12 (m, p ) и G23 = G 23 (m, p) совершенных паросочетаний. Работу этого этапа условимся называть результативной, если указанные паросочетания будут выделены и в результате объединения пересекающихся пар рёбер этих паросочетаний получим множество C = {c}, состоящее из m 3- вершинных цепей.
Лемма 4.6. Если вероятностный граф удовлетворяет условиям леммы 4.3, то в результате применения к нему этапа 2 почти это применение всегда окажется результативным. Для доказательства леммы 4.6 с учетом леммы 4.5 достаточно заметить, что n lim(1 (n)) (1 (n)) = 1, если (n), (n) 0, при n.
Обратимся к описанию третьего этапа, который обозначим через 3. Применим 3 к вероятностному графу G (n, p). Тогда результатом работы этапа 3 является специальный двудольный вероятностный граф, который также обозначим через D = (V, B, ). Здесь множество рёбер будет содержать ребро 0 = (v0, b) тогда и только тогда, когда в графе G (n, p) появится соответст вующая пара рёбер (4.30). Поскольку, вероятность появления каждого из этих рёбер является независимым событием, то эта пара появляется с вероятностью p 2 и, следовательно, вероятность появления ребра 0 в множестве равна P ( 0 ) = P ( 0 ) = p 2.
(4.35) Обозначим через 4 четвертый этап алгоритма. Из определения этапов 2, 3, 4 и вероятностного графа D с учетом леммы 4.5 и равенства (4.35) вытекает, что является справедливой Лемма 4.5. Если в графе G (n, p) вероятность появления всякого ребра удовлетворяет неравенству p 4 ln n +, n (4.36) то почти всегда этап 4 окажется результативным. Поскольку из выполнения неравенства (4.36) вытекает неравенство (4.32), то из определения всех этапов алгоритма получаем, что является справедливой следующая Лемма 4.6. Если в графе G (n, p) вероятность появления всякого ребра удовлетворяет неравенству (4.36), то почти всегда применение алгоритма к вероятностному графу G (n, p) окажется результативным, т.е. с вероятностью P 1 (n), lim (n) = 0 на выходе алгоритма будет получено покрытие данного n n-вершинного графа 4-циклами.
Согласно [15] (теорема 1) существует следующая взаимосвязь между вероятностным графом G (n, p) и множеством (n, R). Если при выполнении неравенства (4.36) граф G (n, p) обладает свойством, то почти каждый граф из G (n, R) обладает этим свойством в том случае, когда выполняется неравенство R2 n. 4 ln n + (4.37) Отсюда получаем, что является справедливой следующая Теорема 4.5. При выполнении неравенства (4.37) алгоритм является статистически эффективным. Для завершения доказательства теоремы 4.5 остается лишь заметить, что в процессе своей работы алгоритм рассматривает каждое ребро данного графа G = (V, R) не более нескольких раз, откуда вычислительная слож ность его первых трех этапов составляет O( E ) O(n 2 ). Отсюда вычислительную сложность алгоритма можно оценить через вычислительную сложность четвертого этапа (нахождения совершенного паросочетания [45]:
( ) O(n 2 ) + O(n 3 ) = O (n 3 ) Выводы 1. В качестве конкретной математической модели землепользования представлена математическая формулировка интервальной экстремальной задачи покрытия графа 4-циклами. 2. Основные результаты исследований главы 4 относятся к алгоритмическим вопросам решения рассматриваемых задач землепользования в условиях неопределенности. 3. Основное внимание уделено исследованию вычислительной сложности и разрешимости с помощью алгоритмов линейной свертки критериев задачи покрытия графа 4-циклами. 4. Получена аппроксимация интервальной задачи покрытия графа 4циклами соответствующей векторной задачей, доказана неразрешимость этой задачи;
доказана неразрешимость с помощью алгоритмов линейной свертки критериев. 5. В качестве основного результата исследования вычислительной сложности рассматриваемых векторных задач на графах осуществлено строгое обоснование достаточных условий наличия в них свойства полноты и, как следствие принадлежности этих задач к классу труднорешаемых. 6. Основным результатом также является построение малотрудоемкого алгоритма для оптимизационной задачи покрытия графа 4-циклами и обоснование достаточных условий, при которых этот алгоритм является статистически эффективным.
ЗАКЛЮЧЕНИЕ 1. Сформулирована автоматическая концепция 2-уровневого моделирования задач землепользования: математическая модель верхнего уровня - это модель теории оптимизации, на базе которой строится и обосновывается наиболее целесообразное управление рассматриваемой системой или процессом;
на нижнем уровне осуществляется моделирование исходных данных для модели верхнего уровня;
исходными данными для нижнего уровня служат временные ряды, отражающие эволюцию основных показателей рассматриваемых эволюционных процессов и систем;
изложена необходимость многокритериального подхода и суть его реализации. 2. На базе инструментария фрактального анализа выявлены такие свойства временных рядов, как долговременная память с оценкой ее глубины, трендоустойчивость, квазицикличность;
для обновления этих свойств разработан метод фазового анализа временных рядов;
на базе инструментария линейных клеточных автоматов и нечетких множеств разработана новая прогнозная модель, включая ее верификацию, а также алгоритмы валидации и вычисления оценок точности прогнозирования. 3. В качестве конкретной реализации 2-уровневого моделирования представлена математическая постановка экстремальных задач покрытия графа 4-циклами (паросочетаниями, звездами);
показана непригодность известных в научной литературе определений операции сложения и сравнения нечетких весов;
разработано новое определение операции суммирования и сравнения нечетких весов, которые адекватны рассматриваемым задачам землепользования. 4. Исследована на разрешимость с помощью алгоритмов линейной свертки критериев (АЛСК) векторная задача покрытия графа 4-циклами с интервальными весами;
осуществлено ее сведение к 2-критериальной задаче и установлена ее неразрешимость.
5. Разработан малотрудоемкий алгоритм покрытия графа 4-циклами и доказано достаточное условие, при которых он является статистически эффективным.
ЛИТЕРАТУРА 1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. - M.: Мир, 1987. - 360 с. 2. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. - Тюмень: Изд-во ТюмГУ, 2000. - 352 с. 3. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с. 4. Баккет М. Фермерское производство: организация, управление, анализ.М.: Агропромиздат, 1989. - 464 с. 5. Батищев А.Ф., Перепелица В.А. Об одном алгоритме нахождения оптимального севооборота //Оптимизация планирования. 1970 16. C. 16-20. 6. Беляева И.П. Практические приложения интервального анализа // В - СО АН СССР. - Переславль - Залесский, 1988.- 156 с. 7. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учебное пособие. - М.: Финансы и статистика, 2001. - 368 с. 8. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. - Новосибирск: Наука, 1978.-333 с. 9. Борисов А.Н., Алексеев А.В., Меркурьева Г.В. Обработка нечеткой информации в системах принятия решений. - М.: Радио и связь, 1989.- 304 с. 10. Буров Д.И., Чуданов И.А. Некоторые вопросы плодородия черноземных почв в связи с освоением пропашных севооборотов. В сб. Гидрофизика и структура почвы. Вып. 11. - Л.: Гидрометеорологическое изд-во, 1965. - С.196-204. 11. Векленко В.И. Экономическая проблема устойчивости и повышения эффективности земледелия.- Курск: Изд-во Курской сельскохозяйственной академии, 1999.- 216 с. 12. Винтизенко И.Г. Детерминированное прогнозирование в экономических системах // Труды III международной конференции Новые технологии в управлении, бизнесе и праве, Невинномысск: Издательство ИУБП, 2003. - С.163-167 13. Возбуцкая А.Е. Химия почвы.- 3-е изд., исправленное и дополненное. Под ред.проф. Д.Л. Аскинази.- М.: Высшая школа, 1968.- 427 с. 14. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. М., 1989. 15. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Об одном приближенном алгоритме с апосториорной оценкой точности решения для задачи размещения. В сб. Оптимальное планирование в отраслях промышленного производства.-Ч.1.-Новосибирск: ИЭОПП СО АН СССР, 1974.- С.102-110. 16. Гирлих Э., Ковалев М.М., Кравцов М.К., Янушкевич О.А. Условия разрешимости векторных задач с помощью линейной свертки критериев //Кибернетика и системный анализ. 1999. № 1. C. 81 -95. 17. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.- 416 с. 18. Дементьев В.Т., Ерзин А.И., Ларин Р.М., Шамардин Ю.В. Задачи оптимизации иерархических структур. - Новосибирск: Изд-во Новосиб. ун-та, 1996. - 167 с. 19. Долятовский В.А. Переход от хаоса к порядку в экономике: роль хаотических процессов в формировании организации. - В сб. российский менеджмент на пороге 21 в. - Краснодар: ЮРИМ, 1997. - 33-46. 20. Долятовский В.А., Касаков А.И., Коханенко И.К. Методы эволюционной и синергетической экономики в управлении. - Отрадная: Изд-во РГЭУ - ИУБиП - ОГИ, 2001. - 577 с. 21. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 384 с. 22. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах//Журн. Выч. Математики и мат. физики.-1989.-Т.29, №2.- С.171-183.
23. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач//Дискретная математика. - 1994. - Т.6, №1. - С.3-33. 24. Жирабок А.Н. Нечеткие множества и их использование для принятия решений // Соровский образовательный журнал. - 2001.- Том 7, №2. - С. 109-115. 25. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приближенных решений. М: Мир, 1976, 165 с. 26. Занг В.-Б. Синергетическая экономика. Время и перемены в нелинейной экономической теории. М.: Мир, 1999.-335 с. 27. Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, Сибирское отделение, 1986.-224 с. 28. Ким-Гю-Пхир. Оптимальное распределение ресурсов в условиях интервальной неопределенности. - М.: Наука, 1992. - 256 с. 29. Козина Г.Л., Рябовол Л.Д., Захарова А.В. основы интервального исчисления.-Запорожье: Изд-во ЗГУ, 1996. - 47 с. 30. Коршунов А.Д. Об одном алгоритме нахождения паросочетаний в конечных графах // Кибернетика. - 1975. - №1. - С. 1-8. 31. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер // Успехи матем. наук. - 1985. - Т.40, №1 (241).- С.107-173. 32. Кравцов М.К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев //Дискретная математика. - 1996. - 8, № 2. - C. 89-96. 33. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. - М.: ЮНИТИ - ДАНА, 2000. - 543 с. 34. Курдюмов С.П., Малинецкий Г.Г., Потапов А.Б. Нестационарные структуры, динамический хаос, клеточные автоматы. В сб. Новое в синергетике. Загадки мира неравновесных структур. - М.: Наука, 1996. - С. 95-164. 35. Ларичев О.И. Наука и искусство принятия решения. - М.: Наука, 1979.- 200 с. 36. Лопатников Л.И. Экономико-математический словарь. - М.: Наука, 1987. - 510 с. 37. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику: Учебное руководство. - М.: Наука, 1990. - 240 с. 38. Малинецкий Г.Г., Потапов А.Б. Нелинейность. Новые проблемы, новые возможности. В кн. Новое в синергетике. Загадки мира неравновесных структур. - М.: Наука, 1996. ЦС. 165-190. 39. Месарович М., Мако Д., Такахара И. Теория Иерархических многоуровневых систем. - М.: Мир, 1973. - 344 с. 40. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно транспортного планирования.- М.: Наука, 1986.- 264 с. 41. Назаренко Т.И., Марченко Л.В. Введение в интервальные методы вычислительной математики. - Иркутск: Изд-во Иркутского университета, 1987. - 107 с. 42. Нейман Дж. Теория самовоспроизводящихся автоматов. - М.: Мир, 1971. - 378 с. 43. Оре О. Графы и их применение. - М.: Мир, 1965. - 173 с. 44. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. - М.: Наука, 1981. - 203 с. 45. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.- М.: Мир, 1985.- 512 с. 46. Пасов В.М. Синоптико-статистический метод прогнозирования зерновых культур// Методология и гидрология. - 1992. - №10. - С.77-84. 47. Перепелица В.A., Cepгиенко И.В, Исследование одного класса целочисленных многокритериальных задач //Журнал вычисл. матем. и матем. физики. - 1988. - 28, № 3. - C. 400-419. 48. Перепелица В.А., Касаева М.Д, Темирова Л.Г. Прогнозная модель урожайности на базе линейного клеточного автомата // Современные аспекты экономики - 2003. - №4(32). - С.190-206. 49. Перепелица В.А., Мамедов А.А. Исследование сложности и разрешимости векторных задач на графах: Уч. пособие. Черкесск, 1995.- 68 с.
50. Перепелица В.А., Попова Е.В. Математическое моделирование экономических и социально- экологических рисков. - Ростов н/Д.: Изд-во Рост. ун-та, 2001. - 126 с. 51. Перепелица В.А., Салпагаров С.И., Тебуева Ф.Б. Точные алгоритмы для задач покрытия графов звездами и цепями //Известия вузов. СевероКавказский регион.- Ростов: №1, 2002.- С.63-74. 52. Перепелица В.А., Сергеева Л.Н. Исследование неразрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач //Кибернетика и системный анализ. - 1996. - № 2. - C. 71-77. 53. Перепелица В.А., Тебуева Ф.Б. Агроэкономическая задача покрытия графа звездами // Тезисы докладов Седьмой международной конференции Математика. Компьютер. Образование. - Дубна, 2002. Ц163 с. 54. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г, Касаева М..Д. Построение прогнозной модели урожайности на базе клеточных автоматов и нечетких множеств / Менеджмент, экономика и финансы, региональное управление. Труды III Международной научно-практической конференции Проблемы регионального управления, экономики, права и инновационных процессов в образовании, г. Таганрог, 10-13 сентября 2003 г. - Таганрог: Изд-во Таганрогского института управления и экономики, 2003. - С.182185. 55. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Дискретное программирование с нечеткими данными. Сб.науч.трудов V Всероссийского симпозиума. Математическое моделирование экономических и экологических систем, г. Кисловодск, 17-19 октября 2002г. - Кисловодск: Изд.центр КИЭП, 2002. - С.7-10. 56. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Математическая модель землепользования на базе нечетких множеств и клеточных автоматов Электронный журнал Исследовано в России- 207- 2003.- С. 2429-2438 zhurnal.ape.relarn.ru/articles/003/207.pdf 57. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Моделирование экстремальных задач на графах с нечеткими данными // Труды участников Международной школы-семинара по геометрии и анализу памяти Н.В. Ефимова, Абрау-Дюрсо, 5-11 сентября 2002 г. /МГУ, РГУ. - Ростов-на-Дону, 2002. - С. 267. 58. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Фрактальный анализ устойчивости развивающихся агросистем. Материалы III Международной научно-практической конференции Математическое моделирование в образовании, науке и производстве. - Тирасполь, 17-20 сентября, 2003 г. - Тирасполь: РИО ПГУ, 2003. - С.56-59. 59. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Использование инструментария клеточных автоматов для формирования прогнозных нечетких значений урожайностей на базе временного ряда //Известия вузов - Ростов-на-Дону.- 2003.- №4.- С.67-76. 60. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М..Д. Об одном подходе к оценке глубины фрактальной памяти временных рядов урожайностей.- Нальчик (Международный Российско-Узбекский симпозиум) Уравнения смешанного типа и родственные проблемы анализа и информатики, п.Эльбрус, 21-25 мая 2003 г./ КБГУ.- Нальчик.- 2003. 61. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Прогнозная модель урожайности на базе клеточных автоматов и нечетких множеств //Труды III международной конференции Новые технологии в управлении, бизнесе и праве. НФ ИУБиП г.Невинномыск, 30 мая 2003. - С. 163167. 62. Перепелица В.А., Ф.Б.Тебуева, Темирова Л.Г. Новый метод прогнозирования на базе клеточных автоматов и нечетких множеств. / Тезисы докладов VIII Международной конференции серии Нелинейный мир, г. Астрахань, 15-20 сентября 2003г. - Астрахань: ГУП Издательскополиграфический комплекс Волга, 2003.-С.240. 63. Перепелица В.А., Ф.Б.Тебуева, Темирова Л.Г. Об одной задаче землеполь зования в условиях неопределенности. Математические методы и информационные технологии в экономике, социологии и образовании: Сборник статей X Международной научно-технической конференции.- 24-25 декабря 2002 г. - Пенза, 2002 - С. 69-71. 64. Петерс Э. Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка. - М.: Мир, 2000. - 333 с. 65. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.Наука, 1982.- 256 с. 66. Пригожин И., Стингерс И. Порядок из хаоса. Новый диалог человека с природой. - М.: Прогресс, 1986. 67. Прикладные нечеткие системы. Под редакцией Т.Тэрано, К.Асаи, М.Сугэно. - М.: Мир, 1993. - 368 с. 68. Рощин В.А., Семенова Н.В., Сергиенко Н.В. Декомпозиционный подход к решению некоторых задач 5. - C. 789-791. 69. Рюэль Д., Такенс Ф. О природе турбулентности// Странные аттракторы. - М.;
1991, С.117-151. 70. Сакович В.А. Исследование операций: Справочное пособие.1985.- 256 с. 71. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. - М.: Мир, 1984. - 455 с. 72. Сергеева Л.Н. Моделирование поведения экономических систем методами нелинейной динамики (теории хаоса). - Запорожье: ЗГУ, 2002. - 227 с. 73. Сигел, Эндрю. практическая бизнес-статистика.: Пер. с англ. - М.: Издательский дом Вильямс, 2002. - 1056 с. 74. Суслов О.П., Кудина Т.М. Моделирование формирования иерархической структуры систем управления // Машинная обработка информации. - Киев: Ин-т нар.хоз-ва, 1988.- № 46. - С.116-126. 75. Темирова Л.Г. Полиномиально разрешимый подкласс теоретико-графовой Минск, целочисленного программирования с неточными данными //Журнал вычисл. матем. и матем. физики. - 1990. - 29, № модели для задачи землепользования. Тезисы II Международной конференции Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. КБН - РАН, 3-7 декабря 2001 г. - Нальчик, 2001. - С.45-46. 76. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи формирования целевых групп. Материалы Северо-Кавказской региональной научной конференции молодых ученых, аспирантов и студентов Перспектива-2001.-Нальчик, 2001.- С.191-198. 77. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи землепользования // Современные аспекты экономики. - Санкт-Петербург. - 2002 г.- №15(28). - С.47-56. 78. Темирова Л.Г., Петова Е.Х. Об одном подходе к моделированию процесса формирования состава малых групп. Решение научно-технических и социально-экономических проблем современности // Сборник трудов IV научно-практической конференции. Часть II, КЧГТИ.- Черкесск, 2002. - С 4244. 79. Тимошенко П.Н., Яковенко В.С. Экономические циклы - новые подходы к обнаружению, анализу, прогнозированию. Циклы. Материалы пятой Международной конференции. Том 1. - Ставрополь: Изд. СевероКавказского государственного технического университета, 2003. - С.87-90. 80. Федер Е. Фракталы. - М.: Мир, 1991. - 260 с. 81. Шокин Ю.И. Интервальный анализ // В - СО АН СССР.- Новосибирск, 1988.- 137 с. 82. Шустер Г. Детерминированный хаос: Введени. - М.: Мир, 1988. - 240 с. 83. Яновский Л.П. Принципы, методология и научное обоснование урожая по технологии Зонт. - Воронеж: ВГАУ, 2000.-379 с. 84. Cootner P. УComments on the Variation of Certain SpeculativePricesФ, in P. Cootner ed. The Random Chaacter of Stock Market Prices. Cambridge:MIT Press, 1964 a. 85. Holden K., Peel D.A. and Thompson J.L. - Press Syndicate of the University of Cambridge, 1990. - P. 231. 86. Kuchert W.Y.M. and oth. Aplication of Fuzzy Controller in a Warm Water Plent. УAutomaticaФ, v.12, №4, 1976, Р.301-308. 87. Lodwick A.W. Special Issue on the Linkages Between Interval Mathematics and Fuzzy Set Theory // Reliable Computing. - 2002. - Volume 8 - P. 93-95. 88. Mandelbrot B. The Fractal Geometryof Nature. New York: W.H.Freeman, 1982. 89. Packard N., Cruthfield I., Forman D., Shaw R. УGeometry from a Time SeriesФ, Phisical Review Letters 45, 1980. 90. Perepelitsa V.A. and Kozina G.L. Interval Discrete Models and Multiobjectivity. // Interval computations. - 1993. - №1. - P. 51-59. 91. Scheikman J.A., LeBaron B. УNonlinesr Dinamics and Stock ReturnsФ. Journa of Business 62, 1989. - P. 311-337/ 92. Zadeh L.A. Fuzzy sets. - Inf. Contr., 1965, 8, P.338-353.
Приложение Исходные данные для точек абсциссы zi и ординаты z i на базе статистических данных озимой пшеницы по КБР с 1952 по 2002 гг. Таблица П2.1 Годы 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 zi 13,1 7,5 8,3 7 13 13,9 15,7 14,1 18,8 12,7 22 18,1 13,9 15,4 18,6 24,4 25, z i -5,6 0,8 -1,3 6 0,9 1,8 -1,6 4,7 -6,1 9,3 -3,9 -4,2 1,5 3,2 5,8 0,7 -4,6 z i Годы 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 zi 20,5 27,1 29,1 21,9 29,3 18,3 21,9 30,9 26,7 26,9 30,1 29,1 27,5 22,5 27,1 24,2 21, z i 6,6 2 -7,2 7,4 -11 3,6 9 -4,2 0,2 3,2 -1 -1,6 -5 3,2 -1,5 -3,1 12, Годы 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 zi 33,9 26,8 32,8 36,2 44,3 36,4 28,7 26,4 30,3 33,4 28,1 25,5 18,9 28,4 25,5 31,2 32, z i -7,1 6 3,4 8,1 -7,9 -7,7 -2,3 3,9 3,1 -5,3 -2,6 -6,6 9,5 -2,9 5,7 1, 15 10 5 0 0 -5 -10 - zi 10 20 30 40 Рис.П2.1. Фазовый портрет вида F ( z ) = {( z i, z i )} временного ряда урожайности озимой пшеницы по Кабардино-Балкарии за период с 1952 по 2002 гг.
8 6 4 2 0 -2 0 -4 - 10 5 -5 - 15 10 5 0 -5 0 -10 - 4 2 0 -2 26 10 20 30 40 -4 - 15 10 10 5 0 0 - - - 6 4 2 0 -2 0 -4 - 15 10 10 20 30 0 -5 0 - Рис.П2.2. Квазициклы временного ряда урожайности озимой пшеницы по КБР, выявленные из фазового портрета вида F ( z ) = {( z i, z i )} указанного ВР.
Размерности Lk этих квазициклов представлены в таблице П2. Таблица П2.2. Ck Lk C1 C C3 C C5 C6 C7 C8 C9 C10 Приложение Эмпирические значения частостей переходов из каждой конкретной l 0 0 конфигурации u10 u 2...u l0 M l в состояние Н, С и В, l = 3,4,5,6,7,8, wl u10u2...ul0 Н, wl u u...u С, wl u u...u В для урожайности озимой пшеницы по КБР 00 12 0 l 0 1 0 2 0 l ( ) ( ) ( ) 2 ННН 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 4 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 5 6 0 1 0 0 1/2 1/2 0 1 0 1 0 Переход из Переход в Количество переходов Всего переходов Частость переходов Глубина 2 СВН 4 0 1 0 0 3 0 0 2 1 0 0 1 0 1 0 1 0 0 2 1 2 1 0 1 0 1 2 0 1 0 5 1 6 0 1 0 0 1 0 0 2/3 1/3 0 0 1 0 1 0 1 0 0 2/5 1/5 2/5 1/2 0 1/2 0 1/3 2/3 0 1 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В СНВ ННС СВС 3-конфигурация ССН ННВ СВВ ССС НСН ВНС ССВ 3-конфигурация 3-конфигурация НСС 0 1/2 1/2 0 1/2 1/2 0 0 1 1/2 1/2 0 1/3 1/3 1/3 1/2 1/2 ВНВ НСВ ВСН НВН ВСС НВС ВСВ СНН ВВС СНС ВВВ Всего 3-конфигураций Ц24 шт. Из них с памятью (однозначных переходов) - 10 шт.
Переход из Переход в Количество переходов Всего переходов Частость переходов 2 3 Н С В Н С В Н С В Н С В 4 1 0 0 0 2 1 1 0 1 0 2 2 5 1 6 1 0 0 0 2/3 1/3 1/2 0 1/2 0 1/2 1/2 3 2 Частота переходов Всего переходов Частость переходов Глубина Переход из Переход в Глубина 2 ННСС 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 4 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 5 6 0 1 0 0 1 0 1 0 0 0 0 1 0 1 2 ССНС 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 4 1 1 0 1 0 0 0 0 1 0 1 0 0 2 0 0 0 1 2 0 1 0 0 2 0 1 0 0 2 0 0 0 1 0 1 1 0 1 61 2 3 1/2 Н ВСВВ С 2 1/2 0 В 1 0 0 0 0 1 0 1 4 0 1 0 0 1 0 1 0 5 6 0 1 0 0 1 0 1/2 0 1/ 4-конфигурация ННСВ ССНВ Н ВВСС С В Н ВВСВ С В НССС СССН НССВ СССВ Всего 4-конфигураций - 39 шт. Из них с памятью - 32 шт.
НСВС ССВС 0 2 2/2 0 0 0 1 2/3 0 1/3 0 0 2/2 0 1 НСВВ ССВВ 4-конфигурация НВСН 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 4-конфигурация СВСС НВСС СВВС СННН СВВВ СННС ВССН 0 2 2/2 0 0 0 СННВ ВССС СНСН ВССВ 2 1/2 1/2 0 1 СНСС ВСВН 2 ССНСН ССНСС Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 0 0 1 2 0 0 0 2 0 0 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 Н СВССНС С В 1 1 0 0 1 0 0 1 0 1 0 1/2 1/2 0 0 1 0 0 1 0 1 0 7-конфигурация 3 Н С В 4 1 0 5 6 1 0 3 Н ССВССН С В 4 0 2 5 6 0 2/2 2 ССВССНС 3 Н С В Н С В 4 1 1 0 1 0 5 6 1/2 1/2 0 1 0 СВССНСН 6-конфигурация ССВСС 2/2 0 Н СВВСВН С В Н СВВСВВ С В Н ВССНСН С В 0 0 Н СВССНСС С 0 1 0 1 1 В Всего 7-конфигураций - 48 шт. Из них с памятью - 46 шт.
СВССН 2/ 5-конфигурация 1/2 2 1/2 1/2 2 1/2 0 0 1 0 0 0 1 0 1 0 0 1 СВВСВ 0 0 Н ВССНСС С 0 1 0 1 1 В Всего 6-конфигураций- 45 шт. Из них с памятью - 43 шт.
8-конфигурация СВССВ 0 1 Н ССВССНСН С В Н ССВССНСС С В 1 0 0 0 0 1 0 0 ВССНС Всего 8-конфигураций - 48 шт. Из них с памятью - все 48 шт.
ВССВС ВССВВ ВВСВН ВВСВВ Всего 5-конфигураций Ц43 шт. Из них с памятью - 39 шт.
Приложение Результат валидации прогнозной модели на примере урожайности озимой пшеницы за 1952-2002 гг. по КБР Таблица П4.1.
Переходы l- конфигурации в состояния Н,С,В Прогнозируемый год l - конфигурация Ненормированные значения функции принадлежности В , С, Н 1 2 ВССНССВВ 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 4 2/15=0,27 8/15+3/4+2/3=1,94 5/15+1/4+1/3+1=1,91 2/12+1/7=0,27 8/15+3/7+2/4=1,45 5/15+3/7+2/4+1=2,25 6/23+3/9=0,59 9/23+2/9+1/2=1,11 8/23+4/9+1/2+1=2,29 6/23+1/5+1/2+1/2+1/2+1/2+1/2=2,96 9/23+2/5+1/2+1/2+1/2+1/2+1/2+1=4,29 8/23+2/5=0,75 4/12+3/6=0,83 5/12+2/6+2/3+2/2+2/2+2/2+1=5,4 3/12+1/6+1/3=0,74 6/23+3/9+2/5+2/3+2/2+1=3,65 9/23+2/9+1/5=0,81 8/23+4/9+2/5+1/3=1,51 6/23+1/8=0,38 9/23+5/8+3/3+2/2+1=4,01 8/23+2/8=0,58 2/17+1/7=0,27 8/15+3/7+2/4+1=2,45 5/15+3/7+2/4=1,25 6/23+3/9+1/2=1,09 9/23+2/9=0,61 8/23+4/9+1/2+1=2,28 6/23+3/9+2/5=0,99 9/23+2/9+1/5+1=1,81 8/23+4/9+2/5=1,18 6/23+1/8=0,38 9/23+5/8+1/3+1=2,34 8/23+2/8+2/3=1,24 2/15=0,13 8/15+3/4+1=2,28 5/15+1/4=0,58 2/15=0,13 8/15+3/4+2/3=1,95 5/15+1/4+1/3+1=1,91 2/15+1/7=0,27 8/15+3/7+2/4+1/2=1,95 5/15+3/7+2/4+1/2+1=2,75 6/23+3/9+2/5=0,99 9/23+2/9+1/5=0,81 8/23+4/9+2/5+1=2, Сумма ненорми рован ных значений функций принадле жности 5 3, Значение функции принадле жности U = {(Н;
Н ), (C;
C ), (В, В )} Прогнозное нечеткое терм-множество 6 0,03 0,49 0,48 0,07 0,36 0,57 0,15 0,28 0,57 0,37 0,54 0,09 0,12 0,77 0,11 0,61 0,14 0,25 0,08 0,81 0,11 0,07 0,62 0,31 0,27 0,15 0,58 0,25 0,55 0,30 0,1 0,6 0,3 0,02 0,76 0,20 0,03 0,49 0,48 0,05 0,40 0,55 0,25 0,20 0, 7 U={(Н;
0,03), (С;
0,49), (В;
0,48)} СВССНССВ 3, U={(Н;
0,07), (С;
0,36), (В;
0,57)} ССВССНСС 3, U={(Н;
0,15), (С;
0,28), (В;
0,57)} СССВССНС U={(Н;
0,37), (С;
0,54), (В;
0,09)} ВСССВССН 6, U={(Н;
0,12), (С;
0,77), (В;
0,11)} ВВСССВСС 5, U={(Н;
0,61), (С;
0,14), (В;
0,25)} ВВВСССВС 4, U={(Н;
0,08), (С;
0,81), (В;
0,11)} СВВВСССВ 3, U={(Н;
0,07), (С;
0,62), (В;
0,31)} ССВВВССС 3, U={(Н;
0,27), (С;
0,15), (В;
0,58)} ВССВВВСС 3, U={(Н;
0,25), (С;
0,55), (В;
0,30)} НВССВВВС 3, U={(Н;
0,1), (С;
0,6), (В;
0,3)} ННВССВВВ 4, U={(Н;
0,04), (С;
0,76), (В;
0,20)} СННВССВВ 3, U={(Н;
0,03), (С;
0,49), (В;
0,48)} (по факту-высокий) НСННВССВ 4, U={(Н;
0,05), (С;
0,40), (В;
0,55)} СНСННВСС 3, U={(Н;
0,25), (С;
0,20), (В;
0,55)} 1 2 ССНСННВС 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 4 6/23+1/8+1/2=0,88 9/23+5/8+1/2+1=2,51 8/23+2/8=0,58 2/15+1/3=0,46 8/15+2/3+1=2,19 5/15=0,33 4/12+1/4+1/3=0,91 5/12+2/4+1/3=1,24 3/12+1/4+1/3+1=1,83 4/12+3/6+1=1,83 5/12+2/6=0,74 3/12+1/6=0,41 6/23+1/5+1/2+1/2+1/2+1/2+1/2+1=3,96 9/23+2/5+1/2+1/2+1/2+1/2+1/2=3,29 8/23+2/5=0,75 4/12+3/6=0,83 5/12+2/6+2/3+2/2+2/2+2/2+1=5,4 3/12+1/6+1/3=0,74 6/23+3/9+2/5+2/3+2/2+1=3,65 9/23+2/9+1/5=0,81 8/23+4/9+2/5+1/3=1,51 6/23+1/8=0,38 9/23+5/8+3/3+2/2+1=4,01 8/23+2/8=0,59 2/15+1/7=0,27 8/15+3/7+2/4+1/2+1=2,95 5/15+3/7+2/4+1/2=1,75 6/23+3/9+2/5+2/3=1,65 9/23+2/9+1/5=0,81 8/23+4/9+2/5+1/3+1=2,51 6/23+1/8=0,38 9/23+5/8+3/3+1=3,01 8/23+2/8=0,59 2/15+1/7=0,27 8/15+3/7+1/2+1=2,45 5/15+3/7+1/2=1,25 6/23+1/5=0,46 9/23+2/5=0,79 8/23+2/5+1=1,55 4/12=0,33 5/12+1/2+1=1,91 3/12+1/2=0,75 2/15+1/7+1/2+1/2+1/2+1=2,77 8/15+3/7=0,95 5/15+3/7+1/2+1/2+1/2=2,25 6/23+1/8=0,38 9/23+5/8+1/3=1,34 8/23+2/8+2/3+1=2,25 2/15=0,13 8/15+3/4+2/3+1=2,94 5/15+1/14+1/3=0,91 2/15+1/7+1/2+1/2+1/2+1/2=1,77 8/15+3/7=0,95 5/15+3/7+1/2+1/2+1/2+1=3,25 6/23+1/8=0,38 9/23+5/8+1/3=1,34 8/23+2/8+2/3+1=2, 5 3, 6 0,22 0,63 0,15 0,15 0,73 0,12 0,23 0,31 0,46 0,61 0,25 0,14 0,49 0,41 0,10 0,12 0,77 0,11 0,61 0,14 0,25 0,08 0,8 0,12 0,05 0,60 0,35 0,33 0,16 0,51 0,09 0,76 0,15 0,07 0,62 0,31 0,16 0,28 0,56 0,11 0,64 0,25 0,46 0,16 0,38 0,10 0,34 0,56 0,03 0,74 0,23 0,30 0,16 0,54 0,09 0,34 0, 7 U={(Н;
0,22), (С;
0,63), (В;
0,15)} ВССНСННВ 2, U={(Н;
0,15), (С;
0,73), (В;
0,12)} СВССНСНН 3, U={(Н;
0,23), (С;
0,31), (В;
0,46)} ССВССНСН 2, U={(Н;
0,61), (С;
0,25), (В;
0,14)} ВССВССНС U={(Н;
0,49), (С;
0,41), (В;
0,10)} СВССВССН 6, U={(Н;
0,12), (С;
0,77), (В;
0,11)} НСВССВСС 5, U={(Н;
0,61), (С;
0,14), (В;
0,25)} ВНСВССВС 4, U={(Н;
0,08), (С;
0,8), (В;
0,12)} СВНСВССВ 4, U={(Н;
0,05), (С;
0,60), (В;
0,35)} ВСВНСВСС 4, U={(Н;
0,33), (С;
0,16), (В;
0,51)} ВВСВНСВС 3, U={(Н;
0,09), (С;
0,76), (В;
0,15)} СВВСВНСВ 3, U={(Н;
0,07), (С;
0,62), (В;
0,31)} ВСВВСВНС 2, U={(Н;
0,16), (С;
0,28), (В;
0,56)} ВВСВВСВН 2, U={(Н;
0,11), (С;
0,64), (В;
0,25)} СВВСВВСВ 5, U={(Н;
0,46), (С;
0,16), (В;
0,38)} НСВВСВВС 3, U={(Н;
0,01), (С;
0,34), (В;
0,56)} ННСВВСВВ 3, U={(Н;
0,03), (С;
0,74), (В;
0,23)} СННСВВСВ 5, U={(Н;
0,30), (С;
0,16), (В;
0,54)} ВСННСВВС 3, U={(Н;
0,09), (С;
0,34), (В;
0,57)} 1 2 НВСННСВВ 3 Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В Н С В 4 2/15=0,13 8/15+3/4+2/3+1=2,92 5/15+1/14+1/3=0,91 2/15+1/7=0,27 8/15+3/7+1/2=1,45 5/15+3/7+1/2+1=2,25 6/23+1/5=0,46 9/23+2/5+1/2=1,29 8/23+2/5+1/2+1=2,24 4/12+1/2+1/3=1,16 5/12+2/4+1/3+1=2,24 3/12+1/4+1/3=0,83 4/23+3/6+1=1,83 5/12+2/6=0,74 5/12+1/6=0,41 6/23+1/8+1/2+1=1,88 9/23+5/8+1/2=1,51 8/232/8=0,59 2/15+1/3=0,46 8/15+2/3+1=3,19 5/15=0,33 4/12=0,33 5/12+1/2=0,91 3/12+1/2+1=1,75 2/15+1/3+1=1,46 8/15+2/3=1,19 5/15=0,33 4/12+3/6=0,83 5/12+2/6=1,4 3/12+1/6+1/3+1=1, 5 3, 6 0,03 0,74 0,23 0,07 0,37 0,56 0,12 0,32 0,56 0,27 0,53 0,20 0,61 0,25 0,14 0,47 0,38 0,15 0,12 0,80 0,08 0,11 0,30 0,59 0,49 0,40 0,11 0,21 0,35 0, 7 U={(Н;
0,03), (С;
0,74), (В;
0,23)} ВНВСННСВ 3, U={(Н;
0,07), (С;
0,37), (В;
0,56)} НВНВСННС 3, U={(Н;
0,12), (С;
0,32), (В;
0,56)} СНВНВСНН 4, U={(Н;
0,27), (С;
0,53), (В;
0,20)} ССНВНВСН 2, U={(Н;
0,61), (С;
0,25), (В;
0,14)} СССНВНВС 3, U={(Н;
0,47), (С;
0,38), (В;
0,15)} НСССНВНВ 3, U={(Н;
0,12), (С;
0,80), (В;
0,08)} ННСССНВН 2, U={(Н;
0,11), (С;
0,30), (В;
0,59)} НННСССНВ 2, U={(Н;
0,49), (С;
0,40), (В;
0,11)} СНННСССН 3, U={(Н;
0,21), (С;
0,35), (В;
Pages: | 1 | 2 | Книги, научные публикации