Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Идеальной или точкой абсолютного максимума называют точку в критериальном пространстве, в которой все критерии достигают своих максимальных значений: .
Если эта точка принадлежит достижимому множеству 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). В этой точке f 1=-5.87, f 2=16.44, f 3=-1.66.
Метрика с р = дает уже рассмотренный ранее подход: критериальная функция определяется как максимальное отклонение
, (10.21)
которое следует минимизировать по X D
Пример 10.4. Если воспользоваться сверткой (10.21) для модели из примера 10.1, то получим решение: х =1,52, х =1,37 (точка N на рис. 10.9), в котором f 1=-1,82, f 2=10,19, f 3=-3,81.
Пример 10.5. Пусть требуется максимизировать два критерия
f 1 ( X )=- 2 x 1 +x 2,,
f 2 ( X )= 4 x 1- x 2
при условиях
x 1 +x 2 8,
-x 1 +x 2 2,
0 x 1 6, 0 x 2 4.
|
Решения этой задачи, полученные при различных способах свертки, сведены в следующую таблицу.
№ | Обобщенный критерий | Решение | ||||
Рис. 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 fi -min f i), то можно ожидать более "справедливого" соотношения значений критериев в оптимальном решении. Действительно, максимизация минимальной относительной величины критерия с весовым коэффициентом приводит к увеличению f 2 и уменьшению f 1 (строка 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, которые обеспечат выполнение целевых ограничений.
Дата публикования: 2015-01-23; Прочитано: 2592 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!