2.2. Классификация векторных задач математического программирования (ВЗМП)
Любую из многочисленных ВЗМП, поставленных и исследованных в настоящее время, можно свести к одному из следующих типов, в соответствии с выбранными признаками-классификаторами.
1. По характеру оптимизации каждого критерия:
а) однородные ВЗМП – в которых все критерии оптимизируются одинаково (либо max, либо min);
б) неоднородные ВЗМП – где часть критериев максимизируется, для остальных ищется минимум.
2. По характеру предпочтений ЛПР:
а) равнозначные ВЗМП – в которых ЛПР не отдает предпочтений ни одному из критериев, считая их все равноценными;
б) неравнозначные ВЗМП – где ЛПР определяет приоритет каждого критерия, ранжируя их по важности.
3. По виду
целевых функций и ограничений
:
а) линейные
ВЗПМ – все и
линейны
относительно
;
б) нелинейные
ВЗМП – хотя бы одна из или
является нелинейной.
4. По типу
переменных :
а) непрерывные
ВЗМП – все могут принимать любые
неотрицательные, действительные значения;
б) дискретные
ВЗМП – все (или частично) могут быть любыми
из некоторого дискретного множества, в частности, целых чисел;
в) стохастические
ВЗМП – в которых все (или частично) принимают
некоторые значения лишь с определенной вероятностью.
Первые 2 признака являются основными, т.к. они определяют принципы построения алгоритма решения. Остальные – вспомогательные, поскольку принципиально не влияют на характер алгоритма, а лишь определяют его модификации.
Рассмотрим теперь принципы, на которых должна основываться методика решения различных типов ВЗМП. Для этого, сначала, сделаем постановку ВЗМП в соответствии с классификацией, предложенной выше.
2.3. Однородные и неоднородные ВЗМП
2.3.1. Однородные ВЗМП.
Определим однородную ВЗМП с максимизацией критериев (назовем ее ВЗМП 1) в следующей постановке. Найти:
,
если
,
где - вектор неизвестных;
- вектор
критериев;
- вектор ограничений;
- вектор, определяющий уровень
ограничений.
Пусть
также - вогнутые,
-
выпуклые функции, а область допустимых решений ВЗМП 1 не является пустым
множеством:
.
Рассмотрим также однородную ВЗМП с минимизацией критериев (назовем ее ВЗМП 2) в следующей постановке. Найти:
,
если
,
где - вектор неизвестных;
- вектор
критериев;
- вектор ограничений;
- вектор, определяющий уровень
ограничений.
Пусть
также - вогнутые,
-
выпуклые функции, а область допустимых решений ВЗЛП 2 не является пустым множеством:
.
2.3.2. Неоднородные ВЗМП.
Теперь определим неоднородную ВЗМП (назовем ее ВЗМП 3). Требуется найти:
где - вектор неизвестных;
;
- множество
индексов критериев ВЗМП 3;
-
вектор ограничений;
-
вектор ограничений;
- заданные уровни ограничений.
Пусть функции -вогнутые;
-выпуклые,
а область допустимых решений ВЗМП 3 не является пустым множеством:
2.4. ВЗМП с равнозначными критериями.
В соответствии с замечаниями, изложенными в п.2.1.4. необходимо, в первую очередь, установить принципы (аксиомы) равенства критериев ВЗМП, а для этого, очевидно, их следует нормализовать. Только в том случае, когда все разнородные критерии будут приведены к одинаковому, безразмерному виду их можно обоснованно сравнивать между собой.
2.4.1. Нормализация критериев в равнозначных ВЗМП.
Для нормализации критериев в ВЗМП общем случае используется линейное преобразование вида:
,
,
или
,
где - исходное значение критерия;
- нормализованное значение; a и c – некоторые
константы.
Такая
нормализация в ВЗМП не влияет на результат решения. Действительно, если ,
, то в точке оптимума
имеем
. Тогда и
,
т.е. результат идентичен.
В ВЗМП 1 критерии считаются нормализованными, если:
1)
, если
, где
,
,
, причем
.
2)
Более общий случай: если , где
,
тогда
,
,
, и тоже
.
Здесь имеет естественный физический
(экономический) смысл как относительный уровень достижения k-м
критерием своего максимума.
Можно вводить
и другую относительную величину – относительное отклонение от достижения k-м критерием своего максимума - . Тогда нормализация будет иметь вид:
1) ,
,
,
;
2),
,
,
.
Совершенно аналогично
нормализуются критерии в ВЗМП 2, как с помощью относительных уровней , так и с помощью относительных отклонений
.
В ВЗМП 3 используется обобщенный нормализованный критерий вида:
1) ,
,
; (2.4.1)
или
2) ,
,
. (2.4.2)
Совершенно очевидно, что между относительными
уровнями и относительными
отклонениями
существует
однозначная связь:
Этим единым
нормализованным критерием мы и будем пользоваться в дальнейшем
2.4.2 Принципы равенства критериев ВЗМП.
Идея здесь
проста: сравнивать критерии по величине их - относительных уровней, или
- относительных отклонений.
В любой ВЗМП
два критерия k и q
() будут считаться
равными в точке
, если
,
. Или: два критерия k и q равны в точке
, если
,
.
Критерии в ВЗМП считаются равнозначными,
если
возможна операция
сравнения по числовой величине относительных оценок
,
между собой, при этом на каждый
критерий
и соответственно
не накладывается условий о
приоритетах критериев.
Некоторая
числовая характеристика всех относительных оценок λ называется
нижним уровнем всех ,
если
,
,
, т.е.
. Соответственно, уровень λ
называется верхним для всех относительных уровней
, если
,
,
, т.е.
.
Аналогично
для отклонений: оценка называется
верхней среди всех относительных отклонений
, если
,
,
, т.е.
, а оценка
называется нижней для всех
относительных отклонений
,
если
,
,
, т.е.
.
Эти определения мы будем использовать при построении принципов оптимальности решения ВЗМП 1 и 3 с равнозначными критериями. Для ВЗМП 2 они “подойдут” с точностью до наоборот.
2.4.3. Принципы оптимальности решения равнозначных ВЗМП.
Идея
построения этих принципов также несложна: поскольку нижний уровень является функцией, необходимо найти
его максимум в некоторой точке
, тогда все
критерии
должны быть в
этой точке не хуже его.
ВЗМП 1 при
равнозначных критериях решена, если найдена точка и
такой нижний уровень
,
что:
(2.4.3)
Таким образом, ВЗМП 1 может быть
сведена к следующей скалярной задаче: найти такое, что
, (2.4.4)
при дополнительных ограничениях:
,
(2.4.5)
и основных ограничениях:
и
. (2.4.6)
Полученную
задачу (2.4.3) - (2.4.6), называют λ – задачей. Ее решение будем
называть решением ВЗМП, полученным на основе принципа гарантированного
результата и нормализации критериев (в дальнейшем метод ГРНК). Очень важно
отметить, что точка оптимума , полученная при
решении ВЗМП 1 методом ГРНК, оптимальна по Парето, причем такая точка только
одна. Кроме того, среди решений ВЗМП 1 методом ГРНК всегда найдется два
критерия p и q
, для которых
справедливо равенство:
.
а остальные критерии удовлетворяют неравенству:
, k
p
q,
.
Таким образом, величина и есть гарантированный (не меньше)
результат, откуда, собственно, и происходит название метода.
Точно также можно
сформулировать принципы оптимальности решения ВЗМП 1 для относительных отклонений:
необходимо взять максимальное из отклонений и найти его минимум в некоторой
точке
, тогда относительное отклонение
любого критерия в этой точке будет не больше его.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.