08. Задача о максимальном потоке
Как (т. е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (Рис. 8.8).
Рис. 8.8. Исходные данные к задаче о максимальном потоке
Исходные данные о транспортной системе, например, внутризаводской, приведенные на Рис. 8.8, можно также задать таблицей (Табл. 8.5).
Таблица 8.5
Исходные данные к задаче о максимальном потоке
|
Пункт |
Пропускная |
|
|
0 |
1 |
2 |
|
0 |
2 |
3 |
|
0 |
3 |
1 |
|
1 |
2 |
4 |
|
1 |
3 |
1 |
|
1 |
4 |
3 |
|
2 |
3 |
1 |
|
2 |
4 |
2 |
|
3 |
4 |
2 |
Решение задачи о максимальном потоке может быть получено из следующих соображений.
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.
Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (Табл. 8.6).
Таблица 8.6
Решение задачи о максимальном потоке
|
Пункт |
План |
Пропускная |
|
|
0 |
1 |
2 |
2 |
|
0 |
2 |
3 |
3 |
|
0 |
3 |
1 |
1 |
|
1 |
2 |
0 |
4 |
|
1 |
3 |
0 |
1 |
|
1 |
4 |
2 |
3 |
|
2 |
3 |
1 |
1 |
|
2 |
4 |
2 |
2 |
|
3 |
4 |
2 |
2 |
| < Предыдущая | Следующая > |
|---|
