# Linear programming - min cost!

• Apr 17th 2011, 01:53 AM
tom27
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)$\displaystyle \geq 0$. 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 $\displaystyle \in$ 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$\displaystyle \in$V - {s,t},
- 0 $\displaystyle \leq$ f(e) $\displaystyle \leq$ c(e), e$\displaystyle \in$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$\displaystyle \in$V - {s,t},
- 0 $\displaystyle \leq$ f(e) $\displaystyle \leq$ c(e), e$\displaystyle \in$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?