Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«МАТИ» – Российский государственный технологический университет

имени К.Э.Циолковского

На правах рукописи

Селин Павел Сергеевич

Метод характеристических функций в задачах

оптимизации на некоторых классах сетей

01.01.09 – Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва – 2014

Работа выполнена на кафедре «Прикладная математика и информационные технологии» Института информационных систем и технологий Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «МАТИ» – Российский государственный технологический университет имени К.Э.Циолковского.

Научный руководитель: доктор физико-математических наук, профессор ЦУРКОВ Владимир Иванович

Официальные оппоненты: КОВАЛЕНКО Алексей Гаврилович, доктор физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Самарский государственный университет, профессор кафедры математики и бизнес-информатики;

ДУМБАДЗЕ Ламара Георгиевна, кандидат физико-математических наук, Специализированное опытно-конструкторское бюро систем и средств измерений «Вектор», руководитель группы.

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский педагогический государственный университет

Защита состоится 30 октября 2014 года в 16:00 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительный центр им. А.А. Дородницына Российской академии наук, расположенном по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Вычислительный центр им. А.А. Дородницына Российской академии наук и на сайте http://www.ccas.ru.

Автореферат разослан 2014 г.

Ученый секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор В.В. Рязанов

Общая характеристика работы

Актуальность темы Одной из важных задач оптимизации является задача о нахождении максимального потока, впервые сформулированная Харрисом Т. и Россом Ф., и решенная Фордом Л.

и Фалкерсоном Д., создавшими первый алгоритм, известный как алгоритм ФордаФалкерсона, многократно улучшавшийся в дальнейшем. В работе исследуются классы сетей с фиксированными степенями узлов. Производится произвольное разбиение множества узлов на два подмножества. В теории «Потоки в сетях» это разбиение называется разрезом. Указанное разбиение задает три подсети, две из которых есть сети, порожденные подмножествами узлов разбиения, а третья – это двудольная сеть. Далее рассматриваются суммы весов (пропускных способностей) дуг всех трех сетей. Учитывая, что исходные сети данного класса имеют заданные степени узлов, для этих сумм строятся достижимые ограничения снизу и сверху. Оценки построены для случаев, когда веса дуг ограничены сверху константой и степенями узлов, а также когда веса дуг ограничены только степенями узлов.

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

величина максимального потока сети из истока в сток равна минимальной пропускной способности разреза. Для класса рассматриваемых сетей вычислены две оценки, такие что: минимальная величина максимального потока равна нижней оценке, а максимальная величина максимального потока не превышает верхней оценки. Для многополюсной задачи, в которой каждый узел одного подмножества узлов – это исток, а каждый узел другого есть сток, указанные две оценки задают следующее: нижняя оценка – это минимальная величина максимального потока, а верхняя – максимальная величина максимального потока.

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

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

Цели и задачи исследования В работе рассматриваются классы сетей (взвешенных графов) без петель и с петлями с фиксированными степенями узлов (вершин). Основной результат работы заключен в следующей конструкции:

а) задается неотрицательный параметр, и рассматривается класс указанных сетей с общим множеством узлов, веса дуг (ребер) которых не превосходят этого параметра;

б) множество узлов сетей из класса произвольно разбивается на два подмножества;

в) вводятся три переменные величины, две из которых – это суммы весов дуг, инцидентных только узлам одного из подмножеств разбиения, а третья переменная – это сумма весов дуг, инцидентных узлам двух подмножеств;

г) строятся формулы, выраженные через степени узлов и параметр, задающие оценки снизу и сверху для указанных переменных;

д) показано, что указанные оценки являются точными (достижимыми).

Научная новизна В работе построен математический аппарат исследования классов сетей (взвешенных графов, графов, мультиграфов) с фиксированными степенями узлов. Также получены формулы для вычисления минимаксных значений, определяющих необходимые и достаточные условия непустоты рассматриваемых классов сетей, и алгоритм построения наследственно минимаксной сети.

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

В работе применяются характеристические функции и уравнения: неотрицательность характеристической функции – это критерий существования сети с заданными степенями узлов и заданным ограничением для весов (пропускных способностей) дуг;

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

