«ПОТОКОВЫЕ МЕТОДЫ РЕШЕНИЯ МНОГОИНДЕКСНЫХ ЗАДАЧ ТРАНСПОРТНОГО ТИПА ...»

элемент FN ( s ) E N ( S ) однозначным образом представим в виде FN ( s ) Ff1... Ffk, где По построению C (G) {CFN ( s ) | FN ( s ) E N ( s ) }. Тогда определим функцию следующим образом: каждой переменной x FN ( s ) поставим в соответствие простой цикл CFN ( s ), Покажем, что построенная задача z совместна тогда и только тогда, когда совместна исходная задача w. Действительно, пусть x FN ( s ), FN ( s ) E N ( s ) – допустимое решение системы ограничений задачи w. Определим yC FN ( s ) xFN ( s ), FN ( s ) E N ( s ), далее G и по построению:

Тогда в соответствии с введенной функцией набор zij, (i, j ) A, будет являться допустимой циркуляцией задачи z.

Далее, пусть zij, (i, j ) AG – допустимая циркуляция задачи v. Согласно теореме 2.4, для данной циркуляции существует ее циклическая декомпозиции y C, C C (G).

Согласно введенной функции, построим следующий набор значений переменных:

Отсюда построенный набор является допустимым решением задачи w.

C C (G) – ее циклическая декомпозиция. Используя функцию, построим следующий набор значений переменных xFN ( s ) yC FN ( s ), FN ( s ) E N ( s ), который (как уже было показано) является допустимым решением задачи w. Теперь покажем от противного, что построенный набор будет оптимальным решением задачи w. Действительно, пусть это не так и x N ( s ), FN ( s ) EN ( s ) – оптимальное решение задачи w. Тогда по предположению таким образом набор e z, получаем противоречие. Таким образом, предположение неверно, и построенный набор xFN ( s ), FN ( s ) E N ( s ), является оптимальным решением задачи w.

Далее проведем анализ сложности вычислительных процедур, связанных с построением задачи z и построением решения задачи w по решению задачи z. Заметим, что исходная задача w содержит | E N (s ) | переменных. По построению граф G в задаче z Применяя леммы 5.1 и 5.2, можно получить следующие оценки | V | O(| E N (s ) |), | A | O(| EN (s ) |).

Отсюда построение задачи z требует линейных от размера матрицы Matr (w) вычислительных операций. Схема построения решения задачи w по решению задачи z циклической декомпозиции циркуляции, которое, согласно утверждению 2.6, требует O(| V || A |) O(| E N (s ) | 2 ) вычислительных операций. Отсюда класс W (M, H ) является L | L equal || E N ( s ) |2 cycle сводимым к классу WGraph. Теорема доказана.

Конструктивная схема доказательства теоремы 5.2 позволят для задач класса W (M, H ) и для систем линейных неравенств класса D(M ), где M и H являются алгоритм решения, основанный на сводимости к классу WGraph.

Алгоритм 5.1. Решение многоиндексных задач с декомпозиционной структурой.

Вход. Задача wW (M, H ) (система w D(M ) ), где M и H являются f1,..., f k декомпозиционными, f1,..., f k – разбиение множества N (s).

Шаг 1. Используя конструктивную схему, применяемую при доказательстве теоремы 5.2, построить задачу z WGraph, соответствующую w. Перейти на шаг 2.

Шаг 2. Найти решение (допустимое решение) задачи z, используя алгоритм 2.2.

(алгоритм 2.1). Если задача z несовместна, то w также несовместна, и алгоритм завершен; иначе переход на шаг 3.

Шаг 3. Построить циклическую декомпозицию решения, найденного на шаге 2, применяя алгоритм 2.7. Перейти на шаг 4.

Шаг 4. Используя отображение, описанное при доказательстве теоремы 5.2, найти решение w согласно определению 5.1. Алгоритм завершен.

Матрица системы ограничений задачи z WGraph абсолютно унимодулярна, поэтому для совместной задачи z с целочисленными параметрами гарантируется существование целочисленного решения [51]. При этом конструктивная схема построения задачи z, применяемая при доказательстве теоремы 5.2, гарантирует целочисленность ее параметров при целочисленности параметров задачи (системы) w. Согласно следствию 2.3, для произвольной целочисленной циркуляции ее циклическая декомпозиция, построенная алгоритмом 2.7 (применяемым на шаге 3 алгоритма 5.1), является целочисленной. Отсюда на шаге 4 алгоритма 5.1 в случае целочисленности решения задачи z решение задачи (системы) w также является целочисленным. Отсюда алгоритм 5.1 применим также при исследовании целочисленных задач: WZ (M, H ) и DZ (M ). Как уже было отмечено при построении алгоритма 4.1, если w WZ (M, H ) ( w DZ (M ) ) содержит нецелочисленные свободные коэффициенты, то в силу целочисленности коэффициентов матрицы системы ограничений w, задача (система) w при помощи округления параметров может быть преобразована к эквивалентной постановке с целочисленными параметрами.

Заметим, что для задачи z zMCC (G; lij, uij, eij, (i, j ) AG ) WGraph, соответствующей | AG | O(| EN (s ) |). Отсюда с учетом утверждений 2.1, 2.2, 2.6 можно сформулировать следующее следствие.

Следствие 5.4. Пусть M, H 2 N ( s ), множества M и H являются f1,..., f k декомпозиционными, f1,..., f k – разбиение множества N (s). Тогда алгоритм 5.1 решения задач класса W (M, H ) и класса WZ (M, H ) (систем класса D(M ) и класса DZ (M ) ) требует ( (O(| EN ( s ) |), O(| EN ( s ) |)) + O(| EN (s ) |2 )) вычислительных операций.

Здесь, напомним, (n, m) и (n, m) – количество вычислительных операций алгоритма решения задачи поиска максимального потока и алгоритма решения задачи поиска потока минимальной стоимости заданной величины соответственно в сети с n вершинами и m дугами. Применим, как и при исследовании алгоритма 4.1, для поиска потока минимальной стоимости заданной величины алгоритм, предложенный в работе Орлина [172], для поиска максимального потока воспользуемся алгоритмом СлейтораТарьяна [181]. Тогда, согласно следствию 5.4, можно сформулировать следующее утверждение.

Утверждение 5.1. Пусть M, H 2 N ( s ), множества M и H являются f1,..., f k декомпозиционными, f1,..., f k – разбиение множества N (s). Тогда существует алгоритм решения задач класса W (M, H ) и класса WZ (M, H ) (систем класса D(M ) и класса DZ (M ) ), требующий O(| E N ( s ) |2 log 2 | E N ( s ) |) ( O(| EN ( s ) |2 log | EN ( s ) |) ) вычислительных операций.

Схема L | L equal || E N ( s ) |2 cycle сводимости, предложенная при доказательстве теоремы 5.2, также является схемой P* | P* equal | P* cycle сводимости. На основании теоремы 5.1 справедливо следующее следствие.

целочисленного линейного программирования WZ (M, H ) разрешим за полиномиальное время.

Таким образом, полученные результаты сводимости позволили выделить новый полиномиально разрешимый подкласс WZ (M, H ), сформулированный в следствие 5.5, в NP-трудном классе многоиндексных задач целочисленного линейного программирования.

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

j1J1 j2 J 2 j3J M {{3},{1,2},{1,3},{2,3}} и s 3. Многоиндексная матрица стоимостей {cFN ( s ) } задачи (5.1)-(5.6), определяемая выражением u j2 j3 v j2 w j3, может быть представлена в виде Несложно увидеть, что M, H { f i | i 1,3} { f i f i1 | i 1,2} и, согласно определению 5.2, множества M и H являются {1},{2},{3} -декомпозиционными. Отсюда, согласно теореме 5.2, класс W (M, H ) является L | L equal || E N ( s ) |2 cycle сводимым к классу WGraph, здесь конструктивном доказательстве теоремы 5.2, на примере задачи (5.1)-(5.6). Пусть | J1 || J 2 || J 3 | 2. Приведем транспортную сеть, определяющую задачу поиска потока минимальной стоимости, соответствующую исходной многоиндексной задаче.

На рисунке 5.2 для ряда дуг приведены их пропускные способности и стоимости. Дуги, у неограниченную верхнюю пропускные способности. Дуги, у которых не указаны стоимости, имеют нулевую стоимость. Согласно доказательству теоремы 5.2 и алгоритму 5.1, решение исходной многоиндексной задачи определяется следующим образом: каждой переменной x j1 j2 j3 многоиндексной задачи (5.1)-(5.6) присваивается значение потока вдоль соответствующего простого цикла (s, v( j1 ){1}, v(j1 ){1}, v( j2 ){2}, v(j2 ){2}, v( j3 ){3}, v(j3 ){3}, t, s), которое, в свою очередь, получается в результате циклической декомпозиции потока минимальной стоимости данной сети.

Далее проиллюстрируем применимость метода исследования декомпозиционных многоиндексных W (M, H ), основанного на сводимости к классу задач поиска потока в сети, при решении ряда рассмотренных ранее многоиндексных задач. Пусть M 2 N ( s ) и множества M и H являются f1,..., f k -декомпозиционными, где f1,..., f k – разбиение множества N (s). Согласно теореме 5.2, класс задач W (M, H ) сводим к поиску потока в сети с O(| EN (s ) |) вершинами и O(| EN (s ) |) дугами. В рамках исследуемой схемы сведения ограничения исходной многоиндексной задачи. В случае несовместности ограничений потоковой задачи для ее исследования может быть применен, как и при обосновании утверждения 4.4, алгоритм поиска потока в несовместной сети.

декомпозиционным, где f1,..., f k – разбиение множества N (s). Тогда существует алгоритм операций.

утверждениям 4.5 и 4.6, используя утверждение 5.1, справедливо:

Утверждение 5.3. Пусть M, H 2 N ( s ) и множество M H является f1,..., f k декомпозиционным, где f1,..., f k – разбиение множества N (s). Тогда существует алгоритм решения задач класса U (M, H ), требующий O(| EN ( s ) |3 log | EN ( s ) | log p) вычислительных операций.

Утверждение 5.4. Пусть M, H 2 N ( s ) и множество M H является f1,..., f k декомпозиционным, где f1,..., f k – разбиение множества N (s). Тогда существует алгоритм вычислительных операций.

Дополнительно проиллюстрируем полученные результаты при решении ряда прикладных многоиндексных задач, поставленных в главе 1. Общая математическая модель проблемы объемно-календарного планирования переработки газового конденсата (1.19)-(1.22) относится к классу D(M ), где M {{i, j},{i, p},{ j, k, p, t}}. При этом s 5, N (s) {i, j, k, p, t} и | EN ( s ) || I || J || K || P || T |. Рассмотрим разбиение f1 {i}, f 2 { j}, f3 {k, t}, f 4 { p} множества N (s). Заметим, что, согласно определению 5.2, множество M является {i},{ j},{k, t},{ p} -декомпозиционным, т.к. M { fi | i 1,4} { f i f i1 | i 1,3}.

Отсюда, согласно утверждению 5.1, система (1.19)-(1.22) может быть решена, используя O(| I |2 | J |2 | K |2 | P |2 | T |2 log(| I || J || K || P || T |)) вычислительных операций. Ранее были переработки газового конденсата, различающиеся выбором критерия. Задача (1.19)относится к классу W (M, H1 ), где H1 {{k, p, t}}. Легко увидеть, что, согласно определению 5.2, множество H1 является {i},{ j},{k, t},{ p} -декомпозиционным, т.к. H1 { f i | i 1,4} { f i f i1 | i 1,3}. Задача (1.19)-(1.22),(1.24) относится к классу W (M, H 2 ) W (M, H 2 ), где H 2 {{ j, k, t}} и множество H 2 является {i},{ j},{k, t},{ p} декомпозиционным по определению 5.2. Задача (1.19)-(1.22),(1.25) относится к классу W (M, H 3 ), где H 3 {{i, j}}. Согласно определению 5.2, множество H 3 является {i},{ j},{k, t},{ p} -декомпозиционным. Задача (1.19)-(1.22),(1.26) относится к классу декомпозиционным по определению 5.2. Задача (1.19)-(1.22),(1.27) относится к классу выполняется W (M, H 6 ) W (M, H 6 ), где H 6 {{i, j},{ j, k, t},{k, p, t}} и H 6 является {i},{ j},{k, t},{ p} -декомпозиционным по определению 5.2. Отсюда, согласно утверждению 5.1, рассмотренные задачи объемно-календарного планирования переработки газового | I |2 | J |2 | K |2 | P |2 | T |2 log 2 (| I || J || K || P || T |) вычислительных операций.

Задача составления рассписания занятий (1.29)-(1.36), как было показано в главе 3, относится к классу W (M, H ), M {{i, j},{ j, k},{k, t},{i, k, t}}, H {{i, j},{i, t},{k, t}}.

При этом s 4, N (s) {i, j, k, t} и | EN ( s ) || I || J || K || T |. Рассмотрим разбиение f1 { j}, f 2 {i}, f 3 {t}, f 4 {k} множества N (s). Заметим, что, согласно определению 5.2, O(| I |2 | J |2 | K |2 | T |2 log 2 (| I || J || K || T |)) вычислительных операций. Предлагаемый метод решения задачи составления расписания основан на полученных результатах сводимости многоиндексных задач к классу задач поиска потока в сети. Отметим, что в ряде случаев анализ схемы сведения для конкретных прикладных задач приводит к уточнению оценок сложности алгоритма. Так, применяя схему сведения, описанную при доказательстве AG предварительно исключили дуги с нулевой верхней пропускной способностью.

следствию 5.4, задача составления расписания занятий (1.29)-(1.36) может быть решена, O(d 2 log 2 d ) вычислительных операций, что уточняет полученную в используя утверждение 5.1 общую оценку сложности алгоритма.

5.3. Декомпозиционные NP-трудные многоиндексные задачи В общей постановке класс целочисленных многоиндексных транспортных задач является NP-трудным уже в трехиндексном случае [52]. Для задач данного класса не существует полиномиальных результат также справедлив уже в трехиндексном случае [131]. Более того, можно показать отсутствие эффективных приближенных алгоритмов для класса целочисленных многоиндексных задач, обладающих определенными декомпозиционными свойствами.

Сформулируем используемое определение -приближенного алгоритма, приведенное в [52]. Пусть W – класс задач минимизации; V – алгоритм, который для любой задачи w W возвращает допустимое решение V (w) задачи w ; c(V ( w)) – значение критерия задачи w на допустимом решении V (w) ; OPT (w) – оптимальное значение критерия задачи w. Тогда алгоритм V будем называть -приближенным алгоритмом для задач класса W, где – неотрицательная константа, если выполняется следующее условие:

Рассмотрим далее ряд декомпозиционных классов многоиндексных задач, связанные с ними вопросы сложности и вопросы построения приближенных алгоритмов, основанных на полученных результатах t1 | t 2 equal | t3 cycle сводимости.

разбиение множества N (s), k 3. Тогда для задач класса WZ (M, H ) не существует полиномиального -приближенного алгоритма для любых 0, иначе P NP.

Доказательство. Проведем доказательство от противного. Пусть выполняются условия утверждения, и для задач класса WZ (M, H ) существует полиномиальный приближенный алгоритм для некоторого 0.

Рассмотрим трехиндексную аксиальную задачу о назначениях с матрицей стоимостей специального вида. Пусть m N, uij1), uip2), u (jp) 0, i, j, p 1, m. Тогда задача ставится как следующая задача целочисленного линейного программирования:

В [131] было показано, что для класса задач (5.7)-(5.11) не существует полиномиального приближенного алгоритма для любых 0, иначе P=NP.

Несложно увидеть, что если k 3, то класс WZ (M, H ) включает в себя класс задач (5.7)-(5.11). Отсюда из существования полиномиального -приближенного алгоритма для задач класса WZ (M, H ) следует существование полиномиального -приближенного алгоритм для класса задач (5.7)-(5.11). Получаем противоречие. Далее пусть k 4.

уменьшая общности, будем считать, что такой выбор возможен). Перенумеруем элементы FN ( s ) EN ( s ), где {d F }, f H – заданные матрицы коэффициентов. Определим значения свободных коэффициентов двусторонних неравенств в задаче w следующим образом:

Матрицы {d F f }, f H, задающие матрицу коэффициентов целевой функции {cFN ( s ) }, определим следующим образом:

Пусть yijp, i, j, p 1, m, и u * – оптимальное решение и оптимальное значение критерия задачи (5.7)-(5.11) соответственно. Т.к. f1,..., f k – разбиение множества N (s), то Рассмотрим многоиндексную матрицу {xFN ( s ) }, построенную по следующему правилу:

FN ( s )EN ( s ) предположению. Тогда рассмотрим набор Несложно увидеть, что yijp, i, j, p 1, m, является допустимым решением задачи (5.7)m m m является оптимальным решением задачи. Получаем противоречие, предположение неверно и, следовательно, {xFN ( s ) } является оптимальным решением задачи w. Таким образом, оптимальное значение критерия задачи w равно u *.

полиномиальный -приближенный алгоритм. Пусть {x N ( s ) } решение найденное данным FN ( s )EN ( s ) выше оценке. Тогда набор yijp x ( i ) F ( j ) F ( p ) F ( i )...F ( i ), i, j, p 1, m, будет являться допустимым Отсюда для класса задач (5.7)-(5.11) существует полиномиальный -приближенный алгоритм, заключающийся в построении задачи w по описанной выше схеме, ее решении полиномиальным -приближенным алгоритмом и построении приближенного решения исходной задачи по описанному выше правилу. Получаем противоречие, предположение неверно. Утверждение доказано.

H { fi fi mod k 1 | i 1, k}, f1,..., f k – разбиение множества N (s). Тогда класс задач WZ (M, H ) включен в класс WZ (M ). Отсюда, согласно утверждению 5.5, справедливо:

разбиение множества N (s), k 3. Тогда для задач класса WZ (M ) не существует N (s), k 3. Тогда рассмотрим класс задач WZ (M ). Согласно утверждению 5.6, для данного класса не существует полиномиальных выполнении известной гипотезы о неравенстве классов P и NP. Данный факт обуславливает поиск эвристических методов решения задач класса WZ (M ). В качестве такого метода может быть предложен следующий алгоритм, основанный на полученном в теореме 5.2 результате сводимости. Идея алгоритма заключается в выборе среди задач, для которых могут быть применены результаты сводимости, задачи наиболее «близкой» к исходной задаче.

Алгоритм 5.2. Эвристический алгоритм решение многоиндексных задач с декомпозиционной системой ограничений.

многоиндексные матрицы {d F f }, f H, и связанную с ними многоиндексную матрицу {eFN ( s ) } как решение следующей оптимизационной задачи где dist некоторая функция «близости» многоиндексных матриц. Перейти на шаг 2.

алгоритм 5.1. Полученное решение будет являться приближенным решением задачи w.

Алгоритм завершен.

H { fi | i 1, k} { fi fi 1 | i 1, k 1}. Согласно определению 5.2, множества M и H являются решения задачи w может быть применен алгоритм 5.1. Системы ограничений задач w и w совпадают. Тем самым решение задачи w будет являться допустимым решением задачи w.

Конкретная реализация алгоритма 5.2 определяется выбором функции близости dist. Так в качестве такой меры близости может быть выбрана сумма квадратов отклонений компонент матриц. Тогда задача (5.12),(5.13) может быть поставлена как следующая задача квадратичной безусловной оптимизации:

Для решения задачи (5.14) может быть применен метод минимизации суммы квадратов невязок [60]. Алгоритм 5.2 с использованием на шаге 1 решения задачи (5.14) будем называть алгоритмом 5.2 с минимизацией сумм квадратов отклонений.

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

Далее алгоритм 5.2 с использованием на шаге 1 решения задачи (5.15),(5.16) будем называть алгоритмом 5.2 с минимизацией максимума относительного отклонения. Для решения задачи (5.15),(5.16) могут быть применены общие методы решения задач линейного программирования [102]. Для приближенного алгоритма 5.2 с минимизацией максимума относительного отклонения справедлива следующая оценка отклонения от оптимума.

Теорема 5.3. Пусть c * – оптимальное значение критерия задачи w, c – значение минимизацией максимума относительного отклонения, * – оптимальное значение w WZ (M ), M { fi | i 1, k} { fi fi 1 | i 1, k 1}, где f1,..., f k – разбиение множества Доказательство. Пусть w wZ (s; M ; n1,..., ns ;{aFf },{bFf }, f M ;{cFN ( s ) }) WZ (M ) и {xFN ( s ) } – оптимальное решения задачи w, {x N ( s ) } – приближенное решение задачи w, найденное алгоритмом 5.2 с минимизацией максимума относительного отклонения. Тогда Согласно условию (3.2) выполняется x N ( s ), xFN ( s ) 0, FN ( s ) E N ( s ). Согласно (5.15) Теорема доказана.

Заметим, что оценка отклонения от оптимума, сформулированная в теореме 5.3, не является константой, т.к. зависит от исходных данных задачи w. Обратное, согласно утверждению 5.6, означало бы равенство классов P и NP.

разбиение множества N (s), k 3. Тогда класс задач WZ (M, H ) является NP -трудным.

трехиндексную аксиальную задачу о назначениях (5.7)-(5.11), матрица стоимостей которой удовлетворяет неравенству треугольника:

В [131] было показано, что класс задач (5.7)-(5.11) с матрицей стоимостей, доказательство путем полиномиального сведения к классу WZ (M, H ) класса задач (5.7)с матрицей стоимостей, удовлетворяющей условию (5.17)-(5.19).

Несложно увидеть, что если k 3, то класс WZ (M, H ) включает в себя класс задач (5.7)-(5.11) с матрицей стоимостей, удовлетворяющей условию (5.17)-(5.19). Отсюда класс WZ (M, H ) является NP-трудным.

Далее пусть k 4. Рассмотрим задачу (5.7)-(5.11) с матрицей стоимостей, w wz (s; M ; n1,..., ns ;{aFf },{bFf }, f M ;{cFN ( s ) }) WZ (M, H ) такую, что | E fl | m, l 1, k (не уменьшая общности, будем считать, что такой выбор возможен). Перенумеруем элементы FN ( s ) EN ( s ), где {d F f }, f H – заданные матрицы коэффициентов. Определим значения свободных коэффициентов двусторонних неравенств в задаче wZ следующим образом:

Матрицы {d F f }, f H, задающие матрицу коэффициентов целевой функции {cFN ( s ) }, определим следующим образом:

где 1 (uij1) uip2) u (jp) ). Заметим, что f1,..., f k – разбиение множества N (s) и таким образом, EN ( s ) {Ff(1i1 )...Ff(kik ) | il 1, m, l 1, k}. По построению Следовательно, матрица коэффициентов целевой функции удовлетворяет обобщенному неравенству треугольника (3.5). Отсюда w WZ (M, H ).

Пусть {xF N ( s ) } является оптимальным решением задачи w. Тогда покажем от противного, что выполняется следующее условие:

Предположим, что найдутся i1,..., ik {1,..., m} и l {4,..., k}, что xF ( i1 )...F ( ik ) 1. Тогда по построению Определим {xFN ( s ) } следующим образом:

Несложно увидеть, что {xFN ( s ) } является допустимым решением задачи w и Получаем противоречие, предположение неверно. Следовательно, условие (5.20) выполняется.

i, j, p 1, m. Согласно условию (5.20) набор yijp, i, j, p 1, m, является допустимым Докажем от противного, что yijp, i, j, p 1, m, является оптимальным решением задачи (5.7)-(5.11). Предположим, что yijp, i, j, p 1, m, – оптимальное решение задачи (5.7)и выполняется Тогда построим {xFN ( s ) } следующим образом Несложно увидеть, что {xFN ( s ) } является допустимым решением задачи w и Отсюда Однако {xF N ( s ) } является оптимальным решением задачи w. Получаем противоречие, предположение неверно. Следовательно, yijp, i, j, p 1, m, – оптимальное решение задачи (5.7)-(5.11).

Таким образом, NP-трудный класс класса задач (5.7)-(5.11) с матрицей стоимостей, удовлетворяющей условию (5.17)-(5.19) полиномиально сводим к классу WZ (M, H ).

Отсюда класс WZ (M, H ) является NP-трудным [52]. Утверждение доказано.

множества N (s), k 3. Тогда, согласно утверждению 5.5, для задач класса WZ (M, H ) не существует полиномиального P NP. Рассмотрим подкласс WZ (M, H ), содержащий задачи класса WZ (M, H ), удовлетворяющие обобщенному неравенству треугольника (3.5). Согласно утверждению приближенных методов решения задач класса WZ (M, H ). В качестве такого метода может быть предложен следующий алгоритм, основанный на полученном в теореме 5. результате сводимости.

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

