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, которые обеспечат выполнение целевых ограничений.