kursovik (664074)

Файл №664074 kursovik (Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог)kursovik (664074)2016-07-31СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла


Введение

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

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

Наиболее распространено понимание системы как совокупность элементов, находящихся во взаимодействии и образующих некоторую целостность, единство. Важным качеством любой системы является эмерджентность – наличие таких свойств, которые не присущи ни одному из элементов, входящих в систему. Поэтому при изучении систем недостаточно пользоваться методом их расчленения на элементы с последующим изучением этих элементов в отдельности. Одна из трудностей экономических исследований – в том, что почти не существует экономических объектов, которые можно было бы рассматривать как отдельные (внесистемные) элементы.

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

Сложность экономики иногда рассматривалась как обоснование невозможности ее моделирования, изучение средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и любой сложности. И как раз сложные объекты представляют собой наибольший интерес для моделирования; именно здесь моделирование может дать результаты, которые нельзя получить другими способами исследования.

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

1. Краткое описание модели поставленной задачи

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии),также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

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

Сетевые модели используются для решения следующих задач:

  1. проектирование газопровода;

  2. нахождение кратчайшего маршрута между городами по сети дорог;

  3. определение максимальной пропускной способности при транспортировки нефти;

  4. составление временных графиков работ и др.

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

1) алгоритм построения минимального основного дерева. Предполагает соединение всех узлов сети с помощью путей наименьшей длины.

2) алгоритм Дейкстры. Используется для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети

3) алгоритм Флойда. Используется для нахождения оптимального маршрута между любыми двумя узлами сети.

Основные определения

Сеть состоит из множества улов, связанных дугами (или ребрами). Таким образом, сеть описывается парой множеств (N,A), где N – множество узлов, а A – множество ребер. Например, сеть, показанная на рис. 1, описывается след образом.

N = {1, 2, 3, 4, 5},

A = {(1, 3), (1, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}.


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

Ребро называется направленным, или ориентированным (и в этом случае ребро будем называть дугой), если в одном направлении возможен только положительный поток, а в противоположном – только нулевой. В ориентированной сети все ребра ориентированы.

Путем называется последовательность различных ребер, соединяющих два узла, независимо от направления от направления потока в каждом ребре. Путь формирует цикл, если начальный и конечный узлы совпадают. Например, на рис. 2 ребра (2, 3), (3, 4) и (4, 2) составляют цикл. Ориентированный цикл – это цикл, в котором все дуги ориентированы в определенном направлении.

Связная сеть – такая сеть, у которой любые два узла связаны по крайней мере одним путем. На рис. 1 показан именно такой тип сети и не имеющий циклов. Остовное дерево – это дерево, содержащая все узлы сети. На рис. 2 показаны дерево и Остовное дерево для сети из рис. 1.


2. Математическая формулировка задачи, обоснование

Алгоритм Флойда

Алгоритм Флойда находит кратчайший путь между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i ,j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i ,j), и равен бесконечности в противном случае.

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 3). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i → k путем i → j → k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.


Алгоритм Флойда требует выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояний D0 и матрицу последовательности

узлов S0. Диагональные элементы обеих матриц помечаются знаком “ – “,

показывающим, что эти элементы в вычислениях не участвуют. Полагаем k=1.

Основной шаг. Задаем строку k и столбец k как ведущую строку и ведущий столбец.

Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство

dij + djk < dik (i ≠k, j≠k, i ≠j),

тогда выполняем следующие действия :

  1. создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dij + djk, (рис. 4)

  2. создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k=k+1 и повторяют шаг k. (рис. 5)

d12

d1j

d1n

d21

d2i

d2n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

di1

di2

dij

din

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

dn1

dn2

dnj


рис. 4



2

j

n

1

j

n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1

2

j

n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1

2

j


рис. 5


После реализации n шагов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам .

  1. Расстояние между узлами i и j равно элементу dij в матрице Dn.

  2. Промежуточные узлы пути от узла i до узла j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i → j → k. Если далее sik = k и ski = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

3. Численное решение показательного примера

Найдем для сети, показанной на рисунке 5, кратчайшие пути между любыми двумя узлами. Расстояния между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3,5) ориентировано, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны.


Шаг 0. Начальное решение матрицы D0 и S0 строятся непосредственно по заданной схеме

сети. Матрица D0 симметрична, за исключением пары элементов d35 и d53, где d35 = ∞ (поскольку невозможен переход от узла 5 к узлу 3).

рис. 8

D0

1

2

3

4

5

1

100

30

2

100

20

15

3

30

20

10

4

15

10

50

5

60

50


S0

1

2

3

4

5

1

2

3

4

5

2

1

3

4

5

3

1

2

4

5

4

1

2

3

5

5

1

2

3

4


Шаг 1. В матрице D0 выделены ведущие строка и столбец (k=1) (рис. 8). После этого каждый элемент проверяется с помощью треугольного оператора. Таким образом, чтобы на основе матриц D0 и S0 получить матрицы D1 и S1, выполняем следующие действия:

  1. проверяем d32 > d31 + d12 = 20 > 30 + 100 = 20 > 130 если условие принимает истину, то устанавливаем S32 = 1 ,а если нет тогда все так и остается.

Матрицы D1 и S1 имеют следующий вид (см. рис. 9):

рис. 9

D1

1

2

3

4

5

1

100

30

2

100

20

15

3

30

20

10

4

15

10

50

5

60

50


S1

1

2

3

4

5

1

2

3

4

5

2

1

3

4

5

3

1

2

4

5

4

1

2

3

5

5

1

2

3

4


Шаг 2. Полагаем k=2. Треугольный оператор применяется к элементам матриц D1 и S1,

Характеристики

Тип файла
Документ
Размер
295,5 Kb
Тип материала
Учебное заведение
Неизвестно

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов реферата

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6499
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее