Классификация методов решения дискретных задач

Методы дискретной оптимизации и соответствующие алгоритмы по основной идее каждого из них можно разделить на три большие группы:

  • - отсечения;
  • - комбинаторные (переборные);
  • - приближённые.

Исторически исследованиям задач дискретной оптимизации предшествовало развитие теории и методов линейного программирования, в частности создание Дж. Данцигом симплекс- метода как универсального метода решения линейных задач. Естественны были попытки представить исходную дискретную задачу как задачу целочисленного линейного программирования и свести её решение к использованию уже имевшихся методов решения непрерывных линейных задач, в частности двойственного симплекс- метода [2,10,16]. Однако простое округление получаемых значений переменных приемлемо далеко не во всех случаях. Поэтому была разработана следующая более сложная процедура решения целочисленной задачи линейного программирования.

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

  • - полученное нецелочисленное решение ему не удовлетворяет;
  • - все допустимые целочисленные решения удовлетворяют этому ограничению.

Другими словами, отсекается ненужное решение непрерывной задачи и исключается возможность потери решения целочисленной задачи. Снова решается задача без условия целочисленности. Процесс продолжается до тех пор, пока оптимальное решение не окажется целочисленным. Такая процедура была впервые реализована в алгоритме Р. Гомори [1,20,21], который сформулировал универсальное правило формирования отсечений и доказал конечность процесса отсечений. Характерно, что количество шагов существенно зависит не только от размерности задачи, но и от конкретных числовых данных. Были обнаружены задачи относительно небольшой размерности, решение которых требует больших затрат машинного времени.

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

Среди комбинаторных методов наибольший интерес представляют метод ветвей и границ [20,21] и метод динамического программирования [3,4], а также их комбинация [1,36].

Приближённые методы основаны на отказе от поиска точного решения и введении дополнительного условия прекращения процесса оптимизации. Вместо поиска x*eD, для которого F(x") минимальна, ставится задача поиска такого x°gD, что F(x0)- F(x*)< s или (F(x0)- F(x*))/ F(x*)< e. Здесь F(x*)^0; e>0.

Другими словами, поиск прекращается если абсолютная или относительная ошибка не превышают заданного значения е. С практической точки зрения эти условия, как правило, равноценны, но с точки зрения теории для многих задач второе из них приводит к полиномиальному росту объёма вычислений с увеличением размерности задачи, тогда как первое сохраняет экспоненциальный рост [23].

Основанием для перехода к приближённым методам являются:

  • - экспоненциальный рост объёма вычислений с ростом размерности задач. Это явление получило название «проклятие размерности»;
  • - для точного решения задач большой размерности нужны мощные компьютеры, а приближённые решения можно получить на имеющихся;
  • - в прикладных задачах, как уже отмечалось, математическая модель обычно является лишь приближённой формализацией исходной задачи и точное решение представляет скорее теоретический интерес;
  • - исходные данные в прикладной задаче известны, как правило, приближённо, соответственно приближёнными являются параметры модели, и поиск точного решения не оправдан.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >