Библиографическое описание:

Полянский И. С., Фролов М. М., Лукьянченкова Н. Е. Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой [Текст] // Технические науки в России и за рубежом: материалы II Междунар. науч. конф. (г. Москва, ноябрь 2012 г.). — М.: Буки-Веди, 2012. — С. 52-55.



В общем виде, иерархическая система транспортного типа представлена совокупностью элементов разделяемых на три множества: 1. пункты производства; 2. промежуточные пункты; 3. пункты потребления однородного ресурса, функциональная взаимосвязь между которыми представлена в виде древовидной структуры. Задача распределения однородного ограниченного ресурса в иерархической системе транспортного типа заключается в определении оптимального плана перевозок, обеспечивающего эффективное функционирование системы и заключающегося в нахождении оптимальных объемов: 1. производства ресурса -м пунктом производства (, где – общее число пунктов производства однородного непрерывного ресурса в иерархической системе); 2. потребления ресурса -м пунктом потребления (, где – общее число пунктов потребления однородного непрерывного ресурса в иерархической системе), с учетом ограничений на: 1. максимально допустимый объем производства ресурса -м пунктом производства; минимально и максимально допустимые объемы потребления и ресурса -м пунктом потребления; 3. пропускную способность при перевозки ресурса через -е промежуточные пункты (, где – общее число пунктов перевозки однородного непрерывного ресурса в иерархической системе).

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

, (1)

при условии, что

(2)
, ; (3)
, ; (4)
, , (5)

в случае, когда

, (6)

где – объем ресурса, поступающего на вход -го промежуточного пункта.

Согласно [1 – 3], представим иерархическую систему транспортного типа в виде ориентированного связного графа без петель и параллельных рёбер (корневого ориентированного дерева) [4], представленного совокупностью непустого множества вершин и множества ребер двухэлементных подмножеств множества [5]:

, , , , (7)

где , а , N и Mобщее число вершин и ребер графа соответственно. Причем, в рассматриваемой постановке задачи, множество вершин графа представлено совокупностью непересекающихся подмножеств: 1. – пунктов производства (корней ориентированного дерева); 2. – промежуточных пунктов (промежуточных узлов ориентированного дерева); 3. – пунктов потребления (листьев ориентированного дерева), т. е. , с условием и , , , .

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

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

, (8)

с учетом ограничений

; ; , (9)

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

, (10)

где

, , , . (11)

Геометрия решения задачи представлена на рисунке 1.

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

; (12)
. (13)


Рис. 1. Геометрия решения задачи распределения однородного непрерывного ограниченного ресурса в иерархической системе транспортного типа с древовидной структурой.


Для ориентированного графа определим матрицу , являющуюся матрицей достижимости (т. е. если vp вершина достижима из vi, то (i, p)-й элемент матрицы достижимости равен 1, в противном случае – 0, ) для пути кратности r (r задает число ребер, проходя через которые из vi вершины есть путь в vp вершину). Матрица определяется равенством

. (14)

Поскольку является ориентированным связным графом без петель и параллельных рёбер, то, согласно [5], величина r ограничена значением R, определяющим максимально-возможное число ребер, проходя через которые существует путь из i-й вершины в p-ю. Величина R определяется максимально допустимым числом переходов, для которых норма матрицы не равна нулю, т.е. , а .

Введем векторную функцию , i-й элемент () которой определяет вес i-й вершины, т. е., в рассматриваемой постановке задачи, характеризует объем ресурса передаваемого в i-ю вершину графа , определяемую согласно выражения

, (15)

где – векторная функция, i-й элемент () которой определяет величину ресурса производимого i-й вершиной графа ; R-я векторная функция рассчитывается согласно рекуррентной формуле

. (16)

В выражении (16) начальное значение функции и матричная функция , определяются равенствами

;

, (17)

Тогда элементы векторной функции , принадлежащие подмножеству пунктов потребления ресурса множества V вершин графа , определяют i3-е элементы искомой векторной функции минимизируемого выражения (8):

, (18)

где – вектор размерностью , -е элементы которого определяют номера вершин графа составляющих подмножество пунктов потребления ресурса.

Формализованную задачу распределения однородного ограниченного непрерывного ресурса в иерархической системе транспортного типа с древовидной структурой предлагается осуществлять по критерию оптимальности, путем численного решения оптимизационной задачи (8) с учетом ограничений (9), (10) и топологии (12), (13) методами второго порядка (Ньютона, Ньютона–Рафсона, Марквардта и др.) обладающими, согласно [6] и исследованию, проведенному в [7], наилучшей скоростью сходимости.


Литература:

    1. Прилуцкий М. Х. Распределение однородного ресурса в иерархических системах древовидной структуры. Труды международной конференции «Идентификация систем и задачи управления SICPRO 2000». Москва 26-28 сентября 2000. Институт проблем управления им. В. А. Трапезникова РАН. М.: Институт проблем управления им. В. А. Трапезникова РАН, 2000, с. 2038-2049.

    2. Прилуцкий М. Х., Картомин А. Г. Потоковые алгоритмы распределения ресурсов в иерархических системах. Электронный журнал «Исследовано в России», 39, стр. 444-452, 2003.

    3. Афраймович Л. Г., Прилуцкий М. Х., Многоиндексные задачи распределения ресурсов в иерархических системах.//Автоматика и телемеханика, 2006, №6, с.194-205.

    4. Бертсекас Д., Галлагер Р. Сети передачи данных. – М.: Мир, 1989. – 544 с.

    5. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб.: Питер, 2008. – 384 с.: ил.

    6. Полак Э. Численные методы оптимизации. Единый подход. : Пер. с английского Ф. И. Ерешко / Под ред. И.А. Вателя. – М., "Мир", 1974. – 376 с.

    7. Химмельблау Д. Прикладное нелинейное программирование. – М.: изд. «МИР», 1975. – 536 с.



Основные термины (генерируются автоматически): однородного непрерывного, однородного непрерывного ресурса, иерархической системе, распределения однородного, однородного непрерывного ограниченного, непрерывного ограниченного ресурса, ресурса -м пунктом, иерархической системе транспортного, транспортного типа, потребления однородного, системе транспортного типа, вершин графа, потребления однородного непрерывного, однородного ресурса, потребления ресурса, древовидной структурой, распределения однородного непрерывного, пунктов потребления, распределения однородного ограниченного, пунктов потребления ресурса.

Обсуждение

Социальные комментарии Cackle
Задать вопрос