которой осуществляется путем построения соответствующей транспортной сети и решения для нее задачи поиска максимального потока, например, модифицированным алгоритмом расстановки пометок (см. [7]). Если допустимый поток в сети с двусторонними пропускными способностями существует, то соответствующая система ограничений D(M) совместна. Так как вычислительная сложность модифицированного алгоритма расстановки пометок имеет порядок O(V3), где V - множество узлов транспортной сети, то вопрос о совместности систем ограничений типа D(M) решается за порядка O(V3) арифметических операций.

Пример.

Рассмотрим 3-х индексную системудвусторонних линейных

алгебраических неравенств транспортного типаD(M), образованную с

использованием индексов i, j, k, iel, jeJ, keK,при заданном множестве M={{i,k},{/,k},{k},0}:

aj <ZZ xjk < bj, j e J;

iel keK

C <ZZ Xjk < di , i G 1 ;

jeJ keK

gj <Z xjk < hj, i e1, j e J;

keK

rjk < Xjk < Sjk, i e 1, j e J, k e K •

Существующее разбиение Mi={{i,k},{k},0}, M2={{j,k}} множества М удовлетворяет условиям теоремы, т.е. система ограничений D(M) сводится к задаче поиска допустимой циркуляции в соответствующей (согласно конструктивной схеме доказательства теоремы) транспортной сети.

Пусть I={1,2}, J={1,2}, K={1,2,3} и система D(M) задается ограничениями:

14 <ZZ Xik < 24, 17 <ZZx, 2k < 25;

i=1 k=1i=1 k=1

19<ZZX1 jk <26, 18<ZZx2jk <20;

j=1 k=1j=1 k=1

9<ZXnk < 15, 13 <ZX12k < 18, 9<ZX21k < 13, 10<ZX22k < 14;

k=1k=1k=1k=1

1 < Xm < 5, 0 < < 3, 2 < X113 < 8, 3 < X121 < 9, 4 < X122 < 7, 4 < X123 < 9, 4< X211 <8, 0< X212 < 5, 2< X213 < 7, 6< X221 < 7, 0<X222 < 5, 0< X223 <4. Транспортная сеть, соответствующая системе D(M), представлена на рисунке 1. На рисунке с дугами сети связаны сегменты, соответствующие пропускным способностям. Дуги, у которых сегменты не приведены, имеют нулевую нижнюю и неограниченную верхнюю пропускные способности. Символ X означает, что в соответствующем данному узлу ограничении происходит суммирование по всем значениям данного индекса.

Рис. 1

В таблице 1 приведена допустимая циркуляция, определяемая значениями величин потока на дугах. В данной таблице начала и концы дуг обозначены через u и v, соответственно, а величина потока на дуге (u,v) через G(u,v).

Таблица 1

Существование допустимой циркуляции определяет совместность системы D(M), допустимое решение которой приведено в таблице 2.

___________ Таблица 2

x112 x113 x121 x122 x123 x211 x212 x213 x221 x222 x223

522346603703

Литература

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

2.Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры. Труды международной конференции «Идентификация

систем и задачи управления SICPRO2000». Москва, 26-28 сентября 2000 г. М.: Институт проблем управления им. В. А. Трапезникова РАН, 2000, с. 2038-2049.

3.Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами.// Вестник ВГАВТ. Межвузовская серия "Моделирование и оптимизация сложных систем". Н.Новгород: Издательство ВГАВТ, вып. 1, 2004, с. 56-63.

4.Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. - М.: Радио и связь, 1982, 240 с.

5.Черников С.Н. Линейные неравенства.- М. : Наука, 1968, 488с.

6.Форд Л., Фалкерсон Д. Потоки в сетях. - М.: МИР, 1966, 276с.

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