Решение на основе лексикографического упорядочения критериев

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

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

1) >

2) > (10.15)

………

m) > .

В этом случае говорят, что вектор Y лексикографически больше вектора .

Множество векторов (решений), оптимальных по отношению на G (соответственно на D), называют множеством лексикографически оптимальных точек (Opt_lex Y). Так как для любых двух векторов либо один лексикографически больше другого, либо они равны, то множество Opt_lex Y, если оно не пустое, содержит только один элемент. Так на множестве G, изображенном на рис.10.3, лексикографически оптимальной является только точка h.

Лексикографически-оптимальное решение достигается в процессе решения следующей последовательности задач:

1) находим при условии ;

2) находим при условии ;

.....................

m) находим при условии .

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

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

В этом методе каждому критерию соответствует своя строка относительных оценок (i-индекс критерия, j- индекс переменной). Строки располагаются в порядке убывания приоритетов критериев. Сначала симплекс-преобразования выполняются по . При достижении оптимального решения по 1-му критерию () выявляют нулевые оценки небазисных переменных. Если таких нет, то решение единственное и лексикографическая оптимизация завершается. Если они есть, то в строке в столбцах с выделенными нулевыми ищут отрицательные оценки. Небазисная переменная x_s, для которой а <0, вводится в базисное решение, улучшая значение 2-го критерия без ухудшения значения 1-го критерия. Этот процесс продолжается, пока будут выявляться такие перспективные переменные. Если они исчерпались или их не было, то переходят к решению по 3-му критерию, т.е. к выбору перспективных переменных по строке . Введение в решение небазисной переменной х_р улучшит значение 3-го критерия без изменения первых двух, если а <0. Процесс решения многокритериальной задачи завершается, когда на последующих этапах не находятся перспективные переменные.

 

 

Методы главного критерия, свертки, идеальной точки, целевого прогр.

Метод главного критерия

Суть метода состоит в том, что ЛПР выделяет главный критерий (далее f ₁(X)), а на остальные критерии накладывает требования, что они были не меньше задаваемых им минимальных (пороговых) значений t _i. Тогда многокритериальная задача сводится к однокритериальной задаче

(10.16)

Если эта задача разрешима, то ее решение всегда является слабо эффективным, а если оно единственно, то и эффективным. Заметим, что этот вывод не зависит от выбора главного критерия. Рис.10.7 иллюстрирует случай единственного решения задачи (10.16), а рис.10.8 – множества оптимальных решений, лежащего на границе ab, из которого только точка а является эффективной.

Практически задачу (10.16) решают для нескольких наборов значений { t_i }, и затем на основании анализа полученных (слабо) эффективных решений ЛПР определяет наиболее предпочтительное из них.

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

Линейная свертка

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

, (10.17)

где С_i - положительные числа, отражающие веса критериев в структуре предпочтений ЛПР. При групповом ЛПР C_i находятся по индивидуальным весам одним из методов обработки экспертных оценок. Обычно значения С_i нормируются так, чтобы =1. Как следует из теоремы 5, точка максимума функции (10.17) при положительных С_i является эффективной.

Данный способ решения многокритериальной задачи имеет существенные недостатки. Во-первых, большие затруднения возникают при определении весов. Одно дело – расположить критерии по важности, и совсем другое - оценить на сколько или во сколько один критерий важнее другого. Во-вторых, неизвестна связь между значениями весов и значениями критериев в точке максимума F (Х). Очень часто эта зависимость оказывается существенно нелинейной (даже в линейных задачах), включая зоны нечувствительности значений f_i к изменению C_i. Поэтому для получения решения, удовлетворяющего ЛПР, приходится максимизировать F (X) для нескольких наборов С _i. Наконец, заметим, что в свертке (10.17) целесообразно все критерии приводить к одним единицам измерения. С этой целью лучше представлять критерии в относительных единицах, беря за базовое максимальное или желаемое значение. Достоинство метода – в стандартности задачи, к которой сводится исходная многокритериальная проблема.

Пример 10.1. Рассмотрим задачу линейного программирования с тремя критериями: максимизировать

f ₁(X) =- 3 x ₁ + 2 x ₂,

f ₂(X) = 4 x _{1 +} 3 x _2,

f ₃(X)=2 x ₁ - 5 х ₂

при условиях

2 x ₁ + 3 x ₂ 18,

2 x ₁+ x ₂ 10,

x ₁, x ₂ 0.

Допустимая область и линии равного уровня критериев показаны на
рис.10.9. Максимальное значение функции f ₁(X) равно 12 и достигается в точке А(0,6), при этом =18, =-30; max f ₂(X)=24 в точке В(3,4), где =-1 и =-14; mах f ₃(Х)=10 в точке С(5,0), в которой =-15 и =20. Если взять свертку с равными весами, то есть

то результат максимизации F (Х), как легко убедиться, совпадает с максимизацией одной функции f ₃(Х).Таким образом, при равных весах решение по линейной свертке дает наилучшее значение f ₃ и наихудшее для f ₁. Используя параметрическое программи­рование, можно определить диапазон значений C_i (зону нечувствительности), в котором оптимальное решение по F (Х) будет оставаться в точке С.

Максиминная свертка

Как и в предыдущем подходе, ЛПР должен задать веса C_i всем критериям, но обобщенный критерий записывается в виде

F(X)= . (10.I8)

Тогда многокритериальная задача сводится к максимизации F (X) на Х D. Если ввести новую переменную х _о, то эта задача преобразуется к виду

F (Х )=х _о max;

х _о, i = ; (10.19)

X D,

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

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

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

Пример 10.2. Применим рассмотренный подход к задаче из примера 10.1. Снова возьмем равные веса. В соответствии с (10.19) к исходным условиям задачи добавятся ограничения

-3 x ₁+2 x ₂ 3 x ₀

4 x ₁+3 x ₂ 3 x ₀

2 x ₁-5 x ₂ 3 x ₀

и новый критерий х₀ max. Оптимальное решение этой задачи достигается в точке х =х =х = 0, в которой f ₁, f ₂ и f ₃ тоже равны нулю.

Сравним с результатами примера 10.1. При решении по критерию (10.17) получили f_i=-15, а по критерию (10.18) f_i=0. Однако это решение доставляет наихудшее значение критерию f ₂ и ни одному из критериев не обеспечивает максимального значения.

Метод идеальной точки

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

Если эта точка принадлежит достижимому множеству G, то все эффективное (паретовское) множество состоит из этой единственной точки (рис. 10.10) и проблемы как таковой в этом случае нет. Однако идеальная точка обычно лежит вне множества G и поэтому нереализуема. В связи с этим ее иногда называют также утопической. Идея метода состоит в том, чтобы на множестве G найти точку, наиболее близкую к идеальной. Мерой близости выступает некоторая функция расстояния , в качестве которой используют в общем случае взвешенные L_p -метрики

,

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

(10.20)

где - веса отклонений, задаваемые ЛПР ( =1, >0). На практике чаще используют значение р =2. В соответствии с теоремой 5 минимизация такой функции приводит к эффективному решению.

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

Пример 10.3. Найдем решение для модели из примера 10.1 при одинаковых и р =2. Так как =12, =24 и =10, обобщенный критерий запишется в соответствии с (10.20) в виде

.

После отбрасывания общего множителя (1/3), свободного члена (820) и простых преобразований приходим к выражению

.

Используя метод квадратичного программирования, получаем: х =2,97, х =1,52 (точка M на рис.10.9). В этой точке f ₁=-5.87, f ₂=16.44, f ₃=-1.66.

Метрика с р = дает уже рассмотренный ранее подход: критериальная функция определяется как максимальное отклонение

, (10.21)

которое следует минимизировать по X D

Пример 10.4. Если воспользоваться сверткой (10.21) для модели из примера 10.1, то получим решение: х =1,52, х =1,37 (точка N на рис. 10.9), в котором f ₁=-1,82, f ₂=10,19, f ₃=-3,81.

Пример 10.5. Пусть требуется максимизировать два критерия

f ₁ ( X )=- 2 x ₁ +x ₂,,

f ₂ ( X )= 4 x ₁- x ₂

при условиях

x ₁ +x ₂ 8,

-x ₁ +x ₂ 2,

0 x ₁ 6, 0 x ₂ 4.

R

Так как задача содержит две переменные и два критерия, множества D и G предста­ви­мы на плоскос­ти, что позво­ляет наглядно сравнить резу­ль­таты рассмот­ренных подхо­дов (рис.10.11).

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

№	Обобщенный критерий	Решение
Рис. 10.11	Х1	Х2	Y1	Y2
		A				-2
		K			-12
		[K,E]		[0,2]	[-12,-10]	[24,22]
		L
		P	1,176	3,176	0,824	1,53
		M			-7,7	18,2
		N	4,75	3,25	-6,25	15,75
		R	4,08	3,92	-4,24	12,4

Здесь квадратными скобками обозначены интервалы, соответствующе множеству решений, оптимальных по данному обобщенному критерию. Как видно из таблицы, линейная свертка с равными весовыми коэффициентами (строка 3) дает весьма однобокий результат: значения второго критерия лежат в области максимума, а первого – в области минимума. Максиминная свертка дала равные абсолютные значения критериев, но второй критерий сильнее, чем первый, отличается от своего максимально возможного значения (строка 4). Очевидно, если использовать в этой свертке относительные величины критериев, взяв за базу, например, разность (max f_i -min f _i), то можно ожидать более "справедливого" соотношения значений критериев в оптимальном решении. Действительно, максимизация минимальной относительной величины критерия с весовым коэффициентом приводит к увеличению f ₂ и уменьшению f ₁ (строка 5). Следующие два решения, представленные в 6 и 7 строках таблицы, минимизируют отклонения от идеальной точки I. Результат, соответствующий минимуму суммы квадратов отклонений. можно получить геометрически. Так при одинаковых значениях , как в нашем случае, линии равного уровня обобщенного критерия представляют собой окружности с центром в идеальной точке. Точка минимума есть точка касания линии равного уровня и границы области достижимости G, а так как у нас линии - окружности, то это будет основание перпендикуляра, опущенного из идеальной точки на ближайшую границу G (точка M). Использование минимаксного отклонения приводит к выравниванию отклонений критериев: если в точке M отклонения составляют 9,7 и 5,8, то в точке N - 8,25 для обоих критериев. Решение по максимальному относительному отклонению представлено в строке 8 таблицы и точкой R на рис 10.11.

Таким образом, все способы свертки дают решения, принадлежащие паретовскому множеству, которое лежит на ломаной КЕСВА (рис.10.11).