Лекция 4 Многокритериальные задачи

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

В такой постановке мы опять сталкиваемся с проблемой сочетания формальных и неформальных методов исследования сложных систем.

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

Оптимизация выбранного совокупного критерия стандартная (пусть временами и сложная) математическая задача.

Рассматриваются наиболее интересные с практической точки зрения примеры сверток и демонстрируется тщетность попыток изобретения «суперсвертки», претендующей на формализацию понятия самого эффективного способа свертки. Для этого приводится замечательный результата Ю.Б. Герейера о том, что любая функция свертки может быть интерпретирована как суперпозиция максимум пяти видов сверток.

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

Вернемся к схеме согласования интересов ( к ее формализуемой части). Функции выигрыша (критерии эффективности) анализируемой социально-экономической системы и подсистем (субъек5тов управления), соответственно и,i=1,2,…,n, можно интерпретировать как текущие совокупные активы, определяемые совокупностью материального богатства («чистые активы» в принятом в экономике определении), ценности людских и природных ресурсов.

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

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

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

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

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

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

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

Таким образом, критерии эффективности каждого субъекта включают в себя, по крайней мере, три составляющие:

- оценка экономической эффективности,

- оценка людского потенциала,

- оценка природных ресурсов.

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

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

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

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

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

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

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

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

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

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

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

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

2. Разбиение критериев на удовлетворительные и неудовлетворительные.

Зададим «удовлетворительные» значения критериев эффективности ,i=1,2,…,m. Например, минимальные значения желаемых величин доходности и надежности ценных бумаг.

Качественный критерий эффективности вложений в ценные бумаги имеет вид:

M=1, еслиgⁱ

M=0, в остальных случаях.

Этот вариант может применяться при m=1. При этом количественная цель (увеличение доходности) заменяется качественной – получение доходности, не меньшей некоторой фиксированной величины.

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

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

Пусть варианты вложения оцениваются следующим образом

	95	70	90	50	95	95
	10	70	30	70	5	15
x

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

С точки зрения доходности, оптимальны второй и четвертый варианты. Из них наиболее надежный – второй вариант.

4. Логическое объединение качественных целей.

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

.

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

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

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

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

Пример. Цели уменьшить риск r операции и увеличить надежность g, связаны соотношениемg= 1-r

5. Обобщенное логическое свертывание количкритериев

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

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

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

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

Заметим, что свертки (4.1), (4.2) прямо следуют из (5.1), (5.2), если все используемые функции принимают значения только 0 или 1.

3. Замена критерия на антагонистический. В этом случае, аналогичном случаю 4.3, максимизация критерия заменяется на минимизацию, то есть критерий g… , заменяется наM= -

Связь 5и4-ЮБ

Пример. Инвестор анализирует целесообразность вложения средств в проект. Он рассматривает две цели: увеличение доходности и надежностиРассмотрим различные варианты сверток.

Экономический. Пусть потеря 1% надежности для инвестора компенсируется 5% доходности. Тогда его критерий эффективности можно записать в виде

Разбиение на удовлетворительные и неудовлетворительные. Если инвестора устраивают только варианты: , а, его качественная цель запишется в виде:

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

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

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

Покажем это на примере качественных целей

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

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

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

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

Доказательство.Пустьv=(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.

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

. (*)

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

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

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

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

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

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

1. экономическая свертка;

2. разбиение на удовлетворительные и неудовлетворительные;

3. конъюнкция(обобщенная);

4. дизъюнкция (обобщенная);

5. отрицание (максимизация антагонистического критерия).

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

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

Определение. Будем говорить, что управление xX доминирует (по Парето) управление yX, а соответствующий вектор выигрышей (g¹(x),…,g^m(x)) доминирует вектор (g¹(y),…,g^m(y)), если для всех i=1,…,m выполняются неравенства gⁱ(x)gⁱ(y), а для некоторого k выполняется строгое неравенство g^k(x)>g^k(y).

Определение. Будем говорить, что управление xX сильно доминирует (по Парето) управление yX, а соответствующий вектор выигрышей (g¹(x),…,g^m(x)) сильно доминирует вектор (g¹(y),…,g^m(y)), если для всех i=1,…,m выполняются неравенства gⁱ(x)>gⁱ(y)

Определение. Управление xX, и соответствующий вектор выигрышей (g¹(x),…,g^m(x)) называются эффективными (оптимальными по Парето), если не существует управления yX, которая доминировала бы управление x.

Определение. Управление xX, и соответствующий вектор выигрышей (g¹(x),…,g^m(x)) называются слабо эффективными, если не существует управления yX, которая сильно доминировала бы управление x.

Пусть в пространстве критериев множество выигрышей задается ломаной OABCDO.

Тогда отрезок BC– определяет множество эффективных точек, отрезокAB– слабоэффективных точек.

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

Вильфредо Парето(1848-1923) – итальянский экономист.