ГЛАВА 13. ЛОКАЛЬНЫЙ ПОДХОД к ЗАДАЧАМ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

Локальный подход, развитый в дискретном анализе (см. Журавлев был впервые перенесен на задачи целочисленного линейного программирования Журавлевым и Финкельштейном [8]. Существо локального подхода применительно к задачам дискретного программирования заключается, грубо говоря, в выделении и

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

Впоследствии локальный подход был распространен на более широкий класс задач в работах Финкельштейна [31], [34]. Этот общий подход и будет изложен в настоящей главе.

§ 1. Предварительные рассмотрения

1.1. Пусть имеется следующая задача дискретного программирования с сепарабельной целевой функцией.

Задача Z.

Максимизировать

при условиях

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

Введем матрицу инциденций уравнений и переменных задачи определив ее следующим образом:

Алгоритм, предложенный в [34], предназначен для решения квазиблочных задач, т. е. задач, в которых множества индексов можно разбить на непересекающиеся подмножества,

обладающие определенными свойствами:

Здесь множество переменных, могущих входить только в уравнения из множество переменных, могущих входить только в уравнения из

Рис. 13.1.1. Матрица инциденций

Введем обозначение

Матрица инциденций соответствующая квазиблочной задаче (1.1) — (1.3), изображена на рис. 13.1.1 (возможно, после некоторой перестановки строк и столбцов). Блоки на рис. 13.1.1 - это заштрихованные прямоугольники, причем блок находится на пересечении строк из и столбцов из Ненулевые

элементы матрицы инциденций могут находиться только в одной из заштрихованных клеток (т. е. в одном из блоков).

Блоки на рис. 13.1.1 слабо связаны между собой. Иначе говоря, если зафиксировать все переменные из при некотором положив

и рассмотреть задачу (1.1) — (1.3) при дополнительном условии (1.7), то задача распадется на две независимые задачи: Задача содержит нефиксированные переменные из множества и ограничения из множества Задача содержит нефиксированные переменные из множества и ограничения из множества

Алгоритм, предложенный в [34], эффективен для квазиблочных задач с не слишком большими блоками, т. е. для таких задач, в которых полный перебор

проделать невозможно, но можно произвести перебор

при объеме одновременно хранимой информации, не превышающем

1.2. Теперь, следуя работе Финкельштейна [31], предположим, что к условиям (1.1) — (1.3) добавлены еще следующие «сепарабельные» ограничения, содержащие все переменные:

Задачу, определяемую условиями будем называть задачей

Введем некоторые дополнительные обозначения. Вектор переменных будем обозначать через X:

Далее обозначим

Под будем понимать «подвектор» вектора X с компонентами, номера которых определяются множеством Более формально, если то

Фиксированное значение вектора будем обозначать через Символ будет обозначать вектор-функцию с аргументом Кроме того, условимся писать

если для всех Введем еще одно естественное обозначение:

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

Рассмотрим два вектора: вектор и вектор Предположим, что

Допустим теперь, что для некоторого вектора имеет место соотношение

I. Если выполнены условия (1.13) — (1-17), то вектор не может быть оптимальным планом задачи Если же допустить, что вместо соотношения (1.16) имеет место

то получаем следующее утверждение:

II. Если выполнены условия и оптимальный план задачи то оптимальным планом задачи является и вектор компоненты которого определяются по формуле

Алгоритм, излагаемый ниже, является непосредственным обобщением алгоритма для задачи (см. [34]) и отличается от него лишь структурой правил I и II, позволяющих сузить множество рассматриваемых вариантов. В правилах I, II учтено наличие условий (1.8), добавление которых превращает задачу в задачу