Page 24 - 4517

ЛАБОРАТОРНА РОБОТА № 8
ЗНАХОДЖЕННЯ ПОТОКУ МІНІМАЛЬНОЇ ВАРТОСТІ
(6 год.)

Мета: одержання практичних навичок знаходження потоку
мінімальної вартості.

Теоретичні відомості

Будемо розглядати мережу, в якій кожній дузі A
ij
поставлена у відповідність дугова вартість c , тобто вартість
ij
доставки одиниці потоку із вузла N в N по дузі A . Необхідно
i j ij
знайти потік із джерела в стік, який має задану величину і
набуває мінімальної вартості.
Теоретичні відомості викладені в конспекті лекцій [1] на
сторінках 145 – 152.

Завдання до лабораторної роботи

Нехай у мережі, яка подана на рис. А.1, перше число біля
кожної дуги вказує на її пропускну здатність b , а друге число –
ij
її дугова вартість c . Всі дуги не орієнтовані. Необхідно знайти
ij
потік величини 2 (v  ) мінімальної вартості.
2
Приклад графа мережа з вказаними пропускними
можливостями дуг і дуговими вартостями для варіанту № 33
зображено на рисунку 8.1. Дугова вартість c визначається з
ij
формули c  b  1.
ij ij

22