Причины появления многокритериальности

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

Определение. Многокритериальной задачей называется набор , где u – множество, а (i=1,…,m) – функции.

Множество u интерпретируется как множество стратегий оперирующей стороны, а функции gⁱ – как ее критерии.

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

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

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

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

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

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

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

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

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

Эти соображения приводят к следующим определениям.

Определение. Многокритериальной задачей называется набор , где u – множество, а gⁱ – функции, отображающие u во множество действительных чисел .

Нашей целью будет рассмотрение способов построения на основе многокритериальной задачи модели операции вида .

Часто такую операцию строят, задавая функцию , и полагая, что . функцию f в таком случае называют функцией свертки (или просто сверткой) критериев.

Примеры сверток

По техническим причинам удобно разделить цели операций на два класса: количественные и качественные. К первым относятся те, которые могут быть либо достигнуты, либо нет. Ко вторым – те, степень достижения которых может быть выражена числом.

Разумеется, качественная цель может быть описана количественным критерием, который, например, принимает значение 1, если цель достигнута, и значение 0 в противном случае.

Экономический способ свертки. свертка частных критериев g¹,…,g^m представляет собой взвешенную сумму .

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

Пример. Предприятие выпускает m видов продукции. критерии g¹,…,g^m выражают количества продукции каждого из видов, выпущенных предприятием. доходы предприятия от реализации продукции выражаются сверткой . коэффициенты свертки в этом случае имеют смысл цен.

Пример. Рассмотрим деятельность фирмы за m лет. критерии g¹,…,g^m выражают прибыль фирмы в соответствующие годы. свертка оценивает суммарную прибыль за весь период. числа l₁,…l_m в этом случае имеют смысл коэффициентов дисконтирования.

Пример. В классической биатлонной гонке имеется два критерия: количество промахов g¹ и время прохождения дистанции g². Результат спортсмена оценивается по линейной свертке (если время измерять в секундах).

Разбиение на удовлетворительные и неудовлетворительные. пусть имеется количественный критерий g и число g. свертка задает качественный критерий

Пример. Знания студента на экзамене оценивается количественным критерием g, принимающим значения от двух до пяти. Качественная цель сдать экзамен описывается критерием

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

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

Лексикографическая свертка. Пусть даны критерии g¹,…,g^m, ранжированные в порядке возрастания номеров. Сначала находятся все точки максимума критерия g¹, из них выбираются те, которые доставляют максимум критерию g² и так далее. Наконец, из уже отобранных, выбираются те, которые доставляют максимум критерию g^m. Выбранные на последнем этапе стратегии называются точками лексикографического максимума.

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

Дизъюнкция. Пусть есть m качественных критериев g¹,…,g^m. цель, состоящая в достижении, по крайней мере, одной из частных целей описывается критерием .

Конъюнкция. Пусть есть m качественных критериев g¹,…,g^m. Цель, состоящая в достижении, сразу всех частных целей описывается критерием .

Пример. Если за сессию студенту предстоит сдать m экзаменов и каждый из критериев g¹,…,g^m описывает сдачу одного из них, то цель, состоящая в успешной сдаче сессии, описывается критерием .

Отрицание. Пусть имеется качественный критерий g. критерий 1–g описывает цель, состоящую в не достижении исходной.

Пример. Если исходная цель g состоит в том, чтобы избежать скандала, то цель, состоящая в попадании в скандальную хронику, описывается критерием 1–g.

Обобщенная дизъюнкция. Часто используется следующий способ свертки. Пусть есть m количественных критериев g¹,…,g^m. результирующий критерий образуется по правилу .

Пример. Пусть в шоссейной велогонке принимают участие m спортсменов из одной команды и критерии g¹,…,g^m задают места, занятые ее членами. Очень часто все члены команды работают на одного лидера, то есть критерий команды есть .

Обобщенная конъюнкция. Это свертка, при которой количественные критерии g¹,…,g^m заменяются общим критерием .

В экономических моделях такой способ свертки применяется при агрегировании абсолютно не взаимозаменяемых продуктов.

Пример. Пусть для производства изделия требуются комплектующие m видов и количества произведенных деталей описываются числами g¹,…,g^m. критерий описывает количество готовых изделий, которое из них можно собрать. Числа имеют при этом смысл количества деталей i-го вида, необходимых для сборки одного готового изделия.

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

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

Приведенные выше примеры являются наиболее простыми, и потому наиболее часто встречающимися. Но, разумеется, бывают и более экзотические способы.

Принцип наименьшего сожаления. Это свертка, при которой количественные критерии g¹,…,g^m заменяются общим критерием , который нужно минимизировать.

Принцип принятия решений в ЕЭС. По новым законам решение принимается по правилу двойного большинства: решение считается принятым, если за него проголосовало 55% стран население которых составляет 65%. в этом случае можно считать, что имеется столько качественных критериев, сколько стран принимает участие в голосовании. Из них делается два количественных критерия, которые в свою очередь сворачиваются в один качественный.

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

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

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

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

Теорема о свертке

Теорема. Пусть каждый из критериев g¹,…,g^m принимает лишь два значения 0 и 1, а f:{0,1}^m®{0,1} – произвольная функция. тогда критерий g,определенный условием g(u)=f(g¹(u),…,g^m(u)), может быть выражен через следующие элементарные операции:

1. конъюнкция: g¹,…,g^m ® ;

2. дизъюнкция: g¹,…,g^m ® ;

3. отрицание: gⁱ ® 1–gⁱ.

Доказательство. Пусть y=(y₁,…,y_m) – произвольный булев вектор размерности m (здесь y_i равны 0 или 1 при любом i=1,…,m). рассмотрим функцию f_y :{0,1}^m®{0,1}, определенную условием , где z_i=x_i, если y_i=1, и z_i=1–x_i, если y_i=0. непосредственно проверяется, что f_y(y)=1, и f_y(x)=0 для любого x¹y.

Пример. На референдуме о сохранении союза советских социалистических республик гражданам предлагалось ответить на четыре вопроса. Власти предлагали своим сторонникам ответить «да, да, нет, да». таким образом, есть, четыре вспомогательных качественных критерия gⁱ (ответ на i-ый вопрос). Если общая цель g состоит в лояльности власти, то она выражается через частные с помощью свертки g=g¹g²(1–g³)g⁴.

Для заданной нам функции f, обозначим y={y: f(y)=1}. Покажем, что интересующий нас критерий g представляется в виде

. (28)

В самом деле, если g(u)=1, то по определению вектор t=(g¹(u),…,g^m(u)) принадлежит множеству y. значит, произведение в формуле (28) содержит множитель (1–f_y(g¹(u),…,g^m(u))), равный нулю. следовательно, и все произведение равно нулю, а вся правая часть формулы (28) равна 1.

Если же g(u)=0, то вектор t=(g¹(u),…,g^m(u)) не принадлежит множеству y, и для всех yÎy имеем f_y(g¹(u),…,g^m(u))=0. значит, для этого u все сомножители в формуле (28) равны 1, а тогда и произведение в правой части равенства (28) равно 1, а сама правая часть равна нулю.

Для завершения доказательства остается заметить, что при построении функций f_y мы пользовались лишь операциями отрицания и конъюнкции, а в формуле (28) использовалась еще и дизъюнкция.

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

Теорема. Пусть каждый из критериев g¹,…,g^m принимает лишь конечное число значений, а – произвольная функция. Тогда критерий g,определенный условием g(u)=f(g¹(u),…,g^m(u)), может быть выражен через следующие элементарные операции:

1. экономическая свертка: g¹,…,g^m ® ;

2. разбиение на удовлетворительные и неудовлетворительные: gⁱ ®

3. конъюнкция: g¹,…,g^m ® ;

4. дизъюнкция: g¹,…,g^m ® ;

5. отрицание: gⁱ ® 1–gⁱ.

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

1. для каждого i=1,…,m и каждого с помощью элементарной операции второго типа образуем вспомогательный критерий . разумеется, критерий может быть выражен как функция критерия gⁱ.

2. верно и обратное: критерий gⁱ может быть представлен как функция критериев . чтобы убедиться в этом, заметим, что

(29)

где положено =0.

в самом деле, если , то для всех j>l справедливо равенство , а для всех j≤l будем иметь . поэтому для такого u правая часть равенства (29) может быть переписана в виде . эта сумма, очевидно, равна , то есть равенство (29) справедливо.

3. рассмотрим вспомогательные критерии g_g(u), определенные условиями

(здесь ). Каждый из этих критериев является функцией критерия g.

4. тогда по условию теоремы, тогда критерий может быть представлен, как функция критериев g¹,…,g^m. значит, он может быть представлен и как функция вспомогательных критериев .

5. но каждый из критериев g_g и принимает лишь значения 0 и 1, поэтому в силу предыдущей теоремы, каждый из критериев g_g может быть выражен через критерии с использованием лишь элементарных операций конъюнкции, дизъюнкции и отрицания.

6. аналогично формуле (29) доказывается равенство

где g₀=0.

Для завершения доказательства остается заметить, что критерии мы получили, пользуясь только сверткой типа 2, на шаге 4 для получения критериев g_g использовались свертки типов 3,4,5, и, наконец, на шаге 6 использовалась свертка типа 1. теорема доказана.

Примеры

Пример. Пусть каждый из критериев g¹,…,g^m принимает лишь конечное число значений. Значения, которые может принимать критерий gⁱ, обозначим в порядке возрастания символами . опишем, как с помощью элементарных операций получить свертку .

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

используя разбиение на удовлетворительные и неудовлетворительные. Тогда .

Пример. Пусть каждый из критериев g¹,…,g^m принимает лишь конечное число значений. значения, которые может принимать критерий gⁱ, обозначим в порядке возрастания символами . опишем, как с помощью элементарных операций получить свертку .

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

Используя разбиение на удовлетворительные и неудовлетворительные. тогда ..

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

Пусть и . обозначим и положим . нужный нам критерий задается экономической сверткой .