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

следовательно вариант В ₃ наилучший, как имеющий наибольшее значение критерия.

Метод расстояния. Определим идеальное решение, используя данные табл. 3. В качестве координат абсолютного максимума выбираются наибольшие значения НВП по каждому критерию, а именно, К ₁(В _ид) = 0,570, К ₂(В _ид) = 0,696, К ₃(В _ид) = 0,574, К ₄(В _ид) = 0,645, К ₅(В _ид) = 0,333, К ₆(В _ид) = 0,645, К ₇(В _ид) = 0.635, К ₈(В _ид) = 0,559.

Расстояние Хемминга (p = 1). Подсчитаем значение меры расстояния для каждого варианта решения, используя функцию Хемминга , что дает ; ; . Наилучший вариант В ₃, так как ему соответствует наименьшее значение меры.

Расстояние Евклида (p = 2). Для меры расстояния имеем в этом случае выражение , и расчет значений меры для вариантов дает ; ; . Наилучший вариант В ₃.

Расстояние по максимальному различию (p = ¥). В этом случае имеем для меры расстояния предельное соотношение , что дает ; ; , т.е. наилучший вариант В ₃.

Расстояние по минимальному различию (p = − ¥). Для меры расстояния имеем выражение , и расчеты дают ; ; . В данном случае значение меры расстояния для всех вариантов равно нулю, поэтому можно считать все решения равнозначными. Их можно различить, если подсчитать число нулей для каждого варианта и учесть вес «нулевых» критериев. Вариант В ₁ имеет четыре нуля, вариант В ₂ – четыре нуля, вариант В ₃ – два нуля. С учетом веса «нулевых» критериев предпочтение следует отдать варианту В ₁, как наиболее близкому к идеальному решению.

Метод пороговых критериев. Так как пороговые значения критериев не заданы, то определяем их непосредственно из табл. 3. В качестве пороговых значений выбираются наименьшие значения НВП для каждого критерия (сравните с методом расстояния!), а именно K ₁₀ = 0,097; K ₂₀ = 0,075; K ₃₀ = 0,065; K ₄₀ = 0,058; K ₅₀ = 0,333; K ₆₀ = 0,058; K ₇₀ = 0,078; K ₈₀ = 0,089. Теперь определяем значение общего критерия для каждого варианта, используя первые строки табл. 3. Расчеты дают K (B ₁) = min (0,097/0,097, 0,229/0,075, …, 0,559/0,089) = 1. Аналогично, используя вторые строки табл. 3, получим K (B ₂) = min (0,570/0,097, …, 0,352/0,089) = 1. Наконец, используя третьи строки табл. 3, находим для третьего варианта K (B ₃) = min (0,333/0,097, …, 0,089/0,089) = 1. Поскольку для всех трех вариантов значение общего критерия одинаково и равно единице, то все варианты равноценны. Решения можно дифференцировать (различить), если подсчитать число единиц для каждого варианта. Наилучшим является вариант, имеющий наименьшее число совпадений с пороговыми значениями, т.е. имеющий наименьшее число единиц. В нашем случае это вариант В ₁ (две единицы).

Таким образом, по аддитивной, мультипликативной сверткам, а также методу расстояния при р = 1, р = 2, р = ¥ предпочтительным вариантом является В ₃; по методу главного критерия и свертке по наилучшему критерию – В ₂; по максминной свертке с учётом и без учёта веса критериев, методу пороговых критериев, методу расстояния при p = − ¥ предпочтителен вариант В ₁. Так как в примере выполняются условия применения аддитивной свертки (плавное убывание весов критериев), то наилучшим (предпочтительным) следует считать вариант В ₃, полученный по этой свертке.

Задача 6. По результатам опроса экспертов составлена таблица оценок m вариантов решения некоторой проблемы по n критериям. Использованы балльные оценки в пятибалльной шкале и словесные оценки, причем большей оценке соответствует лучшее значение критерия. По данным таблицы, считая все критерии одинаково важными, требуется определить множество Парето-решений, найти наилучшее решение и оценить достоверность выбора.

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

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

Пример 1. По результатам опроса экспертов составлена таблица оценок пяти вариантов плана застройки территории по восьми крите­риям. Результаты представлены в табл. 1. Использованы балльные оценки в пятибалльной шкале и словесные оценки, причем большей оценке соответствует луч­шее значение критерия. По данным таблицы, считая все критерии оди­наково важными, требуется а) построить множество Парето-решений; б) определить наилучшее решение, используя подходящую свертку кри­териев; в) оценить ошибку выбора, если ошибка оценок таблицы составляет, например, 1,2 балла.

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

Варианты решения	Значения критериев
	K 1	K 2	K 3	K 4	K 5	K 6	K 7	K 8
В 1	Высокое	Среднее					Среднее	Очень высокое
В 2	Среднее	Низкое					Среднее	Среднее
В 3	Среднее	Очень низкое					Среднее	Среднее
В 4	Низкое	Низкое					Среднее	среднее
В 5	Среднее	Низкое					Низкое	Низкое

Решение

По определению множество Парето состоит из вариантов решений, которые по всем критериям не хуже остальных и хотя бы по одному кри­терию лучше. Один из способов построения множества Парето заключается в попарном срав­нении вариантов. Сравнение осуществляется последова­тельно, начиная с варианта В ₁, т.е. он сравнивается с вариантами В ₂, В ₃ и т.д. Затем В ₂ сравнивается с вариантами В ₃, В ₄ и т.д., причем дальнейшие действия на каждом шаге зависят от результата сравнения. При сравнении произвольной пары вариантов, i и j (например, i = 1 j = 2) возможны три случая. В первом случае вариант i не хуже варианта j по всем критериям и хотя бы по одному критерию лучше; тогда вариант j исключается из дальнейшего рассмотрения, а вариант i сравнивается с оставшимися вариантами. Этот случай представлен в табл. 2, где использованы словесные оценки: ОВ – очень высокое значение, В – высокое, С – среднее, Н – низкое. Из таблицы видно, что оценки верхней строки не хуже оценок второй строки, поэтому вариант j = 2 можно исключить из дальнейшего рассмотрения.

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

Варианты	Значения критериев
К 1	К 2	К 3	К 4	К 5	К 6	К 7	К 8
i = 1				ОВ	С
j = 2				В	Н

Во втором случае вариант j не хуже варианта i по всем критериям и хотя бы по одному критерию лучше; тогда вариант i исключается из дальнейшего рассмотрения, а вариант j сравнивается с оcтавшимися вариантами. Этот случай представлен в табл. 3. Из данных табл. 3 видно, что вариант i = 1 можно исключить из рассмотрения.

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

Варианты	Значения критериев
К 1	К 2	К 3	К 4	К 5	К 6	К 7	К 8
i = 1				С
j = 2				В

В третьем случае по одним критериям вариант i лучше варианта j, а по другим – вариант j лучше варианта i; тогда варианты i и j считаются несравни­мыми, оба остаются и должны сравниваться с оставшимися вариантами. Этот случай представлен в табл. 4. Из данных табл. 4 видно, что ни один из вариантов не может быть исключен.

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

Варианты	Значения критериев
К 1	К 2	К 3	К 4	К 5	К 6	К 7	К 8
i = 1				С
j = 2				В

Те варианты решения, которые останутся после завершения проце­дуры сравнения, образуют множество Парето. В нашем примере множе­ство Парето состоит из вариантов В ₁, В ₂. Следовательно, варианты В ₃, В ₄, В ₅ можно исключить из дальнейшего рассмотрения.

Если исходное множество состоит из большого числа вариантов, то их непосредственное сравнение по всем критериям может оказаться утомительным. Рекомендуется следующая проце­дура. Для каждого критерия выписываются все варианты решения, имеющие по нему наивысшую оценку. В нашем примере имеем для К ₁ – В ₁, для К ₅ – В ₂, для К ₂ – В ₁, для К ₆ – В ₁, для К ₃ – В ₁, для К ₇ – В ₁, В ₂, В ₃, В ₄, для К ₄ – В ₂, для К ₈ – В ₁. Определяется наиболее часто повторяющийся вариант, т.е. встречающийся в наибольшем числе критериев (если таких вариантов несколько и они встречаются в разных критериях, то выбирается любой из них; если же они встречаются только в одних и тех же критериях, то их надо сравнить попарно по оставшимся критериям, пользуясь схемой, изложенной выше). Этот вариант включается в множество Парето. В нашем примере это В ₁. Анализируются варианты решений (для каждого критерия в отдельности) для тех критериев, в которые не входит выбранный наиболее часто повторяющийся вариант. В нашем примере это крите­рии К ₄ и К ₅, каждому из которых соответствует всего один вариант В ₂. Этот вариант можно сразу же включить в множество Парето. Если какому-то критерию соответствует несколько вариантов решений, то они сравниваются попарно между собой (сравнение проводится только для вариантов, соответствующих одному и тому же критерию). При сравнении двух вариантов, например i и j, возможны рассмотренные выше три случая, в каждом из которых делается соответствующий вывод. Те варианты решений, которые останутся после завершения изло­женной процедуры сравнения, включаются в множество Парето.

После того как построено множество Парето, оно записывается в окончательном виде. В нашем примере π = { B ₁, В ₂}. Остальные варианты оказались исключенными из дальнейшего рассмотрения. Если сравнить между собой оставшиеся варианты (в нашем примере B ₁ и В ₂), то они окажутся несравнимыми. Если же сравнить их с отброшенными альтернативами (в нашем примере В ₃, В ₄, В ₅), то обязательно один из оставшихся вариантов (в нашем примере или B ₁, или В ₂) не хуже их (или одного из них) по всем критериям и хотя бы по одному критерию лучше.

Для выбора наилучшего решения к оставшимся альтернативам применяется в зависимости от условий задачи один из методов первой группы (метод свертки, метод главного критерия, метод пороговых критериев, метод расстояния и т.д.) либо графические методы, например метод диаграмм [1, 28].

В нашем примере для определения наилучшего варианта из двух оставшихся построим диаграмму в полярных координатах. Диаграмма строится сле­дующим образом. Нарисуем круг и в нем восемь равномерных шкал (по числу критериев), на которые нанесем числовые и словесные оценки для каждого варианта таким образом, что лучшие значения располага­ются дальше от центра, а худшие − ближе к нему. В прин­ципе, не имеет значения, как проградуированы шкалы, главное, чтобы было видно постепенное изменение критериев, отражающее тенденцию к ухудшению при движении от периферии к центру. После нанесения оценок по критериям на соответствующих шкалах соединяем точки на осях для каждого варианта замкнутой ломаной линией и получаем два многоугольника. Теперь сравниваем на глаз площади многоугольников. Большей пло­щади соответствует лучший вариант решения, причем это различие должно быть явно заметным, так как метод является приближенным. Если площади примерно одинаковы, то оба варианта практически эквивалентны. В нашем случае, как легко убедиться, предпочтительным (наилучшим) является В ₁, так как соответствующий ему многоугольник явно превышает по площади многоугольник для В ₂ (убедитесь в этом, сделав построение самостоятельно).

Для уточнения решения в данной задаче рекомендуется использовать аддитивную свертку. Так как все критерии считаются одинаково важными, то общий критерий равен среднему значений частных критериев для каждого варианта. Чтобы провести расчеты, преобразуем словесные оценки в балльные по следующему правилу: очень высокое значение (очень большое) − 5; высокое (большое) − 4; среднее − 3; низкое − 2; очень низкое − 1. Тогда получим для первого варианта K (B ₁) = 30/8, для второго K (B ₂) = 25/8, т.е. предпочтителен первый вариант, что совпадает с результатом по диаграмме.

