Препроцессинг в современных программных системах решения задач дискретной оптимизации.

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

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

7.2. Приближенные алгоритмы.

7.2.1. Метод вектора спада для приближенного решения задач дискретной оптимизации.

Рассмотрим из приближенных методов ‑ метод вектора спада, разработанный И. В. Сергиенко в середине 60-х годов прошлого века. В общем случае этот метод позволяет находить локальный минимум целевой функции задачи ДО, однако, если она имеет соответствующие свойства выпуклости, то он приводит к определению глобального минимума.

Рассмотрим задачу ЦЛП вида:

(7.9)

при ограничениях:

(7.10)

(7.11)

— целые (7.12)

Введем необходимые понятия. Пусть М ‑ некоторое дискретное точечное пространство. ‑ множество допустимых решений задачи ЦЛП (7.9) - (7.12). Введем метрику в пространстве М, т.е. функцию, которая определяет расстояние между произвольными точками этого пространства Х и Y. Метрика должна удовлетворять трем аксиомам:

1) аксиоме тождества: при условии, что X = Y;

2) аксиоме симметрии: ;

3) аксиоме неравенства треугольника

Метрику можно определять по-разному. В частности, в прямоугольной декартовой системе координат это может быть , где - соответственно координаты точек X и Y в пространстве М.

Пусть ‑ некоторое допустимое решение задачи ЦЛП. Для некоторого числа множество всех точек, для которых выполняется неравенство называется открытой окрестностью с центром в точке и радиусом r, а множество всех точек для которых выполняется неравенство называется замкнутой окрестностью.

Определим некоторое окрестность точки с радиусом r₁ такую, чтобы кроме решения, она содержала бы и другие решения задачи, для чего радиус r₁ должен быть не меньше некоторой величины R. Далее будем рассматривать только указанные окрестности решений задачи. Определим функцию следующим образом:

Назовем вектором спада функции в некоторой окрестности точки , являющейся одним из допустимых решений задачи ЦЛП, вектор, компонентами которого являются величины , где - решения задачи, принадлежащих окрестности .

При неотрицательности всех компонент вектора спада в окрестности точки получим для любого значения

т.е. точка является точкой локального минимума функции в выделенной окрестности , то есть:

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

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

Как правило, на каждом шаге алгоритма (т.е. для каждой новой окрестности) не нужно вычислять все компоненты вектора спада, а лишь часть из них, что дает существенный выигрыш в объеме и продолжительности вычислений.

Приведем один из возможных алгоритмов реализации метода вектора спада.

1. Выбрать начальную точку Х₀ и радиус окрестности R так, чтобы точка Х₀ была допустимым решением задачи ЦЛП а окрестность содержала также другие допустимые решения задачи. Этот выбор может осуществляться случайно с проверкой выполнения указанных условий.

2. Определяются компоненты вектора спада в выбранном окрестности. Если все его компоненты неотрицательны, то локальный минимум найден (т.е. задача решена и оптимальным целочисленным решением является ).

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

4. Возвращаемся к пункту 2. Процесс продолжаем, пока для некоторого все компоненты соответствующего вектора спада не будут неотрицательными.

Пример. Решим задачу целочисленной оптимизации

,

;

;

,

и — целые.

Решение. Пусть Выбранная точка является допустимым решением задачи, поскольку удовлетворяет всем ограничениям и условию целочисленности, а окрестность выбранного радиуса содержит другие решения задачи, например, точку

Определяем точки, принадлежащие рассматриваемом окрестности (рис. 7.1). Это такие три точки:

Рис. 7.1. Окрестность.

Определим компоненты вектора спада:

Наименьшей является третья компонента вектора спада, следовательно, соответствующая ей точка становится центром следующей окрестности . Радиус

В новую окрестность будут входить точки с координатами:

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

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

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

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