Содержание

ВВЕДЕНИЕ…………………………………………………………………………3

1. ОСОБЕННОСТИ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА……………5

1.1 Задача коммивояжера: сущность и применение на практике…………...5

1.2 Методы решения задачи коммивояжера……………………………………7

2. Решение задачи коммивояжера при помощи надстройки MS Excel «Поиск решения»…………………………12

Заключение...…………………………………………………………………17

Список использованной литературы…………………………...18

Введение

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

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

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем, Я. Бернулли, Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций.

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

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

В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

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

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

Целью данной курсовой работы является постановка задачи коммивояжера и ее решение методом полного перебора с использованием надстройки MS Excel «Поиск решения».

Объектом исследования в курсовой работе выступает программа, реализующая один из методов решения задачи коммивояжера - надстройка MS Excel «Поиск решения».

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

Для достижения поставленной цели необходимо решить следующие задачи:

• изучить понятие и особенности задачи коммивояжера;

• ознакомиться с практическим применением задачи коммивояжера;

• рассмотреть методы решения задачи коммивояжера;

• получить представление о назначении надстройки MS Excel «Поиск решения»;

• сформулировать задачу коммивояжера и решить ее при помощи надстройки MS Excel «Поиск решения».