Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Задача отыскания кратчайшего пути из вершины 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 при соблюдении условий, заданных ограничениями.

Данная задача является задачей о кратчайшем пути и может быть

решена индексно – матричным методом.

3. Решение задачи.

Составим матрицу весов графа, представленного на рисунке. Эле-

мент L ij этой матрицы равен весу ребра, если вершины i и j связаны между собой ребром, и бесконечности – в противном случае. Диагональные элементы также равны бесконечности, так как граф без петель. Для наглядности в матрицу весов бесконечности записывать не будем, оставляя соответствующие им клетки пустыми.

Добавим к составленной таким образом матрице нулевую строку и

нулевой столбец, в которые будем записывать соответственно индексы столбцов и строк U i и V j (U i – расстояние от вершины 1 до вершины i, V j – расстояние от вершины 1 до вершины j). Тогда матрица весов будет иметь вид, представленный в таблице ниже.

[pic]

Для вычисления индексов выполним следующие действия:
1. Положим U 1 = V 1 = 0/
2. Значения всех заполненных клеток первой строки перенесём на соответствующие места индексов столбцов 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 (смотрите таблицу ниже)

[pic]

3. Определим недостающие индексы 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.
Следовательно,

Рекомендуем скачать другие рефераты по теме: сочинение по картине, антикризисное управление.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата