Решение задач назначения целей с использованием тензорной методологии Макарычев Петр Петрович Профессор, доктор технических наук Пензенский государственный университет 440052, г. Пенза, ул. Калинина, д.4, кв. 13 makpp@yandex.ru Безяев Виктор Степанович Кандидат технических наук Советник генерального директора, НПП «Рубин» pm@pnzgu.ru Аннотация: Рассматривается решение задачи о назначениях целей с использованием конструктивного алгоритма и алго- ритма комбинаторной оптимизации. Входные данные, ре- зультаты решения задачи представляются в виде тензоров. След тензора характеризует остаточную угрозу от всего множества целей и рассматривается как глобальная целевая функция. Задача поиска оптимального решения выполняется в два этапа. На первом этапе задача решается с использова- нием конструктивного алгоритма. На втором этапе осу- ществляется комбинаторная оптимизация. Ключевые слова: Цель, средство поражения, тензор, диада, след диады, след тензора, целевая функция, конструктивный алгоритм, алгоритм комбинаторной оптимизации. Solving the task of appointment goals using the tensor methodology Makarychev Petr Petrovich Professor, doctor of technical Sciences 440052, Penza, st. Kalinina, h.4, a.13 makpp@yandex.ru Bezyаev Viktor Stepanovch Professor, candidate of technical Sciences Penza, bezyaev@npp-rubin.ru Abstract: The solution of the target assignment problem using a constructive algorithm and a combinatorial optimization algo- rithm is considered. The input data and the results of the Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 45 problem solution are presented in the form of tensors. The tensor trace characterizes the residual threat from the whole set of tar- gets and is considered as a global target function. The task of finding the optimal solution is performed in two stages. At the first stage, the problem is solved using a constructive algorithm. The second stage is combinatorial optimization. Key words: A goal, a means of destruction, tensor, dyad, dyad trail, the trace of the tensor, the objective function, a constructive algorithm combinatorial optimization. 1 Введение Управление противовоздушной обороной (ПВО) подразумевает решение задачи назначения целей средствам пора- жения. Одним из известных алгоритмов является конструктивный алгоритм [1]. Алгоритм анализирует все подхо- дящие решения и находит оптимальное решение за довольно длительное время. Известно решение задач о назна- чениях методом целочисленного программирования [2]. Алгоритмы целочисленного программирования является NP-сложным, что делает невозможным применение этих алгоритма в режиме реального времени при достаточно большом количестве целей. Количество итераций при решении задачи велико и составляет O ( m !) , где m – коли- чество целей. Ближайшей к задаче назначения целей по постановке является задача назначений. Для решения этих задач реко- мендуется использовать три группы методов. Представителями первой группы являются метод линейного про- граммирования, метод ветвей и границ, венгерский метод [14, 15]. Эти методы относятся к методам математиче- ского программирования и обеспечивают решение задачи о назначениях за полиноминальное время. Сложность алгоритмов реализующих эти методы составляет O ( m 3 ) . Вторую группу представляют методы дискретной оптимизации: метод ветвей и границ, метод динамического программирования [16. 19. 20]. Сложность алгоритмов реализации методов второй группы составляет O ( n 3 ) . Тре- тью группу составляют методы комбинаторной оптимизации [3, 13, 17, 19]. Методы комбинаторной оптимизации основаны на понятии «пространство состояний» [3]. Особенность этих алгоритмов состоит в том, что для снижения вычислительной сложности используются идеи сокращения размерности пространства, разбиения задачи назначе- ния целей на подзадачи [4, 21]. В связи с разработанностью эффективных методов решения задачи о назначениях, представляется возможным задачу о назначении целей разделить на подзадачи. Первая подзадача – назначение целей с использованием кон- структивного алгоритма, сложность которого O(m) . Вторая подзадача – преобразование полученных результатов и постановка задачи о назначениях, которая может быть решена с использованием менее сложных алгоритмов. Третья подзадача - поиск оптимального назначения целей с использованием комбинаторного алгоритма, слож- 2 ность которого O(m ) . 2 Постановка задачи о назначениях целей Рассмотрим постановку задачи комбинаторной оптимизации, которая обеспечивает как сокращение размерности предметного пространства, так и разбиение задачи на подзадачи. Предположим, что имеется множество средств поражения W  w1 ,..., w j ,..., wn  , множество целей C  c1 ,..., ci ,..., cm  . Каждое средство поражения w j имеет g j целевых каналов и может быть назначено на любую цель. Каждая цель ci характеризуется уровнем угрозы U i , i  1, 2,..., m и множеством вероятностей (степеней) поражения: pi   pi ,1 ,..., pi , j ,..., pi , n  , i  1, 2,..., m (1) На основе вероятностей поражения pi   pi ,1 ,..., pi , j ,..., pi , n  для каждой цели формируется множество оценок выживания цели ci : qi  qi,1 ,..., qi, j ,..., qi,n   (1  pi,1 ),...,(1  pi, j ),...,(1  pi, j ) , (2) где xi , j - количество назначенных целевых каналов на цель ci в средстве поражения w j . При этом для каждого средства поражения целей  iI xi , j  O j . j Таким образом, при появлении новой цели для всех средств поражения на основе выражений (1, 2), производит- ся оценка остаточной угрозы, создаваемая при применении того или иного средства поражения, в виде: U ( ci )  (U i qi ,1 ,..., U i qi , j ,..., U i qi , n ) . 46 Формализованная постановка задачи о назначениях целей методом целочисленного программирования может быть выполнена в виде: F ( X)   i 1  j 1U i qi , j X j ,i  min , m n (3) где X - неизвестный тензор назначения целей размерности n  m . Задача решается при следующе системе ограничений: X × H  L, LT  X  Q  H T , X j , i  0 , H   hi  , hi  1, i  1, 2,..., m ; L   l j  , l j  O , j  1, 2,..., n где Q - количество целевых каналов средств поражения . Для Q  3 и m  9 тензор остаточных угроз A может быть задан в следующем виде: c1 c2 c3 c4 c5 c6 c7 c8 c9  1,3 2,5 4,1 1, 4 3,3 4,1 2,9 5,3 2, 4  w1 (4) A  U i qi , j    2,5 2,1 2,3 2, 2 3, 7 5, 6 5, 2 3,5 5,1  w2 T T 3, 7 1, 2 3,1 2, 7 4,3 4, 7 5, 8 2,5 3, 4  w3 Решением задачи о назначении целей является тензор: c1 c2 c3 c4 c5 c6 c7 c8 c9 1 0 0 0 0 0 1 0 1  w1 . (5) X  0 0 1 1 1 0 0 0 0  w2 0 1 0 0 0 1 0 1 0  w3 При этом решение является оптимальным, а величина остаточной суммарной угрозы составляет: U    i   j Ai , j X j ,i  23, 2 . m n На основе выражений (4, 5) решение задачи о назначении целей может быть представлено в виде тензора: 1, 3 3.7 2.5 2.5 2.5 3.7 1.3 3.7 1.3   2.5 1, 2 2.1 2.1 2.1 1.2 2.5 1.2 2.5    4.1 3,1 2, 3 2.3 2.3 3.1 4.1 3.1 4.1    1.4 2.7 2.2 2, 2 2.2 2.7 1.4 2.7 1.4  W  AX  3.3 4.3 3.7 3.7 3, 7 4.3 3.3 4.3 3.3  (6)    4.1 4.7 5.6 5.6 5.6 4, 7 4.1 4.7 4.1   2.9 5.8 5.2 5.2 5.2 5.8 2, 9 5.8 2.9    5.3 2.5 3.5 3.5 3.5 2.5 5.3 2, 5 5.3     2.4 3.4 5.1 5.1 5.1 3.4 2.4 3.4 2, 4  В (6) диагональ тензора содержит значения остаточных угроз всех целей и суммарная величина остаточной угрозы характеризуется следом тензора. U    j  W j , j  23, 2 . m Решение задачи является оптимальным, но найдено с использованием NP - сложного алгоритма. Тензор (6) можно рассматривать как сумму диад. При этом каждая диада соответствует одному средству поражения (точнее средству поражения и целевому каналу) и одой цели. В связи с этим индексы строк тензора совпадает с номерами целей. Столбцам тензора соответствуют двойные индексы: V  1.1 3.1 2.1 2.2 2.3 3.2 1.2 3.3 1.3 . Первая цифра индекса соответствует номеру средства поражения, вторая – целевому каналу средства поражения. 3 Конструктивный алгоритм решения задачи о назначениях целей Рассмотрим решение задачи о назначениях целей с использованием тензорной методологии на конкретном приме- ре [1, 2, 12]. Пусть m  9, n  3 и xi , j  0,1 , i  1, 2,..., m, j  1, 2,..., n . Тензор остаточных угроз A в матричной форме определяется выражением (4). В тензоре A T строки соответствую средствам поражения целей, столбцы – воздушным целям: Значения элементов тензора остаточных угроз A определяются при поступлении данных о воз- душных целях. 47 ai , j  U i q i , j . Задача назначения целей может быть решена с использованием конструктивного алгоритма. Схема алгоритма приведена на рисунке 1. PrA ( A)  "Determining the dimension of the matrix À(n,m)" "Setting initial values X, K" "Reset the counter of channels Sj, j=1..m" "Definition of the q element with the maximum value in A " for k  1  n "The selection of the row G of the matrix A" for j  1  m Gj  q if Sj  m K  k if ( Sj  m)  ( K 0) "Search in G for a g element with a minimum value" "Determination of the index i of the element G by the value g" "Correction of the channel counter value Si = Si+1" "To assign Xj,k a value of 1" N n "Output X, V, N, K" Рисунок 1 – Схема конструктивного алгоритма В схеме конструктивного алгоритма, приведенного на рисунке 1, использованы следующие обозначения: A - тензор остаточных угроз, X - тензор назначения целей, K - номер итерации, при которой назначение цели произ- водится с нарушением минимума остаточной угрозы, S j - количество занятых каналов средства поражения, G - тензор первого ранга, сформированный из строки тензора A , q - максимальное значение элемента тензора оста- точных угроз, V - тензор двойной индексации средств поражения. Результатом выполнения конструктивного алгоритма является тензор второго порядка X и тензор первого по- рядка V . Тензор X содержит результаты назначения целей и имеет вид: c1 c2 c3 c4 c5 c6 c7 c8 c9 1 0 0 1 1 0 0 0 0  w1 X  0 0 1 0 0 0 1 0 1  w2 0 1 0 0 0 1 0 1 0  w3 В тензоре X строки соответствуют средствам поражения, столбцы – воздушным целям. Значения элементов тензора X должны удовлетворять следующим ограничениям: x j , i  g j ,  j 1 x j ,i  bi , b  1 1 1 1 1 1 1 1 1 . 3  9 i 1 Тензор первого ранга V является более компактной формой представления назначения целей. Значения элемен- тов тензора первого ранга V являются двойными индексами: c1 c2 c3 c4 c5 c6 c7 c8 c9 . (7) V  1.1 3.1 2.1 1.2 1.3 3.2 2.2 3.3 2.3 В тензоре (7) первая цифра элемента - номер средства поражения, вторая цифра - номер целевого канала сред- ства поражения. Например, для цели c5 , назначенной третьему каналу первого устройства поражения, двоичный индекс имеет значение 1.3. В тензоре A элементы, отражающие назначение целей средствам поражения отмечены жирным шрифтом. Не- сложно убедиться, что предварительное назначение целей осуществлено с использованием конструктивного (жад- ного) алгоритма (первая подзадача). Цели 6, 7, 8 и 9 назначены средствам поражения, не обеспечивающим мини- мума остаточных угроз. На основе тензоров A , X может быть определен тензор второго ранга, который можно рассматривать как сум- му специальных тензоров второго ранга (диад): 48 1.1 3.1 2.1 1.2 1.3 3.2 2.2 3.3 2.3 1, 3 3,7 2,5 1,3 1,3 3,7 2,5 3,7 2,5 с1  2,5 1, 2 2,1 2,5 2,5 1, 2 2,1 1, 2 2,1 с2   4,1 3,1 2, 3 4,1 4,1 3,1 2,3 3,1 2,3 с3   1.4 2,7 2, 2 1,4 1.4 2,7 2, 2 2,7 2, 2 с4 G  AX   3,3 4,3 3.7 3,3 3, 3 4,3 3,7 4,3 3,7  с5 (8)    4,1 4,7 5,6 4,1 4,1 4.7 5,6 4.7 5.6  с6  2,9 5,8 5, 2 2,9 2,9 3, 2 5, 2 5,8 5, 2  с7    5,3 2,5 3,5 5,3 5,3 2.5 3,5 2, 5 3,5  с8   2, 4 3.4 5,1 2, 4 2, 4 3, 4 5,1 3, 4 5,1 с9 В тензоре G строки соответствуют целям, столбцы – средствам поражения и номерам целевых каналов. На главной диагонали тензора G выделены значения остаточных угроз сформированных назначений с использовани- ем конструктивного алгоритма. Решение задачи с использованием конструктивного алгоритма не является опти- мальным tr(G)  27,0 . Сложность конструктивного алгоритма Q(n) . Тензоры G , V можно использовать для реше- ния задачи назначения целей как задачи назначений с использование известных алгоритмов линейного и динами- ческого программирования, алгоритмов метода ветвей и границ, венгерского метод. Сложность перечисленных алгоритмов Q(n3 ) . Кроме того, на основе тензоров G , V можно решить подзадачу поиска оптимального решения с использованием алгоритма комбинаторной оптимизации, имеющим сложность Q(n2 ) . 4 Решение задачи о назначениях методом линейного программирования Результаты решения задачи о назначениях с использованием перечисленных выше алгоритмов линейного про- граммирования, венгерского алгоритма, метода ветвей и границ, динамического программирования могут быть представлены в виде тензора G . В этом можно убедиться на примере решения задачи с использованием алгоритма линейного программирования. Выполним постановку задачи в следующем виде: F (G , X)   j 1  i gi , j xi , j  min ; n m  x  1, i  1, 2,..., m; n j 1 i , j  x  1, j  1, 2,..., n. n i 1 i , j В результате решения задачи определяется тензор (матрица) назначения целей, который имеет вид: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0  0 0 0 0 0 0 0 0 1   0 0 0 0 0 0 1 0 0 X  0 0 1 0 0 0 0 0 0 , (9)   0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 1 0   0 0 0 0 1 0 0 0 0 В тензоре G значения остаточных угроз, соответствующих единицам в тензоре назначения целей, выделены жирным шрифтом. В отличие от тензора (8) в тензоре (10) результаты назначения целей расположены произволь- но. 49 1.1 3.1 2.1 1.2 1.3 3.2 2.2 3.3 2.3  1,3 3,7 2.5 1, 3 1,3 3,7 2,5 3,7 2,5 с1  2,5 1, 2 2,1 2,5 2,5 1, 2 2,1 1, 2 2,1  с2   4,1 3,1 2,3 4,1 4,1 3,1 2,3 3,1 2, 3 с3    1.4 2,7 2, 2 1, 4 1.4 2,7 2, 2 2,0 2, 2 с4 G   3,3 4,3 3.7 3,3 3,3 4,3 3,7 3, 4 3,7  с5 (10)    4,1 4,7 5,6 4,1 4,1 4.7 5.6 5.6 5.6  с6  2,9 5,8 5, 2 2, 9 2,9 5,8 5, 2 5,0 5, 2  с7    5,3 2,5 3,5 5,3 5,3 2.5 3.5 2,5 3,5  с8    2, 4 3.4 5,1 2, 4 2,4 3, 4 5,1 5,0 5,1  с9 Из выражений (9, 10) следует, что решение задачи является оптимальным. Решение задачи можно также представить в виде, при котором остаточные угрозы назначенных целей распола- гаются на главной диагонали: 1.3 3.7 2.5 2.5 2.5 3.7 1.3 3.7 1.3   2.5 1.2 2.1 2.1 2.1 1.2 2.5 1.2 2.5    4.1 3.1 2.3 2.3 2.3 3.1 4.1 3.1 4.1    1.4 2.7 2.2 2.2 2.2 2.7 1.4 2.7 1.4  W = GX  3.3 T 4.3 3.7 3.7 3.7 4.3 3.3 4.3 3.3  . (11)    4.1 4.7 5.6 5.6 5.6 4.7 4.1 4.7 4.1   2.9 5.8 5.2 5.2 5.2 5.8 2.9 5.8 2.9    5.3 2.5 3.5 3.5 3.5 2.5 5.3 2.5 5.3     2.4 3.4 5.1 5.1 5.1 3.4 2.4 3.4 2.4  Сравнивая (6, 11), несложно убедиться, что остаточные угрозы назначенных целей расположены на главной диаго- нали в одном и том же порядке, а назначение является оптимальным. 5 Решение задачи методом комбинаторной оптимизации 5.1 Представление назначений целей суммой диад При решении задачи комбинаторной оптимизации тензор W следует рассматривать как неупорядоченную после- довательность специальных тензоров второго ранга (диад). Для всей группировки средств поражения сумма после- довательности диад определяется по формулам: W    1 W , W  A j ,   X  , j ; j  1, 2,...,9. 3 (12) где j - скользящий индекс,  - фиксированный индекс. При формировании W вектор столбец выбирается из множества столбцов тензора A , а вектор строка из тен- зора назначения целей X , являющегося результатом выполнения конструктивного алгоритма. Например, для тре- тьего средства поражения сумма диад имеет вид:  3, 7  0 3, 7 0 0 0 3, 7 0 3, 7 0   1, 2  0 1, 2 0 0 0 1, 2 0 1, 2 0      3,1  0 3,1 0 0 0 3,1 0 3,1 0       2, 7  0 2, 7 0 0 0 2, 7 0 2, 7 0  W3  A j ,3  B3, j   4,3    0 1 0 0 0 1 0 1 0   0 4,3 0 0 0 4,3 0 4,3 0  . (13)      4, 7  0 4, 7 0 0 0 4, 7 0 4, 7 0   5,8  0 5,8 0 0 0 5,8 0 5.8 0       2,5  0 2,5 0 0 0 2,5 0 2, 5 0       3, 4  0 3, 4 0 0 0 3, 4 0 3.4 0  Из выражения (13) следует, что третьему средству поражения c использованием конструктивного алгоритма назначены вторая, шестая и восьмая цели. При этом величина остаточной угрозы для этих целей составляет: 50 U   tr (W )  8, 4 . Аналогично можно определить суммы диад для первого и третьего средства поражения. 5.2 Глобальная и локальная целевые функции Значение следа tr ( W ) характеризует остаточную угрозу, исходящую от всей совокупности целей, но не позволяет сделать заключение о минимальности остаточной угрозы или оптимальности найденного решения. Для решения задачи комбинаторной оптимизации введем в рассмотрении локальную целевую функцию в сле- дующем виде: 1, если ( wi ,i  w j , j )  ( wi , j  w j ,i )  0; Fi , j   . (14) 0, если ( wi ,i  w j , j )  ( wi , j  w j ,i )  0. Значение функции Fi , j определяется в результате сравнения суммы следов диад ( ai  bi )  (a j  b j ) и диад ( a j  bi )  (ai  b j ) , которые могут быть сформированы за счет преобразования диад тензора W . Для тензора (8) суммы диад ло преобразования и после преобразования имеют значения ( w1,1  w9,9 )  6 и ( w1,9  w9,1 )  4,1 , соответственно. Следовательно, локальная целевая функция F1,9  1 и может быть осуществлено переназначение целей и преобразование диад. За счет преобразования диад след тензора W уменьшится на вели- чину ( w1,1  w9,9 )  ( w1,9  w9,1 )  1, 9 . Для осуществления преобразования последовательности диад в тензоре W введем в рассмотрение тензор 0 0 0 0 0 0 0 0 1  0 1 0 0 0 0 0 0 0   0 0 1 0 0 0 0 0 0   0 0 0 1 0 0 0 0 0 C  0 0 0 0 1 0 0 0 0 . (15)   0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0   0 0 0 0 0 0 0 1 0   1 0 0 0 0 0 0 0 0  Из (15) следует, что диады 2, 3, …, 8, соответствующие единицам на главной диагонали, сохраняют положение диад в тензоре W , а 1 и 9 диады преобразуются (перемещаются). Выполнив преобразование тензора G с исполь- зованием тензора C , получим:  2,5 3, 7 2,5 1,3 1,3 3, 7 2,5 3, 7 1,3   2,1 1, 2 2,1 2,5 2,5 1, 2 2,1 1, 2 2,5     2,3 3,1 2, 3 4,1 4,1 3,1 2,3 3,1 4,1     2, 2 2, 7 2, 2 1, 4 1.4 2, 7 2, 2 2, 7 1, 4  W  G ×C   3, 7 4,3 3.7 3,3 3, 3 4,3 3, 7 4,3 3,3     5, 6 4, 7 5, 6 4,1 4,1 4.7 5, 6 4.7 4.1   5, 2 5,8 5, 2 2,9 2,9 3, 2 5, 2 5,8 2,9     3,5 2, 5 3,5 5,3 5,3 2.5 3,5 2,5 5,3     5,1 3.4 5,1 2, 4 2, 4 3, 4 5,1 3, 4 2, 4 Несложно убедиться, что счет преобразования диад след составил tr ( W )  25, 5 . Следовательно, с использованием введенной локальной целевой функции Fi , j можно вести поиск несоответствий в последовательности диад и осу- ществлять поиск минимума целевой функции tr ( W ) . С использованием тензора C изменения в тензор V вводятся следующим образом: V  V  C  (2.3 3.1 2.1 1.2 1.3 3.2 3.2 2.2 1.1) . (16) Из (16) видно, что первая цель в результате преобразований назначена 2-му средству поражения (третий целевой канал), а девятая цель – 1-му средству поражения (первый целевой канал). Одной из проблем реализации комбинаторной оптимизации является определение необходимого и достаточного условий, выполнение которых позволяет локально осуществить снижение значения целевой функции за счет пре- образования двух диад. Преобразование диад существенно отличается от перестановки столбцов в матрице, так 51 как в результате преобразования диад значения остаточных угроз располагаются на главной диагонали тензора. Предположим, что в тензоре W выполнено преобразование диад, которое графически приведено на рисунке 1.  w w ... w k   w w ... w k  w w  ... w k  w w  ... w jk      .  ... ... ... ...   ... ... ... ...       wk wk  ... w kk   wk  wk ... w kk  Рисунок 2 - Преобразование диад тензора В тензорах фиксированные индексы обозначены греческими символами  ,  , переменный индекс латинским символом k  1, 2,..., n (k  i, j ) . Обозначим диады в тензоре следующим образом: D , D , Dk . Индексы диад ука- зывают на расположение элементов w , w , wkk , значения которых определяют значения глобальной и локальной целевых функций. Кроме того, индексы диад соответствуют двойным индексам средств поражения. Для выбран- ных диад (см. рисунок 1), независимо от этапа оптимизации, можно составить систему следующих уравнений: ( a  a )  (a  a )  R1 . (17) ( akk  a )  ( a k  ak )  R2 (18) ( akk  a )  ( a k  ak  )  R3 (19) В уравнениях (17, 18, 19) R1 , R2 , R3 представляют выигрыш от переназначения целей в результате возможного пре- образования диад. При Ri  0, k  1, 2, 3 - выигрыш от преобразования будет положительным Из уравнений (18, 19) следует: 2akk  ( a  a )  ( a k  ak  a k  ak  )  R2  R3 (20) Используя выражение (8), уравнение (11) можно привести в виду: 2akk  ( a  a )  ( a k  ak  a k  ak  )   R1  R2  R3 (21) Из выражения (21) следует, что независимо от значений R2 , R3 можно выполнить операцию переназначения целей и преобразовать диады D , D . Преобразование диад приведет к снижению значения следа тензора только за счет преобразования выделенных диад. В этом несложно убедиться, сравнив выражения (20) и (21). Значение третьего слагаемое в выражениях (20, 21) определяется одними и теми же элементами тензора . Таким образом, достаточ- ным и необходимым условием переназначения целей (преобразования диад) является выполнение неравенства: ( a  a )  ( a  a )  0 . (22) Если имеет место ( a  a )  ( a  a )  0 , (23) то переназначение целей и преобразование диад не выполняется. Выражение (23) можно использовать для оценки качества полученного решения. Если это неравенство выполня- ется для всех возможных пар диад тензора, то след тензора имеет минимальное значение и найденное решение является оптимальным. 5.3 Алгоритм комбинаторной оптимизации назначений. Схема разработанного алгоритма комбинаторной оптимизации приведена на рисунке 3. Входные данные алгоритма – результаты выполнения конструктивного алгоритма: тензор второго ранга W и тензор первого ранга V . В соот- ветствие с рисунком 3 локальный поиск начинается с первой цели и заканчивается на цели m . Количество итера- ций по поиску несоответствий в назначениях целей N  m  ( m  1) . Если m  9 , то N  72 . При m  32 коли- чество итераций по поиску несоответствий значительно возрастает и составляет N  1024 . 52 Pr ( G V)  "Determination of the dimension of the matrix G(n,n)" "Formation of a unit matrix C of dimension (n,n)" for j  1 2  n for i  1 2  n if i  j "Calculating the value of the local objective function F" if "value F"  0 "Matrix transformation Ñ" "The transformation of vector V: V=VC" "Matrix transformation G: G = GC" "Reconstruction of the unit matrix C" "Output of result: G" "Output of result: V" Рисунок 3 – Схема алгоритма комбинаторной оптимизации Количество несоответствий в начальном распределении величина случайная. Поэтому сложность вычислений определяется не только размерностью входных данных, но и содержанием этих данных. Схема поиска несоответ- ствий (22) с целью минимизации следа тензора приведена на рисунке 4. 1 1 2 2 3 3 ⁞ ⁞ 9 9 Рисунок 4 – Поиск несоответствий в назначениях целей В соответствии со схемой поиска несоответствий в назначении целей количество итераций составляет величину, определяемую формулой. N  Q  m(m  1) , где Q – коэффициент, учитывающий повторные вычисления. При проведении вычислительных экспериментов оптимальное назначение целей достигалось при значениях коэф- фициента Q равным 1. 6 Результаты вычислительного эксперимента Результаты вычислительного эксперимента приведены в таблице 1. Количество распределяемых целей m  16 . Остаточные угрозы формировались как случайная выборка с равномерным распределением. Количество целей равно количеству целевых каналов всех средств поражения. Первый столбец таблицы содержит номера вычисли- тельного эксперимента, второй столбец – количество несоответствий в назначениях целей по результатам комбина- торной оптимизации R , в третьем столбце приведены значения остаточной угрозы по результатам решения задачи назначения целей с использование конструктивного алгоритма. В четвертом столбце приведены значения следа тензор tr ( W ) , сформированного с использованием алгоритма комбинаторной оптимизации. В пятом столбце при- ведены значения коэффициента эффективности решения задачи о назначении целей методом комбинаторной опти- мизации. Из таблицы 1 следует, что за счет комбинаторной оптимизации величин остаточной угрозы U снижена на вели- чину равную сумме остаточных угроз, от двух целей. Количество итераций при решении задачи комбинаторной оптимизации N  m ( m  1)  m  m 2  240 . 53 Для сравнения, при применении венгерского метода N  m 3 и равно 3096 итерациям. Таблица 1– Результаты вычислительного эксперимента Номер tr ( W ) tr (Q ) (tr ( W )  tr (Q )) / tr ( W ) эксперимента R 1 0 71,45 57,97 0,19 2 0 112,36 93,52 0,17 3 0 78,36 73,32 0,06 4 0 51,31 51,31 0,00 5 0 80,64 68,40 0,15 6 0 102,34 72,37 0,29 7 0 86,17 81,19 0,06 8 0 102,52 79,1 0,29 9 0 84,73 75,07 0,14 10 0 92,40 72,70 0,21 Если исключить сравнения между целями, назначенными каналам одного и того же устройства поражения, то количество итераций в можно значительно уменьшить. При этом количество итераций можно рассчитать по фор- муле: N  m( m  g ) . При m  16 и g  4 количество итераций N  192 . Таким образом, сложность вычислений снижена на 48 итераций. С увеличением количества целевых каналов эф- фект от исключения процедуры вычисления локальной целевой функции будет более значимым. 7 Разбиение задачи комбинаторной оптимизации на две подзадачи Сложность рассмотренного выше алгоритма состоит в необходимости проверки условия начального распределения целей одному и тому же средству поражения, что требует также затрат вычислительных ресурсов. Эту операцию можно исключить, если использовать подход к решению задачи, основанный на сведении задачи к двум подзада- чам [4]. Для рассматриваемого примера поиск и устранение несоответствий в назначениях целей выполняется с использованием двух подзадач (рисунок 5). ЗРКi ЗРКj Каналы ЗРКi Каналы ЗРКj 1 1 1 1 2 2 2 2 3 3 3 3 а) б) Рисунок 5 – Поиск и устранение несоответствий: а) на уровне средств поражения, б) на уровне целевых каналов Первая подзадача связана с локальным поиском несоответствий на уровне средств поражения (см. рис. 5,а). Вто- рая подзадача связана с поиском несоответствий в назначениях на уровне целевых каналов средств поражения (см. рис. 5.б). Разделение задачи назначения целей на подзадачи обеспечивает реализацию распределенных вычисле- ний, что также приведет к снижению временных затрат на решение задачи. Для рассматриваемого выше примера n  3, g  3 количество итераций N  n ( n  1) g 2  54 . В случае n  4, g  8, m  ng количество итераций N  768 . По сравнению с первым вариантом назначения целей количество итераций сокращено на 13%. 8 Выводы Решение задачи о назначении целей целесообразно разделить на три этапа. На первом этапе поиск решения при- ближенного к оптимальному осуществляется с использованием конструктивного алгоритма. На втором этапе полу- ченное решение представляется в виде тензора второго ранга, в котором остаточные угрозы от целей расположены на главной диагонали. След тензора рассматривается как глобальная целевая функция, а след двух диад как ло- 54 кальная целевая функция. Третий этап связан с поиском минимума глобальной целевой функции при ограничениях на количество средств поражения. При поиске минимума глобальной целевой функции вычисляются значения ло- кальной целевой функции. В случае отрицательного значения локальной целевой функции выполняется операция преобразования диад тензора назначений. Последовательное выполнение всех этапов обеспечивает поиск опти- мального решения. Сложность объединения двух алгоритмом Список использованной литературы [1] Крон Г. Тензорный анализ сетей: Пер. с англ. /Под ред. Л.Т. Кузина, П.Г. Кузнецова. М.: Сов. Радио, 1978. – 720 с. [2] Петров А.Е. Тензорные методы в информационных технологиях // Технологии информатизации профессио- нальной деятельности (в науке, образовании и промышленности), ТИПД–2011:Труды III Всероссийской науч. конференции с межд. участием. Изд-во Удмуртского университета¿, 2011. – 540 с. [3] Корте Бернард. Комбинаторная оптимизация. Теория и алгоритмы / Б. Корте, Й. Фиген // Пер. с англ. М. А. Бабенко. = Москва: Изд-во МЦНМО, 2015. = 719 с. [4] Нильсон Н. Искусственный интеллект. Методы поиска решений. Перевод с англ. В.Л. Стефанюка. Под ред. С.В. Фомина. 1973. [5] Безяев В.С. Решение задачи о назначениях в автоматизированных системах оперативного управления на ос- нове тензорного исчисления / В.С. Безяев, П.П. Макарычев // Известия высших учебных заведений. Поволж- ский регион. Технические науки. – 2015. – № 3 (35). – С. 77-85. [6] Макарычев П.П. Модельные представления данных на основе прямого тензорного анализа / П.П. Макарычев, Д.В. Артамонов // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2016. – № 3 (39). – С. 3-14. [7] Макарычев П.П. Программа решения задачи о назначениях на основе тензорной методологии Макарычев П.П. свидетельство о регистрации программы для ЭВМ RUS 2017660445 25.07.2017 [8] Макарычев П.П. Комбинаторная оптимизация пути коммивояжера с применением тензорной методологии Макарычев П.П. В сборнике: Аналитические и численные методы моделирования естественно-научных и социальных проблем Материалы XI Международной научно-технической конференции. под ред. И. В. Бой- кова. 2016. С. 85-88. [9] Карманов В.Г. Математическое программирование. – М.: Физматлит, 2004. – 263 с. [10] Безяев В.С., Алгоритм решения задачи о назначениях целей / Безяев В.С., Макарычев П.П. В сборни- ке: Аналитические и численные методы моделирования естественно-научных и социальных про- блем Сборник статей X Международной научно-технической конференции. под ред. И. В. Бойкова. 2015. С. 51-54. [11] Макарычев П.П. Построение моделей классов и объектов с применением тензорной МЕТОДОЛОГИИ Макарычев П.П., Попова Н.А. В сборнике: УНИВЕРСИТЕТСКОЕ ОБРАЗОВАНИЕ (МКУО-2013) сборник статей XVII Международной научно-методической конференции, посвященной 70-летию образования уни- верситета. Под редакцией В. И. Волчихина, Р. М. Печерской. 2013. С. 457-458. [12] Электронное научное издание «Устойчивое инновационное развитие: проектирование и управление» www.rypravlenie.ru том 8 № 2 (15), 2012, ст. 5 УДК 51.74 Тензорная методология для поиска оптимальной структуры системы В.А. Кутергин, доктор технических наук, профессор, Институт прикладной механики Уральского отделения Российской Академии Наук [13] C. H. Papadimitriou, K. Steiglitz. Combinatorial optimization: algorithms and complexity. — Mineola, NY: Dover, 1998. — ISBN 0486402584. [14] H.P. Williams. Logic and integer programming. — 2009. — Т. 130. — (International Series in Operations Research & Management Science). — ISBN 978-0-387-92280-5. [15] R.E. Burkard, M. Dell’Amico, S. Martello: Assignment Problems. SIAM, Philadelphia (PA.) 2009. ISBN 978-0- 89871-663-4 Венгерский алгоритм [16] Хемди А. Таха. Введение в исследование операций. – 7-е изд. – СПб.: Вильямс, 2005. – 901 с. [17] Кочетов Ю.А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. – 2008. – Т.48, No 5. – C. 747–764. [18] [18] Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Серия 2. – 2003. – Т. 10, No 1. – С. 11–43. [19] Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219 - 228. [20] А.Н. Пифтанкин, Н.А. Пифтанкин Модели и подходы, используемые в задачах управления пво корабельного соединения. интегрированные асу. корабельные комплексы и системы / Автоматизация процессов управле- ния № 1(23). 2011. – С. 41-49. [21] Безяев, В. С. Методы анализа систем и сетей информационного обмена / В. С. Безяев // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2007. – № 2. – С. 42–47 55