метр 514, где бн - правило, по которому при любых / должна быть создана группа G, т.е. группа на базеу-4. Такова возможная интерпретация введенных параметров.

Пусть индексы группировочных элементов j - номера столбцов в матрице {Р, на базе которых осуществляется процедура разбиения множества R на группы Gj, где j - номер столбца; к - номер группы. Группы Gj образуются по следующему правилу.

Шаг 1. Для каждого у рассчитывается функция

и отыскивается значение Fj = Р.,„,,, а именно:

Fj. (ДЛ = exstrf р,П X,, = exstrX P,j-(4.1.10)

Полученная функция Fy предварительно определяет номер столбца J = уj, содержащего первую группу (Т,-. Индекс }\ означает, что группа по индексу j выбрана лищь в первом приближении. Группа G,-содержит пока все Л„ т.е. является наибольщей и наиболее полно отвечает условию (4.1.5).

Шаг 2. Проверяются условия (4.1.8) по каждому Л,- с Gy. Для всех RjdGy, по которым условия (4.1.8) не выполняются, в матрице {Р} вычеркиваются строки, соответствующие этим значениям /. Это означает, что из группы Gy исключаются все Л,, называемые обособленными, для которых не выполняются условия (4.1.8). После этого рассматривается {Рфх, т.е. матрица с вычеркнутыми по условию (4.1.8) строками, и рассчитывается функция

F.,.oAR,J) = exstr У РлПЧ,"(4.1.11)

Выражение (4.1.11) определяет новое значение экстремума функции Fj с Р.„„р,, т.е. новое значение Gj«, характеризующее первую группу. Наиденное значение j" определяет окончательный номер группировочного элемента у, образующего первую группу С,». Заметим, однако, что состав группы Gj« на этом щаге, удовлетворяя условию (4.1.5) и являясь допустимым по условию (4.1.8), не является пока оптимальным по условиям (4.1.4), (4.1.6). Завершая процедуру нахождения Gy., вычеркнем из матрицы (PJi столбец с индексом yl".

Рассмотрим теперь множество R\Gj«, состоящее из обособленных для группы Gj- подмножеств Rj, и матрицу {Pjjj полученную путем вычеркивания из матрицы {Pjj) столбца j" и всех строк, принадлежащих матрице {PyJi. Вычислим по {Pj>i2 функцию (4.1.10), т.е. Fj, и далее функцию (4.1.11), т.е. /». Таким образом находится номер груп-пировочного элемента, образующего вторую группу С7у», которая также удовлетворяет условию (4.1.5), допустима по условию (4.1.8), но не оптимальна по условиям (4.1.4), (4.1.6).

По аналогии находим группы , С7у, С,», С,» из множеств

{R\Gj.,Gj.),...,

Jk =Jt

А u Gj-.

. Jk =J

. Определив группы

{Gj-- } таким образом, можно утверждать, что они удовлетворяют следующим условиям:

F,-(R,J)= ехз1гД У

х- 1

Gj-, iR,j) = max R,;

уЛу(Л) . yPiiR); yyX,j{R)*y\/Kj{R).

(4.1.12) (4.1.13)

(4.1.14)

Здесь имеет место оптимизация по двум критериям (4.1.12) и (4.1.13) при ограничениях (4.1.14). Критерий (4.1.12) выполняется явно вследствие выражений (4.1.10), (4.1.11). Критерий (4.1.13) обеспечивается пошаговой процедурой следующим образом: вначале из множества R выбирается максимально возможная по величине группа Gj-, удовлетворяющая условиям (4.1.14), затем из обособленных подмножеств Л, <= (R\Gj-) выбирается также максимально возможная по величине группа С,» и т.д. По аналогии выбираются все группы Gj,,. Следовательно, все группы С,» - максимально большие по величине с учетом условий (4.1.14).

Шаг 3. Описанная процедура может быть улучшена в отношении условий (4.1.12) и (4.1.14). При выборе групп, например Gj„ и Gj,., часто оказывается, что некоторые множества R, можно отнести и к группе Gj- и к группе Gj--, если условия (4.1.14) выполняются для обоих группировочных элементов Д 1 и Д. При этом множества Л; всегда окажутся в группе Gj- . Однако далеко не всегда множества R] лучше включать в группу ф . Так, например, на рис. 4.1.4 показан

Рис. 4.1.4. Пример улучшения процедуры размещения

случай, когда множество Л можно отнести к любой из групп или С7у--, так как условия (4.1.14) выполняются для Д , и Д.

Если более подробно проанализировать содержательный смысл условий (4.1.14), то оказывается, что рещение существенно улучшается при отнесении R] к группе G--, а не к Gj« (как дает процедура). Например, если pj - расстояние (время), а функция (4.1.12) минимизируется, то при прочих эквивалентных условиях в случае р,у»< ру» при выполнении одновременных условий р,у»< р,- и Ру-предпочтительнее R] отнести к группе Gy». При этом значения (4.1.12) и (4.1.14) улучшаются.

Для реализации процедуры улучшения и окончательного определения состава групп Gj вычисляется функция для каждого / и

FijiRJ) = p,...fj?i,. exstr.

(4.1.15)

х= 1

По экстремальному значению Fjj для каждого группировочного элемента /[, полученного в результате 2-го и 3-го шагов, окончательно формируем группы Gj. Таким образом, в группу Gj входят только те узловые элементы /, для которых Fj имеет экстремальное значение. Естественно, формирование групп производится только вокруг уже полученных точек у",/2,...J". Поскольку условия (4.1.14)

по всем Л,, выполняются, хотя бы для одной из этих точек, дополнительной проверки условий (4.1.14) при этом не требуется. Таким образом, предложенный алгоритм решает задачи размещения по трем критериям: