Технологии программирования задач сетевой оптимизации

Рассмотрим цикл , порожденный дугой . Определим направление обхода цикла в соответствии с направлением дуги , которая является прямой.

Определение 1.2.3. Дуга , где фиксировано, называется прямой дугой цикла , если направление дуги совпадает с направление дуги в цикле. Аналогично дуга , где фиксировано, называется обратной дугой цикла , если направление дуги противоположно направлению дуги в цикле

Обозначим знак дуги в цикле через :

 

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

Приведем конструктивное определение характеристического вектора, порожденного некоторой дугой.

Определение 1.2.4. Характеристический вектор, порожденный дугой относительно покрывающего дерева , есть вектор , где фиксировано, построенный по следующим правилам:

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

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

 

Примеры характеристических векторов, порожденных дугами  , на рисунке 2:

 

 

Рисунок 2. – Характеристические векторы

 

В двух следующих леммах приводятся основные свойства характеристических векторов.

 

Лемма 1.2.1. Характеристический вектор , порожденный дугой , где фиксировано, является решением однородной системы

 

 

Доказательство. Определим некоторую опору сети S для системы Для фиксированного рассмотрим множество , которое по теореме 1.2.2 является покрывающим деревом сети , и – единственный цикл сети , полученный в результате добавления дуги ко множеству дуг.

Рассмотрим вектор , компоненты которого являются неизвестными системы 

Положим . Система имеет вид

 

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

Полагая для уменьшенной системы (9), легко определяем значения остальных неизвестных :

 

Алгоритмически, положив , проходим от узла к узлу по дугам цикла , последовательно устанавливая значения соответствующих неизвестных равным знакам дуг цикла . Направление в цикле определяется дугой , которая его порождает и является прямой. Заметим, что построенный вектор удовлетворяет всем условиям определения 1.2.4 характеристического вектора, порожденного дугой , и, следовательно, = – решение однородной линейной системы (8). Лемма доказана.

 

Пример разрешения системы вида с помощью характеристического вектора на рисунке 2:

 

 

Рисунок 3. – Вычисление характеристического вектора решением системы (8)

 

 

          

Рисунок 4. – Вычисление характеристического вектора с использование таких структур данных, как

pred[i]   – список предков  узлов дерева;

dir[i]    - список направления  дуг дерева;

thread[i] – список индексов связи  узла дерева (династический обход);

 

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

Доказательство. По лемме 1.2.1 каждый характеристический вектор является решением системы (8).

Согласно теореме 1.2.2, для фиксированного множество – покрывающее дерево сети ,  следовательно, . Таким образом, число характеристических векторов во множестве равно.

Докажем, что векторы множества линейно независимы. Каждый характеристический вектор  , порожденный некоторой дугой, всегда имеет хотя бы одну  компоненту, соответствующую дуге из множества , которая равна 1. Эта компонента, равная 1, соответствует дуге , которая порождает этот вектор. Все остальные компоненты, которые соответствую дугам , равны нулю 0. Это означает, что два любых характеристических вектора, порожденных различными дугами,  линейно независимы.

 

Теорема 1.2.3. Общее решение системы для фиксированного может быть представлено в следующем виде:

 

   

где – любое частное решение неоднородной системы – независимые переменные, соответствующие дугам .

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

 

как сумму общего решения однородной системы и некоторого частного решения неоднородной системы (5); – коэффициенты линейной комбинации характеристических векторов в (11).

Представим (11) в компонентной форме:

 

                            (13)

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

 

Замечание . На практике при построении частного решения системы будем полагать , и решаем систему

 

Таким образом, формула принимает вид:

 

 

В дальнейшем будем использовать формулу

 

Рисунок 5. – результат поиска частного решения средствами языка Java

Рисунок 6. - результат поиска частного решения средствами Wolfram Mathematica

1.3. Декомпозиция системы

Пусть – некоторая опора сети S для системы . Определим  множество циклических дуг , выбрав произвольных дуг из множества . Определим – множество дуг, которые не входят в опор и не входят во множество циклических дуг

Подставим общее решение системы для каждого в

 

 

 

 

 

Изменим порядок суммирования в

 

 

 

 

В уравнениях (16) сгруппируем переменные, соответствующие множествам :

 

 

 

 

Определение 1.3.1. Назовем число

 

детерминантом цикла , порожденного дугой относительно уравнения с номером p системы

 

Рисунке 7. – Вычисление детерминантов циклов

 

 

Обозначим

 

 

 

Рисунок 8. – Вычисление

 

Уравнения согласно , примут вид:

 

 

В сгруппируем переменные, соответствующие множествам

 

Применим аналогичные рассуждения к системе  Заметим, что систему  можно рассматривать как частный случай системы с , равными 0 или 1.

Для каждого подставим общее решение системы в уравнение :

 

 

или

 

Заметим, что для каждой дуги , которая порождает цикл , выполняется равенство:

 

где

                            

 

Таким образом, уравнения примут вид

 

где

 

Пример вычисления на рисунке 7:

 

Рисунок 9. – Вычисление

 

