Консалтология Общая теория консалтинга (стр. 103 )

Тогда для ГMСК

= (x)≥ (x)-LYz= -LYz

Аналогично для ИМСК

= (x)≥ (x)-LYzΩ= -LYzΩ.

Итак, вообще для МСК

≥ -λ≥v-λ,

где

λ=

Если Ат — оптимальная стратегия, то = m.

Таким образом, для того чтобы m-элементная стратегия, q эле­ментов которой отстоят друг от друга не более чем на z, была оптимальна, должно соблюдаться условие

λ≥-Fm;

λ= (10.208)

Полученное условие (10.208) позволяет ограничить переборы при проверке различных стратегий из Y на оптимальность. Заметим, что ввиду очевидного неравенства ≥ при к>т условие (10.208) можно усилить следующим образом.

Если z таково, что

λ <-, (10.209)

в частности,

λ <-, λ =- Fa

(где А — любая m-элементная стратегия), то стратегия, из т эле­ментов которой q расположены не далее чем на расстоянии z друг от друга, неоптимальна.

Если положить в условии (10.208) q — т, то оказывается, что если z таково, чго λ <-, в частности,

(10.210)

(где А — любая m-элементная стратегия), то элементы m-элементной оптимальной стратегии отстоят друг от друга на расстоянии не меньшем z.

Если положить q=2 и воспользоваться условием (10.209), можно получить оценку для целесообразного значения δу-параметра сети Y*. Действительно, если некоторый элемент сети входит в оптимальную стратегию, то в нее не может войти элемент, отстоя­щий от него менее чем на z, определяемое условием:

λ <-,

Поэтому нецелесообразно выбирать δу < z/2.

Наконец, получим оценку для сравнения показателей эффек­тивности МСК двух близких стратегий. Пусть А — {yj}j=1.....т, а стратегия А' отличается от А лишь последним элементом η, причем

|| yт — η || ≤ψ.

Тогда имеем:

для ГМСК

FA ≥ Fa′ — LYψ;

для ИМСК

FA ≥ Fa′ — LYψΩ.

Отсюда видно, что если в стратегиях A, A'q, q ≤ т совпадает m — q элементов, а остальные q соответственно отличаются друг от друга не более чем на ψ1, ..., ψq, то

λ<β(Fm-1-Fa),

где

β= (10.211)

Полученные оценки позволяют с заданной точностью перехо­дить от оптимизации МСК с бесконечными множествами X и Y к оп­тимизации МСК с конечными множествами Хк, Yк:

Xк = {xs}s=l,....,N

Yк = {yi}i=l,....,n

Для оптимизации такой МСК разработано несколько алгоритмов:

- комбинаторный с ограничением перебора;

- оценок на основе линейного программирования;

- распределения;

- улучшения.

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

10.2.6.3. Комбинаторный алгоритм оптимизации с ограничением перебора

Допустим, что даны число элементов оптимизируемой страте­гии т и число z, которые, используя условия (10.210), определяют минимальную взаимную близость элементов в оптимальной стра­тегии. Обозначим

G(yi) = {yp: || yi — уР||<z, р=1,...,М, р≠i, i=1,...,М.

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

А= {yj}j=1,.....,m, удовлетворяющие условию

A∩Ø

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

(10.212)

Первое условие в (10.212) порождает следующий эффективный алго­ритм перебора m-элементных стратегий, содержащих оптимальную стратегию. При этом рассматривается множество номеров I1={1,2,...,М}. Один из его элементов j1 принимается за номер первого элемента стратегии. Затем из I1 исключаются номера j такие, что

G (yj)j1; j≤ j1.

Второе условие в (10.212) служит для того, чтобы исключить из перебора стратегии, отличающиеся лишь порядком следования элементов. В перебираемых стратегиях номер в Y последующего элемента всегда больше, чем у предыду­щего. Тем самым, I1 преобразуется в I2. Один из элементов I2 — j2, принимается за номер второго элемента стратегии. Из I2 исклю­чаются номера j такие, что

G (yj) j2, тем самым формируется I3 и т. д. до получения Im, т. е.

I1 = {1,.2, .... М};

Ik+1 = Ik \{j: G (yj) jk ; j ≤ jк;. jк Ik}к=1 ...m-1;

А = { }, js Is, s= 1,...,m.

Если Iк = Ø, к ≤ т, то осуществляется выбор иного элемента в Ik-1. Когда это невозможно (все элементы уже перебраны), про­цесс прекращается.

Если Im≠Ø, то каждый его элемент является m-м элементом стратегии А. После перебора из всех выбирается новый элемент Im-1 в качестве т — 1-го элемента стратегии и т. д. до перебора всех элементов I1. Для каждой сформированной таким образом стратегии А подсчитывается FA, и таким сбразом определяется оптимальная стратегия А:

F≡ FA ≡FA,

а заодно подсчитываются оценки (10.201), (10.202), необходимые для последующей модификации сетей Xк, Yк.

Для еще большего ограничения перебора используют условие (10.203). Пусть FT — текущая верхняя оценка , например, наи­меньшее из уже подсчитанных значений FA, а А1 — некоторая сформированная алгоритмом стратегия. Для того чтобы страте­гия A, q членов которой не более чем на ψi (i=1,...,q) отли­чаются от соответствующих членов А1, не была оптимальной, до­статочно по условию (10.211), чтобы

-β> FT

так как тогда Fa ≥ FA — β > Fт > F. Отсюда следует, что для этой стратегии

(10.213)

Проверка условия (10.213) позволяет отсеивать заведомо неопти­мальные стратегии, не вычисляя для них значения показателя эффективности.

Алгоритм позволяет найти абсолютный минимум FA и опти­мальную стратегию, однако (в худшем случае) может возникнуть потребность полного перебора.

10.2.6.4. Алгоритм оценок на основе линейного программирования

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