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

Вход. Задача (2.28), (2.34).

Шаг 1. Вычислить g ( p, p,..., p), если g ( p, p,..., p) 1, то переход на шаг 2; иначе задача (2.28), (2.34) несовместна, и алгоритм завершен.

Шаг 2. Определим оптимальное значение компонент вершины как решение следующей оптимизационной задачи.

Оптимальное решение y 0 задачи (2.35)–(2.37) находится при помощи бинарного поиска на множестве {0,1,..., p}, на каждой итерации которого вычисляется соответствующее значение g ( y, y,..., y). Пусть vi y, i 1, k. Алгоритм завершен.

Работа алгоритма 2.9 связана с вычислением общего значения компонент вершины v 0, определяемого при помощи бинарного поиска на множестве мощности p 1. На каждой итерация бинарного поиска вычисляется значение функции g, а следовательно, проверяется на совместность система вида (v ). Отсюда:

Утверждение 2.9. Алгоритм 2.9 требует O(log p) проверок совместности системы ограничений вида (v ).

Для проверки совместности системы (v ) можно воспользоваться общими методами решения систем линейных неравенств [109]. Т.к. (v ) представляет собой систему линейных неравенств транспортного типа, то для ее решения можно также воспользоваться модифицированным методом ортогональных проекций, описанным в пункте 2.5. При решении ряда многоиндексных транспортных задач возникающая система ограничений (v ) может быть решена потоковыми алгоритмами, соответствующие классы задач будут рассмотрены далее в работе при исследовании вопросов сводимости.

Выводы Рассмотрены методы решения ряда задач транспортного типа, построены оценки вычислительной сложности. Пусть (n, m) и (n, m) – количество вычислительных операций, требуемых для решения задачи поиска максимального потока и потока минимальной стоимости заданной величины соответственно, где n и m – количество вершин и дуг сети. Описана и обоснована процедура поиска потока в сети с двусторонними пропускными способностями:

– поиск допустимого потока требует (O(| V |), O(| V | | A |)) вычислительных операций, (O(| V |), O(| V | | A |)) + (O(| V |), O(| V | | A |)) вычислительных операций.

Описана и обоснована процедура поиска потока в древовидной сети с двусторонними пропускными способностями:

– поиск допустимого потока требует O(|V |) вычислительных операций, – поиск потока минимальной стоимости требует O(| V |2 ) вычислительных операций.

Разработан и обоснован алгоритм поиска потока в несовместной сети, требующий (O(| V | | A |), O(| V | | A |)) + (O(| V | | A |), O(| V | | A |)) вычислительных операций.

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

Описан и обоснован метод решения k-критериальных задач транспортного типа с кусочно-постоянными (p+1)-значными критериями:

– при лексикографической свертки алгоритм требует O(k log p) проверок совместности систем транспортного типа, совместности систем транспортного типа.

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

Глава 3. Многоиндексные задачи транспортного типа Глава посвящена постановкам исследуемых многоиндексных задач транспортного типа. Постановки задач приведены с использованием введенной в [93] и далее развитой в [8, 9, 20] схемы формализации многоиндексных задач. Данная формализация используется в работе при описании результатов исследования многоиндексных задач. Описывается общая формализация схем сводимости, разработанная в [8, 9, 20], применяемая далее при классификации схем сведения многоиндексных задач к классу задач поиска потока в сети.

3.1. Постановки многоиндексных задач транспортного типа При постановке многоиндексных задач транспортного типа воспользуемся следующей формализацией, основанной на обозначении, введенном в [93]. Пусть s N и N (s) {1,2,..., s}. Каждому числу l поставим в соответствие параметр jl, называемый индексом, который принимает значения из множества J l {1,2,..., nl }, где nl 2, l N (s).

Там где это не вызывает неоднозначности, будем отождествлять номер индекса l и индекс jl. Пусть соответствующих f, определим как E f {F f | F J k1 J k2... J kt }. Там, где это не вызывает неоднозначности, будем опускать нижний индекс f и записывать t-индекс как определим f N (s) \ f, тогда согласно введенному обозначению FN ( s ) Ff Ff, если Каждому набору F f поставим в соответствие действительное число z F f, Ff E f.

Данное отображение множества t-индексов E f в множество действительных чисел назовем t-индексной матрицей и обозначим через {z F f }. Рассмотрим s-индексную матрицу {z N (s ) } и введем следующее обозначение Введенное обозначение подсумм s-индексной матрицы будем использовать при формализации многоиндексных транспортных задач.

матрицы свободных коэффициентов, 0 aFf bFf, F f E f, f M ; {c FN ( s ) } – заданная sиндексная матрица коэффициентов целевой функции; {x FN ( s ) } – s-индексная матрица неизвестных. Тогда многоиндексная задача линейного программирования транспортного типа формализуется следующим образом:

Задачу (3.1)-(3.3) будем обозначать w(s; M ; n1,..., n2 ;{aF },{bF }, f M ;{cFN ( s ) }), а класс всех многоиндексных задач линейного программирования (3.1)-(3.3) при фиксированном обозначать d (s; M ; n1,..., ns ;{aFf },{bFf }, f M ), а класс всех многоиндексных систем линейных неравенств (3.1),(3.2) при фиксированном множестве M будем обозначать D(M ).

фиксированному множеству d ( w, f, F f ). Матрицу системы ограничений задачи w обозначим через Matr (w). Строку матрицы Matr (w), определяемую двусторонним неравенством d ( w, f, F f ), обозначим row( w, f, F f ), Ff E f, f M. Столбец матрицы Matr (w), соответствующий переменной f (1),..., f ( k1 ) M, образованную элементами матрицы Matr (w), находящимися на пересечении строк В ряде задач s-индексная матрица коэффициентов целевой функции {cFN ( s ) } имеет многоиндексных матриц коэффициентов {d F f }, f H, что Тогда рассмотрим целевую функцию следующего вида:

Класс всех многоиндексных задач задача линейного программирования (3.1),(3.2),(3.4) при фиксированных множествах M и H будем обозначать W (M, H ). Справедливы следующие утверждения.

многоиндексная матрица {d Ff 2 }, что cFN ( s ) d ( FN ( s ) ) f 2, FN ( s ) EN ( s ). Такую матрицу можно определить следующим образом d( FN ( s ) ) f2 d( FN ( s ) ) f1, FN ( s ) EN ( s ). Отсюда несложно увидеть, что справедливо следующее утверждение.

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

фиксированных множествах M и H будем обозначать W (M, H ).

целочисленности переменных Задачу (3.1)-(3.3),(3.6) будем обозначать wZ (s; M ; n1,..., ns ;{aF },{bF }, f M ). Также будем добавлять нижний индекс Z к обозначению класса многоиндексных задач, если дополнительно выполняется условие целочисленности (3.6). Тогда соответствующие классы систем целочисленных линейных неравенств (3.1),(3.6), задач целочисленного линейного программирования (3.1),(3.6),(3.3) и задач целочисленного линейного обозначать через DZ (M ), WZ (M ) и WZ (M, H ) соответственно.

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

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

принимающий значение 1, если для неравенства d ( w, f, F f ) разрешено изменение нижней (верхней) границы, и значение 0 в противном случае; eF f ( eF f ) – штраф за изменение на единицу нижней (верхней) границы неравенства d ( w, f, F f ), eFf, eFf 0 ; y F f ( y F f ) – неизвестная величина, на которую будет изменена нижняя (верхняя) граница неравенства d ( w, f, F f ) F f E f, f M, wW (M ). Пусть система ограничений задачи wW (M ) несовместна и w w(s; M ; n1,..., ns ;{aF },{bF }, f M ;{cFN ( s ) }). Тогда задача исследования несовместной многоиндексной системы заключается в определении многоиндексных матриц неизвестных { y Ff }, { y Ff }, f M и {x FN ( s ) }, являющихся решением следующей задачи линейного программирования:

Класс всех задач задача линейного программирования (3.7)-(3.10) при фиксированном множестве M будем обозначать S (M ).

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

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

многоиндексных неравенств транспортного типа (3.1),(3.2). Множество H определяет кусочно-постоянные критерии, формализация которых приводится далее. Пусть H 2 N ( s ) вложенных сегментов S (fl,)F f, l 0, p, что S (fl,)Ff S (fl,1f), l 0, p 1, S (f pFf [,], ( f, Ff ) P( H ). Каждая из пар ( f, Ff ) определяет следующую функцию предпочтения Тогда рассмотрим многокритериальную задачу определения s-индексной матрицы минимизирующей функции предпочтения Класс многокритериальных задач (3.1),(3.2),(3.11) будем обозначать U (M, H ). Пусть множество P(H ) упорядочено по значимости соответствующих критериев. Тогда в качестве схемы компромисса при решении поставленной многокритериальной задачи (3.1),(3.2),(3.11) оптимальности, соответствующий класс оптимизационных задач при фиксированных множествах M и H будем обозначать U (M, H ). Также в качестве схемы компромисса будем рассматривать максиминную свертку критериев оптимальности, соответствующий класс оптимизационных задач при фиксированных множествах M и H будем обозначать U max min (M, H ).

3.2. Задачи распределения ресурсов как многоиндексные задачи Введенную схему формализации многоиндексных задач транспортного типа проиллюстрируем на примере прикладных многоиндексных задач распределения ресурсов, описанных в главе 1. Определим место описанных прикладных задач в классе многоиндексных задач транспортного типа.

Транспортная задача с промежуточными пунктами Рассмотрим транспортную задачу с промежуточными пунктами, описанную в разделе 1.1. Для данной задачи s 3, N (s) {i, j, k} и M {{i},{k},{i, j},{ j, k}}. Здесь ограничение (1.1) соответствует множеству { j, k}, ограничение (1.2) – множеству {i, j}, ограничение (1.3) – множеству {k}, ограничение (1.4) – множеству {i}.

Тогда поставленные многоиндексные задачи линейного программирования (1.1)задача (1.1)-(1.5),(1.7) и задача (1.1)-(1.5),(1.8) относятся к классу W (M ).

Можно заметить, что коэффициенты целевых функций (1.6), (1.7) и (1.8) имеют декомпозиционную структуру – они определены в виде суммы многоиндексных матриц коэффициентов. Так для критерия (1.6) коэффициенты целевой функции имеют вид W (M, H ), где H {{i},{i, j},{ j, k}}. Задача (1.1)-(1.5),(1.7) относится к классу W (M, H ), H {{i},{k},{i, j},{ j, k}}.

При постановке многокритериальной задачи выбора плана перевозок (1.1)в качестве показателей плана, определяющих критерии задачи, выбраны объемы продукта соответствующего потребителям системы. Объем продуктов потребленный M {{i},{k},{i, j},{ j, k}} – определяет жесткие показатели, формализуемые в виде системы ограничений (1.1)-(1.5), H {{k}} – определяет желательные показатели, формализуемые в виде критериев (1.9). Если множество потребителей K упорядочено с точки зрения их приоритета, то при решении многокритериальной задачи (1.1)-(1.5),(1.9) может быть рассмотрена лексикографическая свертка критериев. Соответствующая задача относится к классу U (M, H ). В случае равнозначности потребителей в качестве схемы компромисса при решении многокритериальной задачи (1.1)-(1.5),(1.9) может быть рассмотрена максиминная свертка. Соответствующая задача относится к классу U max min (M, H ).

Задача формирования портфеля заказов Рассмотрим задачу формирования портфеля заказов, описанную в разделе 1.2. Для данной задачи s 3, N (s) {i, j, t} и M {,{ j},{i, t},{ j, t}}. Здесь ограничение (1.10) соответствует множеству { j, t}, ограничение (1.11) – множеству { j}, ограничение (1.12) – множеству {i, t}, ограничение (1.13) – множеству. Тогда поставленная проблема определения допустимого портфеля заказов (1.10)-(1.14) относится к классу D(M ).

несогласованностью внутренних ограничений предприятия. Вопрос о несогласованности (1.10),(1.11),(1.14), которая относится к классу D(M ), где M {{ j},{ j, t}}. Далее рассматриваются две задачи: задача формирования портфеля заказов с возможными нарушениями требуемых объемов работ по заказам и задача формирования портфеля заказов с возможными нарушениями сроков выполнения работ по заказам.

Задача формирования портфеля заказов с возможными нарушениями требуемых объемов работ по заказам ставится как задача (1.10),(1.11),(1.13)-(1.17). В поставленной задаче разрешены нарушения ограничения (1.12), определяемого множеством {i, t}.

Задача формирования портфеля заказов с возможными нарушениями сроков выполнения работ по заказам ставится как задача линейного программирования (1.10)Поставленная задача относится к классу W (M ), где (1.12),(1.14),(1.18).

M {{ j},{i, t},{ j, t}}.

Объемно-календарное планирование переработки газового конденсата Рассмотрим задачу объемно-календарного планирования переработки газового конденсата, описанную в разделе 1.3. Для данной задачи s 5, N (s) {i, j, k, p, t} и M {{i, j},{i, p},{ j, k, p, t}}. Здесь ограничение (1.19) соответствует множеству { j, k, p, t}, ограничение (1.20) – множеству {i, p}, ограничение (1.21) – множеству {i, j}. Тогда поставленные многоиндексные задачи линейного программирования (1.19)-(1.22),(1.23), задача (1.19)-(1.22),(1.24), задача (1.19)-(1.22),(1.25), задача (1.19)-(1.22),(1.26), задача (1.19)-(1.22),(1.27) и задача (1.19)-(1.22),(1.28) относятся к классу W (M ).

Можно заметить, что коэффициенты целевых функций рассматриваемых задач имеют декомпозиционную структуру. Отсюда задача (1.19)-(1.22),(1.23) относится к классу W (M, H ), где H {{k, p, t}}. Задача (1.19)-(1.22),(1.24) относится к классу W (M, H ), где H {{ j, k}}. Задача (1.19)-(1.22),(1.25) относится к классу W (M, H ), где H {{i, j}}. Задача (1.19)-(1.22),(1.26) относится к классу W (M, H ), где H {{t}}. Задача (1.19)-(1.22),(1.27) относится к классу W (M, H ), где H {{k, p}}. Задача (1.19)-(1.22), (1.28) относится к классу W (M, H ), где H {{t},{i, j},{ j, k},{k, p},{k, p, t}}.

Задача составления расписания занятий Рассмотрим задачу составления расписания занятий, описанную в разделе 1.4. Для данной задачи s 4, N (s) {i, j, k, t} и M {,{i, j},{ j, k},{i, k, t}}. Здесь ограничение (1.29) соответствует множеству { j, k}, ограничение (1.30) – множеству {i, k, t}, ограничение (1.31) – множеству {i, j}, ограничения (1.32), (1.33), (1.34) – множеству, ограничение (1.35) эквивалентно совокупности ограничений (3.12) и дополнительного ограничения целочисленности переменных, при этом ограничение (3.12) также соответствует множеству.

Отсюда система целочисленных линейных неравенств (1.29)–(1.35) относится к классу DZ (M ), задача целочисленного линейного программирования (1.29)–(1.36) относится к классу WZ (M ).

Заметим, что с учетом ограничения неотрицательности переменных ограничения (1.32), (1.33), (1.34) могут быть записаны в следующей эквивалентной форме kK tT jJ kK iI jJ Кроме того, ограничение (3.12) автоматически выполняется при выполнении ограничения (1.29) и ограничения неотрицательности переменных. Отсюда система целочисленных M {{i, j},{ j, k},{k, t},{i, k, t}}. Далее несложно увидеть, что коэффициенты целевой функции (1.36) имеют декомпозиционную структуру. Отсюда задача (1.29)–(1.36) относится к классу W (M, H ), где H {{i, j},{i, t},{k, t}}.

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

неизвестных. Через w( A, b, c) будем обозначать задачу линейного программирования min{(c, x) | Ax b, x 0} ; через w( A, b, b, c) – задачу линейного программирования min{(c, x) | b Ax b, x 0}. Для удобства через nrow(A) и ncol (A) будем обозначать количество строк и столбцов матрицы A соответственно. Отметим, что задача w( A, b, b, c) может быть описана с использованием обозначения вида w( A, b, c). Тем не менее будем использовать обозначение w( A, b, b, c) в случае, когда хотим подчеркнуть, что система ограничений задачи представляет собой систему двусторонних неравенств.

Также будем рассматривать задачи целочисленного линейного программирования. Если w w( A, b, c) – задача линейного программирования, то через wZ обозначим задачу целочисленного линейного программирования wZ min{(c, x) | Ax b, x Z ( A) }. Пусть W – произвольный класс задач линейного программирования. Соответствующий класс задач целочисленного линейного программирования определим как WZ {wZ | w W }.

Далее рассмотрим два класса задач линейного программирования W и W. На возможность построения для произвольной задачи w W соответствующей задачи w W таким образом, чтобы решение задачи w определяло решение задачи w. При формализации схем сведения будем определять временные затраты и (или) конкретные вычислительные процедуры, связанные с:

– построением матрицы системы ограничений задачи w по исходным параметрам задачи w ;

– построением свободных коэффициентов и коэффициентов целевой функции задачи w по исходным параметрам задачи w ;

– построением решения задачи w по решению задачи w.

Предлагаемое далее обозначение схемы сведения вводится по аналогии с нотацией Р. Грэхема (R. Graham), используемой при классификации задач теории расписаний [129].

Определение 3.1. Будем говорить, что класс W является t1 s1 | t 2 s2 | t3 s сводимым к классу W, если для любой задачи w w( A, b, c) W можно за время O(t1 ) с использованием процедуры s1 построить матрицу A, за время O(t 2 ) c использованием процедуры s2 построить векторы b, c, что w w( A, b, c) W и при этом – задача w совместна (ограничена) тогда и только тогда, когда совместна (ограничена) задача w ;

– если известно оптимальное (допустимое) решение x задачи w, то оптимальное (допустимое) решение x задачи w может быть построено за время O(t3 ) с использованием процедуры s3.

Здесь s1, s3 – строковые обозначения вычислительных процедур, связанных с построением матрицы системы ограничений, с построением свободных коэффициентов и коэффициентов целевой функции и с построением решения задачи соответственно.

Замечание. Опционально будем опускать записи вычислительных затрат t1, t 2, t 3 и (или) записи обозначений вычислительных процедур s1, s2, s3, если при сведении не конкретизируются соответствующие вычислительные затраты и (или) вычислительные процедуры. Задачу w (см. определение 3.1) будем называть задачей, соответствующей соответствующим решению x. При определении вычислительных затрат t1, t 2, t 3, если не оговорено иного, будем оценивать, как и в [82], количество вычислительных операций на машине с произвольным доступом к памяти. Иногда для удобства функции оценки вычислительной сложности t1, t 2, t 3 будем заменять обозначениями L или P, подразумевая линейные или полиномиальные функции от размера матрицы соответственно. В случае, когда при определении t1, t 2, t 3 оценивается вычислительная сложность рассматриваемых вычислительных процедур, будем добавлять верхний индекс «*» в записи соответствующих оценок. В частности будем записывать L* или P*, когда речь идет о линейной или полиномиальной оценках вычислительной сложности как функции от размера индивидуальной задачи соответственно. Схематично концепция t1 s1 | t 2 s2 | t3 s3 сводимости представлена на рис. 3.1.

В работе исследуется возможность сведения класса многоиндексных задач линейного программирования транспортного типа к классу задач поиска потока минимальной стоимости. В качестве потоковой задачи будем рассматривать задачу поиска zMCC (G; aij bij, cij (i, j ) A). Класс всех задач (2.5),(2.6),(2.4) будем обозначать WGraph. Также нас будет интересовать возможность сведения к классу задач поиска циркуляции минимальной стоимости в древовидной сети. Под древовидной сетью задачи о циркуляции будем понимать сеть, определяемую графом G (V, A), для которого существует корневое ориентированное дерево G (V, A) с корнем s V и множеством листьев T V, что A A {(t, s) | t T }. Класс задач поиска циркуляции минимальной стоимости в древовидной сети будем обозначать WTree, здесь WTree WGraph.

Далее в работе исследуются вопросы t1 s1 | t 2 s2 | t3 s3 сводимости классов многоиндексных задач W (M ) и W (M, H ) к классам задач поиска потока в сети WGraph и WTree. Применяемые при исследовании сводимости вычислительные процедуры s1, s 2, s будут определены при описании рассматриваемых схем сведения.

Выводы Описана общая схема формализации многоиндексных задач, применяемая в работе.

Данная схема проиллюстрирована на примере прикладных многоиндексных задач, рассмотренных в главе 1. Полученные в работе теоретические результаты исследования многоиндексных задач будут изложены с использованием данной формализации. Описана общая схема формализации сводимости задач линейного программирования, применяемая далее при исследовании сводимости многоиндексных задач к классу задач поиска потока в сети. Результаты исследования сводимости будут применены в работе при построении алгоритмов решения поставленных многоиндексных задач D(M ), W (M ), W (M, H ), W (M, H ) (и соответственно DZ (M ), WZ (M ), WZ (M, H ), WZ (M, H ) ), а также S (M ), Глава 4. Сводимость с сохранением соответствия ребер Глава посвящена исследованию сводимости класса многоиндексных задач к классу задач поиска потока минимальной стоимости в сети с использованием схемы сведения с сохранением соответствия ребер [8, 20, 25, 27, 28, 32, 34, 89]. Особенностью рассматриваемой концепции сводимости является существование соответствия между переменными исходной задачи и дугами вспомогательной сети. Предлагаемая схема сведения гарантирует, что произвольный оптимальный поток вспомогательной сети будет определять такое оптимальное решение исходной задачи, в котором переменным присваивается значение потока вдоль соответствующих дуг сети. В рамках рассматриваемой схемы сведения в данной главе найдены условия сводимости класса многоиндексных задач линейного программирования к классу задач поиска потока в сети и к классу задач поиска потока в древовидной сети. Предлагается конструктивная схема сведения. На основе предложенной схемы сведения строятся алгоритмы решения многоиндексных задач, удовлетворяющих условиям сводимости. Результаты обобщаются при исследовании более широкого класса схем сводимости.

4.1. Концепция t1 | t2 equal | t3 edge сводимости Введем схему t1 | t 2 equal | t3 edge сводимости (сводимости с сохранением соответствия ребер), которая будет применяться в данной главе при исследовании сводимости многоиндексных задач к классу задач поиск потока в сети. Основные особенности предлагаемой схемы:

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

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

Таким образом, рассматриваемая схема сведения является частным случаем схемы, описанной в определении 3.1, для которой s2 equal, s3 edge.

Определение 4.1. Пусть W – класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является t1 | t2 equal | t3 edge сводимым к классу W WGraph, если класс W является t1 | t 2 | t сводимым к классу W, и дополнительно произвольная задача w w( A, b, b, c) W, а также соответствующая ей задача z zMCC (G; lij, uij, eij, (i, j ) AG ) W удовлетворяют следующим условиям. Найдутся такие инъективные функции : {1,..., nrow( A)} AG, : {1,..., ncol ( A)} AG, что – если xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z, то ( x (1),..., x ( ncol( A)) ) будет являться оптимальным (допустимым) решением задачи w, соответствующим решению задачи z.

Замечание. В качестве величины b * выбрана величина, значение которой эквивалентно отсутствию (в данном контексте) верхней пропускной способности дуги.

Схематично концепция t1 | t2 equal | t3 edge сводимости представлена на рис. 4.1.

Согласно определению 4.1, в случае t1 | t 2 equal | t3 edge сводимости класса W к классу W WGraph гарантируется, что если wW, z zMCC (G; lij, uij, eij (i, j ) AG ) WGraph и z является задачей, соответствующей задаче w, то при построении задачи поиска потока минимальной стоимости пропускные способности и стоимости дуг в задаче определяются через коэффициенты задачи w, а решение задачи w находится через подмножество компонент решения задачи z. Тогда, согласно утверждению 2.2, можно предложить алгоритм решения задачи w, основанный на решении соответствующей (O(| VG |), O(| VG | | AG |)) вычислительных операций, где (n, m) и (n, m) – количество вычислительных операций, требуемых для решения задачи поиска максимального потока соответственно в сети с n вершинами и m дугами. Обзор оценок вычислительной сложности для известных потоковых алгоритмов можно найти, например, в [149, 151, 172]. Если дополнительно известно, что W WTree, то для решения задачи z может быть применен алгоритм поиска потока минимальной стоимости в древовидной сети. Тогда, согласно утверждению 2.4, можно предложить алгоритм решения задачи w, основанный на решении соответствующей задачи z поиска потока минимальной стоимости в древовидной сети и имеющий вычислительную сложность O(t1 t2 t3 | V |2 ).

Далее в данной главе будут рассмотрены вопросы сводимости класса W (M ) к классам WGraph и WTree, а также некоторые обобщения.

4.2. Многоиндексные задачи с 2-вложенной структурой Вид задач линейного программирования класса W (M ) определяется заданным множеством M. Поэтому нас будет интересовать нахождение условий, которым должно сводимым к классу WGraph.

сводимым к классу WGraph, то для произвольной задачи wW (M ) матрица Matr (w) является абсолютно унимодулярной.

t1 | t 2 equal | t 3 edge сводимым к классу WGraph, и найдется такая задача wW (M ), что матрица Matr (w) не является абсолютно унимодулярной. Согласно [51], условие абсолютной унимодулярности матрицы является необходимым и достаточным условием целочисленности многогранника соответствующей системы линейных неравенств с целочисленными свободными коэффициентами. Отсюда существует задача w W (M ), удовлетворяющая следующим условиям:

– свободные коэффициенты задачи w являются целочисленными, – система ограничений задачи w совместна, – задача w не имеет целочисленных решений.

Класс W (M ) является t1 | t 2 equal | t3 edge сводимым к классу WGraph. Тогда рассмотрим задачу z WGraph, соответствующую задаче w. По определению 4.1 задача поиска потока минимальной стоимости z совместна и пропускные способности сети в задаче z являются целочисленными. Матрица системы ограничений задачи z является абсолютно унимодулярной, отсюда задача z имеет целочисленное оптимальное решение.

Тогда, согласно определению 4.1, задача w также имеет целочисленное оптимальное решение. Получаем противоречие. Таким образом, предположение неверно. Теорема доказана.

Определение 4.2. Множество M, M 2 N ( s ), называется k-вложенным, если существует разбиение множества M на k подмножеств M i { f1(i ),..., f mii ) }, i 1, k, что Лемма 4.1. Пусть M 2 N ( s ) и множество M является 1-вложенным, тогда Было найдено следующее достаточное условие сводимости.

L | L equal | L edge сводимым к классу WGraph, достаточно, чтобы множество M было 2вложенным.

Доказательство. Пусть множество M 2 N ( s ) является 2-вложенным. Тогда общности, будем считать (для удобства описания схемы сведения), что в противном случае, добавим недостающие двусторонние неравенства, в качестве нижней границы которых выберем ноль, в качестве верхней – достаточно большую величину, z zMCC (G; lij, uij, eij, (i, j ) AG ) WGraph, соответствующей задаче w.

Определим функцию следующим образом:

таким образом, в задаче z нижняя и верхняя границы данной дуги будут составлять таким образом, в задаче z нижняя и верхняя границы данной дуги будут составлять Определим функцию следующим образом: каждой переменной xFN ( s ) поставим следовательно, N ( s) f1(1).

Покажем, что построенная задача z совместна тогда и только тогда, когда совместна исходная задача w. Действительно, пусть x FN ( s ), FN ( s ) E N ( s ) – допустимое решение системы ограничений задачи w. Определим циркуляцию yij, (i, j ) A, в графе G следующим образом:

рассчитывается однозначно через ограничение баланса (2.5) согласно структуре По построению и с учетом ограничения (3.1) справедливы следующие соотношения Тогда в соответствии с введенной функцией набор yij, (i, j ) A, будет являться допустимой циркуляцией задачи z.

Далее, пусть yij, (i, j ) AG – допустимая циркуляция задачи z. Согласно введенной FN ( s ) E N ( s ). По построению, с учетом введенной функции и с учетом ограничения (2.6), справедливы соотношения (4.1)–(4.4). Отсюда построенный набор является допустимым решением задачи w.

Пусть yij, (i, j ) AG, – циркуляция минимальной стоимости в задаче z. Используя FN ( s ) E N ( s ), который (как показано выше) является допустимым решением задачи w.

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

Как уже было показано выше, построенный таким образом набор yij, (i, j ) AG, является yij, (i, j ) AG, – циркуляция минимальной стоимости в задаче z. Таким образом, предположение неверно, и построенный набор xFN ( s ), FN ( s ) E N ( s ), является оптимальным решением задачи w.

Далее проведем анализ сложности вычислительных процедур, связанных с построением задачи z и построением решения задачи w по решению задачи z. Заметим, что исходная задача w содержит | E N (s ) | переменных. По построению граф G в задаче z определению 4.2 множества M 1 и M 2 являются 1-вложенными. Тогда по лемме 4. выполняется | VG | O(| EN (s ) |), | AG | O(| EN (s ) |). Отсюда построение задачи z требует линейных от размера матрицы Matr (w) вычислительных операций. Схема построения вычислительных операций. Отсюда W (M ) является L | L equal | L edge сводимым к классу WGraph. Теорема доказана.

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

Алгоритм 4.1. Решение 2-вложенных многоиндексных задач.

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

Шаг 2. Найти оптимальное решение (допустимое решение) задачи z, используя алгоритм 2.2 (алгоритм 2.1). Если задача z несовместна, то w также несовместна, и алгоритм завершен; иначе переход на шаг 3.

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

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

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

Следствие 4.1. Пусть множество M 2 N ( s ) является 2-вложенным, тогда алгоритм 4.1 решения задач класса W (M ) и класса WZ (M ) (систем класса D(M ) и класса DZ (M ) ) требует вычислительных операций.

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

Утверждение 4.1. Пусть множество M 2 N ( s ) является 2-вложенным, тогда существует алгоритм решения задач класса W (M ) и класса WZ (M ) (систем класса D(M ) вычислительных операций.

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

M 1 M 2, если существует подмножество g N ( s2 ), | g | s1 и биективная функция Содержательно определение 4.4 означает, что при «игнорировании» индексов множества N (s2 ) \ g для любой задачи класса W ( M 1 ) существует задача класса W ( M 2 ) содержащая (с точностью до перенумерации индексов ) ограничения соответствующей задачи класса W ( M 1 ).

унимодулярной, то существует задача w2 W (M 2 ), что матрица Matr (w2 ) также не является абсолютно унимодулярной.

Доказательство. Пусть выполняются условия леммы. Тогда по определению 4. существует подмножество g N (s2 ), | g | s1 и биективная функция : g N (s1 ), что Покажем, что для любой задачи w1 W (M 1 ) существует задача w2 W (M 2 ), что Matr ( w1 ) w2 w(s2 ; n1,..., n2 ;{af },{bFf }, f M 2 ;{cN ( s2 ) }) row( w1, f1, F f ) находящиеся на пересечение со столбцами Matr (w2 ; ( f 2, F f ); Fg (1,1,...,1) g, Fg E g ) размера 1 | E N ( s1 ) | совпадают с точностью до перестановки столбцов, которая определяется функцией. Отсюда матрица Matr (w1 ) является подматрицей Matr (w2 ).

Следовательно, если существует задача w1 W (M 1 ), что матрица Matr (w1 ) не является абсолютно унимодулярной (т.е. содержит минор отличный от 0, 1, 1 ), то существует задача w2 W (M 2 ) такая, что Matr (w2 ) также содержит минор отличный от 0, 1, 1. Лемма доказана.

Лемма 4.3. Пусть M 2 N ( s ). Если выполняется одно из следующих трех условий:

1. s 3, M {{1,2},{1,3},{2,3}};

2. s 3, M {{1},{2},{3}} ;

3. s 4, M {{1,2},{2,3},{1,4}} ;

то существует wW (M ), что матрица Matr (w) не является абсолютно унимодулярной.

подматрицу Можно увидеть, что H 1 0 1 и det H 2.

2. Пусть s 3, M {{1},{2},{3}}. Рассмотрим произвольную задачу wW (M ) такую, что n1, n2, n3 3 и рассмотрим ее подматрицу ({1}, (1,3){2,3}), ({1}, (2,2){2,3}), ({1}, (2,3){2,3}), ({3}, (1,1){1,2}), ({3}, (2,2){1,2}), ({2}, (1,2){1,3}), ({2}, (3,3){1,3}) ;

(1,1,2) N (3), (1,1,3) N (3), (1,2,2) N (3), (2,2,2) N (3), (2,2,3) N (3), (3,1,3) N (3), (3,2,3) N (3) ).

3. Пусть s 4, M {{1,2},{2,3},{1,4}}. По определению n1, n2, n3 2, тогда выберем произвольную задачу wW (M ) и рассмотрим ее подматрицу ({1,2}, (1,1){3,4}), ({2,3}, (1,1){1,4}), ({2,3}, (1,2){1,4}), ({1,4}, (1,1){2,3}), ({1,4}, (1,2){2,3});

