Глава5 Задачи многокритериальной

оптимизации

5.1. Общая постановка задачи многокритериальной оптимизации. Парето-эффективное множество.

Задача вида

fi (x) → max (min) ,

x D

где i>1, D Rn – допустимое множество, а fi (x) – гладкие функции

на D , называется задачей многокритериальной оптимизации.

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

Определение 5.1. Пусть X и Y – два допустимых решения. Говорят, что X доминирует Y, если для всех i=1,2,…n выполняется

неравенство fi (X ) ≥ fi (Y ) и найдется такое k, что fk (X ) > fk (Y ) . Определение 5.2. Решение Z называется недоминируемым

(эффективным), если нет решения X, которое бы доминировало Z. Определение 5.3. Множество эффективных (недоминируемых) решений называется множеством Парето. Геометрическое изображение множества Парето называется Парето-

эффективной границей (Парето-оптимальной границей).

В задаче многокритериальной оптимизации наилучшее решение следует искать в множестве Парето.

Алгоритм построения Парето-эффективной границы:

1.Строим допустимое множество D, заданное системой ограничений, как пересечение полуплоскостей, соответствующих каждому неравенству, входящему в эту систему.

2.Для каждой функции fi = ci1 x1 + ci2 x2 + cio строим линию уров-

ня как прямую, перпендикулярную соответствующему вектору нормали ni = (ci1, сi2 ) . Каждая из этих линий уровня разбивает плоскость

67

XOY на две полуплоскости. Пусть Пi –полуплоскости, содержащие

вектор градиента целевой функции fi , а их пересечение П = n Пi ;

i=1

3. Перемещая данную область П по границе допустимого множества D, находим те точки границы, которые являются единственными точками пересечения областей П и D. Данные точки являются оптимальными по Парето, а множество всех таких точек – Па- рето-эффективной границей.

Пример 5.1. Найти Парето-эффективную границу задачи

f1 = 4x1 + x2 → maxf2 = x1 + 2x2 → maxx1 + x2 ≤ 7

x1 ≤ 5x2 ≤ 4x1 ≥ 0x2 ≥ 0

Решение. Область допустимых решений D задается системой неравенств

x1 + x2 ≤ 7x1 ≤ 5x2 ≤ 4x1 ≥ 0

x ≥ 02

Построим данную область.

l1 : x1 + x2 = 7 l2 : x1 = 5

l3 : x2 = 4

В качестве допустимого множества получаем область ОАВСD с угло-

выми точками О(0;0), А(0;4), В(3;4), С(5;2), D(5;0).

68

Для функций f1 и f2 построим линии уровня (f1=const, f2=const) как прямые, перпендикулярные соответствующим векторам нормали

n1 =(4;1) и n2 =(1;2). Каждая из этих линий уровня разбивает плос-

кость XOY на 2 полуплоскости. Рассмотрим те из них Пi, которые содержат соответствующий вектор нормали (вектор градиента целевой функции). Пусть П=П1∩П2. Перемещая область П по границе множества D легко определить, что Парето-эффективной границей будет отрезок [BC], т.е. множество точек (1-t)(3;4)+t(5;2)=(3+2t; 4-2t),

t [0;1].

Ответ. [BC] – Парето-эффективная граница, т.е. множество точек (3+2t; 4-2t), t [0;1]

Замечание 5.1. Задача минимизации одной или нескольких целевых функций в задаче многокритериальной оптимизации легко сводится к задаче максимизации умножением на (-1).

Пример 5.2. Для выпуска 2-х видов продукции используется

цены на ресурсы Q=(1; 1; 4), цены реализации продукции P=(17; 12),

даче максимизации прибыли и выручки.

69

70

Ответ. [BC] - Парето-эффективная граница, (10+2t; 5-2t), t [0;1].

Задачи для самостоятельного решения

Найти Парето-оптимальную границу следующей задачи:

75. Рекламное агентство, в штате которого 12 человек, получило заказ на рекламу нового продукта на радио и ТВ. Основные данные об аудитории, стоимости рекламы и количестве занятых ее изготовлением агентов занесены в таблицу (на 1мин.):

Рекламное агентство решает задачу о максимизации возможной аудитории и минимизации издержек на изготовление рекламы при условии, что контракт запрещает использовать более 4 минут рекламы на радио. Найти Парето-оптимальную границу.

76. Для выпуска двух видов продукции используются два вида

цены на ресурсы, P=(5,12) – цена реализации продукции, B = 10 - за-

15

пасы ресурсов. Найти Парето-оптимальную границу в задаче максимизации прибыли и выручки.

71