Оптимизационные задачи на графах по "Экономико-математическому моделированию"

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

Требуется определить максимальный поток в сети, приведенный на рис.1, из вершины  X₁ в вершину X₆ , где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях.

рис.1.

 

Решение. В качестве начального возьмем нулевой поток, когда все z_ij=0.

Возьмем  какой-нибудь путь из X₁ в X₆ , например, m={ X₁ , X₀, X_5,X_{4 ,}X₆ } .

По этому пути можно  пропустить поток величиной не более

Получили новый поток  . При этом пропускные способности дуг пути и симметричных им дуг изменяются. Пропускные способности дуг пути уменьшаются на 1 единицу: т. е. дуга(X₄ , X₆ ) становится насыщенной, а пропускные способности дуг, симметричных дугам пути, увеличиваются на 1 единицу:

Теперь находим новый  путь из X₁ в X₆ , проходящий по ненасыщенным

дугам, например, m2={ X₁, X₀, X₂, X₃, X₆, } , определяем  

и пропускаем по этому пути поток величиной в одну единицу. Меняем

пропускные способности  дуг этого пути и симметричных им дуг:

 

Дуга (X₂ , X₃ ) становится насыщенной.

Дуга (X₁ , X₆ ) становится насыщенной.

Дуга (Х6,Х7) становится насыщенной.

Чтобы определить максимальный поток, вычитаем от пропускных спо-

собностей дуг исходной сети  измененные пропускные способ-

ности тех же дуг последней  сети.

 Получим:

Положительные значения найденных  разностей дают нам величины z_ij

потоков по соответствующим  дугам (X_i,X_j)в максимальном потоке из источника X₁ в сток X₆ .

Величина максимального  потока равна

 

 

Задача о кратчайшем пути.

Требуется определить кратчайший путь из вершины  Х1 в вершину Х6 в графе, приведенном  на рис.2, где числа на дугах означают длины этих дуг.

рис.2.

Решение.

Кратчайший путь из вершины  Х1 в вершину Х6 :

Х1      Х4     Х6 и Х1    Х3      Х6.

Длина этого пути равна: 2+2=4 или 3+1=4.

Задача о критическом  пути.

рис.3.

Требуется определить критический  путь из вершины в Х1 в вершину  Х6 в графе, приведенном на рис.3., где числа на этих дугах равны  продолжительностям соответствующих  этим дугам работ инвестиционного  проекта.

Решение. Критический путь из вершины Х1 в вершину Х6 будет  являться наибольший по длине путь:

Х1      Х3        Х2      Х7        Х6

Длина этого пути равна:

3+4+4+2=13.