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

• Селин, Павел Сергеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Селин, Павел Сергеевич

Оглавление

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

Введение

I. Двудольные сети с фиксированными степенями узлов

1.1. Характеристические функции и условия с-реализуемости

1.2. Минимакс и наследственно минимаксная матрица смежности для двудольной сети

1.3. Характеристические уравнения

1.4. Приведение пары векторов к с-реализуемости в двудольную сеть

II. Сети без петель с фиксированными степенями узлов

2.1. Характеристические функции и условия с-реализуемости

2.2. Минимакс и наследственно минимаксная матрица смежности для сетей без петель

2.3. Характеристические уравнения

2.4. Приведение вектора к с-реализуемости в сеть без петель

2.5. Ограничения для сумм весов дуг класса сетей без петель с фиксированными степенями узлов при произвольном разбиении множества узлов

2.6. Приложение в теории «Потоки в сетях»

III. Сети с петлями с фиксированными степенями узлов

3.1. Характеристические функции и условия с-реализуемости

3.2. Минимакс и наследственно минимаксная матрица смежности для сетей с петлями

3.3. Характеристические уравнения

3.4. Приведение вектора к с-реализуемости в сеть с петлями

3.5. Ограничения для сумм весов дуг класса сетей с петлями с фиксированными степенями узлов при произвольном разбиении множества узлов

3.6. Приложение в теории «Потоки в сетях»

Заключение

Список литературы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В работе построен математический аппарат исследования классов сетей (взвешенных графов, графов, мультиграфов [1,2,7,10,34,43]) с фиксированными степенями узлов. Также получены формулы для вычисления минимаксных значений, определяющих необходимые и достаточные условия непустоты рассматриваемых классов сетей, и алгоритм построения наследственно минимакснои сети.

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

Настоящая работа основана на идеях, содержащихся в работах о реализуемости степенями вершин наборов целых неотрицательных чисел в граф [13-16,42,43,47] и о реализуемости неотрицательных чисел во взвешенный граф, веса ребер которых не превосходят заданного параметра [17-20].

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

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

Результаты имеют приложение в теории «Потоки в сетях» [41, 45, 48, 50, 51, 53, 54, 57]. Полагая, что веса дуг - это пропускные способности, разбиение множества узлов на два подмножества задает разрез сети и третья переменная - это пропускная способность разреза. Если в одном из подмножеств узлов выбрать узлы-источники, а в другом - узлы-стоки, то ограничения для третьей переменной есть ограничения для величины максимального потока (величина максимального потока равна минимальной величине пропускной способности разреза).

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

Результаты также имеют применение в сетях связи [4,5,7,8,35,46], сенсорных сетях [49,56].

Апробация

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

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

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

Публикации

Основные результаты диссертации опубликованы в 7 печатных работах [30, 32, 36-39, 55], две из которых находятся в изданиях из перечня ВАК [30, 39].

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Метод характеристических функций в задачах оптимизации на некоторых классах сетей»

Введение

Все п-вершинные сети будем рассматривать с множеством узлов и(п) — = {щ,... ,ип}, а все п, т-вершинные двудольные сети - с множествами узлов (долями) и(п) = {щ,... ,ип} и У(ш) = {г>1,...,Ут}. Будем отождествлять п-вершинные сети и п, т-вершинные двудольные сети с неотрицательными матрицами смежности соответственно X = (х1 ^ 1,3 ^ п, и X = (х1 ^ г ^ п, 1 ^ 3 ^ т, где Х{2 = - вес дуги (петли при г = 3)- с вершинами щ и и^ в первом случае и х^ - вес дуги с вершинами щ и - во втором. Под суммой сетей (матриц) X' — (х'^) и X" = {х'1^) с равными количествами узлов называется сеть (матрица) Х' + Х" =

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

= {А = (о!,...,оп) : щ ^ ОУг}, 1+ = {А е М+ : а{ ^ а{+1,1 < г < тг - 1 ( п > 2)};

п тп

М+,= = {(А, В) : А е , В е к?, 5>* =

г=1 3=1

= {(А, в) е : А е 1+, в е 1+ }.

В транспортных задачах [3,40] условие равенства сумм координат пары векторов из М™'™ называется замкнутостью или условием баланса.

Многие утверждения и конструкции (не ограничивая общности) рассматриваются

-ц —'

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

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

п

ТЬ(А) = {Х(А) = (жу) : ху = хл ^ 0 Уг, j;degщ = 53 = а» Уг} -

3 = 1

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

Г(А) = {Х{А) = (хц) : Х{А) е Гь(А);хц = 0 Уг} - класс сетей без петель;

Гь(А;с) = {Х(А) = (®у) : Х(А) е ^ сУг, Л,

Г(А;с) = {Х(А) = (хц) : Х(А) е Г(А)]х^ ^ с Уг, - классы сетей, веса дуг (и петель) которых не превосходят заданного неотрицательного параметра с.

Множества сетей-матриц (без петель и с петлями) Г(А), Г^ (А) и Г(А; с), Г^(А; с) называются соответственно сетевыми и усеченными сетевыми многогранниками [28]. Очевидно, что Г(А) С Гс, (А) и Г (А; с) С ТЬ(А; с).

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

Г (А, В) = {.Х{А,В) = (®у) : хц ^ ОУг^';

га п

degг¿¿ = ^Хц = а{ Уг; degvj = ^ху = У./},

3=1 г=1

Г(А, В\ с) = {Х(А,В) = : Х(А,В) € Г(А,В);®у ^ с}.

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

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

Для произвольного вектора А € = {А € К" : сц € Ъ Уг} возникает вопрос: является ли он реализуемым в сеть (с петлями или без петель). Сети с весами дуг, равными нулю или единицы называются графами. В случае графа без петель ответ был получен Хакими С. Л. [42].

п

Утверждение. Пусть А € = {А € М+ : а* € 2 Уг} и ^^ а^ =

г=1

q € Z. Вектор А реализуем в граф без петель тогда и только тогда, когда реализуемым является вектор А! = (а2 — 1,..., atti+i — ßai+2? • • • ? Оп)-

Данное утверждение содержит в себе алгоритм построения графа с заданным вектором степеней узлов.

Позже работ Хакими, аналитический критерий реализуемости был получен Эрде-шем П. и Галлаи Т. [47].

п

—TI V ^ _

Утверждение. Пусть A Е Z+ и у. ai — q £ Z. Вектор А реализуем в

i=l

граф без петель тогда и только тогда, когда

к п

к(к — 1) — Е + a¿} ^ 0 \/к : 1 < & < п — 1.

г=1 i=fc+l

Однако, приведенные выше результаты неприменимы в случае взвешенных сетей, сетей с петлями, двудольных сетей, а также в случае ограничения пропускных способностей дуг некоторой константой. Эти случаи были исследованы Мироновым А. А. [14-20] и будут рассмотрены в главах I - III.

Основная конструкция работы, приведенная выше, основана на следующих построениях.

1) Приведены характеристические функции, зависящие от координат векторов и параметра. Если координаты рассматриваемых векторов упорядочены по невозрастанию, то неотрицательность этих функций есть критерий того, что Г( А, В; с), Г (А; с), Гь(А;с) ф0.

2) Применением характеристических функций получены аналитические формулы вычисления минимаксных значений

min{c : Г(А, В; с) ф 0}, min{c : Г(А; с) ф 0}, min{c : TL(A; с) ф 0},

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

3) Построены специальные разбиения множества узлов сетей усеченных многогранников Г(А,В\с), Г(А;с), Г^А; с) ф 0, и приведены характеристические уравнения. Эти уравнения точными равенствами связывают значения характеристических функций и сумм весов дуг (и петель) подсетей, порожденных указанным разбиением, для всех сетей усеченных многогранников.

4) В случаях Г(А, В] с), Г (А; с), Г ¿(А; с) = 0 с помощью характеристических функций найдены наименьшие величины, на которые необходимо уменьшить значения сумм координат векторов, чтобы получить ореализуемую пару векторов и с-реализуемые векторы. С применением характеристических уравнений построены соответствующие с-реализуемые пара векторов и векторы.

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

I. Двудольные сети с фиксированными степенями узлов

1.1. Характеристические функции и условия с-реализуемости

Сформулируем условия, при которых Г( А, В; с) ф 0. Для этого введем понятие характеристической функции [22-25,27,29,56].

Определение 1. Пусть (А, В) € К™'™ и с ^ 0. Характеристической функцией (ХФ) называется

га к

6к{А, Б; с) = Ьз ~ XI & ~ ~ (1-1)

3=1 Ь^ск г=1

Неотрицательность (1.1) есть необходимое условие с-реализуемости пары векторов в двудольную сеть (без петель).

Теорема 1. Пусть Г (А, В; с) ф 0, где (А, В) Е Тогда 4(А, В; с) ^ 0 У/г, 1 < к ^ п.

В случае (А, Б) € ХФ (1.1) можно упростить: если обозначить 1к{В; с) =

{шах{^ ^ ск},Ъ\ ^ ск,

О, &1 < с/г, Т°

к

5к(А,В;с) = сЫк(В-,с) + ^ - ^а^ 1 < /с ^ п. (1.1')

3>1к{В-,с) ¿=1

В следующем утверждении содержится критерий с-реализуемости пары векторов в двудольную сеть при условии упорядоченности координат векторов по невозрастанию [21-25,27,29,56].

Теорема 2 . Если (А, В) € К+ то Г (А, В\с)ф0 4 (А, Б; с) ^ 0 У/г, 1 < А; ^ п.

—9 12

Пример 1. Применим ХФ (1.1) к паре векторов (А, Б) 6 где А =

= (30,30,30,26,26,14,14,4,4), В = (21,21,21,21,19,19,17,17,8,8,3,3) и с = 2. Получим ¿х (А, В] 2) = -6, ¿2(Д5;2) = —14, 63(А,В;2) = -24, ¿4(А, В\2) = -30, ¿5(А, В; 2) = -40, ¿6(А, В; 2) = -38,

57(А,В] 2) = —36, Ss(A, В; 2) = -24, <59(А, В; 2) = -14 и min6к(A, J3; с) =

к

= Ó5 (А, В; с) = —40 (это значение потребуется в примере 6). Из теоремы 2 следует, что Г(А, В; 2) = 0.

_9 12

Пара векторов (А, -В) из примера 1 будет исследоваться во всех примерах первого раздела.

Пример 2 . К паре векторов (А, В) примера 1 при с = 4 применим ХФ (1.1). Тогда ó1(A,B;4) = 16,á2(A,B;4) = 26,á3(A,B;4) = 28,Ó4(A,B;4) = = 34, Sß(A, В] 4) = 32, ¿6(A,B;4) = 22,¿7(A,B;4) = 8, Í8(A,B;4) = 4, ¿9(А, В; 4) = 0. Из теоремы 2 следует, что Г(А, В; 4) ф 0.

1.2. Минимакс и наследственно минимаксная матрица смежности для двудольной сети

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

Определение 2. Пусть (А, Б) G R"'™. Величина

с(А, В) = min{c : Г(А, В-с) ф 0}

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

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

minie : Г(А, В; с) Ф 0} = min тах{хц : Х(А,В) = (хц)}. 1 X(A,B)er(A,B) i,j 1 J 4 ' J'J

Для минимакса имеет место [21-25,27,29,56].

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

минимаксом (с = с(А, В)) -Ф=Ф- Зк G Z, 1 ^ к ^ п, что В-, с) = 0 и &i ^

-Л 77Х

Построим формулу вычисления минимакса с(А, В), где (A, JE?) £ М+']=. Обозначим Т(А,В) = {(i,j) : а{ > a¿+1 или г = n, bj > bj+i или j = m}. Для

г) £ Т(А, В) построим систему линейных соотношений

г

_ ¿=1 з>г

сгг ~ Тг ' (1-2)

, с^Ь > Ъг+1, г < т.

Если система (1-2) при некоторых г) не имеет решения, то положим = 0. Имеет место [25-27,29,31,56]

Лемма 1. Для (А, В) 6 имеет место

с(А, .В) = тах с<г. (1.3)

Отметим, что пара индексов (к, р), при которой с( А, В) = определяется неоднозначно.

Определение 3 . Сети (матрицы) из Г(А, В; с( А, В)) называются минимаксными.

Следующая теорема характеризует минимаксные матрицы (см. ХФ (1.1;)) [25-27,29,56].

■ щ

Теорема 4 . Если (А, В) £ В; с(А, В)) = 0 и &1 ^ с(А, В),

то для Х(А,В) = (хц) £ Г(А,В-,с(А,В)) справедливо

Хц

{о, г>к, з>1к{В-с{А,В)). Вычисление минимакса с( А, 23) можно упростить: при его вычислении достаточ-

но использовать первое соотношение из (1.2).

—.ТТЬ

Лемма 2 . Пусть (А, В) £ К+ =. Для Ш £ Ъ, 1 ^ Ь ^ п, положим

с+а = тах

1 1<г<т

г=1 з>г г=1 3~>Я

¿г Ьо

(ь,г)ет(А,в) *

Тогда а) СгдЬ ^ Ьд и б) с^ ^ (если д < т), причем с^ = с^ = С49//,гдед" = пипО' : € Т(А,В),.; > д}.

