§ 2. Метод последовательных расчетов

Наряду с развитием общих схем дискретного программирования весьма важным является создание методов решения для конкретных классов задач. Одним из наиболее оригинальных и интересных шагов в этом направлении являются работы Черенина [37], [38], в которых развивается «метод последовательных расчетов» для нахождения экстремума функции, определенной на всех подмножествах данного конечного множества. Интересно отметить, что первоначальная разработка этого метода и его применение к одному типу прикладных задач (составление плана формирования поездов) относится еще к 1948 г.

2.1. Опишем формально общую постановку задачи. Дано некоторое конечное множество Его можно

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

Для любого подмножества задана функция характеризующая «качество» решения, которое определяется множеством Требуется найти множество на котором достигается глобальный максимум т. е. такое что для всех

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

В методе последовательных расчетов предполагается, что функция удовлетворяет следующему условию (в определенном смысле аналогичному условию выпуклости). Для любых

2.2. Теоретические основы метода последовательных расчетов даются следующей теоремой.

Теорема 2.1. Пусть функция удовлетворяет условию (2.1), — точка ее глобального максимума. Тогда для любой конечной последовательности содержащей со и такой, что функция монотонно возрастает до со и монотонно убывает после

Устанавливаемая этой теоремой своеобразная «унимодальность» функции позволяет отбраковывать сразу целые массивы вариантов. Действительно, пусть для некоторых таких, что найдены значения

Тогда при из рассмотрения можно исключить все вариантов Если же то можно отбросить все вариантов

Пусть, например, взяты некоторые для которых Тогда отбрасывается сразу вариантов (т. е. половина их общего числа). Это варианты, отвечающие ненулевому значению параметра оптимизации с номером из

2.3. Вычисления начинаются с пустого множества для которого (или же можно вести их и одновременно с обоих концов). После этого просматриваются все вариантов с и из них запоминаются только те, у которых Далее из оставшихся вариантов комбинируются всевозможные варианты и запоминаются лишь те из них, у которых не меньше, чем у каждого из двух составляющих вариантов и т. д. Этот процесс быстро заканчивается из-за невозможности дальнейшего комбинирования вариантов — все остальные варианты оказываются отсеянными. Вариант с максимальным из всех рассмотренных и будет оптимальным.

Обычно порядок объема перебора в этом процессе не превышает что существенно ниже объема полного перебора

2.4. В работах Черенина [37], [38] и Черенина и Хачатурова [39], [40] приведены формулировки ряда прикладных задач, которые могут успешно решаться методом последовательных расчетов. Наиболее важной из этих задач представляется модель размещения предприятий с учетом капиталовложений на их строительство, а также транспортных затрат. Некоторые результаты машинных экспериментов с задачами средних размеров охарактеризованы в [371, [40], [35а].