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

В работе [1, 12-13] рассмотрена тензорно-геометрическая постановка задачи и методы поиска решения оптимальной структуры сети на примере транспортной задачи, тензорногеометрическая интерпретация описания [11], построения и решения сетевой транспортной задачи показана в работах [2-6], тензорная интерпретация критериев оптимальности [7]. Для прямой задачи f(x) = Cj x^j -> min приведена последовательность действий для поиска оптимального решения:

том 17 № 3 (52), 2021, ст. 3

• 1.    Задание уравнений связи, формирование матрицы прямого преобразования Aj ;

• 2.    Задание допустимого распределения потоков на сети – определение независимых и

• базисных элементов;

• 3.    Формирование матрицы перенумерации S. для изменения порядка элементов (независимые; базисные);

• 4.    Вычисление    перенумерованной    матрицы    прямого    преобразования

• ^a Ji             ;

• 5.    Вычисление значений потоков на сети в перенумерованном базисе X¹¹ = WJ"¹ ^ ;

• 6.    Вычисление стоимости транспортировки в перенумерованном базисе ^C41 ~ \i^ck ;

• 7.    Вычисление целевой функции /to = C._Z1X, ;

• 8.    Проверка оптимальности найденного решения – есть ли С_Л1 < U, где ^CI1 ^{=      c}41 . Если среди ^Л1 нет отрицательных значений, то найденное решение

• 9.    Выбор кандидата на ввод в базис - MINQc^ < 0) – минимального из отрицательных значений. Ввод выбранного элемента в базис;

• 10.    Выберем в качестве кандидата на вывод из базиса переменную, которая имеет максимальное значение среди всех отрицательных - MAX (x^¹< 0);

• 11.    Вывод выбранного элемента из базиса. Возврат к шагу 3.

7 n

является оптимальным, в ином случае – переходим к п.9;

Здесь и далее: m – число узлов; n – число ветвей; M = m - 1 - число базисных переменных; N = n - M - число независимых переменных; sj.k,l= (l,n)

A, [4= (1,7V); K,h = (7V + 1,7V + M) ; цифровой индекс - номер итерации; (.) - символ обозначающий объекты с упорядоченным координатным базисом.

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

том 17 № 3 (52), 2021, ст. 3

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

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

f(x) = Cj xj -> min(1)

A” xJ = b*(2)

xj < Wj(3)

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

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

(то есть, уравнений связи наложенных на сеть, и, следовательно, структуры сети) и значения внешнего потока ^У7 , то снизить xj возможно следующими способами:

• 1.    Снижением значения внешнего потока ^7 , что приведет к уменьшению нагрузки на

• 2.    Управлением структурой сети с целью поиска структуры, обеспечивающей максимально близкое к оптимальному распределение потоков с учетом (3).

сеть, но не позволит доставить всю передаваемую информацию потребителям;

том 17 № 3 (52), 2021, ст. 3

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

Рис. 1. Фрагмент сети

Таблица 1. Параметры сети

Стоимость транспортировки по ветви	С1	Сд	=8
	10	10	10
Внешний поток	ь1		ья
	200	0	200
Налагаемое ограничение	IV1	w-	IVа
на пропускную способность	100	100	100

Для данной сети m = 3 – число узлов; n = 3 – число ветвей; M = m - 1 = 2 - число базисных переменных; N = n - M = 1 - число независимых переменных.

Уравнения связи для узлов сети:

Д—х1 -х2 + b1 = О или

А-х¹ -х² = —Ь¹

В: х² -X³ = Ь²

С; х1 + х3 = Ь3

В; х² -х³ - b² = О

С; х¹ + х³ - Ь³ = О

Число независимых уравнений M = 2, следовательно, одно из уравнения связи можно исключить, пусть это будет уравнение для узла С.

Тогда, матрица прямого преобразования примет вид:

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

том 17 № 3 (52), 2021, ст. 3

Рис. 2. Базисное решение

Независимые переменные: х^А = {х²}, Базисные переменные: X^х = {х^х³}.

Упорядочим последовательность переменных

z1	xL	X?	z3
xi	x2	z1	Iя
si	5; = 1	5L2 =	.     5| = .

Матрица перенумерации будет иметь следующий вид:

О 1 О

1 О

о о

О 1

Тогда, матрица прямого преобразования координат нового представления потокового вектора и старого, но имеющего другой произвольный порядок обозначения будет иметь вид [1]:

AS _ с/

Получаем следующую структуру:

, где – символ Кронекера.

о о

-1

Значения потоков в новой системе координат (СК): %р — ^л ^-

Следовательно, в перенумерованной исходной СК значения потоков можно высчитать по формуле [1]:

= R'$1vS= R^

• X. = d₅ Хф =

где B^s — (^л)   — матрица обратного преобразования:

том 17 № 3 (52), 2021, ст. 3

1-1

о

о

-1

о

о о -1

о

-200 О

О

200 О

Стоимость транспортировки в перенумерованном базисе:

0 10

c.u = S^c_k= 1 О О |10 10 10| = |10 10 10|

0 0 1

Значение целевой функции:

о

Лех W= с^' = с₄₁х^и = 110 10 10| 200 = 2000

О

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

решения):

=\<о cS = G-tf)"1^ = |10|

Условие (6) не выполняется, следовательно, кандидаты на ввод в базис отсутствуют, и найденное решение является оптимальным по критерию минимизации.

Значения потоков в исходной СК вычислим по формуле: x^j = (Sj^x^¹

О 1

х^ = 1 О 0 200

О О

О О

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

b 3= 200

x = 0

x 1= 200 c =10

/A

b1 =200

том 17 № 3 (52), 2021, ст. 3

Выполнив проверку ограничения (3) мы видим, что для ветви 1 имеет место быть перегрузка          >             Для ограничения пропускной способности проведем замену ветви 1 на имитацию узловой пары:

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

• обеспечит при работе алгоритма поиска оптимального решения по критерию минимизации использование данной ветви в последнюю очередь;

• 2.    Откорректируем значения внешних потоков для узлов, примыкающих к преобразуемой ветви – представим, что поток значением численно равным выводится в узле, где от которого начинается ветвь 1 (A) и заново вводится в узле, к которому данный приходит данная ветвь (C) : '.’" = с’" ^_ .  ", с’." = с’" ^_ .. ", т.е.

• 3.    Запомним, что в исходной СК ограничен поток по ветви 1:          ;

• 4.    Откорректируем значение ограничения для ветви 1:         .

имитируем, что поток значением численно    был передан по ветви 1;

(‘) – символ, обозначающий объекты с введенными ограничениями.

Внесенные изменения в параметры ветви 1 аналогичны используемому Г. Кроном [9] преобразованию ветви в узловую пару: когда ветвь, по которой протекает контурный ток , раскрывается, эта частная контравариантная переменная обращается в нуль. Вместо нее возникает другая переменная, которая, однако, является ковариантной, а именно, разность потенциалов на открытой ветви. Во время добавления и устранения связей структура динамической системы не изменяется, а наличие связей только изменяет относительное число ковариантных и контравариантных переменных, сумма которых при этом остается постоянной.

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

Электронное научное издание «Устойчивое инновационное развитие: проектирование и управление» www.rypravlenie.ru том 17 № 3 (52), 2021, ст. 3

ограничение. При следующей итерации потоковая переменная перейдет из базисной в независимую (т.к. стоимость транспортировки по данной ветви станет огромной по сравнению с альтернативными маршрутами), что выполняется при использовании матрицы перенумерации , которая вызовет преобразование матрицы в соответствии с (4).

Рис. 4. Схема сети после внесения искусственных ограничений для компенсации перегрузки

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

Таблица 2. Параметры сети после введения искусственных ограничений

Стоимость транспортировки по ветви	С1	С2	са
	10	10	10
Внешний поток		ь?
	100	0	100
Налагаемое ограничение по			№а
пропускной способности	0	100	100

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

,  перенумерации

Следовательно, матрицы прямого преобразования перенумерованная матрица прямого преобразования      и перенумерованная матрица обратного преобразования     не изменятся.

том 17 № 3 (52), 2021, ст. 3

Тогда потоки на сети: х-1 = SV1

1    О

^ = о   о

о о

-1

о

-100 о

о

100 о

Стоимость транспортировки в перенумерованном базисе вычислим по формуле (5):

С 41 = S4ick =

О

о

1 о о

о о

11010 10 10| = |10 1010 10|

Значение целевой функции:

/(х) = с^¹ = 110 1010

о

10| 100 о

= 101000

Выполним проверку на наличия кандидатов на ввод в базис (6):

с^ = ^)-1^.zl = 1-9901 < О, ^'. является кандидатом на ввод в базис.

Введем данную ветвь в контур. Если постепенно увеличивать значение Л- \ , то ветвям, входящим в контур с положительным знаком необходимо добавлять данное значение, а ветвям с отрицательным знаком вычитать данное значение. Это связано с необходимости балансировки потоков, входящих в образованный замкнутый контур. Поскольку потоки должны оставаться положительными, то мы не можем бесконечно увеличивать л.\ , а только до минимального значения потока X- , имеющих отрицательный знак в    :

О

100 о

В данном случае, кандидатом на вывод из базиса является только поток ^', .

том 17 № 3 (52), 2021, ст. 3

х!² = В-'² by

,

СЧ2 —  -12С'к ~

1-1-1

о

-1-1

о о -1

о

-100 о

о

1 о о

о

о

о о

101=11010 10 10|

о

/(х) = с_Ч2х^? = 11010

10| 100 = 2000

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

7 л решения)         :

^ = (A'i)"*^ = 19901

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

Значения потоков в исходной СК: вычислим по формуле:

х? =

1 о о

о о о

о о

о

о

Рис. 5. Оптимальное решение транспортной задачи по критерию минимизации с наложенными ограничениями

Выполним проверку на выполнения ограничения (3)

О

100 < w^j =

о

Т.к.

ограничение

критерию

минимизации

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

по

не

Устойчивое

инновационное

развитие:  проектирование и управление [Электронный ресурс]

/

гл. ред. А.Е. Петров. – Дубна : 2008-2021. – ISSN 2075-1427. – Режим доступа: http://rypravlenie.ru/

том 17 № 3 (52), 2021, ст. 3

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

^ИОЛН

о

100 о о

Уполн С^) ~ ^/^ПОЛН — |Ю 10

10| 100 = 3000

В результате использования предлагаемого решения найденное значение целевой функции /полнМ = 3000, что превышает значение целевой функции для варианта, без проверки на ограничение пропускной способности /исхМ = 2000. Вместе с тем, /полн С^) учитывает использование резервов и альтернативных маршрутов, что позволяет доставить от отправителя к получателю весь требуемый поток в необходимый момент (см. рис. 6) без необходимости проведения модернизации инфраструктуры, что требуется при использовании исходного распределения потоков на сети (см. рис. 3). Кроме того, в результате проведения модернизации инфраструктуры стоимость транспортировки по элементам сети может значительно увеличиться [10], и найденное значение целевой функции Уисх(^) также возрастет.

b = 200

b 2= 0

x ¹ =100 полы

B x п2олн=100

b1 = 200

Рис. 6. Оптимальное решение транспортной задачи по критерию минимизации с учетом использованных резервов и альтернативных маршрутов

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

Электронное научное издание «Устойчивое инновационное развитие: проектирование и управление» www.rypravlenie.ru                                          том 17 № 3 (52), 2021, ст. 3