ПРИМЕР 1. Оптимальный маршрут перевозки неупакованного груза
Таблица 1. Транспортировка неупакованного груза
|
|
|
|
|
| в
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -
| -
| -
| -
|
|
|
|
|
| -
|
|
| -
| -
|
|
|
|
| -
|
|
| -
|
| -
|
| Из
|
| -
|
|
|
|
|
| -
|
|
|
| -
|
| -
|
|
| -
| -
|
|
|
| -
| -
|
|
| -
|
| -
|
|
|
| -
| -
| -
|
|
|
|
|
Итерация 0: Исходные матрицы
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
| -µ
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
| -µ
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
| -µ
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 1:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
| -µ
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
| -µ
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 2:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
|
|
| -µ
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 3:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
| -µ
| -µ
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 4:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 5:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 6:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
Итерация 7:
| Матрица пропускных способностей
| Матрица маршрутов
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -µ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | | | | | | | | | | | | | | | |
ПРИМЕР 2. Транспортировка космического корабля
Рис. 1. Допустимые нагрузки на мосты.
|
Таблица 2. Маршруты с максимальной пропускной способностью
| Источник
| сток
| Максимальная пропускная способность
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Исходная матрица
Матрица пропускных способностей дуг
Матричное представление узлов в путях с максимальной пропускной способностью
Оптимальные решения - в табл. 3.
Таблица 3. Оптимальные решения
| источник
| сток
| путь
| Пропускная способность оптимального маршрута
|
|
|
| 2 – 4 – 7 - 13
|
|
|
|
| 3 – 6 – 4 – 7 - 13
|
|
Таблица 4. Процедура трассировки пути из узла 2 в узел 13
| из
| в
| Через узел
|
| путь
|
|
|
|
|
|
|
|
|
|
| ®
|
| ®
|
|
|
|
|
|
|
|
| ®
|
| ®
|
|
|
|
|
|
|
|
| ®
|
| ®
|
| ®
|
|
|
|
|
|
| ®
|
| ®
|
| ®
|
|
|
|
|
|
| ®
|
| ®
|
| ®
|
|
Таблица 5. Процедура трассировки пути из узла 3 в узел 13.
| из
| в
| Через узел
| путь
|
|
б
|
|
б
| 
|
