ГЛАВА 9. ОБ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ МЕТОДА ОТСЕЧЕНИЯ

Глава носит в значительной мере обзорный характер. Об эффективности алгоритмов метода отсечения здесь говорится применительно к задаче целочисленного линейного программирования.

В § 1 ставится задача исследования эффективности. В § 2 кратко изложены некоторые результаты вычислительных экспериментов. В § 3 даны некоторые выводы.

§ 1. Проблема эффективности

1.1. Какова эффективность некоторого алгоритма метода отсечения? Идеальным ответом на этот вопрос была бы формула, дающая количество арифметических операций (необходимых для решения задачи) как функцию от параметров задачи и позволяющая предсказать статистику вычислительного эксперимента.

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

1.2. Вкратце остановимся на эффективности алгоритмов это будет полезно для сравнения с ЦЛП. Гасс (см. [77], стр. 65 русского перевода) приводит следующую экспериментальную оценку для числа итераций метода последовательного улучшения плана. Пусть количество уравнений для задачи ЛП в каноническом виде (гл. 4, задача Тогда для подавляющего большинства задач ЛП

Оценка (1.1) указывает на высокую эффективность метода последовательного улучшения плана.

Следует отметить, что оценка (1.1) отнюдь не очевидна. Она существенно лучше, чем строгая оценка сверху для числа вершин V многогранного множества планов (число V заведомо превышает 5)

Неочевидность оценки (1.1) подчеркивает следующий любопытный эпизод из истории создания метода последовательного улучшения плана (симплекс-метода). «Простая идея движения по ребрам выпуклого многогранника от одной вершины к другой (чем и характеризуется симплекс-метод) ранее была интуитивно отвергнута как неэффективная. Однако в другой геометрии она оказалась полезной и по счастливой случайности была проверена и принята» (см. Данциг [66], стр. 31 русского перевода).

1.3. Теоретическое обоснование эффективности метода последовательного улучшения плана (и других конечных методов ЛП) оказалось трудной задачей. Эта задача пока не решена; не удалось пока решить и некоторые близкие по проблематике задачи, например задачу Гирша (см. Данциг [66], задача 13, стр. 168 русского перевода). Работа Филипповича и Козлова [28], посвященная вероятностной оценке числа итераций в некоторых методах ЛП, основана на недоказанном предположении. Некоторое продвижение на пути к строгому обоснованию эффективности метода последовательного улучшения плана осуществил Кли [104], [105].

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

1.4. Другое положение сложилось в целочисленном линейном программировании. Теоретическое исследование эффективности алгоритмов метода отсечения также отсутствует. Однако накопленный опыт вычислений

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