Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
5.1. Задачи на графах с интервальными параметрами.
Пусть 
есть граф [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. ПМА определяется как такое подмножество 
паретовского множества , которое содержит по одному представителю из каждого класса эквивалентности.