Шаг 1. Пусть {d F f }, f H – заданные многоиндексные матрицы такие, что образом и обозначим wi wZ (s; M ; n1,..., n2 ;{aF },{bF }, f M ;{cFi ) }), i 1, k. Переход на шаг 2.

Шаг 2. Решим задачу wi при помощи алгоритма 5.1, если задача wi несовместна, то задача w также несовместна и алгоритм завершен, i 1, k. Далее пусть {xFiN) ( s ) } – оптимальное решение задачи wi, i 1, k. Переход на шаг 3.

Тогда {xFiN )s ) } является приближенным решением задачи w. Алгоритм завершен.

Далее приведем обоснование корректности алгоритма 5.3 и покажем, что рассматриваемого класса WZ (M, H ).

Доказательство. Пусть выполняются условия леммы. Обозначим через x(i ) оптимальное решение задачи min{(ci, x) | Ax b, x Z }, i 0, l. Тогда выполняется Отсюда Лемма доказана.

множества N (s), k 3. Тогда алгоритм 5.3 является (k 2) / k -приближенным алгоритмом для задач класса WZ (M, H ).

шагу 1 алгоритма, строятся k задач wi wZ (s; M ; n1,..., n2 ;{aF },{bF }, f M ;{cFi ) }), где многоиндексная матрица {cFiN) ( s ) } определяется согласно соотношению (5.21), i 1, k.

Пусть i {1,..., k}. Рассмотрим задачу wi. Обозначим H i H \ { fi fi mod k 1}. По построению wi WZ (M, H i ). Согласно определению 5.2, множества M и H i являются fi1,..., f k, f1,..., fi -декомпозиционными. Следовательно, алгоритм 5.1 может быть применен для решения задачи wi на шаге 2. Системы ограничений задач w и wi совпадают, таким образом, задача w совместна тогда и только тогда, когда совместна задача wi.

Далее пусть {xFiN) ( s ) } является оптимальным решением задачи wi, i 1, k, {xFN ( s ) } – оптимальным решением задачи w. Т.к. системы ограничений задач w и wi совпадают, то {xFiN) ( s ) } является допустимым решением задачи Отсюда, согласно лемме 5.3, Покажем от противного, что предположение неверно и соотношение (5.22) выполняется.

С другой стороны, согласно обобщенному неравенству треугольника (3.5) выполняется Следовательно, Тогда, в силу ограничения неотрицательности переменных (3.2), выполняется Отсюда с использованием соотношения (5.22) Следовательно, алгоритм 5.3 является (k 2) / k -приближенным алгоритмом для задач класса W (M, H ). Теорема доказана.

Алгоритм 5.3 основан на решении k задач, каждая из которых может быть решена алгоритмом 5.1. При этом т.к. f1,..., f k – разбиение множества N (s), то k s. Тогда на основании утверждения 5.1 справедлива следующая оценка сложности алгоритма 5.3.

разбиение множества N (s), k 3. Тогда алгоритм 5.3 поиска приближенного решения задач класса WZ (M, H ) требует O(| E N ( s ) |2 log 2 | E N ( s ) |) вычислительных операций.

Заметим, что построенный (k 2) / k -приближенный алгоритм для задач класса W (M, H ) обобщает, полученный в работе [131] результат, связанный с построением приближенного алгоритма для трехиндексных аксиальных задач о назначениях, трехиндексных аксиальных задач о назначениях, удовлетворяющих неравенству В данном случае алгоритм 5.3 будет представлять собой 1/3-приближенный алгоритм для класса трехиндексных аксиальных задач о назначениях, удовлетворяющих неравенству треугольника. Данная оценка для рассматриваемой задачи о назначениях совпадает с оценкой, полученной в [131]. Однако в отличие от метода, предложенного в работе [131], алгоритм 5.3 применим при исследовании гораздо более широкого класса задач – целочисленных многоиндексных задач линейного программирования транспортного типа, обладающих декомпозиционной структурой и удовлетворяющих обобщенному неравенству треугольника.

Выводы Предложена схема t1 | t2 equal | t3 cycle сводимости (сводимости с сохранением соответствия циклов) класса задач линейного программирования к классу задач поиска потока в сети WGraph. При исследовании t1 | t2 equal | t3 cycle сводимости класса W (M ) к классу WGraph установлено:

– для того, чтобы класс W (M, H ) являлся L | L equal || E N ( s ) |2 cycle сводимым к классу WGraph, достаточно, чтобы множества M и H были f1,..., f k -декомпозиционными;

– пусть множества M, H являются f1,..., f k -декомпозиционными, тогда существует алгоритм решения задач класса W (M, H ) и систем класса D(M ), требующий соответственно, данный алгоритм применим при исследовании целочисленного случая, что позволяет выделить новый полиномиально разрешимый подкласс в NPтрудном классе многоиндексных задач целочисленного линейного программирования;

– пусть множество M является f1,..., f k -декомпозиционным, тогда существует алгоритм решения задач класса S (M ), требующий O(| E N ( s ) |2 log 2 | E N ( s ) |) вычислительных операций;

– пусть множество M H является f1,..., f k -декомпозиционным, тогда существуют алгоритмы решения задач класса U (M, H ) и задач класса U max min (M, H ), требующие O(| EN ( s ) |3 log | EN ( s ) | log p) и O(| EN ( s ) |2 log | EN ( s ) | log p) вычислительных операций соответственно;

где f1,..., f k – разбиение множества N (s).

Результаты исследования t1 | t2 equal | t3 cycle сводимости применены также при построении приближенных алгоритмов решения ряда NP-трудных многоиндексных задач, обладающих декомпозиционной структурой:

– рассмотрен класс задач WZ (M ), для которого не существует полиномиального P NP, отклоняющееся от оптимального значения критерия не более чем в * раз, где * является оптимальным значение критерия вспомогательной задачи линейного программирования;

H { f i f i mod k 1 | i 1, k} ; для задач класса WZ (M, H ) предложен полиномиальный (k 2) / k -приближенный алгоритм;

где f1,..., f k – разбиение множества N (s), k 3.

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

– сводимость с сохранением соответствия ребер ( t1 | t 2 equal | t3 edge сводимость), – сводимость с сохранением соответствия циклов ( t1 | t2 equal | t3 cycle сводимость).

При исследовании t1 | t 2 equal | t3 edge сводимости класса многоиндексных задач W (M ) к классу задач поиска потока минимальной стоимости в сети WGraph был получен исчерпывающий ответ вопроса сводимости:

– для того, чтобы класс W (M ) являлся L | L equal | L edge сводимым к классу WGraph, достаточно, чтобы множество M было 2-вложенным, – для того, чтобы класс W (M ) являлся t1 | t 2 equal | t3 edge сводимым к классу WGraph, необходимо, чтобы множество M было 2-вложенным.

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

– задач класса W (M ) и систем класса D(M ), а также задач соответствующих целочисленных классов WZ (M ) и DZ (M ), где множество M является 2-вложенным, – задач класса S (M ), где множество M является 2-вложенным, – задач класса U (M, H ) и задач класса U max min (M, H ), где множество M H является 2-вложенным.

При исследовании t1 | t 2 equal | t3 edge сводимости класса многоиндексных задач W (M ) к классу задач поиска потока минимальной стоимости в древовидной сети WTree был также получен исчерпывающий ответ вопроса сводимости:

– для того, чтобы класс W (M ) являлся L | L equal | L edge сводимым к классу WTree, достаточно, чтобы множество M было 1-вложенным, – для того, чтобы класс W (M ) являлся t1 | t 2 equal | t3 edge сводимым к классу WTree, необходимо, чтобы множество M было 1-вложенным.

Предложенная конструктивная схема сводимости класса W (M ) в случае 1-вложенности множества M здесь также является оптимальной. Были разработаны алгоритмы решения следующих многоиндексных задач, основанные на полученных результатах сводимости:

– задач класса W (M ) и систем класса D(M ), а также задач соответствующих целочисленных классов WZ (M ) и DZ (M ), где множество M является 1-вложенным, – задач класса U (M, H ) и задач класса U max min (M, H ), где множество M H является 1-вложенным.

Была предложена схема t1 | t2 Z | t3 Z сводимости класса W (M ) к классу WGraph, являющаяся обобщением схемы t1 | t 2 equal | t3 edge сводимости. При исследовании t1 | t2 Z | t3 Z сводимости класса многоиндексных задач W (M ) к классу задач поиска потока минимальной стоимости в сети WGraph были получены следующие результаты:

– для того, чтобы класс W (M ) являлся L | L Z | L Z сводимым к классу WGraph, достаточно, чтобы множество M было 2-вложенным, – для того, чтобы класс W (M ) являлся P | P Z | P Z сводимым к классу WGraph, необходимо и достаточно, чтобы множество M было 2-вложенным, в противном случае P=NP.

При исследовании t1 | t2 equal | t3 cycle сводимости класса многоиндексных задач W (M, H ) к классу задач поиска потока минимальной стоимости в сети WGraph было сводимым к классу WGraph, достаточно, чтобы множество чтобы множества M и H были разработаны алгоритмы решения следующих многоиндексных задач, основанные на полученных результатах сводимости:

– задач класса W (M, H ) и систем класса D(M ), а также задач соответствующих целочисленных классов WZ (M, H ) и DZ (M ), где множества M и H являются f1,..., f k -декомпозиционными, – задач класса S (M ), где множество M является f1,..., f k -декомпозиционным;

– задач класса U (M, H ) и задач класса U max min (M, H ), где множество M H является f1,..., f k -декомпозиционным, здесь f1,..., f k – разбиение множества N (s). Построенные результаты позволили выделить новый полиномиально разрешимый класс (класс WZ (M, H ), где множества M и H являются f1,..., f k -декомпозиционными, f1,..., f k – разбиение множества N (s) ) в NPтрудном классе многоиндексных задач целочисленного линейного программирования.

Полученные результаты сводимости применены также при построении приближенных декомпозиционной структурой:

– рассмотрен класс задач WZ (M ), для которого не существует полиномиального P NP, отклоняющееся от оптимального значения критерия не более чем в * раз, где * является оптимальным значение критерия вспомогательной задачи линейного программирования;

H { fi fi mod k 1 | i 1, k} ; для задач класса WZ (M, H ) предложен полиномиальный (k 2) / k -приближенный алгоритм;

здесь f1,..., f k – разбиение множества N (s), k 3.

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

Список литературы 1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. – М.: Наука. 1975.

2. Афраймович Л.Г. Задача поиска потока в несовместной транспортной сети // Проблемы теоретической кибернетики. Тезисы докладов международной конференции. 2008. С. 8.

3. Афраймович Л.Г. Задачи распределения однородного ресурса в иерархических системах // VIII Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров. 2003. C. 41–42.

4. Афраймович Л.Г. Задачи распределения однородного ресурса в многоуровневых иерархических системах // IX Нижегородская сессия молодых ученых. Технические науки.

Тезисы докладов. Нижний Новгород. 2004. C. 5–6.

транспортных задач с декомпозиционной структурой // Доклады Одесского семинара по дискретной математике. 11. 2011. С. 4–14.

6. Афраймович Л.Г. Минимизация затрат при распределении однородного ресурса в иерархических системах с двусторонними ограничениями // КоГраф 2002. Материалы докладов всероссийской конференции. – Нижний Новгород. 2002. C. 81–83.

7. Афраймович Л.Г. Многоиндексные задачи линейного программирования с декомпозиционной структурой // VI Московская международная конференция по исследованию операций (ORM2010): Москва, 19-23 октября 2010 г.: Труды – М.: МАКС Пресс, 2010. С. 280–281.

8. Афраймович Л.Г. Многоиндексные транспортные задачи с 2-вложенной структурой // Автоматика и телемеханика. 2013. 1. С. 116–134.

9. Афраймович Л.Г. Многоиндексные транспортные задачи с декомпозиционной структурой // Автоматика и телемеханика. 2012. 1. С. 130–147.

10. Афраймович Л.Г. Модифицированные потоковые алгоритмы распределения однородного ресурса в иерархических системах // Математика и кибернетика 2003.

Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород. 2003. C. 23–25.

11. Афраймович Л.Г. Оптимальное распределение однородного ресурса в задачах программирования. Труды Всероссийской конференции студентов, аспирантов и молодых ученых. Центральный регион. – М.: Издательство МГТУ им Н.Э. Баумана. 2005. C. 31–32.

иерархических систем распределения однородного ресурса // IX Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров. 2004. C 6–7.

Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2006. 2(31). С. 129-138.

иерархических системах // Тезисы докладов НТК «Технические, программные и математические аспекты управления сложными распределенными системами». Нижний Новгород. 2003. C. 6.

транспортных задач с декомпозиционной структурой // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20- июня 2011 г.) – Нижний Новгород: изд-во Нижегородского госуниверситета, 2011. С. 42Афраймович Л.Г. Проблема существования решения в многоресурсных иерархических системах // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. 2005. Вып. 14. с. 122–127.

17. Афраймович Л.Г. Равномерное перераспределение ресурсов в иерархических Нижегородского госуниверситета. 2007. С. 320–321.

транспортного типа с ограничениями. Построение математических моделей и их исследование // Труды НГТУ. Системы обработки информации и управления. 2005. Т. 45.

Вып. 23. С. 27–34.

19. Афраймович Л.Г. Сведение системы линейных неравенств транспортного типа к задаче поиска максимального потока в сети при дополнительных ограничениях // Проблемы теоретической кибернетики. Тезисы докладов Международной конференции. – М.: Изд-во механико-математического факультета МГУ. 2005. C. 13.

20. Афраймович Л.Г. Трехиндексные задачи линейного программирования с вложенной структурой // Автоматика и телемеханика. 2011. 8. С. 109–120.

21. Афраймович Л.Г. Учебно-методическое пособие по курсу «Модели и методы эффективного использования распределенных вычислительных систем» при изучении темы «Задачи статической балансировки». – Нижний Новгород: Нижегородский госуниверситет. 2011.

22. Афраймович Л.Г. Циклическая сводимость многоиндексных систем линейных неравенств транспортного типа // Известия РАН. Теория и системы управления. 2010.

4. С. 83–90.

23. Афраймович Л.Г. Батищев Д.И., Костюков В.Е., Прилуцкий М.Х., Шагалиев Р.М. Статическая балансировка параллельных методов моделирования газодинамических процессов Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции – Челябинск: Изд. ЮУрГУ, 2009. C. 364–369.

производительности купола по газовым скважинам // Технологии Microsoft в теории и практике программирования. Материалы конференции. – Нижний Новгород: Изд-во Нижегородского госуниверситета. 2009. C. 350–352.

25. Афраймович Л.Г. КатеровА.С. Трех- и четырехиндексные задачи с вложенной структурой // Математическое моделирование. Оптимальное управление. Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. 3 (1). С. 163–169.

самостоятельной работы студентов по курсу «Моделирование сложных систем» при изучении темы «Распределение ресурсов в многоиндексных иерархических системах». – Нижний Новгород: Нижегородский государственный университет. 2006.

27. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального планирования производства // Автоматика и телемеханика. 2010.. 10. C. 148–155.

28. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика. 2006. 6. С.194–205.

29. Афраймович Л.Г., Прилуцкий М.Х. Многопродуктовые потоки в древовидных сетях // Известия РАН. Теория и системы управления. 2008. 2. С. 57–63.

транспортных сетях // Управление большими системами. 2009. Вып. 24. С. 147–168.

31. Афраймович Л.Г. Прилуцкий М.Х. Распределение ресурсов в иерархических системах транспортного типа. Учебно-методический материал по программе повышения квалификации «Новые подходы в исследованиях и разработках информационнотелекоммуникационных систем и технологий». – Нижний Новгород: Нижегородский госуниверситет. 2007.

32. Афраймович Л.Г., Прилуцкий М.Х. Распределение ресурсов в несовместных многоиндексных иерархических системах // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009 г. Труды.: МАКС Пресс. 2009. С. 18–23.

33. Афраймович Л.Г., Прилуцкий М.Х. Сводимость задачи распределения ресурсов в иерархических системах древовидной структуры к потоковым задачам // Технологии Microsoft в теории и практике программирования. Материалы конференции. – Нижний Новгород: Изд-во Нижегородского госуниверситета. 2006. С. 25–26.

34. Афраймович Л.Г., Прилуцкий М.Х. Трехиндексные транспортные задачи с вложенной структурой // Материалы X Международного семинара «Дискретная математика и ее приложения» – М.: Изд-во механико-математического факультета МГУ, 2010. С. 286–288.

35. Афраймович Л.Г., Прилуцкий М.Х., Бухвалова И.Р., Старостин Н.В., Филимонов А.В. Оптимизационные задачи оперативного управления работой компрессорной станцией // Электронный журнал «Исследовано в России». 2008. 032. С.

375–382. http://zhurnal.ape.relarn.ru/articles/2008/032.pdf Филимонов А.В. Оптимизационные задачи объемно-календарного планирования для предприятий по переработке газового конденсата // Электронный журнал «Исследовано в России». 2008. 031. С. 365–374. http://zhurnal.ape.relarn.ru/articles/2008/031.pdf магистральном газопроводе // Электронный журнал «Исследовано в России». 2008. 033. С.

383–391. http://zhurnal.ape.relarn.ru/articles/2008/033.pdf 38. Бабенко М.А. О потоках в простых двунаправленных и кососимметрических сетях // Проблемы передачи информации. 2006. Т. 42. Вып. 4. С. 104–120.

39. Березнев B.А. О полиномиальной сложности одной модификации симплексметода // Журнал вычислительной математики и математической физики. 2004. Т. 44. 7.

С. 1244–1260.

40. Берж К. Теория графов и ее приложения. – М.: ИЛ. 1962.

41. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. Специальные задачи. – М.: Наука. 1977.

42. Верховский Б.С. Многомерные задачи линейного программирования типа транспортной // Доклады АН СССР. 1963. Т. 151. 3. С. 515–518.

43. Гейл Д. Теория линейных экономических моделей. – М.: Мир. 1969.

44. Гимади Э.Х., Глазков Ю.В. Об асимптотически точном алгоритме решения одной модификации трехиндексной планарной задачи о назначениях // Дискретный анализ и исследование операций. Сер. 2. 2006. Т. 13. 1. С. 10–26.

45. Гимади Э.Х., Коркишко Н.М. Об одном алгоритме решения трехиндексной аксиальной задачи о назначениях на одноциклических подстановках // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10. 2. С. 56–65.

46. Гимади Э.Х., Сердюков А.И. Аксиальные трехиндексные задачи о назначении и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ // Известия высших учебных заведений. Математика. 1999. 12. С. 19–25.

47. Голиков А.И., Евтушенко Ю.Г. Нахождение нормального решения задачи линейного программирования / / Динамика неоднородных систем. 10. С. 104–117.

транспортного типа. – М.: Наука. 1969.

49. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании М: Советское радио, 1966.

50. Голиков А.И., Евтушенко Ю.Г., Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности Журнал вычислительной математики и математической физики. 2004. Т. 44. 9. С. 1564–1573.

51. Гофман А.Д., Краскал Д.Б. Целочисленные граничные точки выпуклых многогранников // Линейные неравенства и смежные вопросы. – М.: ИЛ. 1959. С. 325–347.

52. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир. 1982.

53. Давидсон М. Р., Малашенко Ю. Е., Новикова Н. М. и др. Математические постановки задач восстановления и обеспечения живучести для многопродуктовых сетей.

– М.: ВЦ РАН. 1993.

54. Диниц Е.А. Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой // Доклады АН СССР. 1970. Т. 194. 4. С. 754–757.

55. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях // Журнал вычислительной математики математической физики. 2007. Т. 47. 6. С. 1077–1086.

56. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения трехиндексной планарной проблемы выбора // Журнал вычислительной математики математической физики. 2006. Т. 46. 2. С. 222–228.

57. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. – М.: Наука. 1981.

58. Емеличев В.А., Кравцов М.К. Полиэдральные аспекты многоиндексных аксиальных транспортных задач // Дискретная математика, 1991. Т. 3. Вып. 2. С. 3–24.

59. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. – М.:

Наука. 1967.

60. Канатников А.Н., Крищенко А.П. Линейная алгебра. – М.: Изд-во МГТУ им.

Н.Э. Баумана. 2002.

61. Канторович Л.В. Математические методы организации и планировании производства. – Л.: Изд-во ЛГУ, 1939.

62. Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. – М.: Изд-во АН СССР, 1960.

63. Карзанов А.В. Нахождение максимального потока в сети методом предпотоков // Доклады АН СССР. 1974. Т. 215. 1. C. 49–52.

64. Ковалев М.М. Матроиды в дискретной оптимизации. – М: Едиториал УРСС.

2003.

65. Костюков В.Е., Прилуцкий М.Х. Распределение ресурсов в иерархических системах. Оптимизационные задачи добычи, транспорта газа и переработки газового конденсата. – Нижний Новгород: Изд-во Нижегородского государственного университета.

2010.

66. Кравцов В.М., Кравцов М.К., Лукшин Е.В. О типах (3n2)-нецелочисленных вершин многогранника трехиндексной аксиальной задачи выбора // Известия высших учебных заведений. Математика. 2002. 12. С. 84–90.

67. Кравцов М.К., Крачковский А.П. Асимптотический подход к решению многоиндексной аксиальной транспортной задачи // Журнал вычислительной математики и математической физики. 1998. Т. 38. 7. С. 1133–1139.

68. Кравцов М.А., Крачковский А.П. О некоторых свойствах трехиндексных транспортных многогранников // Дискретная математика. 1999. Т. 11. Вып. 3. С. 109–125.

69. Кравцов М.А., Крачковский А.П. О полиномиальном алгоритме нахождения асимптотически оптимального решения трехиндексной планарной проблемы выбора // Журнал вычислительной математики математической физики. 2001. Т. 41. 2. С. 342– 345.

70. Кравцов М.К., Кравцов В.М. О типах максимально нецелочисленных вершин релаксационного многогранника четырехиндексной аксиальной задачи о назначениях // Известия высших учебных заведений. Математика. 2012. 3. С. 9–16.

71. Кравцов М.К., Кравцов В.М., Лукшин Е.В. О нецелочисленных вершинах многогранника трехиндексной аксиальной задачи о назначениях // Дискретная математика. 2001. Т. 13. Вып. 2. С. 120–143.

72. Кравцов М.К., Лукшин Е.В. О нецелочисленных вершинах многогранника трехиндексной аксиальной транспортной задачи // Автоматика и телемеханика. 2004. 3.

С. 71–79.

73. Кропанов В.А., Рублев В.С. Равномерное назначение работ минимальной стоимости // Дискретная математика. 2001. Т. 13. Вып. 4. 2001. С. 144–156.

допускающие сетевую постановку // Экономика и математические методы. 1970. Т. 6.

Вып. 4. С. 594–604.

75. Мазалов В.В. Математическая теория игр и приложения. – Санкт-ПетербургМосква-Краснодар: Лань, 2010.

76. Малашенко Ю. Е., Новикова Н. М. Потоковые задачи анализа уязвимости многопродуктовых сетей. – М.: ВЦ АН СССР. 1989.

77. Меламед И.И., Сигал И.Х. Вычислительное исследование алгоритмов решения бикритериальных задач дискретного программирования // Журнал вычислительной математики и математической физики. 2000. Т. 4. 11. С. 1602–1610.

78. Меламед И.И., Сигал И.Х. Вычислительное исследование трехкритериальных задач о деревьях и назначениях // Журнал вычислительной математики и математической физики. 1998. Т. 38. 10. С. 1780–1787.

79. Миронов А.А., Цурков В.И. Замкнутые транспортные модели с минимаксным критерием // Автоматика и телемеханикаю. 2002. 3. С. 50–61.

80. Миронов А.А., Цурков В.И. Минимакс в транспортных задачах. – М.: Наука.

1997.

81. Нестеров Ю.Е. Метод линейного программирования с трудоемкостью O(n3L) операций // Экономика и математические методы. 1988. Т. 24. 16. C. 174–176.

82. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир. 1985.

83. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика. 1996. 2. С. 24–29.

84. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объемнокалендарного планирования // Известия РАН. Теория и системы управления. 2007. 1. C.

78–82.

85. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры // Труды международной конференции «Идентификация систем и задачи управления SICPRO’2000». – М.: ИПУ им. В.А. Трапезникова РАН. 2000.

С. 2038–2049.

86. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. 2004. Вып. 9. C. 56–63.

