§ 4. Классификация численных методов

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

4.1. Для методов первой группы характерна прежде всего «регуляризация» задачи, достигаемая погружением ее исходной области допустимых решений (1.2), (1.4) в объемлющую ее выпуклую область (иными словами, временным отбрасыванием условий дискретности (1.4)). Затем к получившейся регулярной задаче применяются стандартные методы оптимизации. Если получившееся в результате решение уже удовлетворяет требуемым условиям дискретности, задача решена. Если же это не так, то требуется дальнейший переход к целочисленному решению. Еще раз подчеркнем, что этот переход не

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

Таким образом, указанный переход и составляет самую сущность методов этой группы. Впервые идея такого перехода была указана в работе Данцига, Фулкерсона и Джонсона [68] применительно к задаче о бродячем торговце; позднее аналогичная идея использовалась для другой конкретной задачи Марковицем и Манном [115]. Для общей целочисленной задачи линейного программирования соответствующая идея была высказана Данцигом [65]. Она заключается в следующем. Если в результате первого шага (решение задачи без учета требования целочисленности) получен не целочисленный план, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами:

1) полученный нецелочисленный план ему не удовлетворяет;

2) любой целочисленный план ему заведомо удовлетворяет.

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

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

Идея отсечения естественным образом приводит к трем проблемам:

1) нахождение универсального правила формирования дополнительных ограничений;

2) доказательство конечности соответствующего процесса отсечения;

3) борьба с чрезмерным «разрастанием» задачи при добавлении дополнительных ограничений.

Только решение этих проблем может привести к универсальному и реализуемому в вычислительном отношении алгоритму. Впервые это было проделано Р. Гомори в 1958 г. (первая публикация алгоритма [88]; см. также [83], [84]). Именно с этого момента начинается развитие общих методов отсечения; как отмечает Данциг [65], предыдущие реализации отсекающих плоскостей были сугубо неформальными, представляя собой скорее искусство, чем науку.

В дальнейшем Гомори обобщил идею формирования дополнительных ограничений и получил другую форму алгоритма для полностью целочисленных задач [85а], [86]. Этот метод особенно удобен в вычислительном отношении, ибо он требует лишь выполнения действий сложения и вычитания. В литературе [120] эти методы иногда называются соответственно «циклическим» и «дискретным» алгоритмами Гомори. Кроме того, Гомори распространил первый из своих алгоритмов на частично целочисленные задачи линейного программирования (первая публикация [85]). Важно отметить, что при определенных условиях доказана также конечность этих трех алгоритмов.

Нетривиальность проблемы отсечения состоит, в частности, в том, что далеко не любое правило формирования дополнительных ограничений, удовлетворяющих требованиям 1) и 2) (см. стр. 23), приводит к конечному вычислительному алгоритму. Этот вопрос будет рассмотрен в § 5 гл. 6 на примере одного правила формирования дополнительных ограничений, предложенного Данцигом вскоре после первой работы Гомори.

Развитие методов отсечения в последние годы шло как по пути их детализации, так и по пути их распространения с линейных на более общие задачи. Так, Кюнци и Этли [107], [108] предложили метод минимизации положительно определенной квадратичной формы

при линейных ограничениях и ограничениях целочисленности на ее переменные.

В работах [29], [30] был предложен алгоритм, использующий специфику задачи линейного программирования с булевыми переменными (см. § 4 гл. 6).

Витцгалл [127] перенес идею второго алгоритма Гомори на задачи с линейной целевой функцией (с требованием целочисленности переменных) и «параболическими» ограничениями, т. е. ограничениями вида

где линейно независимые формы,

4.2. Вторая из указанных выше групп методов отличается от первой тем, что в ней, напротив, максимально используется конечность проблемы, ее комбинаторный характер. Естественно, что методы этой группы по своему характеру довольно разнородны; все они в какой-то степени используют идею перебора. Впервые метод такого рода был предложен в работе Лэнд и Дойг [109] в 1960 г. Позднее Литтл и др. авторы использовали весьма близкую идею для решения задачи о бродячем торговце; их подход оказался весьма перспективным. Названный авторами «методом ветвей и границ», этот алгоритм породил ряд вариантов («метод последовательного отделения и оценивания» [57] и др.), а главное — привлек внимание к самой идее «ветвей и границ», не оцененной после работы Лэнд и Дойг. Тем самым он стимулировал разработки в этом направлении, которые в настоящее время ведутся весьма интенсивно (см. обзор Лаулера и Вуда [111]).

По существу на близких к идеям «ветвей и границ» приемах основан «аддитивный» алгоритм Балаша [47] и его модификации; основному варианту этого метода будет посвящена гл. 11. Томпсон [125] предложил алгоритм для решения линейных целочисленных задач («симплекс-метод с остановками»), близкий к алгоритму Лэнд и Дойг, но существенно более экономный в смысле требований к памяти.

Более простые эвристические соображения лежат в основе «булевого» метода, предложенного Фором и Мальгранжем [74] для решения целочисленных задач линейного программирования (см. § 1 гл. 14).

Здесь заслуживает также упоминания аппарат так называемого «псевдобулевого» программирования, разработанный Ивэнеску, Розенбергом и Рудеану. Предметом псевдобулевого программирования является решение систем уравнений или неравенств с переменными, принимающими значения 0 или 1, а также изучение соответствующих задач оптимизации — как линейных, так и нелинейных. Будучи ограничены объемом книги, мы не имеем возможности остановиться на псевдобулевом программировании, тем более, что этот подход по своему духу лежит несколько в стороне от общего направления настоящей книги. Интересующегося этими вопросами читателя отошлем к монографии [99] или к обзорной статье [100].

Локальный подход, зародившийся в дискретном анализе, был затем развит применительно к задачам дискретного программирования [8], [34], [31] (см. гл. 13).

Несколько особняком стоит оригинальный метод В. П. Черенина для решения одного класса комбинаторных задач; он будет вкратце описан в § 2 гл. 14.

4.3. Третья группа методов — это методы случайного поиска и другие приближенные методы. Возникновение приближенных методов стимулировалось разными причинами. Среди них отметим прежде всего сложность существующих точных методов и трудности в их реализации для задач больших размеров. Далее, для многих прикладных задач точные решения в значительной мере обесцениваются из-за недостаточной достоверности исходного материала. Кроме того, специфическая структура многих задач позволяет разработать достаточно мотивированные эвристические подходы, ценные своей простотой и тем самым приложимые к решению оперативных задач.

В наиболее «чистом» виде метод случайного поиска применительно к задачам целочисленного линейного программирования с булевыми переменными был развит в работе Пятецкого-Шапиро, Волконского, Левиной и Поманского [25] (см. § 1 гл. 15).

Нередко случайный поиск сочетается с так называемой локальной оптимизацией. В общих чертах эти методы можно охарактеризовать следующим образом. Производится случайный выбор некоторого допустимого плана. Определяется «окрестность» этого допустимого решения, состоящая из точек, в определенном смысле близких к исходной. Имеющееся допустимое решение улучшается на точках этой окрестности до получения «локального» оптимума. Вся эта процедура повторяется многократно, и из полученных «локальных» оптимумов выбирается наилучший по значению целевой функции. Разумеется, идея такого подхода является весьма общей и применима в принципе к любым задачам оптимального программирования. Более формальное описание мы дадим в § 2 гл. 15.

Отметим наконец, что для некоторых частных задач построены приближенные методы, вовсе не использующие случайного поиска, а учитывающие лишь специфику модели. Один такой метод, предназначенный для решения транспортной задачи с фиксированными доплатами (см. § 5 гл. 2), описан в § 1 гл. 16 (см. [11], [14]).