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