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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовик Задача о назначении. Задача коммивояжера

Информация:

Тип работы: Курсовик. Предмет: Математика. Добавлен: 26.5.2013. Сдан: 2011. Страниц: 33. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Введение 5
1. Основные понятия 6
1.1 Терминология 6
Эйлеровы графы 7
1.3 Кратчайшие пути 8
1.4 Деревья 9
2. Задачи о назначениях 10
2.1 Общие положения 10
2. Венгерский метод 12
3. Задача коммивояжера 15
1. Общие положения 15
5. Методы решения ЗК 17
5.1 Жадный алгоритм 17
5.2 Деревянный алгоритм 20
5.3 Метод ветвей и границ 23
Заключение 30
Литература 31


ВВЕДЕНИЕ

Данная работа посвящена изучению одним из важных задач комбинаторики - задачам о назначениях и задачам коммивояжёра, решение которых позволяет выбрать наиболее оптимальный алгоритм действий.
Так задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей, а также является частным случаем транспортной задачи (число пунктов производства равно числу пунктов назначения).
В тоже время посредством задач коммивояжёра становится возможным наиболее просто и наглядно отыскать маршрут, проходящий через указанные города хотя бы по одному разу с последующим возвратом в исходный город при выполнении условий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.).
Применение такого рода задач на практике позволяет наиболее максимально сократить, удешевить, одним словом получить желаемый результат с наименьшими затратами.
Целью данной работы является раскрытие сущности наиболее действенных методов решения поставленных задач, а также описание существующих.
Курсовая работа состоит из пяти разделов: основные понятия, задачи о назначениях, венгерский метод, задачи коммивояжера, методы решения задач коммивояжера.
В разделе «основные понятия» даются определения терминам, которые будут употребляться в последующем.
В разделе «задачи о назначениях» подробно рассматриваются общие положения и условия такого рода задач.
В разделе «венгерский метод» изучается наиболее эффективный метод решения задачи о назначении.
В следующем разделе также подробно описываются общие положения и условия задачи коммивояжёра.
В заключительном разделе «методы решения задач коммивояжера» исследуются жадный алгоритм, деревянный алгоритм, метод ветвей и границ, как основные для решения подобных задач.
Выполненная работа состоит из 30 страниц, содержит 12 рисунков и 3 таблицы.
В качестве основной литературы использовались учебники по высшей математике, освещающие главы комбинаторики:


1. ОСНОВНЫЕ ПОНЯТИЯ
1.1 Терминология
Граф G(V,E) - комбинаторный объект, состоящий из двух конечных мно­жеств: V - называемого множеством вершин и множества пар элементов из V, т.е. Е VxV, называемого множеством ребер, если пары неупорядочены, и множеством дуг, если пары упорядочены. В первом случае граф G(V,E) называется неориентированным, во втором ориентированным.
Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень d0(v) по выходящим дугам и d1(v) - по входящим.
Путь - это последовательность ребер e1, е2, ... , еm, такая, что ei, ei+1 имеют об­щую вершину. Число ребер называется длиной пути. Если ни одна из вершин не появля­ется более одного раза, то путь называется простым. Ясно, что в простом пути ни одно ребро не используется дважды.
Путь называется циклом, если его начальная вершина совпадает с конечной, простым циклом, если это не выполняется для других вершин.
В случае ориентированного графа, если путь проходит в направлении дуг, он называется ориентированным. Аналогично определяется ориентированный цикл.
Граф называется связным, если для любых двух вершин существует путь, их со­единяющий. Ориентированный граф называется сильно связным, если для любых двух вершин существует ориентированный путь, их соединяющий. Для ориентированного графа определяем скелетный граф, как неориентированный граф, полученный снятием ориентации исходного графа.
Двудольные графы. Это графы, у которых множество вершин можно
разбить на два множества V1, и V2 , и так что каждое ребро графа соединяет только некоторую вершину из V1 с некоторой вершиной из V2.
Граф единичного n-мерного куба Вn. Вершины графа - n-мерные двоичные наборы. Ребра соединяют вершины, отличающиеся одной координатой.

1.2 Эйлеровы графы
Эйлеровым путем графа G(V,E) называется путь e1,e2, ..., et такой, что каждое ребро появляется ровно 1 раз, т.е. t = | Е |. Граф G(V,E) называется эйлеровым, если он имеет замкнутый эйлеровый путь, и полуэйлеровым, если существует эйлеров путь, не являющийся замкнутым.
Теорема 1. Связный граф G является эйлеровым тогда и только тогда, когда ка­ждая вершина G имеет четную степень.
Теорема 2. Связный граф G является полуэйлеровым тогда и только тогда, когда в нем существует точно две вершины нечетной степени. Аналогичное определение можно сделать для ориентированных графов. Ориентированный эйлеров путь это ориен­тированный путь, содержащий каждую дугу точно один раз. Ориентированный граф называется эйлеровым, если в нем существует ориентированный эйлеров путь.
Теорема 3. Ориентированный граф G(V,E), у которого связан соответствующий скелетный граф, является Эйлеровым тогда и только тогда, когда либо для всех вершин v, di(v) = d0(v), либо существуют точно две вершины v1 и v2 такие, что d0(v1) = di(v1) + 1,
d0(v2) + 1 = di(v2), а для остальных вершин
dI(v) = d0(v). (3)
В первом случае любой эйлеров путь является ориентированным циклом, во втором - начинается в вершине v1 заканчивается в вершине v2
Теорема 4. Пусть G - связный граф, имеющий точно 2s > 0 вершин нечетной степени. Тогда существует s и не существует меньшего числа путей P1, ... , Ps, которые в совокупности содержат все ребра графа G точно по одному разу. При этом каждый из путей P1, ..., Ps начинается в одной нечетной вершине и кончается в другой.
Теорема 5. Пусть G - эйлеров граф. Тогда следующая процедура всегда возмож­на и приводит к построению эйлеровой цепи графа G.
Выходя из произвольной вершины, идем по ребрам графа произвольным обра­зом, соблюдая следующие правила:
стираем ребра по мере их прохождения (вместе с изолированными вершина­ми, которые при этом образуются);
на каждом этапе идем по ребру, удаление которого нарушает связность, толь­ко в том случае, когда нет других........


ЛИТЕРАТУРА

1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965, 174 с.
2. В. П. Сигорский. Математический аппарат инженера. - К., “Техніка”, 1975, 768 с.
3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. - М., Наука, 1979, 345 с.
5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. - Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.



Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.