Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
Вернемся к интервальной ЦФ (5.1)-(5.2), которая определена для интервально-взвешенного графа и данного множества ТГ
. Граф
рассматриваем также в виде 2- взвешенного графа: если ребро
было взвешено интервалом
, то в процессе "2- взвешения" этому ребру приписываем 2 веса
и
, которые представляют собой концы интервала
. Далее, на представленном МДР
определим векторную целевую функцию (ВЦФ)
,(5.3)
которая состоит из критериев
,
,(5.4)
где .
Определение 5.4. Пусть ВЦФ (5.3) состоит из максимизируемых критериев (5.4) т.е. для
. Решение
называем паретовским оптимумом, если МДР
не содержит такой элемент
, для которого выполняются неравенства
и хотя бы одно из этих неравенств является строгим;
– паретовское множество.
Определение 5.5. В условиях определения 5.4 подмножество называется ПМА, если выполняются следующие два условия: удовлетворяется равенство
, где определяем
для всякого
, и мощность
подмножества
является минимальной.
В статье [7] представлено строгое обоснование сводимости интервальной задачи об остовных деревьях к 2- критериальной задаче об остовных деревьях. Представленное в [7] доказательство этого сведения можно применить к общей постановке интервальной задачи оптимизации на графах, которая сформулирована выше. Таким образом, является справедливой следующая
Теорема 5.1. Для всякого множества ТГ задача оптимизации на интервально-взвешенном графе с интервальной ЦФ (5.1)-(5.2) сводится к векторной задаче с ВЦФ (5.3)-(5.4) на этом же 2-взвешенном графе. Паретовское множество и ПМА 2-критериальной задачи с ВЦФ (5.3)-(5.4) на 2-взвешенном графе
однозначно определяет собой паретовское множество и ПМА этой же задачи с ИЦФ (5.1)-(5.2) на интервально-взвешенном графе
.