Лекция: Метод идеальной точки

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

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

,

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

(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). В этой точке f1=-5.87, f2=16.44, f3=-1.66.

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

, (10.21)

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

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

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

f1(X)=-2x1+x2,,

f2(X)= 4x1 — x2

при условиях

x1+x28,

-x1+x22,

0 x16, 0 x24.

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

Здесь квадратными скобками обозначены интервалы, соответствующе множеству решений, оптимальных по данному обобщенному критерию. Как видно из таблицы, линейная свертка с равными весовыми коэффициентами (строка 3) дает весьма однобокий результат: значения второго критерия лежат в области максимума, а первого – в области минимума. Максиминная свертка дала равные абсолютные значения критериев, но второй критерий сильнее, чем первый, отличается от своего максимально возможного значения (строка 4). Очевидно, если использовать в этой свертке относительные величины критериев, взяв за базу, например, разность (maxfi-minfi ), то можно ожидать более «справедливого» соотношения значений критериев в оптимальном решении. Действительно, максимизация минимальной относительной величины критерия с весовым коэффициентом приводит к увеличению f2 и уменьшению f1 (строка 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 показаны утопические множества для случая, когда притязания ЛПР заданы в виде

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

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

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

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

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

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

,

,

,

.

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

,

,

,

,

,

.

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

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

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

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

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

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

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