Метод лексикографического перебора

Этот метод основан на процедуре перебора отдельных точек области возможных решений задачи, упорядоченных по быстроте изменения переменных. Такое упорядочение подобно упорядочению слов в словаре. Чем обусловлено название метода?

В процессе перебора каждая переменная хi, где хi (i=1,n) принимает последовательность начиная с хi^min и заканчивая хi^max.

Прежде чем значение хi увеличить на 1 необходимо перебрать все возможные комбинации переменных от хi+1,.. хn при этом каждая из них должна пробежать последовательно все свои значения от наименьшего до наибольшего.

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

n

Σ cixi<z(xдоп)

і=1

z(xдоп)-значение целевой функции для допустимого решения.

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

n

Σ cixi≥z(xдоп) то переходят к следующему решению, обосновывается это тем, что после

і=1

нахождения допустимого решения в дальнейшем, с точки зрения оптимизационных задач имеет смысл рассматривать лишь те значения х для которых значения целевой функции меньше z(xдоп)

Если в ходе решения задачи найдено более лучшее решение, т.е. такое для которого

z(x ^ٰдоп)< z(xдоп) то правая часть фильтрующего ограничения заменяется на значение z(x ^ٰдоп)

Следовательно, ограничение становится наиболее жестким.

Вторая возможность которая обеспечивает сокращение объема вычислений – это использование упорядочивания переменных по быстроте изменения соответствия со значениями коэффициента целевой функции.

Самой быстроизменяющейся будет та переменная, которой соответствует значение коэффициента в целевой функции.

При таком упорядочении в процессе перебора раньше будут рассмотрены решения с меньшими значениями целевой функции. Если среди них найдется допустимое решение, то в более ранний момент будет найдено более жесткое фильтрующее ограничение, что приведет к дополнительному сокращению объема вычислений.

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

По аналогии с фильтрующим ограничением применение этого правила дает сокращение объема вычислений.