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

341

Значения μ

πi

в (15.42) находятся в результате решения в

подсистемах задач, двойственных по отношению к задаче (15.34)

- (15.37). Такие задачи имеют вид

║ π

¦ b

║ μ

→ min, (15.45)

: ║ A

¦ A

║ μ

≥ с

, (15.46)

≥ 0. (15.47)

Обобщенно последнюю задачу (по аналогии с (15.44)) можно за-

писать как

(μ

, π

) = min (μ

, π

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

∈Δ

Объединяя задачу (15.44) и задачи (15.48), можно заклю-

чить, что оптимальное в целом решение ищется как

(μ

,π

) = max min (μ,π) . (15.49)

π∈Δ

μ∈Δ

Здесь

Задачи подсистем (15.45)-(15.47) относятся к классу задач

линейного программирования и могут быть решены на основе

симплекс-метода. Здесь следует отметить, что использование

метода обратной матрицы для решения прямой задачи (15.34) -

(15.37) позволяет получать решение и двойственной задачи

(15.45) - (15.47).

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

давать ресурсов π

больше той подсистеме, где эффективность

их использования μ

πi

выше. Тогда очевидное решение такой за-

дачи имеет вид

0, μ

πij

< max μ

πij

= i

, μ

πij

= max μ

πij

Непосредственное использование последнего выражения

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

вычислительный процесс неустойчивым, поэтому используются

другие схемы решения задачи. Алгоритм Корнаи-Липтака являет-

ся исторически первым способом решения такой задачи, в основе

342

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

следовательности партий игры двух лиц. В качестве первого иг-

рока выступает Центр, а в качестве второго выступают подсисте-

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

онные задачи. Сходимость процесса обеспечивается использо-

ванием итеративной процедуры Брауна-Роббинсон (см. 13.3.3).

При этом Центр решает задачу

(μ, π

(μ)) = max (μ, π)

π∈Δ

в подсистемах решается задача

(μ

(π), π) = min (μ, π).

μ∈Δ

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

которого состоит из нескольких шагов.

Начальная итерация (1-я).

1). Выбирается произвольное распределение глобальных ре-

сурсов, например, как π

= b

/ p, j=1,...,m

2). В результате решения задач (15.45)-(15.47) вычисляется μ

3). Полагаем μ[1] = μ

; k = 2. Задается критерий завершения

итерационного процесса ε > 0.

Произвольная итерация (k-ая):

1). В результате решения задачи (15.42), (15.43) находится

значение π

= π

(μ[k-1]).

2). Вычисляется значение

π[k] = (k-1)/k π[k-1] + 1/k π

3). В результате решения задач вида (15.45) - (15.47) находит-

ся значение μ

= μ

(π[k])).

4). Вычисляется значение

μ[k] = (k-1)/k μ [k-1] + 1/k μ

5). Если

║ μ[k] - μ[k-1] ║ ≤ e, то процесс окончен.

Если

║ μ[k] - μ[k-1] ║ > e, то k = k + 1; производится переход

на шаг 1.

Последовательность значений (μ

[j], π

[j]) сходится к сед-

ловой точке исходной задачи (15.49). Вместе с тем сходимость

данной процедуры достаточно медленная. В ряде работ рассмат-

риваются другие схемы решения данной координационной зада-

чи, обладающие более высокой сходимостью.

343

15.4. Релаксация в задачах координации

Релаксация, заключающаяся во временном отбрасывании

части ограничений, особенно эффективна в ситуациях со специ-

фической структурой условий или, когда заранее известно, что

часть ограничений несущественна при оптимальном решении. В

ряде случаев часть ограничений (R) задачи удовлетворяет неко-

торым теоретическим условиям, позволяющим использовать эф-

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

ствуют и другие ограничения (P), не соответствующие таким ус-

ловиям. Тогда разумная стратегия решения такой задачи состоит

во временном отбрасывании P ограничений и решении релакси-

рованной R - задачи. Если такая R - задача неразрешима, то не-

разрешима и исходная задача. Если она разрешима, и получен-

ное решение удовлетворяет P - ограничением, то решение опти-

мальное для R - задачи будет

и в целом оптимально. В против-

ном случае необходимо ввести в R-задачу одно или более из P

ограничений и повторить процедуру.

Итак, пусть имеется задача

= Arg max f(x) , Δ = {x∈R

│g

(x) ≤ b

, i ∈ M}

x∈Δ

Релаксированная R - задача заключается в учете ограниче-

ний только из множества R, где R⊆M. Предположим, что сущест-

вует конечный максимум f(x), который достигается на решении x

тогда релаксационная стратегия представляет собой итератив-

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

следующих шагов.

0) Назначим F = +∞; выбирается подмножество ограниче-

ний R⊆M такое, что f(x) ограничена на Δ

= {x∈R

│g

(x) ≤ b

, i ∈ R}.

1) Решается R-задача. Если она неразрешима, то и исход-

ная задача неразрешима, в противном случае x

- оптимальное

решение такой задачи.

2) Решение x

проверяется на допустимость по отношению

к оставшимся ограничениям. Если g

) ≤ b

, i∈M\R, то x

- опти-

мальное решение исходной задачи в целом.

3) Пусть S⊆M\R, такое, что ∃k∈S, для которого не выполня-

ется k-е ограничение при x

(т.е. g

) > b

). Введем подмножест-

во V⊆R, для которого ограничения выполняются как строгие не-

равенства V = { j∈R│g

) < b

344

4) Тогда,

- если выполняется f(x

) = F, то R = R ∪ S;

- если выполняется f(x

) < F, то R = R ∪ S\V; F=f(x

Осуществляется переход к шагу 1.

Таким образом, в процедуре добавляется одно или более

невыполненных ограничений, если F не изменяется, и добавля-

ются невыполненные ограничения и изымаются несущественные

ограничения, если F уменьшается. Данная процедура за конечное

число шагов либо устанавливает неразрешимость исходной за-

дачи, либо приводит к оптимальному решению.

Описанная процедура достаточно эффективна в

условиях

специфической структуры ограничений и служит для формально-

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

ординации. Действительно, если ограничения имеют блочно-

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

будет иметь блочную структуру (определяемую задачами подсис-

тем). В этом случае решение рассматриваемой релаксированной

задачи сводится к решению p независимых задач, для которых

впоследствии

учитываются связующие ограничения. В других

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

условиям, которые позволяют использовать для этой части огра-

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

зование идей релаксации для таких задач также оказывается

весьма полезным.

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

операций управления КА

Функционирование автоматизированной системы управле-

ния КА характеризуется, с одной стороны, большим разнообрази-

ем задач, решаемых объектами, а с другой - взаимной зависимо-

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

всех объектов комплексом технических средств, привлекаемых к

управлению. Указанные особенности функционирования системы

необходимо учитывать при решении задач автоматизации управ-

ления и,

в частности, планирования на основе разработки ком-

плекса частных моделей планирования для отдельных КА (при-

меры таких моделей рассматривались в 12.4) и модели коорди-

нации планов, которую рассмотрим здесь.

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

формализация конфликтов между подсистемами в удобном для

345

анализа виде. Представим общий план в виде u = ║u

,...,u

║,

где u

- план управления ν-м КА. Плану u

однозначно соответ-

ствует упорядоченное множество запланированных действий ║y

i∈I

║. В плане u

содержатся компоненты, соответствующие опе-

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

темах (на основе моделей планирования операций отдельных КА

см.1.4). Тогда u∈Δ, где Δ - множество допустимых планов всей

системы в целом, если u

∈Δ

, ν∈ N = {1,...,n}, и планы отдельных

КА u

не конфликтуют между собой по привлекаемым в процессе

реализации этих планов техническим средствам управления.

Можно различать следующие ситуации, приводящие к кон-

фликтам операций управления:

а) конфликты локализованы на сравнительно небольшом

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

способностью средств управления. Это, например, ситуации, ко-

гда:

- операции проводятся в одно и то

же время и требуют при-

влечения одного и того же технического средства управления;

- операции проводятся в разное время, но требуют привлече-

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

после выполнения одной операции для выполнения другой;

- совместная работа средств невозможна по условиям техни-

ческой совместимости проводимых работ;

и т.д.

б) ситуации, когда имеются ограничения ресурсного типа,

которые определяются техническими возможностями и особенно-

стями функционирования средств управления и проявляются на

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

планирования. Например,

- ограниченная длительность непрерывной работы средства

управления;

- ограничения по информационной загрузке каналов связи при

передаче данных между пунктами управления;

- ограниченный суммарный расход

некоторых видов ресурсов

на интервале управления

и др.

Ситуации первого типа имеют локальный характер, и опи-

сываемые ими конфликты должны анализироваться в каждый

момент времени. Рассмотрим особенности решения задачи, свя-

занной с развязыванием конфликтов такого рода. Основное со-

держание данной релаксированной задачи определяется кон-

346

фликтными ситуациями, имеющими место между планами управ-

ления различными КА, которые определяются конфликтами дей-

