Математика/5. Математическое моделирование

к.т.н. Дунаевская О.И.

Национальный технический университет

«Харьковский политехнический институт», Украина

Расчет матрицы стоимостей оптимальных маршрутов для совокупности пар (поставщик - потребитель)

При решении транспортных задач конструктивно используется матрица «расстояний» для любых пар «поставщик - потребитель» [1]. При этом предполагается, что для каждой пары рассчитан оптимальный в смысле выбранного критерия маршрут.

Задачу расчета матрицы оптимальных маршрутов в системе «поставщик - потребители» удобно сформулировать и решать в терминах теории графов. Введем граф, вершин которого есть пункты поставки и потребления, а также точки пересечения магистралей. Участкам магистралей, соединяющих разные пункты, соответствуют дуги графа, которые оцифрованы значениями «расстояний» между этими пунктами. Перенумеруем все вершины графа и в соответствии с этой нумерацией введем - длину дуги, соединяющей непосредственно - ю и - ю, , вершины графа. Пусть - матрица длин этих дуг, . Найдем теперь матрицу кратчайших двухзвенных путей между всеми парами вершин графа. Пусть для некоторой пары вершин существует несколько двухзвенных путей: , , …, . Для отыскания кратчайшего из них с использованием матрицы расстояний введем специальную операцию «перемножения» матриц следующим образом: для двух произвольных квадратных матриц и , , зададим их произведение по правилу:

, ,, (1)

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

Поясним процедуру расчета матрицы кратчайших двухзвенных путей простым примером. Пусть матрица длин однозвенных путей , нормированная максимальным значением длины, имеет вид

.

Рассчитаем матрицу кратчайших двухзвенных путей

.

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

.

При этом, например, оптимальных двухзвенный путь из пункта 2 в пункт 3 проходит через промежуточный пункт 4, то есть маршрут имеет вид . С другой стороны, если для какой-либо пары элементов никакой двухзвенный маршрут не лучше однозвенного, то в матрице это обращается значком «-».

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

При этом

.

Матрице оптимальных расстояний для трехзвенных маршрутов соответствует матрица промежуточных пунктов, которая имеет вид:

.

Из матрицы следует, что например, оптимальный трехзвенный путь из пункта 1 в пункт 6 имеет промежуточный пункт 5. Однако, для попадания из начального пункта 1 в промежуточный пункт 5 в соответствии с необходимо использовать промежуточный пункт 3. Поэтому, оптимальный трехзвенный маршрут из 1в 6 имеет вид . Если в матрице какому-либо элементу соответствует значение «-», это означает, что не существует никакого трехзвенного маршрута, более короткого, нежели двухзвенный, найденный ранее. Заметим, что в полученной матрице уже нет ни одного элемента, равного . Это означает, что между любыми двумя пунктами существует маршрут, составленный не более чем из трех звеньев.

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

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

Литература:

1. Просветов Г.И. Математические методы в логистике. Задачи и решения. / Г.И. просветов. – М.:Альфа-Пресс, 2008. – 304с.

2. Дунаевская О.И. Задача транспортной логистики со случайной стоимостью перевозок / О.И. Дунаевская, Л.Г. Раскин // Вестник Харьковского национального автомобильно - дорожного университета. – Харьков.: 2007. – Вып. 37. – с.87-89.