Математические методы в организации транспортного процесса

Х
8
Х 6
- Построение математической модели.
Пусть G(A, U) – граф, где A – множество вершин, означающих объекты (базу – вершина 1, а магазины – вершины 2, 3, 4, 5, 6, 7, 8), U – множество рёбер, означающих возможную связь между двумя вершинами. Каждому ребру поставлено в соответствие некоторое число L ij (i, j = 1, 2,…, 8 – вес ребра (расстояние между двумя вершинами).
Задача отыскания кратчайшего пути из вершины i в вершину j заключается в минимизации целевой функции:

Y = L i X ij ,
где X ij = 1, если путь проходит из вершины i в вершину j,
X ij = 0, в противном случае.
Данная функция определяет длину между заданной начальной и конечной вершинами.
При этом должны выполняться следующие условия:

(X ij – X ji) = 0, i = 2, 3,…,m – 1
(т. е. для любой вершины i, исключая начальную и конечную, число путей, входящих в эту вершину, равно чису путей, выходящих из неё);

(X 1j – X j1) = 1.
(т. е. в последнюю вершину входит на один путь больше, чем выходит);

(X mj – X jm) = 1.
(т. е. количество путей, входящих в вершину 1, превышает на единицу число путей, выходящих из неё).
Необходимо определить такие значения X ij, равные 0 или 1, которые
доставят минимум целевой функции Y при соблюдении условий, заданных ограничениями.
Данная задача является задачей о кратчайшем пути и может быть
решена индексно – матричным методом.
- Решение задачи.
Составим матрицу весов графа, представленного на рисунке. Эле-
мент L ij этой матрицы равен весу ребра, если вершины i и j связаны между собой ребром, и бесконечности – в противном случае. Диагональные элементы также равны бесконечности, так как граф без петель. Для наглядности в матрицу весов бесконечности записывать не будем, оставляя соответствующие им клетки пустыми.
Добавим к составленной таким образом матрице нулевую строку и
нулевой столбец, в которые будем записывать соответственно индексы столбцов и строк U i и V j (U i – расстояние от вершины 1 до вершины i, V j – расстояние от вершины 1 до вершины j). Тогда матрица весов будет иметь вид, представленный в таблице ниже.

Для вычисления индексов выполним следующие действия:
Положим U 1 = V 1 = 0/
Значения всех заполненных клеток первой строки перенесём на
соответствующие места индексов столбцов V j и строк U i , т. е. V 2 = 8, V 3 = 10, V 4 = 10, V 7 = 12, U 2 = V 2 = 8, U 3 = V 3 = 10, U 4 = V 4 = 10, U 7 = V 7 = 12 (смотрите таблицу ниже)

Определим недостающие индексы V j. В нашем примере это индексы
V 5, V 6 и V 8. Для этого в каждом столбце, соответсвующем неизвестному индексу V j, просмотрим заполненные клетки и вычислим недостающие индексы по формуле V j = U i + L ij, если для них известны индексы U i.
Для столбца, соответствующего индексу V 5, этими элементами будут L 4, 5 = 16 и L 7, 5 = 25. Значения U 4 и U 7 известны: U 4 = 10, U 7 = 12.
Следовательно,
V 5 = min(U 4 + L 4, 5 = 10 + 16 = 26; U 7 + L 7, 5 = 12 + 25 = 37) = 26.
Для столбца, соответствующего индексу V 6, ими будут L 2, 6 = 7, L 3, 6 = 17, L 7, 6 = 18. Значения индексов U 2, U 3, U 7 известны: U 2 = 8, U 3 = 10, U 7 = 12. Следовательно,
V 6 = min(U 2 + L 2, 6 = 8 + 7 = 15; U 3 + L 3, 6 = 10 + 17 = 27;
U 7 + L 7, 6 = 12 + 18 = 30) = 15.
Для столбца, соответствующего индексу V 8, ими будут L 5, 8 = 17, L 6, 8 = 13, L 7, 8 = 19. Значения индексов U 5, U 6, U 7 известны: U 5 = 26, U 6 = 15, U 7 = 12. Следовательно,
V 8 = min(U 5 + L 5, 8 = 26 + 17 = 43; U 6 + L 6, 8 = 15 + 13 = 28;
U 7 + L 7, 8 = 12 + 19 = 31) = 28.
Запишем их в строку V i (смотрите таблицу ниже).
Все индексы найдены. Проверим полученное решение на
оптимальность, т. е. выполнение условия L ij >= V j – U i для каждой заполненной клетки матрицы.

Для всех заполненных клеток условие L ij >= V j – U i соблюдается. Полученное решение является оптимальным. Следовательно, минимальными расстояниями от вершины 1 до всех остальных будут:
V 2 = 8, V 3 = 10, V 4 = 10, V 5 = 26, V 6 = 15, V 7 = 12, V 8 = 28.
Определим кратчайший путь от вершины 1 до вершины 5. Для этого в столбце 5 найдём элемент, значение которого равно разности индексов столбца и строки L ij = V j – U i :
L 4, 5 = V 5 – U 4 = 26 – 10.
L 4, 5 – последнее звено пути и, соответственно, вершина 4 – предпоследняя.
И далее, в столбце 4 определим:
L 1, 4 = V 4 – U 1 = 10 – 0 = 10.
L 1, 4 – первое звено пути, так как вершина 1 является начальной фиксированной.
Таким образом, имеем минимальный путь от вершины 1 до вершины 5, проходящий через вершины 1, 4, 5, длина которого равна 26.
----
СЕВЕРО-ЗАПАДНЫЙ ЗАОЧНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
__________________________________________________
КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
КУРСОВАЯ РАБОТА
ПО
ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
Выполнил:
Студент 2 курса заочного отделения
Калинкин Степан Валерьевич
Факультет: ЭМиАТ
Специальность: 1502
Зачётная книжка: № 96 – 0084
__________________________________________________
САНКТ-ПЕТЕРБУРГ 2001