Linear Programming on a Network

**Rubberduckzilla** · January 16th 2010, 04:26 AM

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?

**CaptainBlack** · January 17th 2010, 02:17 AM

Originally Posted by Rubberduckzilla

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

**Rubberduckzilla** · January 17th 2010, 03:25 AM

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?

**CaptainBlack** · January 17th 2010, 04:22 AM

Originally Posted by Rubberduckzilla

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

**Rubberduckzilla** · January 17th 2010, 04:51 AM

I'm also told that 'the company ships hundreds of goods crates every month to docks m and n' if that helps..

**CaptainBlack** · January 17th 2010, 09:04 AM

Originally Posted by Rubberduckzilla

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

**Rubberduckzilla** · January 17th 2010, 09:08 AM

Can I get by this by making the total goods shipped to the docks a variable, G? Would it still be solvable via LP?

**CaptainBlack** · January 17th 2010, 09:14 AM

Originally Posted by Rubberduckzilla

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

**Rubberduckzilla** · January 17th 2010, 09:19 AM

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?

**CaptainBlack** · January 17th 2010, 09:24 AM

Originally Posted by Rubberduckzilla

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

**CaptainBlack** · January 17th 2010, 11:14 AM

Is not this problem solved more easily by the gready algorithm?

CB

**Rubberduckzilla** · January 17th 2010, 10:29 PM

Originally Posted by CaptainBlack

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.

Originally Posted by CaptainBlack

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.

**CaptainBlack** · January 18th 2010, 12:50 AM

Originally Posted by Rubberduckzilla

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

**Rubberduckzilla** · January 18th 2010, 01:13 AM

Originally Posted by CaptainBlack

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?

Thread: Linear Programming on a Network

LinkBack

Thread Tools

Display

Linear Programming on a Network

Similar Math Help Forum Discussions

Linear Programming on a network

Linear Programming and Operational Research Question, Dynamic Programming

Linear Programming

linear programming

[SOLVED] Rain Gage Network Linear Algebra?

Search Tags