Доказательство, а) Предположим > Для д возможны два случая: 1) Ь\ > Ьд и 2) 61 = Ьд.

1) Здесь существует ^ = тах{<7 : (£, ]) € Т(А, В),^ < <7}. Тогда для разности

~ сЬд' получим

¿Ьд ~ сЬд' =

Е^'Е^'

3>Я

г=1

ч

г=1_з>д'

{ч' - ч) 53 ~ ^53^'+«53 ^

1 г=1

£

4 9 1 _г=1_.7>д_э=д'+1

1 т'

Еа*-536; +« 53 ъз

1 \г=1 ¿>д /

Я'

( 4 Е ^

з=ч'+1 (я - я')^

Ьд \

г

г

\

1 д

= Е (ьз~с^) =

4 3=<7'+1

/

9г

что противоречит условию леммы.

bq ¿= 1 j~>4.

2) Так как по предположению bq < Ctqt, то здесь — < —

tq

и bqq <

т

< У] di — bj. Следовательно, ^^ — bj > 0, что противоречит условию

г=1

замкнутости.

г=1 ¿=1

б) Пусть q < т. Для разности — имеем

Ctq — Ctq" =

г=1 j>q i= 1 j>q"

tq

tq

//

1

t

г=1

¿><? j>q'

qq

//

t

{q" - g) - fe" " 9) E bi " E b*

1 _t=l_i=g+l

t'

qq

и

1

9

1 \г=1 j>q" J j=q+1

E ^

Ctq"t(q" - g) j=q+1

/

V

9 J=g+1

/

qt

q" - q

Предположим, что < 6q+i. Тогда cíg — cíg" < -(ctq" — Ctq) и (cíg —

— cío") — <0, что противоречит условию леммы.

q

q"

Пусть Ctqt — bq+i. Тогда (ctq — Ctq")— = 0, что справедливо тогда и только тогда, когда ctq = ctq".

Из лемм 1 и 2 следует [25-27,31,56]

■ ■ тть

Теорема 5 . Пусть (А, В) Е =■ Для минимакса с(А, В) имеет место

с(А,В)= max —-. (1.4)

(t,r)eT(A,B) tr

Пример 3 . Найдем минимакс с(А, В) для пары векторов примера 1. Здесь Г(А, В) = {(3,4), (3,6), (3,8), (3,10), (3,12), (5,4), (5,6), (5, 8), (5,10), (5,12), (7,4), (7, 6), (7,8), (7,10), (7,12), (9,4), (9,6), (9,8), (9,10), (9,12)}. Применим теорему 5.

Вычисляя величины c¿r, где (t, г) £ Т(А, В), получим С34 = —С36 = С38 = 2|, сз ю = 2|, сз 12 = 2|, с54 = 2|, ese = 2у|, c5g = 3, С5 ю = Q> 12 = 2^, с74 = 2|, С76 = 2|, С78 = с7 ю = 2||, с7 12 = 2^, с94 = 2^, с96 = Сд$ = Сд ю = 1ц, с9 12 = iff.

Из теоремы 5 следует, что с(А, В) = 3. Для каждой минимаксной матрицы Х(А, В) = (Xij) £ Г(А, В; 3) имеет место (теорема 4)

. 3, 1 ^ i < 5, 1 < i ^ 8, г .

tJ i 0, 6 < i ^ 9, 9 ^ j ^ 12. { J

Определение 4 . Сеть (матрица) Х(А, В) = (х^) называется равномерной, если справедливы два условия [25-27,31,56]:

&) = СЬр, Ъу — Ъд Л Х^у — Жрд

б) ^ Ор, Ъу ^ Ъд л ^ Хрд.

Каждая неотрицательная матрица X = (х^), 1 ^ г ^ п, 1 ^ ^ ^ ш, задает пару векторов (А, В) £ К™'™, где

тп п

<Н = ьз = Е*«' Х = € Г(А,В).

¿=1 »=1

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

Определение 5. Для (А, В) Е К™'™ двудольная сеть-матрица (минимаксная) Х(А, В) называется наследственно минимаксной, если каждая ее подматрица есть минимаксная матрица пары векторов, которую задает эта подматрица [25-27,31,55,56].

Основные свойства наследственно минимаксных матриц заключены в следующих двух (эквивалентных) утверждениях [25-27,31,56].

Теорема б. Для каждой пары векторов (А, В) из М™'™ существует единственная наследственно минимаксная матрица Х(А, В), причем она является равномерной.

Теорема в'. Каждый транспортный многогранник Г(А, В) содержит одну и только одну наследственно минимаксную матрицу, которая есть равномерная.

Алгоритм построения наследственно минимаксной матрицы заключен в следующей лемме [25—27,31,55,56].

__гул л-yi _______

Лемма 3. Пусть (А, В) в К+',= и Х(А,В) = (хц) € Г(А, JE?; с(А, В)), причем с(А, В) = Скд. Тогда для пар векторов (А', В') и (А", В"), где а'{ = a¿ - с(А, В) • q, 1 ^ i ^ к, b'j = bq+j, 1 < j < т - q, a'¡ = ak+i, 1 ^ i ^ n - к, b'J = bj - c(A, B) ■ к, 1 ^ j < q, имеет место (А', В') € {А", В") G и Г (А', В'; с(А, В)) ф 0,

Т{А",В"-с{А,В))ф0.

Замечание 1 к лемме 1. Из теоремы 4 следует:

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

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

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

Алгоритм 1. Построение наследственно минимаксной двудольной сети-матрицы [25-27,31,55,56]. Пусть (А, В)

— произвольная пара векторов из Наследственно минимакс-

ная матрица Х(А, В) = (Xij) строится следующим образом.

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

(t,r)eT(A,B) 4

5) и строятся подматрицы искомой матрицы Х(А, В), первая из которых состоит из

минимаксных элементов, а вторая - нулевая (теорема 4).

Шаг 2. Вычисляются пары векторов {А', В'), {А", В") (см. лемму 3), применяется теорема 5 для вычисления минимаксов с(А', В'), с(А", В") и опять применяется теорема 4 для вычислений части элементов подматриц Х\ (А', В') 6 £ Г (А', В'] с(А', В')) и Х2{А", В") е Г (А", В"- с(А", В")) искомой матрицы Х(А,В).

И т. д.

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

Пример 4 . Построим наследственно минимаксную матрицу Х(А, В) — = (хц) £ Г(А, В; 3), где (А, В) - пара векторов примеров 2 и 3. Часть элементов искомой матрицы определена в (1.5):

/

Х(А,В) =

\

Хц — 3 : Хг = (хц)

1 ^ г ^ 5 : 1 ^ г ^ 5

1 ^ 3 ^ 8 : 9 < з < 12

Х2 = {хц) - 0

6 ^ г < 9 : 6 ^ г ^ 9

1 ^ з < § 5 9 ^ з ^ 12

\

Теперь строим наследственно минимаксные матрицы

XI = Х^А; = (6, б, 6, 2,2), В[ = (8,8,3,3))

Х2 = Х2{А'( = (14,14,4,4), В'{ = (6,6,6, б, 4,4,2,2)),

координаты векторов вычислены по правилам леммы 3. Применяя теорему 5, получим с(А[, В[) = 2 = С32 и с(А'{, В") = 2 = С26- А из теоремы 4 для подматриц Х\ и

Х2 наследственно минимаксной матрицы получим

Х1(А'1:В[) =

Х2{А'(,В'{) =

— 2 Хз = (ху) \

1 ^ г ^ 3 : 1 ^ г ^ 3

9 < з < 10 : 11 ^ з < 12

Х4 = (ху) — 0

4 ^ г < 5 : 4 ^ г < 5

9 ^ з ^ 10 : 11 < 3 < 12 /

— 2 : Хъ = {хц) \

6 ^ г ^ 7 : 6 ^ г ^ 7

1 ^ з < 6 : 7 ^ з ^ 8

II 1.® — 0

8 ^ % < 9 : 8 ^ г ^ 9

1 < 3 < б : 7 ^ з ^ 8 /

Строим наследственно минимаксные матрицы Хз = Хз(А'2 = (2,2,2), #2 = (3,3)), Хд = Х±{А2 = (2,2), В2 = (2,2)), Хъ = Хъ(АГ2 = (2,2), = (2,2)), Хб = = (4,4), = (2,2,2, 2,0,0)).

Здесь можно применить замечание к лемме 1 и понятие равномерной матрицы. Получим с(А2, В'2) = 1,с(А'2',В£) = 1,с(А'2",В£') = 1, с(А2у, В2У) = 1 и все элементы подматриц Хз, Х4, Х5 матрицы Х(А, В) равны единице, а подматрица Х§ имеет вид

^6 =

11110 0

ч1 1 1 1 о оу'

Этим построена наследственно минимаксная двудольная сеть-матрица (для всех матриц, построенных в примерах настоящей работы, сверху и слева будем указывать

координаты векторов, задающих эти матрицы)

21 21 21 21 19 19 17 17 8 8 3 3

30 (s 3 3 3 3 3 3 3 2 2 1

30 3 3 3 3 3 3 3 3 2 2 1 1

30 3 3 3 3 3 3 3 3 2 2 1 1

26 3 3 3 3 3 3 3 3 1 1 0 0

26 3 3 3 3 3 3 3 3 1 1 0 0

14 2 2 2 2 2 2 1 1 0 0 0 0

14 2 2 2 2 2 2 1 1 0 0 0 0

4 1 1 1 1 0 0 0 0 0 0 0 0

4 U 1 1 1 0 0 0 0 0 0 0 oy

и завершен пример 4: Г(А, В;3) С Г(А, В; 4).

1.3. Характеристические уравнения

Пусть X = (Xij), l^i^n, т - произвольная двудольная сеть

(матрица) и U С U(n), V С V(m). Введем обозначение для сумм весов дуг: 5{U,V)= жуй, если а*,- ^ с\/г J, то S(U,V) = c\U\\V\ - S(U,V).

щеи

Определение 6. Пусть (А, В) G R+'™, где Г(А, В; с) ф 0. Для У/с, 1 < ^ к ^ п, /г-разбиением f/(n) и V(m) относительно пары векторов (А, В) и ограничения с (относительно множества Г(А, В; с)) называется представление U(п) = = C/f и C/2fc и F(m) = Vf и где Uf = {щ : i ^ к}, Щ = {щ : i > /с},

Vf = {vj : bj ^ ск}, V2 = {vj : bj < ck}.

Приведем соотношение, связывающее суммы весов дуг на подмножествах к-разбиений множеств U (п) и V(m) со значениями ХФ (1.1) [25-27,29,31,56].

Теорема 7 . Пусть (А, В) G R+'™ иГ(А, В] с) ф 0. Тогда для УХ (А, В) G £ Г(А, В; с) имеет место

¿(trf, Vi) + 5(U$, V2k) = Sk(A, В; с), 1 ^ /с ^ n.

20

(1.6)

и yyi i

К теореме 7 отметим, что при В 6 М+ имеет место = {vj : 1 ^ j ^ lk} и = {*>¿ : h + 1 < i < где 1к = 1к(В; с) (см. (1.1'))-

Определение 7 . Соотношение (1.6) называется характеристическим уравнением для множества Г(А, В; с) [25-27,29,31,56].

Характеристические уравнения (1.6) задают общие свойства всех сетей из Г (А, Б; с).

Пример 5. Определим некоторые общие свойства сетей из Г(А, В;3) и Г (А, В; 4), где (А, В) - пара векторов примеров 2-4.

а) Рассмотрим Г(А,В;3) при 5- и 6-разбиениях. Здесь $s(A,B;3) = О, <56(А,В; 3) = 8,

t^l = {ui,...,W5},C/| = {w6,...,1íg}, Vf = {vi,...,U8}, V? = {^9, ...,^12}; c/f = {«1, . . . , Uq}, Щ = {w7, . . . , u9}, v]6 = {vi, . . . , kf = {v7, . . . , v12}. Применяя (1.6), для VX(A, В) € Г(А, В; 3) получим

¿(C715,T/15) + ^|,F25) = 0,

á(C/16,y16) + J(C/26,F26) = 8.

Из первого равенства следует ¿(Uf, V-j*) = , V^5) = 0, что для каждой сети

Х(А, В) Е Г( А, В; 3) означает: дуги, порожденные подсетью с узлами Uf и V^, насыщены полностью (X{j = 3, щ £ C/f, Vj £ Vj5), а подсеть, порожденная узлами С/2 и У25, есть вполне несвязная (Xij = 0,щ Е Í7|, Vj Е Kf). Из второго равенства следует ¿(U!, VÍ) < 8 и ¿(tff, У}3) = 3 • 6 • 6 - ¿(t/f, V?) ^ 8, то есть S(Uf, Vf) ^ 100, что для каждой сети Х(А, В) £ Г(А, В; 3) означает: сумма весов дуг подсети, порожденной узлами Uf и V]6, не меньше 100, а сумма весов дуг подсети, порожденной узлами С/| и V-2, не превосходит 8.

б) Рассмотрим Г(А, В; 4) при 5-разбиении. Здесь ¿5(А, В; 4) = 32,

I/? = {«1.....= Vj5 = {Vi, . . . , V4}, V{ = {V5i-..,«i2}.

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

ад,у!5)+ад,у25) = з2.

Поэтому 6(и%,у£) ^ 32 и V?) = 4 • 5 • 4 - ¿(С/?, V?) ^ 32, то есть ¿»(/тр, У]5) ^ 48. Поэтому числа 32 и 48 задают ограничения для сумм весов дуг подсетей, порожденных узлами £/|, У2 и ? У]5 каждой сети (матрицы) из Г(А, -В; 4).

Отметим, что уравнение (1.6) задает ограничения для сумм весов дуг и других порож-

5

денных подсетей. Например, в п. б примера 5 так как ^ а{ = 142 и 5 (11^, У-±) ^ 48,

¿=1

то ¿(С/р, ^ 142 - 48 = 94.

Замечание 2 к теореме 7. Характеристическое уравнение (1.6) задает "жесткость" для сумм весов дуг подсетей, порожденных /с-разбиениями: чем меньше значение ХФ (1.1), тем меньше отличаются веса дуг х^ от 0 при щ £ 112, гл/ £ У2 и от с при щ £ и^, Vj £

1.4. Приведение пары векторов к с-реализуемости

в двудольную сеть

5П

Определение 8 . а) Пусть А, 2} £ М+. Вектор I) называется вписанным в А (И < А), если <1{ ^ а* \/г 1 ^ г ^ п.

б) Пусть (А, В), (£), Е) £ М™'™. Пара векторов (X?, Е) называется вписанной в (А, Б) ((£>, Б) ^ (А, Б)), если £> < А и Е < Б.

Обозначим ШГ(А, Б; с) = {(£>,#) : ^ (А, В), Г(£>, Е\ с) ф 0}

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

I шух ТТЬ

Применяя ХФ (1.1) для (А, В) £ введем обозначение

хглг* \ ) ,тт4(ЛБ;с)|,Г(А,В;с) = 0, 5{А,В-с) = \ к (1.7)

I О, Г (А, Б; с) т^ 0.

В случае £(А, Б; с) > 0 через /с* = к* (А, Б; с) обозначим такой индекс, для которого 15к* (А, Б; с) | = Б; с). Отметим, что значение к* определено неоднозначно. Например, для пары векторов (А, А), где А = (5,5,4,4), легко проверить, что 62 (А, А; 1) = ¿4 (А, А; 1) = — 2 и <5(А, А; 1) = 2. Поэтому здесь к* = 2 или Г =4.

Величина (1.7) - это минимальное значение, на которое необходимо уменьшить суммы координат векторов А и В, чтобы получить с-реализуемую пару. Основные результаты раздела сформулированы в теоремах 8 и 9 [30, 33, 36 - 39]. Теорема 8 . Пусть (А, В) Е К"'™. Тогда

п

тах ^ = а{ — 6 (А. В: с).

(.о,Е)ет(А,в-,с) ^

г=1 г=1

Напомним, что вектор А построен из координат вектора А упорядочиванием их по невозрастанию. Для А Е К" иа ^ 0 положим Аа = (а",..., а")-такой вектор, что

1 {аг, а,{ < а. 4 '

Пусть (А, В) Е М™'™ и с ^ 0. Очевидно, что существуют такие числа ад (А, В; с), ав(А, Б; с), при которых

гг п

- 6(А,В-с) = ^тт{аА{А,В\с),аг),

г=1 г=1

тгг тп

53Ь, -¿(А,-В; с) = (Х-9)

¿=1 ¿=1

Правило (1.8) и числа сха(А,В]с), а в {А, В] с) задают пару векторов (АаА(Л'в'с\ Вав(А,в'с)) =

= ((а[аА{Л>В>с)),... ,а!аА(А,В;с))), (Ь[ав{А'В'с)\ ... ,6^в(А'В;с)))). Отметим, что при Г(А, В;с) ф 0 справедливо (АаА^В'с\ Вав<<А'В^) = (А, В).

Теорема 9. Пусть (А, В) Е М+'™. Тогда Г(АаА(Л'В;с), Вав(Л,-В;с); с) ф 0.

Доказательство теоремы 8 следует из лемм 4-6, в которых, не ограничивая общности, рассматриваются векторы с упорядоченными по невозрастанию координатами [30, 33,36-39].

Для пары векторов (А, В) Е и с > 0, где Г(А, В', с) = 0, построим

вспомогательную пару векторов (2*1, Н) такую, что

- __ Г а», 1 < г < п, ~ \а,п + 1 ^ г ^п + щ]

Ъ = X (1-Ю)

О, т + 1^.7 < 771 + 7711,

где ап1 = Ьт1 = <5(А, В; с) и а < тт(ап, с, 1), Ъ < тт(6т, с, 1). Пара векторов (2*1, 22") позволит построить пару векторов (22, В) с наибольшими суммами координат, удовлетворяющую теореме 8.

Лемма 4 . Пусть (А, В) 6 и Г(А, В; с) = 0, где с > 0. Тогда для

пары векторов (Р1, В), построенной по правилу (1.10), имеет место Г(Р, Н] с) ф Ф 0, причем 6к* (Р1, Н; с) = 0, где к* = к* (А, В; с).

Доказательство. Применим ХФ (1.1') и (1.1) для пары (Р, 22") при а) 1 <

к

а) Я"; с) = сЫ* СНГ; с) + ^ = сЫк(В; с)+

3>1к{Н\с) г=1

к

+ Е ^ + -У^а^ = Д;с) + Ьт1 = ^(А,В;с) + <У(А,В;с) =

3>1к{В-,с) ъ=1

= 5к(А, В;с) — 5к* (А, В; с) ^ 0, и очевидно, что 5к* (Р1,22"; с) = 0;

ттг+тпх А; т

^'=1 г=1 э=1

п т п

~~ Е ^ ^ сп)—В; с)+

Ън^ск г=1 3 = 1 Ъ^сп г=1

+а(к -п) = дп(А, В; с) — 4* (А, В; с) + а(к - п) > 0. Из теоремы 2 следует, что (Р, 22") - с-реализуемая пара векторов.

Лемма 5. Для любой пары (А, В) Е существует пара

(А7, В') = ((а!,..., О, (6!,..., О Е где (А', В') < (А, В),такая, что

Г(А',В'-,с)ф0и

п п т т

Е< = Е<н - А Е ^ = Е ьз - А с))'

г=1 г=1 з=1 з=1

причем 6к* (А', В'; с) = О, если Г(А, Б; с) = 0, где /с* = к* (А, В; с).

Доказательство. При Г(А, В; с) ф 0 утверждение очевидно, так как в этом случае 6(А, В] с) = 0 и (А', В') = (А, Б). Пусть Г(А, В; с) = 0. Если с = О, то утверждению леммы удовлетворяет только пара нулевых векторов. При с > 0 рассмотрим пару векторов (.Р, Д-) леммы 4, в которой показано с) ^ 0. Пусть .НГ) = (¡г^) - произвольная двудольная сеть (матрица) из Г(Р, с) с долями и(п) и и иУ(т) и V, где и = {мп+ъ • • ■»ип+п1], V = {ут+11... ,ут+ТП1}. Для этой сети применим характеристическое уравнение (1.6) при к* = к*(А, В; с). Так как 5к- (Р, Н\ с) = 0 (лемма 4), то

¿(и?, V?) + 6(и$* и и,У£* и V) = 0, (1.11)

где V?* = {^1,.. • , }, = {У1к,+1,..., Схематически на рис. 1 представлено /с*-разбиение множества узлов сети ТУ).

Рис. 1

Из равенства (1.11) следует:

а = Ои = с\Щ*\ • Поэтому для рассматри-

ваемой сети Х(1Р1 Н) имеет место х^ = сУ1,з, где 1 < г < к*, 1 ^ 3 ^ 1к* = = 1к*{Н\ с);

б) 5{Щ* и и, V.и V) = 0 и для сети Н) справедливо хц = 0 Уг, з, где к* + 1 < г < п + пх, + 1 < 3 < т + т1-

Из пп. а и б для сети Н) получаем: если Хц > 0, где г > к*, то з < , а

если Хц > 0 при з ^ 1к* + 1, то г < к*. Следовательно,

тг+п 1 к* т-\-тп\

Е ^Хц = апх = 6(А,В-,с), Е Хц =Ъгп1 = 6(А,В-,с),

г=п+1 ^'=1 г=1 ,7=т7г+1

т.е. все дуги с положительными весами, инцидентные узлам из С/, инцидентны только узлам из У^ , а все дуги с положительными весами, инцидентные узлам из V, инцидентны только узлам из . Удалим из рассматриваемой сети Х(1Р, Н) 6 £ Г(Р, Н; с) множество узлов 17 и V. Получим подсеть сетиХ(.Р, Н),

порожденную множеством узлов С/(п) и У(га), и пара векторов (А', В') удовлетворяет утверждению леммы 5.

Покажем, что величина 5(А, В; с) есть критическая при построении с-реализуемых пар векторов, вписанных в (А, В).

Лемма б. Пусть (А, В) £ М+' Г(А, В; с) = 0 и (А', В') = ((а;,...,<), (Ь^,..., О £ где (А', В') ^ (А, В), причем

п

п

т

т

< ¿(А,В;с), 53^'<*(А-В;С).

г=1 г=1 ^'=1 ^'=1

Тогда Г (А', В'; с) = 0.

Доказательство. Предположим, что существует (А', В') < (А, В), что

п п

Г(А',В') ^ 0, причем 53 аг ~ 53 = $ < <5(А,В;с). Рассмотрим

г=1 г=1

Х(А',В') = {хц) € Г (А, В] с). Легко видеть, что существуют такие числа а > > 0, Пх € 2 и 6 > О, шх 6 для которых а < шт(ап, 1, с), <Ш1 = 5, иЬ < < тт(&т, 1, с), Ьт\ — 6. Добавим к сети Х(А', В') два множества изолированных узлов и = {ип+1, . . . } и V = {ут+1,..., г;т+т1}. Для таким образом

построенной сети У — (у^) имеет место

ху, 1 ^ г < те, 1 ^ .7 ^ т,

Уч =

О, + 771+1^.7^771 + 7711

/

У =

Ут-З — 1 ^ г ^ п 1 < 3 ^ т

\

У13 = О 1 < 3 ^ т

\

УН = 0 1 ^ г ^ п

2/»^ = О п + 1^г^п + п1

+ 7721 /

Так как а* — > 0,1 ^ г ^ п, — ^ 0,1 ^ ,7 < га,

тг

пг

г=1 г=1 .7 = 1 .7 = 1

и

ап\ = Ът\ = 5, то существует сеть У = (у'ц), 1 < ъ < п + п\, 1 < ] < т + ть

для которой у'ц = 0 при 1 < г < п, 1 < < га, или при п+1<г<п+ пь

га + 1<17<га + ть причем

т

П+П1

^ т/^ = а, п + 1 < г < п + щ, ^ г/^ = Ь^ - 1 < з < га, 3=1 1=п+1

п

т+т\

у'ч = Ь, т + 1 < 3 < 772 + 7711, у'гз = ^ ~ а>И 1 ^ 1 ^ 71'

г=1

Этим построена сеть /

У' =

^ = о

1 < г < п

1 < .7 < 777

\

Угз

п + 1<г<п + 721 1 < .7 < 777

Угз 1 < г < п

777+1^^' <777 +7771

\

^ = О

77+1<г<П + 771 77г+1<^' <777 + 7721 /

для которой ¿(£/(п),У(га)) = 0, 6(11, V) = 0, 8(и, У(т)) = 5, 5(и(п),У) = = 5. Рассмотрим сумму сетей Z = У + У. Сеть Z есть с-реализация пары векторов (А", В"), где

а*, 1 < г < га,

а, п + 1<г<п + п1,

и"

Ъ3 =

< 3 < 771,

Ь, т + 1 < < га + 7771,

т.е. Г(А", В"; с) ф 0. Применим ХФ (1.17) к паре векторов (А", В") при к*

= к* (А, В] с):

к*

(А", В"; с) = (В"; с) + ^ - ^ а'! = ск*1к. (В; с)+

Э>1к*{В"-,с) i=l

+ Е ^ + Ьт1-^2а{ = 5к*(А,В;с) + д = д-д(А,В-,с) <0,

3=1к*(В"-,С) +1 г=1

что противоречит Г (А", В" ; с) ф 0 (теорема 2). Лемма 6 доказана и доказана теорема 8.

Перейдем к доказательству теоремы 9. Для этого вернемся к леммам 4 и 5. Пусть

. ттъ

(А, в) е и Г(А, В; с) = 0, где с > 0. Рассмотрим пару векторов

(Р, Н) из леммы 4, координаты которых удовлетворяют (1.10). Было показано, что 8к (Р, Н; с) ^ 0 У к и 6к* Н\с) = 0 (лемма 4).

В доказательстве леммы 5 было показано: еслиХ(.Р, Н) = (х^) - произвольная сеть из Г(.Р, Н; с), то ¿(С/^ , ) = с\ик \ • |У/2 | и 5(Щ* и и, ^ иУ) = 0, где = {«!,...,«*.}, V?* = = =

= У(тп)\У1к*, и

X(F,H) =

(

Xij

l^i^k* l^i^k*

h* + 1 < j ^ m + mi

X{j — 0

k*

1 ^ j < ¿fc* h* + 1 ^ i ^ m + mi

\

\

Поэтому для векторов из пар (.F, ii) и (A, J5) следует

щ ^ clk*, 1 < г ^ A;*; bj ^ ск*, 1 < j < ; a>i ^ clk*,i > к*; bj < ck*,j > lk*.

(1.12)

Так как 5k*(A,B-,c) = ck*lk* + 53 fy ~ УЗ ai < 0 и ^(A B;c) =

j>h*

= -5k* (A, 2?; с), то

г=1

Y^di = ck*lk* + 53 +

г=1 j>lk*

(1.13)

Рассмотрим пару векторов (АаА, Вав), где а а = ад (А, В; с), ав = = ав (А, В; с) (см. (1.9)). Пусть qvir- последние индексы уменьшаемых координат соответственно векторов А и В при переходе к паре (АаА, Вав): q = тах{г : а* >

> ад}, г = max{j : bj > ав}- Очевидно, что

q

Q = S(A,B;c),

г=1 г

^bj-aB-r = 5(А, В; с). (1.14)

3 = 1

Лемма 7 . Для пар векторов (А, В) и (АаА, JBas) имеет место: а) к* = к* (А, В\ с) ^ q и б) 1к* = 1к* (В; с) ^ г.

q к*

Доказательство, а) Предположим, что к* < q. Тогда ^Г^д^ = ^^а^ +

¿=1 г=1

q

+ ^^ aj и из (1.13) и (1.14) следует i=fc*+l

q

5(А,В',с) + ал • q = ck*lk* + bj + S(A,B;c) + ^ ац

j>lk* i=k*+1 q

ck*lk* -f ^ bj + щ — aA • q = 0. (1-15)

z = fc* + l

Так какад = aA 'к* + ад (q — k*), то равенство (1.15) можно представить в виде

q

k*{clk* -аА)+ bj+ Y1 (<к~<*А) = 0. (1.16)

j>lk* г=к*+1

Из определения числа q следует, что ai > а а при г < q, а из (1.12) следует aq < (по предположению к* < q) и а а < clk*. Поэтому левая часть (1.16) строго положительна, что противоречит указанному равенству и предположению к* < q. Итак, показано к* ^ q.

б) Если предположить г > 1к*, то учитывая (1.14), из (1.13) получим

г к* г

ск*1к* + + Е^з ~ аг + - ав - Г = 0.

3=1к*+1 «=1 3=1

Применяя тождество ав • т = ав ' 1к* + ав(г — 1к*)> последнее равенство примет вид

г гп к*

1к* (ск* -ав)+ ^2 (Ьз ~ ав) + Е ~~ Е = (1Л7)

5=1**+1 3 = 1 г=1

По определению числа г имеем > а в при у < г, а из (1.12) следует bj < ск* при > 1к* и ав < ск*, так как ав < Ьг. Этим показано, что первые два слагаемых из

т к*

(1.17) строго положительны. А так как ^2 Ъ^ ^ ^^ бц, то левая часть (1.17) больше

¿=1 ¿=1

нуля. Из этого противоречия следует, что г < .

Покажем, что 5к(АаА, Вав;с) ^ 0 У к, 1 < к < п. Этим теорема 9 будет

доказана.

Для к ЕХ рассмотрим два случая:

от 7Т2>

Лемма 8 . Если (А, В) € и Г (А, В; с) = 0, то дк(АаА, Вав\ с) ^ 0 У/г, 1 < к < д.

Доказательство. Воспользуемся леммой [25-27,29,56].

■ ц уд

Лемма 9. Пусть (А, В) 6 _ и ар = ад, где д — р = 2, причем 6р(А,В-,с) ^ 0 и 5д(А,В;с) ^ 0. Тогда 5к(А, В; с) ^ 0 Ук,р < к < д.

Отметим, что для вектора Аад имеет место = ... = и покажем, что

а) 5д{АаА, Вав; с) ^ 0 и б) 61 (.А°а , Вав; с) > 0 (при д ^ 2).

ч

о)дд(АаА,Вав',с)=сд1д(Вав;с)+ ^ - ^ Из лем-

3>1ч{Вав -с) г=1

мы 7 следует неравенство 1д(В\ с) ^ г = тах{^' : bj > ав}- Поэтому

^(Аал,Вав;с) = сдгд(В;с)+ ^ Ьй - аА • д. (1.18)

¿>1,(В;с)

Следовательно, 6д(АаА, Вав; с) = сд1д(В; с) + 53 ~ 53

3>1ч{В-,с) <=1

+<*(А, В; с) = 5д(А, В; с) + ¿(А, В; с) > (А, В; с) + ¿(А, В; с) = 0.

б) Предположим, что 61 (АаА, Вав; с) = с/1 (Вав; с)+ + 53 - с*А < 0. Тогда

3>1\{ВаВ ;с)

с* А > (Вав; с) + 53 (Ы9)

С этим предположением рассмотрим 5д(АаА, Вав; с): учитывая (1.18) и (1.19), получим 5я{АаА,Вав;с) < сд/д(В;с) + 53

3>1д{В-,С)

/ \ *х(В;с)

- с/1(В;с)+ 53 Ы^-сд(11(В;с)-уВ;с))+ 53 Ьй-

\ 3>к(В-,с) ) з=1ч{В-,с)+1

¿1(В;с)

-!) 53 = 53 ~- (я -1) 53 ^ Так как

¿>*х(В;с) ¿=^(В;с)+1 ¿>*1(В;с)

53 — сд) ^ 0 и (д — 1) 53 ^ 0 (см. определения чисел д и

¿=/д(В;с)+1 Э>1г{В-,с)

1д(В] с)), то 5д(АаА, Вав; с) <0, что противоречит п. а. Из леммы 9 следует, что 5к{АаА,Вав-,с) ^ 0У/с, 1 ^ /с ^ д.

Лемма 10. Если (А, В) € М+™ и Г(А, В; с) = 0, то 6к(АаА, Вав; с) ^ 0 У к, д < к ^ п.

Доказательство. Рассмотрим

Список литературы диссертационного исследования кандидат наук Селин, Павел Сергеевич, 2014 год

Список литературы

1. Басакер Р. Саати Т. Конечные графы и сети. М.: Наука, 1974.

2. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320 с.

3. Гольдштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. 382 с.

4. Давыдов Г.Б., Рогинский В.Н., Толчан А.Я. Сети электросвязи. М.: Связь, 1977.

5. Ершов В.А. Коммутация на интегральной цифровой сети связи. М.: Связь, 1978.

6. Емеличев В.А,, Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

7. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969.

8. Клейнрок Л. Коммуникационные сети. М.: Наука, 1970.

9. Кононенко A.M., Трухановский H.H. О транспортных многогранниках с максимальным числом вершин // Изв. АН БССР, сер. физ.-матем наук. 1978. N5. С. 23-25.

10. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

И. Кузнецов A.B., Сакович В.А., Холод H.H. Высшая математика. Математическое программирование. Минск: Высшая школа, 1994. 288 с.

12. Мизин И.А., Уринсон Л.С., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений. М.: Связь, 1972. 319 с.

13. Миронов A.A. О реализуемости множества целых неотрицательных чисел степенями вершин графа//Тр. МИИТа. 1976. Вып. 510. С. 68-77.

14. Миронов A.A. Геометрия точек пространства Rn , реализуемых в граф // УМН. 1977. Т. 32. N6. С. 231-232.

15. Миронов A.A. Некоторые свойства наборов чисел, реализуемых в граф // Тр. МИИТа. 1979. Вып. 640. С. 115-120.

16. Миронов A.A. О реализуемости наборов чисел в граф и свойства графов с заданным набором степеней // Тр. Гор. ГУ, 1981. С. 76-97.

17. Миронов A.A. О свойствах наборов степеней вершин обобщенных графов // ДАН.

1992. Т. 342. N 5. С. 959-963.

18. Миронов A.A., Цурков В.И. Сетевые модели с фиксированными параметрами на узлах связи I // Изв. РАН. Техн. кибернетика. 1993. N 4. С. 212-223.

19. Миронов A.A., Цурков В.И. Сетевые модели с фиксированными параметрами на узлах связи II // Изв. РАН. Техн. кибернетика. 1993. N 6. С. 3-14.

20. Миронов A.A. Обобщенные графы с ограничениями для степеней вершин // ДАН.

1993. Т. 333. N4. С. 437-439.

21. Миронов A.A., Цурков В.И. Класс распределительных задач с минимаксным критерием // ДАН. 1994. Т. 336. N 1. С. 35-38.

22. Миронов A.A., Цурков В.И. Транспортные и сетевые задачи с минимаксным критерием//РАН. Ж. вычисл. мат. и мат. физ. 1995. Т. 35. N 1. С. 24-45.

23. Миронов A.A., Цурков В.И. Транспортные задачи с минимаксным критерием // ДАН. 1996. Т. 346. N2. С. 168-171.

24. Миронов A.A. Задачи транспортного типа с минимаксным критерием // А и Т. 1996. N12. С. 109-118.

25. Миронов A.A., Цурков В.И. Минимакс в транспортных задачах. М.: Наука, 1997.

26. Миронов A.A., Цурков В.И. Наследственно минимаксные матрицы в моделях транспортного типа // Изв. РАН Теория и системы управления. 1998. N 6. С. 104-121.

27. Миронов A.A., Цурков В.И. Открытые транспортные модели с минимаксным критерием // ДАН. 2001. Т. 381. N4. С. 448-451.

28. Миронов A.A. Выпуклые многогранники в задачах оптимазации на сетях // РАН. Ж. вычисл. мат. и мат. физ., 2002. Т. 42. N 5. С. 729-740

29. Миронов A.A., Цурков В.И. Замкнутые транспортные модели с минимаксным критерием // А и Т. 2002. N 3. С. 50-61.

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

31. Миронов A.A., Соколов A.A., Цурков В.И. Алгоритм построения наследственно минимаксной матрицы классического транспортного многогранника // Тр. ИСА РАН. Динамика неоднородных систем. 2006. 10(1). С. 43 - 46.

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

33. Миронов A.A. Взвешенные графы с фиксированными степенями вершин и потоки в сетях // Изв. РАН Теория и системы управления. 2007. N 3. С. 1-4.

34. Ope О. Теория графов. М.: Наука, 1968. 353 с.

35. Рогинский В.Н., Харкевич А.Д., Шнепс М.А., Давыдов Г.Б., Толчан А.Я. Теория сетей связи. М.: Радио и связь, 1981. 192 с.

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

37. Селин П.С. Ограничения при обмене информацией в сетях с петлями с фиксированными степенями узлов // Тез. докл. Междунар. молодежной научн. конф. «XXXII Гагаринские чтения» 2006. Т. 5. С. 68-70.

38. Селин П.С. О достижимости оценок в потоковых задачах на классах сетей с петлями и без петель с фиксированными степенями узлов. // Научн. тр. Междунар. молодежной научн. конф. «XXXIV Гагаринские чтения» 2008. Т. 5. С. 100-102.

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

40. Триус Е.Б. Задачи математического программирования транспортного типа. М.: Современное радио, 1967. 208 с.

41. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

42. Хакими С.Л. О реализуемости множества целых чисел степенями вершин графа // Кибернет. сб. нов. сер. Вып. 2. М.: Мир, 1966.

43. Харари Ф. Теория графов. М.: Мир, 1973. 300 с.

44. Хачатуров В.Р., Монтлевич В.М. Решение нелинейных производственно транспортных задач с неделимыми потребителями. М: ВЦ АН СССР, 1987. 24 с.

45. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 520 с.

46. Шнепс М.А. Система распределения информации. Методы расчета. Справ, пособие. М.: Связь, 1979.

47. Эрдеш П., Галлаи Т. Графы с заданными степенями вершин // Mat. Lapok, 11.1960. P. 264-274.

48. Ford L.R. Network Flow Theory. The RAND Corp., 1956. 923 p.

49. Goldsmith A. Wireless communications. Cambridge university press. 2005. 571 p.

50. Gomory R.E. Ни T.C. Multi-terminal Network Flows // J. Soc. Ind. Appl. Math, 9. 1961. P. 551-570.

51. Gomory R.E. An algorithm for integer solutions for linear programs, in recent advaces in mathematical programming // Mc Graw Hill. 1963. P. 269-302.

52. Lewis F.L. Wireless sensor networks // Smart Environments: Technologies, Protocols, and Applications. John Wiley. New York. 2004.

53. Hu T.C. Multi-commodity Network Flows//MIT Interim Tech. Rept. 8. 1958.

54. Kuhn H.W., Tucker A.W. Nonlinear programming in J. Neyman // (ed.) Proceedings of the second berkley symposium on mathematical statistics and probability. Berkley: Uneversity of California Press. 1951. P. 481-492.

55. 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.

56. Tsurkov V., Mironov A. Minimax under transportation constrains. Dordrecht/Boston/London: Kluwer Academic Publishers, 1999.

57. Hitchcock F.L. Distribution of a product from several sources to numerous localities // J. MathPhys. V. 20. 1941. P. 224-230.