ВВЕДЕНИЕ - Задача коммивояжера

Данная работа посвящена теме "Задача о коммивояжере". Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда.

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

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

Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.

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

Похожие статьи

• ВВЕДЕНИЕ - Задачи линейного програмирования

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

• ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера

  Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...

• Введение - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов

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

• Введение - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

  Изучение теоретических вопросов анализа чувствительности оптимального решения ЗЛП к вариациям некоторых параметров задачи и введению нового ограничения....

• Введение - Решение оптимизационных экономических задач методами линейного программирования

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

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

  В настоящей работе предлагается классификация задач многокритериальной оценки эффективности систем различного назначения. В качестве факторов...

• Введение - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

  Оптимизация инвестиционного портфеля (ИП) [Дубровин и др., 2008], [Мищенко и др., 2002], [Серов, 2000] является одной из важных экономических задач,...

• Анализ чувствительности оптимального решения ЗЛП к введению нового ограничения - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

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

• Анализ чувствительности оптимального решения ЗЛП к вариациям коэффициентов целевой функции., Графический способ анализа чувствительности оптимального решения к вариациям C[j - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

  Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...

• ЗАКЛЮЧЕНИЕ, СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ - Задача коммивояжера

  Задача коммивояжер граф моделирование В данной курсовой работе был рассмотрен один из видов задач теории графов и сетевого моделирования "Задачу о...

• Введение - Постановка задачи прогнозирования продуктивности агроэкосистем

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

• Введение - Экономико-математические методы

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

• Анализ чувствительности оптимального решения к вариациям правых частей ограничений - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

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

• Введение - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

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

• Введение - Приложение интегрального и дифференциального исчисления к решению прикладных задач

  Целью данной курсовой работы является самостоятельное изучение следующих разделов высшей математики: задачи линейного программирования (симплексный и...

• Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах

  Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...

• РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера

  Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...

• Введение - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

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

• Обслуживание с ожиданием - Задачи линейного програмирования

  СМО с ожиданием распространены наиболее широко. Их можно разбить на 2 большие группы - Разомкнутые и Замкнутые . Эти системы определяют так же, как...

• Задачи повышения экономической эффективности производства - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

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

• Графическое решение задачи нелинейного программирования - Методика решения двойственных задач линейного программирования

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

• Нелинейное программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

  Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...

• Изложение теоретических аспектов исследования, Динамическое программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

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

• Линейное программирование, Общая задача линейного программирования - Экономико-математические методы

  Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...

• Общая постановка задачи исследования операций - Экономико-математические методы

  Все факторы, входящие в описание операции, можно разделить на две группы: Постоянные факторы (условия проведения операции), на которые мы влиять не...

• Введение - Оптимизация управлением производства на примере ОАО "Днепропетровский стрелочный завод"

  Современный этап развития экономики характеризуется переходом предприятий на новые условия хозяйствования, необходимостью развития перспективных...

• РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера

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

• Введение. Постановка задачи - Задача исследования итогового ранжирования мнений группы экспертов с помощью медианы кемени

  Экспертные процедуры применяются во многих областях деятельности [1 - 3]. К таким областям относятся прежде всего менеджмент (особенно производственный...

• Введение - Моделирование временного тренда среднегодовой численности занятого населения

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

• ВВЕДЕНИЕ - Понятие и виды логистической системы

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

• Формализация решения многоцелевых задач при управлении научной деятельностью - Формализация решения многоцелевых задач при управлении научной деятельностью

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

• Основные задачи анализа временных рядов - Динамические ряды

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

• Основные методы решения задач, Решение задачи с помощью математического аппарата - Формирование оптимального штата фирмы

  Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....

• Введение - Формирование оптимальной производственной программы предприятия

  Цель курсовой работы - обеспечение достаточно глубокого усвоения учебного материала по курсу "Планирование на предприятии", а также приобретение...

• Классификация экономико-математических методов и моделей в управлении предприятием и их задачи в повышении экономической эффективности производства, Основные понятия теории экономико-математического моделирования, Кибернетический подход к исследованию экономико-математических систем - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...

• Задачи регрессионного анализа, Метод наименьших квадратов - Выполнение регрессионного и дисперсионного анализа

  Регрессия -- зависимость среднего значения какой-либо величины от некоторой другой величины или от нескольких величин. Задача регрессионного анализа...

• Транспортная задача - Экономико-математические методы

  Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ...

• Теория игр - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

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

• Задачи, связанные с поиском гамильтоновых циклов - Гамильтоновы циклы

  В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат...

• Основные понятия и определения исследования операций, Цель и задачи исследования операций - Экономико-математические методы

  Цель и задачи исследования операций Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее...

ВВЕДЕНИЕ - Задача коммивояжера

Предыдущая | Следующая