Может возникнуть вопрос, зачем применять метод диаграмм,еслипроще использовать аддитивную свертку. Метод диаграмм это – приближенный метод, что является его преимуществом, так как позволяет нивелировать (сгладить) ошибки в оценках вариантов по критериям, приведенных в табл. 1 к данному примеру. Подсчитаем ошибку выбора. Обозначим ошибку оценок таблицы s. Тогда среднеквадратичная ошибка определения общего критерия составит , где n – число исходных критериев (в нашем примере n =8), а доверительная ошибка равна (при вероятности Р = 0.95) . На такую величину могут отличатся друг от друга значения K (B ₁), К (В ₂), К (В ₃) и т.д. по случайным причинам. Следовательно, если для какой-то пары вариантов разность значений общего критерия K меньше Δ K, то эти варианты равноправны между собой (равноценны). Поэтому нет необходимости очень точно рассчитывать значение общего критерия для каждого варианта решения. Если же разность значений общего критерия K больше Δ K, то варианты различаются значимо, и лучше тот, у которого значение критерия больше. Проведем расчеты. В нашем случае ошибка оценок таблицы составляет s = 1,2, поэтому доверительная ошибка ∆ K = 0,7 s = 0,8 (n =8). Сравним разность К (B 1) – К (B 2) с ошибкой (сравнивать нужно по модулю, чтобы разность была всегда положительной). Так как разность меньше ошибки, то решения B 1 и B 2 являются равноправными с учетом ошибки. Хотя точный расчет дает, что B 1 лучше B 2, однако достоверность такого вывода сомнительна, так как значения общего критерия для этих вариантов различаются незначимо.

Задача 7. В таблице даны два множества X и Y, а также тип отношения R. По данным таблицы выберите из множеств X и Y элементы, связанные отношением R; определите систему, состоящую из элементов множеств X и Y с отношением R; проведите топологический анализ системы, а именно определите первый структурный вектор и вектор препятствий комплекса K_X (Y, R) либо K_Y (X, R), число несвязных компонентов комплекса, степень связности и эксцентриситет каждого симплекса, входящего в комплекс; укажите, какой из симплексов является наиболее адаптированным; насколько сильно связан комплекс.

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

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

Пример 1. Постройте матрицу инциденций для двух множеств объ­ектов по отношению соответствия. Проведите топологический анализ системы по этому отношению. Первое множество Х – измерительные приборы (ИП), а второе Y – решаемые измерительные задачи (ИЗ); X = {ИП₁, ИП₂,..., ИП₆,}; Y = {ИЗ₁, ИЗ₂,..., ИЗ₇}. Матрица инциденций дана в табл. 1. Она соответствует отношению соответствия “Прибор ИП _i соответствует задаче ИЗ _k, если последнюю можно решить этим прибором” (в клетке (i, k) матрицы стоит 1, если отношение выполняется, и 0 – если не выполняется).

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

Приборы	И31	ИЗ2	ИЗ3	И34	И35	И36	И37
ИП1
ИП2
ИП3
ИП4
ИП5
ИП6

Решение

Топологический анализ проводится по алгоритму, изложенному в главе 6. Выберем для анализа комплекс приборов. Комплекс K_X (Y, R)включает 6 симплексов, имеющих разную связность. Анализ начинается с наибольшей связности, а заканчивается связностью, равной нулю. По матрице инциденций определяем наибольшую связность, для чего нахо­дим строку с наибольшим числом единиц. Это строка ИП₁, содержащая пять единиц, следовательно, наибольшая связность комплекса на единицу меньше q = 5 − 1 = 4. На этом уровне связности имеется один компонент {ИП₁}, т.е. q₄ = 1. Понижаем уровень связности на единицу. На уровне связности q = 3 имеем два симплекса ИП₁ и ИП₃, так как им в матрице инциденций соответствуют строки с не менее чем четырьмя единицами. Теперь надо определить можно ли эти симплексы объединить в один компонент либо нет, т.е. различимы они по своим связям или нет. В соответствии с определением, чтобы на уровне связности q = 3 симплексы ИП₁ и ИП₃ были неразличимы, т.е.их можно было объединить в один компонент, они должны иметь по 3 + 1 = 4 общих столбца с единицами. В нашем примере таких столбцов всего два ИЗ₂ и ИЗ₃, т.е. симплексы объединить нельзя. Следовательно, на уровне q = 3 имеем два различных компонента {ИП₁}, {ИП₃}, т.е. q₃ = 2. Опять понижаем размерность на единицу. На уровне q = 2 имеем три симплекса ИП₁, ИП₃, ИП₂ (им в матрице инциденций соответствуют строки с не менее чем 2+ 1 = 3 единицами). Проверяем для каждой пары симплексов условия объединения в один компонент. Для этого они должны иметь по q + 1 = 3 общих столбца с единицами, что не выполняется. Следовательно, на уровне q = 2 имеем три компонента {ИП₁}, {ИП₃}, {ИП₂} и q₂ = 3. На уровне связности q = 1 имеем четыре симплекса ИП₁, ИП₂, ИП₃, ИП₄ (им соответствуют строки хотя бы с двумя единицами). Проверим условие объединения. Для объединения какой-то пары симплексов на этом уровне в один компонент достаточно, чтобы было два общих столбца с единицами. Условия выполняются. Так, например, симплексы ИП₁ и ИП₂ имеют общие столбцы ИЗ₃, И3₄; симплексы ИП₂ и ИП₃ имеют общие столбцы ИЗ₃, И3₆; симплексы ИП₂ и ИП₄ имеют общие столбцы ИЗ₃, И3₄. Следовательно, все симплексы связаны двумя общими столбцами, т.е. их все можно объединить в один компонент {ИП₁, ИП₂, ИП₃, ИП₄} и q₁ = 1. Наконец, на уровне q = 0 аналогично определяем, что все симплексы можно объединить в один компонент (кроме симплекса ИП₅, которому соответствует нулевая строка). Суммируем результаты анализа. Для q = 4: q₄ = 1, и имеем один компонент, состоящий из симплекса {ИП₁}, для q = 3: q₃ = 2 и имеем два компонента {ИП₁}, {ИП₃}, для q = 2: q₂ = 3, и имеем три компонента {ИП₁}, {ИП₃}, {ИП₂}, для q = 1: q₁ = 1, т.е. имеем один компонент {ИП₁, ИП₂, ИП₃, ИП₄}, для q = 0: q₀ = 1, имеем один компонент {все симплексы, исключая ИП₅}.

