9.3. АЛГОРИТМ

Согласно изложенному в гл. 1 решения задачи могут быть получены с помощью построения последовательности такой, что:

- начальное разбиение, произвольно выбранное из для каждого

- решение задачи

- решение задачи

9.3.1. Этап представления

Для фиксированного разбиения задача

эквивалентна, благодаря свойству аддитивности критерия К задачам

где

Решение исходной задачи получим, если выберем в качестве решения множество, состоящее из решений задачи

Мы выбираем решение образованное всеми решениями задачи Множество конечно благодаря гипотезе

Замечание. В этих обозначениях и обозначениях, принятых в 9.1.3,

Две формулировки задачи являются, таким образом, эквивалентными.

9.3.2. Этап назначения

На этот раз речь идет о решении задачи

Представительство теперь фиксировано. Как и в гл. 1, благодаря аддитивности критерия мы можем выбрать в качестве решения

где функция назначения, определенная формулой

9.3.3. Сходимость и разные задачи

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

Напротив, сходимость самой последовательности требует детального исследования, поскольку задачи

не обязательно имеют единственное решение.

Предложение. Последовательность стабилизируется.

Доказательство. Как и в гл. 1, покажем сначала, что стабилизируется последовательность заметив, что она убывает и может принимать только конечное множество значений, так как

Если для достаточно больших , то согласно двум неравенствам, приведенным выше,

для достаточно больших

Полагая получим, используя результаты из 9.3.1, что представительства и являются решениями задачи т. е. и являются решениями задачи

Так как содержит все такие решения, для всех и для достаточно больших имеем

Отсюда получаем, что последовательность

также возрастает для достаточно больших Так как множество конечно, эта последовательность обязана стабилизироваться. То же верно для последовательности поскольку согласно гипотезе

Отсюда легко следует стабилизируемость последовательности

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