Распределение ограниченного ресурса

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

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

80

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

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

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

Рассмотрим несколько примеров. Пусть у нас име­ется система, состоящая из k объектов и одного обслу­живающего устройства (рис. 3.10). Обслуживающее ус­тройство периодически с периодом длительности Т через коммутатор подклю­чается к каждому обслу­живаемому объекту и работает с ним в течение

времени t_k . При этом очевидно, что Сумма( t_k )=Т. Дли­тельность периода Т выступает здесь в качестве огра­ниченного ресурса, распределяемого между объекта­ми обслуживания. На каждом объекте в результате обслуживания его в течение времени t_k достигается эффект, равный Фи_k(t_k). Заметим опять, что все эф­фекты соизмеримы, т. е. измерены в одних и тех же

81

 

единицах. При этом могут существовать различные системные критерии качества функционирования.

Предположим, что в качестве объектов выступают следящие устройства с импульсным регулированием через один и тот же регулятор (обслуживающее устройство). Качество функционирования каждого сле­дящего устройства, зависящее при заданном периоде от скважности сигналов регулятора, определяется, например, среднеквадратичным отклонением от от­слеживаемой величины. Поведение системы опреде­ляется среднеквадратичным отклонением наихудшего устройства. В этом случае наилучшее поведение си­стемы получается при достижении min max Фи_k(t_k). Нетрудно понять, что этот критерий удовлетворяется в том случае, когда среднеквадратичные ошибки во всех устройствах одинаковы. Действительно, если при определенном распределении времен обслужива­ния в течение периода в одном из каналов слежения ошибка больше, чем в других, то имеет смысл увели­чить время обслуживания этого следящего устрой­ства путем некоторого увеличения ошибки в других каналах. Здесь мы исключаем из рассмотрения такие экзотические случаи, когда распределение времен об­служивания, обеспечивающее равные ошибки во всех следящих устройствах, вообще недостижимо. Для это­го. достаточно предположить, что ошибки в этих уст­ройствах монотонно уменьшаются при уменьшении скважности регулирования. Оптимальное распределе­ние ресурса в таком случае определяется решением системы уравнений

Фи_k(t_k) - Лямбда = 0, (k=1, k); Сумма (t_k) = T.

В качестве общесистемного критерия может выступать и просто арифметическая сумма эффектов, которые возникают у потребителей ресурса, как, на­пример, было с лесозаготовительными участками в приведенном выше примере (см. § 3.2). В системе, структура которой изображена на рис. 3.10, такой эффект функционирования системы может опреде­ляться суммарным достигаемым эффектом и поведени­ем системы, обеспечивающем приближение к Сумма[Фи_k(t_k)]. В этом случае, как следует из теории нелинейного программирования, оптимальное распределение до­стигается в ситуации,. определяемой решением систе-

82

мы уравнений

 

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

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

При такой организации поведения мы, однако, не можем исключить из рассмотрения еще одного участ­ника — владельца ресурса. О какой же децентрализа­ции может идти речь при наличии центрального объекта, который располагает ресурсом и раздает его потребителям?

Заметим, что мы рассматриваем децентрализацию. поведения при оптимизации и, следовательно, ресур-содержатель не должен решать никаких оптимизаци­онных задач. Более того, мы будем стремиться к то­му, чтобы обмен информацией в системе был доста­точно простым, например, сводился бы к тому, чтобы потребители ресурса посылали в центр заявку на же­лательное количество ресурса, а центр достаточно простым способом на основании полученных заявок делил бы его между потребителями. Наиболее про­стой способ такого распределения—распределение всего ресурса пропорционально поступившим заяв­кам. Тогда, если х_k — количество указанного в заяв­ке k-го потребителя ресурса, то количество выделяе­мого ему ресурса равно

 

Теперь возникает естественный вопрос — существуют ли локальные правила формирования заявок на

83

 

ресурс при описанном способе его распределения, обеспечивающие оптимизацию поведения системы по общесистемному критерию?

Рассмотрим задачу с минимаксным критерием. Допустим вначале, что центральное устройство на­значает величину л и сообщает ее всем потребителям ресурса, а потребители ресурса указывают свои за­явки на ресурс так, чтобы сделать получаемый ло­кальный эффект равным Лямбда. Тогда, если у потребителя эффект меньше Лямбда, он увеличивает заявку, а если больше — уменьшает ее. Если все потребители уменьшают свои заявки, то это означает, что Лямбда мень­ше, чем необходимо, а если увеличивают, то Лямбда боль­ше, чем необходимо. В связи с этим центр ведет себя следующим образом: уменьшает Лямбда, если сумма заявок меньше наличного количества ресурса, и увеличива­ет Лямюда, если наличное количество ресурса меньше сум­мы заявок на него. В ситуации, когда все эффекты равны Лямбда и сумма запрошенного ресурса равна налич­ному его количеству, система находится в устойчивом равновесии. Заметим, однако, что мы нарушили анон­сированный выше принцип — центральное устройство занимается регулированием значения Лямбда. Кроме того, центральное устройство должно сообщать потреби­телям текущее значение Лямбда. С другой стороны, если весь ресурс распределяется пропорционально подан­ным заявкам, то количество выделяемого потребите­лю ресурса несет информацию о соотношении суммы запросов и наличного запаса ресурса. Этой информа­цией можно воспользоваться и находить свои запро­сы на шаге (Тау + 1) следующим образом:          

 

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

Коэффициент Альфа определяет «чувствительность» потребителя, т. е. степень его инерционности. В этом смысле он некоторым образом аналогичен глубине Памяти автоматов в рассмотренных выше моделях поведения. Точность достижения оптимума растет с

84

уменьшением Альфа, но при этом падает способность опе­ративно реагировать на изменение условий функцио­нирования.

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

Демонстрация таких возможностей и была целью настоящего параграфа.

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: