Maximum Flow Assumptions


Theorem 6.11 (Circulation Feasibility Conditions)



Download 1 Mb.
Page6/6
Date02.05.2018
Size1 Mb.
#47333
1   2   3   4   5   6
Theorem 6.11 (Circulation Feasibility Conditions). A circulation problem with nonnegative lower bounds on arc flows is feasible if and only if for every set S of nodes



Theorem 6.12. The feasible flow problem stated in (6.2) has a feasible solution if and only if for every subset
So, an algorithm to check feasibility works like this:
Can start with zero flow, look at infeasible arcs (xij < lij)

Increase xij to lij by finding an augmenting path from j to i.


Continue until

1. All xij  lij



2. Can't find the augmenting path you need which implies the problem is infeasible because theorem 6.11 is violated.





Download 1 Mb.

Share with your friends:
1   2   3   4   5   6




The database is protected by copyright ©ua.originaldll.com 2024
send message

    Main page