Тема 3. Задачи многокритериальной оптимизации

 

Эффективность функционирования экономической системы оценивается, как правило, несколькими критериями. Математической формой критерия эффективности в оптимизационных экономико-математических задачах является целевая функция.

Пусть имеется K критериев, которые можно записать в виде целевых функций , где . Поскольку , то для простоты в дальнейшем будем предполагать, что все целевые функции максимизируются. Задача многокритериальной оптимизации в этом случае запишется

; (3.1)

; (3.2)

. (3.3)

Если точки максимума , определенные при решении задач по каждому критерию не совпадают, то решение задачи (3.1) – (3.3) может быть только компромиссным. В области допустимых значений задачи находится область компромиссов. При перемещении из одной точки области компромиссов в другую, невозможно одновременное улучшение всех критериев. Решение задачи многокритериальной оптимизации должно принадлежать области компромиссов. Принадлежащие области компромиссов планы называются эффективными, или оптимальными по Парето (по имени итальянского экономиста, впервые сформулировавшего проблему многокритериальной оптимизации и принцип оптимальности). План оптимален по Парето, если он допустим и не существует другого плана для которого

и хотя бы для одного критерия выполняется строгое неравенство.

При разработке методов решения многокритериальных задач приходится решать ряд специфических проблем.

1) Проблема нормализации возникает наиболее часто. Отдельные критерии, как правило, имеют различные единицы и масштабы измерения, что делает невозможным их непосредственное сравнение. К единому и безразмерному виду критерии приводятся посредством операции нормирования. Наиболее распространенными способами нормирования является замена абсолютных значений критериев их относительными величинами

или относительными значениями отклонений от оптимальных значений критериев

,

где .

2) Проблема учета приоритета критериев встает, если критерии имеют различную значимость. В этом случае необходимо найти математическое определение приоритета и степень его влияния на решение задачи.

3) Проблема определения области компромисса возникает при решении многомерных нелинейных задач, поэтому для их решения необходимо применять методы, гарантирующие эффективное решение.

Методы решения задач многокритериальной оптимизации можно подразделить на четыре группы:

– методы, основанные на свертывании критериев;

– методы, использующие ограничения на критерии;

– методы целевого программирования;

– методы, основанные на отыскании компромиссного решения.

Вместо исходной многокритериальной задачи, в соответствии с выбранным методом, формируется замещающая задача. В состав замещающей задачи входит один критерий, а к исходной системе ограничений добавляется одно или несколько дополнительных ограничений. Решение замещающей задачи называется субоптимальным.

Рассмотрим один из методов, использующих ограничения на критерии – метод последовательных уступок. Алгоритм метода следующий:

1) Критерии нумеруются в порядке убывания важности.

2) Решается задача

;

;

.

Определяется значение .

3) Устанавливается уступка по этому критерию.

4) Решается задача

;

;

;

.

Если в задаче более двух критериев, то пункты 3) и 4) повторяются для .

К группе методов отыскания компромиссного решения относится метод равных наименьших относительных отклонений. Сущность его заключается в следующем. Определяются оптимальные значения критериев , затем критерии нормируются, т.е. записываются относительные отклонения функции от оптимального значения

.

Замещающая задача имеет вид

;

;

;

.

Несложно показать, что в качестве целевой функции этой замещающей задачи можно записать любую целевую функцию исходной задачи. Замещающая задача тогда запишется

;

;

;

.

Полученное этим методом решение может не быть эффективным, поэтому необходимо проверить его принадлежность области компромиссов.

Рассмотрим метод целевого программирования. В задаче ставится цель – приближение значения каждого критерия к определенной величине . В самом общем виде целевая функция имеет вид

,

где – весовые коэффициенты, отражающие важность критериев. Точка обычно не принадлежит области допустимых значений, поэтому ее называют идеальной или утопической точкой. В некоторых задачах целевого программирования задается утопическое множество. Рассмотрим этот метод.

Целевые значения функций могут быть заданы тремя способами:

1) , отклонение функции от целевого значения в большую или меньшую сторону обозначим и . В этом случае дополнительное ограничение запишется

.

2) , в этом случае возможно только отклонение в меньшую сторону . Дополнительное ограничение имеет вид

.

3) . Дополнительные ограничения

;

.

Замещающая задача, построенная в соответствии с методом целевого программирования, имеет вид

;

, ;

, ;

, ;

, ;

;

; ,

где – весовые коэффициенты.

 

Пример. Предприятие может производить продукцию двух видов и , используя для этого два вида ограниченных ресурсов и . Расход ресурсов на производство продукции, запасы ресурсов и прибыль известны:

 

Ресурс	Расход ресурса на 1 т продукции	Запас ресурса, т
Прибыль, ден. ед.

 

Определить план производства продукции, максимизирующий прибыль и суммарное количество продукции.

Необходимо решить задачу:

1) методом равных наименьших относительных отклонений;

2) методом последовательных уступок, если более важным является критерий прибыли и уступка по нему составляет 175 ден. ед.;

3) методом целевого программирования, исходя из того, что целевое значение показателя прибыли составляет ден. ед., а объема выпуска – т.

 

Решение. Построим экономико-математическую модель задачи. Обозначим через и количество продукции вида и соответственно. Тогда модель задачи будет

1) Решим задачу методом равных наименьших относительных отклонений.

Определим максимальную величину прибыли при ограниченных ресурсах. Для этого решим графически задачу

Построим область допустимых значений, которая задается системой ограничений. Геометрической интерпретацией линейного ограничения является полуплоскость, ограниченная прямой. Запишем уравнения граничных прямых и для их построения найдем по две точки, лежащих на этих прямых:

1) , (0; 40), (60; 10);

2) , (30; 30), (40; 0).

Пересечением полуплоскостей является многоугольник ОАВС (см. рис. 3.1) – это область допустимых значений.

Графической интерпретацией целевой функции является множество линий уровня. Вектор-градиент , координатами которого являются частные производные целевой функции по и , показывает направление наискорейшего возрастания целевой функции. Линии уровня перпендикулярны вектору-градиенту. На чертеже обычно изображают одну из них .

Для определения точки, в которой целевая функция принимает наибольшее значение, перемещаем линию уровня в направлении вектора-градиента до тех пор, пока она займет крайнее положение в области допустимых значений. Для данной задачи это точка А с координатами (0; 40). В этой точке значение целевой функции

.

Итак, максимальная прибыль составляет 1400 ден. ед. и достигается при выпуске 40 т продукции вида .

Определим максимальный объем выпуска при ограниченных ресурсах. Для этого решим графически задачу

Координаты вектора-градиента . На чертеже изображен вектор . Максимальное значение целевой функции достигается в точке В (см. рис. 3.1).

(1)

Рис. 3.1

 

Координаты точки В определяем из решения системы, составленной из уравнений прямых, пересекающихся в этой точке.

Решая систему, находим

Следовательно, точка В имеет координаты (32; 24). В этой точке значение целевой функции

.

Итак, максимальный выпуск продукции составляет 56 т и достигается при выпуске 32 т продукции вида и 24 т продукции вида .

Отрезок АВ является областью компромиссов.

Запишем относительные отклонения для обеих функций.

, .

Для построения дополнительного ограничения замещающей задачи приравняем отклонения , т.е.

.

После упрощения этого выражения получим

.

Замещающая задача в соответствии с методом равных наименьших относительных отклонений будет иметь вид

Областью допустимых значений замещающей задачи является отрезок OD (см. рис. 3.2). Максимальное значение целевой функции достигается в точке D. Координаты точки D определяем из решения системы, составленной из уравнений прямых, пересекающихся в этой точке.

Рис. 3.2

 

Решая систему, находим

Следовательно, точка D имеет координаты (20; 30) – это субоптимальное решение. Точка D принадлежит области компромиссов, следовательно, найденное решение эффективно. В этой точке целевые функции принимают значения

Итак, по методу равных наименьших относительных отклонений план производства составит 20 т продукции вида и 30 т продукции вида . Прибыль будет равна 1250 ден. ед., а объем выпуска продукции составит 50 т.

Относительные отклонения составляют

; .

Это означает, что обе целевые функции отклоняются от своих оптимальных значений на 10,7%.

2) Решим задачу методом последовательных уступок. Решив задачу по первому критерию, мы получили, что максимальная величина прибыли .

Уступка по критерию прибыли составляет ден. ед. Дополнительное ограничение замещающей задачи формируется в соответствии с неравенством

и для данной задачи имеет вид

тогда замещающая задача примет вид

Графическая иллюстрация решения изображена на рис. 3.3. Область допустимых решений – треугольник ALK.

Максимальное значение целевой функции достигается в точке K.

 

Рис. 3.3

 

Координаты точки K определяем из решения системы, составленной из уравнений прямых, пересекающихся в этой точке.

Решая систему, находим

Следовательно, точка K имеет координаты (23,3333; 28,3333). В этой точке значения целевых функций

Итак, по методу последовательных уступок план производства составит 23,3333 т продукции вида и 28,3333 т продукции вида . Прибыль будет равна 1225 ден. ед., а объем выпуска продукции составит 51,6666 т.

3) Решим задачу методом целевого программирования. Поскольку целевые значения превышают максимально возможные при заданных ограничениях (было получено раньше и ), необходимо минимизировать сумму отклонений и от целевых функций. Замещающая задача будет иметь вид

Решим задачу графически. Для этого преобразуем данную задачу к эквивалентной задаче, содержащей две переменные. Из первого ограничения-равенства системы ограничений выразим переменную , а из второго – :

и подставим в целевую функцию

.

Т.к. и , то и их выражения через переменные и также будут неотрицательными, т.е.

или

Таким образом, получили задачу

Графическая иллюстрация решения изображена на рис. 3.4. Область допустимых решений – многоугольник ОАВС. Координаты вектора-градиента . На чертеже изображен вектор .

 

Рис. 3.4

 

Максимальное значение целевой функции достигается в точке А с координатами (0; 40).

Тогда

и субоптимальное решение будет

Итак, при выпуске 40 т продукции вида отклонение от целевого значения прибыли составит 100 ден. ед., а от целевого значения объема производства продукции – 30 т.