ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2010, том 50, № 5, с. 836-847
УДК 519.626
ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ С ИНТЕРВАЛЬНЫМИ ПАРАМЕТРАМИ^
© 2010 г. В. А. Перепелица, Ф. Б. Тебуева
(357100 Черкесск, Ставропольская, 36, Карачаево-Черкесская гос. технол. акад.)
e-mail: Perepel2@yandex.ru; fariza-t@yandex.ru
Поступила в редакцию 27.02.2007 г. Переработанный вариант 04.12.2009 г.
Рассмотрены задачи оптимизации на графах с интервальными параметрами, обоснованы соответствующие экспоненциальные и полиномиальные оценки их вычислительной сложности. Для выделенного подкласса полиномиально разрешимых задач предложены 2 алгоритма: нахождение оптимального решения и нахождение субоптимального решения. Установлены достаточные условия статистической эффективности алгоритма нахождения субоптимального решения. Библ. 23.
Ключевые слова: задачи дискретной оптимизации, задачи с интервальными параметрами, полиномиальная разрешимость задач, приближенные алгоритмы.
ВВЕДЕНИЕ
Приближенные методы решения различных задач естествознания в настоящее время получают интенсивное развитие, вызывая при этом интерес к оценкам величины погрешности как результатов вычислений, так и исходных данных. Интервальные параметры являются одним из способов адекватного отражения исследуемого объекта в условиях неточных данных. Огромное количество учебных и научных публикаций отечественных и зарубежных авторов посвящено интервальному анализу и его приложениям, среди которых можно выделить работы [1]—[6].
Настоящая статья является продолжением начатых в [7] исследований экстремальных задач на графах с интервальными весами. Это — задачи, которые в дальнейшем будем называть задачами дискретной оптимизации с интервальными параметрами.
Известно, что сравнение интервалов является одним из важных вопросов интервального анализа. В [8] предложено строгое отношение частичного порядка для пар непересекающихся интервалов, при этом пересекающиеся интервалы являются несравнимыми. В литературе по интервальному анализу при сравнении интервалов используются и другие отношения предпочтения: в сильном, слабом, центральном, показательном смыслах (см. [9], [10]). Выбор конкретного определения сравнения зависит от содержательной сути задачи с интервальными параметрами. В настоящей работе предлагается сводить задачи с интервальными параметрами к двухкритери-альным задачам (в качестве первого критерия брать начала весовых интервалов, второго критерия — концы весовых интервалов) и осуществлять переход от интервальной оптимизации к многокритериальной. Следует обратить внимание, что метод сравнения интервалов по его началам и концам для оптимизационных интервальных задач используется в [10]. В заключительной части этой статьи говорится о том, что интервальная постановка прикладных задач не всегда имеет решение. Вопрос сводится к выделению (нахождению) максимального (минимального) интервала из данного множества, что имеет место далеко не всегда, и предлагается решать уже другую задачу, оставляя в стороне вопрос о том, насколько эта задача далека от первоначальной. Такой вопрос в настоящей работе не возникает.
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 10-07-00329а).
1. ЗАДАЧИ ОПТИМИЗАЦИИ НА ГРАФАХ С ИНТЕРВАЛЬНЫМИ ПАРАМЕТРАМИ
Пусть G = (V, E) есть граф (см. [11], [12]), где V = {v1, ..., vn} является множеством его вершин и E = {e1, ..., eL} — множеством его ребер. Задано также множество типовых графов Q = {T1, ., Tq}. Допустимое решение x определяется подграфом x = (V, Ex), Ex с E, в котором каждая компонента связности изоморфна некоторому типовому графу из Q. При этом множество X = X(G, Q) = {x} является множеством допустимых решений на графе G для множества типовых графов Q.
Рассмотрим конкретные примеры множеств типовых графов Q. Пусть множество типовых графов Q состоит из одного элемента Q = {T1}. Тогда X = X(G, Q) является множеством допустимых решений задачи о совершенных паросочетаниях, если T1 есть ребро, и X = X(G, Q) — множеством допустимых решений задачи коммивояжера, если T1 есть простой n-вершинный цикл. Если элементами множества Q являются Агвершинные звезды, t = 1, q, то X = X(G, Q) есть множество допустимых решений задачи покрытия графа звездами.
Пусть каждое ребро e е E графа G = (V, E) взвешено интервальным весом w(e) = [w1(e), w2(e)]. Тогда целевая функция F(x, G) задачи оптимизации на графах с интервальными весами имеет вид
F(x, G) = £ w(е) = [Fi (x, G), F2(x, G)] — min, (1)
е e Ex
Fv(x, G) = £ wv(е), v = 1, 2. (2)
е e Ex
Заметим, что целевая функция (1) линейна по слагаемым w(e), следовательно, она принимает интервальные значения, получаемые с помощью известного определения операции суммирования интервалов (см. [1]). В [13]—[15] приведены различные способы определения оптимальности в случае интервальных значений показателя качества. В настоящей статье мы рассматриваем па-ретовское определение оптимальности. Будем измерять качество каждого допустимого решения x е X, рассматривая интервал (1) возможных значений этой целевой функции; для того чтобы выбрать оптимальное решение, нужно сравнивать эти интервалы. При этом F(x, G) называем интервальной целевой функцией.
Определение 1. Пусть интервальная целевая функция (1), (2) является минимизируемой и для пары решений имеем x, y е X = X(G, Q). Будем говорить, что допустимое решение x е Xлучше, чем допустимое решение y е X (и обозначать x < y), если в (2) выполняются неравенства F1(x, G) < < F1(y, G), F2(x, G) < F2(y, G) и хотя бы одно из этих неравенств является строгим; x и y являются эквивалентными, если F(x, G) = F(y, G); иначе x и y являются несравнимыми.
Определение 2. В условиях определения 1 решение x е Xназывается паретовским оптимумом, если не существует такого x е X, что x < x.
Совокупность всех паретовских оптимумов составляет паретовское множество, обозначаемое
через X, X с X. Два решения принадлежат к одному классу эквивалентности, если они эквивалентны. Это определение распространяется и на классические (т.е. неинтервальные и однокри-териальные) задачи оптимизации. Такая задача решена, если получено одно решение, которое принадлежит множеству всех оптимумов, образующих класс эквивалентности. С учетом этого условия считаем, что искомым решением интервальной задачи дискретной оптимизации является полное множество альтернатив.
Определение 3. Полное множество альтернатив определяется как такое подмножество X0 па-
ретовского множества X, которое содержит по одному представителю из каждого класса эквивалентности.
2. СВЕДЕНИЕ ИНТЕРВАЛЬНОЙ ЗАДАЧИ ДИСКРЕТНОИ ОПТИМИЗАЦИИ К ДИСКРЕТНОИ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧЕ
Вернемся к интервальной целевой функции (1), (2), которая определена для интервально взвешенного графа G = (V, E) и заданного множества типовых графов Q = {Г1, ..., Т^. Граф G рассматриваем в виде 2-взвешенного графа: если ребро е было взвешено интервалом w(e) = [^1(е), ^2(е)], то
в процессе "2-взвешения" этому ребру приписываем два веса w1(e) и w2(e), которые представляют собой концы интервала w(e). Далее, на представленном в разд. 1 X = X(G, Q) = {x} определим векторную целевую функцию
F(x, G) = (F(x, G), F2(x, G)), (3)
состоящую из критериев
Fv(x, G) = £ wv(e) — max, v = 1, 2. (4)
e e Ex
Определение 4. Пусть векторная целевая функция (3) состоит из критериев (4) для v = 1, 2. Решение х е Xназываем паретовским оптимумом (см. [16]), если множество допустимых решений X не содержит такого элемента x*, для которого выполняются неравенства Fv(x*, G) > Fv(x, G), v = 1, 2, и хотя бы одно из этих неравенств является строгим; X = {х} — паретовское множество.
Для следующего определения введем обозначение F(X*) = {F(x, G) : x е X*} для всякого X* с X.
Определение 5. В условиях определения 4 подмножество X0 с X называется полным множеством альтернатив, если при минимальной мощности |X°| выполняется равенство F(X°) = F(X).
Полное множество альтернатив является обобщением понятия классического оптимума: найти полное множество альтернатив в случае N = 1 — это значит найти какой-либо оптимум рассматриваемой однокритериальной задачи (при N = 1 мощность |X°| = 1 для всякой задачи с непустым X).
В [7] представлено строгое обоснование сводимости интервальной задачи об остовных деревьях к 2-критериальной задаче об остовных деревьях. Представленное в [7] доказательство этого сведения можно применить к общей постановке интервальной задачи оптимизации на графах, которая сформулирована выше. Таким образом, является справедливой следующая
Теорема 1. Для всякого множества типовых графов Q = {Т1, ..., Tq} задача оптимизации на ин-тервально взвешенном графе с интервальной целевой функцией (1), (2) сводится к векторной задаче с векторной целевой функцией (3), (4) на этом же 2-взвешенном графе: паретовское множество и полное множество альтернатив 2-критериальной задачи с векторной целевой функцией (3), (4) на 2-взвешенном графе G однозначно определяет собой паретовское множество и полное множество альтернатив этой же задачи с интервальной целевой функцией (1), (2) на интервально взвешенном графе G.
3. ОЦЕНКИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ
Рассмотрим представленную в разд. 1 формулировку интервальной задачи на графах. Используя понятие "задача", как предикатную переменную, обозначаем ее символом Z(Q) в смысле понятия "массовая задача", которое предложено в [17]. Если эта интервальная задача рассматривается как "индивидуальная задача" (см. [14]) на конкретном интервально взвешенном графе G = = (V, Е), то обозначим ее символом Z(G, О); ее множество допустимых решений, паретовское
множество и полное множество альтернатив обозначим, соответственно, через X = Х^, О), X =
= X(^ © и Xю = Х°(в, ®.
Пусть 8(п) = — множество всех (невзвешенных) п-вершинных графов.
Определение 6. Интервальная задача Z(Q) с интервальной целевой функцией (1), (2) называется полной (обладает свойством полноты), если для каждого ее множества допустимых решений X = Х(^ О), G = (V, Е е Дп), п = 1, 2, ..., существуют такие веса w(e), е е Е, что выполняются равенства
X3 (с, 0) = Х( с, 0) = Х( с,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.