(1,1,1,2) N ( 4), (1,1,2,1) N ( 4), (1,1,2,2) N ( 4), (1,2,1,1) N ( 4), (2,1,1,1) N ( 4) ).

Замечание. Матрицы, используемые при доказательстве леммы 4.3, были получены при помощи параллельной программной системы, выполнявшейся на супер-ЭВМ вычислительного центра коллективного пользования ФГУП «РФЯЦ-ВНИИЭФ» [25].

Лемма 4.4. Пусть M 2 N ( s ). Для того, чтобы множество M было 1-вложенным, необходимо и достаточно, чтобы для любых f1, f 2 M существовали k, l {1,2}, k l, Доказательство. Доказательство необходимости. Пусть множество M является 1вложенным, тогда, согласно 4.2, множество M может быть представлено следующим j1, j2 {1,2,..., m}. Если j1 j 2, то f j1 f j2, иначе f j2 f j1.

k, l {1,2}, k l, что f k f l. Упорядочим элементы множества M по неубыванию их множество M является 1-вложенным. Лемма доказана.

Теорема 4.3. Пусть M 2 N ( s ). Для того, чтобы множество M было 2-вложенным, необходимо и достаточно, чтобы для любых f1, f 2, f 3 M существовали k, l {1,2,3}, Доказательство. Доказательство необходимости. Пусть множество M является 2вложенным, тогда, согласно определению 4.2, существует разбиение множества M на k, l {1,2,3}, k l, что алгоритм нахождения разбиения M 1 { f1(1),..., f m1 ) }, M 2 { f1( 2),..., f m22) } множества M Алгоритм 4.2. Разбиение множества M на два 1-вложенных множества.

Вход. Множество M 2 N ( s ), удовлетворяющее условию теоремы.

на шаг 2.

Шаг 2. Упорядочим элементы множеств M 1, M 2 по неубыванию их мощности, то алгоритм завершен; иначе переход на шаг 3.

переход на шаг 2; иначе переход на шаг 4.

Рассмотрим множество I I1 I 2 и упорядочим его элементы по неубываню их Приведем доказательство корректности построенного алгоритма. По построению к началу выполнения каждого из очередных шагов 2 справедливо M 1 M 2 и очередной элемент g j добавляется в M 1 либо в M 2. Таким образом, после завершения работы алгоритма M 1, M 2 является разбиением множества M. Далее покажем, что перед каждым из шагов 2 множества M 1, M 2 являются 1-вложенными.

Изначально M 1, M 2 и, согласно определению 4.2, являются 1-вложенными.

Пусть M l { f1(l ),..., f mll ) }, f i f i1, i 1, ml 1, l 1,2. Если на шаге 3 найдется l {1,2}, являться 1-вложенным. В случае перехода на шаг 4 справедливо f m1 ), f m22) g j, тогда f m11) I1, f m22) I 2, следовательно, I1, I 2 и существуют величины i1*,i2. Т.к. множества M 1, M 2 являются 1-вложенными, то I1 { f i (1),..., f m1) }, I 2 { f i ( 2),..., f m2) }. Схематично множества M 1 и M 2, как подмножества 2 N ( s ), можно отобразить следующим образом:

По построению q g j, q I. С другой стороны, согласно построенному алгоритму, | g j | q, q I, отсюда g j q, q I. Рассмотрим произвольные q I1, q I 2. Как уже было показано g j q, q и q, q g j, тогда, согласно условию леммы, выполняется одно из следующих соотношений: q q или q q. Отсюда по лемме 4.4. множество I является 1-вложенным и qs qs 1, s 1, | I | 1. По построению q1 I t. Далее либо f i*( r1 g j. Отсюда построенное множество M r : M r \ I r {g j } является 1-вложенным.

Схематично построенные на шаге 4 множества M 1 и M 2, как подмножества 2 N ( s ), можно отобразить следующим образом:

Следовательно, после завершения работы алгоритма построенные множества M 1, M 2 представляют собой разбиение множества M и являются 1-вложенными. Теорема доказана.

Следствие 4.2. Пусть M 2 N ( s ). Если | M | 2s 1, то множество M не является 2вложенным. Если | M | s 2, то множество M не является 1-вложенным.

Доказательство. Пусть | M | 2s 1. Т.к. M 2 N ( s ) и N (s) {1,..., s}, то найдутся три различных множества f1, f 2, f 3 M, что | f1 || f 2 || f3 |. Тогда f k fl для любых k, l {1,2,3}, k l. Отсюда по теореме 4.3. множество M не является 2-вложенным.

множества f1, f 2 M, что | f1 || f 2 |. Тогда по лемме 4.4 множество M не является 2-вложенным. Следствие доказано.

Заметим, что критерий 2-вложенности множества M, сформулированный в теореме 4.3, и следствие 4.2 позволяют предложить следующий алгоритм проверки два вложенности множество M.

Алгоритм 4.3. Проверка 2-вложенности множества M.

Шаг 1. Если | M | 2s 1, то множество M не 2-вложенное, алгоритм завершен;

иначе переход на шаг 2.

Шаг 2. Если для каждой тройки f1, f 2, f 3 M выполняется условие теоремы 4.3, то множество M является 2-вложенным; иначе множество M не является 2-вложенным.

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

Утверждение 4.2. Алгоритм 4.3 проверки 2-вложенности множества M требует O( s 4 ) вычислительных операций.

Доказательство. Шаг 1 алгоритма связан с подсчетом числа элементов множества M, причем если | M | 2s 1, то алгоритм завершается. Таким образом, шаг 1 требует O(s) вычислительных операций. Шаг 2 алгоритма связан с перебором всех троек f1, f 2, f 3 M, причем, на данном шаге | M | 2s. Отсюда общее число таких троек не превышает 8s 3. Для каждой тройки множеств f1, f 2, f3 проверяется вложенность каждого из множеств в остальные, всего 6 проверок. В силу того, что M 2 N ( s ), выполняется:

| f | s для каждого f M. Тогда проверка вложенности одного множества может быть осуществлена, используя O(s) вычислительных операций. Таким образом, шаг 2 требует O( s 4 ) вычислительных операций. Утверждение доказано.

Проведем анализ сложности алгоритма разбиения 2-вложенного множества M на два 1-вложенных множества, используемого при доказательстве теоремы 4.3.

Утверждение 4.3. Алгоритм 4.2 разбиения 2-вложенного множества M на два 1вложенных множества требует O( s 3 ) вычислительных операций.

Доказательство. Согласно следствию 4.2, т.к. множество M является 2вложенным, то | M | 2s. Напомним, что M 2 N ( s ), и следовательно выполняется: | f | s для каждого f M. Тогда проверка вложенности пар множеств из M может быть осуществлено, используя O(s) вычислительных операций.

Шаг 1 алгоритма связан с сортировкой множества M по неубыванию мощности множеств, входящих в M. Данная сортировка может быть осуществлена, используя O( s 2 ) вычислительных операций (более точная оценка не изменит итоговую оценку алгоритма). Далее алгоритм состоит из | M | O(s) повторений шагов 2, 3, 4. Шаг 2 связан с сортировкой множеств M 1, M 2 по неубыванию мощности множеств, входящих в M 1, M 2. Выполнение данной сортировки на шаге 2 можно избежать, если выполнять (сортировка была указана на шаге 2 лишь для краткости изложения доказательства теоремы 4.3). Шаг 3 связан с проверкой условий f m1) g j, f m22) g j и следовательно, требует O(s) вычислительных операций. Отметим, что при выполнении шага справедливо соотношение | M1 | | M 2 | j. Тогда построение множеств I1, I 2 требует O( js ) вычислительных операций. Т.к. I M1 M 2, то | I | j, следовательно, его построение и упорядочивание требует O( j 2 ) вычислительных операций. Определение t, r вычислительных операций. Таким образом, выполнение алгоритма 4.2 требует O( s 2 ) + O(s)O(s) + доказано.

Далее рассмотрим произвольные множества выполняется следующее условие:

Условие (4.5) выполняется тогда и только тогда, когда существуют такие элементы aij N (s), j {1,2,3} \ {i}, i {1,2,3}, что Множество A {aij | j {1,2,3} \ {i}, i {1,2,3}} будем называть множеством, разделяющим f1, f 2, f 3. Обозначим через A( f1, f 2, f 3 ) множество всех разделяющих f1, f 2, f 3 множеств.

Из теоремы 4.3, используя понятие разделяющего множества, можно сформулировать следующее следствие.

aij f i, aij f j, j {1,2,3} \ {i}, i {1,2,3}. Обозначим через p(A) следующую величину разделяющих f1, f 2, f 3, множества мощности d ( f1, f 2, f 3 ) с максимальным значением величины p(A) :

Решение A ( f1, f 2, f 3 ) задачи (4.6) обладает следующим важным свойством.

A* ( f1, f 2, f 3 ) {aij | j {1,2,3} \ {i}, i {1,2,3}}, где aij f i, aij f j, j {1,2,3} \ {i}, i {1,2,3}.

Доказательство от противного. Предположим, что выполняются условия леммы, и найдутся такие i, j, k {1,2,3}, i j, i k, j k, что aij f k, но aij akj. Рассмотрим множество A {a | s {1,2,3} \ {t}, t {1,2,3}}, построенное следующим образом По предположению akj aij f k, при этом по построению akj aij f j. Отсюда доказательство, рассмотрев следующие два возможных случая:

По построению akj aij f i и aki aki f i, таким образом, akj aki. По условию akj aki.

Отсюда p(A) Следовательно, p( A) p( A ( f1, f 2, f 3 )) 1. Получаем противоречие.

2. Пусть akj aki. По предположению akj aij. По построению akj f k и aik f k, тогда akj aik. Далее по построению akj f j, a * , a * f j, тогда akj a *, a *. Отсюда Получаем противоречие. Таким образом, предположение неверно. Лемма доказана.

Лемма 4.6. Пусть M 2 N ( s ). Если множество M не является 2-вложенным, то выполняется одно из следующих трех условий:

– {{1,2},{1,3},{2,3}} M, – {{1},{2},{3}} M, – {{1,2},{2,3},{1,4}} M.

Доказательство. Пусть множество M 2 N ( s ) не является 2-вложенным. Тогда, согласно следствию 4.3, найдутся такие f1, f 2, f 3 M, что A( f1, f 2, f 3 ). Рассмотрим aij f i, aij f j, j {1,2,3} \ {i}, i {1,2,3}, являющееся решением задачи (4.6). Схематично будем представлять возможные комбинации множества A ( f1, f 2, f 3 ) в виде графа G f с {(ij, kl) | aij akl, ij kl, ij, kl V }. Проведем доказательство, рассмотрев следующее возможные два случая.

1. Пусть для каждого i {1,2,3} существует t i {1,2,3} \ {i}, что aiti f ki, где ki {1,2,3} \ {i, ti }. Рассмотрим элементы a1t1, a2t2, a3t3. По построению И следовательно a1t1 a2t2, a3t3, a2t2 a1t1, a3t3, a3t3 a1t1, a2t2. Тогда подграф графа G f, индуцированный подмножеством вершин {1t1,2t 2,3t 3 }, будет иметь вид, представленный на рис. 4.4.

Отсюда {{a1t1 },{a2t2 },{a3t3 }} M ({a1t1, a2t2, a3t3 }) и, по определению 4.4, {{1},{2},{3}} M.

aij f k, где k {1,2,3} \ {i, j}. Не уменьшая общности, будем считать, что i 1, в противном случае перенумеруем элементы. Тогда a12 f 3, a13 f 2. Согласно лемме 4.5, Следовательно, akl alm, m, k {1,2,3} \ {l}, l {1,2,3}. По построению a12 f 3, a13 f 3, a32 a12 f1, a31 f1, отсюда a31 a32. Далее возможен один из двух подслучаев:

a21 a31 или a21 a31.

2.1. Пусть a21 a31. Тогда граф G f будет иметь вид, представленный на рис. 4.5.

Отсюда {{a12, a13},{a13, a21},{a12, a21}} M ({a12, a13, a21}) и, по определению 4.4, {{1,2},{1,3},{2,3}} M.

2.2. Пусть a21 a31. Тогда граф G f будет иметь вид, представленный на рис. 4.6.

Отсюда {{a12, a13},{a13, a21},{a12, a31}} M ({a12, a13, a21, a31}) и, по определению 4.4, {{1,2},{2,3},{1,4}} M. Лемма доказана.

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

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

– {{1,2},{1,3},{2,3}} M ;

– {{1},{2},{3}} M ;

– {{1,2},{2,3},{1,4}} M.

Тогда, согласно леммам 4.2, 4.3, найдется wW (M ), что Matr (w) не является абсолютно предположение неверно. Теорема доказана.

Согласно теоремам 4.2 и 4.4, найденное условие 2-вложенности является необходимыми и достаточным условием сводимости (согласно введенной концепции сведения) многоиндексных задач к задаче поиска потока минимальной стоимости. Более того, оказывается, что предложенная при конструктивном доказательстве теоремы 4. схема сведения класса многоиндексных задач W (M ) с 2-вложенным множеством M, требующая линейных вычислительных затрат, является (в рамках рассматриваемой концепции t1 | t2 equal | t3 edge сводимости к классу WGraph ) оптимальной в том смысле, что – сведение с использованием вычислительных затрат асимптотически меньших линейных невозможно в связи с необходимостью считывания входных данных задачи (асимптотически меньшая оценка понимается в смысле оценки o(), «о малое», принятой при анализе сложности алгоритмов [179]);

– сколь угодное увеличение вычислительных затрат на сведение не приводится к расширению класса многоиндексных задач, сводимых к классу WGraph.

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

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

j1J1 j2J 2 j3J M {{1},{1,2},{2,3}} и s 3. Множество M является 2-вложенным, т.к. существует разбиение M1 {{1},{1,2}}, M 2 {{2,3}}, удовлетворяющее определению 4.2. Отсюда, согласно теореме 4.2, класс W (M ) является L | L equal | L edge сводимым к классу доказательстве теоремы 4.2, на примере задачи (4.7)-(4.11). Пусть | J1 || J 2 || J 3 | 2.

Приведем транспортную сеть, определяющую задачу поиска потока минимальной стоимости, соответствующую исходной многоиндексной задаче (см. рисунок 4.7). На рисунке 4.7 для ряда дуг приведены их пропускные способности и/или стоимости. Дуги, у неограниченную верхнюю пропускные способности. Дуги, у которых не указаны стоимости, имеют нулевую стоимость. Согласно доказательству теоремы 4.2 и алгоритму 4.1, решение исходной многоиндексной задачи определяется следующим образом: каждой переменной xi1i2 i3 многоиндексной задачи (4.7)-(4.11) присваивается значение потока вдоль дуги (v( j2, j3 ){2, 3}, v( j1, j2, j3 ){1, 2, 3} ), который в свою очередь определяется как поток минимальной стоимости данной сети.

многоиндексных задач класса W (M ), основанного на сводимости к классу задач поиска потока в сети, при решении ряда рассмотренных ранее многоиндексных задач. Пусть M 2 N ( s ) является 2-вложенным. Согласно теореме 4.2, класс задач W (M ) сводим к поиску потока в сети с O(| EN (s ) |) вершинами и O(| EN (s ) |) дугами. В рамках исследуемой схемы сведения пропускные способности дуг вспомогательной сети моделируют двусторонние ограничения исходной многоиндексной задачи. В случае несовместности многоиндексной задачи, соответствующая потоковая задача также является несовместной.

Тогда можно построить алгоритм решения задач класса S (M ), основанный на сводимости к поиску потока в сети по схеме, предложенной при доказательстве теоремы 4.2, и решении соответствующей задачи поиска потока в несовместной сети при помощи алгоритма 2.5. Применим для поиска потока минимальной стоимости заданной величины алгоритм, предложенный в работе Орлина [172], для поиска максимального потока воспользуемся алгоритмом Слейтора-Тарьяна [181]. Данные алгоритмы используются в алгоритме 2.2 (на шаге 2 алгоритма 2.5). Тогда, согласно утверждению 2.5, можно сформулировать следующий результат.

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

быть применен алгоритм 2.8, который, согласно утверждению 2.8, требует O(k log p) проверок совместности системы ограничений вида (v ). Здесь k | E f | и система ограничений вида (v ) относится к классу D(M H ). Также отметим, что | H | 2 s, | E f || EN (s ) |, отсюда k O(2s | EN ( s ) |) O(| EN ( s ) |). Пусть множество M H является 2вложенным. Тогда, согласно утверждению 4.1, соответствующая системы вида (v ) может быть решена, используя O(| EN ( s ) |2 log | EN ( s ) |) вычислительных операций. Отсюда Утверждение 4.5. Пусть M, H 2 N ( s ) и множество M H является 2-вложенным, O(| EN ( s ) |3 log | EN ( s ) | log p) вычислительных операций.

Дополнительно рассмотрим задачу U max min (M, H ), решение которой, согласно утверждению 2.9, связано с решением O(log p) систем вида (v ). Таким образом, справедливо утверждение:

Утверждение 4.6. Пусть M, H 2 N ( s ) и множество M H является 2-вложенным, O(| EN ( s ) |2 log | EN ( s ) | log p) вычислительных операций.

В качестве замечания отметим, что если множество M 2 N ( s ) не является 2вложенным, то возможно отыскание 2-вложенного подмножества M M и применение для решения систем класса D(M ) алгоритма 4.1. Полученное решение может быть итерационным методом ортогональных проекций, описанным в главе 2.

Дополнительно проиллюстрируем полученные результаты при решении ряда прикладных многоиндексных задач, поставленных в главе 1. Транспортная задача с M {{i},{k},{i, j},{ j, k}}. При этом s 3 и | EN ( s ) || I || J || K |. Заметим, что множество M является 2-вложенным, т.к. существует разбиение M1 {{i},{i, j}}, M 2 {{k},{ j, k}}, удовлетворяющее определению 4.2. Отсюда, согласно утверждению 4.1, транспортная O(| I |2 | J |2 | K |2 log 2 (| I || J || K |)) вычислительных операций. Многокритериальная задача выбора плана перевозок (1.1)-(1.5),(1.9) относится к классу U (M, H ), где H {{k}}.

Рассмотрим соответствующие задачи U (M, H ) и U max min (M, H ). Заметим, что множество M H {{i},{k},{i, j},{ j, k}} M, как уже было показано, является 2-вложенным. Таким образом, согласно утверждениям 4.5, 4.6, задачи U (M, H ) и U max min (M, H ) могут быть O(| I |2 | J |2 | K |2 log(| I || J || K |) log p) вычислительных операций соответственно.

Проблема формирования допустимого портфеля заказов (1.10)-(1.14) относится к классу D(M ), где M {,{ j},{i, t},{ j, t}}. При этом s 3 и | EN ( s ) || I || J || T |. Множество M является 2-вложенным, т.к. существует разбиение M1 {,{ j},{ j, t}}, M 2 {{i, t}}, удовлетворяющее определению 4.2. Отсюда, согласно утверждению 4.1, проблема O(| I |2 | J |2 | T |2 log(| I || J || T |)) вычислительных операций. В случае несовместности (1.10),(1.11),(1.13)-(1.17) формирования портфеля заказов с возможными нарушениями требуемых объемов работ по заказам, относящаяся к классу S (M ). Тогда, согласно утверждению 4.4, проблема формирования портфеля заказов с возможными нарушениями O(| I |2 | J |2 | T |2 log 2 (| I || J || T |)) вычислительных операций. Рассматривается также задача формирования портфеля заказов с возможными нарушениями сроков выполнения работ Множество M является 2-вложенным, отсюда, согласно утверждению 4.1, задача формирования портфеля заказов с возможными нарушениями сроков выполнения работ операций.

4.3. Многоиндексные задачи с 1-вложенной структурой Далее будем рассматривать вопросы нахождения условий, которым должно сводимым к классу WTree. Как было определено ранее, класс WTree представляет собой класс задач поиска циркуляции минимальной стоимости в древовидной сети, здесь под древовидной сетью понимается сеть, представляющая собой корневое ориентированное дерево, дополненное дугами из листьев в корень. Таким образом, WTree WGraph.

Исследование сводимости к классу WTree представляет особый интерес, т.к. задачи данного класса эквивалентны задачам поиска потока минимальной стоимости в древовидной сети zMCFT (G; ai, bi, ci, i V ). Таким образом, согласно утверждениям 2.3, 2.4:

Утверждение 4.7. Существует поиска оптимального (допустимого) решения задачи zMCC (G; lij, uij, eij, (i, j ) AG ) WTree, требующий O(| VG | ) ( O(| VG |) ) вычислительных операций.

Пусть множество M 2 N ( s ) является 1-вложенным, согласно определению 4.2, множество M при этом также будет является и 2-вложенным. Тогда, применяя схему сведения, описываемую при доказательстве теоремы 4.2, для задач wW (M ) будет построена соответствующая задача z WGraph. Отметим, что если M является 1вложенным, то при доказательстве теоремы 4.2 можно считать, что M 1 M, M 2.

Несложно увидеть, что в данном случае сеть, описывающая задачу z, будет иметь древовидную структуру, и тем самым z WTree. Тогда справедливо следующее следствие.

L | L equal | L edge сводимым к классу WTree, достаточно, чтобы множество M было 1вложенным.

Конструктивная схема доказательства теоремы 4.2 в случае 1-вложенности множества M позволяет для задач класса W (M ) и для систем линейных неравенств класса D(M ) предложить алгоритм решения, основанный на сводимости к классу WTree.

Алгоритм 4.4. Решение 1-вложенных многоиндексных задач.

Вход. Задача wW (M ) (система w D(M ) ), где M – 1-вложенное.

Шаг 1. Используя конструктивную схему, применяемую при доказательстве теоремы 4.2 (необходимо положить M1 M, M 2 ), построить задачу z WTree, соответствующую w. Перейти на шаг 2.

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

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

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

