ГЛАВА V. ОПТИМИЗАЦИЯ

§ 49. Введение

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

В основе почти всех комбинаторных методов оптимизации лежит следующий принцип. Множество всех решений разбивается некоторым образом на два подмножества: подмножество, содержащее все оптимальные решения, и подмножество, не содержащее их. Если первое из подмножеств не есть оптимальное, то стремятся получать подобные разбиения, в которых подмножества, содержащие все оптимальные решения, имеют все меньшую мощность. Действуют так до тех пор, пока не приходят к оптимальному подмножеству. На этом же принципе основаны также некоторые способы, позволяющие получить по крайней мере одно оптимальное решение.

Вопросами оптимизации стали интенсивно заниматься лишь в последнее время.

В педагогических целях мы получаем алгоритмы, позволяющие действовать вручную; некоторые из них непосредственно, а другие — после соответствующей модификации могут быть использованы при вычислениях на ЭВМ. Чтобы решать задачи с большим объемом вычислений в приемлемое время, многие алгоритмы требуют дальнейшего усовершенствования.