Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информационные технологии и моделирование бизнес-процессов

Задача определения кратчайших путей в транспортных сетях

Рассмотрим задачу об определении кратчайшего расстояния от любого пункта (вершины) в другие в заданной транспортной сети.

Пусть на некоторой поверхности задана конечное число точек р1, p2, ..., pn, которые соединены дугами (связями) (р i, pj), не пересекаются. Совокупность точек и дуг, которые их соединяют, называть сетью. Сеть будем называть достаточно связным, если для любых двух точек существует путь (совокупность вершин и дуг, которые соединяют), по которому можно пройти из одной точки в другую. При этом, две точки сети называть соседними, если существует дуга, их соединяет.

Постановка задачи. Пусть задана достаточно связная сеть, каждой дуге которой, исходящий из точки ре входит в точку pj, поставленный в соответствие некоторое действительное неотъемлемое число lij - ее длину, причем lij = lji. Надо определить кратчайшие пути в сети от произвольной точки до всех остальных и указать соответствующие им расстояния.

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

Пусть

Алгоритм решения задачи. Алгоритм состоит из начального шага и общего, что повторяется m -1 раз.

Начальный шаг. У кружочка, обозначающий точку Pi, записываем ноль - характеристику этой точки, так как расстояние от точки Pi к ней самой равна нулю. Определяем соседние с Pi точки и у кружочков, которыми обозначены эти точки, записываем их характеристики, то есть 0 + lij, если Рj является соседней точкой, а на дугах ставим стрелки, направленные в сторону точки Pi. После этого отмечаем точку Pi символом +, который означает, что операция над этой вершиной завершена.

Общий шаг. Предположим, что мы уже выполнили г шагов: нашли характеристики всех точек, наименьшее количество дуг в которых от фиксированной

характеристики соседних с ней точек (кроме точки рir и меняем при необходимости их характеристики и направление стрелок.

Если же при определении характеристик соседних с Рir точек окажется, что характеристика какой-то соседней точки раньше не исчислялась, то на соответствующей дуге, исходящей из этой точки, ставим стрелку в направлении к точке рir.

Наконец, отметим, что (r + 1) - первый шаг выполнять до тех пор, пока последовательно НЕ будут перебраны все вершины сети, то есть точки р (г) (i = 1,2, ..., k).

Пример 9.2. Отыщем кратчайшие пути от всех точек до точки с номером 1 в такой сети (рис.9.1).

Решение. Начальный шаг. Точке 1 ставим в соответствие характеристику ноль и определяем характеристики точек 2, 5, 3. Эти характеристики соответственно равны 4, 15, 6. На дугах (1, 2), (1, 5), (1, 3) ставим стрелки, направленные в сторону точки 1, а саму точку 1 отмечаем символом +.

Представление сети в виде графа

Рис.9.1. Представление сети в виде графа

Шаг 1. Берем точку 2 и определяем характеристику соседней к ней точки 4. Она равна 4 + 18 = 22. Поэтому на дуге (2, 4) ставим стрелку, направленную к точке 2, а точку 2 отмечаем символом +.

Берем точку 5 и определяем характеристики ее соседних точек 4, 6, 7. Они соответственно составлять 25, 21, 23. Новая характеристика точки 4 равно 25. Поскольку 25> 22, то характеристика точки 4 остается равной 22. На дугах (5, 6 ) и (5, 7) ставим стрелки, направленные к точке 5, а точку 5 отмечаем символом +.

Далее берем точку 3 и определяем характеристику ее соседней точки 6. Она составляет 13, но для точки 6 ранее уже была определена характеристика, равная числу 21. Поэтому, поскольку 13 <21 за характеристику точки 6 примем 13, а стрелку на дуге ( 5, 6) заменяем на стрелку на дуге (3, 6), направленную к точке 3, после чего точку 3 отмечаем символом +.

Шаг 2. Берем точку 4 и определяем характеристики ее соседних точек 5, 7, 9. Они соответственно равны 32, 30, 36. Ранее исчисленные характеристики точек 5 и 7 составляют, соответственно, 15 и 23. Поскольку 32> 15 и 30> 23 , то характеристики точек 5 и 7 оставляем без изменений, то есть 15 и 23 соответственно. После этого на дуге (4, 9) ставим стрелку, направленную к точке 4, которую отмечаем символом +.

Берем точку 7 и определяем характеристики ее соседних точек 4, 8, 9, 10. Они соответственно равны 31, 29, 30, 32. Но характеристики точек 4 и 9, которые были вычислены ранее, есть 22 и 36 соответственно. Поскольку 31> 22, а 30 <36, то характеристика точки 4 остается равной 22, а характеристику точки 9 заменяем на 30. Согласно этому стрелку на дуге (4, 9) заменяем стрелкой на дуге (7, 9), направленной к точке 7. Далее на дугах (7, 8) и (7, 10) ставим стрелки, направленные к точке 7, а саму точку 7 отмечаем символом +.

Далее берем точку 6 и определяем характеристики ее соседних точек 5 и 8. Они, соответственно, составляют 19 и 23. Ранее исчисленные характеристики этих точек были, соответственно, 15 и 29. Поскольку 19> 15, а 23 <29, то характеристика 15 точки 5 остается без изменения, а характеристику точки 8 заменяем на 23 Поэтому стрелку на дуге (7, 8) заменяем стрелкой на дуге (6, 8), направленной к точке 6. Точка 6 отмечаем символом +.

Шаг 3. Берем точку 9 и определяем характеристики ее соседних точек 4, 10 и 12. Они, соответственно, равны 44, 32 и 42. Поскольку ранее вычисленные характеристики точек 4 и 10 - это значение 22 и 32 соответственно, то есть: 44> 22 и 32 = 32. Поэтому характеристики точек 4 и 10 оставляем без изменений. На дуге (9, 12) ставим стрелку в направлении к точке 9, после чего точку 9 отмечаем символом +.

Рассмотрим далее точку 10 и определим характеристики ее соседних точек 8, 9, 11, 12. Они, соответственно, будут 38, 34, 44, 47. Для точек 8, 9, 12 ранее уже были вычислены соответствующие характеристики, а именно: 23 30 42. Поэтому, поскольку 38> 23 34> 30 и 47> 42, характеристики точек 8, 9, 12 оставляем без изменений, а на дуге (10, 11) ставим стрелку в направлении к точке 10. Точка 10 отмечаем знаком +.

Берем точку 8 и определяем характеристики ее соседних точек 7, 10 и 11. Они, соответственно, равны 29, 29 и 31. Ранее для этих точек уже были вычислены характеристики: 23, 32 и 44 соответственно. Поскольку 29> 23, а 29 <32 и 31 <44, то характеристика точки 7 остается без изменения, характеристики точек 10 и 11 заменятся, соответственно, на 29 и 31, а стрелки на дугах (7, 10) и (10, 11 ) заменятся стрелками на дугах (8, 10) и (8, 11), направленными к точке 8. Точка 8 отмечаем символом +. Поскольку при этом изменилась характеристика точки 10, которая уже была отмечена символом +, то перечисляем характеристики ее соседних точек 9, 11, 12. Получим, соответственно, значение 31, 41, 44. Однако, для этих точек ранее уже были вычислены соответствующие характеристики 30 31 и 42. Поскольку 31> 30 41> 31 и 44> 42, то характеристики точек 9, 11 и 12 оставляем без изменений.

Шаг 4. Рассмотрим точку 11 и определим характеристики ее соседних точек 10 и 12. Они будут равны, соответственно, 43 и 44. Но прежде вычисленные характеристики этих точек, соответственно, равны 29 и 42. Поскольку 43> 29 и 44> 42, то старые характеристики этих точек оставляем без изменений. Точку 11 отмечаем символом +.

Наконец, берем точку 12 для ее соседних точек 10 и 11 характеристики, соответственно, равны 57 и 55. Ранее исчисленные для них характеристики, соответственно, составляют 29 и 31. Поскольку 57> 29 и 55> 31, то вычисленные ранее характеристики точек 10 и 11 оставляем без изменений. Точку 12 отмечаем символом +.

Итак, мы получили решение задачи, который показан на графе стрелками (рис. 9.2).

Решение задачи 9.2

Рис.9.2. Решение задачи 9.2

Оптимальные пути можно изобразить, указывая сначала значение характеристики вершины (расстояние до точки 1) и соответствующий путь:

Преимуществом этого метода является то, что он по сравнению с другими алгоритмами обладает большим быстродействием.

Задача распределения кредитных средств банка с минимальной величиной риска

Пусть для кредитования банк может выделить т денежных единиц средств, объем каждой из которых составляет S условных единиц. Известно, что

банк имеет возможность кредитовать п заемщиков Р1, Р2, ..., Рn. При этом для кредитования одного заемщика банк может выделить не более одного кредита, размер которого может составлять к денежных единиц средств, где k = 1, 2, ..., m. Размер кредита и заемщик составляют соответствующую величину риска. Задача состоит в таком распределении кредитов банка среди заемщиков, при котором суммарная величина риска была бы минимальной.

Оптимальное распределение кредитов среди заемщиков P1, P2, ..., Рn определяем следующим образом.

надо предоставить заемщику Р1. Суммарная величина минимального риска составляет Fn (m) единиц.

Задача оптимального распределения инвестиционных средств банка для финансирования проектов. Пусть для инвестирования проектов банк может выделить т денежных единиц средств, объем каждой из которых составляет 5 условных единиц. Известно, что банк имеет возможность вложить средства в исполнение n проектов P1, P2, ..., Pn. При этом для финансирования одного проекта банк может выделить не более одной инвестиции, размер которой может составлять к денежных единиц средств, где k = 1,2, ..., m. В зависимости от размера вложенных средств в тот или иной проект банк получает соответствующую прибыль. Задача состоит в таком распределении средств банка между проектами, при котором суммарная величина прибыли была бы наибольшей.

Оптимальный план распределения средств банка между проектами P1, P2, ..., Pn, определяем по следующему алгоритму.

надо вложить в исполнение проекта Р1.

Максимальная прибыль от распределения средств между проектами составляет Fn (m) единиц.

Оптимальное распределение задач между компьютерами сети

Пусть надо распределить т задач одинаковой сложности между и

компьютерами К1, К2, ..., Кn сети (компьютеры могут иметь неодинаковую мощность). Известно при решении задач на каждом компьютере. Задача состоит в таком распределении задач между компьютерами, чтобы общее время решения задач был минимальным.

Резюме

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

Ключевые слова

Динамическое программирование, задача о замене оборудования, условный прибыль, кратчайший путь, граф, задача о распределении средств, оптимизация распределения задач среди компьютеров сети.

 
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Региональная экономика
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее