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

Введем переменные:

(10.214)

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

=m; (10.215)

= m-1, s=1,...,N, i = l,...,M; (10.216)

vsi ≤ ui, s= 1.....N,

и функции:

L (xs) = - vsi) ρ (xs ,yi), s = 1.....N; (10.217)

FГМСК≥L(xs), s=l.....N; (10.218)

FИМСК = L (xs). (10.219)

Рассмотрим следующие оптимизационные задачи: найти значе­ния

, при которых достигается минимум FГМСК или FИМСК при выполнении условий (10.214)— (10.218).

Эти задачи яв­ляются задачами линейного программирования с матрицей огра­ничений весьма простой структуры. Решение таких задач — стан­дартная проблема вычислительной математики, для чего имеется достаточно много программ, входящих в математическое обеспе­чение всех современных ЭВМ.

Исследуем эти задачи. Первыми определяющими их условиями являются

FГМСК≥ L(xs) ≥0; FИМСК ≥L(xs) ≥0,

т. е. критерии ограничены снизу, поэтому задачи имеют решения.

Если и=(u1.....им) — фиксированный вектор, удовлетворяю­щий условиям (10.213), (10.214), определим значения , минимизирующие FГМСК, FИМСК. Значения {vsi}i=1.....M для раз­личных и независимы между собой, поэтому их можно определить из следующей вспомогательной задачи:

vsi = ui-zsi, i=1,...,M; (10.220)

L(xs)= zsiρ(xs, yi)→min; (10.221)

zsi = 1;

0≤zsi≤ ui, i=l,...,M. (10.222)

Простейшая задача линейного программирования, определяе­мая условиями (10.220)— (10.222), имеет очевидное решение. Числа

ρ(xs, yi), i=1,…, М упорядочиваются по возрастанию, т. е. каждому номеру i сопоставляется номер k числа ρ(xs, yi) в этой последовательности, так что если,

ks (il) >ks(i2)

то

ρ(xs, )≥ ρ(xs, ) il, i2 {1,...,М}. (10.223)

Затем определяется номер k*s такой, что (10.224)

где is (k) — обратная функция ks(i). Оптимальные значения:

(10.225)

которым соответствуют значения:

(10.226)

Из выражения (10.226) следует, что оптимальное значение vsi будет не более, чем при одном значении i (при данном s), отличном от 0 или ui. При этом соотношению (10.225) соответствует следующее оп­тимальное значение (10.220):

(10.227)

Cуществует оптимальное решение исходной задачи, для которого выполняются соотношения (10.225)— (10.227).

Допустим, что условия (10.214)-(10.219) дополнены требованиям целочисленности ui, i = 1, ..., М. Такие задачи назовем сужен­ными, поскольку множество векторов ui здесь уже, и соответст­венно оптимальные значения критериев будут не меньше, чем в задачах, определяемых условиями (10.224)— (10.229).

В суженных задачах, очевидно,

Тогда из соотношения (10.227) с учетом условия (10.223) можно записать

L(xs) = ui (k*s)ρ( xs, , (k*s)) = ρ(xs ,yi ) (10.228)

Соотношение (10.228) совместно с выражениями (10.218), (10.219) позво­ляет установить взаимооднозначное соответствие между

m-элементными стратегиями А множества YK и булевыми векторами

и = (u1, ..., им), удовлетворяющими выражениями (10.218), (10.219):

(10.229)

Причем значения FГМСК, FИМСК в суженных задачах равны соответ­ствующим значениям показателей эффективности ГМСК и ИМСК. Это следует из того, что по условиям (10.228) и (10.229)

Lu(xs) = L(xs),

а в суженной задаче, учитывая неравенство (10.228), а также требо­вание минимизации FГМСК, можно получить

FГМСК = L(xs),=L(x).

Как отмечалось, оптимальное значение критериев в суженных задачах не меньше, чем в исходных задачах, определяемых условиями (10.214)— (10.219), поэтому окончательно можно установить, что если ГМСК ИМСК — оптимальные значения критериев в исходных задачах, то

≥ ИМСК для ИМСК

≥ ГМСК для ГМСК

Обозначая

лп

запишем

F≥ лп (10.230)

Итак, решая задачу, определяемую условиями (10.214)— (10.219), с критерием ГМСК или ГМСК в зависимости от типа оптимизируе­мой МСК можно получить оценку снизу для оптимального значе­ния показателя эффективности МСК. Если — оптимальное реше­ние рассматриваемой задачи — булево, то

= лп (10.230)

и соответствующая по условию (10.229) стратегия — оптимальна. Если же небулево, можно получить ближайший к нему булевый вектор s, например,

s = ( 1б..... Mб );

uiб =m;

i .

В этом случае F ≥ F, где б — стратегия, соответствующая по

условию (10.229) б.

Заметим, что если — булево, то б = и.

Итак, рассматривая полученные условия совместно с выражением (10.226), получим

Fли≤F≤ F (10.232)

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

10.2.6.5. Алглритмы распределения и улучшения

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

Пусть {E0j}j=1,.....,т — начальный набор областей Дирихле.

Перебором для любого у Yк можно рассчитать

(10.233)

и вычислить , у0j, j = 1,..., т, т. е.

0j= (у) = { 0j ), j=l,...,m.

Для стратегии А0 = { j}j=1, ..,m найдем оптимальный

набор областей Дирихле {E} j=1, ..,m , использyя очевидное

условие: хЕ1j, если L (х)=ρ (х, j,). При этом, учитывая выражения (10.183), (10.184), можно получить

F =

Затем процесс повторяется: для {Е1j} j=1, ..,m отыскивается

А1 = {1j } j=1, ..,m и т. д.