ГЛАВА 14. НЕКОТОРЫЕ ДРУГИЕ МЕТОДЫ

Эта глава носит чисто обзорный характер. В ней приводится краткое описание еще двух методов комбинаторного типа: метода Фора и Мальгранжа для решения целочисленных задач линейного программирования и метода последовательных расчетов В. П. Черенина для решения одного класса комбинаторных задач.

§ 1. Метод Фора и Мальгранжа

1.1. В 1963 г. в заметке Фора и Мальгранжа [74] был анонсирован (на численном примере) метод решения задач линейного программирования с булевыми переменными. Свой подход они назвали «булевым методом». Затем Ле Гарф и Мальгранж [76а] распространили булев метод на общую целочисленную задачу линейного программирования. Впоследствии Фор и Мальгранж [73]

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

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

1.2. Остановимся прежде всего на первоначальном «булевом методе» Фора и Мальгранжа [74]. Рассмотрим задачу линейного программирования с булевыми переменными (все коэффициенты целые числа).

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

при условиях

Все коэффициенты не умаляя общности, можно считать неотрицательными. Выше мы уже видели, что этого всегда можно добиться, производя для отрицательных замену переменных (см., например, § 1 гл. 11).

Процесс состоит из двух этапов: поиска исходного плана и его улучшения. На первом этапе ищется произвольный план, удовлетворяющий (1.2) — (1.3). Для этого все коэффициенты также превращаются в неотрицательные: если некоторое то вместо ограничение вводится переменная Далее коэффициенты целевой функции располагаются в порядке убывания их величин. Рассматривается максимальный коэффициент и переменной придается значение 1 (или, что равносильно, переменной придается значение 0); после этого исключается из ограничений

(1.2), а правые их части заменяются на Аналогичная операция проделывается для следующего по величине Если на шаге условия (1.2) нарушаются как при так и при то пересматривается предыдущий выбор. В конечном счете получаем некоторый план (либо устанавливаем неразрешимость задачи).

На втором этапе значение пытаются улучшить, присоединяя к исходным ограничениям задачи новое ограничение

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

и снова повторяется процесс улучшения.

1.3. Намеченное в статье Фора и Мальгранжа [74] обобщение «булевого метода» на общую задачу целочисленного линейного программирования было затем более подробно и более формально описано Ле Гарфом и Мальгранжем [76а]. Рассматривается задача максимизации (1.1) при условиях (1.2) и

Кроме того, считается, что переменные ограничены сверху:

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

Для каждого легко найти такое при котором Тем самым каждую переменную можно представить в виде двоичного разложения

где могут принимать значения или 1. Таким образом, будет означать наличие «веса» в значении его отсутствие.

Общая схема метода не отличается от схемы описанного выше «булевого метода»: на первом этапе ищут исходный план, а на втором его пытаются улучшить.

Не умаляя общности, считаем, что:

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

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

где определяется из условия

Тогда верхняя граница заменяется на

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

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

Второй этап — улучшение полученного плана как и в булевом методе, проводится путем присоединения к исходным ограничениям дополнительного требования типа (1.5). Расширив таким путем систему ограничений, пытаются удовлетворить ей, возвращаясь к последнему уровню выбора и полагая вместо имевшего место ранее

План X, улучшить который окажется невозможно, и будет оптимальным. В случае неединственности оптимального плана метод дает возможность получить все эквивалентные планы. Это делается путем присоединения к окончательной таблице ограничения

и повторения второго этапа.

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

Ле Гарф и Мальгранж [76а] сообщают также о первоначальном вычислительном опыте с этим методом.

Например, задача размера была решена за 20 сек.; время по методу Гомори для той же задачи составило около 30 сек. (тип машины не указан). Однако эффективность метода быстро убывает с ростом числа переменных и с увеличением их верхних границ Так, одну задачу размера 10X20 не удалось решить за приемлемое время.

1.4. В последующей работе Фора и Мальгранжа [73] предлагается еще один метод решения общей задачи целочисленного линейного программирования. Построенный по описывавшейся выше двухэтапной схеме, он имеет ряд особенностей, сближающих его, например, с методом Лэнд и Дойг (см. § 2 гл. 10). Главная из этих особенностей заключается в том, что в этом методе используется решение задачи линейного программирования отвечающей исходной задаче (1.1), (1.2), (1.3). Основным приемом здесь также является обращение верхних границ переменных в нуль (или сближение верхних и нижних границ). При этом для пересчета границ переменных используется информация, заключенная в полной симплексной таблице (см. § 5 гл. 4) задачи .

Сведения о машинных экспериментах с этим методом отсутствуют.