§ 4. Пример и заключительные замечания

4.1. Проиллюстрируем ход вычислений в описанном алгоритме на следующем небольшом примере. Минимизировать

при условиях

Произведем замену переменных

Умножим первое из неравенств (4.2) на — 1 и введем свободные переменные Задача (4.1) -(4.3) при этом приводится к следующему виду. Минимизировать

при условиях

Процесс начинается с плана Все вычисления удобно свести в таблицу;

(см. скан)

Для плана имеем и

Итерация 1.

Шаг 1. Просматриваем Имеем

Шаг 2. Образуем, согласно (3.12), множество Имеем (см. 1-ю строку таблицы):

Здесь

Шаг 3. Для проверяем неравенства (3.15):

Имеем (строка 2). Получено строгое неравенство Согласно (3.8), находим для

(Напоминаем, что множества находятся согласно

Имеем «Вычеркиваем» и переходим к шагу 8.

Шаг 8. Полагаем Имеем:

Итерация 2.

Шаг 1. Просматриваем . Видим, что

Шаг 2. Образуем множество Имеем Таким образом,

так что

Шаг 3. Проверяем неравенства (3.15) для 1 (строка 8). Имеем

Получено строгое неравенство Находим для

Имеем Вычеркиваем переходим к шагу 8,

Шаг 8. Полагаем Имеем:

Итерация 3.

Шаг 1. Просматриваем для Видим, что все Полагаем и образуем, согласно (3.13), множества для По определению

где Далее

так что Аналогично этому Вычеркиваем для т. е. и и переходим к шагу 5.

Шаг 5. Образуем, согласно (3.14), множество

Здесь Переходим к шагу 6.

Шаг 6. Проверяем неравенства (3.20) при

Так как (3.20) не выполнено вычеркиваем для т. е. и возвращаемся к шагу Рассмотрим множество

Снова имеем Возвращаемся к шагу 6.

Шаг 6. Проверяем неравенства (3.20) при

(3.20) не выполнено Вычеркиваем для т. е.

Неравенства (3.20) не выполняются ни при одном для которого Поэтому процесс окончен. Оптимальный план получен:

Возвращаясь теперь к переменным получаем оптимальный план исходной задачи

4.2. В рассмотренном примере имеется 25 планов. Их перебор, как всегда, удобно представить графически в виде дерева, вершина которого отвечает нулевому начальному плану.

Рис. 11.4.1.

Узлы дерева расположены в пяти «уровнях»; на уровне переменной последовательно придаются значения и 1. Все узлы, лежащие на ветвях, идущих влево вниз, изображают один и тот же план; узлы же, лежащие на ветвях, идущих вправо вниз, отвечают различным планам (рис. 11.4.1).

Полный перебор всех планов отвечает просмотру всех ветвей этого дерева. Аддитивный алгоритм дает возможность получения оптимального плана после

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

Рис. 11.4.1 соответствует рассмотренному выше численному примеру. В нем просматривались лишь ветви, изображенные жирными линиями. Именно, были проверены лишь следующие три плана:

последний из которых оказался оптимальным.

4.3. Вычислительный опыт, подтверждающий эффективность аддитивного алгоритма, пока сравнительно небогат. Сам Балаш проводил ручной счет для нескольких примеров, максимальный из которых имел размеры 12X15; он был решен за 22 итерации (см. Балаш [47]). Первое сообщение о машинной реализации аддитивного алгоритма принадлежит Фримэну [75а]. Эксперименты велись в корпорации РЭНД на машине IBM-7044. Задача размерами 6X20 потребовала 2 мин. машинного времени; задача 50X15 — 2,5 мин. Для задачи размерами 31X31 за 10 мин. был получен план с рекордом, равным 19 (точное значение оптимума равнялось 18).

Отчет о вычислительном опыте с алгоритмом Балаша содержится также в заметке Флейшмана [74а]. Эксперименты проводились в Вычислительном центре ФРГ (Дармштадт) на машине IBM-7094. Максимальный размер решавшихся задач составлял 37X159; задача была решена за 2,45 мин. и потребовала 1622 итерации. Максимальное время счета (30,65 мин.) и максимальное количество итераций (80 417) было зафиксировано для задачи размерами 11X80. Задача размерами 46X90 не была решена за 110 000 итераций (машинное время — 90 мин.).

Численные эксперименты с аддитивным алгоритмом позволяют сделать некоторые качественные выводы. Алгоритм работает быстро и надежно для задач среднего размера (до 30 переменных). Судя по всему, он

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

4.4. Недавно в статье Джеффриона [80] был предложен метод «неявного перебора», который является по существу вариантом аддитивного алгоритма. Наконец, в последней работе Балаша [48] развивается «метод фильтра», позволяющий ускорить сходимость аддитивного алгоритма. Ограниченный объем книги не позволяет здесь остановиться на этих интересных вопросах.