Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой | Статья в сборнике международной научной конференции

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

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



В общем виде, иерархическая система транспортного типа представлена совокупностью элементов разделяемых на три множества: 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 с.



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

Похожие статьи

Способы построения гибридных систем управления

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

Задача распределения однородных непрерывных...

Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой. II международная научная конференция «Технические науки в России и за рубежом» (Москва, ноябрь 2012).

Задача распределения однородных непрерывных...

Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой. II международная научная конференция «Технические науки в России и за рубежом» (Москва, ноябрь 2012).

Расчет оптимального плана распределения грузопотоков между...

Тогда система ограничений примет вид: . (1). Система (1) включает в себя уравнения баланса по строкам и по столбцам.

Транспортная задача — задача об оптимальном плане перевозок продукта из пункта наличия в пункт потребления.

Оптимизация сайта с помощью выявления связанных структур

2. Иерархическая кластеризация дает более быстрый алгоритм, однако, не всегда правильный ответ [3,4]. Метод состоит в том, что

2. В графе, полученном в результате стяжки связанной структуры из первого пункта, выбираем вершину, отличную от выбранной ранее, и для нее...

Решение транспортных задач с применением программирования...

Одной из задач линейного программирования является транспортная задача — задача о наиболее экономном плане перевозок однородного продукта из пунктов производства в пункты потребления.

Задача распределения однородных непрерывных...

Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой. II международная научная конференция «Технические науки в России и за рубежом» (Москва, ноябрь 2012).

Организация автомобильных перевозок мелких партий груза на...

Планирование грузопотоков в транспортных системах основывается на определении рационального объема и направлении перевозок.

- определять оптимальные варианты продвижения однородных грузопотоков от источников их генерации до пунктов назначения...

Россия — родина логистики | Статья в сборнике международной...

Начиная с середины 1977 года на базе морского торгового порта Ленинградского транспортного узла функционировала система НПГРТУ — непрерывного

- контактные графики движения и графики технологических процессов обработки транспортных средств в перевалочных пунктах

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Способы построения гибридных систем управления

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

Задача распределения однородных непрерывных...

Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой. II международная научная конференция «Технические науки в России и за рубежом» (Москва, ноябрь 2012).

Задача распределения однородных непрерывных...

Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой. II международная научная конференция «Технические науки в России и за рубежом» (Москва, ноябрь 2012).

Расчет оптимального плана распределения грузопотоков между...

Тогда система ограничений примет вид: . (1). Система (1) включает в себя уравнения баланса по строкам и по столбцам.

Транспортная задача — задача об оптимальном плане перевозок продукта из пункта наличия в пункт потребления.

Оптимизация сайта с помощью выявления связанных структур

2. Иерархическая кластеризация дает более быстрый алгоритм, однако, не всегда правильный ответ [3,4]. Метод состоит в том, что

2. В графе, полученном в результате стяжки связанной структуры из первого пункта, выбираем вершину, отличную от выбранной ранее, и для нее...

Решение транспортных задач с применением программирования...

Одной из задач линейного программирования является транспортная задача — задача о наиболее экономном плане перевозок однородного продукта из пунктов производства в пункты потребления.

Задача распределения однородных непрерывных...

Задача распределения однородных непрерывных ограниченных ресурсов в иерархических системах транспортного типа с древовидной структурой. II международная научная конференция «Технические науки в России и за рубежом» (Москва, ноябрь 2012).

Организация автомобильных перевозок мелких партий груза на...

Планирование грузопотоков в транспортных системах основывается на определении рационального объема и направлении перевозок.

- определять оптимальные варианты продвижения однородных грузопотоков от источников их генерации до пунктов назначения...

Россия — родина логистики | Статья в сборнике международной...

Начиная с середины 1977 года на базе морского торгового порта Ленинградского транспортного узла функционировала система НПГРТУ — непрерывного

- контактные графики движения и графики технологических процессов обработки транспортных средств в перевалочных пунктах

Задать вопрос