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

• Автор: Селин, Павел Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 100 с. : ил.

Оглавление

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

Введение

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]) с фиксированными степенями узлов. Также получены формулы для вычисления минимаксных значений, определяющих необходимые и достаточные условия непустоты рассматриваемых классов сетей, и алгоритм построения наследственно минимаксной“сети.
II. Сети без петель с фиксированными степенями узлов
2.1. Характеристические функции и условия с-реализуемости
Для вектора А Є К” сформулируем критерий реализуемости в сеть без петель [17,18].
Теорема 11. Если А Є К, то Г(А) ф 0 ■<=>■

<=> 2тах{оі : 1 ^ г ^ п} ^ Vа*. (2-1)

Отметим, что в случае целочисленности вектора А (при условии четности суммы координат) этот результат был получен С.Л. Хакими [42].
Построим характеристическую функцию, зависящую от вектора А Є М” и параметра с ^ О, неотрицательность которой есть критерий с-реализуемости (в случае А ЄІ+) [17,18,20,28,30,33].
Определение 9. Для А Є К” , с ^ 0 и к Є Х, 1 ^ к ^ п, характеристической функцией (ХФ) называется
5к(А;с) = ск(к- 1) - (ск-с-сц)- ^ (а* - ск) - ^ а* + а*.
а^^ск — с а^^ск
(2.2)
Неотрицательность ХФ (2.2) есть необходимое условие с-реализуемости вектора в сеть без петель [17,20,28,18,30,33].
Теорема 12 . Пусть А Є К” , с ^ 0. Если Г(А; с) ф 0, то <5^.(А; с) ^ 0 /&, 1 < А: ^ п.
В случае упорядоченности координат вектора по невозрастанию, неотрицательность ХФ (2.2) является необходимым и достаточным условием с-реализуемости [17,20,28,18,30,33,39].
Теорема 13. Если А Є , то Г(А; с) ф 0 <=> 5/с(А; с) ^ 0 /к, 1 ^ к ^