СодержаниеВведение 3
Глава 1. Теоретические аспекты метода графов 4
1.1. Классификация методов исследования систем управления 4
1.2. Основные понятия метода графов 5
1.3. Нахождение кратчайшего пути в графе 9
Глава 2. Решение практических задач методом графов 13
2.1. Сферы применения метода графов 13
2.2. Постановка и методы решения транспортной задачи 18
2.3. Пример решения транспортной задачи 20
Заключение 26
Литература 28ВведениеВ последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.
Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться.
Зарождение теории графов можно отнести к концу XVIII в., к работам А.Эйлера, посвященным решению математич. развлекательных задач. В ХХ в. толчком к развитию теории графов служат задачи, возникающие в физике, химии, электротехнике, биологии, экономике, социологии, а также во многих математич. дисциплинах. Современная теория графов включает различные подходы к решению соответствующих задач: комбинаторно-логические, геометрические (типологич.), теоретико-вероятностные.
Цель курсовой работы – исследовать теоретические аспекты метода графов и изучить примеры решения задач методом графов.
Задачи курсовой работы:
- исследование классификации и основных понятий метода графов;
- рассмотрение нахождения кратчайшего пути в графе;
- решение практических задач методом графов.ЗаключениеТеория графов это область дискретной математики, особенностью к-рой является геометрич. подход к изучению объектов. Основной объект Т.г. граф. Граф (G,(V,Е)) задается множеством вершин (V) и набором (Е) неупорядоченных и упорядоченных пар вершин. Неупорядоченная пара вершин наз. ребром, упорядоченная дугой. Граф, содержащий только ребра, наз. неориентированным; граф, содержащий только дуги, ориентированным. Пара вершин может соединяться двумя и более ребрами (дугами одного направления; направление дуги отвечает упорядоченности соответствующей пары вершин).
Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: \"структуры\" в гражданском строительстве, \"сети\" – в электронике, \"социограммы\" – в социологии и экономике, \"молекулярные структуры\" – в химии, \"дорожные карты\", электрические или газовые распределительные сети и т. д.
Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
Петля – это дуга, начальная и конечная вершина которой совпадают.
Степень вершин – это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Путь в ориентированном графе – это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Маршрут в графе – путь, ориентацией дуг которого можно пренебречь. Цепь – маршрут, в котором все ребра попарно различны. Цикл – замкнутый маршрут, являющийся цепью.
Подграф графа – это граф, являющийся подмоделью исходного графа. Т. е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Граф называется связным, если любая пара его вершин связана.
Дерево – это связный граф без циклов.Литература1. Бродецкий Г.Л. Системная аналитика принятия решений в исследованиях логистики. – М.: Изд. ГУ-ВШЭ, 2004. 170с.
2. Букан Д., Кенигсберг Э. Научное управление запасами - М. : Наука, 1967
3. Вентцель Е.С. Исследование операций. – М.: Высшая школа, 2006.
4. Глущенко В.В., Глущенко И.И. Исследование систем управления: Социологические и экономические исследования, прогнозные и плановые исследования, экспериментальные исследования. - Московская область: Крылья, 2005. - 416 с.
5. Игнатьева А.В., Максимцов М.М. Исследование систем управления: Учебное пособие. - М.: Юнити - Дана, 2005. - 156.
6. Исследование операций в экономике /Под ред. Кремер. – М.: ЮНИТИ, 2007.
7. Красс М.С. Математика для экономических специальностей. – М.: ИНФРА-М, 2006.
8. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. – М.: Дело, 2007.
9. Кремер Н.Ш. и др. Высшая математика для экономистов. – М.: ЮНИТИ, 2005.
10. Макаров С.И. Математика для экономистов. – Самара: СГЭА, 2002.
11. Малин А.С., Мухин В.И. Исследование систем управления. Учебник
12. Малыхин В.И. Математика в экономике – М.: ИНФРА-М, 2002.
13. Математические методы в теории игр, программировании и экономике.- М.: Мир, 1964
14. Прабху Н. Стохастические процессы теории управления запасами. - М. : Мир, 1984
15. Райншке К. Ушаков И. Оценка надежности систем с использованием графов. - М. : Радиосвязь, 1988
16. Рубальский Г.Б. Управление запасами при случайном спросе. - М. : Сов. Радио, 1977
17. Хэмди А. Таха Введение в исследование операций. – М., СПб., Киев: Издательский дом «Вильямс», 2001.
18. Экономико-математические методы в снабжении./Под ред. проф. В.М. Лагутина. - М. Экономика, 1971
|
|
