Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
Теорема 5.1 констатирует сведение интервальных задач на графах к 2-критериальным задачам. Как известно [3], задачи оптимизации на графах с ВЦФ весового вида (5.3)-(5.4) являются труднорешаемыми. Существует ряд подходов к тому, чтобы элиминировать проблему труднорешаемости, которая обусловлена свойством полноты (см. определение 5.6). Один из таких подходов состоит в том, чтобы ввести специальные дополнительные условия (ограничения) в математическую постановку рассматриваемой массовой задачи. Например, для ВЦФ вида (5.3)-(5.4) вместо второго минимизируемого (максимизируемого) критерия весового вида ввести критерий вида MINMAX (MAXMIN). В результате такой замены получаем, что максимальная мощность ПМА ,
ограничена полиномом порядка
[3].
По аналогии с 2-критериальными задачами [89] для рассматриваемых интервальных задач на графах представляют интерес такие нетривиальные условия, при которых мощность ПМА для всех
ограничена сверху константой или хотя бы полиномом от n "невысокой" степени. В этой связи рассмотрим интервальную задачу покрытия графа звездами при выполнении следующих условий:
1) множество ТГ состоит из одного элемента, который является
-вершинной звездой;
2) задача рассматривается на 2-дольных графах , у которых число вершин первой (второй) доли равно
(
), общее число вершин
кратно
и
;
3) всякое допустимое решение представляет собой такой остовный подграф графа
, у которого каждая из
компонент связности является
- вершинной звездой, а ее центр – это некоторая вершина
;
4) ребра взвешены интервалами из множества
, состоящего из
интервалов
одинаковой длины, т.е. интервалы из
удовлетворяют равенствам
,
.(5.14)
Определяемую условиями 1) – 4) задачу покрытия графа звездами с ИЦФ (5.1)-(5.2) будем обозначать символом . Доказательство полиномиальной разрешимости задачи
является конструктивным, т.е. оно базируется на описании и обосновании соответствующего полиномиального алгоритма
, который состоит из трех этапов.
Этап 1. В данном графе для каждой вершины
,
выделяем подмножество
всех вершин
, смежных с
, а также подмножество
всех ребер, инцидентных вершине
. Далее, для каждой вершины
строится множество
,
ее дубликатов. Объединение этих множеств по индексу
вместе с долей
образует пополненную первую долю
. После чего для каждого дубликата
строится звезда
с центром
и множеством ребер
. Таким образом, множество
пополняется ребрами звезд-дубликатов
,
,
, причем при дублировании веса ребер сохраняются. Результатом этого пополнения является 2-дольный граф
,
с равномощными долями:
.
Этап 2. Сначала в графе интервальные веса
ребер
заменяются на числа
. Далее в 1-взвешенном графе
с помощью подходящего алгоритма [65] (например, венгерский алгоритм) выделяем оптимальное совершенное паросочетание
, где через
обозначаем подмножество всех вершин
, смежных с дубликатами
или с самой вершиной
; мощность
,
;
. В завершение этапа 2 для каждого ребра
числовой вес
заменяется на первоначальный интервальный вес
.
Этап 3. К полученному совершенному паросочетанию применяется известная операция склеивания вершин графа: для каждого
, вершины-дубликаты
склеиваются с вершиной
; для полученной после склеивания с
вершины оставляем обозначение
. Эта вершина является центром полученной
-взвешенной звезды, состоящей из
ребер
таких, что
. Результатом работы этапа 3 является остовной подграф
исходного графа
, его компонентами связности являются
- вершинных звезд с центрами в вершинах
,
, т.е.
является допустимым решением задачи
.
Обозначим через подмножество 2-дольных графов
, удовлетворяющих условиям 1) – 4) задачи
.
Теорема 5.4. Для всякого графа с непустым МДР задачи
ее ПМА
состоит из одного допустимого решения
, которое алгоритм
находит с вычислительной сложностью
.
Доказательство. Рассмотрим индивидуальную задачу [27] с минимизируемой ИЦФ (5.1) на конкретном графе
и определим на МДР
для интервальных значений его ИЦФ (5.1)-(5.2) бинарное отношение нестрогого предпочтения
. Выражение
означает выполнение нестрогих неравенств
,
.
По определению алгоритма на его выходе получаем допустимое решение
, на котором достигает минимума значение левого конца ИЦФ (5.1)-(5.2):
(5.15)
Из равенств (5.14) следует, что в представлении (5.2) концов интервала (5.1) значение правого конца определяется выражением
,
,(5.16)
где . Из (5.15) и (5.16) получаем, что для значения ИЦФ
выполняется бинарное отношение нестрогого предпочтения по отношению к любому допустимому решению
:
,
. При этом согласно определения этапа 2 вычислительная сложность
алгоритма
имеет тот же порядок, что и вычислительная сложность задачи о совершенных паросочетаниях на двудольном графе [65]:
.
Теорема 5.4 доказана.
Определяемую условиями 1) – 4) полиномиально разрешимую задачу можно расширить, ослабив представленное выше условие 2) следующим образом. Задачу покрытия графа звездами рассматриваем на всех графах
, но при условии, что множество ТГ
состоит из такой звезды, у которой число вершин
,(5.17)
где – это независимая от
константа. В этом случае можно предложить полиномиальный алгоритм
, у которого подготовительный этап осуществляет перебор вариантов множества вершин первой доли
для индуцируемых в данном графе
2- дольных графов
,
,
. Вычислительная сложность этого перебора определяется числом сочетаний из
элементов по
, т.е. она ограничена сверху полиномом
. Далее, для каждого варианта первой доли
осуществляется решение рассмотренной выше индивидуальной задачи
на конкретном 2-дольном графе
,
,
. Заметим, что для всякого
выполняется неравенство
. Таким образом, неравенство (5.17) вместе с условиями 1), 3) и 4) определяют собой еще один подкласс полиноминально разрешимых интервальных задач покрытия графа звездами.