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

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

Если эта точка принадлежит достижимому множеству 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).

10.2.1.7. Целевое программирование (ЦП)

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

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

Притязания ЛПР могут быть выражены по-разному в зависимости от смысла критерия:

1) не меньше ;

2) не больше ;

3) равно ;

4) принадлежать диапазону [ ].

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

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

	D

На рис.10.13 представлен случай, когда ЛПР ставит цель в виде: , i= 1,2,3. При этом утопическое множество решений оказывается пустым, так как нет точек, в которых одновременно все критерии достигают уровней притязаний. Однако совершенно очевидно, что в пространстве критериев утопическое множество не пусто: оно состоит из одной точки с координатами ().

При целевом программировании изменяется модель задачи:

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

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

- критерий в модели ЦП строится как функция новых переменных.

Пусть, например, исходная задача содержит 4 критерия и ЛПР выдвигает по ним разные варианты притязаний:

,

,

,

.

Тогда целевые ограничения будут иметь вид:

,

,

,

,

,

.

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

- лексикографическое упорядочение ;

- линейная свертка

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

- квадратичная свертка (аналог (10.20))

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

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