АльфаОмега

база знаний!

Приветствую Вас, Гость | RSS
...
Форма входа
Логин:
Пароль:


1с бухгалтерия [12]Английский язык [6]
Банковское дело [22]Безопасность жизнедеятельности [12]
Биология [3]Бухгалтерское дело [166]
Бухгалтерский учет [129]Информатика [91]
Инновационный менеджмент [12]История экономики [80]
История экономических учений [162]Концепции современного естествознания [54]
Конфликтология [18]Культурология [45]
Линейная алгебра [72]Линейное программирование [7]
Макроэкономика [43]Маркетинг и реклама [68]
Математическая статистика [21]Математический анализ [50]
Менеджмент [141]Микроэкономика [39]
Мировая экономика [85]Моделирование портфеля ценных бумаг [19]
Основы предпринимательства [44]Отечественная история [39]
Политология [27]Правоведение [74]
Прикладные программы [21]Психология и педагогика [159]
Региональная экономика [81]Социология [57]
Теория вероятностей [53]Теория оптимального управления [3]
Управление организацией [35]Физическая культура [42]
Философия [157]Финансовый анализ [99]
Финансы и кредит [236]Численные методы [8]
Эконометрика [15]Экономика предприятия [70]
Экономико математическое моделирование [48]Экономическая география [69]
Экономическая теория [99]Экономическая политика [23]
Юриспруденция [20]Другие предметы [39]

Кратчайший путь



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

Рассмотрим пример. Задан неориентированный граф, имеющий 16 вершин.

Как можно попасть из вершины 1 в вершину 16?  Здесь можно воспользоваться путём 1→2→3→4→8→12→16, а можно1 →2→6→10→11→15→16. Если на каждом шаге мы идем только вверх или вправо, то всего в этом примере имеются 20 возможных путей из вершины 1 в вершину 16. Иногда может быть выгодно разрешить двигаться не только вверх или вправо. В этом случае число путей увеличится. Так, возможен вариант 1→2→6→5→9→10→11→12→16. Нашей задачей является нахождение кратчайшего пути, ведущего из одной вершины в другую.

Получили следующую математическую задачу.

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

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

В частности, задача о кратчайшем пути возникает при рассмотрении задачи об использовании оборудования.

Рассмотрим пример. Пусть наше производство в течение года нуждается в автомобиле. Нам представляются различные возможности. Например, мы можем арендовать автомобиль на определенный срок по определенной стоимости. Мы можем купить автомобиль, какое-то время им пользоваться, а затем продать, и т.д. Ставится задача разработать самый дешевый план использования оборудования на указанный период времени. Здесь вершинам графа соответствуют моменты времени, а каждой имеющейся возможности (в каждый момент времени) будет соответствовать ребро графа. Может быть несколько ребер, соединяющих одну и ту же пару вершин. За длину ребра нужно принять стоимость выбранного варианта. Можно проиллюстрировать сказанное следующим рисунком. Здесь точки на прямой соответствуют последовательным моментам времени, отрезки и дуги соответствуют наличию ребра (варианта), аij стоимость соответствующего варианта использования автомобиля на интервале времени [i,j].

Алгоритм расстановки меток.

Нахождение длин кратчайших путей, выходящих из вершины А, будем производить, используя алгоритм расстановки меток. В процессе работы алгоритма каждой вершине будет приписано некоторое число, в дальнейшем эти числа мы будем называть метками. Если какой-то вершине приписана метка, равная d, то это значит, что существует путь из вершины А в эту вершину длиной d. Если найден более короткий путь, то значение метки заменяется на меньшее. Метки могут быть временными или постоянными. Постоянные метки будем отмечать значком *, не отмеченные таким значком - временные. Например, li - временная, а l*i- постоянная. Метка становится постоянной в том случае, если она соответствует самому короткому пути из вершины А в данную вершину. Задача решена, если все метки стали постоянными.

Итак, выпишем шаги нашего алгоритма.

/ шаг. Каждой вершине i приписываем некоторое число li, равное длине самого короткого известного на данный момент пути из вершины А в данную вершину. Вначале это lA =0, a l2 = l3 =…= lB =∞Не ограничивая общности можно считать, что вершине А соответствует вершина с номером l, а вершине В - вершина с самым большим номером. На данном этапе все метки временные.

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

li+aij < lj        (3.1)

Для тех вершину, для которых оно справедливо, заменяем метку lj на li + aij, эта величина соответствует пути из А в вершину i длиной li, а затем по ребру aij в вершину j. Метка li становится постоянной.

Задача решена, если все метки постоянные. Если же среди меток есть временные, то повторяем шаг 2.

Длина кратчайшего пути из А в В равна lB*

Особенности нахождения кратчайшего пути при наличии рёбер отрицательной длины.

В реальных экономических задачах могут возникать ситуации, когда некоторые ребра имеют отрицательную длину. Например, при перевозке попутного груза из i в j можно не только не тратить денег на переезд, но и получать прибыль. В этом случае, необходимо определить наличие в графе циклов отрицательной длины. Если таких циклов нет, то алгоритм можно применять практически без изменений. Отличие состоит в том, что может измениться метка со значком *. В графе без отрицательных длин ребер такие метки мы называли постоянными, и они не могли меняться. Здесь такая метка может измениться. В этом случае мы убираем у нее и продолжаем работу алгоритма. Если же в графе существует цикл отрицательной длины (см. чертеж), то решения может не существовать. Рассмотрим пример, показывающий, как это может произойти.

На рисунке видно, что длина пути из А в В, состоящего из одного ребра, равна 10. Если же сначала пойти из А в С, затем N раз пройти по циклу CDE, а лишь потом пойти в В, то длина пути будет равна (40 - 3N). Попадая на цикл, можем прокручиваться В по нему неоднократно, получая тем самым длину пути из А в В меньше любого наперед заданного числа.

 




Похожие материалы
Система национальных счетов (СНС)
Установление официального курса евро
Ренты с платежами в середине периодов
Подсчет ВВП в развитых странах
Роль финансов и кредита в процессе общественного воспроизводства

Категория: Экономико математическое моделирование | Добавил: irish-lu
Просмотров:1758 | Загрузок: 472 | Рейтинг: 0.0/0
  
Всего комментариев: 0
 
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Меню сайта
Шпаргалки

>Шпаргалки

ПОДЕЛИТЬСЯ