Практическая ценность Результаты имеют приложение в теории «Потоки в сетях». Полагая, что веса дуг – это пропускные способности, разбиение множества узлов на два подмножества задает разрез сети и третья переменная – это пропускная способность разреза. Если в одном из подмножеств узлов выбрать узлы-источники, а в другом – узлы-стоки, то ограничения для третьей переменной есть ограничения для величины максимального потока (величина максимального потока равна минимальной величине пропускной способности разреза).

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

Результаты также имеют применение в сетях связи, сенсорных сетях.

Апробация Результаты, представленные в работе докладывались на семинарах в «МАТИ» и на следующих научных конференциях:

XXXI, XXXII и XXXIV «Гагаринские чтения».

2012 Tohoku-Section Joint Convention of Institutes of Electrical and Information Engineers, Japan.

Публикации Основные результаты диссертации опубликованы в 7 печатных работах, две из которых находятся в изданиях из перечня ВАК.

Структура работы Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 57 наименований. Общий объём работы – 100 страниц.

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

= {u1,..., un }, а все n, m-вершинные двудольные сети – с множествами узлов (долями) U (n) = {u1,..., un } и V (m) = {v1,..., vm }. Будем отождествлять nвершинные сети и n, m-вершинные двудольные сети с неотрицательными матрицами 1 j m, где xij = xji – вес дуги (петли при i = j) – с вершинами ui и uj в первом случае и xij – вес дуги с вершинами ui и vj – во втором. Под суммой сетей (матриц) X = (x ) и X = (x ) с равными количествами узлов называется сеть (матрица) X + X = (xij + xij ).

Для множеств неотрицательных векторов и пар из них применяются следующие обозначения:

Многие утверждения и конструкции (не ограничивая общности) рассматриваются с векторами из R+ : через A обозначим вектор, построенный из вектора A упорядочиванием его координат по невозрастанию.

Обозначим множества сетей с петлями и без петель, степени узлов которых равны координатам вектора A из R+ :

класс сетей с петлями, (A) = {X(A) = (xij ) : X(A) L (A); xii = 0 i} – класс сетей без петель;

веса дуг (и петель) которых не превосходят заданного неотрицательного параметра c.

Множества сетей-матриц (без петель и с петлями) (A), L (A) и (A; c), L (A; c) называются соответственно сетевыми и усеченными сетевыми многогранниками.

Множества двудольных сетей, степени узлов которых равны координатам векторов из пары (A, B) R+,=, обозначим В транспортных задачах множества (A, B) и (A, B; c) называются соответственно классическим и усеченным транспортными многогранниками.

Сети-матрицы из многогранников (A), L (A), (A, B) и (A; c), L (A; c), (A, B; c) называются реализациями и c-реализациями (вектора A и пары векторов (A, B)), а в случае, когда указанные многогранники не являются пустыми множествами, соответствующие им векторы и пара векторов называются реализуемыми и cреализуемыми.

В первой главе введены понятия характеристических функций и уравнений, а также условия c-реализуемости пары векторов в двудольную сеть; получены формулы вычисления минимакса и алгоритм нахождения наследственно минимаксной матрицы смежности усеченного транспортного многогранника. Рассмотрено приведение пары векторов к c-реализуемости в двудольную сеть.

Сформулируем условия, при которых (A, B; c) =. Для этого введем понятие характеристической функции.

Пусть (A, B) R+,= и c 0. Характеристической функцией (ХФ) называется ХФ (1.1) можно упростить: если обозначить В следующем утверждении содержится критерий c-реализуемости пары векторов в двудольную сеть.

Теорема 1. Если (A, B) R+,=, то Для пары векторов (A, B) R+,= найдем наименьшее значение c = c(A, B), при котором (A, B; c) =.

Пусть (A, B) R+,=. Величина c(A, B) = min{c : (A, B; c) = } называется минимаксом для (A, B) или (A, B).

Это определение связано с очевидным тождеством Для минимакса имеет место Теорема 2. Пусть (A, B) R+,= и (A, B; c) =. Величина c является Построим формулу вычисления минимакса c(A, B), где (A, B) R+,=. Обозначим T (A, B) = {(i, j) : ai > ai+1 или i = n, bj > bj+1 или j = m}. Для (t, r) T (A, B) построим систему линейных соотношений Если система (1.2) при некоторых (t, r) не имеет решения, то положим ctr = 0. Имеет место Лемма 1. Для (A, B) R+,= имеет место c(A, B) = max(t,r)T (A,B) ctr.

Отметим, что пара индексов (k, p), при которой c(A, B) = ckp, определяется неоднозначно.

