РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ПРИ ПРОЕКТИРОВАНИИ ОБЪЕКТОВ С ИЕРАРХИЧЕСКОЙ СТРУКТУРОЙ И ИНТЕРВАЛЬНЫМИ ЗНАЧЕНИЯМИ ХАРАКТЕРИСТИК

Прилуцкий М.Х. (nlo@mailru.com), Летнянчик А.А.

Нижегородский государственный университет им. Н.И. Лобачевского, Россия, 603600, Нижний Новгород, пр. Гагарина, 23

Проектирование производственных, технических,

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

1. Содержательное описание задачи

Рассматривается задача выбора характеристик проектируемого объекта, структура которого представима в виде многоуровневой иерархической системы. Элементы системы разбиваются на три класса:

- центр , соответствующий обобщенным характеристикам всего объекта;

- основные элементы , соответствующие характеристикам конкретных показателей проектируемого объекта;

- вспомогательные элементы , соответствующие обобщенным показателям характеристик основных элементов, влияющих на эти показатели. Характеристики проектируемого объекта зависят от ресурса, распределяемого в

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

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

Будем рассматривать данную проблему при следующих условиях:

- каждый основной элемент системы непосредственно влияет лишь на один вспомогательный элемент;

- каждый вспомогательный элемент непосредственно влияет лишь на один вспомогательный элемент, находящийся на более высоком уровне иерархии, или непосредственно на центр системы;

- в системе распределяется однородный ресурс, удовлетворяющий условиям аддитивности и пропорциональности;

- значения технических характеристик элементов линейно зависят от объемов распределяемого ресурса.

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

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

Будем моделировать проектируемую систему корневым взвешенным ориентированным деревом G= (V, A) , где V- множество вершин дерева (элементы системы), V = N, А- множество дуг (условия зависимости элементов), AcV .

Обозначим через {{0}, Vk , У,}-совокупность множеств, представляющую собой разбиение множества вершин графа G, где 0 - корень дерева (центр системы), Vk и Vu, соответственно, множества промежуточных вершин (вспомогательные элементы

системы) и листьев дерева (основные элементы системы). Если S(j)= {i (j,i)eA, i е V} - множество вершин графа G непосредственно следующих после вершины j, а R(j)={i (i,j)e A, ie V} - множество вершин графа G непосредственно предшествующих

вершине j, то из-за того, что G - ориентированное корневое дерево, следует, что: R(j) =1, jeV\{0}. R(0)= 0 .

S(j)nS(i)= 0, если , i,je V\ Vu . S(j)nS(i)= 0, если ij , i, jeVu.

Посредством интервалов otj=[Cj, Dj], 0<Cj<Dj <°°, jeV, мы будем задавать отнормированные безразмерные значения характеристик элементов проектируемой системы, а интервалы в j =[Aj, Bj], 0<Aj<Bj <°°, jeV, мы будем связывать с объемами ресурса, распределяемого в системе. Тогда интервалы а0 и в о определяют, соответственно, обобщенные характеристики всего проектируемого объекта и объемы ресурса, распределяемого при проектировании всего объекта; интервалы Oj и в j, jeVk, определяют соответственно, обобщенные показатели характеристик основных элементов, влияющих на эти показатели, и объемы ресурса, распределяемого между этими основными элементами; интервалы ц и в j, je Vu , определяют, соответственно, возможные значения характеристик основных элементов и возможные объемы ресурса, которые могут быть выделены для получения этих характеристик.

Пусть Xj - количество ресурса, которое поставим в соответствие элементу

системы с номером j, jeV. Посредством функций f . (x) определенных на множествах

o j =[Cj, Dj], со значениями из в j =[Aj, Bj], je V, задаются соответствия между количествами выделенного ресурса и полученными характеристиками элементов системы. При этом предполагается, что введенные функции обладают свойствами как аддитивности, так и пропорциональности, т. е. содержательно можно интерпретировать не только значения, которые принимают эти функции, но и суммы значений функций, соответствующих разным элементам системы. Тогда ограничения на допустимые

