 |
 |
 |
 |
|
 |
 |
74
Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4.
Руководствуясь теми же соображениями, что и на итерации 3, пометим вершину 5 числом m
5
=3 (рис.
3.9). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными
вершинами является вершина 6. Из чего определяем
? = min{
с
~
4,6
,
с
~
5,6
}=2 и после преобразования
имеем
с
~
4,6
=
3,
с
~
5,6
=
0.
Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом
m
6
=5 (см. рис. 3.10). Поскольку мы отметили конечную вершину маршрута, то алгоритм завершен и мы
можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6).
Следует также добавить, что если бы наш выбор на итерациях 3 и 5 был иным, то мы получили бы
альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет несколько решений.
КЛЮЧЕВЫЕ ПОНЯТИЯ
Транспортная таблица
Метод северо-западного угла.
Потенциал.
Цепочка преобразования плана.
Граф (ориентированный и неориентированный).
Ребра и вершины.
Путь и контур.
Цепь и цикл.
Связность.
Дерево.
Частичный граф.
Транспортная сеть.
Поток.
Линейная сетевая задача.
Остов сети.
Опора потока.
Невырожденный поток.
Задача о кратчайшем пути.
Алгоритм Минти.
КОНТРОЛЬНЫЕ ВОПРОСЫ
3.1. Какие специфические свойства позволяют выделить транспортные задачи в отдельный класс из
множества задач линейного программирования?
3.2. Опишите метод построения допустимого плана транспортной задачи.
3.3. Сколько ненулевых элементов должен содержать невырожденный базисный план транспортной
задачи?
3.4. Сформулируйте критерий оптимальности для допустимого плана транспортной задачи.