WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

Пусть – каноническая транспортная сеть, в основе которой лежит ориентированный граф G1=(V1,A1), ; s – исток, t – сток, s,tV; aij – пропускная способность дуги (i,j), (i,j)A1. С канонической транспортной сетью T1 будем связывать задачу поиска максимального потока fij, (i,j)A1.

Пусть – транспортная сеть, в основе которой лежит ориентированный граф G2=(V2,A2), ; bij и cij – нижняя и верхняя пропускные способность дуги (i,j), соответственно,, (i,j)A2. С транспортной сетью T2 будем связывать задачу поиска допустимой циркуляции, которая заключается в определении циркуляции gij, (i,j)A2, удовлетворяющей следующей системе ограничений:

(2.13)

(2.14)

В диссертационной работе вводится понятие канонической транспортной сети T1(T2), соответствующей транспортной сети T2.

Теорема 1. Для существования допустимой циркуляции транспортной сети T2 необходимо и достаточно равенство величины максимального потока соответствующей канонической транспортной сети T1(T2) величине.

В работе вводится понятие транспортной сети T2(G), соответствующей одноресурсной иерархической системе, определимой ограничениями (2.1),(2.2),(2.9).

Теорема 2. Для совместности системы (2.1),(2.2),(2.9), необходимо и достаточно существование допустимой циркуляции в транспортной сети T2(G).

Следствие 3. Система линейных неравенств (2.1),(2.2),(2.9) сводится, сохраняя соответствие между переменными, к системе (2.13),(2.14), связанной с транспортной сетью T2(G).

Таким образом, можно предложить метод исследования совместности одноресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, основанный на ее сводимости к сети T2(G), исследование которой связано с поиском максимального потока в сети T1(T2(G)). Для поиска максимального потока можно воспользоваться известными алгоритмами, например, алгоритмом Карзанова3

, вычислительная сложность которого O(|V1|3). При этом количество вершин сети T1(T2(G)) по порядку совпадает с величиной. Вычислительная сложность предлагаемого метода.

В общем случае проблема исследования совместности иерархической системы при дополнительных ограничениях целочисленности переменных NP-полна. Однако при сводимости иерархической системы к транспортной сети, проблема исследования ее совместности полиномиально разрешима, обоснованием чего является следующая теорема:

Теорема 4. Если совместная система линейных неравенств, обозначаемая через, сводится, сохраняя соответствие между переменными, к системе вида (2.13),(2.14), то в случае целочисленности всех компонент вектора, система имеет целочисленное решение.

В разделе 2.2 рассматривается случай многоресурсной иерархической системы. Как и в одноресурсном случае многоресурсную иерархическую систему будем моделировать ориентированным графом G=(V,A), AV2, |V|=n, |A|=m. Обозначим через K, |K|=r,, множество различных типов ресурсов. Пусть X= – 3-х индексная матрица, элемент xijk которой определяет количество ресурсов k, переданных по связи (i,j), (i,j)A, kK. Ограничения на суммарные объемы ресурсов будем задавать с использованием множества U,.

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

, iV, kK,

(2.19)

, (i,j)A, kK,

(2.20)

, (i,j)A,

(2.21)

,,

(2.22)

где [Bik,Cik] – сегмент, соответствующий балансным ограничениям элемента i, связанным с ресурсом k, BikCik, BikCik0, iV, kK; [Dijk,Eijk] – сегмент, соответствующий пропускной способности связи (i,j), связанной с ресурсом k, 0DijkEijk, (i,j)A, kK; [Fij,Gij] – сегмент, соответствующий суммарной пропускной способности связи (i,j), 0FijGij, (i,j)A; – сегмент, соответствующий ограничениям суммарного объема ресурсов, определяемого множеством,,.

Под допустимым вариантом распределения ресурсов будем понимать 3-х индексную матрицу X=, удовлетворяющую условиям (2.19)-(2.22). Через, и будем обозначать множества производителей, передающих элементов и потребителей ресурсов k, соответственно, kK.

Под объемом ресурсов k, соответствующих элементу i, обозначаемым через, будем понимать следующее выражение:если, если, kK. В случае иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, ограничения (2.22) имеют следующий вид:

, iV, kK,

(2.23)

где через [Hik,Iik] обозначается сегмент, связанный с ограничением объема ресурсов k, соответствующих элементу i, 0HikIik, iV, kK.

В частном случае многоресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, при отсутствии суммарных пропускных способностей связей, математическая модель распределения ресурсов имеет вид (2.19),(2.20),(2.23). В работе показано, что система линейных неравенств (2.19),(2.20),(2.23) сводится, сохраняя соответствие между переменными, к системе вида (2.13),(2.14). При этом предлагаемый алгоритм исследования совместности рассматриваемой иерархической системы, основанный на сводимости к транспортной сети, имеет вычислительную сложность O(rn3).

Особый интерес представляют многоресурсные древовидные иерархические системы. Здесь предполагается, что граф G=(V,A) является ориентированным деревом, корень которого соответствует единственному в системе источнику ресурсов, листья – потребителям ресурсов, остальные вершины – передающим элементам.

В работе вводится понятие транспортной сети T2(r), соответствующей многоресурсной древовидной иерархической системе с ограничениями объемов ресурсов, соответствующих элементам системы.

Теорема 5. Система ограничений (2.19)-(2.21),(2.23) в случае древовидной иерархической системы сводится, сохраняя соответствие между переменными, к системе (2.13),(2.14), связанной с транспортной сетью T2(r).

Таким образом можно предложить метод исследования совместности рассматриваемой иерархической системы, основанный на ее сводимости к сети T2(r), исследование которой связано с поиском максимального потока в сети T1(T2(r)). Для поиска максимального потока можно воспользоваться известными алгоритмами, например, алгоритмом Слейтора и Тарьяна4, вычислительная сложность которого. При этом количество вершин и количество дуг сети T1(T2(r)) по порядку совпадают с величиной. Вычислительная сложность предлагаемого метода.

В разделе 2.3 рассматривается случай многоиндексной иерархической системы. Для построения математической модели воспользуемся следующей формализацией. Пусть. Каждому числу поставим в соответствие параметр, называемый индексом,,,. Пусть,. Набор значений индексов = будем называть t-индексом, а множество всех t-индексов будем обозначать через,. Пусть каждому набору поставлено в соответствие действительное число,. Совокупность таких чисел для всех возможных значений индексов назовем t-индексной матрицей и обозначим через. Пусть, тогда через F= будем обозначать s-индексный набор. Введем следующие обозначения:,.

Общая математическая модель распределения ресурсов в многоиндексной иерархической системе имеет следующий вид:

,

(2.31)

где М – заданное множество, ;, – заданные параметры,,, ; {xF} – s-индексная матрица действительных неотрицательных неизвестных. Систему (2.31) будем обозначать через D(M).

Под допустимым вариантом распределения ресурсов будем понимать s-индексную матрицу {xF}, удовлетворяющую системе ограничений D(M).

Теорема 6. Для того, чтобы система ограничений D(M) сводилась, сохраняя соответствие между переменными, к системе вида (2.13),(2.14), достаточно, чтобы существовало такое разбиение, множества M, для которого и.

Доказательство теоремы 6 основано на конструктивном построении транспортной сети T2(M), к исследованию которой сводится система D(M).

При выполнении условий теоремы 6 можно предложить метод исследования совместности многоиндексной иерархической системы, основанный на ее сводимости к сети T2(M), исследование которой связано с поиском максимального потока в сети T1(T2(M)), для чего можно воспользоваться, например, алгоритмом Слейтора и Тарьяна. При этом количество вершин и количество дуг сети T1(T2(M)) по порядку совпадают с величиной. Вычислительная сложность предлагаемого метода.

В третьей главе рассматривается общая многокритериальная задача распределения ресурсов в иерархических системах транспортного типа.

Будем рассматривать задачу распределения ресурсов на примере одноресурсной иерархической системы.

Среди множества элементов системы выделим подмножество контролируемых элементов P, PV, |P|=d. Тогда будем считать, что каждый из контролируемых элементов i задает на соответствующем ему сегменте бинарное отношение, отражающее его предпочтение относительно соответствующего ему объема ресурсов, iP. Зададим бинарное отношение в виде функции предпочтения, определенной на сегменте, iP.

Задача заключается в определении такого допустимого варианта распределения ресурсов, для которого принимают экстремальные значения функции предпочтения контролируемых элементов:

Заметим, что в случае многоресурсной иерархической системы предполагается, что PVK, и функция предпочтения, задается на сегменте, (i,k)P. В случае многоиндексной иерархической системы для заданного множества fP, fPM, предполагается, что, и функция предпочтения задается на сегменте.

В разделе 3.1 рассматривается случай аддитивной схемы компромисса и линейных функций предпочтения. При этом задача распределения ресурсов обозначается через W1 (W1(M) в случае многоиндексной иерархической системы).

При заданном параметре di в качестве функции предпочтения будем рассматривать следующую линейную функцию

Для решения задачи W1 могут быть применены общие методы решения задач линейного программирования. Однако, транспортная специфика задачи W1 позволила для некоторых частных случаев предложить более эффективные алгоритмы, основанные на ее сводимости к потоковым задачам.

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

Будем обозначать через L1 задачу поиска потока заданной величины минимальной стоимости в канонической транспортной сети T1; через L2 – задачу поиска циркуляции минимальной стоимости в транспортной сети T2.

Теорема 7. Задача W1 в случае одноресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, сводится, сохраняя соответствие между переменными, к задаче L2.

Следствие 5. Задача W1 в случае многоресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, при отсутствии суммарных пропускных способностей связей сводится, сохраняя соответствие между переменными, к задаче L2.

Теорема 8. Задача W1 в случае многоресурсной древовидной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, сводится, сохраняя соответствие между переменными, к задаче L2.

Теорема 9. Для того, чтобы задача W1(M) сводилась, сохраняя соответствие между переменными, к задаче L2, достаточно, чтобы существовало такое разбиение множества M на подмножества и, для которого и.

В работе вводится понятие задачи L1(L2), соответствующей задаче L2 и определенной на сети T1(T2).

Теорема 10. Пусть поток f является решением задачи L1(L2), тогда циркуляция g,, (i,j)A2, будет являться решением задачи L2.

Для решения задачи L1(L2) можно воспользоваться известными алгоритмами, например, алгоритмом Галиля и Тардоша5, вычислительная сложность которого. Тогда в случае сводимости задачи W1 к задаче L2, мы получаем эффективные алгоритмы решения задачи W1.

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

Теорема 11. Если задача линейного программирования P сводится, сохраняя соответствие между переменными, к задаче L2, то матрица ограничений задачи P абсолютно унимодулярна.

В разделе 3.2 в качестве схемы компромисса рассматривается лексикографическое упорядочивание, в качестве функций предпочтения – кусочно-постоянные функции. При этом задача распределения ресурсов обозначается через W2.

Введем для каждого из контролируемых элементов i совокупность из p+1 вложенных друг в друга сегментов,. При этом,,, iP. В качестве функции предпочтения рассмотрим кусочно-постоянную функцию, принимающую значение t, если,,,.

Рассмотрим (p+1)-ичный d-мерный куб, на котором определим порядок П. Каждой вершине куба поставим в соответствие систему, содержащую не зависящие от вершины куба ограничения математической модели распределения ресурсов и ограничения, зависящие от вершины следующим образом: для, если, то,. На множестве вершин куба зададим двузначную функцию, принимающую значение 1, если система совместна и 0 в противном случае. В качестве порядка П рассмотрим лексикографическое отношение порядка: П тогда и только тогда, когда для некоторого l, l=, и одновременно для j=.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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