Интервальные задачи об остовных деревьях с топологическим критерием

Размещено на http://www.allbest.ru/

Интервальные задачи об остовных деревьях с топологическим критерием

Шапошникова Ольга Ивановна

В статье представлена задача об остовных деревьях с топологическими критериями и интервальными весами. Введены отношения предпочтения и несравнимости для нахождения полного множества альтернатив в случае интервальных весов. Базу математических расчетов составляет интервальная математика

Ключевые слова: ГРАФ, ОСТОВНОЕ ДЕРЕВО, ИНТЕРВАЛ, ПАРЕТОВСКИЙ ОПТИМУМ, ПОЛНОЕ МНОЖЕСТВО АЛЬТЕРНАТИВ, ЦЕЛЕВАЯ ФУНКЦИЯ

В процессе практического использования каких-либо математических моделей необходимо учитывать неоспоримый факт того, что все или большинство числовых параметров этих моделей определены приближенно. Как правило, достоверным является тот факт, что значение рассматриваемого параметра принадлежит определенному интервалу или отрезку числовой оси [1].

Фундаментальная проблема определения наилучшего решения интервальной задачи возникает как для многокритериальных постановок, так и в случае, когда рассматриваемая задача является оптимизационной, когда качество решений оценивается целевой функцией с единственным критерием.

Вопрос нахождения наилучшего решения интервальной задачи сводится к следующим этапам. Вначале определяется состав критериев целевой функции, после чего находится полное множество альтернатив (ПМА) [2]. На заключительном этапе с помощью процедур теории выбора и принятия решений из ПМА выбирается искомый «компромиссный» оптимум .

Рассмотрим общую постановку многокритериальной задачи об остовных деревьях [2]. Дан -вершинный -взвешенный граф , в котором каждому ребру приписаны веса . Допустимым решением является остовное дерево графа ; - множество допустимых решений (МДР). На МДР определена векторная целевая функция (ВЦФ):

, (1)

cостоящая в общем случае из критериев вида MINSUM

(2)

и критериев вида MINMAX

(3)

При ВЦФ (1)-(3) определяет на МДР паретовское множество (ПМ) [2], состоящее из паретовских оптимумов (ПО). Элемент называется ПО, если не содержит такого элемента , для которого выполняются неравенства , среди которых хотя бы одно является строгим. Искомым решением данной векторной задачи является так называемое полное множество альтернатив (ПМА) . Подмножество называется ПМА, если его мощность минимальна и при этом выполняется равенство , где .

Существует, однако, немало реальных ситуаций, в которых многообразие критериев не исчерпывается весовыми критериями вида (2) или (3). Сравнивать получаемые решения необходимо с учетом также топологических критериев. Среди них наиболее известными являются: радиус , диаметр остовного дерева; число висячих вершин, т.е. мощность , где - множество вершин степени 1; степень дерева и др.

В настоящей статье рассматривается такой класс 2-критериальных задач об остовных деревьях с топологическим критерием, ВЦФ которых содержит первый критерий вида MINSUM (2) или MINMAX (3), а второй критерий является топологическим. Таким образом получаем двукритериальную задачу с ВЦФ

(4)

у которой представляет собой минимизируемый метрический критерий

, (5)

а второй критерий является топологическим

(6)

Известно, что проблема нахождения ПМА для векторной задачи об остовных деревьях является труднорешаемой, т.е. имеет экспоненциальную вычислительную сложность в случае, если ВЦФ (1) включает в себя критериев вида MINSUM (2). Эта проблема является полиномиально разрешимой при и [2]. Проблема нахождения ПМА для каждой из 2-критериальных задач с ВЦФ (4)-(6) является NP-трудной проблемой [3].

Рассмотрим интервальную задачу об остовных деревьях с топологическим критерием.

Дан -вершинный граф , в котором каждому ребру приписан интервальный вес Допустимым решением является остовное дерево , . Через обозначим множество всех остовных деревьев, образующих множество допустимых решений (МДР). На определена интервальная целевая функция (ИЦФ)

, (7)

где под знаком суммы (7) осуществляется сложение интервалов , согласно аксиомам интервального исчисления [1,4], в частности, если , , то , где и

В качестве топологического критерия возьмем степень остовного дерева

. (8)

Зафиксируем значения критерия (8) в виде равенства

, (9)

и решаем оптимизационную 1-критериальную задачу с целевой функцией (7). В качестве конкретного значения возьмем в условии (9). Согласно определению операции сложения интервалов [4] получим значение ИЦФ где значения ее критериев

(10)

Требуется найти такой элемент , на котором значение ИЦФ (7) достигает требуемого экстремума - минимума.

В случае задания интервальных весов решение задачи, вообще говоря, не единственно, и для определения множества решений необходимо ввести, следуя терминологии [1, 4] отношения предпочтения и несравнимости.

Определение 1. Пусть . Тогда решение предпочтительнее решения (), если , при этом хотя бы одно неравенство строгое.

В случае, когда либо , решения считаем несравнимыми, .

Таким образом, сравнимы лишь интервалы, сдвинутые один относительно другого вдоль числовой оси, причем сдвинутый вправо (влево) интервал, является большим (меньшим) [5].

Введенные на МДР отношения предпочтения и несравнимости порождают Паретовское множество [2]. Паретовское множество состоит из паретовских оптимумов.

Определение 2. Решение называется паретооптимальным для задачи (7), если не существует , такого, что .

Следовательно, паретовское множество состоит из несравнимых решений.

В качестве решения поставленной задачи (7)-(9) можно рассматривать как паретовское множество , так и используемое в многокритериальной оптимизации полное множество альтернатив [2]. ПМА определяется как подмножество минимальной мощности, содержащее по одному представителю на каждое значение ИЦФ (7).

Определение 3. Интервальная задача с ИЦФ (7)-(9) называется полной (обладает свойством полноты), если для ее МДР существуют такие веса , что выполняются равенства.

Как правило, вычисление мощности МДР представляет меньшую трудность по сравнению с вычислением мощности ПМА. Если рассматриваемая задача обладает свойством полноты, то с учетом равенств снижается сложность нахождения максимальной мощности ПМА.

Согласно [6] всякая интервальная задача на графах с ИЦФ (7) является полной в случае, если ее множество типовых графов является однородным, т.е. когда мощности множеств вершин и ребер одинаковы для всех типовых графов. Под множеством типовых графов понимаем множество допустимых решений. В нашей задаче допустимым решением на графе является остовное дерево , и для каждого выполняется условие . Следовательно, МДР рассматриваемой задачи об остовных деревьях с топологическим критерием однородно.

Мощность МДР задачи об остовных деревьях с топологическим критерием растет экспоненциально с ростом в случае, когда - полный граф. При этом максимум мощности МДР определяется формулой . С учетом этих замечаний, интервальная задача об остовных деревьях с топологическим критерием является труднорешаемой.

Рассмотрим конкретную индивидуальную интервальную задачу об остовных деревьях степени 3 на 6-вершинном графе , представленном на рисунке 1.

Рисунок 1. 6-вершинный граф

Каждому ребру графа приписаны интервальные веса, таким образом, как они представлены в таблице 1.

Таблица 1. Интервальные веса ребер графа

МДР рассматриваемой индивидуальной задачи состоит из шести остовных деревьев , , степени 3, где множества ребер

Значения ИЦФ каждого решения , согласно аксиомам интервального исчисления представлены в таблице 2.

остовной топологический интервальный граф

Таблица 2. Значения интервальной целевой функции для МДР

Согласно введенным выше отношениям предпочтения и несравнимости все решения в данной индивидуальной задаче несравнимы, т.е. , и рассматриваемая задача обладает свойством полноты.

Одним из подходов к определению решения оптимизационной задачи на графах с интервальными параметрами является понятие реализации весов ребер графа [7, 8], что означает выбор вещественных значений весов ребер, находящихся внутри заданных интервалов.

В статье представлены три формулы для реализации весов ребер графа .

Первая реализация, в случае , когда веса ребер графа могут отвечать следующим требованиям: .

Применив эту реализацию в нашем примере, мы получим МДР со следующими значениями (см. табл. 3), среди которых, определяем, согласно условию экстремума (7), оптимальное решение, равное , со значением ИЦФ .

Таблица 3. Численные значения множества допустимых решений при первой реализации

Вторая реализация весов ребер графа могут быть веса при . Пусть . При этой реализации рассматриваемая задача имеет значения ИЦФ, представленные таблицей 4.

Таблица 4. Численные значения множества допустимых решений при второй реализации

Среди которых, оптимальным решением является , со значением ИЦФ .

Третий случай реализации весов ребер графа могут быть представлены весами (см. табл.5): .

Таблица 5. Численные значения множества допустимых решений при третьей реализации

Оптимальным решением при этой реализации является , со значением ИЦФ .

Таким образом, проведенные расчеты показывают, что решение будет оптимальным, если оно является оптимальным по большинству числа реализаций.

В статье рассмотрена интервальная задача об остовных деревьях с топологическим критерием. Исследована вычислительная сложность задачи, что привело к ее труднорешаемости. Введены отношения предпочтения и несравнимости для нахождения полного множества альтернатив в случае интервальных весов. Предложен ряд конкретных реализаций весов графа для нахождения оптимального решения.

Литература

Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. Изд-во МЭИ, Москва, изд-во Техника, София, 1989.

Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика.- 1994.-Т.6, вып.1.- С.3 - 33.

Шапошникова О.И. Алгоритмы с оценками для векторной задачи об остовных деревьях. Деп. рукопись в ВИНИТИ, рег. № 3618-1398 от 09.12.98.

Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. - М.: Мир, 1987.- 360с.

Левин В.И. Сравнение интервальных величин и оптимизация неопределенных систем // Информационные технологии. 1998. №7. С.22-32.

Перепелица В.А., Тебуева Ф.Б. Задачи дискретной оптимизации с интервальными параметрами // Журнал вычислительной математики и математической физики. 2010. Т.50. №5. С.836-847.

Yaman H, Karasan O.E, Pinar M.C. Minimum SpanningTree Problem with Interval Data. - Technical Report 9909, Department of Industrial Engineering, Bilkent University, Ankara, Turkey, 1999.

Козина Г.Л. Правило выбора решений оптимизационных задач на графах с интервальными параметрами. -Труды XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск: ИСЭМ СО РАН, 2005, с. 51-54.

Размещено на Allbest.ru