Сети (матрицы) из (A, B; c(A, B)) называются минимаксными.

Следующая теорема характеризует минимаксные матрицы (см. ХФ (1.1 )).

то для X(A, B) = (xij ) (A, B; c(A, B)) справедливо Вычисление минимакса c(A, B) можно упростить: при его вычислении достаточно использовать первое соотношение из (1.2).

Теорема 4. Пусть (A, B) R+,=. Для минимакса c(A, B) имеет место (A, B). Будем говорить, что матрица X задает пару векторов (A, B).

Для (A, B) R+,= двудольная сеть–матрица (минимаксная) X(A, B) называется наследственно минимаксной, если каждая ее подматрица есть минимаксная матрица пары векторов, которую задает эта подматрица.

Алгоритм построения наследственно минимаксной матрицы заключен в следующей лемме.

Лемма 2. Пусть (A, B) R+,= и X(A, B) = (xij ) (A, B; c(A, B)), причем c(A, B) = ckq. Тогда для пар векторов (A, B ) и (A, B ), где (A, B ; c(A, B)) =.

Из теоремы 3 следует:

а) если k = n, то пара векторов (A, B ) не существует.

б) если q = m, то пара векторов (A, B ) не существует.

в) при k = n и q = m пары векторов (A, B ) и (A, B ) не существуют.

ти–матрицы.

Пусть (A, B) – произвольная пара векторов из R+,=. Наследственно минимаксная матрица X(A, B) = (xij ) строится следующим образом.

4) и строятся подматрицы искомой матрицы X(A, B), первая из которых состоит из минимаксных элементов, а вторая – нулевая (теорема 3).

применяется теорема 4 для вычисления минимаксов c(A, B ), c(A, B ) и опять применяется теорема 3 для вычислений части элементов подматриц X1 (A, B ) X(A, B). И т.д.

Очевидно, что процесс, содержащийся в алгоритме конечен.

(матрица) и U U (n), V V (m). Введем обозначение для сумм весов дуг:

(U, V ) = Пусть (A, B), (D, E) R+,=. Пара векторов (D, E) называется вписанной в (A, B) ((D, E) (A, B)), если D A и E B.

множество c-реализуемых пар векторов, вписанных в (A, B). Для произвольной пары векторов (A, B) будет найдена c-реализуемая пара векторов из M(A, B; c) с наибольшей суммой координат каждого вектора.

Применяя ХФ (1.1) для (A, B) R+,=, введем обозначение Величина (1.3) – это минимальное значение, на которое необходимо уменьшить суммы координат векторов A и B, чтобы получить c-реализуемую пару. Основные результаты главы сформулированы в теоремах 5 и 6.

Теорема 5. Пусть (A, B) R+,=. Тогда Правило (1.4) и числа A (A, B; c), B (A, B; c) задают пару векторов A (A,B;c) что при (A, B; c) = справедливо (AA (A,B;c), B B (A,B;c) ) = (A, B).

Теорема 6. Пусть (A, B) R+,=.

Тогда (AA (A,B;c), B B (A,B;c) ; c) =.

Во второй главе для неотрицательного вектора приводятся понятия характеристических функций и условия c-реализуемости в сеть без петель; получены формулы вычисления минимакса и алгоритм нахождения наследственно минимаксной матрицы смежности усеченного сетевого многогранника. Также рассмотрено приведение вектора к c-реализуемости в сеть без петель.

Для A R+, c 0 и k Z, характеристической функцией (ХФ) называется Неотрицательность ХФ (2.1) является необходимым и достаточным условием cреализуемости.

В дальнейшем будем применять ХФ (2.1) и ее упрощенный вид: если обозначить = lk (A; c).

Для вектора A R+ вычислим наименьшее значение c = c(A), при котором (A; c) =.

Пусть A R+ и (A) =. Значение c(A) = min{c : (A; c) = } называется минимаксом для A или (A; c).

Легко видеть справедливость тождества:

Для минимакса имеет место Теорема 8. Пусть A R+ и (A) =. Величина c является минимаксом Перейдем к построению формулы вычисления минимакса c(A), где A R+.

построим систему соотношений:

Положим ctr = 0, если (2.2) не имеет решений.

При r = 1 (тогда и t = 1) система (2.2) не имеет решения, и в этом случае, как указано выше, c11 = 0, но c(A) = 0 A – нулевой вектор. Поэтому будем предполагать, что в (2.2) вектор A отличен от нулевого и r > 1.

Теорема 9. Пусть A R+, где a1 > 0, и (A) =. Тогда Сети без петель (матрицы) из (A; c(A)) называются минимаксными.

Следующая теорема характеризует минимаксные матрицы.

X(A) = (xij ) (A; c(A)) имеет место < j; ai > ai+1, i = n; aj > aj+1, j = n}.

При нахождении минимакса можно удалить последние два неравенства из (2.2) и при вычислении c(A) рассматривать только пары индексов из T (A) = T (n) T (A).

Теорема 11. Пусть A R+, где a1 > 0, и (A) =. Тогда xii = 0, задает вектор A, для которого ai = говорить, что матрица (сеть без петель) X задает вектор A.

Cеть без петель (минимаксная) называется наследственно минимаксной, если каждая ее подсеть без петель и каждая двудольная подсеть, порожденные своими узлами, есть минимаксные.

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

Лемма 3. Пусть A R+ и X(A) = (xij ) (A; c(A)), причем c(A) = = ckq. Тогда для пары векторов (A, A ) и вектора A, где a = ai c(A)(q 1), 1 i k, ai = ai, q < i n, ai = ai c(A)(q k), k < i q, имеет место Алгоритм 2. Построение наследственно минимаксной сети без петель.

Пусть A – произвольный вектор из R+. Наследственно минимаксная сеть строится следующим образом.

= max ctr = ckq. Числа ckq, k, q задают веса дуг искомой сети (элементы симt,r)T (A) метричной матрицы) X(A), равные c(A) и равные 0 (теорема 10).

Шаг 2. Применяя лемму 3, вычисляются пара векторов (A, A ) и вектор A.

Для пары векторов (A, A ) применяется алгоритм 1 для построения наследственно минимаксной двудольной сети. Этим будут найдены веса дуг xij искомой сети X(A), Далее для вектора A применяются шаги 1 и 2 данного алгоритма. И т.д.

Пусть X = (xij ), 1 i, j n – произвольная сеть без петель (матрица), у которой xii = 0, 1 i n. Введем обозначения для сумм весов дуг: для U, V где lk (A; c) определено в (2.1 ).

Для вектора A R+ вычислим наименьшее значение c = cL (A), при котором L (A; c) =.

Пусть A R+. Значение cL (A) = min{c : L (A; c) = } называется минимаксом для A или L (A; cL ).

Легко видеть справедливость тождества Для минимакса имеет место Теорема 18. Пусть A R+. Величина c является минимаксом (c = cL (A)) Перейдем к построению формулы вычисления минимакса cL (A), где A R+.

Для (t, r) T (A) (см. (2.2)) построим систему соотношений Положим ctr = 0, если (3.2) не имеет решений.

Сети с петлями (матрицы) из L (A; cL (A)) называются минимаксными.

Следующая теорема характеризует минимаксные матрицы.

X(A) = (xij ) L (A; cL (A)) имеет место Обозначим TL (n) = {(i, i) : 1 i n}. Покажем, что при нахождении минимакса можно удалить все неравенства из (3.2) и при вычислении cL (A) рассматривать xii = 0, задает вектор A, для которого ai = говорить, что матрица (сеть с петлями) X задает вектор A.

Cеть c петлями (минимаксная) называется наследственно минимаксной, если каждая подсеть и каждая двудольная подсеть, порожденные своими узлами, есть минимаксные.

Из теоремы 21 следует лемма, в которой заключен алгоритм построения наследственно минимаксной сети с петлями.

Лемма 5. Пусть A R+ и X(A) = (xij ) L (A; cL (A)), причем cL (A) = = ckq. Тогда для пары векторов (A, A ) и вектора A, где a = ai cL (A)(q 1), 1 i k, ai = ai, q < i n, ai = ai cL (A)(q k), k < i q, имеет место Алгоритм 3. Построение наследственно минимаксной сети с петлями.

Пусть A – произвольный вектор из R+. Наследственно минимаксная сеть строится следующим образом.

= max ctr = ckq. Числа ckq, k, q задают веса дуг искомой сети (элементы симt,r)T (A) метричной матрицы) X(A), равные cL (A) и равные 0 (теорема 20).

Шаг 2. Применяя лемму 5, вычисляются пара векторов (A, A ) и вектор A.

Для пары векторов (A, A ) применяется алгоритм 1 для построения наследственно минимаксной двудольной сети. Так будут найдены веса дуг xij искомой сети X(A), Далее для вектора A применяются шаги 1 и 2 данного алгоритма. И т.д.

Пусть X = (xij ), 1 i, j n – произвольная сеть с петлями. подмножества U U (n) введем обозначения для сумм весов петель: L (U ) = xii, L (U ) = = c|U | L (U ).

c-реализуемых векторов, вписанных в A. Для произвольного вектора A будет найден c-реализуемый вектор из ML (A; c) с наибольшей суммой координат.

Применяя ХФ (3.1) для A R+ введем обозначение Основные результаты главы III сформулированы в теоремах 22 и 23.

где вектор A получен из вектора A упорядочиванием его координат по невозрастанию.

Пусть A R+ и c 0. Очевидно, что существует L (A; c), для которого По правилу (1.4) величина = L (A; c) задает вектор Теорема 23. Пусть A R+. Тогда L (AL (A;c) ; c) =.

разбиение множества U (n). Разбиение множества U (n) задает два подвектора A1 = = (ai ), ui U1, A2 = (ai ), ui U2, и каждую сеть X(A) = (xij ) из L (A; c) можно представить в виде X(A) = X1 (A1 )+X2 (A2 )+X3 (A1, A2 ), где X1 (A1 ) = = (xij ), ui, uj U1, X2 (A2 ) = (xij ), ui, uj U2, X3 (A1, A2 ) = (xij ), ui Приведем оценки снизу и сверху для величин 2(U1 )+L (U1 ), 2(U2 )+L (U2 ), (U1, U2 ). Из теорем 5, 22 и леммы 4 следует утверждение.

Теорема 24. Пусть A R+, L (A; c) = и X(A) – произвольная сеть из (A; c). При любом разбиении множества узлов U (n) = U1 U2, U1 U2 = для величин 2(U1 ) + L (U1 ), 2(U2 ) + L (U2 ), (U1, U2 ) подсетей X1 (A1 ), X2 (A2 ), X3 (A1, A2 ) Очевидно, что для вектора A R+, где L (A; c) =, оценки для величин (U1 ), (U2 ) и (U1, U2 ) зависят от разбиения множества узлов U (n) = U1 U2 и от параметра c.

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

Аналогичная проблема решена и в случае, когда любой узел есть исток или сток. Указанный подход позволяет строить сети с максимальной плотностью весов дуг на выделенном подмножестве узлов.

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

Следующим шагом может быть распространение результатов исследования на целочисленные сети, а также многоиндексные, нелинейные и бесконечномерные обобщения. Однако, эти задачи остаются за рамками данной работы и только прогнозируются.

1. Миронов А.А., Селин П.С. Метод разбиения сетей с фиксированными степенями узлов и потоки в сетях // Изв. РАН Теория и системы управления. 2005. N 6. С.

2. Селин П.С. Об ограничениях в сетях с фиксированными параметрами на узлах связи // Тез. докл. Междунар. молодежной научн. конф. «XXXI Гагаринские чтения»

2005. Т. 5. С. 47-48.

3. Селин П.С. Ограничения при обмене информацией в сетях с петлями с фиксированными степенями узлов // Тез. докл. Междунар. молодежной научн. конф.

«XXXII Гагаринские чтения» 2006. Т. 5. С. 68-70.

4. Миронов А.А., Селин П.С., Матвеев И. А. Наследственно минимаксная сеть с фиксированным вектором степеней узлов // Тр. ИСА РАН. Динамика неоднородных систем. 2006. 10(1). С. 187 - 192.

5. Селин П.С. О достижимости оценок в потоковых задачах на классах сетей с петлями и без петель с фиксированными степенями узлов. // Научн. тр. Междунар.

молодежной научн. конф. «XXXIV Гагаринские чтения» 2008. Т. 5. С. 100-102.

6. Selin P., Obara H. The algorithm for constructing a hereditarily minimax network with predefined vector of node degrees // 2012 Tohoku-Section Joint Convention Record of Institutes of Electrical and Information Engineers, Japan.

7. Селин П.С., Цурков В.И. Метод характеристических функций для классов сетей с фиксированными степенями узлов // Изв. РАН Теория и системы управления.

2014. N 5. С. 59-68.