авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н.И. ...»

-- [ Страница 3 ] --

n1,..., ns2 ;

{aF f }, {bF f }, f M 2 ;

{cFN ( s2 ) }) i ni n, (i ) рассмотрим произвольную строку матрицы Matr ( w1 ). Строка row ( w1, f1, F f ) также может быть задана как подматрица row ( w1, f1, F f ) размера 1 | EN (s ) |. Выберем так, что f2 M Matr ( w1 ;

f1, F f ;

FN ( s1 ), FN ( s1 ) E N ( s1 ) ) g} ;

и выберем F f E f, что F f (i ) g и F f (i ) 1, F f ( (i )), i f f1 { (i ) | i f 2 2 2 1 f2 \ g. В строке матрицы рассмотрим элементы, i Matr ( w2 ) row ( w2, f 2, F f ) находящиеся на пересечение со столбцами Fg (1,1,...,1) g, где {col(w2, FN ( s2 ) ) | FN ( s2 ) E g }. Можно увидеть, что матрицы и Fg Matr ( w1 ;

( f1, F f );

FN ( s1 ) E N ( s1 ) ) E g ) размера 1 | E N ( s1 ) | совпадают с точностью до Matr ( w2 ;

( f 2, F f );

Fg (1,1,..., ) g, Fg перестановки столбцов, которая определяется функцией. Отсюда матрица 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}} ;

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

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

H ({1,2}, (1){3} ), ({1,3}, (1){2} ), ({2,3}, (1){1} );

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

Можно увидеть, что H 1 0 1 и det H 2.

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

H ({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) ).

Можно увидеть, что H 1 1 0 0 0 0 0 и det H 2.

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

H ({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) ).

Можно увидеть, что H 1 0 1 0 0 и det H 2. Лемма доказана.

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

Лемма 4.4. Пусть M 2 N ( s ). Для того, чтобы множество M было 1-вложенным, необходимо и достаточно, чтобы для любых f1, f 2 M существовали k,l {1,2}, k l, что f k fl.

Доказательство. Доказательство необходимости. Пусть множество M является 1 вложенным, тогда, согласно 4.2, множество M может быть представлено следующим образом где j 1, m 1. Рассмотрим произвольные M { f1,..., f m }, fj 1, fj {1,2,...,m}. Если j1 j 2, то f j1 f j2, иначе f j 2 f j1.

j1, j Доказательство достаточности. Пусть для любых существуют f1, f 2 M l, что f k f l. Упорядочим элементы множества M по неубыванию их {1,2}, k k,l мощности, M { f t1, f t2,..., f t|M | }, | f t j | | f t j 1 |, j 1, | M | 1. Т.к. f t j f t j 1 и | f t j | | f t j 1 |, то f t j, тогда по условию j 1, | M | 1. Отсюда по определению 4. ft j 1, ft j 1 ft j множество M является 1-вложенным. Лемма доказана.

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

k Доказательство. Доказательство необходимости. Пусть множество M является 2 вложенным, тогда, согласно определению 4.2, существует разбиение множества M на подмножества M 1 { f1( 2),..., f m22) }, что f j(i ) { f1(1),..., f m1 ) }, M (1 ( f j(i1, j 1, mi 1, i ) 1,2.

Рассмотрим произвольные f1, f 2, f 3 M. Существуют k,l {1,2,3}, k lиt {1,2}, что M t. Если | f k | | f l |, то f k f l, иначе f l fk.

fk, fl Доказательство достаточности. Пусть для любых существуют f1, f 2, f 3 M l, что f l. Проведем доказательство конструктивно, построим k,l {1,2,3}, k fk алгоритм нахождения разбиения M 1 { f1( 2),..., f m22) } множества M { f1(1),..., f m1 ) }, M (1 ( такого, что f j(i ) f j(i1, j 1, mi 1, i ) 1,2.

Алгоритм 4.2. Разбиение множества M на два 1-вложенных множества.

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

Шаг 1. Упорядочим элементы множества M по неубыванию их мощности, {g1, g 2,..., g|M | }, | g j | | g j 1 |, j 1, | M | 1. Далее пусть M 1, M 2 :, j : 1. Переход M на шаг 2.

Шаг 2. Упорядочим элементы множеств M 1, M 2 по неубыванию их мощности, { f1( 2),..., f m22) }, где | f l (i ) | | f l (i1) |, l 1, mi 1, i 1,2. Если j | M |, { f1(1),..., f m1 ) }, M (1 ( M то алгоритм завершен;

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

Шаг 3. Если существует l {1,2}, что f mll ) g j, то M l : M l ( {g j }, j : j 1, переход на шаг 2;

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

* Шаг 4. Обозначим I l min i, l 1,2. Рассмотрим g j, i {1,...,ml }}, il { f i (l ) | f i l i| f i ( l ) I l множество I и упорядочим его элементы по неубываню их мощности I1 I 1, если q1 1, если q I1 I {q1, q2,..., q|I | }, | qs | | qs 1 |, s 1, | I | 1. Пусть t I,r.

2, если q1 2, если q I2 I Далее M t : M t {g j }, j : j 1, переход на шаг 2.

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

Рисунок 4.2.

По построению q I. С другой стороны, согласно построенному алгоритму, gj, q | g j | q, q I, отсюда g j q, q I. Рассмотрим произвольные q I 2. Как уже I1, q было показано 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. Далее либо { f1(t ),..., f i*(t )1} и следовательно f i*(t )1 f i*(t ), либо q1. При этом M t \ It Mt \ It t t t I r. Отсюда построенное множество является 1 I Mt \ It Mt Mt : Mt Ir { f1( r ),..., f i*( r 1 } и по построению ) вложенным. Далее либо M r \ I r, либо M r \ I r r f i*( r ) g j. Отсюда построенное множество M r : M r \ I r {g j } является 1-вложенным.

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

Рисунок 4.3.

Следовательно, после завершения работы алгоритма построенные множества 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 |. Тогда fl для любых fk l. Отсюда по теореме 4.3. множество M не является 2-вложенным.

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

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

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

Вход. Множество M 2 N (s).

Шаг 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 алгоритма связан с перебором всех троек M, причем, на данном шаге | M | 2s. Отсюда общее число таких троек не f1, f 2, f превышает 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(s3 ) вычислительных операций.

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

Далее рассмотрим произвольные множества N (s), для которых f1, f 2, f выполняется следующее условие:

(4.5) f 2 f3, f1 f3, f1 f 2.

f1 f2 f Условие (4.5) выполняется тогда и только тогда, когда существуют такие элементы N (s), j {1,2,3} \ {i}, i {1,2,3}, что aij f2, f1, a31 f 3, a31 f1, a12 f1, a12 a 21 f 2, a a13 f1, a13 f3, a23 f 2, a23 f3, a32 f 3, a32 f2.

Множество 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, используя понятие разделяющего множества, можно сформулировать следующее следствие.

Следствие 4.3. Пусть M 2 N ( s ). Для того, чтобы множество M было 2 вложенным, необходимо и достаточно, чтобы A( f1, f 2, f 3 ) для любых f1, f 2, f 3 M.

Пусть A A( f1, f 2, f 3 ), тогда A {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}. Обозначим через p ( A) следующую величину p( A) | {a12} {a13} | | {a21} {a23} | | {a31} {a32} |.

Пусть d * ( f1, f 2, f 3 ) | A |. Тогда рассмотрим задачу выбора среди множеств, min A A( f1, f 2, f 3 ) разделяющих f1, f 2, f 3, множества мощности d * ( f1, f 2, f 3 ) с максимальным значением величины p ( A) :

A* ( f1, f 2, f 3 ) (4.6) p( A).

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

Лемма Пусть и f1, f 2, f 3 N ( s), A( f1, f 2, f 3 ) 4.5.

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

f i, aij Если aij f k, то aij akj, где i, j, k {1,2,3}, i * * * j, i k, j k.

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

a jk akj aik aik, jk По предположению akj f k, при этом по построению akj f j. Отсюда * * aij aij и Далее проведем ast f s, ast f t, t {1,2,3} \ {s}, s {1,2,3} A A( f1, f 2, f 3 ).

доказательство, рассмотрев следующие два возможных случая:

1. Пусть a kj a ki. Т.к. aki aij, то | A | * * * * * a kj, akj aki aij | {aij } {aik } {a ji } {a jk } {a ki } {a kj } | | {aij } {aik } {a ji } {a jk } {a ki } | | {aij } {aik } {a * } {a * } {a ki } | * * * ji jk | {aij } {aik } {a * } {a * } {a ki } {a kj } | | A* ( f1, f 2, f 3 ) |.

* * * * ji jk По построению akj f i и aki f i, таким образом, akj aki. По условию a kj * * * * aki a ki.

aij Отсюда p( A ) | {aij } {aik } | | {a ji } {a jk } | | {aki } {akj } | = | {aij } {aik } | | {a * } {a * } | * * ji jk и p( A* ( f1, f 2, f 3 )) | {aij } {aik } | | {a * } {a * } | | {aki } {akj } | * * * * ji jk | {aij } {aik } | | {a * } {a * } | 1.

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

2. Пусть a kj a ki. По предположению akj aij. По построению akj f k и aik * * * * * * fk, тогда a kj aik. Далее по построению a kj f j, тогда akj a *, a *. Отсюда * * f j, a*, a* * * ji jk ji jk |A | | {aij } {aik } {a ji } {a jk } {a ki } {a kj } | | {aij } {aik } {a ji } {a jk } {a ki } | | {aij } {aik } {a * } {a * } {a ki } | * * * ji jk | A* ( f1, f 2, f 3 ) \ {a kj } | | A* ( f1, f 2, f 3 ) | 1.

* Получаем противоречие. Таким образом, предположение неверно. Лемма доказана.

Лемма 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 ). Рассмотрим множество 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}, являющееся решением задачи (4.6). Схематично будем представлять возможные комбинации множества A* ( f1, f 2, f 3 ) в виде графа G f с множеством вершин и множеством дуг V {ij | j {1,2,3} \ {i}, i {1,2,3}} kl, ij, kl V }. Проведем доказательство, рассмотрев следующее * * {(ij, kl) | aij akl, ij возможные два случая.

1. Пусть для каждого i {1,2,3} существует ti {1,2,3} \ {i}, что ait f ki, где * i {1,2,3} \ {i, ti }. Рассмотрим элементы a1t, a2t, a3t. По построению * * * ki 1 2 * * * f2, f3, f1, f 3, f1, f 2.

a1t1 a 2t 2 a 3t И следовательно a1t1 a1t1, a2t2. Тогда подграфа графа G f, * * * * * * * * * a2t2, a3t3, a2t2 a1t1, a3t3, a3t индуцированный подмножеством вершин {1t1,2t 2,3t3 }, будет иметь вид, представленный на рис. 4.4.

Рисунок 4.4.

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

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

k Следовательно, akl alm, m, k {1,2,3} \ {l}, l {1,2,3}. По построению a * * * * f 3, a13 f3, * * * * отсюда a13. Также по построению a23 f1, отсюда a * * * a12 a23 ;

a13 f1, a f1, отсюда a31 a32. Далее возможен один из двух подслучаев:

* * * * * f1, a a32 a a31 или a * * * * a21 a31.

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

* * Рисунок 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.

* * Рисунок 4.6.

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

Теорема 4.4. Пусть Для того, чтобы класс являлся 2 N (s). W (M ) 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, найдется w W (M ), что Matr (w) не является абсолютно унимодулярной. С другой стороны, из теоремы 4.1 следует, что матрица Matr (w) является абсолютно унимодулярной. Получаем противоречие, таким образом, предположение неверно. Теорема доказана.

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

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

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

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

(4.7) a j3 x j1 j2 j3 a j3, j3 J3, j1 J1 j2 J (4.8) b j1 x j1 j2 j3 b j1, j1 J1, j2 J 2 j3 J (4.9) c j2 j3 x j1 j2 j3 c j2 j3, j2 J 2, j3 J3, j1 J (4.10) J 2, j3 J3, 0, j1 J 1, j x j1 j2 j (4.11) d j1 j2 j3 x j1 j2 j3 min.

j1 J1 j2 J 2 j3 J Задача относится к классу многоиндексных задач W (M ), где (4.7)-(4.11) {{1}, {1,2}, {2,3}} и s 3. Множество M является 2-вложенным, т.к. существует M разбиение M 1 {{1},{1,2}}, M 2 {{2,3}}, удовлетворяющее определению 4.2. Отсюда, согласно теореме 4.2, класс W (M ) является L | L equal | L edge сводимым к классу WGraph. Далее рассмотрим схему сведения, используемой при конструктивном доказательстве теоремы 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( j 2, j3 ){2, 3}, v( j1, j2, j3 ){1, 2, 3} ), который в свою очередь определяется как поток минимальной стоимости данной сети.

Рисунок 4.7.

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

Тогда можно построить алгоритм решения задач класса S (M ), основанный на сводимости к поиску потока в сети по схеме, предложенной при доказательстве теоремы 4.2, и решении соответствующей задачи поиска потока в несовместной сети при помощи алгоритма 2.5. Применим для поиска потока минимальной стоимости заданной величины алгоритм, предложенный в работе Орлина [166], для поиска максимального потока воспользуемся алгоритмом Слейтора-Тарьяна [173]. Данные алгоритмы используются в алгоритме 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 ) |) вычислительных операций.

Рассмотрим задачу U ( M, H ), M, H 2 N ( s ). Для решения задачи U ( M, H ) может быть применен алгоритм 2.8, который, согласно утверждению 2.8, требует O(k log p ) проверок совместности системы ограничений вида (v ). Здесь k | E f | и система fH ~ ограничений вида (v ) относится к классу H ). Также отметим, что | H | 2s, D( M ~ | 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-вложенным, тогда существует алгоритм решения задач класса U (M, H ), требующий 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-вложенным, тогда существует алгоритм решения задач класса U max min (M, H ), требующий O(| EN ( s ) |2 log | EN ( s ) | log p) вычислительных операций.

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

Дополнительно проиллюстрируем полученные результаты при решении ряда прикладных многоиндексных задач, поставленных в главе 1. Транспортная задача с промежуточными пунктами относится к классу W (M ), где (1.1)-(1.5),(1.8) {{i}, {k}, {i, j}, { j, k}}. При этом s 3 и | EN ( s ) | | I || J || K |. Заметим, что множество M M является 2-вложенным, т.к. существует разбиение M 1 {{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 ). Заметим, что множество ~ H {{i},{k},{i, j},{ j, k}} M, как уже было показано, является 2-вложенным. Таким M образом, согласно утверждениям 4.5, 4.6, задачи U ( M, H ) и U max min (M, H ) могут быть решены, используя и O(| I |3| J |3| K |3 log(| I || J || K |) log p) 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-вложенным, т.к. существует разбиение M 1 {, { 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 |)) вычислительных операций. Рассматривается также задача формирования портфеля заказов с возможными нарушениями сроков выполнения работ (1.10)-(1.12),(1.14),(1.18), относящаяся к классу W (M ), где {{ j},{i, t},{ j, t}}.

M Множество M является 2-вложенным, отсюда, согласно утверждению 4.1, задача формирования портфеля заказов с возможными нарушениями сроков выполнения работ может быть решена, используя вычислительных O(| I |2 | J |2 | T |2 log 2 (| I || J || T |)) операций.

4.3. Многоиндексные задачи с 1-вложенной структурой Далее будем рассматривать вопросы нахождения условий, которым должно удовлетворять множество M, чтобы класс W (M ) являлся t1 | t 2 equal| t3 edge сводимым к классу 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 |2 ) ( O(| VG |) ) вычислительных операций.

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

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

Следствие 4.4. Пусть 2 N ( s ). Для того, чтобы класс являлся W (M ) M L | L equal | L edge сводимым к классу WTree, достаточно, чтобы множество M было 1 вложенным.

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

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

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

Шаг 1. Используя конструктивную схему, применяемую при доказательстве теоремы 4.2 (необходимо положить M 1 ), построить задачу z WTree, M, M соответствующую 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 ) |2 ) ( O(| EN (s ) |) ) вычислительных операций.

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

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

Вход. Множество M 2 N (s).

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

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

Шаг 2. Упорядочим элементы множества M по неубыванию их мощности, { f1,..., f| M |}, | f j | | f j 1 |, j 1, | M | 1. Переход на шаг 2.

M Шаг 3. Если выполняется условие j 1, | M | 1, то множество M fj fj 1, является 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, выполнялось f j или f i. Пусть i j, тогда по построению | fi | | f j |.

fi fj Следовательно, f i. Таким образом, для того, чтобы множество M было 1 fj вложенным, необходимо и достаточно, чтобы для любых i, j {1,...,| M |}, i j, выполнялось f i f j. Тогда по свойству транзитивности данный критерий может быть записан в следующей эквивалентной постановке. Для того, чтобы множество M было 1 вложенным, необходимо и достаточно, чтобы f j f j 1, j 1, | M | 1. Данное условие проверяется на шаге 3 алгоритма. Следовательно, алгоритм 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-вложенности является необходимым и достаточным условием сводимости многоиндексной транспортной задачи к задаче поиска циркуляции минимальной стоимости в древовидной сети.

Рассмотрим задачу A ) WTree. Пусть G (V, A ), тогда, zMCC (G ;

lij, uij, eij (i, j ) согласно определению класса WTree, существует корневое ориентированное дерево (V, A) с корнем s V и множеством листьев T V, что A T}.

G A {(t, s) | t Обозначим через t (i ) путь из корня s к листу i в дереве G, таким образом, t (i) (v0,..., vk ), где k – длина пути t (i ), v0 i, (v j, v j 1 ) A, j 0, k 1, i T.

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

T}.

T (G ) {t (i ) | i Пусть 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, тогда будем обозначать e1 e2, если существуют t (v0,..., vk ) T (G) и что 1}, j2, j1, j2 {0,...,k j (v j1, v j1 1 ) e1, (v j2, v j2 1 ) e2 ;

в противном случае, будем обозначать e1 e2.

Лемма 4.7. Пусть z A ) WTree и существуют такие дуги zMCC (G ;

lij, uij, eij, (i, j ) A, что e1, e2, e3, e4, e le1 0, ue1 1, le4 4, ue4 4, le2 0, ue2 2, le5 5, ue5 5, le3 0, ue3 3, le 0, ue {0, d}, e A \ {e1, e2, e3, e4, e5}, где d uei. Тогда либо задача z несовместна, любо существует допустимое решение i A, задачи z такое, что {1,2,3} {xe | e A }.

xe, e Доказательство. Пусть для задачи z zMCC (G ;

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

Не уменьшая общности, будем считать, что e1, e2, e3, e4, e5 и le A A 0, ue d, e A \ A ;

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

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

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

Далее пусть условие (4.12) выполняется. Отсюда выполняется одно из следующих двух условий – e5 e4 ;

(4.13) – t или e5 t для любого пути t T (G ). (4.14) e Отдельно рассмотрим два случая: (4.13) и (4.14).

1. Пусть e5 e4. Тогда найдется путь t1 T (G ), что e5 t1, e4 t1 и min ue 1, e t иначе задача z несовместна. Далее обозначим T1 {t | t T (G), e4 t, e5 t}. Тогда и T (4.15) min ue 4, et t T иначе задача z несовместна. Схематично данный случай приведен на рис. 4.8.

Рисунок 4.8.

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

a. существует t2 T1, что min ue 4, e t b. min ue 4, t T1.

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

Шаг 1. xe : 0, e A;

Шаг 2. xe : xe 1, e t1 ;

Шаг 3. xe : xe 4, e t2 ;

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

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

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

Шаг 1. xe : 0, e A;

Шаг 2. xe : xe 1, e t1 ;

Шаг 3. xe : xe 1, e t 2 ;

Шаг 4. xe : xe 3, e t3 ;

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

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

2. Пусть или для любого пути T (G ). Далее обозначим e5 t t e4 t {t | t T (G), e5 t}, тогда T1,T2 и t}, T T1 {t | t T (G ), e (4.16) min ue 4, min ue 5, et et t T1 t T иначе задача z несовместна. Схематично данный случай приведен на рис. 4.9.

Рисунок 4.9.

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

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

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

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

et e t 4, t T1, и min ue 5, t T2.

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

Шаг 1. xe : 0, e A;

Шаг 2. xe : xe 4, e t1 ;

Шаг 3. xe : xe 5, e t 2 ;

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

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

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

Шаг 1. xe : 0, e A;

Шаг 2. xe : xe 4, e t1 ;

Шаг 3. xe : xe 2, e t2 ;

Шаг 4. xe : xe 3, e t3 ;

Шаг 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. Из условий леммы и et e t условия (4.16) следует, что существуют t2, t3 T2, что min ue {1,2}, min ue 3. Тогда e t2 e t построим допустимый поток xe, e A, в задаче z по следующему алгоритму:

Шаг 1. xe : 0, e A;

Шаг 2. xe : xe 5, e t1 ;

Шаг 3. xe : xe 1, e t 2 ;

Шаг 4. xe : xe 3, e t3 ;

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

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

2.d. Пусть min ue 4, t T1, и min ue 5, t T2. Тогда из условий леммы следует et et 6, что противоречит условию (4.16).

min ue min ue u1 u2 u et et t T1 t T Получаем, что задача 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.

Доказательство. Пусть выполняются условия леммы. Если M, то и лемма доказана. Далее пусть M. Рассмотрим задачу M {} M { }). Т.к. { }, то найдется задача M M w w( A, b, b, c ) W (M w w( A, b, b, c) W (M ), что col ( A) col ( A ), row ( A) col ( A ) row ( A ) ;

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

задача w содержит все ограничения задачи w, тогда, не уменьшая общности, можно считать, что Aij Aij, bi bi, bi bi, i 1, row( A), j 1, col( A) ;

c.

c При этом, не уменьшая общности, будем считать, что Arow ( A) 1, i 1, col( A ), i,i Arow ( A) 0, j 1, col( A ) \ {i}, i 1, col( A ).

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

Т.к. W (M ) является t1 | t2 equal| t3 edge сводимым к классу WTree, то, согласно определению существует задача z zMCC (G;

lij, uij, eij, (i, j ) AG ) WTree, 4.1, соответствующая задаче w. И при этом существует пара функций,, удовлетворяющих условиям определения 4.1. Далее опишем схему построения задачи AG ) WTree, соответствующей задаче w.

z zMCC (G ;

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

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

: {1,2,..., col( A )} (i), если (i ) { ( j ) | j 1, col ( A)} – (i), i 1, row( A) ;

(u, p j ), если существует j {1,...,col ( A)}, что (i) ( j) (u, v) – (row( A) i) ( pi, v), где (i) (u, v), i 1, col( A ) ;

– (i) (u, pi ), где (i) (u, v), i 1, col( A ).

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

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

z Следовательно класс { }) является t1 | t2 equal| t3 edge сводимым к классу W (M WTree. Лемма доказана.

Теорема 4.5. Пусть 2N (s). Для того, чтобы класс являлся W (M ) M t1 | t2 equal| t3 edge сводимым к классу WTree, необходимо, чтобы множество M было 1 вложенным.

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

Т.к. множество M не является 1-вложенным, то, согласно лемме 4.4, найдутся такие M, что f f. Тогда существуют k, k k такие, что f,f N ( s), k f,f f,k f, k f,k f.

k Рассмотрим s -индексные наборы FN (s ), FN (s ), FN (s ), где 2, FN ( s ) (i) 1, i N ( s ) \ {k }, FN ( s ) (k ) 2, FN ( s ) (i) 1, i N ( s) \ {k }, FN ( s ) (k ) FN ( s ) (i) 1, i N (s ).

Далее рассмотрим многоиндексные наборы Ff и F f, где Ff (i) 1, i f, F f (i ) 1, i f.

Пусть w W (M ) и рассмотрим следующую подматрицу H матрицы Matr (w) (т.е.

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

Matr (w;

H ( f, Ff ), ( f, Ff ), (, FN ( s ) ), (, FN ( s ) ), (, FN ( s ) );

FN ( s ), FN ( s ) FN ( s ) ).

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

1 0 0.

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

W (M (4.17) 4 xFf Ff 4;

0 xF f F f d, Ff E f \ {F f } ;

Ff Ef Ff Ef (4.18) 5;

0 d, Ff E f \ {Ff } ;

5 xF f xF f Ff Ff Ff Ef Ff Ef (4.19) 1;

0 2;

0 3;

0 xFN ( s ) xF N ( s ) x FN ( s ) 0, FN ( s ) EN ( s ) \ {FN ( s ), FN ( s ), FN ( s ) } ;

0 xF N ( s ) (4.20) d, Ff Ef, f M \ { f1, f 2, } ;

0 xF f F f Ff Ef где d 1 2 3 4 5 15. Тогда система (4.17)–(4.20) эквивалентна следующей системе линейных неравенств 4 x FN ( s ) 5 0 H x FN ( s ) 1, 0 x FN ( s ) 0 0, FN ( s ) EN ( s ) \ {FN ( s ), FN ( s ), FN ( s ) }.

xFN ( s ) Отсюда задача w имеет единственное решение 1, xFN ( s ) 2, xFN ( s ) 3, x FN ( s ) 0, FN ( s ) EN ( s ) \ {FN ( s ), FN ( s ), FN ( s ) }.

xFN ( s ) По предположению класс W (M ) является t1 | t2 equal| t3 edge сводимым к классу WTree. Тогда, согласно лемме 4.8, класс также является W (M { }) сводимым к классу Рассмотрим задачу t1 | t2 equal| t3 edge WTree.

AG ) WTree, соответствующую описанной выше задаче w.

z zMCC (G;

lij, uij, eij, (i, j ) Согласно определению 4.1, задача z удовлетворяет условию леммы 4.7. По лемме 4.7, задача z либо несовместна, либо имеет допустимое решение xij, (i, j) AG, такое, что {1,2,3} {xij | (i, j ) AG }. Задача w совместна и имеет единственное решение xF, N (s) EN ( s ), при этом {1,2,3} {xF EN ( s ) }. Однако, согласно определению 4.1, FN ( s ) | FN ( s ) N (s) должно выполняться условие AG }. Получаем {xFN ( s ) | FN ( s ) EN ( s ) } {xij | (i, j ) противоречие. Таким образом, предположение неверно. Теорема доказана.

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

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

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

Далее проиллюстрируем применимость метода исследования 1-вложенных многоиндексных задач 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 ) |) справедливы следующие утверждения.

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

~ Утверждение 4.11. Пусть 2 N ( s ) и множество M является 1 M, H H вложенным, тогда существует алгоритм решения задач класса U max min (M, H ), требующий O(| EN ( s ) | log p) вычислительных операций.

Дополнительно проиллюстрируем полученные результаты при решении прикладной многоиндексной задачи, поставленной в главе 1. Рассмотрим проблему формирования допустимого портфеля заказов (1.10)-(1.14). В случае несовместности системы ограничений ставится задача идентификации причин (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 Z | t3 Z целочисленности), представляющую собой обобщение рассмотренной ранее схемы t1 | t2 equal| t3 edge сводимости. Для данной схемы сведения будут обобщены результаты сводимости, полученные ранее для 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 | t3 сводимым к классу W, и выполняются следующие условия. Пусть w w( A, b, b, c) W, AG ) W является задачей, соответствующей задаче w. Далее z zMCC (G;

lij, uij, eij, (i, j ) пусть xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z, а xi, i 1, col( A) является соответствующим ему оптимальным (допустимым) решением задачи w. Тогда:

– если b, b Z row( A), то lij, uij Z, (i, j) AG, – если xij AG, то xi Z, (i, j) Z, i 1, col( A).

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

Рисунок 4.10.

Несложно увидеть, что исследуемая ранее схема t1 | t2 equal| t3 edge сводимости является частным случаем более общей схемы сводимости.

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

2 N ( s ). Для того, чтобы класс W (M ) Следствие 4.5. Пусть являлся M L | L Z | L Z сводимым к классу WGraph достаточно, чтобы множество M было 2 вложенным.

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

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

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

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

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

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

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

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

Лемма 4.9. Пусть s1 2 N ( s2 ) и M 1 M 2 тогда, если класс 2 N ( s1 ), M s 2, M WZ ( M 1 ) является NP-трудным, то класс WZ ( M 2 ) также является NP-трудным.

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

По определению 4.4 существует подмножество g N ( s 2 ), | g | s1 и биективная {{ (i) | i функция N ( s1 ), что Обозначим M1 f }}.

:g f M2 (g) M 1. Далее рассмотрим произвольную P( f1 ) { f 2 | f1 { (i ) | i f2 g}, f 2 M 2}, f задачу w1 WZ ( M 1 ), w1 M 1 ;

{cFN ( s1 ) }) и построим задачу wZ ( s1 ;

n1, n2,...,ns1 ;

{aFf },{bFf }, f M 2 ;

{cFN ( s2 ) }), удовлетворяющую w2 wZ ( s2 ;

n1, n2,...,ns2 ;

{aFf },{bFf }, f W (M 2 ), w следующим условиям:

–,i g, ni n (i ) – ni 2, i N ( s2 ) \ g, – bF f, где F f aFf a F f, bF f F f ( (i )), i f2 g,, ( Ff ) f ( Ff ) f (1,..., ) f 1 (i ) g 2\g g 2 1 2 2 2 2 2 2 E f, f2 P ( f1 ), f E f, Ff M1, Ff 2 2 1 b*, где – или aFf 0, bF Ef, f2 M2 \ ( P( f )), (Ff ) f (1,..., ) f Ff 2 \g 2\g f f M 2 2 f2 \ g E f, f2 P( f ),, Ff f M 2 – cFN ( s1 ), где FN ( s2 ) FN ( ss1 ) ( (i)), i g, Fg Fg (1,...,1) g, Fg (i) Eg, FN ( s1 ) EN ( s1 ), cFN ( s2 ) – c* 1, FN ( s2 ) EN ( s2 ) \ {Fg (1,...,1) g | Fg Eg }, cFN ( s2 ) | cFN ( s1 ) |, b* здесь c* b* bF f.

FN ( s1 ) EN ( s1 ) f M1 F f E f Несложно увидеть, что по построению выполняются следующие условия:

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

b. пусть xF E N ( s2 ) – решение задачи w2, и F xFN ( s ), тогда * c, FN ( s2 ) FN ( s2 ) N ( s2 ) FN ( s2 ) EN ( s2 ) b.1. если F c *, то задача w1 несовместна;

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

xFN ( s2 ), где FN ( s2 ) FN ( ss1 ) ( (i )), i g, FN ( s1 ) Fg (1,...,1) g, Fg (i) EN ( s1 ).

xFN ( s1 ) s Количество переменных в задаче w1 равно n ni, по построению количество i s2 s переменных в задаче w2 равно n O(n ). Пусть A 2 s2 s ni ni Matr ( w1 ), i1 i Matr ( w2 ). Тогда число ограничений в задачах w1 и w2 равны nrow ( Matr ( w1 )) и A nrow ( Matr ( w2 )) соответственно. При этом s1 s s Csj1 ) 2s nrow(Matr(w1 )) | Ef | | Ef | ( ni )( ni O(n ), f 2 N ( s1 ) f M1 j i1 i s2 s s s2 s 2 s j nrow(Matr(w2 )) | Ef | | Ef | ( ni )( C) 22 ni O(n ).

s f 2 N ( s2 ) f M2 j i1 i Таким образом, O(n 2 ), nrow ( A) ncol ( A) O(n ) O(n 2 ).

nrow ( A ) ncol ( A ) O(n ) Также отметим, что параметры b*,c* вычислимы за полиномиальное время от размера задачи w1. Отсюда выполненное сведение класса WZ ( M 1 ) к классу WZ ( M 2 ) реализуемо за полиномиальное время. Тогда из NP-трудности класса WZ ( M 1 ) следует NP-трудность класса WZ ( M 2 ) [50]. Лемма доказана.

Лемма 4.10. Пусть 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}}, то класс WZ (M ) является NP-трудным.

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

(4.21) n n yijk 1, k 1, n, i1 j (4.22) n n yijk 1, j 1, n, i1k (4.23) n n yijk 1, i 1, n, j1k (4.24) yijk {0,1}, i, j, k 1, n, (4.25) n n n eijk yijk min, i1 j1k где eijk 0, i, j, k 1, n. Далее рассмотрим ограничение (4.26) yijk Z, i, j, k 1, n.

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

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

(4.27) n yijk 1, j, k 1, n, i (4.28) n yijk 1, i, k 1, n, j (4.29) n yijk 1, i, j 1, n.

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

Пусть Проведем доказательство путем 3. 4, {{1,2},{2,3},{1,4}}.

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

Задаче поставим в соответствие задачу (4.27)-(4.29),(4.24),(4.25) M ;

{cFN ( s ) }) WZ ( M ) такую, что w wZ ( s;

M ;

n, n, n, n;

{a Ff }, {bFf }, f aFf bFf 1, F f Ef, f M, ei2i3i4, если i1 i ci1i2i3i4, i1, i2, i3, i4 1, n,, иначе n n n где eijk. Тогда задача w представляет собой задачу целочисленного i1 j1k линейного программирования (4.30)-(4.34).

(4.30) n n xi1i2i3i4 1, i3, i4 1, n, i1 1 i2 (4.31) n n xi1i2i3i4 1, i1, i4 1, n, i2 1 i3 (4.32) n n xi1i2i3i4 1, i2, i3 1, n, i1 1 i4 (4.33) xi1i2i3i4 Z, i1, i2, i3, i4 1, n, (4.34) n n n n ci1i2i3i4 xi1i2i3i4 min.

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

Далее пусть {xF } – оптимальное решение задачи w. Покажем, от противного, * N (s) что выполняются следующие условия (4.35) 0, если i xi*i2i3i4 i2, i1, i2, i3, i4 1, n.

Предположим, что условие (4.35) не выполняется, т.е. существуют i1, i2, i3, i4 {1,..., n}, i2, что xi*i i i 1. Отсюда i1 n n n n ci1i2i3i4 xi*i2i3i4.

i1 1 i2 1 i3 1 i4 Рассмотрим матрицу значений переменных {xF }, определенную следующим образом N (s) 1, если i1 n 1 или i i3 i4 1, i3 i4 i3 i4 n 1, i3 i4 n xi1i1i3i4, i1, i3, i4 1, n, 0, иначе 0, i1 i2, i1, i2, i3, i4 1, n.


xi1i2i3i Покажем, что построенная матрица {xF } является допустимым решением задачи w. С N (s) учетом i3, i4 {1,..., n} выполняется: если n 1, то 1 i3 i4 1 n ;

если i3 i n 1, то Для удобства i3 i4 1 n 2 n 1 i3 i4 n 1 n n n 1 n 1.

i3 i4 1, если i3 i4 n обозначим Как показано выше, (i3, i4 ), i3, i4 1, n.

i3 i4 n 1, иначе (i3, i4 ) {1,..., n}, i3, i4 1, n. Отсюда n n n xi1i2i3i4 xi1i1i3i4 x 1, i3, i4 1, n.

( i3,i4 ) ( i3,i4 ) i3i i1 1 i2 1 i1 Таким образом, удовлетворяет Обозначим (4.30).

{xFN ( s ) } i1, i4 1, n. Пусть i1, i4 {1,..., n}. Покажем от {1,..., n}}, (i1, i4 ) {i3 | i1 (i3, i4 ), i противного, что | (i1, i4 ) | 1. Предположим что найдутся i3, i3 (i1, i4 ), i3 i3, тогда если i3, i3 n i4 1 или i3, i3 n i4 1, то по построению (i3, i4 ) ;

если (i3, i4 ) то с учетом выполняется i3 n i4 1 i3, i3 i3 n 1 (i3, i4 ) i3 i4 1, и (i3, i4 ), получаем (i3, i4 ) i3 i4 n 1 i3 n 1 i4 n 1 (i3, i4 ) 1 (i3, i4 ) противоречие, предположение неверно и следовательно | (i1, i4 ) | 1. Рассмотрим множество { (i3, i4 ) | i3 1, n} {i3 i4 1 | 1 i3 n i4 1, i3 N} {i3 i4 n 1 | n i4 1 i3 n, i3 N} {i4,..., n} {1,...,i4 1} {1,..., n}.

Тогда, и следовательно | (i1, i4 ) | 1. Отсюда (i1, i4 ) n n n xi1i2i3i4 xi1i1i3i4 x 1, i1, i4 1, n.

i1i1i3i i2 1 i3 1 i3 1 i3 ( i1,i4 ) Таким образом, удовлетворяет Обозначим (4.31).

{xFN ( s ) } (i3, i4 ), i4 {1,..., n}}, по аналогично можно показать, что | (i1, i3 ) | 1, (i1, i3 ) {i4 | i i1, i3 1, n. Отсюда n n n 1, i2, i3 1, n.

xi1i2i3i4 xi2i2i3i4 x i2 i2 i3i i1 1 i4 1 i4 1 i4 ( i2,i3 ) Таким образом, {xF } удовлетворяет (4.32). Следовательно, {xF } является допустимым N (s) N (s) решением задачи w. При этом n n n n n n n n ci1i2i3i4 xi*i2i3i4.

ci1i2i3i4 xi1i2i3i4 i1 1 i2 1 i3 1 i4 1 i1 1 i2 1 i3 1 i4 Получаем противоречие, предположение неверно и условие (4.35) выполняется.

Далее обозначим yijk xiijk, i, j, k 1, n. В силу условия (4.35) и ограничений (4.30) * * набор i, j, k 1, n, является допустимым решением задачи * (4.33) yijk, (4.27) (4.29),(4.24),(4.25) и по построению n n n n n n n ci1i2i3i4 xi*i2i3i4 * eijk yijk.

i1 1 i2 1 i3 1 i4 1 i1 j1k Далее покажем от противного, что 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), что n n n n n n * eijk yijk eijk yijk.

i1 j1k1 i1 j1k Тогда опередим {xF } следующим образом N (s) xi1i1i3i4 yi1i3i4, i1, i3, i4 1, n, 0, i1 i2, i1, i2, i3, i4 1, n.

xi1i2i3i Несложно увидеть, что в силу условий (4.27)-(4.29),(4.24) построенная многоиндексная матрица {xF } является допустимым решением задачи w, и при этом N (s) n n n n n n n n n n n n n n * ci1i2i3i4 xi*i2i3i4.

ci1i2i3i4 xi1i2i3i4 eijk yijk eijk yijk i1 1 i2 1 i3 1 i4 1 i1 j1k1 i1 j1k1 i1 1 i2 1 i3 1 i4 Получаем противоречие, предположение неверно и i, j, k 1, n, является * yijk, оптимальным решением задачи (4.27)-(4.29),(4.24),(4.25).

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

Теорема 4.7. Пусть 2 N (s). Для того, чтобы класс являлся W (M ) M 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-вложенным, тогда существует алгоритм решения задач класса W (M ) и систем класса D (M ), требующий и O(| E N ( s ) |2 log 2 | E N ( s ) |) O(| EN ( s ) |2 log | EN ( s ) |) вычислительных операций соответственно, данный алгоритм применим при исследовании целочисленного случая;

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

~ – пусть множество M является 2-вложенным, тогда существуют алгоритмы H решения задач класса 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) вычислительных операций соответственно.

При исследовании 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-вложеннм, тогда существует алгоритм решения задач класса W (M ) и систем класса D (M ), требующий и O(| E N ( s ) |2 O(| EN (s ) |) вычислительных операций соответственно, данный алгоритм также применим при исследовании целочисленного случая;

~ – пусть множество M является 1-вложенным, тогда существуют алгоритмы H решения задач класса U ( M, H ) и задач класса U max min (M, H ), требующие 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 сводимости. Установлено, что для того, чтобы класс W (M ) являлся сводимым к классу WGraph, P* | P* Z | P* Z необходимо и достаточно, чтобы множество 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 | t2 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, C (G), что : {1,...,ncol ( A)} – b*, (u, v) bi, i 1, nrow( A) ;

l(u,v ) AG \ { (i) | i 1, nrow ( A)}, l bi, u 0, u(u,v ) (i ) (i ) nrow ( A ) где b* bk ;

k – если циркуляция xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z и yC, C C (G ), является циклической декомпозицией данной циркуляции, то ( y ) будет являться оптимальным (допустимым) решением задачи w,,..., y (1) ( ncol ( A)) соответствующим решению задачи z.

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

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

Рисунок 5.1.

Согласно определению 5.1, в случае t1 | t 2 equal| t3 cycle сводимости класса W к классу WGraph гарантируется, что если w W, z AG ) WGraph и z zMCC (G;

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

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

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

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

2N ( s ).

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

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

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

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

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

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

Следствие 5.2. Пусть 2 N ( s ). Для того, чтобы класс являлся W (M ) M L | L equal | L cycle сводимым к классу WGraph, достаточно, чтобы множество M было 2 вложенным.

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

Следствие 5.3. Пусть 2 N ( s ). Для того, чтобы класс являлся W (M ) M P* | P* equal| P* cycle сводимым к классу WGraph, необходимо и достаточно, чтобы множество M было 2-вложенным, в противном случае P=NP.

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

2 N ( s ) и f1,..., f k – разбиение множества N (s). Будем Определение 5.2. Пусть M говорить, что множество является если f1,..., f k -декомпозиционным, M f i 1 | i 1, k 1}.

M { f i | i 1, k} { f i k Лемма 5.1. Пусть f1,..., f k – разбиение множества N (s), тогда | E fi | | E N ( s ) |.

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

i k mk Несложно увидеть, что. Далее, k1 i k max mi i 1,k k mk k k mk. Лемма доказана.

i mi k max mi max mi max mi i 1,k i 1,k i1 i i 1,k Лемма Пусть – разбиение множества N (s), тогда f1,..., f k 5.2.

k | E fi || E fi 1 | | E N ( s ) |.

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

i k mk Несложно увидеть, что. Далее k2 i k max mi mi i 1,k k mk k k mk. Лемма доказана.

i mi mi (k 1) max mi mi max mi mi 1 1 max mi mi i 1,k 1 i 1,k i1 i i 1,k Теорема 5.2. Пусть M, H 2N ( 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 являются Рассмотрим произвольную задачу f1,..., f k -декомпозиционными.

M ;

{cFN ( s ) }) W ( M, H ). Согласно определению w w( s;

M ;

n1,...,n2 ;

{aFf }, {bFf }, f 5. выполняется M { f i | i 1, k} { f i f i 1 | i 1, k 1}, H { f i | i 1, k} { f i f i 1 | i 1, k 1}.

Тогда заданы | H | многоиндексных матриц коэффициентов {d Ff }, H, что f Не уменьшая общности, будем считать, что d ( FN ( s ) ) f.

cFN ( s ) fH f i 1 | i 1, k 1}, в противном случае добавим недостающие M { f i | i 1, k} { f i двусторонние неравенства, в качестве нижней границы которых выберем ноль, в качестве верхней – достаточно большую величину, например bF, где f – произвольный f Ff Ef элемент из Также, не уменьшая общности, будем считать, что M.

f i 1 | i 1, k 1}, в противном случае пусть Ff Ef, 0, H { f i | i 1, k} { f i d Ff f i 1 | i 1, k 1}) \ H. Далее приведем процедуру построения задачи f ({ f i | i 1, k} { f i zMCC (G;

lij, uij, eij, (i, j ) AG ) WGraph, соответствующей задаче w.

z Построим ориентированный граф с множеством вершин G E fi, i 1, k} {s, t} и множеством дуг AG A3, где VG {vFf, vFf | F fi A1 A i i – A1 {(vFf, vFf ) | F fi E fi, i 1, k} ;

i i – A2 {(vFf, vFf ) | F fi E fi, F fi 1 E fi 1, i 1, k 1} ;

i i – A3 {( s, vFf1 ) | F f1 E f1 } {(vFf k, t ) | F fk E fk } {(t, s)}.

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

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

– каждому ограничению поставим в соответствие дугу d ( w, f i fi 1, Ff i ) fi ), таким образом, в задаче z нижняя и верхняя границы данной (v( F fi, v( F fi ) fi ) fi fi 1 fi 1 дуги будут составлять aF и bF соответственно, Ff i E fi, i 1, k 1.

fi fi 1 fi fi 1 fi fi Определим стоимости дуг в задаче z следующим образом:



Pages:     | 1 | 2 || 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.