№146.11.Барщевский

371

Шаг 5. Элементы ik’’, полученные в решениях одной из задач (алгоритмов А1–А5), исключаются из рассмотрения и не могут попасть далее в класс k’ = 1. Удаляются соответствующие строки матрицы А.

Шаг 6. Задается k = k + 1. Если

k

N = Σ mr > mk + 1,

r = 1

переходят к шагу 2. Иначе оставшиеся элементы образуют последний класс и классификация закончена.

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

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

Алгоритм 4.4.

Шаг 1. Не снижая общности, положим P’K[Tp] = R-[Tp], где R-[Tp] задается уровнем h = 3.

Шаг 2. Для каждого k (от k = К до k = 1) рассчитаем описанными ранее методами (с учетом векторного критерия, с определением чувствительности решений) планы P1k[Tp], Fk(Р1k[Tp]), P’k – 1[Tp] = AkP’k[Tp], b’(Tr), ≤≥ b(Tr).

Шаг 3. Для заданного – с уровня h = 3 – значения вектора определим планы P2k[Tp], Fl(Р2k[Tp]) при изменении k от 1 до K.

Шаг 4. Найдем значения Fk = Fk(Р1k[Tp]) – Fk(Р2k[Tp]). Шаг 5. Выявляются два возможных варианта:

1)Fk имеет одинаковые знаки для всех k (k = 1, K) – переход к шагу 6;

2)Fk различные по знакам – переход к шагу 7.

Шаг 6. В первом частном варианте элементы уровня h = 2 согласованы и можно использовать понятие эквивалентности и монотонности функций. Целевые функции Fl = F(Flk, k = 1, K) в выражении (9.35) монотонны относительно

Flk (F(Fl1 ,…, Flk – 1 , Flk, Flk + 1 ,…, FlK) > F(Fl1,…, Flk - 1, Flk‘ , Flk + 1,…, FlK), если

Flk > Flk’. Запишем лагранжиан

K K

где γk, λk – множители Лагранжа; Flk – линейная функция;

Gk = A2kPk[Tp] – b2k(Tr), k = 1, K; (П.9)

– выпукла. Функции Ll и Fl эквиваленты и задача (П.8) разделяется на k локальных и одну глобальную задачи. Для их решения возможно использовать стандартные методы:

372

1)метод целевой координации (баланс взаимодействий, невозможный метод);

2)метод координации моделей (прогноз взаимодействий, возможный метод).

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

Шаг 7. Во втором частном варианте интересы отличаются (не согласованы). Здесь возможно использовать:

1)теорию игр – равновесие по Нэшу;

2)методы решения задач с векторным критерием.

Алгоритм 4.5.

Пусть заданы задача планирования верхнего (h = 3) уровня в виде

AP[Tp] ≤ b(Tr), b(t0) = b(0),

F(P[Tp]) = <C, P[Tp]>Æ max, (П.10)

и задача для среднего (h = 2) уровня

K

F(Pk[Tp]) = Σ <Ck, Pk[Tp]> Æ max,

k = 1

AkPk[Tp] ≤ Pk - 1(Tp), k = 2, K,

A1P1[Tp] ≤ b(Tr). (П.11)

Пусть

C = d*Ck, где d = const.

Тогда задачи (П.10) и (П.11) согласованы.

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

A1P1[Tp] ≤ b(Tr)

A2P2[Tp] ≤ P1(Tp),

AK -1PK - 1[Tp] ≤ PK - 2(Tp),

AKPK[Tp] ≤ PK - 1(Tp).

373

Умножим последнее неравенство на A1 … AK –1, причем по условию Ak ≠ 0. Тогда

A1A2A3 … AK - 1AKPK[Tp] ≤ A1A2A3 … AK - 1PK - 1[Tp] ≤

A1A2A3 … AK - 2PK - 2[Tp] ≤

≤ A1A2A3P3[Tp] ≤ A1P2[Tp] ≤ A1P1[Tp] ≤ b(Tr).

Иначе говоря,

A1A2A3 … AK - 1AKPK[Tp] ≤ b(Tr).

и при A = A1A2A3 … AK - 1AK последнее выражение совпадает с выражением

(П.10).

Таким образом, области существования решений совпадают.

Заметим, что заключительный элемент K технологической линии имеет коэффициенты целевой функции пропорциональные коэффициентам C. Чаще всего d = I, где I – единичная матрица.

Тогда даже при неизменных Pk, k = 1, K – 1, увеличение PK[Tp] приводит к росту F(P[Tp]) при одновременном неубывании FK(PK[Tp]).

Аналогично обстоит дело при убывании PK[Tp]. Если принять во внимание, что рост PK[Tp] вызывает увеличение Pk[Tp], k = 1, K – 1, уменьшение PK[Tp] – уменьшение Pk[Tp], то тенденции в изменениях F(P[Tp]) и FK(PK[Tp]) сохраняются.

Это, как легко показать, имеет место не только при анализируемом последовательном, но и при параллельно-последовательном соединении k-ых элементов в технологической линии.

Иными словами, критерий F(P[Tp]) монотонен относительно составляю-

щей FK(PK[Tp]).

Тогда возможно учесть взаимодействие с верхним уровнем путем введения в целевую функцию уровня h = 2 дополнительных ограничений

K K

L = Σ Lk = Σ Fk(Pk[Tp]) + γ1T(A1P1[Tp] – b(Tr)) + γKT(PK[Tp] – P[Tp]).

k = 1 k = 1

Алгоритм 4.6.

Равновесие по Нэшу, определяемое выражениями (2.37, а), (2.37, б) устойчиво.

Доказательство. Пусть выражения (2.37, а), (2.37, б) определяют точку

374

Очевидно

n K n K n K

Тогда δFl’ > δFl и Fl > Fl’, т.е. элемент l теряет в выигрыше, а элемент s приобретает. Для элемента l это невыгодно.

Аналогичны рассуждения и для l r.

Таким образом, показано, что (9.37, а), (9.37, б) соответствует равновесию по Нэшу.

Алгоритм 4.7.

Вычитая из неравенств (9.9) для Pkн[τ] равенства (9.9) для Pkс[τ], получим выражение (П.12) для нового плана в отклонениях с неизвестными P4k[τ] и P’3k[τ]

где А6k, А9k, А11k, А12k – подматрицы соответствующей размерности матрицы А норм расхода ресурсов.

Поскольку часто |P4k| << |Pk|, |P3k| << |Pk|, то возможно существенное снижение размерности (а следовательно, и времени расчета задачи (П.5) по сравнению с задачей (9.9)).

Приложение 5

Метод моментов

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

.

z(t) = Az(t) + Bu(t) + f(t),

где z, u, f – векторы состояния, управления, возмущения; A, B – матрицы. При управлении с минимальной силой используется целевая функция

J = max{|u1(t)|, | u2(t|), | u1r(t)|}, t [0, T].

При управлении с минимальной энергией используется критерий

T

J = ∫ u(t)TRu(t) dt Æ min.

0

375

Оба метода используют тот факт, что решение дифференциального уравнения имеет вид

t

z(t) = W(t, 0)z(0) + ∫{W(t, τ) Bu(t) + f(t)}dτ,

0

где W(t, τ) – фундаментальная матрица, определяемая из уравнение

.

W(t, τ) = AW(t, τ).

Вводят выражение

T

∫ W(t, τ) Bu(t)dτ = c

0

или

T

c = z(T) – W(T, 0)z(0) – ∫ W(T, τ) f(t)dτ.

0

Если обозначить строки выражения W(T, τ)B через hi(t), то для оптимизации по энергии можно записать

<hi, u> = hi I =1, n,

где <., .> – скалярное произведение. В этом случае [17] решение

n

u(t) = Σ αihi,

i = 1

где αi – вещественные постоянные, а hi – линейно независимы. Вектор α является решением уравнения

Mα = c, M = <hi hj>; i, j. = 1, n,

где M – матрица Грама.

При управлении с минимальной силой решение u(t) получается из системы уравнений

T

∫[W(t, τ) Bu(τ)dτ = c;

0

T

c = z(T) – W(t, 0)z(0) – ∫W(t, τ) f(τ)dτ;

0

u0i = A signhi(t, λ), i = 1, n;

n

Σλici = 1;

i= 1

376

T

A = (∫ |hi(t, λ)|dτ)–1;

0

hi – i-я составляющая вектора W(t, τ) B.

Приложение 6

Открытая архитектура ПВС

Открытость архитектуры языка схем ПВС обуславливает наличие базовых (стандартных) и пользовательских (специализированных) структурных элементов при реализации ПВС. Рассмотрим их более подробно применительно к переходам и позициям предикатно-временной сети.

Переход в схеме ПВС трактуется как

T = <En, Lg, Ex>.

Здесь En – входной предикат, En EN, EN – множество типов входных предикатов данного диалекта языка схем ПВС,

EN = <ENo, ENr>,

где ENo – базовые (стандартные) типы входных предикатов, ENr – пользовательские (расширенные) типы входных предикатов.

Набор базовых (стандартных) типов входных предикатов определен в табл. П6.1.

Логическая операция Lg = {lg1, lg2, …, lgn}, lgi – логический операнд, lgLG, LG – множество типов логических операций данного диалекта языка схем ПВС,

LG = <LGo, LGr>,

где LGo – базовые (стандартные) типы логических операндов, LGr - пользовательские (расширенные) типы логических операндов.

Часто в качестве стандартной логической операции принимают логическую операцию Lg = . Однако в качестве стандартных могут быть приняты операнды обработки атрибутов ЛО “Статистика” и так называемые “графические” операнды, обеспечивающие вывод информации о выполнении модели на экран (информационные табло, карты).

Выходной предикат Ex EX, EX – множество типов выходных предикатов данного диалекта языка ПВС-схем,

EX = <EXo, EXr>,

где EXo – базовые (стандартные) типы выходных предикатов, EXr - пользовательские (расширенные) типы выходных предикатов.

Перечень базовых (стандартных) типов выходных предикатов определен в табл. П6.2.

379

P = <Ts, Sr, Tg>

применительно к функции задания времени задержки метки, функции упорядочивания очереди меток и функции задания времени жизни метки.

Функция задания времени задержки метки Ts TS, где TS – множество типов функций схем ПВС

Ts = <TSo, TSr>

и TSo – базовые (стандартные) функции задания времени задержки метки, TSr – пользовательские (расширенные) функции задания времени задержки метки. Стандартные типы функций времени задержки меток приведены в табл. П6.3.

380

Функция упорядочивания очереди меток Sr SR, для SR – множества типов функций упорядочивания очереди меток

SR = <SRo, SRr>,

где SRo – базовые (стандартные) функции упорядочивания очереди меток, SRr – пользовательские (расширенные) функции упорядочивания очереди меток. Стандартные типы функций упорядочивания меток перечислены в табл. П6.4.

Аналогично функция задания времени жизни метки Tg TG, TG – множество типов функций задания времени жизни метки (табл. П6.5) данного диалекта языка схем ПВС,

TG=<TGo, TGr>,

где TGo – базовые (стандартные) функции задания времени жизни метки, TGr – пользовательские (расширенные) функции задания времени жизни метки.

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