значения распределяемого ресурса и параметры проектируемого объекта описывается системой двусторонних алгебраических неравенств:

Aj < X X < Bj, j eV, (1)

ieQ( j)

Cj < X ft Ы < , j e V, (2)

ieQ( j)

причем, X xi = Xj, j e V .

ieQ (j)

Здесь ограничения (1) связаны с объемами ресурса, распределяемого в системе, а ограничения (2) с характеристиками элементов проектируемого объекта.

3. Постановка оптимизационной задачи

Среди элементов системы выделим контролируемые K, KcV, \Щ = q0, т.е. те, которые определяют основные характеристики проектируемого объекта. Рассмотрим

кусочно-постоянные функции Xi

Xfj(Xj),s0,s1sp ,

jVvjy,j0,s1sp L определенные на множествах

vje6(i) J

\d,Di], со значениями из множества {0,1,...,/?}, где , v = 0,1,...,p - совокупность вложенных друг в друга интервалов, sv c sv+1, sp = \Ci,Di ],

причемxt Xfj(xjxs0,s1 -sp =t, если Xfj(xj)e st и Xfj(xj)*s*-1 Таким

v jeg (i) J jeQ(i) jeQ(i)

образом введенные функции качественно определяют характеристики проектируемого объекта - чем меньше интервал, которому принадлежит значение характеристики элемента, тем лучше параметры проектируемого объекта. Задача распределения ресурсов при проектировании объектов в этом случае заключается в определении такого допустимого решения системы (1 ), (2), при котором введенные функции принимают экстремальные значения:

X, X fj (Xj), s0, s1sp - min, i e K. (3)

v jeQ (i) у

4. Алгоритмы решения задач оптимизации

4.1. Общий случай

Полученная задача (1 )-(3) является многокритериальной, поэтому для ее решения необходимо выбрать схему компромисса. Как и в [1] рассмотрим (р+1)-ичную q0-мерную решетку. Каждый узел решетки определяется q0-мерным вектором r ,

компоненты которого принимают значения из множества {0,1,...,/?}. Узлу решетки r поставим в соответствие систему алгебраических двусторонних неравенств типа (1 )-(2) следующим образом:

сохраняются все ограничения (1), связанные с ресурсом, распределяемым в системе,

если элемент i не является контролируемым, то ему соответствует ограничение из системы (2),

если элемент i является контролируемым и ri = t, то ему соответствует ограничение

Xf ( xj ) e st

jeQ (i)

Так если узел решетки имеет координаты ri = p, то ему соответствует система (1),(2). Зададим на введенной решетке лексикографическое отношение порядка п :

1 2 1 2 1 2

r пr тогда и только тогда, если ri = ri , i = 1,2,...,s, rs+1 <rs+1. Задача распределения

ресурсов в этом случае будет заключаться в определении такого узла решетки r0, которому соответствует совместная система ограничений типа (1), (2) и для которого

выполняется r °ж r для всех узлов решетки, для которых совместны соответствующие им системы типа (1)-(2). Для решения этой задачи необходимо иметь два алгоритма:

алгоритм поиска узла решетки r0, и алгоритм решения систем двусторонних алгебраических неравенств типа (1 )-(2).

Первый алгоритм основан на организации двоичного поиска по координатам узлов

решетки. Поиск узла решетки r0 состоит из q0 шагов. На каждом шаге определяется

очередная оптимальная компонента вектора r0. На первом шаге среди всех узлов решетки вида (v1,p,p,...,p), ve {0,1,...,p}, находится наименьший по порядку ж узел

(v1°, p, p,..., p), для которого совместна система ограничений типа (1)-(2). На £-том

шаге среди узлов (v ,v!°,...,v° 1,vk,p,...,p) находится наименьший по порядку ж узел

Vv°, vl°,..., v° 1, vk1, p,..., p), для которого совместна система ограничений типа (1)-(2). На

q0 шаге находится искомый узел r0. Используя на каждом шаге двоичный поиск по соответствующей этому шагу координате, алгоритм решения поставленной задачи будет включать в себя порядка q0log2(p +1) проверок совместности системы

ограничений типа (1 )-(2) и построения для найденного оптимального узла решетки оптимального решения задачи, т. е. любого допустимого решения соответствующей системы типа (1 )-(2).

Выбор второго алгоритма в большой степени зависит от вида функций f . (x) .

4.2. Линейный случай

В случае, если f (x) линейная функция, т.е. f (x) = a .x + b . , jeV , то система

1 1 j j

(2) преобразуется в систему линейных алгебраических двусторонних неравенств:

C} < Xax < Dj, где (2)

ieQ (j)

ieQ (j) ieQ( j)

Для решения системы линейных двусторонних неравенств типа (1)-(2), как и в [1], здесь предлагается использовать релаксационный метод ортогональных проекций (метод Агмона-Моцкина).

Пусть X e R и X не является решением системы (1)-(2). Обозначим через

(1) (2) (3) (4)

I , I , I , I - соответственно, множество номеров ограничений, для которых не

выполнены условия A} <X x, , X x, < в}, C j <Xa,x Xa,x, < D}.

ieQ(j) ieQ(j) ieQ(j) ieQ(j)

Пусть

< = min( Aj ieQ)xi eQtjj)xi Bj C) ieQu)aixi jeQj)aixi Dj)

j0 = min(ei/n Q(j) ) QUi ) X a) gfr X a) }

i e Q(j) i e Q(j)

Тогда итерационная процедура метода ортогональных проекций заключается в переходе от вектора X к вектору по следующему правилу:

X = X + tin a, (4)

где a - N мерный вектор:

- с нулевыми компонентами, номера которых не принадлежат множеству Q( j0);

- с единичными компонентами, если номера компонент принадлежат множеству

- с компонентами -1 , если номера компонент принадлежат множеству Q( j0 ), а j0 e I ;

- с компонентами q, если i e Q( j0 ),а j0 e I ;

- с компонентами - q, если i e Q( j0 ),а j0 e I .

Как показано в [1 ], такая итерационная процедура при условиях совместности системы (1)-(2) за конечное число шагов сходится к решению этой системы.

4.3.Случай взаимно-однозначного соответствия между объемами распределяемого ресурса и значениями характеристик элементов проектируемого объекта.

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

т.е. fj (Aj) = Cj, fj (Bj) = Dj и fj (x) = -1 x + J 1 j , j e V. Тогда

A j-B j j A j-B j

система ограничений (2) преобразуется к виду:

C . < X CDi x. < D , j eV , (2 )

j i e Q(j) Ai-Bi j

где, C j = Cj - X AiDi-BiCi, D j = Dj - X AiDi-BiCi.

ieQ(j) Ai-Bi ieQ(j) Ai-Bi

Для решения системы (1)-(2 ) можно как и ранее использовать итерационную схему (4). Однако, специфика полученной задачи (биективное соответствие между распределяемым ресурсом и характеристиками элементов) позволяет в этом случае вместо решения системы (1)-(2 ) решать (как и в [2]) систему

Aj < X x, < Bj, j e V, (1)

ieQ( j)

которая является системой двусторонних линейных алгебраических неравенств транспортного типа.

Рассмотрим величины Aip и Bip , которые определяются с помощью следующих рекуррентных соотношений:

Af = Ai , i evu ,

Bp = Bi, i eVu, (5)

Ap = max(Ai, X Ap), i eV / Vu,

jeq(i)

Bp = min(Bi, X Bp), i eV / Vu.

jeq(i)

Покажем, что для рассматриваемых систем, которые моделируются корневыми взвешенными ориентированными деревьями, ограничения (1 ) совместны тогда и только тогда, когда

Ap < Bp, i e V. (6)

Необходимость этих условий очевидна. Доказательство достаточности проведем конструктивно. Покажем, что при выполнении условий (6), специальным образом построенный N мерный вектор x = (x0,x1xN 1), является допустимым решением

системы (1). Здесь x0 - количество ресурса, которое будет распределено центром

системы; xi - количество ресурса, которое будет распределено )-ому

вспомогательному элементу, i e Vk; xj - количество ресурса, которое получит j-ый

основной элемент, j e Vu .

Так как по условиям (6) A0p < B0p, то найдется такое значение x0 , что x0 e [ A0p, B0p], а тем самым (из-за того, что из рекуррентных соотношений (5) при выполнении условий (6) следует, что [A0pp, B0 ] с [A0, B0 ]) x0 - удовлетворяет соответствующему условию соотношений (1 ).

Компоненты вектора xi, i e Q(0), определяются из следующих соотношений:

Xxt = x0, Ap < xt < Bp, ie Q(0).

e Q(0)

Из рекуррентных соотношений (5) и условий (6) следует, что A < x < B , тем самым x , e Q(0) , удовлетворяют соответствующим условиям ограничений (1 ).

Продолжая находить аналогичным образом значения компонент вектора x = (x0, x1 ,... , xN 1 ) , мы построим требуемое допустимое решение системы (1 ).

Утверждение доказано.

Задача распределения ресурсов в этом случае будет заключаться в проверке k ~ q0log2(p +1) раз выполнение условий (6) и для оптимального узла решетки

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

5.Пример.

Рассмотрим задачу проектирования компьютерной офисной системы. Систему можно представить в следующем виде:

Здесь Элемент 0 определяет обобщенную оценку, соответствующую всей компьютерной системе, Элемент 1- определяет группу технических характеристик системного блока, в которую входят скорость процессора (Элемент 3), объем оперативной памяти (Элемент 4), объем видеопамяти (5), объем жесткого диска (Элемент 6). В группу характеристик мультимедиа и офисных расширений (Элемент 2) входят монитор (Элемент 7), CD-ROM (Элемент 8), принтер (Элемент 9), модем (Элемент 1 0).

Таким образом рассматривается трехуровневая система, которая задается ориентированным деревом G=(V,A), A с V2, где V = {0} U Vk U Vu, Vk = {1,2},

Vu = {3,4,5,6,7,8,9,10}, A = {(0,1),(0,2), (1,3),(1,4),(1,5),(1,6),(2,7),(2,8),(2,9),(2,10)},

Q(0) = {1,2}, = {3,4,5,6}, Q(2) = {7,8,9,10}. Интервальные значения возможных

объемов ресурса, распределяемого в системе, приведены в таблице 1:

Таб.1

А0 = 650 Элемент 0 B0 = 850

При выборе конкретных значений технических характеристик основных элементов проектируемой системы здесь предполагается, что некоторые характеристики могут принимать лишь дискретные значения. Так например, объем видеопамяти (Элемент 4) кратен 16 Мб., поэтому интервал возможных значений характеристик этого элемента преобразуется в дискретное множество, состоящее из 8 элементов со значениями: 16Мб, 32Мб, 48Мб, 64Мб, 80Мб, 96Мб, 112Мб, 128Мб. В этом случае нетрудно построить кусочно-постоянную функцию, отображающую величину распределяемого ресурса в соответствующие дискретные значения технических характеристик.

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

На основании соотношений (5),(6) приведенные границы элементов имеют вид:

Ap = 215, B1p = 516, A2p = 284, B2p = 598, A0p = 800, B0p = 1100, откуда следует

совместность системы 1 .

Пусть в качестве контролируемых элементов выбраны элемент 0 (центр), элемент 2, элемент 3 и элемент 9. Пусть совокупность вложенных интервалов для контролируемых элементов имеет вид:

s° =[830,850], s0=[800,850], s02 =[650,850]; s10=[480,500], s\ =[440,500], =[400,500];

s30=[1 70,1 80], s31 =[1 50,1 80], s32 =[79,1 80]; s90=[200,250], s91 =[1 50,250], s92 =[68,250].

Здесь p=2 и распределение ресурсов моделируется троичной четырехмерной решеткой, каждый узел которой определяется четырехмерным вектором, компоненты которого принимают значения из множества {0,1,2}. Будем предполагать, что самым лексикографически предпочтительным является элемент 0, элемент 1

лексикографически предпочтительнее элемента 3, элемент 3 лексикографически предпочтительнее элемента 9.

На первом шаге работы алгоритма среди всех узлов решетки вида (v1 ,2,2,2) найдем наименьший по введенному порядку узел решетки. Рассмотрим узел решетки (1 ,2,2,2). Соответствующая этому узлу система ограничений (2) отличается от системы (1 ) лишь ограничением с номером (7). Для системы (2) это ограничение будет иметь левую границу A0 = 800 , правую границу B0 =850 . Согласно соотношениям (5) приведенные

границы для элемента 0 соответственно равны A0p = 800 , B0p = 850. Из того, что

A0 < Bp, по условию (6) система ограничений (2) совместна. Аналогично рассмотрим

узел решетки (0,2,2,2). Соответствующая этому узлу система ограничений (3) отличается от системы (1 ) лишь ограничением с номером (7). Для системы (3) это ограничение будет иметь левую границу A0 = 830, правую границу B0 = 850 . Согласно соотношениям (5) приведенные границы для элемента 0 соответственно равны Ap = 830, B0p = 850. Из того, что A0 < Bp, по условию (6) система ограничений (3) совместна.

На втором шаге работы алгоритма среди всех узлов решетки вида (0,v 2,2,2) найдем наименьший по введенному порядку узел решетки. Рассмотрим узел решетки (0,1 ,2,2). Соответствующая этому узлу система ограничений (4) отличается от системы (1 ) ограничением с номером (8). По условию (6) система ограничений в этом случае будет совместной. Рассмотрим узел решетки (0,0,2,2). Согласно соотношениям (5) приведенные границы для элемента 0 соответственно равны, A0p = 880 , B0p = 850,

отсюда следует несовместность соответствующей системы ограничений и тем самым вторая компонента искомого узла решетки принимает значение 1 .

Аналогичный поиск по третьей и четвертой компонентам позволяет найти оптимальное решение задачи x0 = (850,448,402,180,86,86,96,151,22,201,28), соответствующее узлу решетки (0,1 ,0,0). Найденные объемы распределяемого ресурса позволяют реализовать компьютерную офисную систему со следующими техническими характеристиками: скорость процессора (Элемент 3)- 750 Мгц, объем оперативной памяти (Элемент 4)- 80 Мб, объем видеопамяти (5)- 24Мб, объем жесткого диска (Элемент 6)- 1 5МБ, монитор (Элемент 7)- 1 4 дюймов, CD-ROM (Элемент 8)- 28 скоростной, принтер (Элемент 9)- 7 страниц в минуту, модем (Элемент

1 0)-1 7 Кбс.

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

проведено распределение ресурса, а тем самым по разному будут определены характеристики элементов системы и всей системы в целом.

Полученные теоретические результаты положены в основу созданной средствами Visual Basic 6.0 диалоговой программной системы принятия решений в рассматриваемой области.

Работа выполнена при поддержке РФФИ грант 00-01-00384.

СПИСОК ЛИТЕРАТУРЫ

1.Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах Автоматика и телемеханика. 1996. №2. С. 24-29. 2. Прилуцкий М. Х. Распределение однородного ресурса в иерархических системах древовидной структуры. Труды международной конференции Идентификация систем и задачи управления SICPRO 2000 . Москва, 26-28 сентября 2000г. Институт проблем управления им. В.А.Трапезникова РАН. М.: Институт проблем управления им. В.А.Трапезникова РАН, 2000, с.2038-2049.