Методические указания и примеры решения задач 2 страница

Таблица к примеру 2 задачи 2

Операции	О 1	О 2	О 3	О 4	О 5
О 1
О 2
О 3
О 4
О 5

Этот пример решается так же, как пример 1. На первом шаге выделяются операции О ₃, О ₅, образующие порядковый уровень N ₀:{ О ₃, О ₅} – N _0. Эти операции выполняются раньше всех других (им не предшествует никакая другая операция). На втором шаге после преобразования строки А ₀ выделяется операция О ₂: { О ₂} – N ₁, которая выполняется раньше всех других, кроме уже выделенных. На третьем шаге выделяется операция О ₁: { О ₁} – N ₂ и на четвертом – операция О ₄: { О ₄} – N ₃. Окончательно получаем, что операции располагаются по уровням порядка следующим образом: { О ₃, О ₅} – N ₀, { О ₂} – N ₁, { О ₁} – N ₂, { О ₄} – N ₃. Итоговый граф имеет такой же вид, как в примере 1, только элементами в нем являются не приборы, а операции. Таким образом, система разбивается на 4 порядковых уровня. Первыми выполняются операции уровня N ₀, а последними – операции уровня N ₃.

Задача 3. Любая сложная система содержит обратные связи, т.е. циклы. Дана система с циклами, отношения между элементами которой представлены матрицей инциденций. Требуется определить порядковую структуру системы.

Методические указания

Цель этой задачи аналогична задаче 2, но ее особенность состоит в том, что анализируемая система является более сложной и представлена графом с обратными связями (циклами). Алгоритм предыдущей задачи здесь не применим, так как в системе с циклами вектор-строка А _0, либо одна из последующих строк не содержит нулей. Поэтому для ее решения сначала нужно объединить элементы, связанные циклом, в группы (в классы эквивалентности). Затем исключить циклы из матрицы и свести задачу к предыдущей. Элементы х_i и х_j связаны циклом, если существует путь из элемента х_i в элемент х_j и обратно. Путь может быть прямым или опосредованным, т.е. через другие элементы. В частности, при i = j элемент х_i может замыкаться на себя, т.е. является циклическим элементом. В матрице инциденций цикл между элементами х_i и х_j представляется последовательностью единиц в соответствующих ячейках, которая связывает х_i и х_j. В частности, если (i, j) = 1 и (j, i) = 1, то х_i, х_j связаны простым циклом, если (i, j) = 1 и (j, k) = 1, (k, i) = 1, то х_i и х_j связаны сложным циклом и т.д. Циклическому элементу в матрице инциденций соответствует единица в ячейке на главной диагонали, например, если (i, i) = 1, то элемент х_i циклический.

После выполнения операции объединения все множество элементов оказывается разбитым на несколько классов эквивалентности, например: С ₁ = (х ₁, х ₅, х ₆), С ₂ = (х ₃, х ₄), С ₃ = (х ₂, х ₇, х ₁₀), С ₄ = (х ₈) и т.д. Элементы в каждом классе связаны между собой циклами, т.е. считаются неразличимыми, так как циклы соответствуют отношению эквивалентности. Затем алгоритм решения задачи 2 применяется уже не к отдельным элементам, а к классам С ₁, С ₂, С ₃, С ₄, так как эти классы образуют простой граф без контуров. Для построения уровней порядка на классах в исходной матрице все единицы в ячейках матрицы, связывающих элементы из одного класса, заменяются нулями. После этого выделяются уровни порядка так же, как в задаче 2. Итоговый порядковый граф будет содержать не отдельные элементы, а классы. Рассмотрим пример.

Пример 1. По результатам испытаний приборостроительной продукции были выявлены типовые неисправности и проведено их ранжирование по ряду признаков. Соответствующая матрица инциденций дана в табл. 1. Постройте уровни порядка на множестве неисправностей по отношению предпочтения («не менее важен, чем»). Итоговый результат представьте в виде порядкового графа.

Таблица 1 к примеру 1 задачи 3

Неисправности	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8

Решение

Из таблицы видно, что вектор-строка А ₀, равная сумме строк исходной матрицы, не содержит нулей, т.е. алгоритм задачи 2 применить невозможно. Решение строится по алгоритму, рассмотренному в разделе 3 конспекта. Он представлен ниже более подробно.

Шаг 1. Проводим анализ исходной матрицы с целью выявления циклов. Анализ проводится последовательно сверху вниз, начиная с первой строки. Каждый элемент должен входить в один и только один класс эквивалентности. Если какой-то элемент, например х ₁, уже проанализирован и включен в класс эквивалентности, то к нему уже не возвращаются при дальнейшем анализе. Класс эквивалентности может содержать цикл, а может состоять из отдельных изолированных элементов. Начинаем анализ с элемента х ₁. Наша цель определить все пути, ведущие из х ₁ обратно в х ₁. Для этого рассмотрим его связи с другими элементами. Элемент х ₁ связан с самим собой, т.е. он циклический, с х ₃ и х ₅. Смотрим строку х ₃. Наша цель – установить, есть ли обратный путь из х ₃ в х ₁. Элемент х ₃ связан с х ₅ и х ₇; х ₅ связан с х ₄ (возврат), т.е. пути к х ₁ нет. Смотрим строку х ₇: х ₇ связан с х ₁ (получаем цикл). Отмечаем также, что элемент х ₇ – циклический. Возвращаемся к строке х ₁ и рассматриваем вторую ветвь: х ₁ – х ₅. Элемент х ₅ связан с х ₄, т.е. этот путь к х ₁ не ведет. Таким образом, класс эквивалентности С ₁ объединяет элементы х ₁, х ₃ и х ₇.

Рассмотрим теперь связи элемента х ₂. Он связан с самим собой, т.е. он циклический; а также с х _6. Смотрим строку х ₆: х ₆ связан с х ₃ (возврат), т.е. к х ₂ пути нет, и это пустая ветвь. Таким образом, класс эквивалентности С ₂ состоит из одного элемента х ₂.

Анализировать связи элемента х ₃ не нужно, так как он уже вошел в класс С ₁. Элемент х ₄ связан с самим собой, т.е. он циклический, а также с х ₅. Элемент х ₅ связан с х ₄, т.е. имеем цикл. Окончательно получаем класс С ₃, состоящий из элементов х ₄ и х ₅.

5-я строка: исходный элемент х ₅. Он уже вошел в класс С ₃, т.е. анализировать его связи не нужно. 6-я строка: исходный элемент х ₆. Он связан с самим собой и х ₃ (возврат), т.е. цикла нет. Элемент х ₆ образует класс эквивалентности С ₄.

7-я строка: исходный элемент х ₇. Он уже включен в класс С ₁, т.е. анализировать его связи не нужно. Элемент х ₈ связан только с собой, т.е. является циклическим, и образует класс эквивалентности С _5.

Таким образом, анализ показывает, что система содержит 5 классов эквивалентности.

Шаг 2. Проводится преобразование исходной матрицы, состоящее в том, что для элементов, входящих в один и тот же класс эквивалентности, единицы, соответствующие связям между ними, заменяются нулями. Например, в первой строке х ₁ и х ₃ связаны циклом, поэтому в ячейке (1, 3) матрицы 1 заменяется на 0; х ₁ и х ₅ циклом не связаны, поэтому в ячейке (1, 5) остается 1 и т.д. Отметим, что преобразованием мы нивелировали (устранили) различие между элементами, связанными циклом, т.е. они стали неразличимы между собой и матрица теперь циклов не содержит. Элементы из разных классов связаны исходным отношением предпочтения. Преобразованная матрица представлена в табл. 2.

Таблица 2 к примеру 1 задачи 3

Неисправности	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8

Шаг 3. К преобразованной матрице применим алгоритм задачи 2. Образуем вектор-строку А ₀, равную сумме строк исходной матрицы А ₀ = (0 0 1 0 2 1 0 1). “Нулевые” элементы х ₁, х ₂, х ₄, х ₇. Порядковый уровень образуют классы эквивалентности, а не отдельные элементы, т.е. пока не соберутся все элементы, входящие в один класс, они на данном уровне не показываются. В нашем случае элементы х ₁ и х ₇ не составляют класса (не хватает х ₃); аналогично х ₄ не образует класса (не хватает х ₅); а вот элемент х ₂ образует класс эквивалентности С ₂, поэтому он составляет порядковый уровень N ₀: {{ C ₂}} – N _0. Преобразуем строку А ₀ аналогично задаче 2, получим строку A ₁ = (´ ´ 1 ´ 1 0 ´ 0). “Нулевые” элементы х ₆, х ₈. Каждый из них образует отдельный класс, поэтому они выделяются на этом порядковом уровне N ₁: {{ C ₄},{ C ₅}} – N _1. Преобразуем строку А ₁, получим строку A ₂ = (´ ´ 0 ´ 1 ´ ´ ´). “Нулевой” элемент х ₃. Он вместе с ранее выделенными элементами х ₁, х ₇ образует класс эквивалентности С ₁, который и составляет порядковый уровень N ₂: {{ C ₁}} – N _2. Преобразуем строку А ₂, получим строку А ₃ = (´ ´ ´ ´ 0 ´ ´ ´). “Нулевой” элемент х ₅. Он вместе с ранее выделенным элементом х ₄ образует класс С ₃, который и составляет порядковый уровень N ₃: {{ C ₃}} – N _3.

Окончательный результат имеет вид {{ C ₂}} – N ₀, {{ C ₄}, { C ₅}} – N ₁, {{ C ₁}} – N ₂, {{ C ₃}} – N ₃. Таким образом, система разбивается на 4 порядковых уровня. Наиболее предпочтительны (важны) классы неисправностей порядкового уровня N ₀ (класс С ₂), а наименее предпочтительны (важны) классы уровня N ₃ (класс С ₃).

Задача 4. Дана проблема и возможные варианты ее решения (множество допустимых альтернатив) B ₁, B ₂, …, B_k.. Каждая альтернатива оценивается множеством (списком) критериев K ₁, K ₂, …, K_n. Требуется выбрать наилучший вариант решения (наилучшую альтернативу) и оценить последствия выбора (положительные и отрицательные).

Методические указания

Цель задачи – освоение методов получения оптимального решения по многим критериям. Особенность этой задачи, характерная для практических задач управления и оптимизации, состоит в том, что исходная информация представлена в виде количественных и качественных экспертных оценок. Будем считать, что множество Парето построено (см. задачу 6). Используем для нахождения наилучшего решения метод анализа иерархий (метод собственных значений), основанный на аддитивной свертке, который позволяет найти наилучшее решение и оценить его достоверность. Название метода связано с тем, что решения принимаются на нескольких уровнях: сначала на уровне критериев, затем на уровне альтернатив. Преимуществом метода является также его применимость в нечетких ситуациях [42, 58]. Обычно метод применяется, когда число критериев n £ 10; если n > 10, то используются обобщенные критерии, так чтобы их общее число не превышало 10, затем они подвергаются декомпозиции. Ниже приводится алгоритм решения.

Проводится предварительное ранжирование критериев, и они располагаются в порядке убывания важности K ₁ > K ₂ > … > K_n (K ₁ важнее K ₂ и т.д.).

Проводится попарное сравнение критериев по важности по девятибалльной шкале и составляется соответствующая матрица (таблица) размера (n ´ n): равная важность – 1; умеренное превосходство – 3; значительное превосходство – 5; сильное превосходство – 7; очень сильное превосходство – 9. В промежуточных случаях ставятся четные оценки 2, 4, 6, 8. Например, если K_i умеренно превосходит K_j, то в клетку (i, j) таблицы ставится 3 (i – строка, j – столбец), а в клетку (j, i) – 1/3 (обратная величина).

Определяется нормализованный вектор приоритетов (НВП) по следующей схеме:

а) рассчитывается среднее геометрическое элементов в каждой строке матрицы

, ; где – число критериев;

б) рассчитывается сумма средних геометрических: ;

в) вычисляются компоненты НВП: 1-й компонент НВП , 2-й компонент НВП , …, n -й компонент НВП . Легко видеть, что сумма компонентов равна единице. Каждый компонент НВП представляет собой оценку важности соответствующего критерия (1-й – первого, 2-й – второго и т.д.). Обратите внимание на то, что оценки важности критериев в таблице должны соответствовать предварительному ранжированию.

Проверяется согласованность оценок в матрице. Для этого подсчитываются три характеристики:

а) собственное значение матрицы l _max = сумма элементов первого столбца ´ 1-йкомпонент НВП + сумма элементов второго столбца ´ 2-й компонент НВП + и т.д. по всем столбцам, где ´ – знак умножения.

б) индекс согласования ИС = ;

в) отношение согласованности ОС = ИC/ПСС,

где ПСС – показатель случайной согласованности, определяемый теоретически для случая, когда оценки в матрице проставлены случайным образом, и зависящий только от размера матрицы. Его значения представлены в табл. 1. Оценки в матрице считаются согласованными, если ОС £ 10-15 %, в противном случае их надо пересматривать и корректировать.

Таблица 1 к задаче 4

Размер матрицы
ПСС			0,58	0,90	1,12	1,24	1,32	1,41	1,45	1,49

Проводится попарное сравнение пригодности (ценности) вариантов по каждому критерию по той же шкале, что для критериев, и заполняются соответствующие таблицы (форма таблиц дана ниже). Подсчитываются _{i max,}, ИС _i, ОС _i для каждой таблицы.

Определяется общий критерий (приоритет) для каждого варианта: K (B ₁) = оценка B ₁ по первому критерию ´ 1-й компонент НВП + оценка B ₁ по второму критерию ´ 2-йкомпонент НВП + и т.д. по всем критериям. Аналогично подсчитываются K (B ₂), K (B ₃) и т.д., при этом в приведенном выражении B _1­­ заменяется соответственно на B ₂, B ₃ и т.д.

Определяется наилучшее решение, для которого значение общего критерия K максимально.

