Условия совместности многоиндексных систем

транспортного типа

Прилуцкий М.Х., Афраймович Л.Г. (afr-fam@sandy.ru )

Нижегородский государственный университет им. Н.И. Лобачевского

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

При решении задач распределения ограниченных ресурсов в иерархических системах возникает проблема проверки на совместность систем ограничений, описывающих множество допустимых решений таких задач (см.[1-3]). Содержательно задачи распределения ресурсов ставятся следующим образом. В иерархической системе распределяются ресурсы между элементами трех типов: источниками ресурсов, передающими элементами и потребителями ресурсов. Элементы системы и связи между ними характеризуются ресурсными ограничениями, определяющими объемы ресурсов, которые могут циркулировать в системе. Задачи распределения ресурсов в иерархических системах заключаются в определении таких допустимых объемов ресурсов, при которых принимают экстремальные значения критерии оптимальности, определяющие эффективность функционирования систем. Для таких задач общим является то, что варьируемые параметры математической модели являются многоиндексными, причем число индексов может быть различным, в зависимости от рассматриваемой задачи. Для исследования вопроса о совместности будем пользоваться формализацией, предложенной в [4].

Пусть N(s) = {1,2,...,s}. Каждому числу l поставим в соответствие параметр j, называемый индексом, который может принимать значения из множества Jt = {1,2,...,щ}, l е N(s). Пусть f = {k1,k2,...,kt}, f <z N(s). Набор значений индексов Ff = (jkjk2,...,jkt) будем называть t-индексом, а множество всех t-индексов будем обозначать черезEf = Jk х Jk2 х... х Jki, t = 1,s . Каждому набору Ff поставим в соответствие действительное число zFf, Ff е Ef. Совокупность таких чисел для всех возможных значений индексов jk2,..., jkt назовем (как и в [4]) t-индексной матрицей и обозначим через {zjk jt jt } = {zFf}. Пусть

f = N (s) \ f. Тогда через F= FfFf будем обозначать s-индексный набор (jvJk2,..,Jkt,A+1,--,Jk,). При этом будем считать, что если f = 0, то Ef состоит из специально выделенного 0-индекса F0, причем F = F0F. Введем следующие

обозначения S zFfF- = S S ••• SzpfFj , Ff е Ej • Тогда система

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

% < S xFfF- < Ьр_, F-f е Ef, f е M,

здесь М - заданное множество, M z 2N(s-1; aF_ , bF_ - заданные параметры, причем

aF_ > 0, Ff е Ef, f еM; {xF} - s-индексная матрица действительных

неотрицательных неизвестных. В дальнейшем данную систему ограничений будем обозначать через D(M).

В общем случае для проверки на совместность системы ограничений D(M) могут быть использованы лишь универсальные методы линейной алгебры ([5]). Однако транспортная специфика линейных ограничений, описывающих множество D(M), позволила для частного класса рассматриваемых систем предложить эффективные алгоритмы проверки на совместность, отличные от общих (достаточно трудоемких) методов.

Нас будут интересовать такие системы ограничений типа D(M), для которых применимы процедуры их сводимости к задаче L - поиска допустимых циркуляций в транспортных сетях [6]. Пусть в системе ограничений D(M) aF_ и bF_

- целые числа, Ff е Ef, f е M . Будем говорить, что система ограничений D(M)

сводится к задаче L, если некоторое подмножество компонент допустимого решения задачи L образует допустимое решение системы ограничений D(M) и система ограничений D(M) не совместна, если не имеет допустимого решения задача L. Так как система ограничений D(M) определяется заданием множества М, M z 2N(s), будем решать задачу поиска таких множеств M, при которых система D(M) сводится к задаче L.

Введем следующие вспомогательные определения: будем говорить, что

набор значений индексов Ff т j^, j^),---, Jkm J включает в себя набор значений индексов Ffd) = ^jk(D, jk2DJk(D J , и обозначать это как Ffт p Ffт , если f(1) z f(2) и Jk(() = Jk(2) при k!(() = k\2). Будем считать, что F0 p Ff, для любого f z N(s).

Теорема. Для того, чтобы система ограничений D(M) сводилась к задаче L достаточно, чтобы существовало такое разбиение M( = {f(((), J2((:i,..., fj(()},

M2 = f((2),f2(2),..., f^f} множества M, для которого f(1) z fi+f1, i = (,m( -( и

j (2) c ji+2), i=cmr-т.

Доказательство. Приведем конструктивное доказательство, основанное на построении сетевой модели. Не уменьшая общности, будем считать, что если 0 и N(s) еM, то f((() =0 и ={(,2,...,s}. Если какое-либо из рассматриваемых

множеств не включено в M, добавим его, приняв соответствующие величины a за нулевые, а bFf за бесконечно большие величины. Будем конструировать сеть, состоящую из:

Ftt е E— \, i = (, m, , j = (,2; 2. специального замыкающего узла ,;

(. узлов множества (,) = j Vpj

3. дуг, определяемых множеством M(, vF_, vF_ с нижней пропускной

fi+i f(1>

способностью aF_ и верхней пропускной способностью bF_, если

Ff(()Ff(()

pгде р~7х) е ^ F~fix) еi = (,m( - (;

4. дуги, определяемой множеством M

f \

F f (()

с нижней пропускной

способностью aF_ и верхней пропускной способностью bF_

f m(f m(

5. дуг, определяемых множеством M2, vF_,vF_ I с нижней пропускной

j<2)

способностью aF_ и верхней пропускной способностью bF_, если

Ff(2)Ff(2)

J i+(JiJiJiJ i+(J i+(

6. дуг, определяемых множеством M

2

f \

Vp—:

f(2)

с нижней пропускной

способностью aF_ и верхней пропускной способностью bF_, где

f(2)Ff(2)

FfI27 е Ef(2) ;

7. замыкающих дуг vF_, vF_ I с нулевой нижней и неограниченной

V Ff((() V7.

верхней пропускными способностями, если F— p F—, где F-^ е Ej^

Ff((2) е Ef((2)

Очевидно, что любому допустимому решению системы ограничений D(M) соответствует допустимая циркуляция построенной сети и наоборот (здесь каждой переменной xF системы ограничений D(M) соответствует дуга вида (v, vF), FеEN(S))• Таким образом, предложенная конструкция сводит систему ограничений D(M) к задаче L — поиска допустимой циркуляции в транспортной сети.

Если для множества М выполняются условия теоремы, то, используя вышеизложенный алгоритм, строится соответствующая транспортная сеть с двусторонними пропускными способностями дуг, поиск допустимой циркуляции в

f