Метод характеристических функций в задачах оптимизации на некоторых классах сетей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

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

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2014 9 <>КТ 2014

005553120

005553120

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

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

Официальные оппоненты: КОВАЛЕНКО Алексей Гаврилович,

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

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

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

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

Ученый секретарь

диссертационного совета Д 002.017.02,

д.ф.-м.н., профессор

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

Актуальность темы

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

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

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

зависящие от заданного набора степеней узлов

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

Цели и задачи исследования

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

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

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

в| вводятся три переменные величины, две из которых - это суммы весов дуг. инцидентных только узлам одного из подмножеств разбиения, а третья переменная - это сумма весов дуг, инцидентных узлам двух подмножеств:

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

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

Научная новизна

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

Методы исследования

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

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

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

Практическая ценность

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

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

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

Апробация

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

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

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

Публикации

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

Структура работы

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

Содержание работы

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

Все //-вершинные сети будем рассматривать с множеством узлов U(n) = = {к 1.....//„ }, а все п. //¡-вершинные двудольные сети - с множествами узлов (долями) (/(н) = {;/].....//.,,}nV(?//) = {?.'].....г,„}. Будем отождествлять //вершинные сети и п. //¡-вершинные двудольные сети с неотрицательными матрицами смежности соответственно А' = (Tij). 1 $ i.j ii /), и X = (xjj). 1 i ' ^ 1 ; <C vi. где .r,j — x ¡, - вес дуги (петли при г = j) -с вершинами и, и itj в первом случае и .r(J - вес дуги с вершинами ?/, и vj - во втором. Под суммой сетей (матриц) X' = (.г' •) и X" = (.г'^) с равными количествами узлов называется сеть (матрица) X' + Х" = + .г'/).

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

К+ = {А = («,.....а„) : а, ^ ОV/}.

R+ = {А € R+ : а, 2 а,+1. 1 ^ i sg п - 1 ( п ^ 2)};

II 11)

®+.= = i(A.B):AeR;,BeR;'.^ «,- = ^ М-

>=i j=i

К+.= = В) е К"-;: :Аей;.Век"'}.

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

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

л

Г,.(А) = {Л-(Л) = (х,}) : ./•„ = xv > ()V».j:dogи, = = «, V/}-

j=i

класс сетей с петлями.

Г(Л) = {Л'(Л) = (х,,) : Х(А) 6 TL(A):.rh = О V/} - класс сетей без нетель:

rL(A:c) = {.Y(A) = (Xfj) : Х{А) е rL(A):xu ^ rV/'.j}-

= = (x,j) : Х(А) е Г{А):хи < с \/i.j} - классы сетей,

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

Множества сетей-матриц (без петель и с петлями) Г(Л). и Г(А:с).

Г/, (А\ г.) называются соответственно сетевыми и усеченными сетевыми многогранниками.

Множества двудольных сетей, степени узлов которых равны координатам векторов из пары (А. В) £ ПС':, обозначим

Г(А. J5) = {Х(А.В) = (-Г i j) : Xij > О W. j:

7II II

dog», = s<j = о» V/; dog Vj = = hj Vj}.

j=i '=i

Г (А. В: с) = {X(A.B) = (j-(J) : .Y(A.B) 6 Г(Л. B):.r,, ^ r}.

В транспортных задачах множества Г( А. В) и Г( А. В: с) называются соответственно классическим и усеченным транспортными многогранниками

Сети-матрицы из многогранников Г(>1). Г (А. В) и Г(Л:г). Г/,(у1:г).

Г(А. В:с) называются реализациями и (-реализациями (вектора А н нары векторов (А. В)), а в случае, когда указанные многогранники не являются пустыми множествами. соответствующие им векторы и пара векторов называются реализуемыми и г-реализуемыми

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

Сформулируем условия, при которых Г(Д. В: с) ф 0 Для тгого введем понятие характеристической функции.

Пусть (Л. В) € и с fi 0. Характеристической функцией (ХФ) называется

т к

6ь(А.В:с) = ХЛ ~~ (bJ ~ <*) 1 ^ k ^ "■

ХФ (1.1) можно упростить: если обозначить

A-

ók(A.B:c) = ckh{B-.r)+ Y, bJ ~ Л"1' 1 ^ k ^ "■ (Lr)

j>hiB:r) < = 1

В следующем утверждении содержится критерии ореализуемости пары векторов в двудольную сеть

Теорема 1. 1-сли (А. В) Е К+. = . то Г (А. В: с) ф 0 6к(А. В, с) ^ О VA-, 1 ^ А: ^

Для пары векторов (А. В) е К";'" найдем наименьшее значение г = с.{А. В), при котором Г( А. В: г) ф 0.

Пусть (Л. В) € Величина r.(A.B) = mm{í: : Г(А,В;с) ф 0}

называется миннмаксом для (А. В) или Г(А. В).

Ото определение связано с очевидным тождеством

minír : V[A.B:c.) ф 0} = mili max{.r¿) : Х(А.В) = {Xjj)}.

' а'(а.в)ег(а.в) i.j

Для мшшмакса имеет место

Теорема 2. Пусть (А. В) е и Г(А. В\с) ф 0. Величина с является

мшшмаксом (г = с(А.В))<=> ЗА- 6 Z. К К п. что 6к (А. В: с) = 0 ubi ^ ск.

Построим формулу вычисления мннимакса с(А. В), где (А. В) € R+.=. Обозначим Т(А. В) = {(i.j) : а, > ш+1 или / = v.bj > bJ+, или.) = m}. Для V(/. г) 6 Т(А.В) построим систему линейных соотношений

<=1 J>r

< ''" =-^ " (1.2)

Г,г! ^ К. , ctrt. > br+1. r<m.

Если система (1.2) при некоторых (/. г) не имеет решения, то положим о,- = 0. Имеет место

Лемма 1. Для {А. В) £ К+.= имеет место г( А. В) = шах(,.г)бТ(д.в) с,,.. Отметим, что пара индексов (к. р), при которой с(А. В) = г*.,,, определяется неоднозначно.

Сети (матрицы) из Г(А. В:с{А. В)) называются минимаксными Следующая теорема характеризует минимаксные матрицы (см. ХФ (1.1')) Теорема 3. Если (А. В) £ 1+ .'1 <М А. В: с(А. В)) = 0 и Ь\ ^ с(А.В). то для Х(А.В) = (г,,) е Г( А. В: с(А. В)) справедливо

_ Г с(А.В). 1 ^ / ^ к. 1 ^ .} ^ 1к.(В:с(А.В)). ~ \0. 1 > к. ] > 1к{В:с(А.В)).

Вычисление минимакса с(А.В) можно упростить: при его вычислении достаточно использовать первое соотношение из (1.2).

Теорема 4 . Пусть (А. В) £ Для минимакса г(А. В) имеет место

I

с(А.В)= тах --——.

(|.г)еГ(Л.В) 1г

Каждая неотрицательная матрица X = (■r¡j). 1 ^ г ^ п. 1 < ./ < т. задает

т м

пару векторов (А. В) £ , где я, = ^ = X " Л_ = В^ 6

3=1 1=1

е Г(А. В). Будем говорить, что матрица X задает пару векторов (А. В).

Для (А. В) £ К™'™ двудольная сеть-матрица (минимаксная) Л'( А. В) называется наследственно минимаксной, если каждая ее подматрица есть минимаксная матрица пары векторов, которую задает эта подматрица.

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

Лемма 2. Пусть (А. Б) £ М+'" и Х(А.В) = (т,,) £ Г( А. В:, (А. В)). причем с(А. В) = Сь,. Тогда для пар векторов (А'. В') и (А". В"), где а\ = «, - с( А. В) ■ 1 «С / ^ к. Ь) = Ья+]. 1 ^ - </•

а'! = ок+,- 1 ' < » ~ А'- Ь'] = Ьз - с(А. В) ■ к. 1 < з < '/■ имеет место (А'. В') £ (А". В") £ К^'" и Г(А'. В': с(А. В)) ф 0.

Г(А". В"-. с(А. В)) / 0.

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

а) если к = н. то пара векторов (А". В") не существует

б) если </ = т. то пара векторов (А'. В') не существует.

в) при к = п и q = in пары векторов (А'. В') и (А". В") не существуют.

Алгоритм 1. Построение наследственно минимаксной двудольной сети-матрицы

