Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

331

Δ = { x∈R

⏐ Ax = b, x≥0.} , (15.2)

то блочно-диагональная матрица условий A представима в ви-

де:

….. A

0 ….. 0

A = 0 A

….. … (15.3)

… … ….. …

0 0 ….. A

Матрицы A

, i=1,...,p часто интерпретируются, как матрицы

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

гда подматрицу

║ A

.... A

║ матрицы A интерпретируют, как

матрицу условий использования общих ресурсов, необходимых

для выполнения работ подсистем.

С учетом блочной структуры (15.3) матрицы условий исход-

ную задачу можно представить в виде:

∑

→ max, (15.4)

∑

= b

, (15.5)

= b

, i = 1,..., p, (15.6)

≥ 0. i = 1,..., p. (15.7)

Здесь

- n

- мерный транспонированный вектор коэффициентов це-

левой функции i-ой подсистемы;

- n

- мерный вектор-решение i-ой подсистемы;

- m

×n - мерная матрица глобальных условий (ресурсных

ограничений) i-ой подсистемы;

- m

- мерный вектор глобальных ограничений;

- m

×n

- мерная матрица условий (технологических ограни-

чений) i-ой подсистемы;

- m

- мерный вектор ограничений.

Причем

∑

= n,

∑

= m,

332

где m и n - размерность матрицы A. Отметим, что к представлен-

ному виду можно свести любую задачу линейного программиро-

вания, тогда p = 2.

Ограничения (15.6), (15.7) задают p выпуклых многогранни-

ков Δ

. Пусть x

, j=1,..., s

- решения, соответствующие вершинам

(крайним точкам) i-го выпуклого многогранника; s

- количество

вершин Δ

. Тогда любое допустимое решение i-ой подсистемы x

можно представить в виде:

∑

, (15.8)

где коэффициенты λ

удовлетворяют условию

∑

= 1, λ

ij.

≥0, i=1,…, p, (15.9)

Введем следующее предположение.

Предположение 1. Пусть известно множество X

всех вер-

шин, выпуклых многогранников Δ

, i=1,...,p, задаваемых условия-

ми (15.6), (15.7).

= { x

}, i = 1,..., p, j = 1,..., s

Тогда, подставляя выражения (15.8), вместо x

в исходную опти-

мизационную задачу (15.4)-(15.7), получим

∑

(λ

) → max, (15.10)

∑

(λ

) = b

, (15.11)

∑

(λ

) = b

, i = 1,..., p, (15.12)

ij.

≥0, i=1,..., p, j=1,…, s

, (15.13)

Обозначим

= c

, α

= A

, (15.14)

где ϕ

- значение целевой функции i-ой подсистемы, вычислен-

ное на решении x

; α

- вектор глобальных ресурсов, необходи-

мых для реализации решения x

. Кроме того, в (15.12) будем

иметь в виду, что A

ij =

, i = 1,..., p.

Тогда задачу (15.10)-(15.13) можно переписать в виде

333

∑

→ max, (15.15)

∑

= b

, (15.16)

∑

= 1, i = 1,..., p, (15.17)

ij.

≥0, i=1,..., p, j=1,…, s

, (15.18)

Таким образом, исходная задача (15.4)-(15.7) в условиях

предположения 1 сведена к задаче (15.15)-(15.18) с переменными

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

лико. В то же время, если исходная задача имела (m

+ m

⋅ ⋅ ⋅ + m

) ограничений, то задача (15.15)-(15.18) имеет всего

+p) ограничений. Матрица условий задачи (15.15)-(15.18) име-

ет вид:

,α

,..., α

,α

,..., α

. . . . . .

,α

,..., α

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

1 1 ...… 1 0 0 ...… 0 . . . . . . 0 0 ...… 0

0 0 ...… 0 1 1 ...… 1 . . . . . . 0 0 ...… 0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

0 0 ...… 0 0 0 ...… 0 . . . . . . 1 1 ...… 1

Рис. 15.2.

Согласно методу обратной матрицы (см. 3.5) решение за-

дачи (15.15)- (15.18) оптимально, если выполняется следующее

условие:

= min (π

- ϕ

) ≥ 0, (15.19)

i,j

где

- транспонированный вектор двойственных оценок условий

(15.16), (15.17):

= ║ π

¦ π

¦ ..... ¦ π

║ (15.20)

здесь π

- транспонированный вектор двойственных оценок усло-

вий (15.16); π

- двойственная оценка i-го условия вида (15.17);

334

- обобщенный вектор условий задачи (15.15) - (15.18) с мат-

рицей условий, изображенной на рис.15.2; a

имеет вид:

= ----- (15.21)

где e

- вектор, i-я компонента которого равна 1, а остальные

компоненты равны 0.

Преобразуем условие оптимальности (15.19) с учетом

(15.20), (15.21):

= min (π

- ϕ

) = min (π

- ϕ

) =

ij ij

= min (π

- max (ϕ

- π

)) ≥ 0,

i j

Здесь задача max (ϕ

- π

), j=1,..., s

представляет из себя

самостоятельную оптимизационную задачу i-ой подсистемы. Дей-

ствительно, с учетом (15.14) ее можно представить как

max (ϕ

- π

)) = max ( c

- π

) =

j j (15.22)

max (( c

- π

) x

) = max ((c

- π

) x

) ,

j x

∈Δ

где Δ

определяется ограничениями (15.6), (15.7) и задает много-

гранник допустимых решений i-ой подсистемы.

Сравнивая полученную задачу оптимизации решений в

подсистемах с исходной, можно отметить, что целевая функция

подверглась модификации. Действительно, если исходная целе-

вая функция i-ой подсистемы имела вид (c

), то целевая функ-

ция подсистем в (15.22) имеет вид (c

- π

) x

, т.е. из коэф-

фициентов целевой функции вычитается стоимость общих ресур-

сов, необходимых для реализации решения x

; π

интерпретиру-

ется как стоимость ресурсов в единицах глобального критерия

("механизм цен").

На каждом шаге решения координирующей задачи решает-

ся p оптимизационных задач подсистем, решения которых служат

информационной основой для координирующей задачи следую-

щего шага. В этих условиях "Предположение 1" больше не явля-

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

335

ней точки многогранника в соответствии с (15.22) эквивалентен

решению оптимизационной задачи

max ((c

- π

) x

) .

∈Δ

Такой метод соответствует процедуре "генерации столбца" [59].

Сама же координирующая задача имеет вид (15.15)-(15.18) с той

разницей, что s

соответствует количеству решений, которые i-ая

подсистема сообщила координатору на некотором шаге решения

координирующей задачи.

Отметим, что оптимальное решение x

задачи в целом, как

правило, не является простым объединением решений подсис-

тем. Из (15.8) следует, что окончательное решение подсистемы

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

с коэффициентами λ

, найденными в результате решения ко-

ординирующей задачи,

∑

Тогда оптимальное решение не обязательно соответствует неко-

торой вершине многогранника, описывающего допустимые реше-

ния i-ой подсистемы, но, как правило, соответствует некоторой

внутренней точке Δ

. В этом смысле рассматриваемый алгоритм

декомпозиции не является средством полной децентрализации

процесса принятия решений. Более удачно определение Дж.

Данцига [26], как "централизованное планирование без использо-

вания в центре полной информации".

Рассмотрим алгоритм координационного принятия решения

в иерархической системе.

На некоторой r-ой итерации подсистемы решают оптимиза-

ционные задачи (Δ

), где Δ

описывается ограничениями (15.6),

(15.7); f

= (c

- π

)

. Центр на основе найденных в подсистемах

решений x

и значений целевой функции ϕ

= f

) = c

строит

координирующую задачу, используя при этом матрицы A

oi,

i=1,..

..,p. В результате решения координирующей задачи вычисляются

координирующие сигналы π

= π

, которые сообщаются в

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

динирующего сигнала π

производят модификацию целевой

функции по правилу (c

- π

и находят новые оптимальные

решения x*

, которые сообщаются в Центр. И т.д. Процесс закан-

336

чивается, когда координирующий сигнал, найденный в результате

решения задачи Центра перестает изменяться.

Обмен информацией между подсистемами и Центром мож-

но характеризовать следующей схемой

, x

Рис. 15.3.

Алгоритм Данцига Вулфа.

Алгоритм носит итерационный характер. Каждая итерация

состоит из нескольких шагов. Рассмотрим содержание действий,

производимых на каждом шаге.

0). Задается начальный номер итерации r = 1. Центр сообщает

всем подсистемам одинаковый координирующий сигнал

= 0

, i = 1,...,p.

1). Подсистемы решают оптимизационные задачи вида

- π

) x

→ max

= b

≥ 0.

В результате решения данных задач находятся оптимальные ре-

шения подсистем на r-ой итерации x

. В соответствии с получен-

ными решениями производится вычисление значений ϕ

, ϕ

Значения ϕ

, x

сообщаются в Центр.

2). Строится координирующая задача в виде

∑

→ max, (15.23)

∑

= b

, (15.24)

∑

= 1, i = 1,..., p, (15.25)

ij.

≥0, i=1,..., p, j=1,…, r, (15.26)

Центр

i-я подсистема

337

Здесь вектор a

вычисляется как α

= A

, i=1,...,p, j=1,...,r,

где {x

}, i=1,...,p, j=1,...,r - множество решений, переданных под-

системами в Центр на r итерациях. Данная задача является зада-

чей линейного программирования и может решаться с использо-

ванием симплекс-метода (метод обратной матрицы (см.3.5)).

Если на первом шаге решения этой задачи устанавливает-

ся оптимальность текущего решения (т.е. ни одна из переменных

, i=1,...,p, соответствующих решениям подсистем x

, найден-

ным на r-ой итерации), не вводится в базис, то, следовательно,

координирующий сигнал не будет пересчитываться (останется

без изменений). Это означает, что найдено оптимальное решение

исходной задачи - производится переход на шаг 5.

3). Производится расчет координирующих сигналов. В нулевой

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

шению координирующей задачи (15.23)-(15.26) (см. алгоритм в

3.5),

содержатся компоненты транспонированного вектора двой-

ственных оценок π

. Первые m

компонент вектора π

- коли-

чество глобальных ограничений в (15.5) образуют вектор π

. То-

гда индивидуальный координирующий сигнал i-ой подсистемы

рассчитывается как

= π

Значения координирующих сигналов π

, i=1,...,p сообщаются в

подсистемы.

4). Изменяется номер итерации r = r + 1. Производится пере-

ход на шаг 1.

5). Формируются оптимальные решения подсистем по правилу

∑

Здесь x

, j = 1,...,r решения i-ой подсистемы, которые сообщались

Центру на r итерациях решения задачи; λ

, i = 1,...,p, j = 1,...., r -

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

(15.23)-(15.26).

Замечание 1.

Размерность координирующей задачи (15.23)-(15.26) посто-

янно увеличивается, т.к. на каждой итерации в нее добавляется p

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

ным на данной итерации. Следует отметить, что подсистемы на

некоторой r-ой итерации (r > 1) могут сообщать в Центр решения,

338

которые там уже имеются. В этом случае такие решения можно

не включать в координирующую задачу.

Замечание 2.

На первой итерации подсистемы сообщают в Центр реше-

ния, соответствующие наилучшему значению целевой функции

подсистемы на Δ

(т.к. π

= 0

, i=1,...,p). В этих условиях (при r = 1)

решение координирующей задачи (15.23)-(15.26) довольно часто

не существует, т.к., как правило, не хватает общих ресурсов на

реализацию таких оптимальных решений подсистем. Поэтому для

решения координирующей задачи целесообразно использовать

М-метод решения задач линейного программирования (см. 3.6),

при использовании которого исходная задача (15.23)-(15.26) по-

гружается в более широкую М-

задачу, исходное опорное решение

которой очевидно - это дополнительные переменные, количество

которых равно (m

+ p). Использование дополнительных пере-

менных при этом штрафуется (М - размер штрафа), вследствие

чего дополнительные переменные в процессе решения коорди-

нирующей задачи выводятся из базиса.

15.3. Координационное планирование на основе

перераспределения ресурсов

Аналогично тому, как это рассматривалось в предыдущем

параграфе будем интерпретировать задачу принятия решения в

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

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

дивидуальных решений привлечения некоторых общих для все

подсистем ресурсов. В отличие от декомпозиции Данцига-Вулфа,

где координация действий подсистем достигалась за счет моди

фикации целевой функции, а координирующие сигналы имели

смысл стоимости общих ресурсов, в декомпозиции Корнаи-

Липтака [85] в качестве координирующих сигналов рассматрива-

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

в связи с чем модификации подвергаются ограничения, описы-

вающие потребности подсистемы в общих ресурсах, и, как след-

ствие этого, модифицируется множество допустимых решений

подсистемы.

Перепишем задачу (15.4)-(15.7) в виде:

339

∑

→ max, (15.27)

∑

≤ b

, (15.28)

≤ b

, i = 1,..., p, (15.29)

≥ 0. i = 1,..., p. (15.30)

Обозначим π

= π

),как

= A

. (15.31)

Тогда задачу (15.27)-(15.30) можно представить в виде со-

вокупности оптимизационных задач.

Задача Центра:

f(π) =

∑

(π

) =

∑

(π

) → max, (15.32)

∑

≤ b

. (15.33)

Задача i - ой подсистемы

→ max, (15.34)

≤ p

, (15.35)

: A

≤ b

, (15.36)

≥ 0. (15.37)

Здесь ограничения (15.36), (15.37) описывают технологиче-

ские условия функционирования i - ой подсистемы; (15.35) пред-

ставляют собой ресурсные ограничения. При этом π

- доля гло-

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

- выступает в качестве координирующего сигнала. Так как π

задаче подсистемы (15.34) - (15.37) является подвектором векто-

ра ограничений i-ой подсистемы, то, следовательно, модифика-

ции подвергается множество допустимых альтернатив Δ

= Δ

(π

Задача Центра (15.32), (15.33) заключается в нахождении

оптимального распределения общего ресурса. Решение такой

задачи усложняется тем, что функции x

(π

) (а, следовательно, и

f(π)) заданы алгоритмически. Действительно, для нахождения

значений x

(π

) необходимо решить задачи подсистем (15.34) -

(15.37). Применение той или иной вычислительной схемы при

максимизации (15.32) порождает соответствующий алгоритм, по-

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

340

ма Корнаи-Липтака данная задача сводится к максиминной зада-

че, которая исследуется методами теории игр.

Анализ задачи (15.32), (15.33) показывает целесообраз-

ность передачи ресурсов той подсистеме, которой соответствуют

максимальные значения целевой функции f

(π

) = c

(π

). Вместе

с тем, учитывая связь целевых функций прямой и двойственной

задачи, можно записать

(π

) = c

(π

) = y

(π

) μ

, (15.38)

где

(π

) - транспонированный вектор всех ограничений задачи i-ой

подсистемы;

(π

) = ║ π

¦ b

║

; (15.39)

- решение задачи, двойственной по отношению к задаче

(15.34) - (15.37); соответственно (15.39) решение двойственной

задачи - вектор μ

можно представить в виде

= ║ μ

πi

¦ μ

║

. (15.40)

Здесь значения двойственных переменных μ

πi

соответствуют об-

щим ресурсам π

, которые передаются Центром i-ой подсистеме,

и характеризуют эффективность их использования в единицах

критерия. Тогда (15.38) можно переписать

(π

) = π

πi

+ b

, (15.41)

Целевая функция глобальной задачи (Центра) (15.32) с уче-

том выражений (15.41) имеет вид

∑

(π

) μ

∑

πi

∑

πi

+ С.

Тогда задача Центра:

(μ, π) =

∑

(π

) ≥

∑

πi

→ max, (15.42)

∑

≤ b

. (15.43)

Обобщенно данную задачу можно записать как

(μ, π

) = max (μ, π) (15.44)

π∈Δ