Первый структурный вектор комплекса q = (1 2 3 1 1). Вид вектора показывает, что относительно приборов комплекс сильно связан для больших и малых значений q, а для промежуточных значений q = 3 и q = 2 он распадается на несколько несвязных компонентов. Определим вектор препятствий D = q − I = (0 1 2 0 0). Он показывает, что имеется препятствие в обмене измеряемыми величинами на уровнях связности q = 3 и q = 2.

Для оценки степени интегрированности симплексов в комплексе рассчитаем эксцентриситет. Результаты даны в табл. 2.

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

Приборы	q 0	q max	Эксцентриситет
ИП1			3/2
ИП2			1/2
ИП3
ИП4
ИП5	−1	−1	∞
ИП6

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

Задача 8. Дана проблема. Требуется построить для нее дерево решений.

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

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

Пример 1. Требуется построить дерево решений для проблемы «дорожно- транспортное происшествие».

Решение

Речь идет о построение типовой структуры для описания проблемы. На первом уровне нужно выделить наиболее общие элементы, совокупность которых определяет проблему. Выделим следующие элементы: 1 – субъект (пешеход, водитель), 2 – техническое средство (автомобиль или другой транспорт), 3 – внешние условия (условия движения).

На втором уровне определяются состояния элементов первого уровня. Для субъекта выделим 11 – физическое состояние, 12 – умственное состояние, 13 – эмоциональное состояние; для водителя следует добавить элемент 14 – квалификация. Для технического средства выделим 21 – исправность, 22 – условия в кабине (комфортность). Условия движения состоят из элементов: 31 – дорога, 32 – погода.

На третьем уровне выделяются характеристики состояний (элементов) второго уровня. Для физического состояния выделим элементы 111 – здоровье, 112 – физическая усталость, 113 – зрение и т.п. Для умственного состояния выделим 121 – умственная усталость, 122 – невнимательность и т.п. Для эмоционального состояния: 131 – возбуждение, 132 – нервозность и т.п. Для квалификации: 141 – опыт, 142 – подготовка, 143 – техника вождения. Для элемента 21 на третьем уровне выделим 211 – ремонт, 212 – текущее обслуживание (профилактика). Для элемента 22 имеем 221 – удобство управления, 222 – освещение, 223 – шум в кабине (музыка, разговоры и т.п.). Для элемента 31 выделим 311 – качество покрытия, 312 – интенсивность движения, 313 – наличие указателей, 314 – видимость и т.п. Для элемента 32 выделим: 321 – осадки, 322 – гололед, 323 – туман и т.п.