ГЛАВА 11. АДДИТИВНЫЙ АЛГОРИТМ

В этой главе будет описан разработанный Э. Балашем «аддитивный алгоритм» для решения задач целочисленного линейного программирования с булевыми переменными. Изложение в основном следует статье Балаша [47].

§ 1. Постановка задачи и идея метода

1.1. Рассмотрим целочисленную задачу линейного программирования.

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

при условиях

Здесь любые из отношений

Путем элементарных преобразований задачу вида (1.1) -(1.3) можно свести к задаче минимизации целевой функции вида (1.1), но уже с неотрицательными коэффициентами при условиях, имеющих форму неравенств со знаком Эти преобразования очевидны:

1) каждое равенство в (1.2) заменить двумя противоположными неравенствами;

2) каждое неравенство со знаком умножить на

3) положить в случае задачи максимизации

а в случае задачи минимизации

Пусть число строк в преобразованной таким образом матрице (1.2) равно за правыми частями преобразованных ограничений (1.2) сохраним для простоты старое обозначение (здесь уже Обозначим также

Таким образом, задача (1.1) — (1.3) может быть записана в следующем виде. Минимизировать

при условиях

где

Вводя обычным образом -мерный вектор свободных переменных можно переписать задачу (1.5) в следующей канонической матричной форме. Минимизировать

при условиях

Задача (1.8) -(1.11) будет в дальнейшем именоваться задачей Пробным планом задачи будет называться любой -мерный вектор удовлетворяющий (1.9) и (1.10). Пробный план называется планом, если он удовлетворяет (1.11); план называется оптимальным, если он удовлетворяет (1.8) (т. е. минимизирует ).

столбец матрицы ограничений А в (1.9) будет далее обозначаться через

1.2. Дадим неформальное описание идеи аддитивного алгоритма. Ясно, что сформулированная выше задача имеет пробных планов. Основная черта аддитивного алгоритма, как и любого другого метода частичного перебора, состоит в получении оптимального плана (или в выяснении отсутствия планов) путем рассмотрения лишь некоторого подмножества всех пробных планов. Это осуществляется в рамках уже известной читателю общей схемы ветвления.

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

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

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

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

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