Пусть (А. В)- произвольная пара векторов из = . Наследственно минимаксная матрица Л'(А. В) = (.)',,) строится следующим образом

Шаг 1. Вычисляется минимакс е( А. В) = max с,г = с:к., (теорема

((.г)бТ(Д.В)

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

Шаг 2. Вычисляются пары векторов (А'. В'), (А". В") (см. лемму 2). применяется теорема 4 для вычисления минимаксов с(А'.В'). с(А".В") и опять применяется теорема 3 для вычислений части элементов подматриц Xi(A'.B') £ € V(A'.B':r(A'.B')) и Х2(А". В") е Г(А". В":с{А". В")) искомой матрицы Х(А.В). И т.д.

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

Пусть Л' = (-I'ij)- 1 ^ ' $ 1 ^ j ^ hi - произвольная двудольная сеть (матрица) и U С h'{ii). V С V'(/»)• Введем обозначение для сумм весов дут:

S(U. V) = Y, ес:ш 'г'.' < г V/. J. то <$({/. V) = c\U\\V\ - S(U. V).

" t < r

'V г

Пусть A. D € R" . Вектор D называется вписанным в A (D ^ А), если </,

sS a, Vi 1 ^ / ^ п.

Пусть (A.B).(D. Е) 6 JR+ Пара векторов (D. Е) называется вписанной в (А. В) ((D. Е) s: (А.В)), если!? ^АпЕ^В.

Обозначим ОТ( А. В: г) = {(D.E) : (D.E) ^ (А. В). Г(£). Е: с) ф 0} множество г-реализуемых пар векторов, вписанных в (А. В). Для произвольной пары векторов (А. В) будет найдена с-реализуемая пара векторов из Ч>!( А. В-.с) с наибольшей суммой координат каждого вектора

Применяя ХФ (1.1) для (А. В) е К+.=. введем обозначение

, ттдк(А.В:с)\.Г(А.В:с) = 0. V . 0. Г( А. В: с) Ф 0.

Величина (1.3) - это минимальное значение, на которое необходимо уменьшить суммы координат векторов А и В. чтобы получить (.--реализуемую пару Основные результаты главы сформулированы в теоремах 5 и (>. Теорема 5. Пусть (А. В) в Тогда

max

(£>.Е)еЯЛ(А.В:г.) ( = 1

II II

Для A G R+ и q > 0 положим A" = («1.....<) - такой вектор, что

a.a, ^ a. ^ ^

ft;. 4, < (v.

Пусть (А. В) e R+ "А и с > 0. Очевидно, что существуют такие числа аа(А.В\с). ав(А.В<с). при которых ^а, - 6{А.В:с) =

i = i

„ in

= min(oA(А. В: с), а,). ]Г Ь} - Л'(А. В: с) = тт(<хв(А. В. r).bj). ,=i j=i J=i

Правило (1.4) и числа аА{А.В\с). с,в(А.В:с) задают пару векторов (Апл(А.В;с) _ jgr>B(A.B;r)) _

= .....аЫл(А.В-.г)))^ь^в{А.В-.г)).....¿аМА.В-.с))^ ^^

что при Г (А. В; с) ^справедливо = (А. В).

Теорема б . Пусть (А. В) 6 Тогда Г(А"л(д"В;'').Вав(Л-В:"):'') Ф 0-

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

Для 0 и к € Z, характеристической функцией (ХФ) называется

6к(А;с) = ск(к-1)- ]Г (a,-ck)-Y,<4+ Ц и,.с ^ ck ^ пк + г. (2.1)

.?/. + ! |<А' iSlt+l

Неотрицательность ХФ (2.1) является необходимым и достаточным условием <■реализуемости.

Теорема 7 . Если А е К+. то

Г(А: г)фе><^> дк(А: с) ^ О \/к. с < ск пк + с.

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

I' (Л-,.) — / 1ПЯХ{? : ^ ск}.ак+1 ^ ск. ''> ~ \k.nk+i < ск.

ók(A;c)=ck(l'k(A-.c)- 1)-£>,+ £ а-

¡>Гк(А-.с)

Пусть А е М+ и с ^ 0. Для (1.1') и (2.1') если ak+l Ss ск, то 1к(А:с) = = Vk{A-.c).

Для вектора A £ М^. вычислим наименьшее значение с = с(А), при котором Г(А:г) ф 0.

Пусть А е R+ и Г(4) ф 0. Значение с(А) = min{r : Г(А:с) ф 0} называется минимаксом для А или Г( А: с).

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

miiií t: : Г (А: с) ф 0} = min nwxí/,, : Х(А) = (.г,;)}.

а'( а)ег(а) i.j

Для минимакса имеет место

Теорема 8. Пусть А & R+ и Г(А) ф 0. Величина г: является минимаксом U- = с(А)) <=> Г( А: с) Ф 0 и Зр € X. с ^ ср ^ и,, + с. что й"„(А; с) = 0.

Перейдем к построению формулы вычисления минимакса <:( А), где А £ R+ . Обозначим Г'(А) = {(i.j) : i.j € Z, 1 sí i ^ j sí и}. Для V (¿. г) £ Т'(А) построим систему соотношений.

£«.-£ п> - í(r-l) •

(2.2)

(■tft ^ а, + с,,. ctrt > иг+]. г < п. c,rt sí о,., г > I.

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

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

Теорема 9. Пусть А € К" , где aj > 0. и Г( А) ф 0. Тогда

с(А) = max ctr-

(t.rW'lA)

Сети без петель (матрицы) из Г( А: с(А)) называются минимаксными. Следующая теорема характеризует минимаксные матрицы. Теорема 10. Если А е К'^ и д",,(А: с(А)) = 0. где с ^ ср ^ ар + с. то для Х(А) = (Xfj) е Г(А: с(А)) имеет место

с(А). (i.j) 6 {(i.j) ■ i ф j. 1 < i-J < ?'} u U {(г-j) : 1 < i < p.p < j < l'„} U {(i.j) : P < ' < ^J^ Pi-X'J ~ 0. (i.j) e {(i.j) :p<i£ n. /J, < j < n) U

t U {(i.j) : /;, < i ^ n.p /;,} и {(i.j) :i = j.p<i *,,}•

Обозначим T(n) = {(¿.г) : 2 < i < n}»T"(A) = {(i.j) e Г (A) : i <

< j-.ai > «,+ь i = n:aj > aj+1- j = n}.

При нахождении минимакса можно удалить последние два неравенства из (2.2) и при вычислении с(А) рассматривать только пары индексов из Т(А) = Г(п) U

U Т"(А).

Теорема 11. Пусть А € R+. где аг > 0. и Г( А) ф 0. Тогда

l^t i>r

с(А) = max

(лг)ег(А) ЦГ-1)

Каждая неотрицательная симметричная матрица X = 1 ^ '■ .1 ^ п. где

,г„ = 0. задает вектор А. для которого а, = иХ = € Булем

7 = 1

говорить, что матрица (сеть без петель) А' задает вектор А.

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

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

Лемма 3. Пусть А € 1+ н Х(А) = 6 Г(А: г( А)), причем г( А) =

= ск,,. Тогда для пары векторов (А'. А") и вектора А'", где = а, - г{А){ч - 1), 1 ^ / ^ к. а',' = а,. <1 < г ^ п. а'/' = а, - с(А)(Ч - к), к < > ^ ч, имеет место (А'. А") е М+.'Г". А'" е и Г(А'. А": с(А)) ф 0. Г(А"': с(А)) ф 0.

Алгоритм 2 . Построение наследственно минимаксной сети без петель. Пусть А - произвольный вектор из К+ . Наследственно минимаксная сеть строится следующим образом

Шаг 1. Применяется теорема II для вычисления минимакса с(А) =

= шах с,г = са-ч- Числа <:кч. к, ц задают веса дуг искомой сети (элементы сим-((.г)еТ(А)

метричной матрицы) Х{А). равные <:{А) и равные 0 (теорема 10)

Шаг 2. Применяя лемму 3, вычисляются пара векторов {А'. А") и вектор А Для пары векторов (А'. А") применяется алгоритм 1 для построения наследственно минимаксной двудольной сети. Этим будут найдены веса дуг хч искомой сети Х{А).

где 1 $ ) < к. ц < ./ < п.

Далее для вектора А'" применяются шаги 1 и 2 данного алгоритма. И т.д. Пусть X = (*>})■ 1 $ 1-.) ^ произвольная сеть без петель (матрица), у которой = 0. V 1 ^ г ^ гг. Введем обозначения для сумм весов дуг: для V. V С и (л). V П V = 0, положим ¿(Щ = -'и. = X •г"- "если

KJ

Xij sC c4i.j,ro6{U) = 'Ш]и21 1} - S(U),S(U.V) = c\U\\V\ - S(U.VY

Обозначим ЯЛ( А: г) = {Ъ : D ^ A. V(D:r) ф 0} множество всех с реализуемых векторов, вписанных в А В данном разделе для произвольного вектора А будет найден (.--реализуемый вектор из ОТ( А: с) с наибольшей суммой координат Применяя ХФ (2.1) для АеК+ введем обозначение

f I min 6k{A\г)|. Г( А: с) = 0. К \ 0. Г(А: с) ф 0.

Основные результаты главы сформулированы в теоремах 12 и 13.

" п II

Теорема 12. Пусть А е К" . Тогда max У" d, = V" в, - Л'(А: с), где

t=i

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

Пусть А 6 1" и с ^ 0. Очевидно, что существует п[А: г), для которого

" "

У^ а, - ¿{А: с) = У"\пш(а(Аи').и,). /=1 >=1

По правилу (1.4), величина а = а(А: г) задает вектор

аг>(А,) = .....(!<„0,А:'»).

Теорема 13 . Пусть ЛеК". Тогда Г(Аа(А:':); с.) ф 0. Пусть А € К" . где Г(А;с) ф 0 и и 112 = 0». {Д П И2 = 0 -разбиение множества и(п). Разбиение множества !/(п) задает два подвектора А-, = = (а,), и, € ¿Д. А2 = (а,), и, € Ь*2, и каждую сеть Л'(А) = (.г,_,) из Г(А;с) можно представить в виде Х( А) = Х\ ()+Х2{ А2)+ХЛ(А1. А2). где Хх (А^ =

= (.г0)-«¿-и,; е их.х2(А2) = (х>3). е и2. Л'3(А,. а2) = (,г0), н, е е е и2.

Для произвольной пары векторов (А. В). где А 6 . В £ К^ и

,=1

г» "

найдется такое число «д. что ^ ппп(^ . ла) = Для пары векторов (А. ВА),

7 = 1 '=1

где/)"4 = / *А" ^ ^ ЛА' 1 <С I <; 7)( выполняется условие замкнутости, то есть

) Ь) < за.

(А.Ва) е

Случай (2.3) в транспортных задачах называется открытым. Имеет место Лемма 4. Пусть для векторов А 6 . В 6 М+ справедливо (2.3). Для множества матриц

Г^(А.В:с) = {А'(А. В) = (х„) : 0 ^ х,} ^ с \ti.j.

т "

хц = а1 ' < "■ ^ ьг1 ^ ^

7 = 1 '=1

имеет место <:{А. ВА ) = шт{г : Г^(А. В:с) ф 0).

Приведем оценки снизу и сверху для сумм весов дуг 6(1/ 1), 6(1/2). ¿('-''1. 1/2)■ В теоремах 5 и 12 содержится доказательство следующей теоремы.

Теорема 14. Пусть А € К",Г(А:с) Ф 0 и .¥( А) - произвольная сеть из Г(А:с). При любом разбиении множества узлов I/(п) = 1}\ и И2. П 1/2 = 0 для сумм весов дуг6(Ъ'\). 6(1/2). 6(1/1.и2) подсетей А'1 (А[). Х2(А2). Аз(Аь А2) имеет место

^¿(А]. А-2А': г) < 6(1/]) £ а, -тях(6(А1-с.).6(Л2:г))\

\i.ef/ 1 '

\ ( И " И + *(А1.А2А1-.с)\ «с 6(1/2)

т-лх(6(А1:с).6(Л2:с)) ^ 6(Ь'}.и2) «С «," - А**':<0- (2.4)

и.еи,

Результаты, содержащиеся в теореме 14. имеют приложения в теории «Потоки в сетях». Рассмотрим усеченный сетевой многогранник Г(А;с) ф 0. где А 6 . Любую неориентированную сеть из Г( А: с) можно рассматривать как ориентированную с симметричной матрицей весов дуг (пропускных способностей дуг). Пусть ЬТ(п) = = II \ и 1/2.гж1]\ П I/ 2 = 0 — произвольное разбиение множества узлов и (п.). которое задает разрез любой сети из Г( А: с). В подмножествах V| и I/2 выберем соответственно узлы-источники и узлы-стоки: V] С £/]. 1'2 С (/2

Рассмотрим классическую чадачу о максимальном потоке. Пусть Х(А) — некоторая сеть из Г(А;с). Задача о вычислении максимального потока из множества источников 1_1 в множество стоков \'2 сводится к двухполюсной. Добавляются два новых узла »о и!/„+1 и множество дуг («о-"¡). где н,- € V]. и (71„ + 1- »;)• где Н; £ 1'2, для пропускных способностей которых полагается = У ' ?/, 6 У]; ;г,-„_|_1

:

= У ' .г^.и^ € \'2- Затем применяется известный алгоритм вычисления максимального потока «метод пометок».

1С

Здесь рассматривается другая потоковая задана, в которой полагается, что сами узлы формируют пропускные способности дуг Для разреза, определяемого разбиением множества узлов II(п) = Ь\ и £/2, формула (2.4) задает ограничения его пропускных способностей всех сетей из Г( А: с). Поэтому неравенства в (2.4) влияют на ограничения величины любого (в том числе и максимального) потока из множества источников V] в множество стоков У2 для любой сети из Г(Л: с). Будет показано, что неравенства из (2.4) задают точные нижнюю и верхнюю границы величины пропускной способности разреза 5(11 и2).

Возможен случай, когда ограничения для величины 6(17\.112)ъ (2.4) строгие. Но в общем случает услилить неравенства в (2.4) невозможно. Отметим также, что ограничения в неравенствах (2.11) и (2 14) для величин 5(1^). 6{112) в общем случае являются достижимыми

Справедлива

Теорема 15. Для любого вектора Ае1'|. где Г(Л: с) ф 0. и произвольного разбиения множества узлов 1Г(п) -- И\ и \]2 оценки, приведенные в теореме 14. являются точными (достижимыми).

Результаты теоремы 14 имеют приложение в теории графов и мультнграфов.

Теорема 16 . Пусть АеК". Г(А: с) ф 0- Щп) = (/, и И2. £/, П И2 = 0. и V] С Ь\. У2 С и-2. где V'! - множество узлов-источников и \ 'г - множество узлов-стоков. Для сетей усеченного сетевого многогранника Г( А\с) справе,оливы следующие утверждения:

а) для произвольной сети из Г( Д; с) величина любого потока (в том числе и максимального) из У1 в 1'2 не превосходит верхней оценки значения пропускной способной разрезаЛ(1/\. 112) формулы (2.4):

б) существует сеть из Г(А:с). в которой (например, при V-! = Ь'\ и У, = Ы2) величина максимального потока из У2 в У2 не менее нижней оценки значения ¿(0',. Ь'2) формулы (2.4):

в) если существует сеть, в которой значение 6(Ь\. и2) достигает верхней оценки из (2 4). то найдется сеть (например, при V] = (Д и У2 = и2). где величина максимального потока из 171 в У2 равна правой части (2.4):

г) если существует сеть, в которой величина 6(Ъ\.и2) достигает нижней оценки из (2.4). то найдется сеть, где величина максимального потока из в У2 не превосходит левой части (2.4). причем существует сеть (например, когда 1'', = 1Л и У2 = Ь2) с

величиной максимального потока, равной нижней оценки для <)(6'i. í/2).

В третьей главе аналогичные результаты получены для классов сетей с петлями Очевидно, что для любого вектора А из R![_ имеет место ["¿(А) ф 0. Для А 6 R+, с J (I и i1 Е Z. 1 ^ A- s; п.. характеристической функцией (ХФ) называется

Ак{А: с) = ск2 - ^ ("' - - + J2 "" '' ^ rk ^ ">■■■ (зл)

+ 1 (> А + 1

, 2 г к

Пеотрицательность ХФ (3.1) является необходимым и достаточным условием с-реализуемости.

Теорема 17 . fic.in А £ М+ . то

Г/ДА: г) ф 0 Д¿.(А: с) ^ « VA-, ^ ск sc

В дальнейшем будем применять ХФ (3.1) и ее упрощенный вид

Ak.(A:c)=cH'k(A:c)-J2»¡+ <ЗЛ')

isJA' i>l[AA:,:)

где/д.(А:г) определено в (2.1').

Для вектора А <Е IR + вычислим наименьшее значение г = г/.(А). при котором Г/Л А: с) ф 0.

Пусть А € R+. Значение r:L(А) = min{r : Г/ДА: с) Ф 0} называется минимаксом для А или Г;, (A:r¿).

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

minie : Г/ДА: с) ф 0} = mili maxjjn : А'(А) = (j-,,)}.

A'(A)srí.(A) >J 1

Для мипимакса имеет место •

Теорема 18. Пусть А £ R+. Величина с является минимаксом (г = г/ДА)) Г,ДА: с) / 0и Эр £ Ъ. г sí ср ^ а,,, что Д,,( А: с) = 0. Перейдем к построению формулы вычисления мипимакса (-i(A). где А е . Для V (/.. г) € Т'(А) (см. (2.2)) построим систему соотношений

/^I 1>г С,,. = ---.

Ir (3.2)

(•frt > ar+l. г < п.

. <1,1 ^ <!,-■ Г > t.

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

Теорема 19 . Пусть А е к" . Тогда г;,(А) = шах с,,..

+ (М-)еТ'(А)

Сети с петлями (матрицы) из Г ¿(А; с/А А)) называются минимаксными. Следующая теорема характеризует минимаксные матрицы.

Теорема 20. Если А е К?| и \(А:(^{А)) = 0. где с ^ ер ^ п,,. то для -¥(А) = {хи) е Г/.(А;С/.(А)) имеет место

сь(А). (¡.Л е{и.Л:Кг.]<р} и

и {(I. Л АЩ^р.р< ] < Гр} и {(?. .Л :р<Щ Гр. />}:

o.('.Лe{(¿.j)■.p<¿^?>.l;l<jí¡'>}u и {(1.Л:1'р<1^п.р<] а I',,}.

Обозначим Т/А") = {(г\') ■ 1 ^ ' "} Покажем, что при нахождении мини-макса можно удалить все неравенства из (3.2) и при вычислении сь{А) рассматривать только пары индексов из 7/,(А) = Т;,(г).) и Т"(А).

Теорема 21. Пусть А е К,. Тогда А = шах ---

Каждая неотрицательная симметричная матрица А' = (х^). 1 < '-.У ^ " где

п

= 0. задает векгор А. для которого а/ = = Х(А) 6 Гг. (А) Будем

J

говорить, что матрица (сеть с петлями) А' задает вектор А

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

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

Лемма 5. ПустьА е К" иА'(А) = (.г,7) £ Г/_( А: А)), причем сь (А) = = с.кч. Тогда для пары векторов (А'. А") и вектора А'", где а\ = а, - с^{А){д - 1). 1 «с ; ^ к. я" = «„ </<;«: II. а'," = (1, - г.1(А){<1 ~ к)- к < ' < '1• имеет мест0 (А'. А") е А'" 6 1С " Г [.(А'. А"-.сил)) ф 0. Г^А"':сь(А)) ф

ф0.

Алгоритм 3 . Построение наследственно минимаксной сети с петлями.

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

Шаг 1. Применяется теорема 21 для вычисления минимакса cl(A) —

= max c-tr = ('к,,- Числа (\ч, к. q задают веса дуг искомой сети (элементы сим-U.r)eT(A)

метричной матрицы) ЛДА). равные с;Д А) и равные 0 (теорема 20).

Шаг 2 . Применяя лемму 5. вычисляются пара векторов (А'. А") и вектор А'". Для пары векторов (А1. А") применяется алгоритм 1 для построения наследственно минимаксной двудольной сети. Так будут найдены веса дуг x,j искомой сети Л'(А). где 1 < / ^ к. ч < j < п

Далее для вектора А'" применяются шаги 1 и 2 данного алгоритма. И т.д. Пусть Л' = (J',j). 1 $ i.j ^ /?-произвольная сеть с петлями. Для подмножества

U С L' {n) введем обозначения для сумм весов петель: = ^ ^l(U) =

и.еи

= c\U\-6L(U).

Обозначим ОТ ¿ДА: г) = {D : D ^ A.TL{D:c) ф 0}-множество всех г-реализуемых векторов, вписанных в А. Для произвольного вектора А будет найден (•-реализуемый вектор из ОТ/ДА: с) с наибольшей суммой координат. Применяя ХФ (3.1) для А е R+ введем обозначение

С | min ДдДА; с)|. Г/ДА: с) = 0. Д( А: с) = { *•

1«. Г/ДА: с) ф 0.

Основные результаты главы III сформулированы в теоремах 22 и 23.

II 71

Теорема 22 . Пусть A G R+. Тогда max > Л, = } а, - Д(А; с).

где вектор А получен из вектора А упорядочиванием его координат по невозрастанию Пусть А € R+ и с > 0. Очевидно, что существует о/ДА: г.). для которого

п и

У" а, - Д(А; с) = У^ шш(м/ДА: с), я,). ,=i i=i

По правилу (1.1) величина а = а/ДА: г) задает вектор

дшЛА-.с) _ ^a(nL[A.r.))

Теорема 23. Пусть А е К+ . Тогда rL(A"'-,A;r): с) ф 0. Пусть А 6 R" . где Г/ДА; с) ф 0 и b\ U U2 = U(n). {/, П U2 = 0 -разбиение множества U{ti). Разбиение множества U(n) задает два подвектора Ai = = (ai).n, в U\. А'2 = (ai). и, е и2. и каждую сеть АДА) = (xjj) из Г/ДА: с)

можно представитьввидеЛ'(А) = Хг (А1 )+Х2[А2)+Х-л{ А,. А2). где Л', (Л!) =

= (хи). и,.1Ч е и1.Х2(А2) = (.ГЧ).П,.Ч3 е U-2.X-AAi.A-2) = (.г,,). и,- € е иг.т^ е и2.

Приведем оценки снизу и сверху для величин 26{1!\) + (Ь (). 2 6{1>2) + <$£ (1;2 )■ 6{У\. 1)2). Из теорем 5, 22 и леммы 4 следует утверждение.

Теорема 24. Пусть А € К+ . Г/ЛА: с) # 0 и А'(А) - произвольная сеть из Г(А; с). При любом разбиении множества узлов и(п) = Ь\ и (/2. 6*1 П Ь'2 = 0 для величин 2<5([/]) + ¿¿(1/,). 2д({/2) + ¿(иии2) подсетей А^АО. А'2(А2).

А:,(А1.А2)

й(А!.А2А1:с) + < «, -тах(Л(А1:г).Д(А2:с)).

и, ей,

£ в._ ^ П1 + 6(АиА2А'-.с)^2б(и2) + б,ли2)^

и.ег-'з ».ел/,

<; а,;- пшх(Д(Аг.с).Л(А2;с)).

,х(А(А!:г). Д(А2'.(0) < ¿(Ь\.и2) ^ '"'(Аь А2Л':с).

Очевидно, что для вектора А 6 К+. где Г/. (А: г) ^ 0. оценки для величин ¿(1/1). 6{112) и д{Ь\ . и2) зависят от разбиения множества узлов II(п) = Ь\ и £<2 « от параметра с.

Заключение

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

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

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

Список публикаций по теме диссертации

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

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 II. The algorithm for constructing a hereditarilv minimax network vvith predefined yector ofnode degrees //2012 Tohoku-Section Joint Convention Record of Institutes of Electrical and Information Engineers. Japan

7. Селин U.C.. Цурков В И. Метод характеристических функций для классов сетей с фиксированными степенями узлов // Изв. РАН Теория и системы управления. 2014. N5. С. 59-68

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

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

Подписано в печать 16.09.2014 Формат бумаги 60x84 1/16 Уч.-изд. л. 1. Усл.-печ. л. 0,9 Тираж 100 экз. Заказ 10

Отпечатано на ротапринтах в Федеральном государственном бюджетном учреждении науки Вычислительный центр им. А.А. Дородницына Российской академии наук 119333, Москва, ул. Вавилова,40