Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


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


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


1)    маршрут должен быть замкнутым, т.е. коммивояжер должен вернуться в город, из которого начал движение;


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


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


Цель задачи состоит в определении маршрута, удовлетворяющего всем условиям, с минимальными затратами на проезд по маршруту.


Метод ветвей и границ для задачи о коммивояжере — это, в сущности, практически полный перебор маршрутов (всего маршрутов (n-1)!), который оптимизируется за счет того, что при переборе вариантов по определенным признакам отсекаются с большой долей вероятности неоптимальные множества перебора. Так как количество вершин от уровня к уровню возрастает в факториальной прогрессии, то отсечение вершин верхних уровней значительно сокращает общее число перебираемых вариантов.


Алгоритм метода:


1. Все множество маршрутов разбивают на (n-1) подмножеств, каждое из которых характеризуется верхней и нижней оценками.


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


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

Скачать в pdf «Экстремальные модели менеджмента и экономики»