Практическое применение решения задачи Коммивояжера

A) Постановка задачи.

b) Различные интерпретации задачи.

3. Метод динамического программирования в решении задач дискретной оптимизации…………………………….………….6

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

a) Классическая задача коммивояжера.

b) Задача коммивояжера с минимаксным критерием.

c) Бикритериальная задача коммивояжера.

5. Метод ветвей и границ в решении задач дискретной оптимизации……………………………………………………12

6. Решение задачи коммивояжера методом динамического программирования……………………………………………..14

a) Классическая задача коммивояжера.

b) Задача коммивояжера с минимаксным критерием.

c) Бикритериальная задача коммивояжера.

7. Решение задачи коммивояжера методом ветвей и границ…18

a) Классическая задача коммивояжера.

b) Бикритериальная задача коммивояжера.

8. Список литературы……………………………………………..22
Введение

Наиболее ярким и характерным примером применения задачи "О коммивояжере" стала оптимизация операций на конвейере. В 1984 году, после того как был проведен анализ последовательности и временных затрат на операции на конвейерах заводов компании "General Motors" и приняты рекомендованные меры, удалось увеличить общую производительность почти на 13% при неизменном числе рабочих и том же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые в то время являлись одними из самых производительных систем в мире. Просчет и оптимизация 200 основных и 87 вспомогательных операций занял около 230 часов. Считается, что это было первое коммерческое применение компьютерных технологий в области управления производством в целом.

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

Практическое применение решения задачи Коммивояжера

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

Что представляет собой задача коммивояжера вкратце в условиях современного города? Например: поездка по магазинам бытовой электроники. Покупатель выезжает из дома, объезжает 5 магазинов и возвращается обратно. Как правило, человек в этом случае интуитивно использует «жадный» алгоритм, то есть, первая поездка к ближайшему от дома магазину, от него к ближайшему следующему и т.д. Но отметим, что общее количество вариантом, которыми можно переместиться между магазинами составляет 5! равный 120 вариантам, и «жадный» алгоритм может проиграть в расстоянии в среднем 10%-20% оптимальному. Всего 120 вариантов для скромного набора магазинов, тогда как в случае с 10-ю магазинами цифра взлетает до 3.628.800

На иллюстрации: оптимальный маршрут по 20-ти городам Италии.

Количество вариантов полного перебора = (20-1)! = 121 645 100 408 832 000

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

1. Доставка продуктов в магазины с оптового склада производителя (в этом случае может быть более уместна постановка транспортной задачи — доставка в несколько магазинов с нескольких складов).

2. Доставка бутилированной воды

3. Мониторинг объектов (базовые станции сотовых операторов, нефтяные вышки)

4. Пополнение банкоматов наличными деньгами

5.Сбор сотрудников для доставки вахтовым методом

6.Расклейка афиш

7. И многие другие...

Дата добавления: 2015-10-26