ствий, составляющих эти планы. Указанные конфликты можно

описать рефлексивным бинарным отношением R

или соответст-

вующим ему неориентированным графом G

без петель и крат-

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

ответствуют существующие между действиями конфликты. Пусть

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

целом, составленный из планов выполнения операций управле-

ния КА, u = ║u

,...,u

║ будет допустимым планом, если

∑

=ν

≤ e,

∈Δ

, ν∈N,

где A

подматрица матрицы инциденций A = ║ A

,...,

║, соот-

ветствующая плану u

управления ν-м КА; e - вектор, все компо-

ненты которого равны единице; Δ

- множество допустимых пла-

нов ν-го КА.

Проводя анализ графа G

, можно заключить, что множество

его вершин разбивается на подмножества, соответствующие

полным подграфам графа G

(на клики). Из каждой такой клики

можно выбрать только одну вершину, так как все остальные вер-

шины данного подмножества (клики) с ней конфликтуют.

Данную конфликтную обстановку можно описать с помощью

гиперграфа H

- обобщенного неориентированного графа, верши-

ны которого соответствуют вершинам G

, а ребрами являются

подмножества конфликтующих вершин. Сопоставив теперь каж-

дому ребру гиперграфа H

клику в графе конфликтов G

, условия

совместности планов u

, можно записать с использованием мат-

рицы A

инциденций гиперграфа H

в виде

u ≤ e. В задачах

планирования операций управления размерность A

, как правило,

существенно меньше размерности матрицы

Таким образом, условия развязывания конфликтных ситуа-

ций можно формально описать совокупностью линейных алгеб-

раических неравенств:

∑

=ν

≤ e,

В целом

задачу оптимального планирования работы

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

347

arg opt { g(u) │

∑

=ν

≤ e, u

∈Δ

, ν∈N }, (15.50)

где u

║ u

,...,u

║ - оптимальное решение;

g(u)- глобальная целевая функция системы в целом;

- ν-я подматрица матрицы A

= ║ A

,..., A

,...,A

║;

opt - экстремальная характеристика g(u), используемая при

нахождении оптимального плана операций; в дальнейшем для

определенности будем полагать, что opt = max;

- множество допустимых планов ν - го КА.

Полагая, что качество функционирования комплекса в це-

лом достигается независимым (в смысле решения целевых за-

дач) функционированием объектов, целевую функцию g(u) можно

представить в виде

g(u) =

∑

=ν

т.е. полагать сепарабельной относительно целевых функций КА.

Здесь γ

относительная важность ν-го объекта; ∀γ

≥ 0; Σγ

= 1. Значения γ

вычисляются в результате анализа целей и за-

дач, решаемых ν-м КА, и представляют, по-существу, результат

формализации решающего правила в задаче векторной оптими-

зации, где векторный критерий образован целевыми функциями

отдельных КА.

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

arg max {

∑

=ν

) │

∑

=ν

≤ e, u

∈Δ

, ν∈N }, (15.51)

Обозначим │Δ

│=S

, ν∈N и сопоставим каждому j-му вари-

анту допустимого плана u

νj

булеву переменную δ

νj

. Тогда задачу

(15.51) можно представить как

∑

=ν

∑

νj

→ max, (15.52)

∑

=ν

∑

νj

≤ e, (15.53)

∑

νj

=1, ν∈N, (15.54)

νj

∈ {0,1}, ν∈N, j = 1,...,S

. (15.55)

348

Здесь g

νj

= g

νj

); α

νj

= A

νj

Таким образом, нелинейная в общем случае задача (15.51),

с учетом проведения соответствующих расчетов для g

νj

и α

νj

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

бенность последней задачи заключается в том, что элементы

матрицы A

= {a

}, a

∈ {0,1}, тогда и компоненты вектора α

νj

также принимают значение 0 или 1. Последнее объясняется тем,

что конфликты между действиями ν-го объекта полагаются развя-

занными, т.е. план u

νj

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

средств управления. В этих условиях все допустимые решения,

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

точкам многогранника, задаваемого ограничениями (15.53),

(15.54) при δ

νj

≥ 0. Множество таких точек связно. Тогда, исполь-

зуя алгоритм симплексного типа, анализирующий целочислен-

ность вершины, в которую осуществляется переход, можно из

исходной целочисленной вершины достичь оптимальной верши-

ны, которая и будет решением задачи (15.52)-(15.55).

Поскольку все допустимые решения задачи (15.52)-(15.55)

являются крайними точками многогранника (15.53), (15.54), δ

νj

≥0,

∀(ν,j), то для них справедливы соотношения двойственности ма-

тематического программирования. Тогда критерием оптимально-

сти некоторого решения δ = ║δ

νj

║ является условие

min ((π

, α

νj

) - γ

νj

+ π

) ≥ 0, (15.56)

ν,j

где (π

, α

νj

) - скалярное произведение векторов π

и α

νj

;

- вектор двойственных оценок условий (15.53);

- двойственная оценка ν - го условия вида (15.54).

Выражение (15.56) можно преобразовать:

min ((π

, α

νj

) - γ

νj

+ π

) = min (π

- max( γ

νj

- (π

, α

νj

)) =

ν,j ν j

(15.57)

min (π

- γ

max (g

) - (π

, A

)) ≥ 0,

ν u

∈Δ

Здесь выражение max (g

) - (π

, A

)), u

∈Δ

представ-

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

вания операций управления ν-го КА. Варианты таких моделей

(статических и динамических) рассматривались ранее в 12.4. Из

выражения (15.57) ясно, что скалярное произведение (π

, A

)

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

349

действует на подсистемы (модели планирования операций

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

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

можно ин-

терпретировать как "цены" конфликтных ресурсов, выраженные в

единицах глобальной критериальной функции. Информационный

обмен между координатором и подсистемами аналогичен пред-

ставленному на рис.15.3, координатор (Центр) посылает в под-

системы значения π

kν

(π

kν

= π

), а подсистемы посылают в

Центр значения u

νj

, которые представляют собой множества

вариантов планов и значений модифицированной целевой функ-

ции, сообщаемых на каждом итерационном цикле согласования

координатору

= (g

νj

) - (π

kν

, u

νj

)), ν∈N, j = 1,..., p

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

координатору на итерационном цикле;

kν

- n-ый подвектор вектора π

двойственных оценок условий

(15.53); π

= |π

,..., π

kν

,...,π

Отметим, что нахождение оптимальных координирующих

сигналов π

kν

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

вания.

Оптимизационная задача Центра (координирующая зада-

ча) имеет вид (15.52)-(15.55) при условии, что S

= p

. Координа-

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

kν

, кото-

рые представляет собой предварительное распределение "цен" в

единицах глобальной целевой функции на использование техни-

ческих средств управления. Если такой информации у координа-

тора нет, то π

kν

представляют собой вектора соответствующий

размерности, все компоненты которого равны 0.

Подсистемы на основе моделей, отражающих особенности

управления КА, планируют операции и находят оптимальный от-

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

kν

план u

(π

kν

). Для по-

вышения скорости сходимости процесса координации планов

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

нения операций управления КА находить некоторое множество

подоптимальных планов. Тогда в подсистемах вырабатываются

множества вариантов планов u

νj

и соответствующих им целевых

функций

, где

= (g

νj

) - (π

kν

, u

νj

)). Значения

, u

νj

сообща-

ются координатору.

350

На основе полученных из подсистем данных (

νj

), ν∈N,

j=1,...,p

координатор строит свою задачу в виде (15.52)-(15.55).

Для этого необходимо проанализировать конфликты между пла-

нами u

νj

, ν∈N, j=1,...,p

, и формализовать их в виде векторов кон-

фликтов α

νj

= A

νj

Процедура координации планов КА идейно схожа с коорди-

нацией Данцига-Вулфа. Действительно, одинаково используется

механизм "цен", как координирующих воздействий, аналогично

проводится модификации целевых функций подсистем. Вместе с

тем имеется ряд существенных отличий:

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

го, то, что глобальный план системы в целом получается как объ

единение планов подсистем в отличие от алгоритма Данцига-

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

торыми коэффициентами, определяемыми в результате решения

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

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

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

вида задач линейного программирования.

Полученный в результате решения рассмотренной задачи

оптимальный план

учитывает особенности управления КА, опре-

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

возникающие при управлении различными объектами, которые

имеют локальный по времени характер. Вместе с тем существует

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

которые проявляются либо на всем интервале планирования в

целом, либо на временных интервалах, соизмеримых с ним. Та-

кие

ограничения целесообразно учитывать при решении допол-

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

идей релаксации (см.15.3). Особенность условий, описываемых

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

управления они, как правило, выполняются. Кроме того, на прак-

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

тер, и в случаях, если других

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

управления, связанных с целевым назначением КА, нет, они мо-

гут не приниматься во внимание. Таким образом, целесообразно

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

сывание части условий) и решать релаксированную адачу с по-

следующим учетом отброшенных условий.

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

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