«Управление и Оптимизация Производственного Предприятия»
|
|
|
|||||||||||||||||||||||||||||||||
|
Основы теории принятия решениий Учебное пособие. Москва, 2002. 9.Теория графов и оптимизация Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).
Рис.7. Исходные данные к задаче о кратчайшем пути. Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.8). Табл.8. Исходные данные к задаче о кратчайшем пути.
Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4? Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается. Для исходных данных, представленных на рис.7 и в табл.6, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0. В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение С(4) = min {С(2) + 4 ; С(5) + 5}. Таким образом, проведена реструктуризация задачи - нахождение С(4) сведено к нахождению С(2) и С(5). В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение С(5) = min {С(3) + 2 ; С(6) + 3}. Мы знаем, что С(3) = 1. Поэтому С(5) = min {3 ; С(6) + 3}. Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3. В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение С(2) = min {С(1) + 7 ; С(3) + 5 ; С(5) + 2}. Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому С(2) = min {0 + 7 ; 1 + 5 ; 3 + 2} = 5. Теперь мы можем найти С(4): С(4) = min {С(2) + 4 ; С(5) + 5} = min {5 + 4 ; 3 + 5} = 8. Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков: 1 → 3 → 5 → 4 . Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.6) полностью решена. Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.
|
||||||||||||||||||||||||||||||||||
