Реферат: Математические методы в организации транспортного процесса
Х 3
Х 2
Х 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 связаны между собой ребром, и бесконечности – в противном случае. Диагональные элементы также равны бесконечности, так как граф без петель. Для наглядности в матрицу весов бесконечности записывать не будем, оставляя соответствующие им клетки пустыми.