А Н Гвоздинский, В Ю Кудряшов - Анализ методов управления распределения ресурсов в сетевых системах - страница 1

Страницы:
1 

УДК 519.7

А.Н. ГВОЗДИНСКИЙ, В.Ю. КУДРЯШОВ

АНАЛИЗ МЕТОДОВ УПРАВЛЕНИЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЕВЫХ СИСТЕМАХ

Рассматривается сетевая модель транспортного типа. Предлагается многокритериаль­ная модель иерархической структуры, а также методы и алгоритмы для решения исследуе­мых задач.

Введение

Общая проблема распределения альтернативных ресурсов в сетевых канонических структурах заключается в определении ресурсов, которые будут использованы каждой работой, интенсивностей, с которыми работы будут эти ресурсы потреблять, а также сроков начала и окончания выполнения работ, при которых принимают экстремальные значения критерии, определяющие условия эффективного функционирования системы. Кри­терии оптимальности для рассматриваемых систем могут зависеть от организационных и ресурсных условий. Критерии организационных условий связаны с минимизацией наруше­ний заданных директивных сроков, а критерии ресурсных условий - с равномерностью потребления ресурсов.

Актуальность

В рамках теории исследования операций рассматривается большое количество практи­ческих задач, которые можно сформулировать и решить как сетевые модели. Недавние исследования показали, что не менее 70% реальных задач математического программиро­вания можно представить в виде сетевых моделей. Решение задач требует применения различных сетевых оптимизационных алгоритмов. Специфическая структура этих задач позволяет разработать специальные сетевые алгоритмы, более эффективные, чем стан­дартный симплекс-метод.

Состояние проблемы

Наличие быстродействующих ЭВМ и успехи в применении операционных методов решения организационных задач обеспечили непрерывное совершенствование систем цен­трализованного планирования и управления, а также систем информационного обеспечения, функционирующих в масштабе целых корпораций и фирм. При этом, внедряя централизо­ванное планирование, охватывающее все функции организации, фирме нет необходимости отказываться от стратегии децентрализованного принятия оперативных решений. Напро­тив, такой «интегрированный» подход позволяет получать данные, необходимые для обес­печения эффективного управления различными структурными подразделениями фирмы. Интегрированная система планирования дает возможность формировать непротиворечи­вые цели, отражающие как задачи, стоящие перед всей фирмой, так и ограничения, опреде­ляющие текущую деятельность отдельных ее подразделений. Обеспечение практической реализуемости столь крупных по масштабам систем обусловливает необходимость разра­ботки эффективных методов решения операционных задач. Этим методам будет уделять­ся в дальнейшем все большее внимание. Алгоритмы решения задач линейного программи­рования обусловлены их связью с динамическими и многошаговыми моделями детермини­рованного класса. Алгоритмы отыскания кратчайшего пути (маршрута), приведенные в общем виде, можно считать основой для получения решений задач на таких моделях.

В основе построения алгоритмов решения оптимизационных сетевых задач лежат четы­ре понятия. Одним из них является понятие двойственности. Другое понятие свойство треугольной структуры базиса. Третье понятие связано с определением кратчайших путей. Наконец, четвертое понятие относится к максимизации общей величины потока в сети с промежуточными пунктами и ограниченными пропускными способностями, имеющей один источник и один сток.

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

Задачей исследования является изучение существующих методов решения исследуе­мой задачи и их сравнение.

Постановка задачи

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

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

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

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

Сеть (или линейный граф) состоит из множества узлов (или вершин, точек) и множества дуг (или ребер, звеньев), соединяющих различные пары узлов. На каждой дуге задана определенная ориентация (определено направление). Поэтому говорят, что сеть является ориентированной. Для описания ориентированной сети можно воспользоваться простыми обозначениями. Пронумеруем узлы числами натурального ряда 1,2 , . . р и обозначим дугу, исходящую из узла i и входящую в узел j, парой номеров ( i, j). Предположим, что между парой узлов допускается только одна дуга (i , j ) и назовем некоторый объект, перемещающийся из узла i в узел j [т.е. по дуге (i, j)], единичным потоком по этой дуге. Сеть называется двудольной, если все ее узлы можно разбить на два подмножества G1 и G2, такие, что для любой дуги (i, j) узел i принадлежит G1, а узел j — подмножеству G2.

Математическая модель

Для решения задачи распределения ресурсов в сетевых системах используются следу­ющие методы: венгерский и метод Данцига - Вулфа.

Рассмотрим алгоритм решения данной задачи с помощью венгерского метода на примере сети, где числа на дугах определяют стоимость единичной перевозки, вершины 1 и 2 - пункты производства продукта в количестве 20 и 10 единиц, вершины 6 и 7 - пункты потребления в количестве 15 и 15 единиц. К тому же на маршрутах 2 - 5 и 3 - 6 пропускная способность не превышает соответственно 5 и 7 единиц продукта.

Воплощая основную идею венгерского метода, введем фиктивные вход 0 и выход 8. Соединим вход 0 с вершинами 1 и 2 дугами с пропускной способностью, равной объемампроизводства, и вершины 6 и 7 с выходом 8 - дугами с пропускной способностью, равной объемам потребления. Стоимости перевозок на этих дугах берем нулевыми. В полученной сети ищем максимальный поток от входа к выходу:

ЦХ) = Z CijXij, (1)

Z xoj = A, (2) j

Z Xin = A, (3) i

ZXij = ZXik,j *■0,n, (4)

i k

0 < xij < dij для всех i, j , (5) где Vj - неопределенная величина, не превышающая A.Получаем задачу, внешне похожую на классическую транспортную, тем не менее, более сложную из-за ограничений на пропускные способности.

Один из возможных алгоритмов состоит в следующем.

Отмечаем вход некоторым значком (множество отмеченных вершин в дальнейшем будем обозначать через М).

Отыскиваем неотмеченные вершины (j), в которые ведут ненасыщенные дуги с нулевы­ми стоимостями перевозок из вершин множества М, т.е. дуги с характеристиками CMj = 0, XMj <dMj. При отсутствии таковых переходим к пункту 3 алгоритма и при наличии - к пункту 4.

Отыскиваем среди неотмеченных вершину, из которой идет дуга во множество М с нулевой стоимостью и ненулевой перевозкой, и переходим к пункту 4. При отсутствии таких - к пункту 7.

Выбранную вершину включаем во множество М и, если выход остался непомеченным, переходим к пункту 2.

По меткам, сопоставленным отмеченным вершинам (откуда и сколько), отыскиваем путь от входа к выходу и его пропускную способность и корректируем суммарный поток и пропускные способности (по аналогии с поиском максимального потока в простейшем случае).

Если пропускные способности дуг, исходящих из вершины входа, не исчерпаны, перехо­дим к пункту 1.

Выясняем наличие дуг, для которых CMj > 0 при j M или CiM < 0 при i M. Если таковых нет, задача неразрешима.

Среди модулей найденных CMj и CiM отыскиваем минимальное значение 8 и корректи­руем матрицу стоимостей, вычитая 8 из стоимостей на дугах, ведущих из множества М, и добавляя к стоимостям на дугах, ведущих во множество М. Возвращаемся к пункту 2.

Рассмотрим метод Данцига-Вулфа для решения задачи оптимального использования сети.

Имеем конечную неориентированную сеть S = {u,v}, где u - множество узлов, v -множество дуг. Путём на сети S, соединяющим корреспондирующую пару узлов u1, Uk , будем, как обычно, считать последовательность узлов и дуг, начинающуюся с узла u1 и заканчивающуюся узлом Uk . Обозначим через К количество корреспондирующих пар, Sk - множество всевозможных путей, соединяющих k-ю корреспондирующую пару, Qk -количество каналов, потребных k-й корреспондирующей паре, bi - ёмкость i-го элемента сети, bi > 0 . Тогда условия существования на сети S требуемого потока (удовлетворения потребности всех корреспондирующих пар) могут быть записаны в виде

K

ZZaiSkwSk < bb i = (6) k=1skeSk

wSk = Qb   k =(7)

wSk > 0, (8) где wSk - часть заявки для k-й корреспондирующей пары по пути Sk e Sk ,

1% если i - й элемент сети входит в путь Sk ,

aiS   = 1 (9) Sk    [0, если не входит v '

m - количество рёбер в сети S . Не всегда можно сразу сказать, существует ли в заданной

сети требуемый поток. При достаточно малом z > 0 поток, удовлетворяющий ограничени­ям (6), (8) и

ZS WSk = zQb (10) существует всегда, таким образом, возникает задача

maXz при (1), (3), (4). (11)

После необходимых преобразований задача может быть решена методом Данцига-Вулфа.

С помощью значений двойственных переменных в оптимальном решении задачи выде­ляется подмножество корреспондирующих пар, сохраняя оптимальность решения задачи, максимизировать удовлетворение для всех корреспондирующих пар задачи. Не умаляя общности, можем считать, что номера корреспондирующих пар задачи начинаются

с k1 + 1(k1 > 1) и идут подряд до K .

Формально задача может быть записана так:

Z2  max,

WSk = zl'° Qk,   k =(12)

(13)

Z   WSk = Z2Qk,    k = k1,...,K K K

Z  Z  aiSkWSk +   Z     Z  aiSkWSk <bi    , (14)

k=1sk eSk k=k1 +1sk eSk

WSk > 0. (15)

Выводы

При решении задачи оптимального использования сети с применением метода Данцига-Вулфа для генерации столбцов необходимо нахождение кратчайших путей для всех кор­респондирующих пар. Длинами линий при этом служат двойственные оценки. В начальных итерациях большинство длин равны нулю. На основе этого свойства модифицирован клас­сический алгоритм нахождения кратчайших путей Дийкстры, что позволило уменьшить объем вычислений при решении задачи на 15%. Экономия вычислений достигается за счет отсутствия необходимости поиска минимума временных пометок.

Научной новизной приведенных в статье результатов является предложенный метод анализа разветвленности сети, который пригоден для оперативного анализа сетей, содер­жащих тысячи узлов и линий. Алгоритм оптимального применения сети позволяет макси­мально использовать ее ресурсы для одноприоритетного набора потребителей или макси­мизировать прибыль владельца сети от сдачи каналов в аренду. Алгоритмы решения задач оптимального развития сети позволяют минимизировать капиталовложения на ее развитие для достижения допустимости заданного многопродуктового потока, максимизировать прибыль владельца сети при ее развитии с ограниченными капиталами либо в условиях получения кредита с определением его оптимального объема.

Практическим значением рассматриваемых методов является то, что на основании этого исследования можно выбрать оптимальный метод для решения задач распределе­ния ресурсов, что позволит минимизировать капиталовложение и максимизировать доход предприятия.

Список литературы: 1. Вагнер Г.М. Основы исследования операций. 1969. 2. ТахаХ.А. Введение в исследование операций. 2005. 905 с. 3. ЗайченкоЮ.П. Исследование операций. К.: Высш. шк., 1988. 552 с.4. ЛаріоновЮ.І., Левикін В. М., ХажмурадовМ. А. Дослідження операцій в інформаційних системах. Навчальний посібник. Харків: ХНУРЕ, 2003. 388 с. 5. Метод Данцига-Вулфа http://vtit.kuzstu.ru/books/ sheM7/doc/part2.html.

Поступила в редколлегию 28.04.2009

Гвоздинский Анатолий Николаевич, канд. техн. наук, профессор кафедры искусственного интеллекта ХНУРЭ. Научные интересы: оптимизация процедур принятия решений в слож­ных системах управления. Адрес: Украина, 61166, Харьков, ул. ак. Ляпунова, 7, кв. 9, тел.

702-38-23.

Кудряшов Владимир Юрьевич, студент магистратуры специальности интеллектуальные системы принятия решений, факультет КН ХНУРЭ. Адрес: Украина, 61141, Харьков, ул. Целиноградская, 36, кв. 215, тел. 8-050-92-22-059.

Страницы:
1 


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

А Н Гвоздинский, В Ю Кудряшов - Анализ методов управления распределения ресурсов в сетевых системах