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

10.2.6.2. Алгоритм абсолютной оптимизации

Наряду с приведенными выше алгоритмами, область примени­мости которых ограничена специальными условиями, необходима разработка надежно действующего универсального алгоритма, гарантирующего отыскание абсолютного оптимума, который предъявлял бы минимальные требования к свойствам множеств X и Y и функции локальной эффективности.

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

Прежде чем перейти к описанию общего алгоритма, напомним, что задача оптимизации МСК (с некоторыми упрощениями) заклю­чается в следующем. Даны множества X и Y и определенная на подмножестве J их прямого произведения функция ρ (х, у) ≥0, такая, что любое сечение множества J по х непусто (обозначим сечение J по х через J (x), a J по у — через J (у) ):

J(x)≠Ø, x X.

Кроме того, задано целое число т. Требуется найти такое m-элементное подмножество А={Yi}i=1, ...,m Y (стратегию) и такую определенную на X распределяющую функцию Е(х), имею­щую область значений {1, 2, ..., т} и удовлетворяющую условию

x J(YE(x)) x X

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

F(X,A, E(x)))=ρ (x, y E(x)). (10.180) или

F (X, А, Е (х)) = (х, уЕ(х)). (10.181)

В первом случае говорится об интегральной многоцелевой системе, а суммирование понимается в смысле метрики X, во втором случае — о гарантирующей многоцелевой системе.

Как было нами установлено, распределяющая функ­ция оптимальной МСК при стратегии А задается условием

Е (х) = к/ρ (х, ук) ≤ ρ (х, уμ),

x J(ук ), x J(уμ ), ук, уμ А. (10.182)

Поэтому выражения (10.180), (10.181) могут быть представлены в виде

Fa= La(х), (10.183)

или

FA=LA(x), (10.184)

где

LA(x)= ρ (x, уj). (10.185)

Таким образом, общий алгоритм оптимизации МСК направлен на решение следующей задачи. Даны ограниченные замкнутые множества X и Y векторов конечно-мерных пространств размер­ности п и р соответственно, числа m, ε > 0 и определенная на J функция ρ (х, у) ≥ 0, удовлетворяющая условию Липшица:

(10.186)

В условии (10.186) норма вычисляется в чебышевской метрике, т. е. если

xк = (xiк) i =1.....n, yк = (ysк )s=1.....р,

то

(10.187) Требуется найти m-элементную стратегию А={yj}j=1,....,т Y, доставляющую с ошибкой не более ε минимум функций (10.183) (для ИМKС) или (10.184) (для ГМСК).

Решение этой задачи всегда существует. Действительно, ее можно рассматривать как задачу оптимизации функции FA на множестве Y' элементов А — прямом произведении т множеств Y:

Так как Y ограничено и замкнуто, то Y' также ограничено и замкнуто. Функция FA непрерывна на Y, поскольку получена суперпозицией конечного числа непрерывных функций (10.183)— (10.185), а функция ρ(х, у)— липшицева, т. е. непрерывна. Тогда по теореме Вейерштрасса FA принимает на Y' свое наименьшее значение. Соответствующий элемент А Y' является решением за­дачи при любом ε.

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

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

Из соображений экономии вычислительных ресурсов процесс «отсеивания» элементов сетей целесообразно организовать последовательно. Вначале строятся сети с большими значениями пара­метра, оптимизируется соответствующая им МСК с конечными мно­жествами и на основе результатов оптимизации вычисляются оценки влияния отдельных элементов сетей на искомое оптималь­ное решение. Полученные оценки используются для перехода к новым сетям с меньшим значением параметра, уже не содержа­щим элементов, в известном смысле близких к заведомо не влияю­щим на решение. Эту операцию назовем модификацией. Затем снова оптимизируется МСК с конечными множествами для модифицированных сетей и так далее, пока не будет по­лучено решение для сетей с параметрами, не превосходящими ε х, ε y.

Структура описанного алгоритма показана на рис. 10.58.

Перейдем к проработке отдельных его частей. Несложно получить оценки от­личия оптимальных решений исходной МСК с множествами X и Y и показателем эффективности F"а от вспомогательной МСК с замкну­тыми ограниченными множествами X* X, Y *Y и показате­лем эффективности ЕA при одинаковой функции локальной эффек­тивности ρ(х, у). Обозначим соответственно оптимальные стра­тегии через и A*, а оптимальные значения показателей эффек­тивности — через и F*. Положим для простоты J = X×Y. Рассмотрим ГМСК. Значение показателя эффективности как исходной, так и вспомогательной МСК будем рассчитывать по формуле (10.184). Таким образом,

= L (x), F* = L (x).

Рис. 10.58. Структура общего алгоритма оптимизации МСК

Для оптимального значения показателя эффективности ГМСК получена оценка:

F*-LYδy≤ ≤F*+Lxδx. (10.188)

Следовательно, оптимизируя вместо исходной ГМСК вспомога­тельную ГМСК с конечными множествами X*, Y*, которые являются сетями соответственно с параметрами δx, δy, можно принять полу­ченную стратегию A* за оптимальную для исходной ГМСК, допу­стив при этом проигрыш А:

∆ ≤ L (x) — F* + LYδy, (10.189)

но очевидно, что

L (x) ≤ L (x) + Lxδx = F* + Lxδx

Поэтому

∆ ≤Lxδx + LY. (10.190)

Обозначив через Ω меру множества X: