Thread: Linear programming - min cost!

Hello everyone!

I have some questions how to write a linear program which can find min cost in network.
I have a network N=(V,E,c,s,t) which is fitted with costs (p) across edges p(e) . f is s-t flow in network N. Cost of flow f, p(f), is defined as p(f)=sum (p(e)*c(e) where e E.

I must describe a procedure how to find the max flow with min cost.

At first I write a linear program for max flow:

max F (F is a value of s-t flow, sum of flows)

constraints:
- sum of inputs and outputs flows in s is F,
- sum of inputs and outputs flows in t is -F,
- sum of inputs and outputs flows in v is 0 (v V - {s,t},
- 0 f(e) c(e), e E.

Then I must write a linear program for min cost and here is some things that I do not understand. I write something like this:

min ???

constraints:
- sum of inputs and outputs flows in s is F,
- sum of inputs and outputs flows in t is -F,
- sum of inputs and outputs flows in v is 0 (v V - {s,t},
- 0 f(e) c(e), e E,
- sum of s-t flows is max F

I do not understand how to define criterion function in this case. Just sum of p(e)*c(e) is not ok I think.
And the second question is: in case if all costs and capacities is 1, what is happen? Is the answer that then we search the shortest path ok?

Thank in advance.

Tom