Задача о максимальном потоке

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

ФГБОУ ВПО «Иркутский государственный университет»

Филиал в г. Братске

 

Факультет очного обучения

Кафедра информационных технологий

 

 

Исследование операций и методы оптимизации

 

 

 

Лабораторная работа № 10

«Задача о максимальном потоке»

Вариант 4

 

 

 

 

 

 

 

Выполнил: Студент		блаблабла
Проверил: ст. преподаватель кафедры ИТ

 

 

 

 

 

 

 

 

 

Задание:

Определить максимальный поток в сети при начальных значениях дуговых потоков:

 

 

 

f0=f12+ f13=2+0=2

∆1=min{c13-f13, c35-f35}=min{2-0, 4-0}=2

f’13=f13+∆1=0+2=2

f’35=f35+∆1=0+2=2

 

 

 

∆2=min{c12-f12, c23-f23, c35-f35}=min{4-2, 3-1,4-2}=2

f’12=f12+∆2=2+2=4

f’23=f23+∆2=1+2=3

f’35=f35+∆2=2+2=4

 

 

 

 

 

 

Min разрез образует дуги: {3-5}, {4-5}. Пропускная способность разреза: cmin=c35+c45=2+3=5, fmax=f0+∆1+∆2=2+2+1=5, cmin=fmax