Results 1 to 14 of 14

Math Help - Linear Programming on a Network

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    22

    Linear Programming on a Network

    OK, goods are transported from both docks m and n to depots a b and c (see attached image). m can handle up to twice as many goods as n and the capacity of each depot is equal. I have the distances between each point and my task is to use linear programming to minimize the total distance traveled.
    My problem is I don't know how linear programming can be adapted to this kind of problem with both capacities and distances. Can anyone start me off please?
    Attached Thumbnails Attached Thumbnails Linear Programming on a Network-lp.bmp  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rubberduckzilla View Post
    OK, goods are transported from both docks m and n to depots a b and c (see attached image). m can handle up to twice as many goods as n and the capacity of each depot is equal. I have the distances between each point and my task is to use linear programming to minimize the total distance traveled.
    My problem is I don't know how linear programming can be adapted to this kind of problem with both capacities and distances. Can anyone start me off please?
    The objective is to minimise the total (or may be the average) distance that goods are transported. The link capacities give you the constraints.

    There does appear to be something missing, like the arrival rate/quantity of goods at the docks. Otherwise this is a standard LP problem.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    22
    That's all the information I'm given. I'm allowed to make simplifying assumptions so there may be further restrictions or practical considerations. But I don't know what these would be.
    Edit:
    If i say the distances are:
    m-a=94
    m-b=126
    m-c=208
    n-a=117
    n-b=258
    n-c=181
    wouldn't there be a variable for each road/edge? is that still solvable or am i over-complicating it?
    Last edited by Rubberduckzilla; January 17th 2010 at 02:37 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rubberduckzilla View Post
    That's all the information I'm given. I'm allowed to make simplifying assumptions so there may be further restrictions or practical considerations. But I don't know what these would be.
    Edit:
    If i say the distances are:
    m-a=94
    m-b=126
    m-c=208
    n-a=117
    n-b=258
    n-c=181
    wouldn't there be a variable for each road/edge? is that still solvable or am i over-complicating it?
    The flows along each edge are the variables. then the objective is:

    O   = \sum_{i,k} f_{i,k} d_{i,k}

    where f_{i,k} denotes the flow from source i to sink k and d_{i,k} is the distance from source i to sink k. The f 's are the variables.

    But I am still suspicious that there is missing data or information.

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    22
    I'm also told that 'the company ships hundreds of goods crates every month to docks m and n' if that helps..
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rubberduckzilla View Post
    I'm also told that 'the company ships hundreds of goods crates every month to docks m and n' if that helps..
    Not really since if the quantity of goods is less than the capacity of both m and a the flow will all be along the link m-a, only if the capacity of one or the other will any other link be utilised. How the flow distributes itself across the links depends on the size of the flow.

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2009
    Posts
    22
    Can I get by this by making the total goods shipped to the docks a variable, G? Would it still be solvable via LP?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rubberduckzilla View Post
    Can I get by this by making the total goods shipped to the docks a variable, G? Would it still be solvable via LP?
    That might be possible but what will you do about the objective? If you do that the above objective will be minimised when G=0.

    CB
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    May 2009
    Posts
    22
    If I leave it in terms of G then after solving I should be able to input a value for G when needed and find each of the variables. This makes the model useful to the company because G could change each month. Am I right?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rubberduckzilla View Post
    If I leave it in terms of G then after solving I should be able to input a value for G when needed and find each of the variables. This makes the model useful to the company because G could change each month. Am I right?
    I doubt you can easily find a general solution for such a LP problem. With a properly set up model with G as a parameter a run can be done each month to find the optimal flow once G is known. So in a sense a properly formulated model is the general solution that you require.

    CB
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Is not this problem solved more easily by the gready algorithm?

    CB
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    May 2009
    Posts
    22
    Quote Originally Posted by CaptainBlack View Post
    Is not this problem solved more easily by the gready algorithm?

    CB
    I was told I had to use LP, but yes, that probably would be a much more suitable method.


    Quote Originally Posted by CaptainBlack View Post
    The flows along each edge are the variables. then the objective is:

    O   = \sum_{i,k} f_{i,k} d_{i,k}

    where f_{i,k} denotes the flow from source i to sink k and d_{i,k} is the distance from source i to sink k. The f 's are the variables.

    But I am still suspicious that there is missing data or information.

    CB
    Minimizing
    O   = \sum_{i,k} f_{i,k} d_{i,k}
    would be the same as maximizing
    O   = -\sum_{i,k} f_{i,k} d_{i,k}
    right?
    but that would mean there are no negatives in the objective row, which is a problem.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Rubberduckzilla View Post
    I was told I had to use LP, but yes, that probably would be a much more suitable method.



    Minimizing
    O = \sum_{i,k} f_{i,k} d_{i,k}
    would be the same as maximizing
    O = -\sum_{i,k} f_{i,k} d_{i,k}
    right?
    but that would mean there are no negatives in the objective row, which is a problem.
    Yes maximising what you give is the same as minimising the earlier expression. I'm not clear why this would be a problem is it something to do with your solver?

    CB
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    May 2009
    Posts
    22
    Quote Originally Posted by CaptainBlack View Post
    Yes maximising what you give is the same as minimising the earlier expression. I'm not clear why this would be a problem is it something to do with your solver?

    CB
    I'm using simplex method to solve, is there a more suitable way I'm not aware of?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Programming on a network
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 14th 2010, 08:18 PM
  2. Replies: 1
    Last Post: November 17th 2008, 03:18 AM
  3. Linear Programming
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: May 6th 2008, 04:31 AM
  4. linear programming
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 6th 2006, 07:29 AM
  5. [SOLVED] Rain Gage Network Linear Algebra?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: September 7th 2005, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum