Указания методические для самостоятельной работы студентов по курсу «Моделирование сложных систем» МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Нижегородский государственный университет им. Н.И.Лобачевского ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ КАФЕДРА ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ НАУЧНЫХ ИССЛЕДОВАНИЙ Методические указания для самостоятельной работы студентов по курсу «Моделирование сложных систем» при изучении темы «Распределение ресурсов в многоиндексных иерархических системах» (Для студентов специальности «Прикладная информатика» 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 , для которых выполняются ограничения: и принимает максимальное значение критерий , характеризующий суммарную прибыль, которую получит система. 1.3. Задача объемно-календарного планирования Необходимо определить на заданный период планирования программу производства в объемных показателях, удовлетворяющую некоторым заданным характеристикам. Пусть S – множество подразделений предприятия, Q – множество заказов, P – множество изделий, T – множество тактов планирования. Обозначим через – общий объем работ, который должен быть выполнен по всем изделиям всех заказов всеми подразделениями в такт t ; – общий объем работ, который должен быть выполнен за все такты планирования по всем изделиям всех подразделений по заказу j ; – общий объем работ, который должен быть выполнен по всем изделиям всех заказов подразделением i в такт t ; – общий объем работ, который должен быть выполнен за все такты планирования по всем изделиям подразделения i заказа j ; – общий объем работ, который может быть выполнен за все такты планирования подразделением i по заказу j изделию k ; – доход, который получит производственная система за выполнение в планируемом периоде работ по изделию k заказа j , i ÎS , j ÎQ, k ÎP , t ÎT . Тогда задача объёмно-календарного планирования заключается в определении таких величин xijkt – объем работ, который должен быть выполнен в такт t по изделию k заказа j в подразделении i , i ÎS , j ÎQ , k ÎP , t ÎT , для которых выполняются ограничения: и принимает максимальное значение критерий , характеризующий суммарный доход, который получит производственная система в планируемом периоде. Для всех этих задач общим является: - варьируемые параметры математической модели являются многоиндексными, причем число индексов может быть различным, в зависимости от рассматриваемой задачи; - ограничения математической модели представляют собой систему линейных алгебраических неравенств транспортного типа, каждое из которых получается суммированием по некоторым индексам; - критерии оптимизационных задач задаются в виде функций, аргументами которых так же являются суммы значений варьируемых параметров по некоторым индексам. 2. Общая математическая модель многоиндексной иерархической системы Задача распределения ограниченных ресурсов в иерархических системах с учетом общих для этих задач свойств может быть поставлена с использованием формализации, предложенной в [9] при постановке многоиндексных транспортных задач линейного программирования. Пусть . Каждому числу поставим в соответствие параметр , называемый индексом, который может принимать значения из множества , . Пусть , . Набор значений индексов = будем называть t -индексом, а множество всех t -индексов будем обозначать через . Каждому набору поставим в соответствие действительное число , . Совокупность таких чисел для всех возможных значений индексов назовем (как и в [9]) t -индексной матрицей и обозначим через . Пусть . Тогда через F = будем обозначать s -индексный набор . При этом будем считать, что если , то состоит из специально выделенного 0-индекса , причем . Введем следующие обозначения , . Тогда задача распределения однородного ресурса в иерархических системах может быть поставлена следующим образом: для заданного множества M , M Í2N (s ) , найти такую s -индексную матрицу {xF }, которая удовлетворяет системе линейных многоиндексных алгебраических неравенств транспортного типа , (1) с учетом критериев оптимальности, задаваемых векторной функцией , определенной на множестве всех s -индексных матриц со значениями из Rm . Поставленная задача является многокритериальной задачей, вид которой зависит от выбора функций . Когда речь идет о задачах распределения ресурсов с учетом экономических показателей, в качестве функций могут быть выбраны линейные функции, и тогда задачи распределения ресурсов в многоуровневых иерархических системах ставятся как многокритериальные многоиндексные задачи линейного программирования. Применив линейную свертку критериев оптимальности, исходная задача сводится к многоиндексной задаче линейного программирования с ограничениями транспортного типа (1) и критерием: , (2) которую в дальнейшем мы будем обозначать через W (M ). В общем случае для решения таких задач могут быть использованы лишь универсальные методы решения задач линейного программирования. Однако специфика поставленной задачи (линейные ограничения транспортного типа) позволила для частного класса рассматриваемых задач предложить эффективные алгоритмы их решения, отличные от общих (достаточно трудоемких) методов решения. 3. Исследование вопроса сводимости задачи к потоковым моделям Нас будут интересовать такие задачи W (M ), для которых применимы процедуры их сводимости к задаче L – поиска циркуляции минимальной стоимости. Пусть в системе ограничений (1) и – целые числа, , . Определение 1. Будем говорить, что задача W (M ) сводится к задаче L , если некоторое подмножество компонент оптимального решения задачи L образует оптимальное решение задачи W (M ), и задача W (M ) не имеет допустимого решения, если не имеет допустимого решения задача L . Так как система ограничений (1) задачи W (M ) определяется заданием множества M , M Í2N ( s ) , будем решать задачу поиска таких множеств M , при которых задача W (M ) сводится к задаче L . В [2] приведены достаточные условия, которые могут быть использованы для исследования сводимости рассматриваемых задач, однако проверка этих условий связана с исследованием свойств матрицы системы ограничений и является достаточно трудоемкой. В данной работе приводятся достаточные условия сводимости задачи W (M ) к задаче L , основанные на исследовании множества M , мощность которого на порядок меньше количества строк системы ограничений задачи W (M ). Введем следующее вспомогательное определение: Определение 2. Будем говорить, что набор значений индексов включает в себя набор значений индексов , и обозначать это как , если и при . Будем считать, что для любого . Теорема 1. Для того чтобы задача W (M ) сводилась к задаче L достаточно, чтобы существовало такое разбиение , множества M , для которого и . Доказательство. Приведем конструктивное доказательство, основанное на построении сетевой модели. Не уменьшая общности, можно предположить, что если Æ и N (s )ÎM , то и . Если какое-либо из рассматриваемых множеств не включено в M , добавим его, приняв соответствующие величины за нулевые, а за бесконечно большие величины. Для удобства обозначений определим . Будем конструировать сеть, состоящую из: 1. узлов множества , , ; 2. специального замыкающего узла ; 3. дуг, определяемых множеством , с нижней пропускной способностью и верхней пропускной способностью , если , где , , ; 4. дуги, определяемой множеством , с нижней пропускной способностью и верхней пропускной способностью , где; 5. дуг, определяемых множеством , с нижней пропускной способностью и верхней пропускной способностью , если , где , , ; 6. дуг, определяемых множеством , с нижней пропускной способностью и верхней пропускной способностью , где ; 7. замыкающих дуг с нулевой нижней и неограниченной верхней пропускными способностями, если , где , . Дугам вида поставим в соответствие стоимости , где v – произвольный узел сети, , а остальным дугам – нулевые стоимости. Очевидно, что любому допустимому решению задачи W (M ) соответствует допустимая циркуляция построенной сети и, наоборот (здесь каждой переменной задачи W (M ) соответствует дуга (v ,vF ), F ÎEN ( s ) . При этом стоимость допустимой циркуляции и значение целевой функции (2) на соответствующем допустимом решении совпадают. Кроме того, система ограничений (1) совместна в том и только том случае, если в построенной сети существует допустимая циркуляция. Таким образом, предложенная конструкция сводит задачу W (M ) к задаче L . Теорема доказана. Теорема 2. Матрица, соответствующая системе ограничений (1), для которой выполняются условия теоремы 1, абсолютно унимодулярна. Доказательство. Проведем доказательство от противного. Предположим, что для системы ограничений (1) выполняются условия теоремы 1, но матрица, соответствующая этой системе, не абсолютно унимодулярна. Так как условия абсолютной унимодулярности, если и – целые числа, , являются необходимыми и достаточными для целочисленности всех вершин, соответствующих многограннику ограничений системы (1), то можно построить такую линейную целевую функцию, что задача W (M ) будет иметь единственное оптимальное не целочисленное решение. По теореме 1 задача W (M ) сводится к задаче L , а для задачи о циркуляции минимальной стоимости согласно теореме о целочисленности потока, всегда существует оптимальное целочисленное решение (если задача имеет решение). Полученное противоречие доказывает теорему. Теорема доказана. 4. Примеры 4.1. Проверка условий теоремы 1 Рассмотрим структуру множества M для задач приведенных в пункте 2: - транспортной задача с промежуточными пунктами M ={{j ,k },{i ,j },{i },{k },Æ}, разбиение M 1 ={{j ,k },{k },Æ}, M 2 ={{i ,j },{i }}, удовлетворяет условиям теоремы 1 - задача объёмно-календарного планирования M ={{i ,j ,k },{i ,k ,t },{j ,k },{k ,t },{t },Æ}, разбиение M 1 ={{i ,j ,k },{j ,k },Æ}, M 2 ={{i ,k ,t },{k ,t },{t }} удовлетворяет условиям теоремы 1 - задача распределения мощностей каналов передачи данных M ={{j ,k },{i ,k },{i ,j },Æ} и не существует разбиения множества M , удовлетворяющего условиям теоремы 1. Кроме того, для матрицы ограничений этой задачи не выполняются условия абсолютной унимодулярности, тем самым данная задача в случае произвольной матрицы не может быть сведена к задаче L с целочисленными исходными данными. 4.2. Построение сетевой модели Рассмотрим 3-х индексную задачу линейного программирования W (M ) с ограничениями транспортного типа, образованными с использованием индексов i ,j ,k , i ÎI , j ÎJ , k ÎK , при заданном множестве M ={{i ,k },{j ,k },{k },Æ}: и критерием Существующее разбиение M 1 ={{i ,k },{k},Æ}, M 2 ={{j ,k }} множества М удовлетворяет условиям теоремы 1, т.е. исходная задача сводится к задаче поиска циркуляции минимальных стоимостей. Пусть I ={1,2}, J ={1,2}, K ={1,2,3} и задача W (M ) имеет следующий вид: Алгоритм построение сети, соответствующей задаче W (M ), основан на конструктивном доказательстве теоремы 1. Транспортная сеть, соответствующая задаче W (M ) приведена на рисунке 1. С дугами сети связаны сегменты, соответствующие пропускным способностям, и стоимости. Дуги, у которых сегменты не приведены, имеют нулевую нижнюю и неограниченную верхнюю пропускные способности и нулевую стоимость. Символ означает, что в соответствующем данному узлу ограничении происходит суммирование по всем значениям данного индекса. Рис. 1. 5. Заключение При выполнении условий теоремы 1, для многоиндексной задачи линейного программирования W (M ) строится соответствующая транспортная сеть с двусторонними пропускными способностями дуг. Поиск допустимой циркуляции проводится путем построения транспортной сети и решения для нее задачи поиска максимального потока. Алгоритм Голдберга и Рао для задачи о максимальном потоке, отбросив логарифмические сомножители, имеет вычислительную сложность O (m 3/2 ), где m – число дуг транспортной сети (см. [11]). Число вершин в построенной транспортной сети по порядку совпадает с величиной – суммой количества переменных и ограничений в задаче W (M ). При выполнении условий теоремы 1 , а число дуг транспортной сети по порядку совпадает с числом вершин. И тогда вопрос о совместности задачи W (M ) требует арифметических операций. Решение задачи L осуществляется путем нахождения потока минимальной стоимости заданной величины. Алгоритм Орлина решения задачи поиска потока минимальной стоимости, отбросив логарифмические сомножители, имеет вычислительную сложность , где n – число вершин транспортной сети (см. [12]). Отсюда задача W (M ) может быть решена за арифметических операций. Проверка условий выполнения теоремы 1 может быть осуществлена перебором вариантов, так как при выполнении условий теоремы |M |£2s и множество М не может содержать более 2 элементов одинаковой мощности. Из теоремы 2 следует, что если условия теоремы 1 выполняются, то оптимальное решение исходной задачи распределения ресурсов будет целочисленным. Отсюда предложенный метод исследования многоиндексных иерархических систем транспортного типа может быть использован для решения задач распределения недробимых ресурсов. Таким образом, предложенный подход к исследованию многоиндексных задач распределения ресурсов в иерархических системах позволяет для широкого класса практически важных прикладных задач применять хорошо разработанные эффективные потоковые алгоритмы. Приведенные оценки вычислительной сложности показывают, что временные затраты, в случае применения данного подхода, на порядок ниже затрат, связанных с общими методами решения задач линейного программирования. Приведенный список литературы содержит публикации, которые могут быть использованы при изучении рассматриваемой темы. Список литературы 1. Гофман А.Дж., Краскал Дж.Б. Целочисленные граничные точки выпуклых многогранников// В сборнике "Линейные неравенства и смежные вопросы". М.:Изд-во ИЛ, 1959, с. 325-347. 2. Литвак Б.Г., Раппопорт А.М. Задачи линейного программирования, допускающие сетевую постановку// Экономика и мат. методы. 1970. Т. 6, Вып. 4, с.594-604. 3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Москва: Мир, 1985. 4. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах.// Автоматика и телемеханика. 1996. №2, с.24-29. 5. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры// Труды международной конференции "Идентификация систем и задачи управления SICPRO'2000". Москва, 26-28 сентября 2000 г. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2000, с. 2038-2049. 6. Прилуцкий М.Х., Картомин А.Г. "Потоковые алгоритмы распределения ресурсов в иерархических системах". Электронный журнал "Исследовано в России", 39, стр. 444-452, 2003 г. http://zhurnal.ape.relarn.ru/articles/2003/039.pdf 7. Прилуцкий М.Х., Афраймович Л.Г. "Условия совместности многоиндексных систем транспортного типа" Электронный журнал "Исследовано в России", 70, стр. 762-767, 2005 г. http://zhurnal.ape.relarn.ru/articles/2005/070.pdf 8. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами.// Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем, 2004, с 56-63. 9. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.: Радио и связь, 1982. 10. Форд Л., Фалкерсон Д. Потоки в сетях. М.: МИР, 1966. 11. A.V. Goldberg , S. Rao. Beyond the flow decomposition barrier. Journal of the ACM, 45, 1998, pp. 783-797. 12. J. B. Orlin, A faster strongly polynomial minimum cost flow algorithm, Operations Research, 41, 1993, pp. 338-350. Содержание Введение 3 1. Постановки задач распределения ресурсов 4 1.1. Транспортная задача с промежуточными пунктами 4 1.2. Задача распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ 5 1.3. Задача объемно-календарного планирования 6 2. Общая математическая модель многоиндексной иерархической системы 8 3. Исследование вопроса сводимости задачи к потоковым моделям 10 4. Примеры 13 4.1. Проверка условий теоремы 1 13 4.2. Построение сетевой модели 13 5. Заключение 15 Список литературы 17