Построение кольцевых маршрутов

Коммерческая деятельность обычно связана с командировками, поездками по городам для заключения сделок. Расстояния между любой парой множества из п городов известны и составляют . Если прямого маршрута между городами i и j не существует, то допускают, что . Коммерсант, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы наименьшей. Таким образом, нам приходиться обращаться к данному методу.

Содержательная постановка задачи

Метод ветвей и границ (англ. branch and bound) - общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации . По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

Математическая постановка задачи

Экономико-математическая постановка этой задачи может быть представлена, как задача целочисленного линейного программирования.

Переменные определим следующим образом: , если коммивояжер переезжает из города i в городу j в противном случае .

Задача заключается в определении матрицы целых неотрицательных значений переменных , минимизирующих целевую функцию вида:

) для въезда в город только один раз

) для выезда из города только один раз

Описание метода решения

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

) чтобы маршрут включал только один въезд в каждый город;

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

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

Таким образом, формируется экономный вариант маршрута в виде кольца.

Пример решения задачи

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

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

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

Заключение

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

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

В своё время каждый из этих методов очень своеобразен и отличается от другого на него похожего. Вот например в методе АВС-анализа для того чтобы прийти к ожидаемому результату, нам необходимо построить таблицу в Microsoft Office Excel «вбить» туда нужные нам формулы и мы получим ответ. В своё время каждый из этих методов очень своеобразен и отличается от другого на него похожего. А если рассматривать межотраслевой балансовый метод, то там всё делается вручную, мы строим деревья затрат на единицу какой-либо продукции и дальше уже по заданным нам формулам рассчитываем и получаем ответ.

Перейти на страницу: 1 2

Другое по теме

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

Разделы