Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой

В общем виде, иерархическая система транспортного типа представлена совокупностью элементов разделяемых на три множества: 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) , в рассматриваемой постановке задачи, i₃-й элемент () которой характеризует величину распределяемого в i₃-й пункт потребления однородного непрерывного ресурса , введем следующие обозначения. Ориентированный граф будем задавать матрицами инциденций для прямого и обратного потоков и соответственно, элементы которых определяются выражениями [5]

; (12)

. (13)

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

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

. (14)

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

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

, (15)

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

. (16)

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

;

, (17)

Тогда элементы векторной функции , принадлежащие подмножеству пунктов потребления ресурса множества V вершин графа , определяют i₃-е элементы искомой векторной функции минимизируемого выражения (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 с.