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

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

Все переменные исходной задачи упорядочиваются по быстроте изменения. Если никаких дополнительных соображений при этом не использовать, то этот порядок будет соответствовать естественному порядку нумерации переменных исходной формализованной записи оптимизационной задачи: самой медленноменяющейся переменной будет x[1], а самой быстроменяющейся - x[n].

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

Когда все ограничения выполнены, то решением будет последний план, который определял фильтр.

Замечание1. Метод записан для задачи С очевидными изменениями метод применим для задачи на минимум.

Замечание 2 Метод применим не только для задач с булевыми переменными, но и для более общих целочисленных задач. При этом значения переменных меняются от заданного до заданного .

Дата добавления: 2014-01-07