Алгоритм подбора весов для решения задачи векторной оптимизации — это алгоритм выбора рационального решения, который сопряжен с преодолением неопределенностей, имеющихся в связи с наличием многих критериев.
Введение
Когда выполняется решение задач линейного программирования, то обычно рассматриваются лишь простые случаи, где является ясным критерий, по которому осуществляется оценка эффективности и необходимо определить экстремум лишь одного показателя. Но в реальной действительности подобные задачи попадаются довольно редко, в основном при исследовании незначительных по масштабам и скромных по значению мероприятий.
Когда же речь идет о большой организации, то эффективность ее работы нельзя охарактеризовать при помощи единственного показателя эффективности. К примеру, необходимо организовать деятельность предприятия. Можно выбирать решение под разными углами зрения и критериями. Как правило, желательно иметь максимальный валовый объем продукции, получать наибольший чистый доход при минимальной себестоимости, максимальную производительность труда и так далее. В данном случае оптимальное решение, найденное по единственному показателю, может стать не самым лучшим по величине показателей других критериев.
Критерием оптимальности (или показателем эффективности, или целевой функцией) является функция, экстремальное значение которой необходимо определить в условиях экономических возможностей задачи. Экономические возможности могут быть формализованы в форме системы ограничений.
Алгоритм подбора весов для решения задачи векторной оптимизации
Векторной оптимизацией, то есть, многокритериальной оптимизацией является определение оптимальных значений на основании нескольких критериев. Особенностью задач векторной оптимизации является наличие в области допустимых значений компромиссной области, в которой нельзя одновременно улучшить все критерии. Планы, которые принадлежат области компромиссов, именуются эффективными или оптимальными по Парето.
Планом является решение экономико-математической модели, то есть, совокупность значений неизвестных, которые удовлетворяют системе ограничений модели. Количество возможных компромиссных схем является практически не ограниченным. Известны разные методы решения задач векторной оптимизации, в их числе:
- методы, которые основаны на свертывании ряда критериев в единый критерий;
- методы, которые используют ограничения на критерии;
- методы, основанные на целевом программировании;
- методы, которые базируются на определении компромиссного решения;
- методы, основанные на человеко-машинных процедурах принятия решений, то есть, это интерактивное программирование.
В методах, которые основаны на свертывании критериев в единый, из локальных критериев выполняется формирование одного. Самым используемым может считаться метод линейной комбинации частных критериев. В этом методе вместо ряда критериев определяется один новый в форме их взвешенной суммы. Таким образом, задача математического программирования превращается в однокритериальную и обладает следующим видом:
Рисунок 1.
Причем должен задаваться вектор весовых коэффициентов всех критериев $а = {a_i, ..., a_k}$, которые характеризуют важность всех критериев:
Рисунок 2.
Весовыми коэффициентами являются положительные числа, суммарное значение которых равняется единице:
Рисунок 3.
при этом:
Рисунок 4.
где K является количеством критериев.
Линейная скаляризованная функция $F^O$ (функция свертки) является суммой частных критериев, которые умножены на весовые коэффициенты. Критерии свертки можно нормализовать, то есть, привести к единому масштабу и безразмерному формату (для непосредственного сравнения критериев). К недостаткам данного метода следует отнести:
- Малым приращениям весовых коэффициентов могут соответствовать большие приращения функции свертки, то есть, решение задачи является неустойчивым.
- Наличие необходимости определять весовые коэффициенты.
К числу преимуществ данного метода следует отнести тот факт, что решение по такому методу является оптимальным, то есть, оно должно принадлежать области компромиссов.
Осуществить определение весовых коэффициентов может быть реализовано, к примеру, таким образом. Следует принять за единицу уровень важности основного критерия, а для всех остальных следует установить их относительную важность в сравнении с главным критерием. Все найденные положительные числа обязаны быть меньше единицы. А далее каждое из них, включая и важность основного критерия (она равняется единице) следует поделить на их сумму и получить весовые коэффициенты.
В методах, которые используют ограничения на критерии, можно применять следующие подходы:
- Подход, использующий метод ведущего критерия.
- Подход, применяющий методы последовательного использования критериев, а именно, метод последовательных уступок, метод ограничений.
Метод ведущего критерия предполагает перевод всех целевых функции, помимо одной в разряд ограничений. Предположим, что выражение:
Рисунок 5.
Является вектором, элементы которого выступают в качестве нижних границ соответствующих критериев. Тогда данная задача может быть представлена в следующем виде:
Рисунок 6.
Сформированное данным методом решение может не являться эффективным, то есть, его необходимо проверить его принадлежность области компромиссов. Метод ведущего критерия может применяться в таких задачах, как сведение к минимуму общих затрат при условии исполнения плана по производству разных видов продукции, а также сведение к максимуму выпуска комплектных наборов при ограничениях на потребляемые ресурсы.
В методе последовательных уступок вместо многокритериальной задачи должен решаться набор однокритериальных задач (по числу критериев), при этом для любого последующего критерия должно вводиться дополнительное ограничение на величину предыдущего критерия.
