Транспортная задача с промежуточными пунктами

Методические указания

для самостоятельной работы студентов по курсу

                     «Моделирование сложных систем»                         

при изучении темы

«Распределение ресурсов

 в многоиндексных иерархических системах»

(Для студентов специальности

 «Прикладная информатика» 35.14.00)

Нижний новгогд, 2006

УДК 519.874

Методические указания для самостоятельной работы студентов по курсу «Моделирование сложных систем» при изучении темы «Распределение ресурсов в многоиндексных иерархических системах» (Для студентов специальности  «Прикладная информатика» 35.14.00)

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

Составители: д.т.н., проф. М.Х.Прилуцкий,

                      аспирант Л.Г.Афраймович

Рецензент:  к.ф.-м.н., доцент Таланов В.А.

Введение

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

Содержательно эти задачи можно описать следующим образом. Предполагается, что в системе присутствуют элементы трех типов: источники ресурсов, передающие элементы и потребители ресурсов. Элементы системы и связи между ними характеризуются ресурсными ограничения, определяющими объемы ресурсов, которые могут циркулировать в системе. Среди элементов системы выделяются так называемые "контролируемые" элементы, которые определяют условия "эффективного" функционирования системы. Каждый из "контролируемых" элементов определяет на соответствующем ему интервале допустимого распределения ресурсов бинарные отношения, которые задаются с помощью функций предпочтения, определенных для "контролируемых" элементов.

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

Особое место среди задач распределения ресурсов в иерархических системах занимают задачи, формализуемые как многоиндексные задача линейного программирования транспортного типа. К таким задачам, например,  относятся: транспортная задача с промежуточными пунктами, задача распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ и задача объемно-календарного планирования.

Постановки задач распределения ресурсов

Транспортная задача с промежуточными пунктами

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

Пусть I – множество пунктов производства, J – множество промежуточных пунктов, K – множество пунктов потребления. Обозначим через  – максимальный объем производства продукта пунктом i ;  – объём продукта, который необходимо доставить k-ому пункту потребления;  – максимальное количество продукта, которое может быть доставлено из j – ого промежуточного пункта k-ому потребителю;  – максимальный объём продукта, который может быть доставлен из i-ого пункта производства в j-ый промежуточный пункт;  – затраты на доставку единицы продукции из i-ого пункта производства через j-ый промежуточный пункт k-му потребителю, iÎI, jÎJ, kÎK. Тогда рассматриваемая задача заключается в определении таких величин   – количество продукта, которое будет перевезено из пункта производства i через j-ый промежуточный пункт k-му потребителю, для которых выполняются ограничения:

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