Проблемы построения обобщённого критерия для векторных задач оптимизации

(этот материал взят из книги В.В. Розена "Модели принятия решений в экономике")

Вопросы:

· Сложности в построении обобщённого критерия; примеры.

· Формальное определение обобщённого критерия. Эквивалентность обобщённых критериев.

· Локальный коэффициент замещения (ЛКЗ). Карта безразличий. Условия постоянства ЛКЗ.

 

1. Как было сказано ранее, задание обобщённого критерия превращает задачу многокритериальной оптимизации в задачу однокритериальной оптимизации. Первоначально кажется, что это единственный способ. Однако на пути построения обобщённого критерия (итоговой “синтетической” оценки) имеются весьма существенные, а подчас – непреодолимые препятствия.

В качестве примера можно рассмотреть задачу построения обобщённой оценки некоторой реальной системы (объекта). Частные критерии оценки системы можно разбить на две группы: критерии, отражающие эффективность системы, и критерии, связанные со стоимостью системы. Предположим, что уже удалось построить обобщённый критерий эффективности (Э) и обобщённый критерий стоимости (С). Как теперь соединить критерий стоимости и эффективности в один критерий? Наиболее естественным представляется в качестве такой оценки рассматривать “удельную эффективность”, т.е. отношение эффективности к стоимости:

f=Э/С. Так как обобщённый критерий указывает “итоговую” оценку полезности системы для принимающего решение, то по величине обобщённого критерия устанавливается предпочтение между сравниваемыми объектами.

Рассмотрим теперь показатели стоимости и эффективности для трёх систем: a₀, a₁, a₂, представленные на рис. 9. Здесь f₀ = Э₀/С₀, f₁ = Э₁/С₁,

f₂ = Э₂/С₂, причём f₁ > f₀, f₂ > f₀ .

Рис. 9. Отношение эффективности к стоимости для трёх систем

 

Из рисунка можно определить, что f₁ = = 1, f₀ = = , f₂ = = .

Таким образом, по обобщённому критерию системы a₁ и a₂ являются более предпочтительными, чем система a₀. Однако система a₁ имеет очень низкую эффективность, а система a₂ – очень высокую стоимость. Ясно, с практической точки зрения ни система a₁, ни система a₂ не могут рассматриваться как удовлетворительные. Поэтому критерий f=Э/С не может претендовать на роль “адекватного” обобщённого критерия. Отметим, что даже на первом шаге – объединении всех частных критериев эффективности в единый обобщённый критерий (Э) можно встретиться с весьма существенными трудностями, особенно в случае наличия критериев, характеризующих объект с разных сторон (например, скорость автомобиля и его надёжность).

Обратимся теперь к проблеме построения обобщённого критерия в виде взвешенной суммы частных критериев, которая превращает векторную оценку y = (y₁, . . . , y_m) в скалярную оценку Ф(y) = λ₁y₁ + … + λ_my_m ,(где λ_j o, j = ). Предложено множество различных способов нахождения весовых коэффициентов, однако ни один из них не может претендовать на роль универсального. Рассмотрим в качестве примера следующий способ нахождения весовых коэффициентов:

 

λ_J =, где M_j = |f_j(x)| .

В этом случае f(x) = , (8)

т.е. итоговой численной оценкой исхода а, является сумма нормализованных оценок по всем критериям (нормализованная оценка по j-му критерию есть отношение f_j(x)/M_j). На первый взгляд, обобщённый критерий (8) представляется вполне разумным. Однако, следующий пример выявляет один существенный недостаток критерия (8).

Предположим, требуется сравнить два альтернативных варианта мест работы А и В, векторные оценки которых приведены в табл.1

Таблица 1

	Зарплата (руб.)	Длительность отпуска (дни)	Время поездки (мин)
А			-60
В			-40

 

Здесь M₁ = 900, М₂ = 30, М₃ = 60, откуда

f(A) = + - = ; f(B) = + - = .

Так как f(B) > f(A), то альтернатива В более предпочтительна, чем альтернатива А.

Пусть теперь наряду с альтернативами А и В появилась ещё одна альтернатива С, которая характеризуется векторной оценкой (400, 60,-100). В этом случае = 900, = 60, = 100, откуда f(A) = + - = ;

f(B) = + - = ; f(C) = + - = .

Получаем, что теперь альтернатива А стала более предпочтительной, чем альтернатива В, т.е. порядок предпочтения альтернатив А и В получился в этом случае обратным! Итак, наличие ещё одной альтернативы с меняет предпочтения между альтернативами А и В. Это парадоксальное свойство называется нарушением независимости предпочтений относительно посторонних альтернатив. (При этом следует заметить, что дополнительная альтернатива С здесь не конкурирует ни с А, ни с В, так как А и В предпочтительнее, чем С).

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

 

2. Рассмотрим теперь в общем виде проблему построения обобщённого критерия для многокритериальных задач принятия решений. Ограничимся случаем двух критериев, оценки по которым будем обозначать через u и v соответственно; тогда каждая векторная оценка может быть представлена точкой на координатной плоскости (u, v). Считаем, что оба критерия являются позитивными, следовательно, целью принимающего решение будет увеличение обоих критериев.

Построение обобщённого критерия представляет собой процедуру, которая “синтезирует” пару оценок (u, v) в единую числовую оценку; формально обобщённый критерий может быть задан в виде отображения

Ф: R R R. Главное, (и, по – существу, единственное) требование, которое должно быть наложено на это отображение, состоит в том, что это отображение должно “сохранять” отношение доминирования по Парето. Поэтому можно дать следующее определение.

Опр. Под обобщённым критерием будем понимать отображение

Ф: RR R , удовлетворяющее условию

(u₁, v₁) (u₂, v₂) Ф(u₁, v₁) > Ф(u₂, v₂). (9)

 

Замечание. Иногда рассматривают ослабленный вариант условия (9), состоящий в импликации

(u₁, v₁)(u₂, v₂) Ф(u₁, v₁)Ф(u₂, v₂). (10)

(Отношение понимается как объединение отношения доминирования по Парето и отношения равенства = ). Например, взвешенная сумма с неотрицательными весовыми коэффициентами удовлетворяет условию (10), а с положительными – более сильному условию (9).

 

Поскольку для обобщённого критерия Ф существенным является не сама величина Ф(u, v), а соотношение типа Ф (u₁, v₁)Ф(u₂, v₂), введём следующее определение.

Опр. Обобщённые критерии и называются эквивалентными, если для любых векторных оценок (u₁, v₁) и (u₂, v₂) выполняется равносильность:

Ф (u₁, v₁) (u₂, v₂) (u₁, v₁) (u₂, v₂)

Например, обобщённые критерии (u, v) = 2u + 3v, (u, v) = =0,4u+0,6v и (u,v)=эквивалентны между собой. Если Ф – обобщённый критерий, то функция = , где – произвольная монотонно возрастающая функция, также будет обобщённым критерием, который эквивалентен критерию .

3. Основной задачей является выявление данных, которые требуются для построения обобщённого критерия. Предположим, что обобщённый критерий (u, v) построен. Тогда уравнение Ф(u, v)=с при каждом фиксированном значении константы с определяет на плоскости переменных (u, v) некоторую кривую, которая называется кривой безразличия. Для любых двух точек М₁(u₁; v₁) и М₂(u₂; v₂), принадлежащих одной кривой безразличия, Ф (u₁,v₁)=Ф(u₂, v₂), поэтому принимающий решение будет рассматривать векторные оценки (u₁, v₁) и (u₂, v₂) как равноценные.

Зафиксируем некоторую точку М(u; v) и проанализируем, что происходит при переходе от точки М к точке при движении по кривой безразличия (рис. 10).

Рис. 10. Кривая безразличия

 

Положим u = - u, v = - v. При переходе от точки М к точке оценка по первому критерию увеличивается на величину |u|, а оценка по второму критерию уменьшается на величину |v | (заметим, что для точек, лежащих на одной кривой безразличия, u и v всегда имеют разные знаки). Так как лицо, принимающее решение рассматривает векторные оценки (u, v) и как равноценные, то для него потеря |v| единиц по второму критерию компенсируется прибавкой |u| единиц по первому критерию. (В эквивалентной форме это можно выразить ещё так: для лица принимающего решение прибавка |v | единиц по второму критерию компенсирует потерю |u | единиц по первому критерию).

Положительное число –(v/u), указывающее соотношение "потерь-прибавок", зависит, конечно, от того, в какую точку произойдёт смещение из точки М по кривой безразличия. Чтобы исключить зависимость от точки , надо взять "бесконечно малое смещение", т.е. перейти к пределу при условии М; последнее эквивалентно тому, что u 0.

Опр. Положительное число

k = (-)

называется локальным коэффициентом замещения (ЛКЗ) в точке М(u, v).

Конечно, в общем случае ЛКЗ зависит от точки М, т.е. k = k(u, v).

Содержательный смысл локального коэффициента замещения заключается в следующем. Если u мало, то можно считать, что -v ku; приняв u за единицу, получаем |v| = -v k. Таким образом, ЛКЗ приблизительно равен той минимальной прибавке по второму критерию, которая компенсирует для лица принимающего решение потерю единицы по первому критерию (равенство тем точнее, чем меньшей взята единица по первому критерию).

Геометрический смысл ЛКЗ ясен из рис. 10: так как v/u есть тангенс угла наклона секущей Мк оси абсцисс, то, переходя к пределу при u 0, получаем следующее правило.

Правило 1. ЛКЗ в точке М(u; v) равен взятому со знаком “минус” тангенс угла наклона к оси абсцисс касательной, проведённой к кривой безразличия в точке М.

Пусть Q R² – некоторое множество векторных оценок. Из определения кривой безразличия следует, что через каждую точку M Q проходит одна кривая безразличия.

Опр. Множество всех кривых безразличия составляет карту безразличий в области Q; типичный вид карты безразличий представлен на рис.11

Рис. 11. Карта безразличий

Будем считать, что кривые безразличия являются гладкими (т.е. имеют касательную в каждой точке).

Правило 2. Задание в области Q карты безразличий равносильно заданию ЛКЗ для каждой точки M Q.

Действительно, предположим, что в области Q задана карта безразличий. Тогда для каждой точки М(u; v) Q существует единственная проходящая через неё кривая безразличия. Взятый со знаком “минус” тангенс угла наклона касательной, проведённой к этой кривой безразличия в точке М, даст по правилу 1 ЛКЗ в точке М.

Обратно, пусть для каждой точки М(u; v) Q задан соответствующий ей локальный коэффициент замещения k(u; v). Тогда для каждой точки области Q известен угловой коэффициент касательной к кривой безразличия. В этом случае можно построить (при некоторых ограничениях на функцию k(u; v)) карту безразличий – это хорошо известный в математике способ построения интегральных кривых в заданном поле направлений.

В заключение данного пункта найдём условия, при которых ЛКЗ является постоянным.

Ø Если в области векторных оценок Q R² ЛКЗ k постоянен, то семейство кривых , составляющих карту безразличий обобщённого

критерия Ф, определяется дифференциальным уравнением dv/du = -k, откуда dv=-kdu, а v = -ku + c, т.е. в этом случае карта безразличий представляет собой семейство параллельных прямых, угловой коэффициент которых равен – k.

Ø Пусть в области Q задана карта К, состоящая из семейства параллельных прямых, имеющих отрицательный угловой коэффициент -k. Тогда обобщённый критерий (u, v) = ku + v совместим с картой К (так как его карта безразличий состоит из линий ku+v=с – прямых, имеющих угловой коэффициент -k, т.е. совпадает с картой К). Получаем, что в этом случае обобщённый критерий, совместимый с картой К, может быть представлен в виде взвешенной суммы критериев u и v (с положительными постоянными коэффициентами).

Ø Предположим, что обобщённый критерий представим в виде взвешенной суммы: Ф(u, v) =u+v, где > 0, > 0 – постоянные. Тогда кривые безразличия этого обобщённого критерия определяются уравнением u + v = с, где с – постоянная величина, т.е. являются прямыми с угловым коэффициентом k = -/; по правилу 1 в этом случае ЛКЗ равен /и является постоянным.

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

a) Обобщённый критерий Ф представим в виде взвешенной суммы частных критериев.

b) Карта безразличий обобщённого критерия Ф состоит из семейства параллельных прямых.

c) Локальный коэффициент замещения в области Q постоянен.

В связи с этим, для представимости обобщённого критерия в виде взвешенной суммы частных критериев необходимо и достаточно постоянного ЛКЗ. Это - очень сильное требование, которое в большинстве экономических задач не выполняется.

Таким образом, при заданном в аналитической форме ЛКЗ задача построения карты безразличия сводится к задаче интегрирования дифференциального уравнения (решения дифференциального уравнения – =-k(u, v)).

Замечание. В качестве обобщённого критерия, совместимого с картой К, может быть взята любая функция, имеющая вид суперпозиции с, где - монотонно возрастающая функция одной переменной. Например, взяв (w) = , получаем обобщённый критерий с₁(u, v) = u.

 

Предыдущая Главная Следующая

Методы последовательной оптимизации

 

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

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