В (25) сгруппируем переменные, соответствующие множествам

 

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

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

      (28)

где подматрица размера подматрица размера , – вектор неизвестных, компоненты которого упорядочены в соответствии с нумерацией .

Правая часть системы имеет вид:

                                    (29)

 

 

Пример вектора и матриц и на рисунках 8 и 9:

 

 

Рисунок 10. – Вычисление вектора и матрицы D для решения уравнения вида

 

Рисунок 11. – Вычисленный вектор и матрица D

 

В случае невырожденной матрицы из (1.3.14) находим искомые неизвестные соответствующие множествуциклических дуг:

. (30)

 

 

Рисунок 12. – вычисление вектора неизвестных средствами Wolfram Mathematica

 

Рисунок 13. – вычисление вектора неизвестных согласно формуле

 

Рисунок 14. – Значение вектора неизвестных, вычисленного средствами Wolfram Mathematica и по формуле совпадают

 

Замечание 1.3.1. В общем случае, из-за произвольного выбора дуг множества , невырожденность матрицы не гарантируется. В случае, если необходимо выбрать другие дуги в состав множества и заново вычислить системы (1.3.14).

Обозначим Представим (30) в компонентной форме

 

Таким образом, определены все неизвестные системы (1) – (3):

 

 

 

 

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

 

Рисунок 15. – Общее решение системы (1) – (3)

 

Кратко изложим наиболее важные аспекты метода. Хотя строгие оценки сложности алгоритма здесь не рассматриваются, следует обратить внимание на то, что описанный подход осуществлен на надлежащих структурах данных, что ведет к эффективному алгоритму: часть вычислений выполнена на небольших подмножествах дуг, например на изолированных циклах или покрывающих (остовных) деревьях . использование сетевой структуры ограничений позволяет выполнить декомпозицию опоры, и, следовательно , декомпозицию системы, и, наконец,  выполняется обращение матрицы размера, намного меньшего ,чем размер исходной системы кроме этого, независимые результаты, полученные для каждого типа потока k из множества K, например теорема 1.2.2, леммы 1.2.1 и 1.2., формулы дают возможность строить решения больших недоопределенных систем линейных уравнений в параллельной среде.

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

 

 

Часть 2

 

1. Разреженные недоопределенные системы (обобщенная сеть)

2.1. Общий вид недоопределенной  системы (обобщенная сеть)

 

Пусть – конечная ориентированная связная сеть без кратных дуг и петель, где множество узлов и  – множество дуг, определенных на , . Пусть ).  – множество различных продуктов, транспортируемых по сети . Без ограничения общности введем множество Обозначим связную сеть, соответствующую типу потока через   , – множество дуг сети . Определим множества и типов потоков, транспортируемых через узел и дугу соответственно.

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

Сеть   может быть представлена в виде объединения сетей ,где .

Рассмотрим линейную недоопределенную систему вида:

 

 

 

где ,, параметры системы, . Условия существования решения системы (2.1.1) следуют из теоремы Кронекера-Капелли [15].

Предположим, что . В дальнейшем будем называть сетевой частью и дополнительной частью системы

 

Матрица системы имеет следующую блочную структуру:

       (4)

Здесь М – блочно-диагонального матрица размера , каждому блоку с номером которой соответствует матрица размера и сеть , Каждый столбец матрицы соответствует дуге   сети , и отличными от нуля элементами указанного столбца являются два элемента: элемент строки с номером , равный 1, и элемент строки с номером , равный . - матрица с элементами ; одматрица, состоящая из нулей и единиц, где все ненулевые элементы соответствуют дугам .

 

2.2. Сетевая часть системы

Теорема 2.2.1. Ранг матрицы системы для сети равен .

Доказательство. Поскольку матрица M системы (1) имеет вид где – диагональный блок матрицы M,  и rank то выполняются соотношения:

 

Теорема доказана. 

Замечание 2.2.1. Предположим, без ограничения общности, что ранг матрицы А системы  равен

Поскольку матрица системы имеет блочно-диагональную структуру, мы разбиваем систему на независимых систем, каждая из которых соответствует отдельному блоку для фиксированного и имеет следующий вид:

 

 

2.2.1. Критерий  опорности обощенной сети

Определим опору сети для системы

 

Определение 2.2.1. Опорой сети   для системы (2.1.1) назовем множество дуг для которого система

 

имеет только тривиально решение для , но имеет нетривиальное решение для множества дуг , 

 

Сформулируем сетевой критерий опорности.

 

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

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

 

 

2.2.2. Характеристические  векторы

Введем в рассмотрение характеристический вектор, , порожденный дугой относительно опоры где фиксированно, компоненты которого являются решение следующей системы:

 

 

  

Определение 2.2.2. Совокупность  дуг назовем бициклом, порожденным  дугой относительно опоры .

Проанализируем структуру сети, полученную в результате добавления дуги , где фиксированно, к опоре . Поскольку опора сети для системы – это объединение связных компонент , каждая компонента связности содержит единственный невырожденный цикл [5,6,18,19], то в результате добавления дуги , где фиксированно, к опоре будет получена сеть, структура которой подробно описана в [18].