ЧАСТЬ III. КОМБИНАТОРНЫЕ МЕТОДЫ

Эта часть посвящена второй большой группе методов дискретного программирования. Как уже указывалось выше, при классификации численных методов (гл. 1, § 4), методы этой группы исходят прежде всего из конечности числа планов задачи, используя ее комбинаторный характер. Центральную идею комбинаторных методов составляет замена полного перебора всех планов их частичным перебором. Грубо говоря, это осуществляется путем отбрасывания некоторых подмножеств вариантов, заведомо не дающих оптимума; перебор при этом ведется лишь среди остающихся вариантов, являющихся в определенном смысле «перспективными».

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

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

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

По своему характеру комбинаторные методы весьма разнородны. Пожалуй, центральное место среди них занимают в настоящее время методы, объединяемые под названием «методов ветвей и границ». Общая идея метода ветвей и границ вместе с двумя важнейшими ее реализациями излагается в гл. 10. Идейно близок к этому подходу аддитивный алгоритм Балаша, описываемый в гл. 11.

Естественно отнести к группе комбинаторных методов также и различные алгоритмы, представляющие собой конкретизацию общих идей динамического программирования применительно к некоторым частным дискретным задачам. Некоторые такие приемы даны в гл. 12. Гл. 13 посвящена применению разработанного в дискретном

анализе локального подхода к некоторым задачам дискретного программирования. Наконец, в гл. 14 конспективно изложены метод Фора и Мальгранжа, а также метод последовательных расчетов В. П. Черенина для решения одного класса комбинаторных задач.