87. Прилуцкий М.Х., Афраймович Л.Г. Параллельные алгоритмы распределения ресурсов в иерархических системах с лексикографическим упорядочиванием элементов // «Высокопроизводительные параллельные вычисления на кластерных системах». – Нижний Новгород: Издательство Нижегородского госуниверситета. 2002. C. 243–248.

88. Прилуцкий М.Х., Афраймович Л.Г. Параллельные структуры потоковых и итерационных алгоритмов распределения ресурса в иерархических системах // «Высокопроизводительные параллельные вычисления на кластерных системах». – Нижний Новгород: Издательство Нижегородского госуниверситета. 2003. C. 140–145.

89. Прилуцкий М.Х., Афраймович Л.Г. Условия совместности многоиндексных систем транспортного типа // Электронный журнал "Исследовано в России", 70. 2005. C.

762–767. http://zhurnal.ape.relarn.ru/articles/2005/070.pdf 90. Прилуцкий М.Х., Афраймович Л.Г., М.С. Куликов. Об одном классе многокритериальных задач квадратичного программирования транспортного типа // Математическое моделирование. Оптимальное управление. Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. 6 (1). C. 178–183.

планирования. Лексикографические схемы // Информационные технологии. 2005. 7. С.

61–66.

многокритериальных задач распределения ресурсов с кусочно-постоянными функциями критериев // Системы управления и информационные технологию. 2011. Т. 44. 2. С.

16–21.

программирования. – М.: Радио и связь. 1982.

информационных систем. 2010. Т. 17. 2. С. 72–98.

95. Рублев В.С., Смирнов А.В. NP-полнота задачи сбалансирования трехмерной матрицы // Доклады Академии наук. 2010. Т. 435. 3. С. 314–316.

96. Рублев В.С., Чаплыгина Н.Б. Выбор критерия оптимизации в задаче о равномерном назначении // Дискретная математика. 2005. Т. 17. Вып. 4. С. 150–157.

97. Серая О.В., Дунаевская О.И. Многоиндексные нелинейные транспортные задачи // Інформаційно-керуючі системи на залізничному транспорті. 2009. 5. С.25–30.

98. Сергеев С.И. Новые нижние границы для трипланарной задачи назначения.

Использование классической модели // Автоматика и телемеханика. 2008. 12. С. 53–75.

99. Сергеев С.И. Улучшенные нижние границы для решения квадратичной задачи назначения // Автоматика и телемеханика. 2004. 11. С. 49–63.

программирование: модели и вычислительные алгоритмы. Учебное пособие. – М.:

Физмалит. 2007.

101. Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем. 2009. Т. 16. 3. С.

70–76.

102. Схрейвер А. Теория линейного и целочисленного программирования: в 2 т. – М.: Мир. 1991.

103. Триус Е.Б. Задачи математического программирования транспортного типа.

М.: Советское радио. 1967.

104. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир. 1984.

дискретного программирования. М.: Наука. 1976.

106. Форд Л., Фалкерсон Д. Потоки в сетях. – М.: Мир. 1966.

107. Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир. 1974.

108. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Доклады АН СССР. 1979. Т. 244. 5. С. 1093–1096.

109. Черников С.Н. Линейные неравенства. – М.: Мир. 1966.

110. Afraimovich L.G. Generalized model of homogeneous resource distribution in hierarchy systems // VI International congress on mathematical modeling. Book of abstracts.

Nizhny Novgorod. 2004. P. 65.

111. Afraimovich L.G. Reconstructing hierarchy systems of homogeneous resource distribution // Избранные вопросы современной математики: Тез. Междунар. науч. конф., приуроченной к 200-летию со дня рождения великого немецкого математика Карла Густава Якоби и 750-летию со дня основания г. Калининграда (Кенигсберга). – Калининград: Изд-во КГУ. 2005. C. 64–66.

112. Afraimovich L.G., Prilutskii M.Kh. Multi-commodity min-cost flow problem in a directed tree structured graph // V Московская международная конференция по исследованию операций (ORM 2007), посвященная 90-летию со дня рождения академика Н.Н. Моисеева. – М.:Макс Пресс. 2007. С. 233–234.

113. Aggarwal C., Ahuja R.K., Hao J., Orlin J.B. Diagnosing infeasibilities in network flow problems // Mathematical Programming. 1998. V. 81. N 3. P. 263–280.

114. Agmon S. The relaxation method for linear inequalities // Canadian Journal of Mathematics. 1954. V. 6. 3. P. 382–392.

115. Ahuja R.K., Magnati T.L., Orlin J.B. Network flows: theory, algorithms, and applications. Prentice Hall. 1993.

116. Alighanbari M., How J.P. Cooperative task assignment of unmanned aerial vehicles in adversarial environments // Proceedings of the American Control Conference. 2005. V. 7. P.

4661–4666.

117. Amaldi E., Pfetsch M.E., Leslie E.T. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs // Mathematical Programming, 2003. V. 95. N 3. P. 533–554.

118. Arbib C., Pacciarelli D., Smriglio S. A. A three-dimensional matching model for perishable production scheduling // Discrete Applied Mathematics. 1999. V. 92. P. 1–15.

119. Balas E., Saltzman M.J. An algorithm for the three-index assignment problem // Operations Research. 1991. V. 39. P. 150–161.

120. Bandelt H.J., Crama Y., Spieksma F.C.R. Approximation algorithms for multidimensional assignment problems with decomposable costs // Discrete Applied Mathematics. 1994. V. 49. P. 25–50.

121. Bandopadhyaya L., Puri M.C. Impaired flow multi-index transportation problem with axial constraints // Journal of Australian Mathematical Society. Series B. 29(3). 1988. P.

296–309.

122. Borradaile G., Klein P., Mozes S., Nussbaum Y., Wulff-Nilsen C. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time // Proceedings of 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). Palm Springs. 2011. P.

170–179.

123. Briskorn D., Drexl A., Spieksma F.C.R. Round robin tournaments and three index assignment // 4OR: a Quarterly Journal of Operations Research. 2010. V. 8. P. 365–374.

124. Burkard R.E., ela E. Heuristics for biquadratic assignment problems and their computational comparison // European Journal of Operational Research. 1995. V. 83. P. 283– 300.

125. Burkard R.E., Cela E., Pardalos P.M., Pitsoulis L. The quadratic assignment problem / Pardalos P.P., Resende M.G.C. (Eds.). Handbook of Combinatorial Optimization. – Dordrecht: Kluwer Academic Publishers. 1998. P. 241–238.

126. Burkard R.E., Dell'Amico M., Martello S. Assignment Problems. – Philadelphia:

SIAM. 2009.

127. Burkard R. E., Rudolf R., Woeginger G. J. Computational investigation on 3dimensional axial assignment problems // Belgian Journal of Operations Research, Statistics and Computer Science. 1992. V. 32. P. 85–98.

128. Burkard R.E., Rudolf R., Woeginger G.J. Three-dimensional axial assignment problems with decomposable cost coefficients // Discrete Applied Mathematics. 1996. V. 65. P.

123–139.

129. Chen B., Potts C.N., Woeginger G.J. A review of machine scheduling. Complexity, algorithms and approximability / Handbook of Combinatorial Optimization. Kluwer Academic Publishers. 1998. V. 3. P. 21–169.

130. Cosares S., Hochbaum D.S. Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources // Mathematics of Operations Research archive. 1994. V. 19. P. 94–111.

131. Crama Y., Spieksma F.C.R. Approximation algorithms for three-dimensional assignment problems with triangle inequalities // European Journal of Operational Research.

1992. V. 60. P. 273–279.

132. Daskalai S., Birbas T., Housos E. An integer programming formulation for a case study in university timetabling // European Journal of Operational Research. 2004. V. 153. P.

117–135.

133. Dantzig G.B. Linear programming and extensions. – Princeton, NJ: Princeton University Press. 1963.

134. De Loera J., Hemmecke R., Onn S., Weismantel R. N-fold integer programming // Discrete Optimization. 2008. V. 5. P. 231–241.

135. De Loera J. A., Kim E.D., Onn S., Santos F. Graphs of transportation polytopes // Journal of Combinatorial Theory. Series A. 2009. V. 116. N. 8. P. 1306–1325.

136. De Loera J., Onn S. All linear and integer programs are slim 3-way transportation programs // SIAM Journal on Optimization. 2006. V. 17(3). P. 806–821.