По аналогии с алгоритмом 4.1 алгоритм 4.4 применим также при исследовании целочисленного случая. Заметим, что для задачи z zMCC (G; lij, uij, eij, (i, j ) AG ) WTree, соответствующей задаче w, согласно доказательству теоремы 4.2, выполняется:

| VG | O(| EN (s ) |), | AG | O(| EN (s ) |). Отсюда, с учетом утверждения 4.7 справедливо следующее утверждение.

Утверждение 4.8. Пусть множество M 2 N ( s ) является 1-вложенным, тогда существует алгоритм решения задач класса W (M ) и класса WZ (M ) (систем класса D(M ) и класса DZ (M ) ), требующий O(| EN (s ) | ) ( O(| EN (s ) |) ) вычислительных операций.

Можно предложить следующий алгоритм проверки 1-вложенности множества M.

Алгоритм 4.5. Проверка 1-вложенности множества M.

Шаг 1. Если | M | s 2, то множество M не является 1-вложенным, и алгоритм завершен; иначе переход на шаг 2.

Шаг 3. Если выполняется условие является 1-вложенным; иначе множество M не является 1-вложенным. Алгоритм завершен.

Утверждение 4.9. Алгоритм 4.5 корректно решает задачу проверки 1-вложенности множества M и требует O( s 2 ) вычислительных операций.

Доказательство. Если | M | s 2 на шаге 1, то, согласно следствию 4.2, множество M не является 1-вложенным. Далее пусть выполнен шаг 2 алгоритма и элементы множества M упорядочены по неубыванию их мощности, M { f1,..., f| M |}, | f j || f j 1 |, j 1, | M | 1. Согласно лемме 4.4, для того, чтобы множество M было 1-вложенным, необходимо и достаточно, чтобы для любых i, j {1,...,| M |}, i j, выполнялось fi f j или f j fi. Пусть i j, тогда по построению | fi || f j |. Следовательно, f j fi. Таким образом, для того, чтобы множество M было 1-вложенным, необходимо и достаточно, чтобы для любых i, j {1,...,| M |}, i j, выполнялось транзитивности данный критерий может быть записан в следующей эквивалентной постановке. Для того, чтобы множество M было 1-вложенным, необходимо и достаточно, чтобы Следовательно, алгоритм 4.5 корректно решает задачу проверки 1-вложенности множества M.

Шаг 1 алгоритма связан с подсчетом мощности множества M и проверкой условия | M | s 2, следовательно, может быть выполнен, используя O(s) вычислительных операций. На шаге 2 алгоритма | M | s 1, следовательно, выполняемая сортировка множества M может быть осуществлена, используя O( s 2 ) вычислительных операций.

Шаг 3 связан с O(s) проверками вложенности множеств, мощность которых не превосходит s. Следовательно, каждая такая проверка вложенности требует O(s) вычислительных операций. Таким образом, алгоритм требует O( s 2 ) вычислительных операций. Утверждение доказано.

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

Рассмотрим задачу согласно определению класса WTree, существует корневое ориентированное дерево G (V, A) с корнем s V и множеством листьев T V, что A A {(t, s) | t T }.

Обозначим через t (i ) путь из корня s к листу i в дереве G, таким образом, Тогда обозначим через T (G) множество всех путей из корня к листьям в графе G, т.е.

Пусть t (v0,..., vk ) – путь в графе G и e A. Тогда для удобства будем обозначать e t, если путь t проходит через дугу e, т.е. найдется j {0,..., k 1}, что (v j, v j 1 ) e ; в противном случае, будем обозначать e t. Далее пусть e1, e2 A, тогда будем обозначать (v j1, v j1 1 ) e1, (v j2, v j2 1 ) e2 ; в противном случае, будем обозначать e1 e2.

Лемма 4.7. Пусть z zMCC (G; lij, uij, eij, (i, j ) A) WTree и существуют такие дуги e1, e2, e3, e4, e5 A, что где d uei. Тогда либо задача z несовместна, любо существует допустимое решение xe, e A, задачи z такое, что {1,2,3} {xe | e A}.

выполняются условия леммы. Тогда G (V, A) и существует корневое ориентированное дерево G (V, A) с корнем s V и множеством листьев T V, что A A {(t, s) | t T }.

Не уменьшая общности, будем считать, что e1, e2, e3, e4, e5 A A и le 0, ue d, e A \ A ; в противном случае, всегда можно перейти к эквивалентной постановке задачи z, удовлетворяющей данным требованиям.

Покажем, что выполняется условие (4.12), иначе задача z несовместна.

Действительно, предположим, что e4 e5. Тогда из древовидности сети следует, что задача z несовместна.

Далее пусть условие (4.12) выполняется. Отсюда выполняется одно из следующих двух условий Отдельно рассмотрим два случая: (4.13) и (4.14).

иначе задача z несовместна. Далее обозначим T1 {t | t T (G), e4 t, e5 t}. Тогда tT иначе задача z несовместна. Схематично данный случай приведен на рис. 4.8.

Далее пусть условие (4.15) выполняется. Тогда возможны лишь два подслучая :

a. существует t2 T1, что min ue 4, 1.а. Пусть существует t2 T1, что min ue 4. Тогда построим допустимый поток xe, e A, в задаче z по следующему алгоритму:

Шаг 4. xe, e A \ A, определяется однозначно через (2.5).

Для полученного допустимого решения справедливо:

2,3 {xe | e A}.

1.b. Пусть min ue 4, t T1. Из условий леммы и условия (4.15) следует, что существуют t2, t3 T1, что min ue {1,2}, min ue 3. Тогда построим допустимый поток xe, e A, в задаче z по следующему алгоритму:

Шаг 5. xe, e A \ A, определяется однозначно через (2.5).

Для полученного допустимого решения справедливо: xe {0,1,3,4,5}, e A. Тогда иначе задача z несовместна. Схематично данный случай приведен на рис. 4.9.

Далее возможны лишь четыре подслучая:

a. Существуют t1 T1 и t 2 T2, что min ue 4 и min ue 5 ;

b. существует t1 T1, что min ue 4 и min ue 5, t T2 ;

c. существует t1 T2, что min ue 5 и min ue 4, t T1 ;

2.a. Пусть существуют t1 T1 и t2 T2, что min ue 4 и min ue 5. Тогда построим допустимый поток xe, e A, в задаче z по следующему алгоритму:

Шаг 5. xe, e A \ A, определяется однозначно через (2.5).

Для полученного допустимого решения справедливо 1,2,3 {xe | e A}.

2.b. Пусть существуют t1 T1, что min ue 4 и min ue 5, t T2. Из условий леммы и условия (4.16) следует, что существуют t2, t3 T2 , что min ue 2, min ue 3. Тогда построим допустимый поток xe, e A, в задаче z по следующему алгоритму:

Шаг 5. xe, e A \ A, определяется однозначно через (2.5).

Для полученного допустимого решения справедливо xe {0,2,3,4,5,9}, e A. Тогда 1{xe | e A}.

2.c. Пусть существуют t1 T2, что min ue 5 и min ue 4, t T1. Из условий леммы и условия (4.16) следует, что существуют t2, t3 T2 , что min ue {1,2}, min ue 3. Тогда построим допустимый поток xe, e A, в задаче z по следующему алгоритму:

Шаг 5. xe, e A \ A, определяется однозначно через (2.5).

Для полученного допустимого решения справедливо xe {0,1,3,4,5,9}, e A. Тогда Получаем, что задача z, удовлетворяющая условиям леммы, либо несовместна, либо имеет допустимое решение xe, e A, такое, что {1,2,3} {xe | e A}. Лемма доказана.

Лемма 4.8. Пусть M 2 N ( s ). Если класс W (M ) является t1 | t2 equal | t3 edge сводимым к классу WTree, то класс W (M {}) также является t1 | t2 equal | t3 edge сводимым к классу WTree.

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

Т.к. W (M ) является t1 | t2 equal | t3 edge сводимым к классу WTree, то, согласно удовлетворяющих условиям определения 4.1. Далее опишем схему построения задачи z zMCC (G; lij, uij, eij, (i, j ) AG ) WTree, соответствующей задаче w.

Задача w отличаются от задачи w лишь наличием двусторонних ограничений на переменные. И при этом функция определяет дуги задачи z, соответствующие переменным исходной задачи. Таким образом, каждую из таких дуг можно заменить на пару последовательных дуг, первая из которых будет соответствовать переменной задачи, а вторая двустороннему ограничению на эту переменную. Тогда для построения задачи z модифицируем задачу z следующим образом. Пусть изначально z z. Для дуги (i) (u, v) преобразуем граф G следующим образом:

где pi – новая вершина, i 1, col ( A). Далее определим функции : {1,2,..., row( A)} AG, : {1,2,..., col ( A)} AG следующим образом:

Параметры lij, uij, eij, (i, j ) AG, задачи z определяются через функции и, согласно определению 4.1.

Таким образом, по построению задача z является задачей, соответствующей задаче w. Сеть, соответствующая задаче z, имеет по построению древовидную Следовательно класс WTree. Лемма доказана.

t1 | t2 equal | t3 edge сводимым к классу WTree, необходимо, чтобы множество M было 1вложенным.

Доказательство. Доказательство от противного, пусть M не является 1-вложенным, и класс W (M ) является t1 | t2 equal | t3 edge сводимым к классу WTree.

Т.к. множество M не является 1-вложенным, то, согласно лемме 4.4, найдутся такие Рассмотрим s -индексные наборы FN (s ), FN(s ), FN(s ), где Далее рассмотрим многоиндексные наборы F f и F f, где Пусть w W (M ) и рассмотрим следующую подматрицу H матрицы Matr (w) (т.е.

подматрицу матрицы системы ограничений задачи w ):

Для произвольной задачи w W (M ) справедливо:

Тогда выберем задачу w W (M ) со следующей системой ограничений:

где d 1 2 3 4 5 15. Тогда система (4.17)–(4.20) эквивалентна следующей системе линейных неравенств Отсюда задача w имеет единственное решение По предположению класс W (M ) является t1 | t2 equal | t3 edge сводимым к z zMCC (G; lij, uij, eij, (i, j ) AG ) WTree, соответствующую описанной выше задаче w.

Согласно определению 4.1, задача z удовлетворяет условию леммы 4.7. По лемме 4.7, задача z либо несовместна, либо имеет допустимое решение xij, (i, j ) AG, такое, что противоречие. Таким образом, предположение неверно. Теорема доказана.

Согласно следствию 4.4 и теореме 4.5, найденное условие 1-вложенности является необходимыми и достаточным условием сводимости (согласно введенной концепции сведения) многоиндексных задач к задаче поиска потока минимальной стоимости в древовидной сети. Более того, оказывается (как и для 2-вложенных множеств при сводимости к классу WGraph ), что предложенная при конструктивном доказательстве теоремы 4.2 схема сведения класса многоиндексных задач W (M ) с 1-вложенным множеством M, требующая линейных вычислительных затрат, является (в рамках оптимальной в том смысле, что – сведение с использованием вычислительных затрат асимптотически меньших линейных невозможно;

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

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

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

Рассмотрим задачу U (M, H ) и U max min (M, H ) M, H 2 N ( s ). Согласно утверждениям 2. и 2.9, решение данных задач связано с последовательным решением систем ограничений вида (v ), относящейся к классу D(M H ). Далее пусть множество M H является 1вложенным. Тогда, согласно утверждению 4.8, соответствующая система вида (v ) справедливы следующие утверждения.

O(| EN ( s ) |2 log p) вычислительных операций.

O(| EN ( s ) | log p) вычислительных операций.

прикладной многоиндексной задачи, поставленной в главе 1. Рассмотрим проблему формирования допустимого портфеля заказов (1.10)-(1.14). В случае несовместности ограничений связан с исследованием совместности системы (1.10),(1.11),(1.14), которая относится к классу D(M ), где M {{ j},{ j, t}}. При этом s 3 и | EN ( s ) || I || J || T |.

Заметим, что по определению 4.2 множество M является 1-вложенным. Отсюда, согласно утверждению 4.8, исследование несогласованности внутренних ограничений предприятия (при формировании портфеля заказов) может быть осуществлено, используя O(| I || J || T |) вычислительных операций.

4.4. Условия t1 | t2 Z | t3 Z сводимости целочисленности), представляющую собой обобщение рассмотренной ранее схемы t1 | t2 equal | t3 edge сводимости. Для данной схемы сведения будут обобщены Основные особенности предлагаемой схемы:

– при построении вспомогательной сети пропускные способности дуг определяются таким образом, что пропускные способности являются целочисленными в случае целочисленности свободных коэффициентов двусторонних неравенств системы ограничений исходной задачи (такая особенность сведения отражается в процедуре, обозначаемой Z);

– при построении решения исходной задачи строится целочисленное решение в случае целочисленности потока в сети (такая особенность сведения отражается в процедуре, обозначаемой Z).

Таким образом, рассматриваемая схема сведения является частным случаем схемы, описанной в определении 3.1, для которой s2 Z, s3 Z.

Определение 4.5. Пусть W – класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является t1 | t2 Z | t3 Z сводимым к классу W WGraph, если класс W является t1 | t 2 | t 3 сводимым к классу W, и выполняются следующие условия. Пусть z zMCC (G; lij, uij, eij, (i, j ) AG ) W является задачей, соответствующей задаче w. Далее пусть xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z, а xi, i 1, col ( A) является соответствующим ему оптимальным (допустимым) решением задачи w. Тогда:

рис. 4.10.

Несложно увидеть, что исследуемая ранее схема t1 | t2 equal | t3 edge сводимости Действительно, согласно определению 4.1 в случае t1 | t2 equal | t3 edge сводимости выполняются условия целочисленности, описанные в определении 4.5. При этом схема t1 | t2 Z | t3 Z сводимости описывает более широкий класс схем сведения (по сравнению с t1 | t2 equal | t3 edge сводимостью), т.к. накладывает лишь условие целочисленности на процедуру сведения. Таким образом, согласно теореме 4.2, справедливо следующее следствие.

Следствие 4.5. Пусть L | L Z | L Z сводимым к классу WGraph достаточно, чтобы множество M было 2вложенным.

Далее покажем, что условие 2-вложенности является необходимым и достаточным условием P* | P* Z | P* Z сводимости многоиндексной транспортной задачи к задаче поиск потока минимальной стоимости, иначе неверной является известная гипотеза о неравенстве классов P и NP (см., например, [52]).

Теорема 4.6. Пусть M 2. Если класс W (M ) является P* | P* Z | P* Z сводимым к классу WGraph, то класс WZ (M ) разрешим за полиномиальное время.

Доказательство. Пусть выполняются условия теоремы. Тогда для каждой задачи wW (M ) P* | P* Z | P* Z сводимости количество вершин и дуг, а также значения пропускных способностей в соответствующей потоковой задаче z полиномиально зависят от размера задачи w. При этом, согласно определению 4.5, пропускные способности дуг в задаче z при целочисленных свободных коэффициентах двусторонних ограничений задачи w также являются целочисленными. Для общности отметим, что если w WZ (M ) содержит нецелочисленные свободные коэффициенты, то в силу целочисленности коэффициентов матрицы системы ограничений задачи w, задача w при помощи округления параметров может быть преобразована к эквивалентной постановке с целочисленными параметрами.

Как известно, матрица системы ограничений задачи линейного программирования z является абсолютно унимодулярной [51]. Тогда в силу целочисленности пропускных способностей дуг, целочисленное решение задачи может быть найдено за полиномиальное время [102]. Отсюда, согласно определению 4.5, построенное за полиномиальное время решение задачи w также будет являться целочисленным.

Следовательно, найденное решение также будет являться решением задачи wZ. Таким образом, класс задач целочисленного линейного программирования WZ (M ) разрешим за полиномиальное время. Теорема доказана.

Следствие 4.6. Пусть M 2. Если класс WZ (M ) является NP-трудным, то класс W (M ) не является P* | P* Z | P* Z сводимым к классу WGraph, в противном случае P NP.

Доказательство. Пусть класс задач WZ (M ) является NP-трудным, и класс W (M ) является P* | P* Z | P* Z сводимым к классу WGraph. Тогда по теореме 4.6 класс WZ (M ) полиномиально разрешимым. Отсюда, согласно концепции NP-трудности, P NP [52].

Следствие доказано.

WZ ( M1 ) является NP-трудным, то класс WZ (M 2 ) также является NP-трудным.

Доказательство. Пусть выполняются условия леммы. Проведем доказательство путем полиномиального сведения NP-трудного класса задач WZ ( M 1 ) к классу WZ ( M 2 ).

По определению 4.4 существует подмножество g N (s2 ), | g | s1 и биективная задачу w1 WZ (M1 ), w1 wZ (s1; n1, n,..., n1 ;{a f },{bFf }, f M1;{c N ( s1 ) }) и построим задачу следующим условиям:

Несложно увидеть, что по построению выполняются следующие условия:

a. если задача w2 несовместна, то задача w1 также несовместна;

b.1. если F * c*, то задача w1 несовместна;

b.2. если F * c*, то решение задачи w1 может быть построено по следующему правилу:

Количество переменных в задаче w1 равно n ni, по построению количество nrow(Matr (w2 )) соответственно. При этом Таким образом, Также отметим, что параметры b*, c* вычислимы за полиномиальное время от размера задачи w1. Отсюда выполненное сведение класса WZ ( M1 ) к классу WZ (M 2 ) реализуемо за полиномиальное время. Тогда из NP-трудности класса WZ ( M1 ) следует NP-трудность класса WZ (M 2 ) [52]. Лемма доказана.

условий:

1. s 3, M {{1,2},{1,3},{2,3}}, 2. s 3, M {{1},{2},{3}}, 3. s 4, M {{1,2},{2,3},{1,4}}, то класс WZ (M ) является NP-трудным.

Доказательство. 1. Пусть s 3, M {{1,2},{1,3},{2,3}}. Согласно [52], класс трехиндексных аксиальных задач о назначениях (4.21)-(4.25) является NP-трудным.

где eijk 0, i, j, k 1, n. Далее рассмотрим ограничение Легко увидеть, что система ограничений (4.21),(4.24) эквивалентна системе ограничений (4.21),(4.26). Таким образом, задача (4.21)-(4.25) может быть поставлена в виде (4.21)В свою очередь задача (4.21)-(4.23),(4.26),(4.25) включена в рассматриваемый класс WZ (M ). Следовательно, класс WZ (M ) является NP-трудным.

2. Пусть s 3, M {{1},{2},{3}}. Согласно [146], класс трехиндексных планарных задач о назначениях (4.27)-(4.29),(4.24),(4.25) является NP-трудным.

По аналогии с пунктом 1 доказательства, задача (4.27)-(4.29),(4.24),(4.25) может быть поставлена в виде (4.27)-(4.29),(4.26),(4.25), которая в свою очередь включена в рассматриваемый класс WZ (M ). Следовательно, класс WZ (M ) является NP-трудным.

полиномиального сведения к классу WZ (M ) класса трехиндексных планарных задач о назначениях (4.27)-(4.29),(4.24),(4.25), который, согласно [146], является NP-трудным.

w wZ (s; M ; n, n, n, n;{aFf },{bFf }, f M ;{cFN ( s ) }) WZ (M ) такую, что где 1 eijk. Тогда задача w представляет собой задачу целочисленного линейного программирования (4.30)-(4.34).

i1 1 i i2 1 i i1 1 i i1 1 i2 1 i3 1 i Заметим, что в силу, например, условий (4.30) и (4.33), если xi1i2i3i4, i1, i2, i3, i4 1, n, является допустимым решением задачи w, то xi1i2i3i4 {0,1}, i1, i2, i3, i4 1, n.

Далее пусть {xFN ( s ) } – оптимальное решение задачи w. Покажем, от противного, что выполняются следующие условия Предположим, что условие (4.35) не выполняется, т.е. существуют i1, i2, i3, i4 {1,..., n}, i1 i2, что xi*i i i 1. Отсюда Рассмотрим матрицу значений переменных {xFN ( s ) }, определенную следующим образом Покажем, что построенная матрица {xFN ( s ) } является допустимым решением задачи w. С учетом (i3, i4 ) {1,..., n}, i3, i4 1, n. Отсюда (i1, i4 ) {i3 | i1 (i3, i4 ), i3 {1,..., n}}, противного, что противоречие, предположение неверно и следовательно множество Тогда (i1, i3 ) {i4 | i1 (i3, i4 ), i4 {1,..., n}}, по аналогично можно показать, что | (i1, i3 ) | 1, i1, i3 1, n. Отсюда Таким образом, {xFN ( s ) } удовлетворяет (4.32). Следовательно, {xFN ( s ) } является допустимым решением задачи w. При этом Получаем противоречие, предположение неверно и условие (4.35) выполняется.

Далее обозначим yijk xiijk, i, j, k 1, n. В силу условия (4.35) и ограничений (4.30)i, j, k 1, n, является допустимым решением задачи Далее покажем от противного, что yijk, i, j, k 1, n, является оптимальным решением задачи (4.27)-(4.29),(4.24),(4.25). Предположим, что существует допустимое решение yijk, i, j, k 1, n, задачи (4.27)-(4.29),(4.24),(4.25), что Тогда опередим {x N ( s ) } следующим образом Несложно увидеть, что в силу условий (4.27)-(4.29),(4.24) построенная многоиндексная матрица {x N ( s ) } является допустимым решением задачи w, и при этом ci1i2i3i4 xi1i2i3i4 eijk yijk eijk yijk ci1i2i3i4 xi*1i2i3i4.

оптимальным решением задачи (4.27)-(4.29),(4.24),(4.25).

Таким образом, NP-трудный класс трехиндексных планарных задач о назначениях (4.27)-(4.29),(4.24),(4.25) полиномиально сводим к классу WZ (M ). Отсюда класс WZ (M ) является NP-трудным [52]. Лемма доказана.

P* | P* Z | P* Z сводимым к классу WGraph, необходимо и достаточно, чтобы множество M было 2-вложенным, в противном случае P=NP.

Доказательство. Пусть множество M 2 N ( s ) является 2-вложенным, то, согласно следствию 4.5, класс W (M ) является L | L equal | L edge сводимым к классу WGraph и, следовательно, является P* | P* Z | P* Z сводимым к классу WGraph.

Далее пусть множество M не является 2-вложенным, тогда, согласно лемме 4.6, выполняется одно из следующих условий – {{1,2},{1,3},{2,3}} M, – {{1},{2},{3}} M, – {{1,2},{2,3},{1,4}} M, и, согласно леммам 4.9, 4.10, класс WZ (M ) является NP-трудным. Отсюда на основании следствия 4.6 класс W (M ) не является P* | P* Z | P* Z сводимым к классу WGraph, в противном случае P NP. Теорема доказана.

Полученный результат является дополнительным обоснованием оптимальности условия 2-вложенности, как условия сводимости класса W (M ) к классу WGraph.

Действительно, согласно теоремам 4.2 и 4.4, найденное условие 2-вложенности является необходимыми и достаточным условием t1 | t 2 equal | t3 edge сводимости. При этом оказывается, что в случае полиномиальных вычислительных затрат применение более общего класса схем сведения, описываемых в рамках концепции P* | P* Z | P* Z сводимости, не приводит к расширению класса сводимых задач, иначе P NP.

Выводы Предложена схема t1 | t 2 equal | t3 edge сводимости (сводимости с сохранением соответствия ребер) класса задач линейного программирования к классу задач поиска потока в сети WGraph. При исследовании 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-вложенным;

– пусть множество M является 2-вложенным, тогда существует алгоритм решения задач O(| EN ( s ) |2 log | EN ( s ) |) вычислительных операций соответственно, данный алгоритм применим при исследовании целочисленного случая;

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

– пусть множество M H является 2-вложенным, тогда существуют алгоритмы O(| EN ( s ) |3 log | EN ( s ) | log p) и O(| EN ( s ) |2 log | EN ( s ) | log p) вычислительных операций соответственно.

При исследовании t1 | t 2 equal | t3 edge сводимости класса W (M ) к классу WTree установлено:

– для того, чтобы класс W (M ) являлся L | L equal | L edge сводимым к классу WGraph, достаточно, чтобы множество M было 1-вложенным;

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

– пусть множество M является 1-вложеннм, тогда существует алгоритм решения задач вычислительных операций соответственно, данный алгоритм также применим при исследовании целочисленного случая;

– пусть множество M H является 1-вложенным, тогда существуют алгоритмы O(| EN ( s ) |2 log p) и O(| EN ( s ) | log p) вычислительных операций соответственно.

Сформулирована схема t1 | t2 Z | t3 Z сводимости класса W (M ) к классу WGraph, являющаяся обобщением схемы t1 | t 2 equal | t3 edge сводимости. Установлено, что для необходимо и достаточно, чтобы множество M было 2-вложенным, в противном случае P=NP.

Глава 5. Сводимость с сохранением соответствия циклов Глава посвящена исследованию сводимости класса многоиндексных задач к классу задач поиска потока минимальной стоимости в сети с использованием схемы сведения с сохранением соответствия циклов [5, 7, 9, 15, 22]. Особенностью рассматриваемой концепции сводимости является существование соответствия между переменными исходной задачи и циклами вспомогательной сети. Предлагаемая схема сведения гарантирует, что произвольный оптимальный поток вспомогательной сети будет определять такое оптимальное решение исходной задачи, в котором переменным присваиваются значения потока вдоль соответствующих простых циклов. В рамках рассматриваемой схемы сведения в данной главе найдены условия сводимости класса многоиндексных задач линейного программирования к классу задач поиска потока в сети.

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

5.1. Концепция t1 | t2 equal | t3 cycle сводимости Введем схему t1 | t2 equal | t3 cycle сводимости (сводимости с сохранением соответствия циклов), которая будет применяться в данной главе при исследовании сводимости многоиндексных задач к классу задач поиск потока в сети. Основные особенности предлагаемой схемы:

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

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

Таким образом, рассматриваемая схема сведения является частным случаем схемы описанной в определении 3.1, для которой s2 equal, s3 cycle.

Определение 5.1. Пусть W – класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является t1 | t 2 equal | t3 cycle сводимым к классу WGraph, если класс W является t1 | t 2 | t сводимым к классу WGraph, и дополнительно произвольная задача w w( A, b, b, c) W, а также соответствующая ей задача z zMCC (G; lij, uij, eij, (i, j ) AG ) WGraph удовлетворяют следующим условиям. Найдутся такие инъективные функции : {1,..., nrow( A)} AG, : {1,..., ncol ( A)} C(G), что – если циркуляция xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z и yC, C C (G), является циклической декомпозицией данной циркуляции, то ( y (1),..., y ( ncol( A)) ) будет являться оптимальным (допустимым) решением задачи w, соответствующим решению задачи z.

Замечание. В качестве величины b * выбрана величина, значение которой эквивалентно отсутствию (в данном контексте) верхней пропускной способности дуги.

Схематично концепция t1 | t2 equal | t3 edge сводимости представлена на рис. 5.1.

Согласно определению 5.1, в случае t1 | t 2 equal | t3 cycle сводимости класса W к классу WGraph гарантируется, что если wW, z zMCC (G; lij, uij, eij (i, j ) AG ) WGraph и z является задачей, соответствующей задаче w, то при построении задачи поиска потока минимальной стоимости z пропускные способности в задаче определяются через свободные коэффициенты задачи w, а решение задачи w находится через подмножество компонент циклической декомпозиции решения задачи z. Тогда, согласно утверждениям 2.2 и 2.6, можно предложить алгоритм решения задачи w, основанный на решении соответствующей задачи z и имеющий вычислительную сложность O(t1 t2 t (O(| VG |), O(| VG | | AG |)) + (O(| VG |), O(| VG | | AG |) + O(| VG || AG |)) вычислительных операций, где (n, m) и (n, m) – количество вычислительных операций, требуемых для решения задачи поиска максимального потока zMF и задачи поиска потока минимальной стоимости заданной величины zMCF соответственно в сети с n вершинами и m дугами.

Как было отмечено ранее, обзор оценок вычислительной сложности для известных потоковых алгоритмов можно найти, например, в [149, 151, 172].

Далее в данной главе будут рассмотрены вопросы сводимости класса W (M, H ) к классу WGraph.

5.2. Многоиндексные задачи с декомпозиционной структурой Согласно следующей теореме, выделение подклассов многоиндексных задач, сводимых (в рамках рассматриваемой концепции сводимости) к потоковым задачам, позволяет выделить в NP-трудном классе целочисленных многоиндексных задач полиномиально разрешимые подклассы.

P* | P* equal | P* cycle сводимым к классу WGraph, то класс WZ (M, H ) разрешим за полиномиальное время.

Доказательство. Пусть выполняются условия теоремы. Тогда для каждой задачи можно построить соответствующую ей задачу wW (M, H ) P* | P* equal | P* cycle сводимости количество вершин и дуг, а также значения пропускных способностей в соответствующей потоковой задаче z полиномиально зависят от размера задачи w. При этом, согласно определению 5.1, пропускные способности дуг в задаче z при целочисленных свободных коэффициентах двусторонних ограничений задачи w также являются целочисленными. Для общности отметим, что если w WZ (M, H ) содержит нецелочисленные свободные коэффициенты, то в силу целочисленности коэффициентов матрицы системы ограничений задачи w, задача w при помощи округления параметров может быть преобразована к эквивалентной постановке с целочисленными параметрами.

Как известно, матрица системы ограничений задачи линейного программирования z является абсолютно унимодулярной [51]. Тогда в силу целочисленности пропускных способностей дуг, целочисленное решение задачи может быть найдено за полиномиальное время [102]. Согласно следствию 2.3 и утверждению 2.6, целочисленная декомпозиция целочисленного решения задачи z может быть найдена за полиномиальное время. Тогда, согласно определению 5.1, построенное за полиномиальное время решение задачи w также будет являться целочисленным. Следовательно, найденное решение также будет являться решением задачи wZ. Таким образом, класс задач целочисленного линейного программирования WZ (M, H ) разрешим за полиномиальное время. Теорема доказана.

По аналогии со следствием 4.6 можно доказать следующий результат.

класс W (M, H ) не является P* | P* equal | P* cycle сводимым к классу WGraph, в противном случае P NP.

описываемая при доказательстве теоремы 4.2, обладает следующей особенностью. В случае 2-вложенности множества M задаче wW (M ) ставится в соответствие задача z WGraph. Согласно определению 4.1, оптимальный поток задачи z определяет такое оптимальное решение задачи w, в котором переменным присваивается значение потока вдоль соответствующих дуг, определяемых функцией. При этом в построенной при доказательстве теоремы 4.2 задаче z через каждую из дуг, определяемых функцией, проходит единственный простой цикл. Отсюда справедливо следующее следствие.

L | L equal | L cycle сводимым к классу WGraph, достаточно, чтобы множество M было 2вложенным.

На основании теоремы 5.1 и лемм 4.6, 4.9, 4.10 справедливо следствие.

P* | P* equal | P* cycle сводимым к классу WGraph, необходимо и достаточно, чтобы множество M было 2-вложенным, в противном случае P=NP.

Сформулированные выше следствия 5.2 и 5.3 обуславливают дальнейшие исследования сводимости частных подклассов класса W (M ). Таким образом, основное внимание в данной главе будет уделено вопросам исследования классов многоиндексных задач W (M, H ), которые могут быть сведены согласно концепции, введенной в определении 5.1, к потоковым задачам. Покажем, что таким подклассом является класс многоиндексных транспортных задач со специальной декомпозиционной структурой.

Доказательство. Пусть f1,..., f k – разбиение множества N (s). Тогда | E f i | n j, Доказательство. Пусть f1,..., f k – разбиение множества N (s). По аналогии с доказательством леммы 5.1 обозначим для удобства | E f i | mi 2, i 1, k, тогда | E N ( s ) | mi. Очевидно при k 1 лемма верна. Далее пусть k 2.

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

Доказательство. Пусть f1,..., f k – разбиение множества N (s) и множества M, H выполняется уменьшая общности, будем считать, что противном случае добавим недостающие двусторонние неравенства, в качестве нижней границы которых выберем ноль, в качестве верхней – достаточно большую величину, общности, будем считать, что H { f i | i 1, k} { f i f i1 | i 1, k 1}, в противном случае пусть процедуру построения задачи z zMCC (G; lij, uij, eij, (i, j ) AG ) WGraph, соответствующей задаче w.

– каждому ограничению d ( w, fi, Ff i ) поставим в соответствие дугу (v f, v f ), таким образом, в задаче z нижняя и верхняя границы данной дуги будут составлять a F f и (v(F fi fi1 ) fi, v(F fi fi1 ) fi1 ), таким образом, в задаче z нижняя и верхняя границы данной Определим стоимости дуг в задаче z следующим образом: