Лекции и учебные пособия по системному анализу

Системный анализ

«Системный анализ и проектирование»

Е. Н. Живицкая

Оглавление    
Лекция 11, «О результатах теории информации» Лекция 13, «Выбор в условиях статической неопределенности»

Лекция 12: Языки описания выбора

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

Выбор как реализация цели

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

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

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

Задачи выбора чрезвычайно многообразны, различны и методы их решения. Прежде всего, введем понятия, общие для всех задач выбора.

Будем представлять принятие решения как действие над множеством альтернатив, в результате которого получается подмножество выбранных альтернатив. Сужение множества альтернатив возможно, если имеется способ сравнения альтернатив и определение наиболее предпочтительных. Каждый такой способ называют «критерием предпочтения». Обратим внимание на то, что при таком описании выбора считают сами собой разумеющимися, уже пройденными, два чрезвычайно важных этапа системного анализа:

  1. порождение множества альтернатив, на котором предстоит осуществлять выбор;
  2. определение целей, ради достижения которых производится выбор.

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

Множественность задач выбора

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

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

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

На примере описания выбора видно, как об одном и том же явлении можно говорить на языках различной общности. К настоящему моменту сложились три основных языка описания выбора. Самым простым и наиболее развитым (и, быть может, поэтому чаще употребляемым) является критериальный язык.

Критериальный язык описания выбора

Такое название языка связано с основным предположением, состоящим в том, что каждую отдельно взятую альтернативу можно оценить конкретным числом (значением критерия), и сравнение альтернатив сводится к сравнению соответствующих им чисел.

Пусть x — некоторая альтернатива из множества X. Считается, что для всех x может быть задана функция q(x), которая называется критерием (критерием качества, целевой функцией, функцией предпочтения, функцией полезности) и обладает тем свойством, что если альтернатива x1 предпочтительнее x2 (будем обозначать это x1>x2 ), то q(x1)>q(x2) и обратно. Если теперь сделать еще одно важное предположение, что выбор любой альтернативы приводит к однозначно известным последствиям (т.е. считать, что выбор осуществляется в условиях определенности) и заданный критерий q(x) численно выражает оценку этих последствий, то наилучшей альтернативой x* является, естественно, та, которая обладает наибольшим значением критерия:

  x*=argmax{q(x)}, (1)

Задача отыскания x*, простая по постановке, часто оказывается сложной для решения, поскольку метод ее решения определяется как характером множества X, так и характером критерия q(x).

Чаще всего на практике оценивание любого варианта единственным числом оказывается неприемлемым упрощением. Более полное рассмотрение альтернатив приводит к необходимости оценивать их не по одному, а по нескольким критериям, качественно различающимся между собой. Например, при выборе конструкции самолета проектировщикам следует учитывать множество критериев: технических, технологических, экономических, социальных, эргономических и пр. Даже в обычной жизни при выборе мы почти никогда не используем единственный критерий: вспомним хотя бы затруднения при выборе подарка ко дню рождения или при выборе места стоянки в турпоходе.

Сведение многокритериальной задачи к однокритериальной

Итак, пусть для оценивания альтернатив используется несколько критериев qi(x); i = 1...p. Как же тогда осуществлять выбор? Рассмотрим наиболее употребительные способы решения многокритериальных задач. Первый способ состоит в том, чтобы многокритериальную задачу свести к однокритериальной. Это означает введение суперкритерия, т.е. скалярной функции векторного аргумента:

  q0(x)= q0[q1(x), q2(x), ..., qp(x)]. (2)

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

  q0 = ∑{αi⋅qi/Si}, (3)
  1 - q0 = ∏{1 - [βi⋅qi/Si]} (4)

Коэффициенты Si обеспечивают, во-первых, безразмерность числа Qi/Si (частные критерии могут иметь разную размерность) и, во-вторых, в необходимых случаях (как в формуле 4) выполнения условия Bi⋅Qi/Si < 1. Коэффициенты Ai и Bi отражают относительный вклад частных критериев в суперкритерий.

Итак, при данном способе задача сводится к максимизации суперкритерия:

  x* = argmax{q0[q1(x), ..., qp(x)]} (5)

Очевидные достоинства объединения нескольких критериев в один суперкритерий сопровождаются рядом трудностей и недостатков, которые необходимо учитывать при использовании этого метода. Оставив в стороне трудности построения самой функции и вычислительные трудности ее максимизации, обратим внимание на следующий очень важный момент. Упорядочение точек в многомерном пространстве в принципе не может быть однозначным и полностью определяется видом упорядочивающей функции. Суперкритерий играет роль этой упорядочивающей функции, и его даже «небольшое» изменение может привести к тому, что оптимальная в новом смысле альтернатива окажется очень сильно отличающейся от старой.

Условная максимизация

Недостатки свертывания нескольких критериев заставляют искать другие подходы к решению задач многокритериального выбора. Рассмотрим второй способ решения таких задач. Он заключается в использовании того факта, что частные критерии обычно неравнозначны между собой. Наиболее явное выражение этой идеи состоит в выделении основного, главного критерия и рассмотрении остальных как дополнительных, сопутствующих. Такое различие критериев позволяет сформулировать задачу выбора как 1 задачу нахождения условного экстремума основного критерия:

  x* = arg{ max q1(x)|qi(x) = Ci, i=2,3,...p} (6)

при условии, что дополнительные критерии остаются на заданных им уровнях.

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

  x*=arg{ max q1(x)|qi(x) ≤ Ci, i=2,3...,p} (7)

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

Поиск альтернативы с заданными свойствами

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

Удобным свойством является возможность задавать желательные значения qi* критериев так точно, как и в виде верхних или нижних границ. Назначаемые значения величин qi* иногда называют уровнями притяжения, а точки их пересечения в p-мерном пространстве критериев — целью или опорной точкой.

Теперь идея оптимизации состоит в том, чтобы, начав с любой альтернативы, приближаться к x* по некоторой траектории в пространстве.

Это достигается введением числовой меры близости между очередной альтернативой x и целью x*, т.е. между векторами q(x)=[q1(x)<...qp(x)] и q*(x)=[q1*(x)<...qp*(x)]. Можно по-разному количественно писать эту близость, что и определяет методы решения задачи.

Нахождение паретовского множества

Четвертый полностью формализуемый способ многокритериального выбора состоит в отказе от выделения единственной «наилучшей» альтернативы и соглашении о том, что 1 предпочтение одной альтернативе перед другой можно отдавать только если первая по всем критериям лучше второй. Если же предпочтение хотя бы по одному критерию расходится с предпочтением по другому, то такие альтернативы признаются несравнимыми. В результате по парного сравнения альтернатив все худшие по всем критериям альтернативы отбрасываются, а все оставшиеся несравнимые между собой принимаются. Если все максимально достижимые значения частных критериев не относятся к одной и той же альтернативе, то принятые альтернативы образуют множество Парето и выбор на этом заканчивается. При необходимости же выбора единственной альтернативы следует привлекать дополнительные соображения: вводить новые добавочные критерии и ограничения, бросить жребий, либо прибегать к услугам экспертов.

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

Подведем итог

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

Описание выбора на языке бинарных отношений

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

  1. отдельная альтернатива не оценивается, т.е. критериальная функция не вводится;
  2. для каждой пары альтернатив некоторым образом можно установить, что одна из них предпочтительнее другой либо они равноценны или несравнимы (чаще всего последние два понятия отождествляются);
  3. отношение предпочтения внутри любой пары альтернатив не зависит от остальных альтернатив, предъявленных к выбору.

Математически бинарное отношение R на множестве X определяется как определенное подмножество упорядоченных пар (x,y). Удобно использовать обозначение xRy, если x находится в отношении R c y. Множество всех пар {(x,y), x, y ∈ X } называется полным (»универсальным») бинарным отношением. Поскольку в общем случае не все возможные пары (x,y) удовлетворяют условиям, накладываемым отношением R, бинарное отношение является некоторым подмножеством полного бинарного отношения R.

Задать отношение — это значит тем или иным способом указать все пары (x,y), для которых выполнено отношение.

Способы задания бинарных отношений

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

Первый, очевидный, способ состоит в 1 непосредственном перечислении таких пар. Ясно, что он приемлем лишь в случае конечного множества R.

Второй удобный способ задания отношения R на конечном множестве — матричный. Все элементы нумеруются, и матрица отношения R определяется своими элементами для всех i и j. Известным примером такого задания отношений являются турнирные таблицы (если ничьи обозначить нулями, как и проигрыш, то матрица изобразит отношение «xi — победитель yj»).

Третий способ — задание отношения — 1 графом. Вершинам графа G(R) ставят в соответствия (пронумерованные) элементы множества X, и если xiRyj, то от вершины xi проводят направленную дугу к вершине xj.

Для определения отношений на бесконечных множествах альтернатив используется четвертый способ — задание отношения R - 1 сечениями. Множество

?

называется верхним сечением отношения, а множество

R-(x) = {y ∈ X | (y,x) ∈ R}

нижним сечением. Иначе говоря, верхнее сечение — это множество всех y, которые находятся в отношении xRy с заданным элементом x, а нижнее сечение — множество всех y, с которыми заданный элемент x находится в отношении R. Отношение однозначно определяется одним из своих сечений.

Подведем итог

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

Некоторые особенности выбора привели к построению третьего, еще более общего языка его описания — «языка функций выбора». Во-первых, нередко приходится сталкиваться с ситуациями, когда предпочтение между двумя альтернативами зависит от остальных альтернатив. Например, предпочтение покупателя между чайником и кофеваркой может зависеть от наличия в продаже кофемолки. Во-вторых, возможны такие ситуации выбора, когда понятие предпочтения вообще лишено смысла. Например, по отношению к множеству альтернатив довольно обычными являются правила выбора «типичного», выбора «среднего», выбора «наиболее отличного, оригинального», теряющие смысл в случае двух альтернатив. Язык функций выбора является весьма общим и потенциально может описывать любой выбор. Однако его теория находится в начальной стадии развития и пока еще занимается описанием преимущественно старых ситуаций в новых терминах. Знакомство с языком функций выбора выходит за рамки настоящего курса лекций.

Оглавление    
Лекция 11, «О результатах теории информации» Лекция 13, «Выбор в условиях статической неопределенности»