137. De Loera J., Onn S. All Rational polytopes are transportation polytopes and all polytopal integer sets are contingency tables // Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. 2004. V. 3064. P. 338–351.

138. De Loera J., Onn S. The complexity of three-way statistical tables // SIAM Journal on Computing. 2004. V. 33. P. 819–836.

139. Delona J., Salomonb J., Sobolevskic A. Local matching indicators for concave transport costs // Comptes Rendus Mathematique. 2010. V. 348. P. 901–905.

140. Diaconis P., Gangolli A. Rectangular arrays with fixed margins // Discrete Probability and Algorithms. The IMA Volumes in Mathematics and its Applications. 1995. V.

72. P 15–41.

141. Dokka T., Kouvela A., Spieksma F.C.R. Approximating the multi-level bottleneck assignment problem // Operations Research Letters. 2012. V. 40. P. 282–286.

142. Duncan G.T., Fienberg S.E., Krishnan R., Padman R., Roehrig S.F. Disclosure limitation methods and information loss for tabular data / P. Doyle, J. Lane, J. Theeuwes, and L.

Zayatz (Eds.). Confidentiality, Disclosure and Data Access: Theory and Practical Applications for Statistical Agencies. 2001. Elsevier. P. 135–166.

143. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of the ACM. 1972. V. 19. N 2. P. 248–264.

144. Eisenbrand F. Fast integer programming in fixed dimension // Algorithms - ESA 2003. Lecture Notes in Computer Science. 2003. V. 2832. P. 196–207.

145. Franz L.S., Miller J.L. Scheduling medical residents to rotations: Solving the largescale multiperiod staff assignment problem // Operations Research. 1993. V. 41. N 2. P. 269– 279.

146. Frieze A.M. Complexity of a 3-dimensional assignment problem // European Journal of Operational Research. 1983. V. 13(2). P. 161–164.

147. Frieze A.M., Yadegar J. An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice // The Journal of the Operational Research Society. 1981. V. 32. N. 11. P. 989–995.

148. Gairing M., Lucking T., Mavronicolas M., Monien B. Computing Nash equilibria for scheduling on restricted parallel links // Proceedings of 36th annual ACM symposium on theory of computing. P. 613–622.

149. Galil Z., Tardos E. An mincost flow algorithm // Journal of the ACM. 1988. V. 35.

N. 2. P. 374–386.

150. Glover F. Flows in arborescences // Management Science. 1971. V. 17. N 9. P. 568– 586.

151. Goldberg A.V., Rao S. Beyond the flow decomposition barrier // Journal of the ACM. 1998. V. 45. N 5. P. 783–797.

approximability of three-dimensional assignment problems with bottleneck objective // Optimization Letters. 2010. V. 4. P. 7–16.

153. Glpinar N., Gutin G., Mitra G., Zverovitch A. Extracting pure network submatrices in linear programs using signed graphs // Discrete Applied Mathematics. 2004. V. 137. N. 3. P.

359–372.

154. Gunawan A., Ng K.M., Poh K.L. Solving the teacher assignment-course scheduling problem by a hybrid algorithm // International Journal of Computer and Information Engineering. 2007. V. 1. N 2. P. 136–141.

155. Chinneck J.W. Dravnieks E.R. Locating minimal infeasible constraint sets in linear programs // ORSA Journal on Computing. 1991. V. 3. N 3. P. 157–168.

156. Goldberg A. V., Tarjan R. E. Solving minimum-cost flow problems by successive approximation // Mathematics of Operations Research, 1990. V. 15. N 3. P. 430–466.

157. Junginger W. On representatives of multi-index transportation problems // European Journal of Operational Research. 1993. V. 66(3). P. 353–371.

158. Karmarkar N. A new polynomial time algorithm for linear programming // Combinatorica. 1984. V. 4. P. 373–395.

159. Kmpke T. The geometry of linear infeasibility // Applied Mathematics and Computation. 2002. V. 129. N 2-3. P. 317–337.

160. Klee V., Minty G.J. How good is the simplex algorithm? / Shisha O. (Ed.).

Inequalities III. – New York, NY: Academic Press. 1972. P. 159–175.

161. Klinz B., Woeginger G.J. A new efficiently solvable special case of the threedimensional axial bottleneck assignment problem // Lecture Notes in Computer Science. 1996.

V. 1120. P. 150–162.

162. Krokhmal P., Murphey R., Pardalos P., Uryasev S., Zrazhevski G. Robust decision making: addressing uncertainties / Butenko et al. (Eds.). Cooperative Control: Models, Applications and Algorithms. Kluwer Academic Publishers. 2003. P. 165– 163. Lenstra H.W. Jr. Integer programming with a xed number of variables // Mathematics of Operations Research. 1983. V. 8. N. 4. P. 538–548.

164. Lim A., Rodrigues B., Zhang X. Scheduling sports competitions at multiple venues – Revisited // European Journal of Operational Research. 2006. V. 175. P. 171–186.

165. Lin Y. A recognition problem in converting linear programming to network flow models // Applied Mathematics - A Journal of Chinese Universities. 1993. V. 8. N. 1. P. 76–85.

166. Luby M., Nisan N. A parallel approximation algorithm for positive linear programming // Proceedings of 25th annual ACM symposium on Theory of computing.

STOC'93. 1993. P. 448–457.

167. Magos D. Tabu search for the planar three-index assignment problem // Journal of Global Optimization. 1996. V. 8. P. 35–48.

168. Malvestuto F.M., Mezzini M., Moscarini M. Auditing sum-queries to make a statistical database secure // ACM Transactions on Information and System Security. 2006. V. 9.

P. 31–60.

169. Martens M., Skutella М. Flows on few paths: algorithms and lower bounds // Networks. 2006. V. 48. N 2. P. 68-76.

170. McCormick S.T. How to compute least infeasible flows // Mathematical Programming. 1997. V. 78. N 2. P. 179–194.

171. Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities // Canadian Journal of Mathematics. 1954. V. 6. N 3. P. 393–404.

172. Orlin J.B. A Faster strongly polynomial minimum cost flow algorithm // Operations research. 1993. V. 41. N 2. P. 338–350.

173. Orlin J.B. Max flows in O(nm) time, or better // Proceedings of the 45th annual ACM symposium on theory of computing. 2013. P. 765–774.

174. Pentico D.W. Assignment problems: A golden anniversary survey // European Journal of Operational Research. 2007. V. 176. P. 774–793.

175. Poore A.B. Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking // Computational Optimization and Applications. 1994. V. 3. N 1. P. 27–57.

176. Pusztaszeri J.F., Rensing P.E., Liebling T.M. Tracking elementary particles near their primary vertex: A combinatorial approach // Journal of Global Optimization. 1996. V. 9. P.

41–64.

177. Queyranne M., Spieksma F.C.R. Approximation algorithms for multi-index transportation problems with decomposable costs // Discrete Applied Mathematics. 1997. V. 76.

P. 239–253.

178. Shapley L.S., Shubik M. The assignment game: the core // International Journal of Game Theory. 1972. V. 1. P. 111–130.

179. Sipser M. Introduction to the theory of computation. Boston: PWS Publishing Company. 1997.

180. Skutella M. An introduction to network flows over time // Research Trends in Combinatorial Optimization. 2009. P. 451-482.

181. Sleator D.D., Tarjan R.E. A data structure for dynamic trees // Journal of Computer and System Sciences. 1983. V. 26. P. 362–391.

182. 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 Academic Publishers. 2000. P. 1–11.

183. Spieksma F.C.R., Woeginger G.J. Geometric three-dimensional assignment problems // European Journal of Operational Research. 1996. V. 91. P. 611–618.

184. Storms P.P.A., Spieksma F.C.R. An LP-based algorithm for the data association problem in multitarget tracking // Computers and Operation Research. 2003. V. 30. N 7. P.

1067–1085.

185. Vartak M.N., Geetha S. Specially structured precedence constraints in threedimensional bottleneck assignment problems // Journal of the Operational Research Society.

1990. V. 41. N 4. P. 339–344.

186. Vlach M. Conditions for the existence of solutions of the three-dimensional planar transportation problem // Discrete Applied Mathematics. 1986. V. 13. P. 61–78.

Приложения Приложение Приложение Приложение Приложение Приложение Приложение Приложение Приложение