Автоматика и телемеханика, № 8, 2021
Оптимизация, системный анализ
и исследование операций
© 2021 г. Л.Г. АФРАЙМОВИЧ, д-р физ.-мат. наук (levafraimovich@gmail.com),
М.Д. ЕМЕЛИН (makcum888e@mail.ru)
(Нижегородский государственный университет)
КОМБИНИРОВАНИЕ РЕШЕНИЙ АКСИАЛЬНОЙ ЗАДАЧИ
О НАЗНАЧЕНИЯХ
Рассматриваются вопросы решения NP-трудной целочисленной трех-
индексной аксиальной задачи о назначениях. Ставится задача оптималь-
ного комбинирования пар допустимых решений задачи и строится линей-
ный по трудоемкости алгоритм ее решения. Данный подход может быть
применен в качестве дополнения к эвристическим или приближенным
алгоритмам решения трехиндексной задачи о назначениях для постобра-
ботки полученных приближенных решений задачи. Приводятся результа-
ты вычислительных экспериментов, демонстрирующие перспективность
предложенного подхода.
Ключевые слова: аксиальная задача о назначениях, многоиндексные за-
дачи, приближенные алгоритмы.
DOI: 10.31857/S0005231021080080
1. Введение
Существует широкий класс прикладных задач, формализуемых в виде
многоиндексных аксиальных задач о назначениях [1-3]. Обзор результатов,
связанных с анализом вычислительной сложности и построением приближен-
ных алгоритмов решения специальных подклассов многоиндексных аксиаль-
ных задач о назначениях, приведен в [1]. В общей постановке класс мно-
гоиндексных аксиальных задач о назначениях является NP-трудным уже в
трехиндексном случае [4]. Более того, для задач данного класса не существу-
ет полиномиальных ε-приближенных алгоритмов (здесь ε — произвольная
константа), иначе P = NP, данный результат также справедлив уже в трехин-
дексном случае [5]. В [5] также показано, что данный результат справедлив
в случае, когда матрица стоимостей задачи о назначениях имеет декомпо-
зиционную структуру (т.е. матрица стоимостей представима в виде суммы
трех двухиндексных матриц). При этом задача о назначениях в случае, когда
декомпозиционная матрица стоимостей удовлетворяет неравенству треуголь-
ника, остается NP-трудной [5]. В [5-8] исследуются аксиальные задачи о на-
значениях со специальной структурой многоиндексной матрицы стоимостей,
в [9-11] обсуждаются вопросы построения потоковых алгоритмов решения
многоиндексных задач, в [12] описывается метод ветвей и границ решения
аксиальной задачи о назначениях, в [13] строится генетический алгоритм,
159
в [14] обсуждается нижняя оценка задачи, в [15] исследуются асимптотиче-
ски оптимальные решения. В планарной постановке задача о назначениях
исследуется в [16-18]. Стохастические постановки многоиндексных задач ис-
следуются в [19-21].
В данной работе ставится задача оптимального комбинирования пар допу-
стимых решений трехиндексной аксиальной задачи о назначениях. Содержа-
тельно задача заключается в поиске оптимального решения, которое может
быть построено c использованием лишь назначения выбранных допустимых
решений. Строится полиномиальный алгоритм решения данной задачи ком-
бинирования. Данный алгоритм может быть применен в качестве дополнения
к эвристическим или приближенным алгоритмам решения трехиндексной за-
дачи о назначениях для постобработки полученных допустимых решений за-
дачи. Начальные допустимые решения могут быть получены при помощи
эвристик, описанных, например, в [2, 5, 13, 22-24 и др.].
Далее статья построена следующим образом. В разделе 2 приводится по-
становка трехиндексной аксиальной задачи о назначениях, в разделе 3 ста-
вится задача оптимального комбинирования допустимых решений задачи о
назначениях, строится алгоритм оптимального комбинирования и доказыва-
ется его корректность, в разделе 4 приводятся результаты вычислительных
экспериментов.
2. Трехиндексная аксиальная задача о назначениях
Пусть I, J, K - непересекающиеся множества индексов, I ∩ J = ∅, I ∩ K =
= ∅, J ∩ K = ∅ и |I| = |J| = |K| = n; cijk, i ∈ I, j ∈ J, k ∈ K - трехиндексная
матрица стоимостей; xijk, i ∈ I, j ∈ J, k ∈ K - трехиндексная матрица неиз-
вестных. Тогда трехиндексная аксиальная задача о назначениях ставится как
следующая задача целочисленного линейного программирования:
∑∑
(1)
xijk
= 1, k ∈ K,
i∈I j∈J
∑∑
(2)
xijk
= 1, j ∈ J,
i∈I k∈K
∑∑
(3)
xijk
= 1, i ∈ I,
j∈J k∈K
(4)
xijk
∈ {0, 1} , i ∈ I, j ∈ J, k ∈ K,
∑∑∑
(5)
cijkxijk
→ min.
i∈I j∈J k∈K
Задача о назначениях (1)-(5) является NP-трудной [4]. При этом суще-
ствует ряд эффективных алгоритмов (эвристических или ε-приближенных),
показывающих хорошие практические результаты при решении численных
задач, выделим некоторые из них.
В [5] предложен алгоритм, применимый при решении задач с декомпози-
ционной матрицей системы ограничений, т.е. с матрицей стоимостей, пред-
ставимой в виде суммы трех двухиндексных матриц: сijk = u1ij + u2ik + u3jk,
160
i ∈ I, j ∈ J, k ∈ K. Данный алгоритм основан на решении пары зависимых
двухиндексных задач. Всего существует три таких пары, таким образом,
предложенный в [5] алгоритм позволяет построить три различных допусти-
мых решения. В [5] показано, что рекорд из данных трех решений является
ε-приближенным решением задачи в случае, когда декомпозиционная мат-
рица стоимостей удовлетворяет неравенству треугольника: u1ij ≤ u2ik + u3jk,
u2ik ≤ u1ij + u3jk, u3jk ≤ u1ij + u2ik, i ∈ I, j ∈ J, k ∈ K. В [2] предложен эвристи-
ческий подход, основанный на аппроксимации матрицы стоимостей исходной
задачи матрицей стоимостей заданной структуры и решении задачи с аппрок-
симационной матрицей стоимостей. Для ряда аппроксимаций в [2] строятся
оценки отклонения от оптимума. В [13] построен гибридный генетический ал-
горитм решения задачи о назначениях, интерес представляет предложенная
стратегия локальной оптимизации, которая может быть применена к любым
допустимым решениям (в том числе полученным случайной генерацией).
Таким образом, начальные допустимые решения задачи (1)-(5) могут быть
получены при помощи эвристик, описанных, например, в [2, 5, 13] и др. Далее
описывается алгоритм, позволяющий оптимально комбинировать назначения
выбранных допустимых решений.
3. Задача комбинирования решений
Пусть задано множество W ⊆ I × J × K, которое определяет подмноже-
ство разрешенных назначений. Тогда рассмотрим задачу (1)-(4), (6), (5).
(6)
xijk
= 0, (i, j, k) ∈ W.
Для удобства изложения задачу (1)-(4), (6), (5) для заданного множества W
будем обозначать через Z (W ) . Очевидно, задача (1)-(5) соответствует задаче
Z (I × J × K).
В общем случае задача Z (W ) является NP-трудной. Более того, проблема
проверки совместности системы (1)-(4), (6) для произвольного множества W
является NP-полной [1]. Будем рассматривать такие множества W , которые
соответствуют набору назначений некоторых допустимых решений задачи
(1)-(5).
Пусть xijk, i ∈ I, j ∈ J, k ∈ K — допустимое решение системы ограниче-
ний (1)-(4). Тогда через W (x) обозначим следующее множество разрешенных
назначений:
W (x) = {(i,j,k)| xijk = 1,i ∈ I,j ∈ J,k ∈ K}.
Далее пусть x1ijk, i ∈ I, j ∈ J, k ∈ K и x2ijk, i ∈ I, j ∈ J, k ∈ K — произвольные
допустимые решения системы ограничений (1)-(4). Тогда
(
)
(
)
(
)
W
x1,x2
=W
x1
W
x2
(
(
))
Данный раздел посвящен алгоритму решения задачи Z
W
x1,x2
(
(
))
Алгоритм 1. Решение задачи Z
W
x1,x2
Шаг 1. Построить граф G = (V,A), где
{
(
)}
V = {I ∪ J ∪ K}, A =
(i, j) , (i, k) , (j, k)
(i, j, k) ∈ W
x1,x2
161
Шаг 2. Найти компоненты связности Vl, l = 1,q графа G и построить под-
графы Gl = (Vl, Al), l = 1, q, порожденные соответствующими компонентами
связанности.
Шаг 3. Построить следующие множества:
{
(
)
}
D1l =
(i, j, k)
(i,j,k) ∈ W
x1
, (i,j) ,(i,k) ,(j,k) ∈ Al
,
{
(
)
}
D2l =
(i, j, k)
(i,j,k) ∈ W
x2
, (i,j) ,(i,k) ,(j,k) ∈ Al
(
(
))
Шаг 4. Оптимальное значение критерия задачи Z
W
x1,x2
определя-
ется как
⎛
⎞
∑
∑
∑
c∗ =
min⎝
cijk,
cijk⎠ .
l=1
(i,j,k)∈D1
(i,j,k)∈D2
l
l
Шаг 5. Оптимальное решение задачи определяется по следующему алго-
ритму. Пусть xijk:=0, i ∈ I, j ∈ J, k ∈ K. Далее для каждого l = 1, q выпол-
нить
∑
cijk.
xijk:=1, (i,j,k) ∈ Dp∗l, где p∗ = argmin
p∈{1,2}
(i,j,k)∈Dpl
Далее рассмотрим доказательство корректности алгоритма 1. При дока-
зательстве будем использовать следующие обозначения:
⋃
⋃
V1l =
{i, j, k}, V2l =
{i, j, k}, l = 1, q.
(i,j,k)∈D1
l
(i,j,k)∈D2
l
Лемма 1. V 1l = V 2l = Vl, l = 1,q.
Доказательство. Покажем, что V 1l = Vl, l = 1,q. Докажем методом
от противного. Предположим, что найдется l ∈ {1, . . . , q}, что выполняется
условие V1l= Vl. По построению V1l ⊆ Vl, тогда существует v, что v ∈ Vl и
v∈V1l.
Тогда согласно условию (1)-(4) существует тройка (i, j, k), что x1ijk = 1 и
(
)
v ∈ {i,j,k}. Отсюда (i,j,k) ∈ W
x1
и, следовательно, (i, j) , (i, k) , (j, k) ∈ A.
Тогда так как v ∈ Vl и v ∈ {i, j, k}, то (i, j) , (i, k) , (j, k) ∈ Al и (i, j, k) ∈ D1l.
Отсюда i, j, k ∈ V1l и, следовательно, v ∈ V1l. Получаем противоречие.
Соотношение V2l = Vl, l = 1, q, доказывается аналогично. Лемма 1 доказана.
Лемма 2. |Vl ∩ I| = |Vl ∩ J| = |Vl ∩ K|, l = 1,q.
Доказательство. Согласно условию (1)-(4) выполняется |V 1l∩I| =
= |V 1l ∩ J| = |V 1l ∩ K|. По лемме 1 V 1l = Vl, отсюда |Vl ∩ I| = |Vl ∩ J| = |Vl ∩ K|.
Лемма 2 доказана.
Теорема 1. Оптимальное значение критерия задачи Z(W(x1,x2)) опре-
деляется как
⎛
⎞
∑
∑
∑
min⎝
cijk,
cijk⎠.
l=1
(i,j,k)∈D1
(i,j,k)∈D2
l
l
162
Доказательство. Рассмотрим компоненту связности Vl, l ∈ {1,...,q}.
Согласно лемме 2 выполняется |Vl ∩ I| = |Vl ∩ J| = |Vl ∩ K|. Тогда упорядо-
чим множества I ∩ Vl, J ∩ Vl, K ∩ Vl следующим образом.
В качестве i1, j1, k1 выберем произвольную тройку (i1, j1, k1) ∈ D1l . Пусть
были упорядочены первые m элементов множеств:
i1,... ,im,
j1,... ,jm,
k1,... ,km.
Тогда выберем тройку im+1, jm+1, km+1, удовлетворяющую следующим пра-
вилам:
— im+1 ∈ (I ∩ Vl)\{i1,...,im}, jm+1 ∈ (J ∩ Vl)\{j1,...,jm},
km+1 ∈ (K ∩ Vl)\{k1,... ,km},
— (im+1, jm+1, km+1) ∈ D1l ,
— существует тройка (im+1, j, k) ∈ D2l , что j ∈ {j1, . . . , jm} или
k ∈ {k1,...,km}.
Далее покажем, что такая тройка (im+1, jm+1, km+1) всегда существует, в
противном случае множества упорядочены.
Построим множества
⋃
⋃
V1m =
{iq,jq,kq}, V2m =
{iq, j, k}.
q=1
q=1,m,(iq,j,k)∈D2
l
Возможны следующие два случая.
1) V1m = V2m, тогда существует вершина jq ∈ V2m или kq ∈ V2m, q = 1, m, сле-
довательно, существует тройка (i, j, k) ∈ D2l, такая что jq = j или kq = k, дан-
ную вершину i выберем в качестве im+1. В качестве jm+1, km+1 выберем такие
индексы, что (im+1, jm+1, km+1) ∈ D1l.
2) V1m = V2m. По построению для каждой вершины i ∈ {i1, . . . , im} суще-
ствует тройка (i, j, k) ∈ D2l, причем j ∈ {j1, . . . , jm} и k ∈ {k1, . . . , km}. Со-
гласно (1)-(4) не существует тройки (i, j, k) ∈ D2l, что {i, j, k} ∩ V1m = ∅ и
{i, j, k} \V1m = ∅. Тогда V1m образует компоненту связанности графа G и, сле-
довательно, V1m = Vl. Таким образом множества упорядочены.
Далее рассмотрим произвольное допустимое решение xijk, i ∈ I, j ∈ J, k ∈ K,
задачи W (x1, x2). Пусть Rl = {(i, j, k)|xijk = 1, {i, j, k} ∈ Vl}, l = 1, q. Предпо-
ложим, что для некоторого l ∈ {1, . . . , q} найдутся (i′, j′, k′), (i′′, j′′, k′′) ∈ Rl,
что (i′, j′, k′) = (i′′, j′′, k′′), (i′, j′, k′) ∈ D1l, (i′′, j′′, k′′) ∈ D2l. Пусть множества
I ∩ Vl, J ∩ Vl, K ∩ Vl упорядочены согласно процедуре, описанной выше:
i1,... ,im,
j1,... ,jm,
k1,... ,km.
Здесь I ∩ Vl = {i1, . . . , im}, J ∩ Vl = {j1, . . . , jm}, K ∩ Vl = {k1, . . . , km}. Не
уменьшая общности, будем считать, что (i1, j1, k1) = (i′, j′, k′).
Как показано выше, (i1, j1, k1) ∈ Rl. Пусть для некоторого t < m вы-
полняется (i1, j1, k1), (i2, j2, k2), . . . , (it, jt, kt) ∈ Rl. Согласно описанному вы-
ше правилу упорядочивания множеств существует тройка (it+1, j, k) ∈ D2l,
163
что j ∈ {j1, . . . , jt} или k ∈ {k1, . . . , kt}. Тогда с учетом условия (1)-(4)
выполняется (it+1, jt+1, kt+1) ∈ Rl. Следовательно, (i1, j1, k1), (i2, j2, k2),
...,(im,jm,km) ∈ Rl. Получаем противоречие.
Таким образом, для каждого l ∈ {1, . . . , q} выполняется Rl = D1l или
(
(
))
Rl = D2l. Отсюда оптимальное значение критерия задачи Z
W
x1,x2
опре-
)
∑
(∑
∑
q
деляется как
min(i,j,k)∈D1
cijk,
. Теорема 1 доказана.
l=1
(i,j,k)∈D2 cijk
l
l
Теорема 2. Алгоритм 1 требует O(n) вычислительных операций.
Доказательство. Пусть входными данными алгоритма 1 являются до-
пустимые решения x1, x2, представленные в виде коллекции троек (i, j, k) и
стоимостей сijk, для которых соответствующие переменные принимают зна-
чение 1. Согласно (1)-(4) для каждого из допустимых решений количество та-
ких троек составляет n. Тогда на шаге 1 алгоритма строится граф G = (V, A),
что |V | = O(n), |A| = O(n).
На шаге 2 граф G разбивается на компоненты связности. Это осу-
ществляется при помощи обхода графа в ширину, который требует
O(|V | + |A|) = O(n) вычислительных операций.
На шаге 3 для входных троек алгоритма определяются соответствующие
компоненты связности, этот шаг требует O(n) вычислительных операций.
И, наконец, на шаге 4 необходимо определить оптимальное значение кри-
терия. Согласно шагу 4 по каждой из компонент связности выбирается ми-
нимум среди подмножества троек, соответствующих входным допустимым
решениям. Данный шаг требует O(n) вычислительных операций.
Таким образом, алгоритм 1 требует O(n) вычислительных операций. Тео-
рема доказана.
4. Вычислительный эксперимент
В [5] предложен набор тестовых задач, состоящий из 18 задач, параметр n
принимает значения 33 и 66. Предложенный в [5] подход основан на реше-
нии трех пар зависимых двухиндексных задач, в результате решения каж-
дой из пары задач строится допустимое решение задачи (1)-(5). По аналогии
с [5] значение критерия (5), полученное на данных трех допустимых решени-
ях, будем обозначать через cIJ , cIK , cJK соответственно. Сами допустимые
решения обозначим через xIJ , xIK , xJK соответственно. Далее последова-
тельно применим алгоритм 1 оптимального комбинирования решений сле-
дующим образом. Пусть xIJ-JK является решением задачи Z (W (xIJ , xJK )),
xIJ-JK-IK является решением задачи Z (W (xIJ-JK,xIK)). Значение крите-
рия (5) на решении xIJ-JK-IK обозначим через сIJ-JK-IK. Оптимальное
значение критерия задачи (1)-(5) обозначим через c∗. Будем сравнивать ре-
корд среди решений xIJ , xIK , xJK (соответствует min{cIJ , cIK , cJK }) с их
оптимальной комбинацией xIJ-JK-IK (соответствует сIJ-JK-IK). Получен-
ные результаты приведены в табл. 1. Среднее отклонение от оптимума для
рекорда среди решений xIJ , xIK , xJK составляет 1,675%, среднее отклоне-
ние от оптимума для оптимальной комбинации данных решений xIJ-JK-IK
составляет 1,527%. Фактическое снижение отклонения от оптимума за счет
комбинирования решений произошло на семи из 18 тестовых задач.
164
Таблица 1
n c∗ cIJ cIK cJK min{cIJ,cIK,cJK} сIJ-JK-IK
1
33
1608
1620
1637
1655
1620
1615
2
33
1401
1420
1416
1411
1411
1406
3
33
1604
1613
1635
1632
1613
1604
4
66
2662
2678
2684
2666
2666
2663
5
66
2449
2503
2486
2470
2470
2466
6
66
2758
2811
2788
2792
2788
2777
7
33
4797
4855
4851
4885
4851
4851
8
33
5067
5165
5150
5181
5150
5150
9
33
4287
4341
4364
4371
4341
4341
10
66
9684
9817
9761
9891
9761
9761
11
66
8944
9138
9177
9129
9129
9129
12
66
9745
9921
9869
9975
9869
9869
13
33
133
139
135
136
135
135
14
33
131
137
138
137
137
136
15
33
131
134
136
136
134
134
16
66
286
296
296
295
295
295
17
66
286
295
295
292
292
292
18
66
282
294
297
294
294
294
Таблица 2
n M
∗
∗
10
10
5,366%
5,366%
11
10
8,435%
6,021%
12
10
13,913%
12,704%
13
10
20,686%
15,913%
14
10
33,339%
29,448%
15
10
55,093%
50,347%
16
10
73,054%
69,869%
17
10
83,103%
75,433%
18
10
75,947%
67,858%
19
10
97,771%
88,445%
По аналогии с [12] построим тестовый набор c матрицами стоимостей,
элементы которых сгенерированы с целочисленными значениями, равномер-
но распределенными в интервале [0, 300]. Будем строить серии эксперимен-
тов с задачами размерности n ∈ {10, 11, . . . , 19}, в каждой серии построим
M = 10 задач. Для каждой из тестовых задач случайным образом сгене-
рируем N = n3 допустимых решений, к каждому из которых итеративно
применим алгоритм локальной оптимизации, предложенный в [13], до тех
пор, пока решение не перестанет меняться. Полученные допустимые реше-
ния задачи (1)-(5) и соответствующие значения критерия (5) обозначим
через x′t и c′t, t = 1, N . Тогда рекорд среди полученных решений обозна-
165
чим как C′ = min c′t. Далее применим алгоритм 1 оптимального комбини-
t=1,N
рования решений следующим образом. Пусть x′′1 является решением задачи
(
(
))
Z (W (x′1,x′2)), x′′t является решением задачи Z
W
x′′t-1,x′t+1
, t = 2,N - 1.
Соответствующие значения критерия обозначим через с′′t, t = 1, N - 1, и вы-
берем рекорд, достигнутый комбинированием всей последовательности N ре-
шений C′′ = c′′N-1. Наконец, через C∗ обозначим оптимальное значение кри-
терия исходной задачи. Будем сравнивать отклонение от оптимума рекорда
среди локально оптимизированных случайных решений и отклонение от оп-
тимума рекорда среди локально оптимальных случайных решений, последо-
вательно комбинированных алгоритмом 1. Для серии экспериментов будем
оценивать среднее отклонение в серии. Полученные результаты приведены в
табл. 2. Таким образом, среднее отклонение для C′ по всем сериям составляет
46,671%, для C′′ по всем сериям составляет 42,141%.
5. Заключение
При исследовании алгоритмов решения трехиндексной аксиальной задачи
о назначениях в работе построен алгоритм, позволяющий эффективно комби-
нировать пары допустимых решений задачи. Данный алгоритм может быть
применен в качестве дополнения к известным эвристическим или приближен-
ным алгоритмам для постобработки полученных приближенных решений за-
дачи о назначениях. Приводятся результаты вычислительных экспериментов,
демонстрирующие повышения качества приближенных решений, полученных
в результате постобработки предложенным алгоритмом оптимального комби-
нирования. Полученные результаты естественным образом обобщаются при
исследовании многоиндексных задач о назначениях. Дальнейшим направле-
нием исследования является построение алгоритма комбинирования произ-
вольного числа допустимых решений.
СПИСОК ЛИТЕРАТУРЫ
1. Spieksma F.C.R. Multi Index Assignment Problems. Complexity, Approximation,
Applications. / P.M. Pardalos, L.S. Pitsoulis (Eds.). Nonlinear Assignment Problems:
Algorithms and Applications. Dordrecht: Kluwer Acad. Publishers, 2000. P. 1-11.
2. Афраймович Л.Г. Эвристический метод решения целочисленных декомпозици-
онных многоиндексных задач // АиТ. 2014. № 8. С. 3-18.
Afraimovich L.G. A Heuristic Method for Solving Integer-Valued Decompositional
Multiindex Problems // Autom. Remote Control. 2014. V. 75. P. 1357-1368.
3. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального пла-
нирования производства // АиТ. 2010. № 10. С. 148-155.
Afraimovich L.G., Prilutskii M.Kh. Multiindex Optimal Production Planning
Problems // Autom. Remote Control. 2010. V. 71. P. 2145-2151.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:
Мир, 1982.
5. Crama Y., Spieksma F.C.R. Approximation Algorithms for Three-Dimensional
Assignment Problems with Triangle Inequalities // Eur. J. Oper. Res. 1992. V. 60.
P. 273-279.
166
6.
Bandelt H.J., Crama Y., Spieksma F.C.R. Approximation Algorithms for Multidi-
mensional Assignment Problems with Decomposable Costs // Discret. Appl. Math.
1994. V. 49. P. 25-50.
7.
Burkard R.E., Rudolf R., Woeginger G.J. Three-Dimensional Axial Assignment
Problems with Decomposable Cost Coefficients // Discret. Appl. Math. 1996. V. 65.
P. 123-139.
8.
Spieksma F., Woeginger G. Geometric three-dimensional assignment problems //
Eur. J. Oper. Res. 1996. V. 91. P. 611-618.
9.
Афраймович Л.Г. Многоиндексные транспортные задачи с декомпозиционной
структурой // АиТ. 2012. № 1. С. 130-147.
Afraimovich L.G. A Multi-index Transport Problems with Decomposition Struc-
ture // Autom. Remote Control. 2012. V. 73. No. 1. P. 118-133.
10.
Афраймович Л.Г. Многоиндексные транспортные задачи с 2-вложенной струк-
турой // АиТ. 2013. № 1. С. 116-134.
Afraimovich L.G. A Multiindex Transportation Problems with 2-embedded Struc-
ture // Autom. Remote Control. 2013. V. 74. No. 1. P. 90-104.
11.
Афраймович Л.Г. Трехиндексные задачи линейного программирования с вло-
женной структурой // АиТ. 2011. № 8. С. 109-120.
Afraimovich L.G. Three-Index Linear Programs with Nested Structure // Autom.
Remote Control. 2011. V. 72. No. 8. P. 1679-1689.
12.
Balas E., Saltzman M.J. An Algorithm for the Three-Index Assignment Problem //
Oper. Res. 1991. V. 39. No. 1. P. 150-161.
13.
Huang G., Lim A. A hybrid genetic algorithm for the Three-Index Assignment
Problem // Eur. J. Oper. Res. 2006. V. 172. P. 249-257.
14.
Kim B.J., Hightower W.L., Hahn P.M., Zhu Y.R., Sun L. Lower bounds for the axial
three-index assignment problem // Eur. J. Oper. Res. 2010. V. 202. P. 654-668.
15.
Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов ре-
шения трехиндексной планарной проблемы выбора // Журн. вычисл. мат., мат.
физики. 2006. Т. 46. 2. С. 222-228.
16.
Думбадзе Л.Г., Леонов В.Ю., Тизик А.П., Цурков В.И. Декомпозиционный ме-
тод решения трехиндексной задачи о назначениях // Изв. РАН. Теория и систе-
мы управления. 2020. № 5. С. 56-59.
17.
Гимади Э.Х., Глазков Ю.В. Об асимптотически точном алгоритме решения од-
ной модификации трехиндексной планарной задачи о назначениях // Дискрет.
анализ и исследование операций. Сер. 2. 2006. Т. 13. 1. С. 10-26.
18.
Magos D. Tabu search for the planar three-index assignment problem // J. Global
Optim. 1996. V. 8. P. 35-48.
19.
Прилуцкий М.Х. Программные управления двухстадийными стохастическими
производственными системами // АиТ. 2020. № 1. С. 81-92.
Prilutskii M.Kh. Programmed Control of Two-Stage Stochastic Production
Systems // Autom. Remote Control. 2020. V. 81. P. 64-73.
20.
Прилуцкий М.Х. Оптимальное управление двухстадийными стохастическими
производственными системами // АиТ. 2018. № 5. С. 69-82.
Prilutskii M.Kh. Optimal Control for Two-Stage Stochastic Production Systems //
Autom. Remote Control. 2018. V. 79. P. 830-840.
21.
Прилуцкий М.Х. Оптимальное планирование двухстадийных стохастических
производственных систем // АиТ. 2014. № 8. С. 37-47.
Prilutskii M.Kh. Optimal Planning for Two-Stage Stochastic Industrial Systems //
Autom. Remote Control. 2014. V. 75. P. 1384-1392.
167
22. Karapetyan D., Gutin D. A New Approach to Population Sizing for Memetic
Algorithms: A Case Study for the Multidimensional Assignment Problem //
Evolutionary Computation. 2011. V. 19. No. 3. P. 345-371.
23. Медведев С.Н., Медведева О.А. Адаптивный алгоритм решения аксиальной
трехиндексной задачи о назначениях // АиТ. 2019. № 4. С. 156-172.
Medvedev S.N., Medvedeva O.A. An Adaptive Algorithm for Solving the Axial Three-
Index Assignment Problem // Autom. Remote Control. 2019. V. 80. P. 718-732.
24. Gabrovšek B., Novak T., Povh J., Rupnik Poklukar D.,
Žerovnik J. Multiple
Hungarian Method for k-Assignment Problem // Mathematics. 2020. V. 8. 2050.
Статья представлена к публикации членом редколлегии А.А. Лазаревым.
Поступила в редакцию 05.11.2020
После доработки 11.01.2021
Принята к публикации 16.03.2021
168
