- •Глава 10. Многокритериальные задачи принятия решений
- •10.1. Основы многокритериальной оптимизации
- •10.1.1. Многокритериальная задача математического программирования
- •10.1.2. Где искать оптимальное решение
- •10.1.3. Определения
- •10.1.4. Условия оптимальности
- •10.2. Методы многокритериальной оптимизации
- •10.2.1. Методы первой группы
- •10.2.1.1.Функция полезности
- •10.2.1.2. Решение на основе лексикографического упорядочения критериев
- •10.2.1.3. Метод главного критерия
- •10.2.1.4. Линейная свертка
- •10.2.1.5. Максиминная свертка
- •10.2.1.6. Метод идеальной точки
- •10.2.1.7. Целевое программирование (цп)
- •10.2.2. Интерактивные методы
- •10.2.2.1. Метод уступок
- •10.2.2.2. Интерактивное компромиссное программирование
- •Построить таблицу
- •10.2.2.3. Метод stem
- •10.2.2.4. Метод взвешенных метрик Чебышева
- •10.2.2.5. Прогрессивный алгоритм принятия многокритериальных решений
- •10.2.3. Построение эффективного множества
10.2.1.7. Целевое программирование (цп)
Целевое программирование применяется в основном для решения линейных многокритериальных задач, но может быть использовано и в нелинейных задачах.
Принципиальное отличие ЦП от вышерассмотренных подходов – в изменении концепции цели. Вместо максимизации (минимизации) критериев ставится задача оптимального приближения к желаемым значениям критериев, которые называют также уровнями притязаний ЛПР. Таким образом, эти значения, обозначаемые далее как, и представляют собой цель, к которой следует стремиться. Если в методе главного критерия ограничения на критерии (10.16) могут приводить к неразрешимости задачи, то в ЦП, как будет показано дальше, желаемые значения, какими бы они ни были, не могут явиться причиной неразрешимости.
Притязания ЛПР могут быть выражены по-разному в зависимости от смысла критерия:
1) не меньше;
2) не больше ;
3) равно ;
4) принадлежать диапазону [] .
Соответственно по-разному эти требования учитываются в математической модели задачи.
Как правило, множество решений, на котором достигаются одновременно все уровни притязаний, не пересекается с допустимым множеством. В таких случаях оно называетсяутопическим. Заметим, что утопическое множество решений не обязательно должно быть непустым. В то же время утопическое множество в критериальном пространстве пустым быть не может. Приведем поясняющие примеры. На рис.10.12 показаны утопические множества для случая, когда притязания ЛПР заданы в виде
D
На рис.10.13 представлен случай, когда ЛПР ставит цель в виде: ,i=1,2,3. При этом утопическое множество решений оказывается пустым, так как нет точек, в которых одновременно все критерии достигают уровней притязаний. Однако совершенно очевидно, что в пространстве критериев утопическое множество не пусто: оно состоит из одной точки с координатами ().
При целевом программировании изменяется модель задачи:
- к исходным условиям задачи добавляются так называемые целевые ограничения, отражающие уровни притязаний;
- с целевыми ограничениями в модель вводятся новые переменные, имеющие смысл отклонений от желаемых значений исходных критериев;
- критерий в модели ЦП строится как функция новых переменных.
Пусть, например, исходная задача содержит 4 критерия и ЛПР выдвигает по ним разные варианты притязаний:
,
,
,
.
Тогда целевые ограничения будут иметь вид:
,
,
,
,
,
.
де – переменные-отклонения, характеризующие недостижение, – переменные-отклонения, означающие превышение. Все эти отклонения нежелательны. Поэтому в модели ЦП цель выражается минимизацией переменных-отклонений. Так как число этих переменных больше единицы, мы снова имеем многокритериальную задачу, в которой роль критериев играют переменные. Очевидно, что для ее решения могут быть применены способы, описанные выше:
лексикографическое упорядочение ;
линейная свертка
минимаксная свертка
- квадратичная свертка (аналог (10.20))
Если исходная модель задачи линейная, то и модели ЦП во всех случаях, кроме последнего, также линейны.
Принципиальной особенностью целевых Ограничений является то, что они не сужают исходную областью, а наоборот, расширяют, переводя ее в пространство решений большей размерности ( за счет переменныхdi). Поэтому они не могут быть причиной неразрешимости задачи. Последнее свойство следует также из того, что на переменные-отклонения не накладывается требование равенства нулю, а значит, всегда найдутся такие неотрицательные di, которые обеспечат выполнение целевых ограничений.