Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
Теоретическая часть:
1. Стоимость доставки единицы потока по дуге?
2. Понятие графа модифицированных стоимостей?
3. Формулировка постановки задачи?
4. Нахождение потока заданной величины минимальной стоимости?
5. Алгоритм Басакера-Гоуэна?
Практическая часть:
Для сети (смотреть практическую работу №3) построить поток заданной мощности в соответствии с вариантом минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в соответствии с вариантом.
| Вариант №1
| Вариант №2
| Вариант №3
|
| SA — 7
SC — 8
SD — 9
AB — 4
AC — 5
BC — 2
BT — 8
CD — 3
CE — 7
DE — 6
ET — 4
CT — 5
| SA — 6
SC — 8
SD — 3
AB — 4
AC — 4
BC — 2
BT — 7
CD — 3
CE — 6
DE — 6
ET — 4
CT — 5
| SA — 7
SC — 9
SD — 2
AB — 4
AC — 5
BC — 4
BT — 8
CD — 7
CE — 7
DE — 6
ET — 2
CT — 4
|
| Вариант №4
| Вариант №5
| Вариант №6
|
| SA — 2
SC — 6
SD — 9
AB — 5
AC — 6
BC — 7
BT — 8
CD — 3
CE — 7
DE — 4
ET — 4
CT — 3
| SA — 6
SC — 3
SD — 4
AB — 4
AC — 5
BC — 2
BT — 5
CD — 3
CE — 7
DE — 6
ET — 7
CT — 9
| SA — 4
SC — 8
SD — 2
AB — 4
AC — 5
BC — 9
BT — 8
CD — 7
CE — 7
DE — 2
ET — 4
CT — 5
|
| Вариант №7
| Вариант №8
| Вариант №9
|
| SA — 3
SC — 4
SD — 9
AB — 6
AC — 8
BC — 6
BT — 4
CD — 3
CE — 7
DE — 3
ET — 7
CT — 9
| SA — 8
SC — 9
SD — 6
AB — 8
AC — 2
BC — 5
BT — 5
CD — 4
CE — 7
DE — 6
ET — 7
CT — 6
| SA — 6
SC — 3
SD — 5
AB — 4
AC — 5
BC — 2
BT — 5
CD — 9
CE — 7
DE — 5
ET — 7
CT — 9
|
| Вариант №10
| Вариант №11
| Вариант №12
|
| SA — 7
SC — 5
SD — 9
AB — 5
AC — 3
BC — 7
BT — 8
CD — 9
CE — 7
DE — 8
ET — 4
CT — 3
| SA — 3
SC — 6
SD — 9
AB — 6
AC — 6
BC — 8
BT — 8
CD — 6
CE — 7
DE — 2
ET — 4
CT — 5
| SA — 2
SC — 7
SD — 7
AB — 9
AC — 3
BC — 5
BT — 7
CD — 3
CE — 4
DE — 4
ET — 7
CT — 8
|
| Вариант №13
| Вариант №14
| Вариант №15
|
| SA — 4
SC — 3
SD — 6
AB — 8
AC — 3
BC — 7
BT — 6
CD — 9
CE — 5
DE — 8
ET — 7
Вариант №16
| SA — 5
SC — 5
SD — 6
AB — 5
AC — 7
BC — 7
BT — 8
CD — 8
CE — 7
DE — 8
ET — 4
Вариант №17
| SA — 2
SC — 4
SD — 8
AB — 2
AC — 9
BC — 4
BT — 8
CD — 9
CE — 7
DE — 2
ET — 7
Вариант №18
|
| SA — 7
SC — 4
SD — 8
AB — 5
AC — 3
BC — 7
BT — 2
CD — 9
CE — 7
DE — 8
ET — 4
CT — 6
| SA — 6
SC — 3
SD — 9
AB — 4
AC — 8
BC — 6
BT — 8
CD — 9
CE — 7
DE — 7
ET — 6
CT — 3
| SA — 5
SC — 5
SD — 7
AB — 6
AC — 7
BC — 7
BT — 9
CD — 5
CE — 9
DE — 8
ET — 4
CT — 2
|
| Вариант №19
| Вариант №20
| Вариант №21
|
| SA — 2
SC — 6
SD — 7
AB — 5
AC — 6
BC — 7
BT — 5
CD — 3
CE — 7
DE — 6
ET — 4
CT — 3
| SA — 8
SC — 5
SD — 9
AB — 4
AC — 4
BC — 9
BT — 8
CD — 4
CE — 7
DE — 4
ET — 8
CT — 7
| SA — 6
SC — 6
SD — 5
AB — 5
AC — 6
BC — 7
BT — 8
CD — 9
CE — 7
DE — 8
ET — 4
CT — 6
|
| Вариант №22
| Вариант №23
| Вариант №24
|
| SA — 4
SC — 4
SD — 7
AB — 2
AC — 9
BC — 8
BT — 8
CD — 9
CE — 7
DE — 7
ET — 7
| SA — 2
SC — 8
SD — 8
AB — 2
AC — 4
BC — 4
BT — 6
CD — 9
CE — 7
DE — 2
ET — 9
| SA — 6
SC — 2
SD — 7
AB — 2
AC — 9
BC — 4
BT — 8
CD — 7
CE — 7
DE — 2
ET — 7
|
| Вариант №25
| Вариант №26
| Вариант №27
|
| SA — 5
SC — 5
SD — 7
AB — 5
AC — 6
BC — 7
BT — 5
CD — 5
CE — 7
DE — 6
ET — 4
CT — 3
| SA — 8
SC — 6
SD — 8
AB — 5
AC — 6
BC — 8
BT — 5
CD — 3
CE — 7
DE — 8
ET — 4
CT — 8
| SA — 2
SC — 6
SD — 7
AB — 7
AC — 6
BC — 7
BT — 5
CD — 3
CE — 7
DE — 6
ET — 7
CT — 3
|
| Вариант №28
| Вариант №29
| Вариант №30
|
| SA — 4
SC — 5
SD — 4
AB — 5
AC — 6
BC — 4
BT — 5
CD — 4
CE — 7
DE — 9
ET — 4
CT — 3
| SA — 9
SC — 5
SD — 7
AB — 9
AC — 6
BC — 7
BT — 9
CD — 5
CE — 7
DE — 9
ET — 4
CT — 3
| SA — 3
SC — 5
SD — 7
AB — 5
AC — 3
BC — 7
BT — 5
CD — 3
CE — 7
DE — 8
ET — 4
CT — 9
|
Практическая работа №5
