Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

5.2. Сведение интервальной задачи дискретной оптимизации к дискретной многокритериальной задаче.

Вернемся к интервальной ЦФ (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) на интервально-взвешенном графе .