Проверяется достоверность решения. Для этого сначала рассчитывается обобщенный индекс согласования ОИС = ИС₁ ´ 1-й компонент НВП + ИС₂ ´ 2-й компонент НВП + и т.д. по всем критериям. Затем, используя значение ОИС, рассчитывается обобщенное отношение согласованности ООС = ОИС/ОПСС, где ОПСС= ПСС для матриц сравнения вариантов по критериям. Решение считается достоверным, если ООС £ 10-15 %, в противном случае нужно корректировать матрицы сравнения вариантов по критериям.

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

Пример 1. Пусть проблема состоит в выборе средства измерений для решения некоторой измерительной задачи (класса задач). Число альтернатив (вариантов) равно 3. Множество альтернатив включает вариант 1(В ₁) – высокоточный аналоговый прибор с визуальным отсчетом; вариант 2(В ₂) – цифровой прибор; вариант 3(В ₃) – многофункциональная установка с выводом информации на экран. Каждая альтернатива оценивается по множеству критериев: точность (К ₁), диапазон (К ₂) быстродей­ствие (К₃), универсальность (К₄), интенсивность эксплуатации (К₅), стоимость (K ₆), простота и удобство эксплуатации (K₇), габариты (К₈) (критерии рас­положены в порядке убывания важности). Требуется выбрать наилучший вариант решения.

Решение

Применим метод анализа иерархий. Решение строится в соответствии с методическими указаниями к этой задаче. Составляется матрица попарных сравнений критериев по важности, представленная в табл.2.

Таблица 2 к примеру 1 задачи 4

Критерии	K 1	К 2	К 3	К 4	К 5	К 6	К 7	K 8	НВП
K 1									0,277
K 2	1/3								0,238
K 3		1/2							0,203
K 4	1/3	1/4	1/2						0,131
K 5	1/5	1/5	1/5	1/5					0,060
K 6	1/6	1/6	1/6	1/5	1/2				0,045
K 7	1/6	1/7	1/6	1/6	1/4	1/4			0,026
K 8	1/7	1/8	1/7	1/8	1/6	1/4	1/2		0,011
									λ max = 8,986 ИС = 0,1408 ОС = 0,0999

Заполнение матрицы происходит следующим образом: если элемент i важнее элемента j, то клетка (i, j), соответствующая строке i и столбцу j, заполняется целым числом, а клетка (j, i), соответствующая строке j и столбцу i, заполняется обратным числом (дробью). Если же элемент j более важен, чем элемент i, то целое число ста­вится в клетку (j, i), а обратная величинав клетку (i, j). Если считается, что элементы i, j одинаковы, то в обе клетки ставится единица. Сравнение элементов по относительной важности проводится по девятибалльной шкале. При заполнении матрицы рекомендуется придерживаться следую­щих правил. Сначала расположите все критерии в порядке убывания их важности и пронумеруйте, т.е. тому критерию, который вы считаете в целом более важным, чем остальные, присвойте индекс К ₁, следующему по важности — индекс К ₂ и т.д. (При этом не бойтесь ошибиться, так как эта оценка предварительная и ошибку можно будет в дальнейшем исправить). При предварительном ранжировании по важности на первые места ставятся функциональные критерии, на последующие – технико-экономические, затем эргономические и специальные (прочие). Хотя индивидуальные предпочтения могут быть разными, но нам важно получить типовое решение, основанное на системном (функциональном) подходе. Затем сформируйте таблицу. Ее заполнение проводится построчно, начиная с первой строки, т.е. с наиболее важного критерия (в нашем примере это К ₁). Сначала следует проставить целочисленные оценки, тогда соответственные им дробные оценки получаются из них автоматически (как обратные к целым числам). При этом учтите, что, если какой-то критерий вы предварительно сочли в целом более важным, чем остальные, то это не означает, что при попарном сравнении с дру­гими, он обязательно будет превосходить каждый из них в отдельности. Однако, чем важнее критерий, тем больше целочисленных оценок будет в соответствующей ему строке матрицы и сами оценки имеют большие значения. Так как каждый критерий равен себе по важности, то главная диагональ матрицы всегда будет состоять из единиц. При назначении оценок надо обращать внимание на их взаимную согласованность. Например, если превосходство К ₁ над К ₂ значительное (оценка 5), а над К ₃ – между значительным и умеренным (оценка 4), то отсюда следует, что К ₃ будет немного превосходить К ₂. Поэтому при заполнении строки К ₃ в клетку (К ₃, К ₂) нельзя ставить произвольную оценку; она должна быть равна 2 либо 3, т.е. показывать незначительное превосходство К ₃ над К ₂, в противном случае это приведет к рассогла­сованию оценок в матрице и низкой достоверности результатов. Отметим, что в рассматриваемом примере умышленно введено рассогласование оценок в табл. 2, чтобы показать возможности метода. Когда заполнение матрицы закончено, все оценки проставлены и проверены на взаимную согласованность, переходят ко второму этапу.