Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Максиминная свертка
|
|
Как и в предыдущем подходе, ЛПР должен задать веса Ci всем критериям, но обобщенный критерий записывается в виде
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 1+2 x 2 
3 x 0
4 x 1+3 x 2 3 x 0
2 x 1-5 x 2 3 x 0
и новый критерий х0 max. Оптимальное решение этой задачи достигается в точке х 
=х 
=х 
= 0, в которой f 1, f 2 и f 3 тоже равны нулю.
Сравним с результатами примера 10.1. При решении по критерию (10.17) получили 
fi=-15, а по критерию (10.18) fi=0. Однако это решение доставляет наихудшее значение критерию f 2 и ни одному из критериев не обеспечивает максимального значения.
10.2.1.7. Целевое программирование (ЦП)
Целевое программирование применяется в основном для решения линейных многокритериальных задач, но может быть использовано и в нелинейных задачах.
Принципиальное отличие ЦП от вышерассмотренных подходов – в изменении концепции цели. Вместо максимизации (минимизации) критериев ставится задача оптимального приближения к желаемым значениям критериев, которые называют также уровнями притязаний ЛПР. Таким образом, эти значения, обозначаемые далее как 
, и представляют собой цель, к которой следует стремиться. Если в методе главного критерия ограничения на критерии (10.16) могут приводить к неразрешимости задачи, то в ЦП, как будет показано дальше, желаемые значения , какими бы они ни были, не могут явиться причиной неразрешимости.
Притязания ЛПР могут быть выражены по-разному в зависимости от смысла критерия:
1) не меньше ;
2) не больше ;
3) равно ;
4) принадлежать диапазону [ 
].
Соответственно по-разному эти требования учитываются в математической модели задачи.
Как правило, множество решений, на котором достигаются одновременно все уровни притязаний, не пересекается с допустимым множеством. В таких случаях оно называется утопическим. Заметим, что утопическое множество решений не обязательно должно быть непустым. В то же время утопическое множество в критериальном пространстве пустым быть не может. Приведем поясняющие примеры. На рис.10.12 показаны утопические множества для случая, когда притязания ЛПР заданы в виде
 |
 | |||||
 | |||||
| |||||
На рис.10.13 представлен случай, когда ЛПР ставит цель в виде: 
, i= 1, 2, 3. При этом утопическое множество решений оказывается пустым, так как нет точек, в которых одновременно все критерии достигают уровней притязаний. Однако совершенно очевидно, что в пространстве критериев утопическое множество не пусто: оно состоит из одной точки с координатами (
).
При целевом программировании изменяется модель задачи:
- к исходным условиям задачи добавляются так называемые целевые ограничения, отражающие уровни притязаний;
- с целевыми ограничениями в модель вводятся новые переменные, имеющие смысл отклонений от желаемых значений исходных критериев;
- критерий в модели ЦП строится как функция новых переменных.
Пусть, например, исходная задача содержит 4 критерия и ЛПР выдвигает по ним разные варианты притязаний:
,
,
,
.
Тогда целевые ограничения будут иметь вид:
,
,
,
,
,
.
де 
– переменные-отклонения, характеризующие недостижение , 
– переменные-отклонения, означающие превышение . Все эти отклонения нежелательны. Поэтому в модели ЦП цель выражается минимизацией переменных-отклонений. Так как число этих переменных больше единицы, мы снова имеем многокритериальную задачу, в которой роль критериев играют переменные 
. Очевидно, что для ее решения могут быть применены способы, описанные выше:
- лексикографическое упорядочение ;
- линейная свертка
- минимаксная свертка
- квадратичная свертка (аналог (10.20))
Если исходная модель задачи линейная, то и модели ЦП во всех случаях, кроме последнего, также линейны.
Принципиальной особенностью целевых Ограничений является то, что они не сужают исходную областью, а наоборот, расширяют, переводя ее в пространство решений большей размерности (за счет переменных di). Поэтому они не могут быть причиной неразрешимости задачи. Последнее свойство следует также из того, что на переменные-отклонения не накладывается требование равенства нулю, а значит, всегда найдутся такие неотрицательные di, которые обеспечат выполнение целевых ограничений.
|
|