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

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. ПМА определяется как такое подмножество  паретовского множества , которое содержит по одному представителю из каждого класса эквивалентности.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074