Network Flow: Can I change edge capacity while solving for max flow?

I want to know if I can change edge capacities in a network flow problem while solving it.

I have a supply/demand problem with goods A, B, and AB. A un开发者_C百科it of demand for A will take one unit of A, B will take B, and AB will take one unit of AB or a unit of A and a unit of B. Given a list of supply and demand for each good, I want to figure out if there enough goods on hand to satisfy the demand.

So I my net work looks like this:

Let sX be supply of X.

Let dX be demand of X.

All flows go from left to right.

You can see that if I push x units of A, I have subtract x from the capacity going to (A+B). Similarly if I 'undo' a push, I have add capacity back to (A+B). So I have do this during the algorithm. Does that mess up the algorithm?

This is not a network flow problem. Suppose that sA = 10, sB = 10, dA = 10, dB = 10, dAB = 10. From the graph you can supply 10 As, Bs, and A+Bs, and therefore meet the demand. But in fact you need 20 As and 20 Bs to supply that need.

I do not know of a way for a simple flow network to represent the condition that you need the flow in one place to match the flow in another.

What you're describing is an interesting problem that I am sure has been studied, but I don't know what you call it.

This can be solved by turning it into a linear programming problem. See http://en.wikipedia.org/wiki/Linear_programming if you are not familiar with linear programming problems. Consider your simple case. You can start with 6 variables:

1. x is the flow from input A to output A.
2. y is the flow from input B to output B.
3. z is the flow from input AB to output AB.
4. w is the flow from A into A + B.
5. w' is the flow from B into A + B.
6. w'' is the flow from A + B into AB.

Of course the last 3 are all equal to each other. So we have 4 variables. (If we didn't note this we'd have more equations.) Now add the following inequalities:

1. 0 ≤ x
2. 0 ≤ y
3. 0 ≤ z
4. 0 ≤ w
5. x + w ≤ sA
6. y + w ≤ sB
7. z ≤ sAB
8. x ≤ dA
9. y ≤ dB
10. z + w ≤ dAB

This is a set of inequalities that says we're producing stuff, we aren't using more than our supply and we aren't creating more than the final demand for any particular thing. This defines our "feasible region".

Next we need an objective function, the thing that we're trying to maximize. The obvious choice is that we want to maximize the amount that we produce. So we want to maximize x + y + z + w.

The answer to your original question can then be found as follows. Given a set of available inputs, and available outputs, solve the above linear programming problem to optimize production. You are able to satisfy production goals if and only if the optimum level of production is dA + dB + dAB. And better yet, the solution you will get will tell you exactly how to satisfy production.