Методические указания для самостоятельной работы студентов по курсу «Моделирование сложных систем» (стр. 1 из 4)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Нижегородский государственный университет
им. Н.И.Лобачевского
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
КАФЕДРА ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ НАУЧНЫХ ИССЛЕДОВАНИЙ
Методические указания
для самостоятельной работы студентов по курсу
«Моделирование сложных систем»
при изучении темы
«Распределение ресурсов
в многоиндексных иерархических системах»
(Для студентов специальности
«Прикладная информатика» 35.14.00)
Нижний новгогд, 2006
УДК 519.874
Методические указания для самостоятельной работы студентов по курсу «Моделирование сложных систем» при изучении темы «Распределение ресурсов в многоиндексных иерархических системах» (Для студентов специальности «Прикладная информатика» 35.14.00)
В методических указаниях рассматриваются задачи распределения ресурсов в многоуровневых иерархических системах, которые формализуются как многокритериальные многоиндексные задачи с линейными ограничениями транспортного типа. Приводятся примеры таких задач, строится общая математическая модель, и исследуются вопросы сведения таких задач к задачам поиска циркуляций минимальной стоимости.
Составители: д.т.н., проф. М.Х.Прилуцкий,
аспирант Л.Г.Афраймович
Рецензент: к.ф.-м.н., доцент Таланов В.А.
Широкий класс прикладных задач связан с распределением ограниченных ресурсов в иерархических системах, формализация которых возможна в виде многокритериальных многоиндексных задач с линейными ограничениями транспортного типа.
Содержательно эти задачи можно описать следующим образом. Предполагается, что в системе присутствуют элементы трех типов: источники ресурсов, передающие элементы и потребители ресурсов. Элементы системы и связи между ними характеризуются ресурсными ограничения, определяющими объемы ресурсов, которые могут циркулировать в системе. Среди элементов системы выделяются так называемые "контролируемые" элементы, которые определяют условия "эффективного" функционирования системы. Каждый из "контролируемых" элементов определяет на соответствующем ему интервале допустимого распределения ресурсов бинарные отношения, которые задаются с помощью функций предпочтения, определенных для "контролируемых" элементов.
В общей постановке задача распределения ресурсов в иерархической системе заключается в определении допустимого варианта распределения ресурсов, при котором принимают экстремальные значения функции предпочтения, определенные для контролируемых элементов. Такие задачи формально представимы как многокритериальные (учет контролируемых элементов) задачи с линейными ограничениями и критериями, вид которых зависит от типа функций предпочтения. В случае, когда функционирование системы связано с экономическими показателями, такими как суммарные затраты, суммарный доход или суммарная прибыль, в качестве функций предпочтения выбираются линейные функции. Тогда, считая, что распределение ресурсов в системе удовлетворяет условиям аддитивности и пропорциональности, в качестве схемы компромисса может быть выбрана линейная свертка частных критериев оптимальности, определенных для "контролируемых" элементов.
Особое место среди задач распределения ресурсов в иерархических системах занимают задачи, формализуемые как многоиндексные задача линейного программирования транспортного типа. К таким задачам, например, относятся: транспортная задача с промежуточными пунктами, задача распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ и задача объемно-календарного планирования.
1. Постановки задач распределения ресурсов
1.1. Транспортная задача с промежуточными пунктами
Имеются пункты производства, промежуточные пункты и пункты потребления однородного продукта. Заданы максимально возможные объемы производства продукта каждым пунктом производства, объёмы потребления продукции каждым пунктом потребления, ограничения на объёмы перевозки продукта от каждого пункта производства до каждого промежуточного пункта, ограничения на объёмы перевозки продукта от каждого промежуточного пункта до каждого пункта потребления. При известных затратах на перевозку продукции от пунктов производства через промежуточные пункты к пунктам потребления, необходимо найти план перевозок, обеспечивающий минимальные затраты.
Пусть I – множество пунктов производства, J – множество промежуточных пунктов, K – множество пунктов потребления. Обозначим через
– максимальный объем производства продукта пунктом i; 
– объём продукта, который необходимо доставить k-ому пункту потребления; 
– максимальное количество продукта, которое может быть доставлено из j – ого промежуточного пункта k-ому потребителю; 
– максимальный объём продукта, который может быть доставлен из i-ого пункта производства в j-ый промежуточный пункт; 
– затраты на доставку единицы продукции из i-ого пункта производства через j-ый промежуточный пункт k-му потребителю, iÎI, jÎJ, kÎK. Тогда рассматриваемая задача заключается в определении таких величин 
– количество продукта, которое будет перевезено из пункта производства i через j-ый промежуточный пункт k-му потребителю, для которых выполняются ограничения:  |
 |
 |
 |
 |
и принимает минимальное значение критерий 
, характеризующий суммарные затраты на перевозку продуктов.
1.2. Задача распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ
Необходимо распределять ограниченные мощности каналов передачи данных между различными узлами сети городских провайдеров. Пусть известны потребности абонентов сети в получении того или иного количества информации. Известны возможности провайдеров в предоставлении каналов той или иной мощности между различными узлами связи. С учетом этих возможностей заданы пожелания (предпочтения) абонентов и провайдеров относительно возможности передачи того или иного количества информации тому или иному абоненту или узлу. Определены условия признания эффективности того или иного распределения каналов (относительно их пропускной способности). Структура сети и распределяемой в ней информации в общем случае может быть самой разнообразной. Мы будем рассматривать данную проблему со следующими ограничениями:
- информация распределяется от центра к абонентам через коммутационные узлы по каналам связи;
- каждый узел или абонент сети обслуживается одним или несколькими коммутационными узлами;
- количество распределяемой информации для коммутационных узлов и абонентов может быть ограничено как сверху (принципиальные ограничения возможностей провайдера), так и снизу (минимальная потребность абонентов в получаемой информации).
Нужно распределить пропускную способность каналов максимально эффективно, учитывая как потребности и предпочтения абонентов, так и возможности провайдеров.
Пусть P – множество провайдеров сети, R – множество коммуникационных узлов, U – множество абонентов. Обозначим через
– верхнее и нижнее ограничение суммарной мощности канала передачи данных, которую способен предоставить провайдер i; 
– верхнее и нижнее ограничение суммарной мощности канала передачи данных, которую способен обработать коммуникационный узел j; 
– верхнее и нижнее ограничение суммарной мощности канала передачи данных, которую необходимо предоставить абоненту k; 
– верхнее и нижнее ограничение мощности канала передачи данных, ведущего от провайдера i к абоненту k через коммуникационный узел j; hi – затраты, связанные с предоставлением провайдера i связи единичной мощности; gj – затраты, связанные с обработкой передающей станции j связи единичной мощности; qk – доход, связанный с получением абонента k связи единичной мощности; iÎP, jÎR, kÎU. Тогда, предполагая что распределение мощностей каналов связи удовлетворяет условиям аддитивности и пропорциональности, можно рассматривать задачу максимизации суммарной прибыли, которая заключается в определении таких величин xijk – мощность канала связи предоставляемая абоненту k через коммуникационный узел j провайдером i, iÎP, jÎR, kÎU, для которых выполняются ограничения: