Results 1 to 1 of 1

Math Help - Linear programming - min cost!

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    15

    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)  \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 \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 \inV - {s,t},
    - 0 \leq f(e) \leq c(e), e \inE.

    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 \inV - {s,t},
    - 0 \leq f(e) \leq c(e), e \inE,
    - 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
    Last edited by tom27; April 17th 2011 at 05:01 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding linear cost function.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 6th 2010, 03:52 PM
  2. Linear Programming Help
    Posted in the Business Math Forum
    Replies: 1
    Last Post: February 20th 2010, 01:28 AM
  3. Linear Programming
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: May 30th 2009, 05:47 PM
  4. Replies: 1
    Last Post: November 17th 2008, 04:18 AM
  5. linear programming Max 5A+5B
    Posted in the Business Math Forum
    Replies: 1
    Last Post: April 13th 2008, 09:24 PM

Search Tags


/mathhelpforum @mathhelpforum