При разработке методов решения векторных задач приходится решать ряд специфических проблем.
Проблема нормализации возникает в связи с тем, что локальные критерии имеют, как правило, различные единицы и масштабы измерения, и это делает невозможным их непосредственное сравнение. Операция приведения критериев к единому масштабу и безразмерному виду носит название нормирования. Наиболее распространенными способами нормирования является замена абсолютных значений критериев их безразмерными относительными величинами
fr(X) = fr(X) ,
f*r
или относительными значениями отклонений от оптимальных значений критериев f*r
fr(X) = f*r - fr(X) ,
f*r
Проблема выбора принципа оптимальности связана с определением свойств оптимального решения и решением вопроса - в каком смысле оптимальное решение превосходит все остальные.
Проблема учета приоритета критериев встает, если локальные критерии имеют различную значимость. Необходимо найти математическое определение приоритета и степень его влияния на решение задачи.
Проблема вычисления оптимума возникает, если традиционные вычислительные схемы и алгоритмы непригодны для решения задач векторной оптимизации.
Решение перечисленных проблем идет в нескольких направлениях. Основные направления:
Методы, основанные на свертывании критериев в единый;
Методы, использующие ограничения на критерии;
Методы целевого программирования;
Методы, основанные на отыскании компромиссного решения;
Методы, в основе которых лежат человеко-машинные процедуры принятия решений (интерактивное программирование).
В методах, основанных на свертывании критериев, из локальных критериев формируется один. Наиболее распространенным является метода линейной комбинации частных критериев. Пусть задан вектор весовых коэффициентов критериев a = {a1,…,ar}, характеризующих важность соответствующего критерия, åar = 1, ar ³ 0 (r = 1,K). Линейная скаляризованная функция представляет собой сумму частных критериев, умноженных на весовые коэффициенты. Задача математического программирования становится однокритериальной и имеет вид
F° = åarfr(X) (max),
qi(X) £ bi (I = 1,M),
X ³ 0.
Критерии в свертке могут быть нормированы. Решение, полученное в результате оптимизации скаляризованного критерия эффективно.
К недостаткам метода можно отнести то, что малым приращениям коэффициентов соответствуют большие приращения функции, т.е. решение задачи неустойчиво, а также необходимость определения весовых коэффициентов.
Направление методов, использующих ограничения на критерии включает два подхода:
1) метод ведущего критерия;
2) методы последовательного применения критериев (метод последовательных уступок, метод ограничений).
В методе ведущего критерия все целевые функции кроме одной переводятся в разряд ограничений. Пусть g = (g2, g3,…, gк-1) – вектор, компоненты которого представляют собой нижние границы соответствующих критериев. Задача будет иметь вид
F = f1 (max)
fr ³ gr (r = 2,K),
qi (X) £ bi (I = 1,M),
X ³ 0.
Полученное этим методом решение может не быть эффективным, поэтому необходимо проверить его принадлежность области компромиссов.
Метод ведущего критерия применяется в таких задачах, как минимизация полных затрат при условии выполнения плана по производству различных видов продукции, максимизация выпуска комплектных наборов при ограничении на потребляемые ресурсы.
Алгоритм метода последовательных уступок:
1. Критерии нумеруются в порядке убывания важности.
2. Определяется значение f*1. Лицом, принимающим решение, устанавливается величина уступки D1 по этому критерию.
3. Решается задача по критерию f2 с дополнительным ограничением f1(X) ³ f*1 - D1.
Далее пункты 2 и 3 повторяются для критерия f2,…, fk.
Полученное решение не всегда принадлежит области компромиссов.
При решении задач методами целевого программирования предполагается приближение значения каждого критерия к определенной величине fr, т.е. достижение определенной цели. В самом общем виде задача целевого программирования формулируется как задача минимизации сумм отклонений целевых функций от целевых значений с нормированными весами.
d(F(X), F) = ( å wR êfR (X) - f R êp) (min),
где F = {f1,...., fR} - вектор целевых значений,
W = {w1,..., wR} - вектор весов, обычно å wR = 1, wR ³ 0
(r = 1, K), значения p находятся в пределах 1 £ p £ ¥,
d(.) – расстояние (мера отклонения) между F(X) и F.
Во многих случаях применения целевого программирования полагают p = 1. Например, в линейном целевом программировании функции fR (X) (r=1, K) и qi (X) (i = 1,M) линейны и нет целочисленных переменных.
В задачах лексикографического программирования критерии строго упорядочены по важности, так что при сравнении пары решений в первую очередь используется критерий f1 и лучшим считается то решение, для которого значение этого критерия больше, если значения первого критерия для обоих решений оказываются равными, то применяется критерий f2 и предпочтение отдается тому решению, для которого значение f2 больше, ели и второй критерий не позволяет определить лучшее решение, то привлекается f3 и т.д. Учет информации о важности критериев осуществляется путем поэтапного решения задачи минимизации отклонений критериев от целевых значений. Часто в лексикографическом программировании F = F, p = 1 .
Точка F обычно не принадлежит области допустимых значений и поэтому ее иногда называют идеальной или утопической точкой. В некоторых методах целевого программирования допускается задание утопического множества, как пример при построении архимедовой задачи.